[Math] Combinatorial Proof Of Binomial Double Counting

binomial-coefficientscombinatoricsdiscrete mathematics

Let $a$, $b$, $c$ and $n$ be non-negative integers.

By counting the number of committees
consisting of $n$ sentient beings that can
be chosen from a pool of $a$ kittens, $b$
crocodiles and $c$ emus in two different
ways, prove the identity

$$\sum\limits_{\substack{i,j,k \ge 0; \\ i+j+k = n}} {{a \choose i}\cdot{b \choose j}\cdot{c \choose k} = {a+b+c \choose n}}$$

where the sum is over all non-negative integers $i$, $j$ and $k$ such that $i+j+k=n.$

I know that this is some kind of combinatorial proof. My biggest problem is that I've never really done a proof.

Best Answer

On the righthand side, we form a committee of size $n$ by lumping all the animals together (so there are $a + b + c$ animals total) and choosing $n$ of them.

On the lefthand side, we form a committee of size $n$ by first choosing exactly $i$ kittens, $j$ crocodiles, and $k$ emus (subject to $i + j + k = n$). For fixed $i$, $j$, and $k$, there are $$ \binom{a}{i}\binom{b}{j}\binom{c}{k} $$ such committees. Summing over all possible partitions of the integer $n$ means we've formed the committees in every possible way, which is precisely what is counted on the righthand side.

Related Question