浅谈——范德蒙德卷积
chenzefan
·
·
算法·理论
介绍
范德蒙德卷积确实是卷积的一种，但不是多项式卷积。主要用处是组合数的降维。
标准形式：
\displaystyle\sum_{i=0}^k {n \choose i}{m \choose k-i}={n+m\choose k}
注意到时间复杂度从 O(k) 变成了 O(1)。
证明
常见证明有两种：
借助二项式定理
引理：(a+b)^n=\displaystyle\sum_{k=0}^n {n\choose k}a^{n-k}b^k。
此时逆着做得到（更换 a,b,n 的值）：
\begin{aligned}
\displaystyle\sum_{k=0}^{n+m}{n+m \choose k} x^k&=(x+1)^{n+m}\\
&=(x+1)^n(x+1)^m\\
&=\bigg(\displaystyle\sum_{i=0}^n{n\choose i}x^i\bigg)\bigg(\displaystyle\sum_{j=0}^m{m\choose j}x^j\bigg)\\
&=\displaystyle\sum_{k=0}^{n+m}\displaystyle\sum_{i=0}^k{n\choose i}{m\choose k-i} x^k
\end{aligned}
最后一步令 k=i+j，则固定 k 可知 0\le i,j\le k，枚举 i 得到 j=n-i。此时只要考虑 \displaystyle{n\choose i}x^i{m\choose j}x^j。直接交换律即可。
发现此时只要满足 x^k 的系数相同即可，也即 \displaystyle{n+m \choose k}=\displaystyle\sum_{i=0}^k{n\choose i}{m\choose k-i}。发现就是范德蒙德卷积公式。
证毕。
考虑组合意义
不太严谨吧。
但是很好理解。
一个袋子里共有 n+m 个小球，从中取出 k 个小球。不妨把袋子拆成两个分别有 n 个和 m 个小球的袋子，第一个袋子取 i 个，第二个袋子取 k-i 个条件等价。
也就是上面那个式子。
推论
类似的，改变形式的常见推论，共有如下几种。
推论 1
::::info[证明]
类似主公式，易证。
::::
### 推论 $2
::::info[证明]
$$
\begin{aligned}
\displaystyle\sum_{i=1}^n{n\choose i}{n\choose i-1}&=\sum_{i=0}^{n-1}{n\choose i+1}{n\choose i}\\
&={2n\choose n-1}
\end{aligned}
$$
::::
### 推论 $3
\displaystyle\sum_{i=0}^n{n\choose i}^2={2n\choose n}
::::info[证明]
\begin{aligned}
\displaystyle\sum_{i=0}^n{n\choose i}^2&=\sum_{i=0}^n{n\choose i}{n\choose i}\\
&=\sum_{i=0}^n{n\choose i}{n\choose n-i}\\
&={2n\choose n}
\end{aligned}
::::
推论 4
\displaystyle\sum_{i=0}^m{n\choose i}{m\choose i}={n+m \choose m}
::::info[证明]
\begin{aligned}
\displaystyle\sum_{i=0}^m{n\choose i}{m\choose i}&=\displaystyle\sum_{i=0}^m{n\choose i}{m\choose m-i}\\
&={n+m\choose m}
\end{aligned}
::::
例题详解
::::info[温馨提示]
例题不多啊，这里就讲 1 题吧。范德蒙德卷积多数是用在化简中的，纯题目很少。
::::
CF785D
枚举每一个左括号 (，为了防止计数的不重复，不妨把这个左括号当成一个子序列中最后的 (。
前后缀预处理得到该左括号左边的 ( 个数 a，右边的 ) 个数 b，去掉与该左括号匹配的一个，还剩 b-1 个。显然这个左括号的贡献就是 \displaystyle\sum_{i=0}^{\min(a,b-1)}{a\choose i}{b \choose i+1}。
总的答案就是 \displaystyle\sum_{a,b}\sum_{i=0}^{\min(a,b-1)}{a\choose i}{b \choose i+1}。用范德蒙德卷积优化，
\begin{aligned}
\displaystyle\sum_{a,b}\sum_{i=0}^{\min(a,b-1)}{a\choose i}{b \choose i+1}&=\sum_{a,b}\sum_{i=0}^{\min(a,b-1)}{a \choose a-i}{b\choose i+1}\\
&=\sum_{a,b}{a+b\choose a+1}
\end{aligned}
时间复杂度 O(n)。
总结
范德蒙德卷积是做题过程中压缩一重循环的技巧，当然，是有前提的。成效很明显，从 O(k) 到 O(1)。而 0\le k \le n+m，故不妨按照 O(n+m) 来算。这可以省下一个量级，是优化组合数学题的好方法。
仅仅是因为 \text{NOIP 2025} 第 2 题罢了。
当作课后习题吧。