2022*2021/2+1変数母関数の畳み込みを計算する.

116

　正三角形状に非負整数を並べた配列が整った三角形であるとは,最下行以外に位置する任意の数について, そのすぐ下に位置する左右 $2$ つの数の最小値以下であることを指します.また, $n$ 段の整った三角形の整い度を,以下に示す二項係数の総積で定めます. 以下は $4$ 段の整った三角形の一例となっています.
$\begin{matrix} 0 \\ 1 & 2 \\ 1 & 5 & 2 \\ 2 & 7 & 6 & 6 \end{matrix}$
　ただし, 上から $x (\geq 1)$ 段目, 左から $y (\geq 1)$ 個目に位置する数を $a_{x, y}$ で表すものとし, $i = 0, 1, \dots$ に対し $a_{i, 0} = 0$ とします.
$\prod_{x = 2}^{n} \prod_{y = 1}^{x - 1} (\binom{a_{x, y} - a_{x - 2, y - 1}}{a_{x, y} - a_{x - 1, y}})$
$2022$ 段の整った三角形であって, 以下を満たすものすべてについて, それらの整い度の総和を求めてください.
$a_{2022, i} = 10000 (1 \leq i \leq 2022), a_{2021, 1000} = 5678$

解説
　以下, 整数の組 $(i, j)$ は $i \geq j$ を満たす正整数の組を指すものとし, $(x_{1}, y_{1}) \leq (x_{2}, y_{2})$ とは辞書式順序において $(x_{1}, y_{1})$ は $(x_{2}, y_{2})$ より後に来ないことを意味する.

　 $N = 10000, M = 10000 - 5678 = 4322$ とし, ${a_{n, m}}$ を定義し直す.

以下のように(問題文の例)左に $0$ を追加し, 下から $n (\geq 0)$ 段目, 左から $m (\geq 0)$ 個目に位置する数を $a_{n, m}$ とする.
$\begin{matrix} a_{3, 0} & a_{3, 1} & a_{3, 2} & a_{3, 3} & a_{3, 4} \\ a_{2, 0} & a_{2, 1} & a_{2, 2} & a_{2, 3} \\ a_{1, 0} & a_{1, 1} & a_{1, 2} \\ a_{0, 1} \end{matrix} = \begin{matrix} 0 & 0 & 2 & 2 & 6 \\ 0 & 1 & 5 & 6 \\ 0 & 1 & 7 \\ 2 \end{matrix}$

このとき, 非負整数 ${b_{n, m}}, {c_{n, m}}$ を以下のように定義する.

$b_{n, m} = a_{n, m} - a_{n, m - 1}$ .
$c_{n, m} = a_{n, m} - a_{n + 1, m}$ .

このとき, 問題文の最後の条件より, 以下が成立. 逆にこれを満たすとき組 $({b_{n, m}}, {c_{n, m}})$ は ${a_{n, m}}$ と一対一に対応する.

条件

$(i, j) \leq (2021, 2021)$ について,
$b_{i, 1} + b_{i, 2} + \dots + b_{i, j} + c_{i - 1, j} + c_{i - 2, j} + \dots + c_{j - 1, j} = N .$
$c_{999, 1000} = M$ .

そして整い度は, ${b_{i, j}}, {c_{i, j}}$ を用いて以下のように表せる.

$({b_{n, m}}, {c_{n, m}})$ に対して整い度は以下で表される.
$\prod_{(i, j) \leq (2021, 2021)} (\binom{b_{i, j} + c_{i - 1, j}}{b_{i, j}})$

これの総和 $S$ を変数 $x_{i, j} ((i, j) \leq (2021, 2021)), y$ による形式的冪級数を用いて求める. $2$ 変数冪級数 $f (x, y)$ を

$f (x, y) := \frac{1}{1 - x - y} = \sum_{i = 0}^{\infty} \sum_{j = 0}^{\infty} (\binom{i + j}{i}) x^{i} y^{j}$

とする. 整い度の総和 $S$ について以下が成立する.

整い度の総和 $S$ は以下の冪級数 $F$ の $y^{M} \prod_{(i, j) \leq (2021, 2021)} x_{i, j}^{N}$ の係数である.
$F := \prod_{(i, j) \leq (2021, 2021)} f (\prod_{k = j}^{i} x_{i, k}, \prod_{k = i}^{2021} x_{k, j}) (* (i, j) = (1000, 1000) のとき, f (\prod_{k = j}^{i} x_{i, k}, y \prod_{k = i}^{2021} x_{k, j}))$

