Counting When There Are Repeats

How many ways can you arrange the letters in the word “MISSISSIPPI”?

This is a popular problem that I always bring up with my statistics students who are first learning how to count. If you are not familiar with the three counting techniques of factorials, permutations, and combinations, bring yourself up to speed by reading my previous post, Counting Can Be Really Tough.

We first must notice that there are 11 letters.  So, using the factorials we previously learned, we start with 11!, which you can find using WolframAlpha. This is much too large, however.

Can you tell the difference between the following two permutations?

• MISSISSIPPI
• MISSISSIPPI

Look closer.  Can you see it?  I switched the “S” in the 3rd spot with the “S” in the 7th spot and switched the 2nd “I” with the 11th “I”.  You may chuckle, but these are different permutations.

The point is, we shouldn’t count these different permutations since we cannot distinguish between the two. There are repeats.

First, let’s analyze a simple example.  How many arrangements for the letters in the word NOON?

We can list all of them: {NNOO, NONO, NOON, OONN, ONON, ONNO}.

There are 6. But how could we have arrived at that analytically, so that we can answer tougher questions like the one above?

Approach 1: Using Combinations

There are four letters that need arranged (two N’s and two O’s) into one “word” so lets create the placeholders for them.

____   ____   ____   ____

We have four placeholders now.  Let’s choose two of the placeholders to place our N’s.  Taking from what we learned last time, we need to use combinations (since we don’t want to count the two ways we can switch the N’s).  There are n=4 placeholders and r=2 placeholder we need to choose for the N’s.

Using a calculator or typing in “nCr(4,2)” or “4 nCr 2” into WolframAlpha (it is very forgiving), we find there are 6 ways of doing this.

Wait, we haven’t chosen the O’s yet and we are already at 6!

That is because once we have chosen our place for the N’s, the O’s must go in the remaining two spots.  There are 2 placeholders, and we need to choose 2 for the O’s.  If you type in nCr(2,2), you will find that this is 1.

So, for each of the 6 ways you can choose an N, there is only 1 remaining way to choose the O’s.  Thus, 6*1=6.

How does this work for MISSISSIPPI?  We should notice that there is 1 M, 4 I’s, 4 S’s, and 2 P’s in this word.

____   ____   ____   ____   ____  ____   ____   ____   ____   ____  ____

To count this up, we calculate the following and multiply them all together.

• 11 placeholders and 1 M: nCr(11,1) = 11
• Now, 10 placeholders and 4 I’s: nCr(10,4) = 210
• Now, 6 placeholders and 4 S’s: nCr(6,4) = 15
• Now, 2 placeholders and 2 P’s: nCr(2,2) = 1

Multiply them together, and we get 34650.

Wait. What if we had chosen the placeholders in a different way? Would we get the same number? The answer is yes.  Let’s try counting in a different way.

• 11 placeholders and 4 S’s: nCr(11,4) = 330
• Now, 7 placeholders and 2 P’s: nCr(7,2) = 21
• Now, 5 placeholders and 4 I’s: nCr(5,4) = 5
• Now, 1 placeholder and 1 M: nCr(1,1) = 1

Multiply them together, and we still get 34650.

Approach 2: Using a quick formula

This counting approach requires a formula which is derived from the formula for combinations.  You learned how to quickly use it on the calculator, but the formula and usual notation for combinations is

where nCr is the same as .

The quick formula for counting the number of special permutations (where there are repeats of indistinguishable characters) is

where you have a total of n characters and k distinct characters, of the first kind, of the second kind, and so on, down to of the kth kind.

In our example of MISSISSIPPI, there are 11 total letters (), and 4 distinct letters (M, I, S, and P). There is 1 M (), 4 I’s (), 4 S’s (), and 2 P’s ().  Our answer can be quickly arrived at not by

Using this tool in my next post, I’m going to explain the solution to the Riddler Classic from the November 3rd post Can You Help A Frogger Out? We will also learn of a faster and elegant way of finding the answer using the famous Fibonacci sequence.