范德蒙恒等式

范德蒙恒等式(英文：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}$

推广

多变量型

$\sum_{k_{ij}} {n_1 \choose k_{11}, k_{12}, \dots, k_{1t}}\dots {n_s \choose k_{s1}, k_{s2}, \dots, k_{st}}={n_1+n_2+\dots+n_s \choose r_1, r_2, \dots, r_t}$

其中${n \choose n_1, n_2, \dots, n_m}=\frac{n!}{n_1!n_2!\dots n_m!},k_{1l}+k_{2l}+\dots+k_{sl}=r_l,l=1,\dots,t$

展开$(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$