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!}$$
$\endgroup$4 Answers
$\begingroup$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!}$$
$\endgroup$ 2 $\begingroup$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.
$\endgroup$ 5 $\begingroup$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.
$\endgroup$ $\begingroup$Consider an example of: (a1,a2,a3,b1,b2) where a1,a2,a3 are the same, b1, b2 are the same.
There are 5! for the number of permutation (a1,a2,a3,b1,b2) if they are all different. However, if a1,a2,a3 are the same, then permuting a1,a2,a3 gives the same permutation => Each permutation is repeated 3! times Similarly, if b1,b2 are the same, making each permutation repeat 2! times...
so the number of different permutation is $5!/(2! 3!)$
$\endgroup$
