476 字
2 分钟
范德蒙德卷积 (Vandermonde's Convolution)

范德蒙德卷积 (Vandermonde’s Convolution)#

1. 核心恒等式#

∑k=0r(mk)(nr−k)=(m+nr)\sum_{k=0}^r \binom{m}{k} \binom{n}{r - k} = \binom{m + n}{r}

2. 组合意义证明#

考虑一个大小为 m+nm + n 的集合,其中前 mm 个元素标记为红色,后 nn 个元素标记为蓝色。 从这 m+nm + n 个元素中任意选取 rr 个元素的总方案数为 (m+nr)\binom{m+n}{r}。 若按选出的红色元素个数 kk 分类(0≤k≤r0 \le k \le r),则需要从 mm 个红色中选 kk 个,同时从 nn 个蓝色中选 r−kr-k 个,方案数为 (mk)(nr−k)\binom{m}{k}\binom{n}{r-k}。 对所有可能的 kk 求和,二者必然相等。

3. 常用推论与变形#

  1. 对称平方和: ∑k=0n(nk)2=∑k=0n(nk)(nn−k)=(2nn)\sum_{k=0}^n \binom{n}{k}^2 = \sum_{k=0}^n \binom{n}{k} \binom{n}{n - k} = \binom{2n}{n}
  2. 上指标求和 (朱世杰恒等式): ∑i=0n(ik)=(n+1k+1)\sum_{i=0}^n \binom{i}{k} = \binom{n + 1}{k + 1}
  3. 带权范德蒙德卷积: ∑k=0rk(mk)(nr−k)=m(m+n−1r−1)\sum_{k=0}^r k \binom{m}{k} \binom{n}{r - k} = m \binom{m + n - 1}{r - 1}

4. 竞赛实战应用:二重计数化简模板#

在很多组合计数问题中,面对形如 ∑k(mk)(nr−k)\sum_{k} \binom{m}{k} \binom{n}{r-k} 的二重求和,直接计算为 O(N)O(N);使用范德蒙德卷积可化简为单次 O(1)O(1) 的组合数 (m+nr)\binom{m+n}{r} 查询。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;
const int N = 200005;
ll fac[N], ifac[N];
ll qpow(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1)
res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
void init_comb(int n) {
fac[0] = 1;
for (int i = 1; i <= n; i++)
fac[i] = fac[i - 1] * i % MOD;
ifac[n] = qpow(fac[n], MOD - 2);
for (int i = n; i >= 1; i--)
ifac[i - 1] = ifac[i] * i % MOD;
}
ll C(int n, int m) {
if (m < 0 || m > n)
return 0;
return fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}
// 范德蒙德卷积求和:sum_{k=0}^r C(m, k) * C(n, r-k) = C(m+n, r)
ll vandermonde(int m, int n, int r) {
if (r < 0 || r > m + n)
return 0;
return C(m + n, r);
}
范德蒙德卷积 (Vandermonde's Convolution)
https://sanzenin.top/posts/obsidian/范德蒙德卷积/
作者
Sanzenin 凪
发布于
2026-09-03
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取