范德蒙德卷积
公式ψ(｀∇´)ψ
又称朱世杰-范德蒙德恒等式(Chu-Vandermonde Identity)。
\[
\sum\limits_{i = 0}^k \dbinom{n}{i}\dbinom{m}{k - i} = \dbinom{n + m}{k}
\]
也可以写成：
\[
\sum\limits_{i = -r}^s \dbinom{n}{r + i} \dbinom{m}{s - i} = \dbinom{n + m}{r + s}
\]
证明ψ(｀∇´)ψ
只证明第一个式子，第二个类似。
考虑组合意义。
本质上就是在两个集合 \(S, T\) 当中选 \(k\) 个数，其中 \(|S| = n, |T| = m\)。
也就是分别考虑在两边各选几个，然后乘起来，不难发现它等价于在 \(S\cup T\) 当中选 \(k\) 个，公式得证。
推论ψ(｀∇´)ψ
Iψ(｀∇´)ψ
\[
\sum\limits_{i = 0}^n \dbinom{n}{i}^2 = \dbinom{2n}{n}
\]
由 \(\dbinom{n}{i} = \dbinom{n}{n - i}\)，结合公式可以得到。
IIψ(｀∇´)ψ
\[
\sum\limits_{i = 0}^n \dbinom{n}{i}\dbinom{m}{i} = \dbinom{n + m}{n}
\]
由 \(\dbinom{n}{i} = \dbinom{n}{n - i}\) 结合公式可以得到，推论 I 是这个的特殊情况。
也可以考虑网格图路径计数，用组合意义证明，这里省略不提。
IIIψ(｀∇´)ψ
\[
\sum\limits_{i = 1}^n\dbinom{n}{i}\dbinom{n}{i - 1} = \dbinom{2n}{n - 1}
\]
这个式子要小心下标，没有 \(0\)，所以我们考虑一下怎么搞出 \(0\)。
拆一项出去：
\[
\sum\limits_{i = 1}^{n - 1}\dbinom{n}{i}\dbinom{n}{i - 1} + \dbinom{n}{n - 1}
\]
注意到 \(\dbinom{n}{0} = 1 = \dbinom{n}{n}\)，所以我们可以整体平移一位：
\[
\sum\limits_{i = 0}^{n - 1}\dbinom{n}{i}\dbinom{n}{i + 1} \iff \\
\sum\limits_{i = 0}^{n - 1}\dbinom{n}{i}\dbinom{n}{n - i - 1} \iff \\
\dbinom{2n}{n - 1}
\]
例题ψ(｀∇´)ψ
最后更新:
May 9, 2023