范德蒙恆等式

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