Why is $\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}$

Question

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.

Answer 1

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).

Answer 2

A quite simple combinatoric argument for your formula can be given using permutations with repetition.

Consider $n$ objects consisting of $r_1$ identical objects of type $1$, $r_2$ identical objects of type $2$ and so on till $r_k$ identical objects of type $k$.

LHS of your formula:

The number of different permutations of the $n= r_1 + \cdots + r_k$ objects:

$$\frac{n!}{r_1!\cdots r_k!}$$

RHS of your formula:

Just count the different permutations as follows:

• Choose $r_1$ out of $n$ places where to put the $r_1$ identical objects of type $1$: $\binom{n}{r_1}$
• Choose $r_2$ out of $n-r_1$ places where to put the $r_2$ identical objects of type $2$: $\binom{n-r_2}{r_2}$

... and so on till

• Choose the remaining $r_k$ places to put the $r_k$ objects of type $k$: $\binom{n-r_1 - \dots - r_{k-1}}{r_k} = \binom{r_k}{r_k}$

This gives $$\binom{n}{r_1}\cdot\binom{n-r_1}{r_2} \cdots\binom{r_k}{r_k}$$