In how many ways can the letters of mississippi be arranged so that no two is are consecutive

I've been working on this question for a while, and i'm in a slump. How many arrangments of Mississippi are there with no consecutive S's? I started with trying to find the ways that it didn't work by grouping all the S's together, as if it were one letter. I then did the equation 10!/(4![*]2!). I was going to continue doing this system, but i'm not sure if this way will work.

Any tips?

In how many ways can the letters of mississippi be arranged so that no two is are consecutive

How many arrangments of Mississippi are there with no consecutive S's?

I think the following will work: You have eleven "slots" for letters. The M, Is, and Ps may be arranged however you like, but no two (or more) Ss may be side-by-side. Considering only seven slots, in how many (distinguishable) ways can you arrange the other seven letters? (Use the formula they gave you for this.) Given all eleven slots, in how many ways can you choose four so that there is at least one empty slot between any given pair of slots? (It might help to think of this as being four double-wide slots, there being an imaginary twelfth slot, and you're needing to pick four of six double-wide slots. Since the first S might go in the first slot, or else it might not, you might want to look at this from each of the right- and left-hand views. That is, multiply the one "six-choose-four" by two.) Since the ordering (left to right) of the other letters does not affect how you chose the slots for the Ss, the two are independent. So multiply to get the total number of ways.

Have fun!

In how many ways can the letters of mississippi be arranged so that no two is are consecutive

Eliz.

In how many ways can the letters of mississippi be arranged so that no two is are consecutive

Here is another way to think about this problem. The other letters will stand between the S’s as separators: _M_I_I_I_P_P_I_ The number of ways those can be arranged is: \(\displaystyle \frac {7!} {(4!)(2!)}\). Now there are eight blanks into which we can place the S’s: \(\displaystyle \binom {8}{4}\).

Answer: \(\displaystyle \binom {8}{4}\frac {7!} {(4!)(2!)}\).

In order to continue enjoying our site, we ask that you confirm your identity as a human. Thank you very much for your cooperation.

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.

Start by removing the P’s & calculating the permutations

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.

Number of permutations of MISSISSIPPI without adjacent P’s

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.

Remove the S’s

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

Using the Multinomial Theorem

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.

Number of permutations of MISSISSIPPI without adjacent S’s

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.

Number of permutations of MISSISSIPPI with at least 2 adjacent S’s

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