范德蒙德卷积公式 (Vandermonde's Identity)

美观起见，证明在 Part 2 。

---

Part 1

范德蒙德卷积公式： \[ \sum_{i=0}^k\dbinom{n}{i}\dbinom{m}{k-i} = \dbinom{n+m}{k} \] 推论1： \[ \sum_{i=-r}^s\dbinom{n}{r+i}\dbinom{m}{s-i}=\dbinom{n+m}{r+s} \] 推论2： \[ \sum_{i=1}^n\dbinom{n}{i}\dbinom{n}{i-1}=\dbinom{2n}{n-1} \] 推论3： \[ \sum_{i=0}^{n}\dbinom{n}{i}^2 = \dbinom{2n}{n} \] 推论4： \[ \sum_{i=0}^{m}\dbinom{n}{i}\dbinom{m}{i} = \dbinom{n+m}{m} \]

---

Part 2

范德蒙德卷积公式 证明： \[ \begin{aligned} \sum_{k=0}^{n+m}\dbinom{n+m}{k}x^k &=(x+1)^{n+m} \\[6pt]&=(x+1)^n(x+1)^m \\[6pt]&=\sum_{r=0}^n\dbinom{n}{r} x^r \sum_{s=0}^m\dbinom{m}{s}x^s \\[6pt]&=\sum_{k=0}^{n+m} \sum_{r=0}^k\dbinom{n}{r}\dbinom{m}{k-r}x^k \end{aligned} \] 即 \[ \dbinom{n+m}{k}=\sum_{r=0}^k\dbinom{n}{r}\dbinom{m}{k-r} \] 推论1 证明类似与原公式，这里不再说明。

推论2 证明： \[ \sum_{i=1}^n\binom{n}{i}\binom{n}{i-1}=\sum_{i=0}^{n-1}\binom{n}{i+1}\binom{n}{i}=\sum_{i=0}^{n-1}\binom{n}{n-1-i}\binom{n}{i}=\binom{2n}{n-1} \] 推论3 证明： \[ \sum_{i=0}^n\binom{n}{i}^2=\sum_{i=0}^n\binom{n}{i}\binom{n}{n-i}=\binom{2n}{n} \] 推论4 证明： \[ \sum_{i=0}^m\binom{n}{i}\binom{m}{i}=\sum_{i=0}^m\binom{n}{i}\binom{m}{m-i}=\binom{n+m}{m} \]

推论4中的 \(\binom{n+m}{m}\) 是我们较为熟悉的网格图路径计数的方案数。所以我们可以考虑其组合意义的证明。

在一张网格图中，从 \((0,0)\) 走到 \((n,m)\) 共走 \(n+m\) 步。规定 \((0,0)\) 位于网格图左上角，其中向下走了 \(n\) 步，向右走了 \(m\) 步，方案数为 \(\binom{n+m}{m}\)。

换个视角，我们将 \(n+m\) 步拆成两部分走，先走 \(n\) 步，再走 \(m\) 步，那么 \(n\) 步中若有 \(i\) 步向右，则 \(m\) 步中就有 \(m-i\) 步向右，故得证。

---

参考文献：

[1] https://oi-wiki.org/math/combinatorics/vandermonde-convolution/