AIOJ

Introduction

Vandermonde's convolution is an identity that combines binomial coefficients and is mainly used in deriving formulas in combinatorics.

Vandermonde's convolution formula

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

Proof

Consider a proof 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}

Therefore:

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

For a proof based on its combinatorial meaning:

Choosing $n+m$ elements from a set of size $k$ is equivalent to splitting the set of size $n+m$ into two sets of sizes $n$ and $m$ , and then choosing $n$ elements from the first set $i$ and $m$ elements from the second set $k-i$ . Since we enumerate $i$ , it is enough to consider one such split, because 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}

By basic combinatorics, we derive:

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

By basic combinatorics, we derive:

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

By basic combinatorics, we derive:

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

$\binom{n+m}{m}$ is the familiar number of paths in a grid, so we can consider a proof based on its combinatorial meaning.

In a grid, going from $(0,0)$ to $(n,m)$ takes $n+m$ steps. Let $(0,0)$ be the upper-left corner; taking $n$ steps downward and $m$ steps to the right gives $\binom{n+m}{m}$ possibilities.

From another viewpoint, split the $n+m$ steps into two parts, first taking $n$ steps and then $m$ steps. If the first $n$ steps contain $i$ rightward steps, then the last $m$ steps contain $m-i$ rightward steps, proving the identity.

Exercises

References and notes

Vandermonde's Convolution Formula