范德蒙德卷积公式 (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/