Rearranging MISSISSIPPI
The puzzle
How many distinguishable ways can the letters of MISSISSIPPI be rearranged?
The word has 11 letters: one M, four I, four S and two P.
Stuck?
One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.
Hint 1
11! = 39,916,800 counts every arrangement as if the letters were all different.
Hint 2
Swapping two of the S around produces the same word, so each distinct word has been counted many times. How many?
Show the answer Hide the answer
34,650.
How to get there
If all eleven letters were distinct there would be 11! = 39,916,800 orders. They are not: the four I can be permuted among their positions in 4! = 24 ways without changing the word, and likewise the four S in 24 ways and the two P in 2.
So every distinct word has been counted 24 x 24 x 2 = 1,152 times, and the answer is 39,916,800 / 1,152 = 34,650.
The general formula for a word of length n with repeat counts a, b, c, ... is n! divided by a! b! c! ... - a multinomial coefficient. The same reasoning explains why BANANA has 6!/(3!2!) = 60 arrangements and why a word with no repeats simply has n!.
The technique worth keeping
Count as if everything were distinguishable, then divide by the rearrangements that leave the result unchanged. Overcounting by a known factor and dividing is almost always easier than counting correctly first time.