How many different words can be formed by jumbling the letter in the word Mississippi in which the four Is not come together?

Today I’m continuing to talk about the fundamentals of combinatorics with the Multinomial Theorem, and what better way to do this than to tackle some classic combinatorics problems 😉

Have you got the chops to solve these problems?

Problem 1

How many total arrangements of the letters in MISSISSIPPI are there?

Problem 2

How many arrangements of the letters in MISSISSIPPI exist such that the 2 P’s are separated?

Problem 3

How many arrangements of the letters in MISSISSIPPI have at least 2 adjacent S’s?

Note:

If you need a review of the basics, check out this intro to combinatorics post:

In the last post we discovered that we can find the number of unique permutations by using the Fundamental Theorem of Counting.

Since MISSISSIPPI has 11 letters, draw eleven lines and fill each in with the number of available letter choices, e.g. 11 options for the first, 10 for the second, and so on…

This is equal to 11! or 39,916,800 permutations.

But is this correct for the unique permutations of the letters in MISSISSIPPI?

Consider this…

What happens if I switch the 3rd and 4th letters in MISSISSIPPI and leave all else the same? Are those different permutations?

Nope.

The 3rd and 4th letters are both S’s so switching them changes nothing. The above calculation is an over count because of these repeat letters.

So how do we adjust for these extra repeated arrangements?

Adjusting for Repeats

To adjust our calculation we need to divide out the duplicate permutations. Finding them isn’t too difficult.

First determine what causes repeated arrangements. This comes from letters that occur more than once. For MISSISSIPPI that includes 2 P’s, 4 I’s, and 4 S’s.

Let’s start with the P’s. For every permutation, we can make an identical permutation with the P’s in opposite positions. So to adjust for these duplications, we must divide by 2! (the number of ways we can arrange the 2 P’s).

To adjust for the repeated I’s, divide by the number of ways we can arrange 4 I’s, which is 4!.

Lastly to account for the 4 S’s divide by another 4!.

There we go! There are 34,650 permutations of the word MISSISSIPPI.

The Multinomial Theorem

This process of dividing out repeated permutations is exactly what the Multinomial Theorem is!

The Multinomial Theorem says in order to count the number of distinct ways a set of elements with duplicate items can be ordered all you need to do is divide the total number of permutations by the factorial of the quantity of each duplicate (turns out doing the math is easier than writing that sentence 😳 ).

So since MISSISSIPPI has 11 total letters with 2 P’s, 4 I’s, and 4 S’s our calculation is: 11!/(2!4!4!).

Solution #2: No Adjacent P’s

To solve this problem we have to get a little creative. We need to count the ways we can make permutations so that no P’s are adjacent. Let’s start simple and remove the P’s altogether.

This of course is just one arrangement of MISSISSII, how many ways could we rearrange those letters? Using the Multinomial Theorem there are 9!/(4!4!) or 630 permutations.

Okay, now let’s deal with the P’s. I’m going to draw in blanks before and after every letter of MISSISSII. These will represent the possible places we can insert P’s, and because each space is separated by some non-P letter, we know these are all safe possibilities.

We have 10 blanks and we can choose any 2 blanks to insert P’s at, so we need to calculate 10 choose 2 = 45 ways (click here for recap on the “choose” combinations formula).

Alright, last step.

We calculated that there are 630 ways of rearranging the non-P letters and 45 ways of inserting P’s, so to find the total number of desired permutations use the basic principle of counting, i.e. multiply the values together.

So there are 28,350 permutations of MISSISSIPPI where the P’s are not adjacent.

Solution #3: At Least 2 Adjacent S’s

Where to begin? You know, we could come at this problem from the opposite angle. Instead of counting how many permutations have 2 or more adjacent S’s, we could find how many permutations have no adjacent S’s and then subtract that number from the total permutations of MISSISSIPPI.

Shall we try that?

Okay, this is similar to our last problem then. Start by removing the S’s and finding the permutations of the remaining letters using the Multinomial Theorem.

We have 7 letters with 4 I’s and 2 P’s, so that’s a total of 105 permutations.

Next add blanks before and after each letter to represent places we can insert S’s.

There are 8 blanks and we have 4 S’s that can be inserted into any of those blanks. So let’s calculate 8 choose 4:

And then multiply the results together.

That gives us the number of permutations of MISSISSIPPI without adjacent S’s. Remember we want to find the opposite. We want to know how many permutations have at least 2 adjacent S’s.

We know from problem #1 there are 34,650 permutations of MISSISSIPPI and we now know that 7,350 arrangements have no adjacent S’s, so to find the permutations with at least 2 adjacent S’s simply take the difference.

So there are 27,300 permutations with 2 or more adjacent S’s.