# What is the proof of permutations of similar objects?

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

-

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

-

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.

-
Thanks for your answer! I know that it is correct, but I don't get some point! If the number of all the possible cases is n, and k cases are repeated (as second or more times), then we should use subtraction! n-k is the answer then. –  Rasa Mar 11 '12 at 22:54
@Rasoul: I don't understand your comment. Nor do I understand why you think subtraction is the way to go. If we are counting each instance $k$ times, then we need to divide by $k$, not subtract $k$. For instance, if you counted 30 different types, but each answer was counted three times (each answer was counted three times), then the correct count is not $30-3$, it's $30/3$. Nor do I understand why you think you need to add exclamation marks to ask question. –  Arturo Magidin Mar 11 '12 at 22:57
Henceforth, my students will be applying and removing stickers in situations like this. Thank you for this excellent tool. –  Austin Mohr Mar 11 '12 at 23:02
Let's have the set {A,A,A,B}. There are 24 permutations of which 20 are repeated twice or more. Then, 24 - 20= 4 is the answer. –  Rasa Mar 12 '12 at 12:34
@Rasoul: You are counting the total number of repetitions. And your phrasing is poor: "20 are repeated twice or more" makes it sound as if there are 20 distinct permutations that are being counted at least twice (which is not the case). I am counting how many times each permutation is being counted. Each of the permutations is being counted 6 times, so the correct answer is 24 (the total number counted) divided by 6 (the number of times each permutation was counted to reach 24). It's much easier to do it this way than yours, which requires identifying unique counts first. –  Arturo Magidin Mar 12 '12 at 14:54

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.

-

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

-