Arranging the word 'MISSISSIPPI'

Solution 1:

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.

Solution 2:

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.

Solution 3:

The number of solutions to $x_1+x_2+x_3+x_4+x_5 = 7$ with $0 \leq x_i \leq 2$ is same as the coefficient of $x^7$ in $(1+x+x^2)^5$. This can be expanded using binomial theorem as $(1+x(1+x))^5$. Since $x^7$ will occur only in the terms $\binom{5}{4}x^4(1+x)^4$ and $\binom{5}{5}x^5(1+x)^5$, the required coefficient is $\binom{5}{4}\binom{4}{3} + \binom{5}{5}\binom{5}{2} = 30$. Since there are $\binom{7}{4,2,1} = 105$ ways to place $SSSSPPM$ in these 7 places, the required answer is 3150.

Solution 4:

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*}