OMC034-B後日談

適当な非負整数$n,h,i$を用いて, $m=n+h,\ l=n+i$ と表すことにすると，$$\begin{eqnarray} \displaystyle \sum_{l=n}^m \ {}_m C _l \cdot {}_l C _n \ x^{l-n} & = & \displaystyle \sum_{i=0}^h {}_{n+h} C _{n+i} \cdot {}_{n+i} C _n \ x^{i} \\ & = & \displaystyle \sum_{i=0}^h \frac{(n+h)!}{(n+i)!\ (h-i)!} \cdot \frac{(n+i)!}{n!\ i!} \cdot \frac{h!}{h!} \ x^i \\ & = & \displaystyle \sum_{i=0}^h {}_{n+h} C _h \cdot {}_h C _i \ x^i \\ & = & {}_{n+h} C _h \displaystyle \sum_{i=0}^h {}_h C _i \ x^i \\ & = & {}_m C _n \ (x+1)^{m-n} \end{eqnarray} $$

行の本数 $j$ に関する数学的帰納法で示す.

(ア) $j=2$ のとき

第1行にある $a_1$ 個のコマから $k$ 個のコマを選んで隣接する真下のマスに移動させるので, 

$S_{2,k} = {}_{a_1} C _{k} = {}_{a_1} C _{k} \cdot (2-1)^{a_1-k}$ 

である. よって, $j=2$ のとき, これは成立している.

(イ) ある$j$ 行の場合において, 上式の成立を仮定する. $j+1$ 行のときを考える.

第$j$ 行目に$a_j$ 個のコマが存在するように操作を繰り返し, さらに$a_j$ 個のコマから$k$ 個のコマを選ぶ. その時のコマの選び方の総数は

$S_{j,a_{j}}\ \cdot \ {}_{a_j} C _{k}$ 

と表せる. $a_{1}\geq a_j \geq k $であるから, この範囲で総和をとれば, $S_{j+1,k}$ を求めることができる.

$$\begin{eqnarray} S_{{j+1},k} & = & \displaystyle \sum_{a_j=k}^{a_{1}} \ S_{j,a_{j}}\ \cdot \ {}_{a_j} C _{k} \\ & = & \displaystyle \sum_{a_j=k}^{a_{1}} {}_{a_1} C _{a_j} \ (j-1)^{a_1 - a_j} \ \cdot {}_{a_j} C _{k} \ (∵帰納法の仮定)\\ & = & \left(\frac{1}{j-1} \right)^{k-a_{1}}\ \displaystyle \sum_{a_j=k}^{a_{1}} {}_{a_1} C _{a_j} \ \cdot \ {}_{a_j} C _{k}\ \left(\frac{1}{j-1} \right)^{a_{j} - k} \\ & = & \left(\frac{1}{j-1} \right)^{k-a_1}\ {}_{a_1} C _{k} \cdot \left(\frac{1}{j-1} + 1 \right)^{a_1 - k} (∵補題1)\\ & = & {}_{a_1} C _k \cdot j^{a_1 - k} \ \end{eqnarray}$$
となる. よって, $j+1$行のときも成立していることがわかる.

(ア)(イ)より, これは示された.