これは展開したときの $x_{i, j}$ の指数が $b_{i, 1} + b_{i, 2} + \dots + b_{i, j} + c_{i - 1, j} + c_{i - 2, j} + \dots + c_{j - 1, j}$ に対応し, $y$ の指数が $c_{999, 1000}$ に対応していることからわかる.
以下の補題を用いて, $[\prod_{(i, j) \leq (2021, 2021)} x_{i, j}^{N}] F$ を求めていく. ( $y$ の多項式として展開する. )

$[x^{n}] ((a x + b)^{n} \frac{1}{1 - α x}) = (a + b α)^{n}$ .

証明

[x^{k}] (\frac{1}{1 - α x}) = α^{k}, [x^{k}] (a x + b)^{n} = (\binom{n}{k}) a^{k} b^{n - k}

より,

\begin{aligned} ((a x + b)^{n} \frac{1}{1 - α x}) & = \sum_{k = 0}^{n} ([x^{k}] (\frac{1}{1 - α x})) ([x^{n - k}] (a x + b)^{n}) \\ = \sum_{k = 0}^{n} (\binom{n}{k}) (b α)^{k} a^{n - k} \\ = (a + b α)^{n} \end{aligned}

$y$ の $1$ 次以下の多項式 $A_{n, m}$ が以下を満たすとする.

$A_{0, 0} = 1$
$A_{i, - 1} = 0, A_{i, i + 1} = 0$
$A_{n, m} = A_{n - 1, m} + A_{n, m - 1} (0 \leq m \leq n)$
( $* (n, m) = (1000, 1000)$ のとき, $A_{n, m} = y A_{n, m - 1} + A_{n - 1, m}$ )

このとき, 以下が成立.

$[\prod_{(i, j) \leq (n, n)} x_{i, j}^{N}] \prod_{(i, j) \leq (n, n)} f (\prod_{k = j}^{i} x_{i, k}, \prod_{k = i}^{2021} x_{k, j}) = (\sum_{k = 0}^{n} A_{n, k} \prod_{\begin{matrix} n + 1 \leq t \leq 2021 \\ 1 \leq s \leq k \end{matrix}} x_{t, s})^{N}$

証明

(n, m)

について, 以下が成立することを示せば,

(n, n)

の場合が上の式となる.

\begin{aligned} [\prod_{(i, j) \leq (n, m)} x_{i, j}^{N}] \prod_{(i, j) \leq (n, m)} f (\prod_{k = j}^{i} x_{i, k}, \prod_{k = i}^{2021} x_{k, j}) \\ = & ((\prod_{k = m + 1}^{n} x_{n, k}) (\sum_{k = 0}^{m - 1} A_{n, k} \prod_{\begin{array}{c} n + 1 \leq t \leq 2021 \\ 1 \leq s \leq k \end{array}} x_{t, s}) + A_{n, m} \prod_{\begin{array}{c} n + 1 \leq t \leq 2021 \\ 1 \leq s \leq m \end{array}} x_{t, s} + \sum_{k = m + 1}^{n} A_{n - 1, k} \prod_{(\begin{array}{c} n + 1 \leq t \leq 2021 \\ 1 \leq s \leq m \end{array}) \lor (\begin{array}{c} n \leq t \leq 2021 \\ m + 2 \leq s \leq k \end{array})} x_{t, s})^{N} \end{aligned}

(n, m) = (1, 1)

のとき, 成り立つことは確認できる.
上の式と

f (\prod_{k = m + 1}^{n} x_{n, k}, \prod_{k = n}^{2021} x_{k, m + 1}) = \frac{1}{1 - (\prod_{k = m + 2}^{n} x_{n, k} + \prod_{k = n + 1}^{2021} x_{k, m + 1}) x_{n, m + 1}}

に補題を適用すると,

(n, m)

について成り立つとき, 以下のように

(n, m + 1)

についても成り立つ.

