Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

"How many ways are there to arrange the letters in the word 'MISSISSIPPI' in such a way that there are no three consonants in a row?"

I am thinking like this. The following are 'slots' for the letters of our word: _ _ _ _ _ _ _ _ _ _ _. There are 21 consonants in total (English). The first slot as 21 possibilities, the second also has 21, but the third has only 5 possibilities. So how many ways can I place vowels within this word... I don't know.

I can try to enumerate all of the place the I's can go, but there has to be a better way than doing that.

share|improve this question
add comment

4 Answers 4

up vote 5 down vote accepted

MISSISSIPPI has seven consonants and four vowels (which all happen to be I). Write X for any consonant, and first think of how many possible patterns of the type IXXIXIXXIXX, with seven Xes and four Is exist, with no three Xs in a row. Then think about how to assign the letters MSSSSPP to the Xs. Note that the two subproblems are quite similar to each other. The final step is a simple multiply.

Edit: A bit more on the first subproblem. You'll have to do a bit of hand counting here, I think. There are only four Is, so consecutive Xs can form at most five groups. But there must be at least four groups of Xs, since no group can have more than two Xs. So the configuration of Xs is either XX XX X X X or permutation thereof, of XX XX XX X or permutations thereof. It should be easy to count the permutations in each case. In the first, case, the Is must go one between each group, but in the second, three Is are needed to fill the gaps, and the fourth I can be placed next to one of the other three, or at the beginning or end – five possibilities there.

share|improve this answer
    
So the first subproblem, we have to figure out how many different ways we can make a pattern with no $3$ X's in a row. This is what I tried to ask, but didn't/don't know how to do. –  Ozera Jul 5 at 15:56
    
You should have made that clear. Rule #1: Always explain your work and tell where you got stuck. I added some detail on that subproblem. The rest is elbow grease, which I insist you provide yourself. –  Harald Hanche-Olsen Jul 5 at 16:11
    
Is the answer 3150? –  Ozera Jul 5 at 18:59
    
Yes, 3150. (I said 3675 earlier, but I found a simple mistake in my calculation.) –  Harald Hanche-Olsen Jul 5 at 21:37
    
Yay! Thank you for taking your time for the assistance. I understand it all now. –  Ozera Jul 5 at 23:59
add comment

One way you could do this is first arrange the four I's in a row, creating 5 gaps in which the consonants can be placed.

If we let $x_i$ be the number of consonants in gap $i$, then $x_1+\cdots +x_5=7$ where $0\le x_i\le2$ for each $i$.

If you calculate the number of solutions to this equation, and then multiply by the number of ways to arrange the consonants SSSSPPM in order, I believe you will get the answer you obtained.

share|improve this answer
    
Yes, that will work. –  Harald Hanche-Olsen Jul 5 at 21:41
add comment

The generating function for the given condition is:

\begin{align*} G(v,c) &= \frac{1+c+c^2}{1-v\left(1+c+c^2\right)} \end{align*}

Since there is one vowel $i$ and three consonants $m,s,p$, we may substitute in the gf to get:

\begin{align*} G(m,s,p,i) &= \frac{1+(m+s+p)+(m+s+p)^2}{1-i\left(1+(m+s+p)+(m+s+p)^2\right)} \end{align*}

and we need to find $[ms^4p^2i^4]$

If the number of M, S, P, I are ${\rm m,s,p,i}$ respectively, then, from the gf:

\begin{align*} \mathrm{N}{\rm(m,s,p,i)} &= \binom{\mathrm{m}+\mathrm{p}+\mathrm{s}}{\mathrm{m},\mathrm{p},\mathrm{s}} \sum_{j=0}^{\mathrm{i}+1}\binom{\mathrm{i}+1}{j}\binom{j}{\mathrm{m}+\mathrm{s}+\mathrm{p}-j} \end{align*}

For ``MISSISSIPPI'', \begin{align*} \mathrm{N}(1,4,2,4) &= 3150 \end{align*}

share|improve this answer
add comment

In order to find the number of combinations, you would find the factorial of the number of letters in MISSISSIPPI, which is $11!$

Now we have to count the indenticals, which means that since there are two P's, you can change the order in two ways to achieve the same result. So we have to divide by 2. Similarly for n of the same letter in a word, we must divide our answer by $n!$.

So our answer becomes $$\frac{11!}{4!4!2!} = 34650$$

share|improve this answer
    
You forgot the requirement of no three constants in a row. –  Harald Hanche-Olsen Jul 5 at 21:38
    
@HaraldHanche-Olsen Forgot to read that sry. Will update the answer –  Varun Iyer Jul 5 at 21:40
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.