# Combinatorics question

• Nov 28th 2011, 11:34 PM
Mathsdog
Combinatorics question
IN how many ways can the letters in MISSISSIPPI be arranged so that no two Is are adjacent?

The solution is allegedly ${{8}\choose{4}} { 7! \over 2!4!1!}$

But I don't see the logic to this solution. Any insights would be greatly appreciated.

Thanks, MD
• Nov 29th 2011, 12:19 AM
FernandoRevilla
Re: Combinatorics question
Hint: Consider the four I's as a block, then we have seven elements:

$\boxed{IIII}\;MSSSSP,\;\ldots,\; MS\;\boxed{IIII}\; SPSS,\ldots$

We have $\frac{7!}{2!4!1!}$ arrangements of those seven elements. Now, move conveniently the four I's.
• Nov 29th 2011, 02:37 AM
Mathsdog
Re: Combinatorics question
Hey, thanks for your reply FernanoRevilla. That makes sense. (n.b. I left an extra P out of MISSISSIPPI, but have now edited it in). But I still dont see where the ${8 \choose4}$ comes from. If the four had to remain in a block then the solution would be ${8 \choose 1}$ but if any of the positions can be chosen for any of the Is then some of these will contain adjacent Is and others will not eg. MISISISISPP It seems to me this will be included in the ${8 \choose 4}$ factor. No?

Thanks again, MD
• Nov 29th 2011, 04:10 AM
Plato
Re: Combinatorics question
Quote:

Originally Posted by Mathsdog
IN how many ways can the letters in MISSISSIPPI be arranged so that no two Is are adjacent?
The solution is allegedly ${{8}\choose{4}} { 7! \over 2!4!1!}$

For two Is are adjacent, consider "MSSSSPP" that string can be arranged is $\frac{7!}{2!\cdot 4!}$ ways.
Now look at "_M_S_S_S_S_P_P_" there are eight spaces into which the I's can be placed.
Choose four if them: $\binom{8}{4}.$
• Nov 29th 2011, 05:31 AM
FernandoRevilla
Re: Combinatorics question
Quote:

Originally Posted by Plato

No, considering all I's adjacent was a strategy. For that reason I said: now, move conveniently the four I's.
• Nov 29th 2011, 06:35 AM
Soroban
Re: Combinatorics question
Hello, Mathsdog!

Quote:

In how many ways can the letters in MISSISSIPPI be arranged
so that no two I's are adjacent?

The solution is allegedly: ${8\choose4} { 7! \over 2!4!1!}$

Arrange the letters $\{P,P,S,S,S,S,M\}$ in a row.

. . There are: ${7\choose2,4,1} \:=\:\frac{7!}{2!\,4!\,1!}$ arrangements.

Insert a space before, after and between the seven letters:

. . $\square\;X\;\square\;X\;\square\;X\;\square\;X\; \square \;X\;\square\;X\;\square\;X\;\square$

Choose 4 of the 8 spaces and insert the I's.

. . There are:. ${8\choose4}$ choices.

Therefore, there are:. ${8\choose4}\,\frac{7!}{2!\,4!\,1!}$ ways.