I want to prove this equation, $$ \binom{n}{a}\binom{n-a}{b-a} = \binom{n}{b}\binom{b}{a} $$ I thought of proving this equation by prove that you are using different ways to count the same set of balls and get the same result. But I'm stuck. Help me please.
(Presumptive) Source: Theoretical Exercise 1.14(a), P19, A First Course in Pr, 8th Ed, by S Ross.
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.
