Prove $\binom{n}{a}\binom{n-a}{b-a} = \binom{n}{b}\binom{b}{a}$

First comes a bureaucratic answer.

We have a group of $n$ people. We want to select a committee of $b$ people, and choose $a$ of them to be a steering subcommittee.

The right-hand side counts the number of ways to pick the committee of $b$ people, and then choose the steering subcommittee from this committee.

The left-hand side picks the steering subcommittee first, then the rest of the committee.

Both sides count the same thing, so they are the same.


Or else we want to choose $b$ people from a class of $n$ to go on a trip. Of these $b$ people, $a$ will ride in the limousine, and the rest in an old bus. We can choose the $b$ people, and then choose the $a$ of them who will ride in the limousine.

Or else we can choose the $a$ people who will ride in the limousine , and then pick $b-a$ people from the remaining $n-a$ to ride in the bus.


Directly, we find that

\begin{align*} {n \choose a}{n - a \choose b - a} &= \frac{n!}{(n - a)!a!} \frac{(n - a)!}{(n - a - (b - a))! (b - a)!} \\ &= \frac{n!}{a!} \frac{1}{(n - b)!(b - a)!} \\ &= \frac{n!}{(n - b)! b!} \frac{b!}{(b - a)!a!} \\ &= {n \choose b}{b \choose a} \end{align*}

The third equality follows by multiplying and dividing by $b!$.


These are just two different ways to express the trinomial coefficient $\binom n{a,b-a,n-b}$ as a product of two binomial coefficients. The relevant formula (not obviously present on the wikipedia page) is $$ \binom n{k,l,m} = \binom nk\binom {n-k}l \qquad\text{whenever $k+l+m=n$,} $$ together with the symmetry with respect to $x,y,z$ of the trinomial coefficient, and similarly for binomial coefficients (so that $\binom nb=\binom n{n-b}$). The formula above is a consequence of $(X+Y+Z)^n=(X+(Y+Z))^n$, and similar formulas hold for higher multinomial coefficients.


Given $n$ people, we can form a committee of size $b$ in ${n\choose b}$ ways. Once the committee is formed we can form a sub-committee of size $a$ in ${b\choose a}$ ways. Thus we can form a committee of size $b$ with a sub-committee of size $a$ in ${n\choose b}{b\choose a}$ ways. We can count the same thing by forming the sub-committee first and then forming the committee that contains the sub-committee. Given $n$ people we can form a sub-committee of size $a$ in ${n\choose a}$ ways. Once the sub-committee is formed we must form the committee of size $b-a$ from the remaining $n-a$ people in ${n-a\choose b-a}$ ways. Thus we can form a sub-committee of size $a$ while forming the committee of size $b-a$ that contains the sub-committee in ${n\choose a}{n-a\choose b-a}$ ways. Hence ${n\choose b}{b\choose a}={n\choose a}{n-a\choose b-a}$.

This combinatorial identity is known as the Subset-of-a-Subset identity.