# explanation for a combinatorial identity involving the binomial coefficient

I am looking for an intuitive explanation for the identity:

$$\binom{n}{h}\binom{n-h}{k} = \binom{n}{k}\binom{n-k}{h}$$

Thanks!

## 3 Answers

both count the number of possibilities for choosing two disjoint subsets from a set of size $n$, one with $h$ elements the other with $k$ elements.

$\binom{n}{h}$ means possible numbers of choosing $h$ objects out of $n$. So, possible numbers of choosing $h$ out of $n$ then choosing $k$ objects out of $n-h$ objects which are not chosen before would be $\binom{n}{h}\binom{n-h}{k}$. Similarly, choosing $k$ objects first and $h$ objects later out of $n$ would be $\binom{n}{k}\binom{n-k}{h}$ cases. Since these two works are same as choosing $h$ objects and $k$ objects separately, number of possible cases are same. So, following identity is true. $$\binom{n}{h}\binom{n-h}{k} = \binom{n}{k}\binom{n-k}{h}$$

The first counts the ways to choose $h$ objects from $n$ distinct objects and then $k$ objects from the remainder.

The second counts the ways to choose $k$ objects from $n$ distinct objects and then $h$ objects from that remainder.

The order of selection is irrelevant; both count the way to select $h$ and $k$ objects into separate sets (leaving $n-h-k$).  Thus they are equal.

$${n \choose h}{n-k \choose k} \\ = \frac{n!}{h!(n-h)!}\frac{(n-h)!}{k!(n-h-k)!} \\ = \frac{n!}{h!k!(n-h-k)!} \\ =\frac{n!}{k!(n-k)!}\frac{(n-k)!}{h!(n-h-k)!} \\ ={n\choose k}{n-k\choose h}$$