范德蒙恒等式
贡献者： addis
1范德蒙恒等式（Vandermonde's identity）是指
\begin{equation}
C_{a + b}^n = \sum_i C_a^i C_b^{n-i} = \sum\limits_i C_a^{n-i}C_b^i~.
\end{equation}
其中求和是对所有使得表达式有意义的非负整数 $i$ 进行的，即
\begin{equation}
\max \left\{0,\, n-b \right\} \leqslant i \leqslant \min \left\{a,\, n \right\} ~,
\end{equation}
当 $a, b \geqslant n$ 时化简为
\begin{equation}
0 \leqslant i \leqslant n~.
\end{equation}
1. 证明 1
假设有编了号的 $a+b$ 个小球。不分顺序抓取 $n$ 个，求总共有几种情况（用 $N$ 表示）。
方法 1：根据定义，有 $N = C_{a+b}^n$ 种情况。
方法 2：先把球分成 $A$， $B$ 两组，分别有 $a$ 个和 $b$ 个。如果在 $A$ 组中抽取 $i$ 个球（有 $C_a^i$ 种情况），在 $B$ 组中只能抽取 $n - i$ 个（有 $C_b^{n-i}$ 种情况），所以一个 $i$ 对应 $C_a^i C_b^{n-i}$ 种情况。所有可能的 $i$ 一共有 $N = \sum_i C_a^i C_b^{n-i}$ 种情况。
由于这个问题只有一个答案，所以有 $C_{a+b}^n = \sum_i C_a^i C_b^{n-i}$。
但 $i$ 的范围具体从多少取到多少，由 $a$， $b$ 是否大于 $n$ 来决定。当 $a,b$ 都大于 $n$ 时，$i$ 可以从 0 取到 $n$， 如果其中至少有一个小于 $n$， 那么 $i$ 的取值不能使 $C$ 的上标大于下标。
证毕。
2. 证明 2
我们也可以通过二项式定理来证明
\begin{equation}
\begin{aligned}
(1 + x)^{a+b} &= \sum_{n=0}^{a+b} C_{a+b}^n x^n\\
&=(1+x)^a (1+x)^b\\
&=\sum_{i=0}^a C_a^i x^i \sum_{j=0}^b C_b^j x^j\\
&=\sum_{n=0}^{a+b} \sum_{i} C_a^i C_b^{n-i} x^n~.
\end{aligned}
\end{equation}
最后两步可以看作对一个表格求和，第 $i$ 行第 $j$ 列的值为 $C_a^i C_b^j x^{i+j}$，求和的方式有两种，一种是每行每列求和，另一种是延斜线求和，每条斜线 $n = i+j$ 的值相同。注意每条斜线中 $i$ 的范围未必相同，满足
式 2 。
由于多项式中每项的系数必须相同，就有式 1 ，证毕。
1. ^ 参考 Wikipedia 相关页面