范德蒙德卷积

Summary

范德蒙德卷积给出一条关于组合数求和的恒等式：sum C(n,i) C(m,k-i) 等于 C(n+m,k)，即两组组合数的卷积等于一个更大的组合数。文中给出两种证明。代数证明借助二项式定理，把 (x+1) 的 n+m 次方拆成 (x+1) 的 n 次方乘 (x+1) 的 m 次方，展开后比较两边 x 的 k 次方的系数即得。组合证明从计数意义出发：在大小为 n+m 的集合里取 k 个元素，等价于先把集合拆成大小分别为 n 与 m 的两部分，再从两部分各取 i 个和 k-i 个并对 i 求和，由于不同的拆法之间彼此等价，只需考虑一种拆法。

参考资料

• 范德蒙德卷积 - OI Wiki

公式

$$\sum_{i=0}^k\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}$$

证明

考虑用二项式定理证明：

$$\begin{aligned} \sum_{k=0}^{n+m}\binom{n+m}{k}x^k & =(x+1)^{n+m} \\ & =(x+1)^n(x+1)^m \\ & =\sum_{r=0}^n\binom{n}{r}x^r\sum_{s=0}^m\binom{m}{s}x^s \\ & =\sum_{k=0}^{n+m}\sum_{r=0}^k\binom{n}{r}\binom{m}{k-r}x^k \end{aligned}$$

即有：

$$\binom{n+m}{k}=\sum_{r=0}^k\binom{n}{r}\binom{m}{k-r}$$

意义

若考虑其组合意义证明：

在一个大小为 $n+m$ 的集合中取出 $k$ 个数，可以等于把大小为 $n+m$ 的集合拆成两个集合，大小分别为 $n$ 与 $m$，然后从 $n$ 中取出 $i$ 个数，从 $m$ 中取出 $k-i$ 个数的方案数。由于我们有了对于 $i$ 的枚举，于是只需要考虑一种拆法，因为不同的拆法之间是等价的。