范德蒙德卷积

范德蒙德卷积

看之前你需要会基础的生成函数。

\([x ^ k]\) 表示生成函数第 \(k\) 项系数。

前置：插板法与生成函数

对于生成函数，可以证得： \(\frac{1}{1 - x} = \sum_{k = 0}^{\infin} x ^ k\)。

所以对于 \(\frac{1}{1 - x}\) 有 \([x ^ k] = 1\)。

推广至 \((\frac{1}{1 - x}) ^ m\) 求其 \([x ^ k]\)。

\[原式 = (\sum_k x ^ k) ^ m \]

每一个 \(x ^ k\) 应该为 \(m\) 个函数某个项的乘积。

比如，当 \(m = 4\)，\(x ^ 6 = x ^ 2 \times x ^ 3 \times x ^ 0 \times x ^ 1\)。

其中每个 \(x ^ i\) 都为 \(4\) 个生成函数所提供的一个。

那么乘积的系数就应该是这种组合方式的方案数。

注意到这个方案数是个插板法，即 \(x_1 + x_2 + \dots + x_m = i\) 且 \(x_j \ge 0\)。

那么我们就得出了：

对于 \((\frac{1}{1 - x}) ^ m\)，

\[[x ^ k] = \binom{k + m - 1}{m - 1} = \binom{k + m - 1}{k} \]

一类范德蒙德卷积

\[\sum_i \binom{m}{k - i}\binom{n}{i} = \binom{m + n}{k} \]

证明

组合意义很好理解。

拓展

由于有：\(\binom{n}{i} = \binom{n}{n - i}\)，所以有：

\[\sum_i \binom{n}{i} \binom{m}{i} = \sum_i \binom{n}{i} \binom{m}{m - i} = \binom{n + m}{m} = \binom{n + m}{n} \]

二类范德蒙德卷积

\[\sum_i \binom{i}{n} \binom{k - i}{m} = \binom{k + 1}{n + m + 1} \]

证明

设 \(A(x) = \sum_{i} \binom{i}{n} x^i = \frac{x^n}{(1-x)^{n+1}}\)，设 \(B(x) = \sum_{j} \binom{j}{m} x^j = \frac{x^m}{(1-x)^{m+1}}\)。两者的乘积为：$$C(x) = A(x)B(x) = \frac{x^n}{(1-x){n+1}} \cdot \frac{x^m}{(1-x){m+1}} = \frac{x^{n+m}}{(1-x){n+m+2}}$$根据二项式定理（负指数形式）：$$(1-x)^{-N} = \sum_{r=0}^\infty \binom{r+N-1}{N-1} x^r$$在 \(C(x)\) 中，我们需要找 \(x^k\) 的系数。这等价于在 \(\frac{1}{(1-x)^{n+m+2}}\) 中找 \(x^{k-(n+m)}\) 的系数。令 \(r = k-n-m\) 且 \(N = n+m+2\)：$$[x^{k-n-m}] (1-x)^{-(n+m+2)} = \binom{(k-n-m) + (n+m+2) - 1}{(n+m+2) - 1} = \binom{k+1}{n+m+1}$$由此证明等式成立。

其实只需要理解组合意义即可。