数学 / 排列组合 · 从计数原理到 P(n,k) 与 C(n,k) / 范德蒙德卷积 待审核 12 / 25
Vandermonde · Σⱼ C(m,j)·C(n,k−j) = C(m+n,k)

范德蒙德卷积

从 m+nm + n 个元素里选 kk 个共 C(m+n,k)C(m+n, k) 种。若把它们分成前 mm 个与后 nn 个两组，就可以按取自前一组的个数 jj 给所有选法分类：先从前 mm 个里选 jj 个，再从后 nn 个里选剩下的 k−jk-j 个，两步相乘。把各类相加即得范德蒙德卷积（Vandermonde's identity）：

∑jC(m, j) C(n, k−j)=C(m+n, k)\sum_{j} C(m,\, j)\, C(n,\, k-j) = C(m+n,\, k)

1 · 按取自前一组的个数分类

Vandermonde · Σⱼ C(m, j)·C(n, k−j) = C(m+n, k)
图 1-1 · 卷积各项的逐类展开。可拖动 mm、nn、kk，点击某一行看该类的具体计数，所有乘积相加正好等于右侧一次性选取的 C(m+n,k)C(m+n, k)。

这条恒等式也可以从生成函数读出：把 (1+t)m(1+t)n=(1+t)m+n(1+t)^m (1+t)^n = (1+t)^{m+n} 两边 tkt^k 的系数对齐，左边是各类乘积之和、右边是 C(m+n,k)C(m+n, k)。

一个具体读法：mm 名男生、nn 名女生里选 kk 人组队，直接选是 C(m+n,k)C(m+n, k)；按队里有几名男生分类，选 jj 名男生要配 k−jk-j 名女生，各类相加同样得到总数。取 m=nm = n 且 k=mk = m 时，卷积化为

∑jC(n, j)2=C(2n, n)\sum_{j} C(n,\, j)^2 = C(2n,\, n)

即中间那个最大的中心二项式系数。

2 · 参考文献

  1. Vandermonde's identity. Wikipedia. 范德蒙德卷积的组合证明、生成函数证明与推广。https://en.wikipedia.org/wiki/Vandermonde%27s_identity
  2. Binomial coefficient. Wikipedia. 二项式系数及其恒等式汇总。https://en.wikipedia.org/wiki/Binomial_coefficient