范德蒙德卷积入门是什么？

范德蒙德卷积 范德蒙德卷积(Vandermonde Convolution)是组合数学中的一个重要公式，常用来计算两个组合数的卷积。 定义 给出公式: \[\sum_{i=0}^{k}\binom{n}{i}\binom{m}{k-i} = \binom{n+m}{k} \] 证明 1.组合意义 先假设这样一个具体情境，有一个长度为 \(n+m\) 的布尔型数组，求出这个数组中有 \(k\) 个 \(1\) 的方案数。 显然，答案是 \(\binom{n+m}{k}\) 但是怎么来推左式呢? 将这个数组分为两个部分，一个是前 \(n\) 个元素，一个是后 \(m\) 个元素 当前面一部分取 \(s\) 个元素，后面一部分取 \(k-s\) 个元素时，根据乘法原理我们可以算出这种情况的答案为 \(\binom{n}{s}\binom{m}{k-s}\) 然后再由加法原理，答案就为 \(\sum_{s=0}^{k}\binom{n}{s}\binom{m}{k-s}\) 2.代数推导 下面给出推导过程，需要使用二项式定理进行展开 \[\begin{aligned} \sum_{r=0}^{n+m}\binom{n+m}{r}x^r &= (x+1)^{n+m}\\ &= (x+1)^n(x+1)^m\\ &= \sum_{p=0}^{n}\binom{n}{p}x^p\sum_{q=0}^{m}\binom{m}{q}x^q\\ &= \sum_{p=0}^{n+m}\sum_{q=0}^{p}\binom{n}{q}\binom{m}{p-q}x^q \end{aligned} \] 应用 [CF785D](Problem - 785D - Codeforces) 经典例题 思路 考虑选择 \(\le p\) 的左括号以及 \(\gt p\) 的右括号的方案数，设 \(p\) 左边的左括号数量为 \(x\) ， 右边的右括号的数量为 \(y\) 。