What is the proof that permutations of similar objects is counted by the multinomial coefficient? What is the proof that the number of permutations of similar objects is counted by the multinomial coefficient? 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!}$$
 A: 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!\cdot n_2! \cdot \dotsc \cdot n_k!}$$ is the number of distinct permutations.
A: 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!}$$
A: 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.
A: 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!)$ 
A: I know this is 11 years late, but I had the same problem and I hope this helps other people that didn't quite understand the accepted answer (like me ;) )
I recommend you watch this video by Eddie Woo, it made everything snap in place for me: https://www.youtube.com/watch?v=1Uy2E2ncazg. I recommend if after my explanation you still don't understand to check him out.
Here is my, a bit more formal, explanation:
Main explanation
Essentially let's consider a word, he uses the example of Kellly (with 3 ls).
Now let's distinguish the ls with numbers:
K E L1 L2 L3 Y
And let's write every possible permutation of this word in a table (with distinguished ls, so with L1, L2 and L3), but let's do it in a particular way:




1
2
3
4
5
6




KEL1L2L3Y
KEL1L3L2Y
KEL2L1L3Y
KEL2L3L1Y
KEL3L2L1Y
KEL3L2L1Y


YL1L2L3EK
YL1L3L2EK
.
.
.
.


.
.
.
.
.
.


.
.
.
.
.
.


.
.
.
.
.
.




We immediately notice that the same permutation is repeated multiple times. For instance KEL1L2L3Y = KEL2L1L3Y = KEL3L1L2Y = ...
And the thing is that we overcounted by a factor of 6, or 3!, because we have a valid permutation, and then we have another permutation where the only thing that swapped were the ls. So essentially we counted 3! times more than we should have, one time per permutation of the repeated letters How do we account for that? We simply divide by the number of possible permutations of the ls, which is the number of ls factorial.
Why do we have to divide?
Now, you might ask, why do we divide? This isn't explained by Eddie Woo, this is my explanation.
Using geometry
Let's consider the previous table:




1
2
3
4
5
6




KEL1L2L3Y
KEL1L3L2Y
KEL2L1L3Y
KEL2L3L1Y
KEL3L2L1Y
KEL3L2L1Y


YL1L2L3EK
YL1L3L2EK
.
.
.
.


.
.
.
.
.
.


.
.
.
.
.
.


.
.
.
.
.
.




If we consider every word as a unit, this is a rectangle of area n! (because it contains every possible permutation). Now we already know that the number of columns  (the top side) is of length n1!, the number of possible permutations of the repeated letters. What we want to know is the number of rows, the left side, which contains every group of permutations that is equal. We know the area, we know one of the sides, so the other side is
$$
\frac{A}{l} = \frac{n!}{n1!}
$$
Using equations
You may have noticed that we overcounted 5 (n1! - 1) elements per each "valid" element. so the number of rows $r$ is equal to all possible permutations $n!$ minus the number of extra permutations (or the number of permutations of the repeated letters minus 1, the "valid" one) $(n1! - 1)$ times the number of rows $r$. So
$$
r = n! - r(n1! - 1) => 
$$
$$
r + r(n1! - 1) = n! => 
$$
$$
r(1 + n1! - 1) = r(n1!) = n! => 
$$
$$
r = \frac{n!}{n1!}
$$
Repeated letters
Now, what about different letters repeated, like the word mississipi? We just repeat the same thing for every repeated letter, so that we account for the first letter, then the second, then the third ...
PS: Another way to think about it is that the number of columns, so the number of permutations of the repeated letters is simply equal to $n1!n2!n3!...nr!$, because they are independent permutations that are thus being multiplied together.
Hence
The number of permutations of $n=n1+n2+⋯+nr$ objects of which $n1$ are of one type, $n2$ are of a second type, $…$ , and $nr$ are of an rth type is
$$
\frac{n!}{n1!n2!...nr!}
$$
