范德蒙恆等式

范德蒙恆等式(英文：Vandermonde's Identity)是一個有關組合數的求和公式。

${\displaystyle {\binom {n+m}{k}}=\sum _{i=0}^{k}{\binom {n}{i}}{\binom {m}{k-i}}}$

證明

組合方法

甲班有 ${\displaystyle m}$個同學，乙班有 ${\displaystyle n}$個同學，從兩個班中選出 ${\displaystyle k}$個同學有${\displaystyle {\binom {n+m}{k}}}$種方法。

從甲班選 ${\displaystyle k-i}$名，從乙班選 ${\displaystyle i}$名有${\displaystyle {\binom {n}{i}}{\binom {m}{k-i}}}$種方法，考慮所有情況${\displaystyle i=0,1,\ldots ,k}$，從兩個班中合計 ${\displaystyle k}$選出個同學有 ${\displaystyle \sum _{i=0}^{k}{\binom {n}{i}}{\binom {m}{k-i}}}$種方法。

所以 ${\displaystyle {\binom {n+m}{k}}=\sum _{i=0}^{k}{\binom {n}{i}}{\binom {m}{k-i}}}$^[1]

母函數方法

注意到

${\displaystyle (1+x)^{n}(1+x)^{m}=(1+x)^{n+m}}$

等號左邊化簡成

${\displaystyle (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}}$

等號右邊則根據定義

${\displaystyle (1+x)^{n+m}=\sum _{k=0}^{n+m}{\binom {n+m}{k}}x^{k}}$

比較 ${\displaystyle x^{k}}$係數，可得

${\displaystyle {\binom {n+m}{k}}=\sum _{i=0}^{k}{\binom {n}{i}}{\binom {m}{k-i}}}$^[1]

推廣

多變量型

${\displaystyle \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}}}$

其中${\displaystyle {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}$^[2]

展開${\displaystyle (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}}}$可得以上結論。

超幾何函數

主條目：超幾何函數

范德蒙恆等式是超幾何函數的一個整數特例。

${\displaystyle {}_{2}F_{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)}$ ^[3]

${\displaystyle \sum _{i=0}^{k}{\binom {n}{i}}{\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)!}}{}_{2}F_{1}(-n,-k;m-k+1;1)}$

${\displaystyle ={\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}}}$