What is the proof of permutations of similar objects?

Solution 1:

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!}$$

Solution 2:

Add stickers numbered $1,\ldots,n_1$ to the $n_1$ identical objects, so that they are now distinguishable; add stickers to the $n_2$ identical objects as well, etc. Now there are $n!$ permutations, since the objects can be distinguished. You get the kind of permutation you want by ignoring the stickers.

Now imagine taking the stickers off the first $n_1$ identical objects, and permuting the stickers before putting them back into the objects; in how many ways can you do that? $n_1!$ ways; they all correspond to the same underlying permutation of the objects. Similarly with the $n_2$ objects in the second set, the $n_3$ objects in the third set, etc. So there are $n_1!n_2!\cdots n_r!$ orderings of the stickered objects that correspond to the same underlying permutation of the indistinguishable objects. So we divide by that extra factor to get the correct number.

Solution 3:

I had a hard time wrapping my head around this for a while myself, but I think the best way to look at it is this. Imagine you have some simple set like $\{a,a,a,b\}$, so that you know how many distinct permutations there are: $\{aaab, aaba, abaa, baaa\}$ thus 4. We can easily use the sticker method mentioned to see that we have:

$\{a_1a_2a_3b,\;a_1a_3a_2b,\;a_2a_1a_3b,\;a_2a_3a_1b,\;a_3a_1a_2b,\;a_3a_2a_1b \} $ thus 6 permutations/distinct permutation, that is 6 permutations per distinct permutation we wouldn't be able to distinguish if we removed the stickers.

Thus, $4 \;\text{distinct permutations} \times 6 \; (\text{permutations}\,/\,\text{distinct permutation}) = 24 \;\text{permutations}$, i.e. the number of permutations you get by distinguishing each of the objects in your set.

This is all well and good, but usually we want to work the other way around, that is, we know that we have 24 permutations and we know that for each distinct permutation there are 6 permutations. But this is easy, in our example we have: $24\;\text{permutations}\;/\;(6\;\text{permutations}\,/ \,\text{distinct permutation})=4\;\text{distinct permutations}$.

So in the general case, you just take $n!$ permutations and divide by $r!$ permutations per distinct permutation (for $r$ repeated things) and you get $\frac{n!}{r!}=c$ distinct permutations.

Now, when there are more than one type of indistinguishable object, then the only thing that changes is the way you calculate the number of permutations per distinct permutation. Suppose our example above changes to $\{aaabb\}$. Now there are $3!\times2!=12$ permutations per distinct permutation, so there are $5!\,/\,(3!\times2!)=10$ distinct permutations. In general when there are $n_1$ indistinguishable objects of type $1$, $n_2$ indistinguishable objects of type $2$, ... , $n_k$ indistinguishable objects of type $k$, you now have $n_1!n_2!...n_k!$ as the number of permutations per distinct permutation, so that $c=\frac{n!}{(n_1!n_2!\,\times \text{ ... }\times \,n_k!)}$ is the number of distinct permutations.