ファンデルモンドの二項係数畳み込み

　二項定理をうまく使うことで二項係数の畳み込みをついて考えることができる。

ファンデルモンドの畳み込み

二項係数を定義されない添え字の時、 $0$ であると拡張すると

${}_{p+q}\mathrm{C}_r=\displaystyle\sum_{i=0}^r{}_p\mathrm{C}_i{}_q\mathrm{C}_{r-i}$

$Proof$

$(1+x)^{p+q}$ を二通りの方法で展開する。そのまま二項定理で展開すると、

$(1+x)^{p+q}=\displaystyle\sum_{k=0}^{p+q}{}_{p+q}\mathrm{C}_kx^k$

が得られる。 $(1+x)^p(1+x)^q$ と見て展開すると

$(1+x)^{p+q}=\Big(\displaystyle\sum_{i=0}^p{}_p\mathrm{C}_ix^i\Big)\Big(\sum_{j=0}^q{}_q\mathrm{C}_jx^j\Big)$

　二つの式の右辺の $x^r$ の係数は同じであるため、係数比較により

${}_{p+q}\mathrm{C}_r=\displaystyle\sum_{i=0}^r{}_p\mathrm{C}_i{}_q\mathrm{C}_{r-i}$ $◽︎$

数ならぬ