Counting Principles - Applications

Vandermonde's Identity is a fundamental combinatorial identity with numerous applications in counting problems involving multiple selections from different groups.

DefinitionVandermonde's Identity

For non-negative integers $m$ , $n$ , and $r$ with $r \leq m+n$ , $\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}$

where we adopt the convention that $\binom{a}{b} = 0$ if $b > a$ or $b < 0$ .

Proof (Combinatorial):

We prove this identity by counting the same objects in two different ways (bijective proof).

Consider selecting $r$ objects from a set of $m+n$ objects. Suppose the objects are partitioned into two groups: group A with $m$ objects and group B with $n$ objects.

The left-hand side $\binom{m+n}{r}$ counts the number of ways to select $r$ objects from all $m+n$ objects without regard to which group they come from.

For the right-hand side, we count by considering how many objects come from each group. If we select $k$ objects from group A, then we must select $r-k$ objects from group B (where $0 \leq k \leq r$ ). The number of ways to do this is $\binom{m}{k}\binom{n}{r-k}$ .

Summing over all possible values of $k$ gives all possible ways to distribute our selection between the two groups: $\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}$

Since both sides count the same thing, they must be equal. $\square$

Proof (Algebraic):

Using the binomial theorem, we have: $(1+x)^m(1+x)^n = (1+x)^{m+n}$

Expanding the left side: $\left(\sum_{k=0}^{m} \binom{m}{k}x^k\right)\left(\sum_{j=0}^{n} \binom{n}{j}x^j\right)$

The coefficient of $x^r$ on the left is obtained by collecting all terms where $k+j = r$ : $\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}$

Expanding the right side: $(1+x)^{m+n} = \sum_{r=0}^{m+n} \binom{m+n}{r}x^r$

The coefficient of $x^r$ on the right is $\binom{m+n}{r}$ .

Since the coefficients of $x^r$ must be equal on both sides, we conclude: $\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}$

This completes the proof. $\square$

ExampleApplication: Committee Selection

A committee of 5 people is to be selected from 7 men and 8 women. Vandermonde's identity tells us: $\binom{15}{5} = \sum_{k=0}^{5} \binom{7}{k}\binom{8}{5-k}$

This equation states that the total number of committees equals the sum of committees with exactly $k$ men (and $5-k$ women) for each $k$ from 0 to 5. This provides both a verification method and an alternative counting strategy when we need to consider gender composition.

Remark

Vandermonde's identity has several special cases. Setting $m = n = r$ gives $\binom{2n}{n} = \sum_{k=0}^{n} \binom{n}{k}^2$ , expressing the central binomial coefficient as a sum of squares. Setting $n = 1$ yields the simpler identity $\binom{m+1}{r} = \binom{m}{r} + \binom{m}{r-1}$ , which is equivalent to Pascal's identity. The identity also extends to negative integers and plays a crucial role in hypergeometric series.