Vandermonde's Convolution

Introduction

Vandermonde's convolution is a formula for combining binomial coefficients, primarily used in the derivation of combinatorial mathematics formulas.

Vandermonde's Convolution Formula

\[ \sum_{i=0}^k\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k} \]

Proof

Consider proving using the binomial theorem:

\[ \begin{aligned} \sum_{k=0}^{n+m}\binom{n+m}{k}x^k&=(x+1)^{n+m}\\ &=(x+1)^n(x+1)^m\\ &=\sum_{r=0}^n\binom{n}{r}x^r\sum_{s=0}^m\binom{m}{s}x^s\\ &=\sum_{k=0}^{n+m}\sum_{r=0}^k\binom{n}{r}\binom{m}{k-r}x^k\\ \end{aligned} \]

Thus we have:

\[ \binom{n+m}{k}=\sum_{r=0}^k\binom{n}{r}\binom{m}{k-r} \]

Alternatively, consider a combinatorial proof:

Choosing \(k\) elements from a set of size \(n+m\) is equivalent to splitting the set of size \(n+m\) into two subsets of sizes \(n\) and \(m\), then choosing \(i\) elements from the subset of size \(n\) and \(k-i\) elements from the subset of size \(m\). Since we sum over all \(i\), we only need to consider one way of splitting, as different splits are equivalent.

Corollaries

Corollary 1 and Proof

\[ \sum_{i=-r}^{s}\binom{n}{r+i}\binom{m}{s-i}=\binom{n+m}{r+s} \]

The proof is similar to that of the original formula.

Corollary 2 and Proof

\[ \sum_{i=1}^n\binom{n}{i}\binom{n}{i-1}=\binom{2n}{n-1} \]

Derived from basic combinatorial knowledge:

\[ \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} \]

Corollary 3 and Proof

\[ \sum_{i=0}^n\binom{n}{i}^2=\binom{2n}{n} \]

Derived from basic combinatorial knowledge:

\[ \sum_{i=0}^n\binom{n}{i}^2=\sum_{i=0}^n\binom{n}{i}\binom{n}{n-i}=\binom{2n}{n} \]

Corollary 4 and Proof

\[ \sum_{i=0}^m\binom{n}{i}\binom{m}{i}=\binom{n+m}{m} \]

Derived from basic combinatorial knowledge:

\[ \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} \]

Here, \(\binom{n+m}{m}\) is the familiar number of paths in a grid graph. Thus, we can consider a combinatorial proof.

In a grid graph, moving from \((0,0)\) to \((n,m)\) takes \(n+m\) steps. Let \((0,0)\) be the top-left corner, with \(n\) steps down and \(m\) steps right. The number of paths is \(\binom{n+m}{m}\).

From another perspective, split the \(n+m\) steps into two parts: first take \(n\) steps, then take \(m\) steps. If among the first \(n\) steps, \(i\) steps are to the right, then among the next \(m\) steps, \(m-i\) steps are to the right. This completes the proof.

Exercises

• CF785D Anton and School - 2

• Luogu P2791 Kindergarten Basketball Problem

References and Notes

1. Vandermonde's Convolution Formula

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用