引入
范德蒙德卷积是一种合并组合数的式子，主要应用于组合数学的公式推导。
范德蒙德卷积公式
i=0∑k(in)(k−im)=(kn+m)
证明
考虑用二项式定理证明：
k=0∑n+m(kn+m)xk=(x+1)n+m=(x+1)n(x+1)m=r=0∑n(rn)xrs=0∑m(sm)xs=k=0∑n+mr=0∑k(rn)(k−rm)xk
即有：
(kn+m)=r=0∑k(rn)(k−rm)
若考虑其组合意义证明：
在一个大小为 n+m 的集合中取出 k 个数，可以等于把大小为 n+m 的集合拆成两个集合，大小分别为 n 与 m，然后从 n 中取出 i 个数，从 m 中取出 k−i 个数的方案数。由于我们有了对于 i 的枚举，于是只需要考虑一种拆法，因为不同的拆法之间是等价的。
推论
推论 1 及证明
i=−r∑s(r+in)(s−im)=(r+sn+m)
证明与原公式证明相似。
推论 2 及证明
i=1∑n(in)(i−1n)=(n−12n)
根据基础的组合数学知识推导，有：
i=1∑n(in)(i−1n)=i=0∑n−1(i+1n)(in)=i=0∑n−1(n−1−in)(in)=(n−12n)
推论 3 及证明
i=0∑n(in)2=(n2n)
根据基础的组合数学知识推导，有：
i=0∑n(in)2=i=0∑n(in)(n−in)=(n2n)
推论 4 及证明
i=0∑m(in)(im)=(mn+m)
根据基础的组合数学知识推导，有：
i=0∑m(in)(im)=i=0∑m(in)(m−im)=(mn+m)
其中 (mn+m) 是我们较为熟悉的网格图路径计数的方案数。所以我们可以考虑其组合意义的证明。
在一张网格图中，从 (0,0) 走到 (n,m) 共走 n+m 步。规定 (0,0) 位于网格图左上角，其中向下走了 n 步，向右走了 m 步，方案数为 (mn+m)。
换个视角，我们将 n+m 步拆成两部分走，先走 n 步，再走 m 步，那么 n 步中若有 i 步向右，则 m 步中就有 m−i 步向右，故得证。
习题
参考资料与注释
- Vandermonde’s Convolution Formula