范德蒙恒等式

范德蒙恒等式(英文：Vandermonde's Identity)是一个有关组合数的求和公式。

: \binom {n+m}k = \sum_{i=0}^k \binom ni \binom m{k-i}

证明
组合方法
甲班有 m个同学，乙班有 n个同学，从两个班中选出 k個同學有\binom {n+m}k种方法。

从甲班选 k-i名，从乙班选 i名有\binom ni \binom m{k-i}种方法，考虑所有情况i=0,1,\ldots,k，从两个班中合計 k选出個同學有 \sum_{i=0}^k \binom ni \binom m{k-i}种方法。

所以 \binom {n+m}k = \sum_{i=0}^k \binom ni \binom m{k-i}

母函数方法
注意到

: (1+x)^n (1+x)^m=(1+x)^{n+m}

等號左邊化簡成

: (1+x)^n (1+x)^m
=\left(\sum_{i=0}^n \binom{n}{i} x^i\right)\left(\sum_{j=0}^m \binom{m}{j} x^j \right)
=\sum_{k=0}^{m+n} \left(\sum_{i=0}^k \binom{n}{i} \binom{m}{k-i}\right)x^k

等號右邊則根據定義

: (1+x)^{n+m}=\sum_{k=0}^{n+m} \binom{n+m}{k} x^k

比較 x^k係數，可得

: \binom {n+m}k = \sum_{i=0}^k \binom ni \binom m{k-i}

展开(x_1+x_2+\dots+x_t)^{n_1+n_2+\dots+n_s}=(x_1+x_2+\dots+x_t)^{n_1}\dots (x_1+x_2+\dots+x_t)^{n_s}可得以上结论。
超几何函数
范德蒙恒等式是超几何函数的一个整数特例。

{}_2F_1(a,b;c;1)=\sum_{n=0}^\infty \frac{a^{(n)} b^{(n)}}{c^{(n)}n!}=\frac{\Gamma(c)\Gamma(c-a-b)}{\Gamma(c-a)\Gamma(c-b)},\quad \Re(c)>\Re(a+b)

\sum_{i=0}^k \binom ni \binom m{k-i}=\frac{m!}{k!(m-k)!}\sum_{i=0}^{\infty} \frac{(-n)^{(i)}(-k)^{(i)}}{(m-k+1)^{(i)}i!}=\frac{m!}{k!(m-k)!}{}_2F_1(-n,-k;m-k+1;1)

=\frac{m!}{k!(m-k)!}\frac{\Gamma(m-k+1)\Gamma(n+m+1)}{\Gamma(n+m-k+1)\Gamma(m+1)}=\frac{(n+m)!}{k!(n+m-k)!}=\binom {n+m}k

参考资料