In a book intended as an Introduction to Combinatorics it included the following equality, but it didn't really explain why.
$$\frac{n!}{{r_1}!{r_2}!\dots{r_k}!}=\binom{n}{r_1}\times\binom{n-r_1}{r_2}\times\binom{n-r_1-r_2}{r_3}\times\dots\times\binom{r_k}{r_k}$$
Would you mind providing a combinatorial insight into why this is true? Please don't provide an algebraic proof; I can prove it using algebra myself :))
Thank you for your kind help.
Best Answer
The multinomial represents the number of ways of simultaneously choosing sets of size $r_1$, $r_2$, $\ldots$, $r_k$ from a set of size $n$ (where $\sum_{i=1}^k r_i=n$; in other words, every element has been chosen). But that choice doesn't have to be performed simultaneously; we can imagine first choosing $r_1$ items from our set of $n$, then choosing $r_2$ items from the remaining set of $n-r_1$, etc. The last choice will be taking $r_k$ items from the remaining set of $n-(r_1+r_2+\ldots+r_{k-1})$ things, but since $\sum_i r_i=n$, ${n-(r_1+\ldots+r_{k-1})\choose r_k}$ is just ${r_k\choose r_k}$ (and, as you'd expect, there's only one way to do it — we're choosing all the remaining things).