ヴァンデルモンドの恒等式と下降冪版二項定理
はじめに
この記事ではVandermondeの恒等式とその一般化について紹介します。
まずヴァンデルモンドの恒等式とは以下の公式のことを言うのでした。
非負整数$m,n,k$と二項係数$\dis\binom nk=\frac{n!}{k!(n-k)!}$について
$\dis\binom {m+n}k=\sum^k_{j=0}\binom mj\binom n{k-j}$
が成り立つ。
日本語では"ヴァンデルモンドの畳み込み"と言われることが多い(っぽい)ですが、この記事では"Vandermonde's identity"の直訳として"ヴァンデルモンドの恒等式"という名称を使っています。
またこの一般化として以下の恒等式が成り立ちます。
非負整数$n$とポッホハマー記号$(x)_n=x(x-1)(x-2)\cdots(x-n+1)$について$x,y$についての恒等式
$\dis(x+y)_n=\sum^n_{k=0}\binom nk(x)_k(y)_{n-k}$
が成り立つ。
下降冪版"二項定理"と表した通りこれは通常の二項定理
$\dis(x+y)^n=\sum^n_{k=0}\binom nkx^ky^{n-k}$
の類似になっています。
また非負整数$n,k$に対して$\dis(n)_k=\frac{n!}{(n-k)!}$が成り立つので
\begin{eqnarray}
(m+n)_k&=&k!\cdot\frac{(m+n)!}{k!(m+n-k)!}=k!\binom{m+n}k
\\&=&\sum^k_{j=0}\binom kj(m)_j(n)_{k-j}
\\&=&\sum^k_{j=0}\frac{k!}{j!(k-j)!}\cdot\farc{m!}{(m-j)!}\cdot\frac{n!}{(n-k+j)!}
\\&=&k!\sum^k_{j=0}\frac{m!}{j!(m-j)!}\cdot\frac{n!}{(k-j)!(n-k+j)!}
\\&=&k!\sum^k_{j=0}\binom mj\binom n{k-j}
\end{eqnarray}
とヴァンデルモンドの恒等式を含んでいることがわかります。
証明
下降冪版二項定理(定理2)を数学的帰納法で示します。
$n=0$のときは自明。$n$のときに成り立つとすると
\begin{eqnarray}
\dis(x+y)_{n+1}&=&(x+y-n)(x+y)_n
\\&=&\sum^n_{k=0}((x-k)+(y-n+k))\binom nk(x)_k(y)_{n-k}
\\&=&\sum^n_{k=0}\binom nk((x)_{k+1}(y)_{n-k}+(x)_k(y)_{n+1-k})
\\&=&\sum^{n+1}_{k=1}\binom n{k-1}(x)_k(y)_{n+1-k}+\sum^n_{k=0}\binom nk(x)_k(y)_{n+1-k}
\\&=&\sum^{n+1}_{k=0}(\binom n{k-1}+\binom nk)(x)_k(y)_{n+1-k}
\\&=&\sum^{n+1}_{k=0}\binom{n+1}k(x)_k(y)_{n+1-k}
\end{eqnarray}
と$n+1$のときにも成り立つ。(ただし$n< k$において$\binom nk=0$とした。)
通常の二項定理も
\begin{eqnarray}
(x+y)^{n+1}&=&(x+y)\sum^n_{k=0}\binom nkx^ky^{n-k}
\\&=&\sum^{n}_{k=0}\binom nkx^{k+1}y^{n-k}+\sum^n_{k=0}\binom nkx^ky^{n+1-k}
\\&=&\sum^{n+1}_{k=0}(\binom n{k-1}+\binom nk)x^ky^{n+1-k}
\\&=&\sum^{n+1}_{k=0}\binom{n+1}kx^ky^{n+1-k}
\end{eqnarray}
と証明されるので本質的に同じと言えますね。