范德蒙恒等式

Prerequisite　二项式定理

　　¹范德蒙恒等式（Vandermonde's identity）是指

\begin{equation} \begin{pmatrix}a + b\\ n\end{pmatrix} = \sum_i \begin{pmatrix}a\\ i\end{pmatrix} \begin{pmatrix}b\\ n-i\end{pmatrix} = \sum\limits_i \begin{pmatrix}a\\n-i\end{pmatrix} \begin{pmatrix}b\\i\end{pmatrix} \end{equation}

其中求和是对所有使得表达式有意义的非负整数 $i$ 进行的．

证明 1

　　假设有编了号的 $a+b$ 个小球．不分顺序抓取 $n$ 个，求总共有几种情况（用 $N$ 表示）．

　　方法 1：根据定义，有 $N = \begin{pmatrix}a+b\\n\end{pmatrix} $ 种情况．

　　方法 2：先把球分成 $A$， $B$ 两组，分别有 $a$ 个和 $b$ 个．如果在 $A$ 组中抽取 $i$ 个球（有 $ \begin{pmatrix}a\\i\end{pmatrix} $ 种情况），在 $B$ 组中只能抽取 $n - i$ 个（有 $ \begin{pmatrix}b\\n-i\end{pmatrix} $ 种情况），所以一个 $i$ 对应 $ \begin{pmatrix}a\\i\end{pmatrix} \begin{pmatrix}b\\n-i\end{pmatrix} $ 种情况．所有可能的 $i$ 一共有 $N = \sum_i \begin{pmatrix}a\\i\end{pmatrix} \begin{pmatrix}b\\n-i\end{pmatrix} $ 种情况．

　　由于这个问题只有一个答案，所以有 $ \begin{pmatrix}a+b\\n\end{pmatrix} = \sum_i \begin{pmatrix}a\\i\end{pmatrix} \begin{pmatrix}b\\n-i\end{pmatrix} $．

　　但 $i$ 的范围具体从多少取到多少，由 $a$， $b$ 是否大于 $n$ 来决定．当 $a,b$ 都大于 $n$ 时，$i$ 可以从 0 取到 $n$，如果其中至少有一个小于 $n$，那么 $i$ 的取值不能使 $C$ 的上标大于下标．

　　证毕．

证明 2

　　我们也可以通过二项式定理来证明

\begin{equation} \begin{aligned} (1 + x)^{m+n} &= \sum_{r=0}^{m+n} \begin{pmatrix}m+n\\r\end{pmatrix} x^r\\ &=(1+x)^m (1+x)^n\\ &=\sum_0^m \begin{pmatrix}m\\i\end{pmatrix} x^i \sum_{j=0}^n \begin{pmatrix}n\\j\end{pmatrix} x^j\\ &=\sum_{r=0}^{m+n} \sum_{k=0}^r \begin{pmatrix}m\\k\end{pmatrix} \begin{pmatrix}n\\r-k\end{pmatrix} x^r \end{aligned} \end{equation}

1. ^ 参考 Wikipedia 相关页面