\begin{aligned} [\prod_{(i, j) \leq (n, m + 1)} x_{i, j}^{N}] \prod_{(i, j) \leq (n, m + 1)} f (\prod_{k = j}^{i} x_{i, k}, \prod_{k = i}^{2021} x_{k, j}) \\ = & [x_{n, m + 1}^{N}] (([\prod_{(i, j) \leq (n, m)} x_{i, j}^{N}] \prod_{(i, j) \leq (n, m)} f (\prod_{k = j}^{i} x_{i, k}, \prod_{k = i}^{2021} x_{k, j})) \times f (\prod_{k = m + 1}^{n} x_{n, k}, \prod_{k = n}^{2021} x_{k, m + 1})) \\ = & [x_{n, m + 1}^{N}] (((\prod_{k = m + 1}^{n} x_{n, k}) (\sum_{k = 0}^{m - 1} A_{n, k} \prod_{\begin{array}{c} n + 1 \leq t \leq 2021 \\ 1 \leq s \leq k \end{array}} x_{t, s}) + A_{n, m} \prod_{\begin{array}{c} n + 1 \leq t \leq 2021 \\ 1 \leq s \leq m \end{array}} x_{t, s} + \sum_{k = m + 1}^{n} A_{n - 1, k} \prod_{(\begin{array}{c} n + 1 \leq t \leq 2021 \\ 1 \leq s \leq m \end{array}) \lor (\begin{array}{c} n \leq t \leq 2021 \\ m + 1 \leq s \leq k \end{array})} x_{t, s})^{N} \\ \times \frac{1}{1 - (\prod_{k = m + 2}^{n} x_{n, k} + \prod_{k = n + 1}^{2021} x_{k, m + 1}) x_{n, m + 1}}) \\ = & ((\prod_{k = m + 2}^{n} x_{n, k}) (\sum_{k = 0}^{m - 1} A_{n, k} \prod_{\begin{array}{c} n + 1 \leq t \leq 2021 \\ 1 \leq s \leq k \end{array}} x_{t, s}) + A_{n, m} (\prod_{\begin{array}{c} n + 1 \leq t \leq 2021 \\ 1 \leq s \leq m \end{array}} x_{t, s}) (\prod_{k = m + 2}^{n} x_{n, k} + \prod_{k = n + 1}^{2021} x_{k, m + 1}) + \sum_{k = m + 1}^{n} A_{n - 1, k} \prod_{(\begin{array}{c} n + 1 \leq t \leq 2021 \\ 1 \leq s \leq m + 1 \end{array}) \lor (\begin{array}{c} n \leq t \leq 2021 \\ m + 2 \leq s \leq k \end{array})} x_{t, s})^{N} \\ = & ((\prod_{k = m + 2}^{n} x_{n, k}) (\sum_{k = 0}^{m} A_{n, k} \prod_{\begin{array}{c} n + 1 \leq t \leq 2021 \\ 1 \leq s \leq k \end{array}} x_{t, s}) + (A_{n, m} + A_{n - 1, m + 1}) \prod_{\begin{array}{c} n + 1 \leq t \leq 2021 \\ 1 \leq s \leq m + 1 \end{array}} x_{t, s} + \sum_{k = m + 2}^{n} A_{n - 1, k} \prod_{(\begin{array}{c} n + 1 \leq t \leq 2021 \\ 1 \leq s \leq m + 1 \end{array}) \lor (\begin{array}{c} n \leq t \leq 2021 \\ m + 2 \leq s \leq k \end{array})} x_{t, s})^{N} \\ = & ((\prod_{k = m + 2}^{n} x_{n, k}) (\sum_{k = 0}^{m} A_{n, k} \prod_{\begin{array}{c} n + 1 \leq t \leq 2021 \\ 1 \leq s \leq k \end{array}} x_{t, s}) + A_{n, m + 1} \prod_{\begin{array}{c} n + 1 \leq t \leq 2021 \\ 1 \leq s \leq m + 1 \end{array}} x_{t, s} + \sum_{k = m + 2}^{n} A_{n - 1, k} \prod_{(\begin{array}{c} n + 1 \leq t \leq 2021 \\ 1 \leq s \leq m + 1 \end{array}) \lor (\begin{array}{c} n \leq t \leq 2021 \\ m + 2 \leq s \leq k \end{array})} x_{t, s})^{N} \end{aligned}

(n, n)

から

(n + 1, 1)

についても同様に示される.

特に,

$\begin{aligned} [\prod_{(i, j) \leq (2021, 2021)} x_{i, j}^{N}] F & = (\sum_{k = 0}^{2021} A_{2021, k})^{N} \\ = (A_{2022, 2022})^{N} \end{aligned}$

$A_{n, m}$ の漸化式より $y$ の一次式 $A_{n, m}$ について以下が成立

( $A_{n, m}$ の係数の総和) $=$ ( $(0, 0)$ から $x \geq y$ の領域内で $x, y$ いずれかの正方向に $1$ 進むことを繰り返し, $(n, m)$ に到達する経路数)
( $A_{n, m}$ の $y$ の係数) $=$ ( $(0, 0)$ から $x \geq y$ の領域内で $x, y$ いずれかの正方向に $1$ 進むことを繰り返し, $(1000, 1000)$ を通り, $(n, m)$ に到達する経路数)