组合恒等式

$\binom{n}{k}$ 是从 $n$ 个物体中选出 $k$ 个的方法数。$\binom{n}{n-k}$ 是选出你不拿的那 $n-k$ 个物体的方法数。每一种“拿哪些”的选法，恰好对应一种“留哪些”的选法，所以这两个数一定相等！

我们用算两次（双重计数）：把同一个东西用两种方法数。

从 $n$ 个物体中选出一个子集，有多少种方法？ 每个物体都有 2 种选择：选或不选。所以共有 $2^n$ 种方法。

选 0 个物体有多少种方法？选 1 个呢？选 2 个呢？选 $n$ 个呢？ 选 0 个有 $\binom{n}{0}$ 种方法，选 1 个有 $\binom{n}{1}$ 种，选 2 个有 $\binom{n}{2}$ 种，……，选 $n$ 个有 $\binom{n}{n}$ 种。

把它们加起来，就是按大小把每个子集恰好数了一次：

它一定等于 $2^n$！

假设有 $n$ 名学生，我们要从中选一些人去春游。

其中一名学生 Bob 生病了，不能去。在其余 $n - 1$ 名学生的所有子集中，设有 $a$ 个子集的人数是偶数，$b$ 个子集的人数是奇数。

后来 Bob 病好了，可以去了。用 $a$ 和 $b$ 表示：全部 $n$ 个人的子集中，有多少个是奇数个人，多少个是偶数个人？ 把 Bob 加进一个组，会改变它人数的奇偶性。$a$ 个偶数组变成奇数组，$b$ 个奇数组变成偶数组。不加 Bob 的话，它们保持原样。

总的来说，$n$ 个人的所有子集中，奇数个人的有多少个，偶数个人的有多少个？ 奇数：$b$（不含 Bob）$+\ a$（含 Bob）$= a + b$。偶数：也是 $a + b$。两者相同！

用组合数怎么写这个结论？ 奇数组的个数是 $\binom{n}{1} + \binom{n}{3} + \cdots$，偶数组的个数是 $\binom{n}{0} + \binom{n}{2} + \cdots$。两者相等，这就是这个恒等式。

设想你有 $m$ 个橙子和 $n$ 根香蕉。

任意选出 $r$ 个水果，有多少种方法？ 有 $\binom{m+n}{r}$ 种方法。

选出 $r$ 个橙子，有多少种方法？ 从 $m$ 个橙子中选，有 $\binom{m}{r}$ 种方法。

选出 $r - 1$ 个橙子和 1 根香蕉，有多少种方法？ 橙子有 $\binom{m}{r-1}$ 种选法，香蕉有 $\binom{n}{1}$ 种：一共 $\binom{m}{r-1}\binom{n}{1}$ 种。

按这个思路，你能找到选出 $r$ 个水果的方法数的另一个式子吗？ 选出的水果是 $r$ 个橙子和 0 根香蕉，或 $r-1$ 个橙子和 1 根香蕉，……，或 0 个橙子和 $r$ 根香蕉。把各种情况加起来：

而 $\binom{m+n}{r}$ 也是选出 $r$ 个水果的方法数，所以两者一定相等！

在范德蒙恒等式中令 $m = n = r = k$，会得到什么？ 得到

为什么每一项都是平方？ 由对称性（定理 6.1.1），$\binom{k}{k-i} = \binom{k}{i}$。所以每一项都是 $\binom{k}{i}^2$。

用文字说：从 $k$ 个穿红衣服的人和 $k$ 个穿蓝衣服的人中选出 $k$ 个人。选了 $i$ 个红衣人，就要选 $k - i$ 个蓝衣人，这等价于选出不去的那 $i$ 个蓝衣人。

设想有 $n + 1$ 个人，你要从中选出 $r + 1$ 名组长。

有多少种选法？ 就是 $\binom{n+1}{r+1}$。

如果 $n + 1$ 人中的 Bob 是组长，从其余 $n$ 人中选出另外 $r$ 名组长有多少种方法？ 是 $\binom{n}{r}$。

如果 Bob 不是组长，从其余 $n$ 人中选出 $r + 1$ 名组长有多少种方法？ 是 $\binom{n}{r+1}$。

我们用两种不同的方法数了选出 $r + 1$ 名组长的方法数！让它们相等：

和前面一样，我们把同一个量用两种方法数。

从 $n + 1$ 个人中选出 $k + 1$ 名组长，有多少种方法？ 是 $\binom{n+1}{k+1}$。

现在按水平给这 $n + 1$ 个人排名，从第 1 名（最好）到第 $n + 1$ 名。

如果排名最靠后的组长是第 $k + 1$ 名，选出其他组长有多少种方法？ 另外 $k$ 名组长必须来自排在他前面的 $k$ 个人：$\binom{k}{k}$。

如果排名最靠后的组长是第 $k + 2$ 名呢？ 排在他前面的有 $k + 1$ 个人，所以是 $\binom{k+1}{k}$。

就这样一直做到最后。

如果排名最靠后的组长是第 $n + 1$ 名呢？ 排在他前面的有 $n$ 个人，所以是 $\binom{n}{k}$。

按排名最靠后的组长分类讨论，得到选出 $k + 1$ 名组长的方法数是

。我们也算出了 $\binom{n+1}{k+1}$ 种方法，所以两者一定相等！

从 $\binom{k}{k}$ 一直到 $\binom{n}{k}$ 的整根球棒是多少？ 由曲棍球棒恒等式，它是 $\binom{n+1}{k+1}$。

你不要的那一段，从 $\binom{k}{k}$ 到 $\binom{j-1}{k}$，是多少？ 再用一次曲棍球棒恒等式：$\binom{j}{k+1}$。

相减。 剩下的就是 $\binom{j}{k} + \cdots + \binom{n}{k} = \binom{n+1}{k+1} - \binom{j}{k+1}$。