Combinatorics – Proof that Permutations of Similar Objects are Counted by the Multinomial Coefficient

combinatoricspermutations

What is the proof of permutations of similar objects? I know the formula, but I cannot figure out how to derive it!

permutations of similar objects
The number of permutations of $n=n_1+n_2+\dots+n_r$ objects of which $n_1$ are of one type, $n_2$ are of a second type, $\dots$ , and $n_r$ are of an $r$th type is

$$\frac{n!}{n_1!n_2!…n_r!}$$

Best Answer

Another way of looking at this is:

You have $n = n_1 + n_2 + \dots + n_r$ slots and need to fill them all.

You can fill in the $n_1$ items of type $1$ in $\binom{n}{n_1}$ ways.

The remaining $n-n_1$ slots can be filled with $n_2$ items in $\binom{n-n_1}{n_2}$ ways.

Continuing this way, the required number of ways is

$$ \binom{n}{n_1} \cdot \binom{n-n_1}{n_2} \cdots \binom{n-n_1-n_2-\dots-n_{r-2}}{n_{r-1}} \cdot 1 =$$

$$ \frac{n!}{n_1! (n-n_1)!} \cdot \frac{ (n-n_1)!}{(n-n_1-n_2)! n_2!} \cdots \frac{(n-n_1-n_2 - \dots -n_{r-2})!}{n_r! n_{r-1}!} = $$

$$ \frac{n!}{n_1! n_2! \dots n_r!}$$

Related Question