OMC100個人的解法 2022×2021÷2+1 変数母関数

155

　正三角形状に非負整数を並べた配列が整った三角形であるとは,最下行以外に位置する任意の数について, そのすぐ下に位置する左右$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 \quad (1\leq i \leq 2022),\quad 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}\quad =\quad \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}\quad ((i,j) \leq (2021,2021)),y$ による形式的冪級数を用いて求める. $2$ 変数冪級数 $f(x,y)$ を

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

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

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

これは展開したときの $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}$ に対応していることからわかる.
以下の補題を用いて, $\displaystyle\Bigg[\prod_{(i,j)\leq (2021,2021) }x_{i,j}^N\Bigg]F$ を求めていく. ( $y$ の多項式として展開する. )

$[x^n]\Big((ax+b)^n\dfrac{1}{1-\alpha x}\Big)=(a+b\alpha)^n$.

証明

$[x^k]\Big(\dfrac{1}{1-\alpha x}\Big)=\alpha ^k, [x^k] (ax+b)^n =\displaystyle\binom{n}{k}a^kb^{n-k}$ より,
$$\begin{aligned} [x^n]\Big((ax+b)^n\dfrac{1}{1-\alpha x}\Big)&=\displaystyle\sum_{k=0}^{n}\Big( [x^k] \Big(\dfrac{1}{1-\alpha x}\Big)\Big)\Big([x^{n-k}] (ax+b)^n \Big)\\\\ &=\displaystyle\sum_{k=0}^{n}\binom{n}{k}(b\alpha)^{k}a^{n-k}\\\\ &=(a+b\alpha)^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}=yA_{n,m-1}+A_{n-1,m}$ )

このとき, 以下が成立.

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

証明

