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.

Given word MISSISSIPPI I am asked to count the number of (1) permutations where all P's are side-by-side (2) permutations where P's are side-by-side and I's are side-by-side. For the first question, I did $$\frac{9!}{4! 4!} \times 10$$ since I have two sets of 4 indistinguishable letters, and I multiply by 10 because 2 P's can be placed in 10 different places in between/to the sides of the remaining letters. The (2) confounds me though. I did start with $$\frac{5!}{4!}$$ and proceeded to multiply by the number of ways I's and P's could vary within the word. So, fixing PP in the beginning, I got 6 variations for IIII, and vice-versa. But now that I can consider moving PP a letter to the right (e.g. MPP...) and then counting possibilities, it seems to get hairy. Is there an easier way to calculate (2) (and perhaps even (1)?)

share|improve this question
    
Should the first question be "... where both P's are side-by-side"? Otherwise your solution does not appear to make sense. –  Henning Makholm Sep 20 '11 at 3:49
    
@Henning: Yes, sorry for my mistake –  permute Sep 20 '11 at 3:52

2 Answers 2

up vote 3 down vote accepted

If all the P's must be together, then it is simpler to consider them as a single "block", PP, which must stay together. Then you just need to arrange this block and the letters M, S, S, S, S, I, I, I, and I. So you are trying to find all possible arrangements of >

PP, M, S, S, S, S, I, I, I, I

This gives you 10 things to arrange in order, $10!$, and then you should divide off by the permutations of the S's ($4!$) and those of the Is ($4!$). So it seems to me that the answer to the first question should be $$\frac{10!}{4!4!}.$$ That gives the same answer you got, but it sets the stage for the second question.

For the second question, put all the I's together, and put all the P's together. You need to arrange >

IIII, PP, M, S, S, S, S

so you have 7 things to arrange; you should divide by the four permutations of the S's, so I would get $$\frac{7!}{4!}$$ different ways of doing it.

share|improve this answer

In (1) you have in effect $10$ positions to be filled, one with PP, one with M, and four each with I and S. There are $\dbinom{10}4$ ways to choose which of the $10$ positions will be I, $\dbinom64$ ways to choose which of the remaining $6$ positions will be S, and $\dbinom21$ ways to choose one of the last two positions for the M, leaving the other for the PP. This comes to a total of $$\binom{10}4\binom64\binom21 = \frac{10!}{4!6!}\cdot\frac{6!}{4!2!}\cdot\frac{2!}{1!1!} = \frac{10!}{4!4!} = 6300$$ permutations.

The same reasoning will work for (2), except that you now have only $7$ positions to be filled, four with S and one each with M, PP, and IIII: $$\binom74\binom31\binom21 = \frac{7!}{4!3!}\cdot\frac{3!}{1!2!}\cdot\frac{2!}{1!1!} = \frac{7!}{4!} = 7\cdot 6\cdot 5 = 210.$$

share|improve this answer
    
First question has beend edited. –  Arturo Magidin Sep 20 '11 at 4:05
    
@Arturo: Thanks for the heads-up. –  Brian M. Scott Sep 20 '11 at 4:14

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.