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)?)
Ordering letters in the word
-
0@He$n$ning: Y$e$s, sorry for my mistake – 2011-09-20
2 Answers
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.
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.$
-
0@Arturo: Thanks for the heads-up. – 2011-09-20