二项恒等式的二重计数证明

考虑由 $n$ 个男生和 $n$ 个女生组成的 $2n$ 人集合。我们用两种方式数从这 $2n$ 人中恰好选出 $n$ 人组成委员会的方法数。

直接地,按定义这个数是 $\binom{2n}{n}$,因为我们只是从 $2n$ 个对象中选 $n$ 个。

另一方面,按委员会中包含的男生人数对所有合法委员会分类。若委员会恰好包含 $k$ 个男生,即对某个满足 $0 \le k \le n$ 的 $k$ 而言,那么这 $k$ 个男生有 $\binom{n}{k}$ 种选法,其余 $n-k$ 名成员必须是女生,从 $n$ 个女生中选出有 $\binom{n}{n-k}$ 种方法。由对称恒等式 $\binom{n}{n-k} = \binom{n}{k}$,恰好包含 $k$ 个男生的委员会数为 $\binom{n}{k} \cdot \binom{n}{k} = \binom{n}{k}^2$。

每个合法的 $n$ 人委员会都有一个介于 $0$ 到 $n$ 之间确定的男生人数 $k$,且不同 $k$ 值之间不会重复计数任何委员会,因此对所有 $k$ 求和即得委员会总数 $\sum_{k=0}^{n} \binom{n}{k}^2$。

由于两个表达式数的是完全相同的委员会集合,它们必须相等:$\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$。