Vandermonde · Σⱼ C(m,j)·C(n,k−j) = C(m+n,k)

范德蒙德卷积：两行相乘配出第三行

从 m + n 个元素里选 k 个，共 C(m+n, k) 种。若把它们分成「前 m 个」与「后 n 个」两组，就可以按取自前一组的个数 j 给所有选法分类：先从前 m 个里选 j 个（C(m, j) 种），再从后 n 个里选剩下的 $k - j$ 个（ $C(n, k-j)$ 种），两步相乘。把各类相加，就得到范德蒙德卷积（Vandermonde's identity）： $Σ_j C(m, j)\cdot C(n, k-j) = C(m+n, k)$ 。

1 · 按「取自前一组几个」分类求和

Vandermonde · Σⱼ C(m, j)·C(n, k−j) = C(m+n, k)

拖动 m、n、k，下表逐个列出 j 的每一类：从前一组取 j 个乘从后一组取 $k - j$ 个。点击某一行看该类的具体计数；所有乘积相加正好等于右侧一次性选取的 C(m+n, k)。这就是把二项式定理里 $(1+t)^m\cdot (1+t)^n = (1+t)^{m+n}$ 两边 $t^k$ 的系数对齐后的结果。

一个具体读法：m 名男生、n 名女生里选 k 人组队，直接选是 C(m+n, k)；按「队里有几名男生」分类，选 j 名男生要配 $k - j$ 名女生，各类相加同样得到总数。取 m = n 且 k = m 时，卷积化为 $Σ_j C(n, j)^2 = C(2n, n)$ ——中间那个最大的中心二项式系数。

2 · 相关链接

Vandermonde's identity — Wikipedia · en.wikipedia.org——范德蒙德卷积的组合证明、生成函数证明与推广。
Binomial coefficient — Wikipedia · en.wikipedia.org——二项式系数 C(n, k) 及其恒等式汇总。