　$(n,m)$ について, 以下が成立することを示せば, $(n,n)$ の場合が上の式となる.
$$ \begin{aligned} &\Bigg[\prod_{(i,j)\leq (n,m)}x_{i,j}^N\Bigg] \prod_{(i,j)\leq (n,m)}f\Big(\prod_{k=j}^{i}x_{i,k},\prod_{k=i}^{2021} x_{k,j}\Big)\\\\ =&\Big(\Big(\prod_{k=m+1}^{n} x_{n,k}\Big)\Big(\sum_{k=0}^{m-1}A_{n,k}\prod_{\substack{n+1\leq t \leq 2021 \\\\ 1\leq s \leq k}}x_{t,s}\Big)+A_{n,m}\prod_{\substack{n+1\leq t\leq 2021 \\\\ 1\leq s \leq m}}x_{t,s}+\sum_{k=m+1}^{n}A_{n-1,k}\prod_{\big(\substack{n+1\leq t \leq 2021 \\\\ 1\leq s \leq m}\big)\lor\big(\substack{n\leq t \leq 2021 \\\\ m+2 \leq s \leq k}\big)}x_{t,s}\Big)^N \end{aligned}$$
　$(n,m)=(1,1)$ のとき, 成り立つことは確認できる.
上の式と
$$f\Big(\prod_{k=m+1}^{n} x_{n,k},\prod_{k=n}^{2021}x_{k,m+1}\Big)=\dfrac{1}{1-\Big(\prod_{k=m+2}^{n}x_{n,k}+\prod_{k=n+1}^{2021}x_{k,m+1}\Big)x_{n,m+1}}$$
に補題を適用すると, $(n,m)$ について成り立つとき, 以下のように $(n,m+1)$ についても成り立つ.
$$ \begin{aligned} &\Bigg[\prod_{(i,j)\leq (n,m+1)}x_{i,j}^N\Bigg] \prod_{(i,j)\leq (n,m+1)}f\Big(\prod_{k=j}^{i}x_{i,k} ,\prod_{k=i}^{2021} x_{k,j}\Big)\\\\ =&[x_{n,m+1}^N]\Bigg(\Bigg(\Bigg[\prod_{(i,j)\leq (n,m)}x_{i,j}^N\Bigg] \prod_{(i,j)\leq (n,m)}f\Big(\prod_{k=j}^{i}x_{i,k} ,\prod_{k=i}^{2021} x_{k,j}\Big)\Bigg)\times f\Big(\prod_{k=m+1}^{n} x_{n,k} ,\prod_{k=n}^{2021}x_{k,m+1}\Big)\Bigg)\\\\ =&[x_{n,m+1}^N]\Bigg(\Bigg(\Big(\prod_{k=m+1}^{n} x_{n,k}\Big)\Big(\sum_{k=0}^{m-1}A_{n,k}\prod_{\substack{n+1\leq t \leq 2021 \\\\ 1\leq s \leq k}}x_{t,s}\Big)+A_{n,m}\prod_{\substack{n+1\leq t\leq 2021 \\\\ 1\leq s \leq m}}x_{t,s}+\sum_{k=m+1}^{n}A_{n-1,k}\prod_{\big(\substack{n+1\leq t \leq 2021 \\\\ 1\leq s \leq m}\big)\lor\big(\substack{n\leq t \leq 2021 \\\\ m+1\leq s \leq k}\big)}x_{t,s}\Bigg)^N\\\\ &\times\frac{1}{1-\Big(\prod_{k=m+2}^{n}x_{n,k}+\prod_{k=n+1}^{2021}x_{k,m+1}\Big) x_{n,m+1}}\Bigg) \\\\ =&\Big(\Big(\prod_{k=m+2}^{n} x_{n,k}\Big)\Big(\sum_{k=0}^{m-1}A_{n,k}\prod_{\substack{n+1\leq t \leq 2021 \\\\ 1\leq s \leq k}}x_{t,s}\Big)+A_{n,m}\Big(\prod_{\substack{n+1\leq t\leq 2021 \\\\ 1\leq s \leq m}}x_{t,s}\Big)\Big(\prod_{k=m+2}^{n}x_{n,k}+\prod_{k=n+1}^{2021}x_{k,m+1}\Big)+\sum_{k=m+1}^{n}A_{n-1,k}\prod_{\big(\substack{n+1\leq t \leq 2021 \\\\ 1\leq s \leq m+1}\big)\lor\big(\substack{n\leq t \leq 2021 \\\\ m+2\leq s \leq k}\big)}x_{t,s}\Big)^N\\\\ =&\Big(\Big(\prod_{k=m+2}^{n} x_{n,k}\Big)\Big(\sum_{k=0}^{m}A_{n,k}\prod_{\substack{n+1\leq t \leq 2021 \\\\ 1\leq s \leq k}}x_{t,s}\Big)+(A_{n,m}+A_{n-1,m+1})\prod_{\substack{n+1\leq t\leq 2021 \\\\ 1\leq s \leq m+1}}x_{t,s}+\sum_{k=m+2}^{n}A_{n-1,k}\prod_{\big(\substack{n+1\leq t \leq 2021 \\\\ 1\leq s \leq m+1}\big)\lor\big(\substack{n\leq t \leq 2021 \\\\ m+2\leq s \leq k}\big)}x_{t,s}\Big)^N\\\\ =&\Big(\Big(\prod_{k=m+2}^{n} x_{n,k}\Big)\Big(\sum_{k=0}^{m}A_{n,k}\prod_{\substack{n+1\leq t \leq 2021 \\\\ 1\leq s \leq k}}x_{t,s}\Big)+A_{n,m+1}\prod_{\substack{n+1\leq t\leq 2021 \\\\ 1\leq s \leq m+1}}x_{t,s}+\sum_{k=m+2}^{n}A_{n-1,k}\prod_{\big(\substack{n+1\leq t \leq 2021 \\\\ 1\leq s \leq m+1}\big)\lor\big(\substack{n\leq t \leq 2021 \\\\ m+2\leq s \leq k}\big)}x_{t,s}\Big)^N\end{aligned}$$
$(n,n)$ から $(n+1,1)$ についても同様に示される.

特に,

$$\begin{aligned}\Bigg[\prod_{(i,j)\leq (2021,2021) }x_{i,j}^N\Bigg]F&=\Big(\sum_{k=0}^{2021}A_{2021,k}\Big)^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)$ に到達する経路数)