All arrangements : $11!/(4! 4! 2!)=34650$
4s together : $8!/4!2!=840 $
3s together 1s apart : $ 56*7!/(4!2!)=5880$
[When $3s=X$ is at the beginnining or at the end $14*7!/(4!2!)$ cases and if not $42*7!/(4!2!)$ cases]
which gives you $27930$ cases ..
We wish to count how many four-letter words can be formed from the letters of the word MISSISSIPPI that include at least one I.
The word MISSISSIPPI has $1$ M, $4$ Is, $4$ Ss, and $2$ Ps.
We consider cases, depending on how many Is are included.
Case 1: Exactly one I is used. There are three subcases.
- Exactly one I is used and another letter is used three times.
- Exactly one I is used, another letter is used twice, and a different letter is used once.
- Exactly one I is used and three different letters are each used once.
Exactly one I is used and another letter is used three times: The only letter other than I that can be used three times is S. There are $\binom{4}{3}$ ways to choose which positions are occupied by the three Ss. The position of the I is then fixed. Hence, there are
$$\binom{4}{3}$$
admissible arrangements in this case.
Exactly one I is used, another letter is used twice, and a different letter is used once: The letter that is used twice must be a P or an S. That gives us two choices. Once we choose that letter, we are left with two choices for the letter that is used once (M and the letter we did not choose). There are $\binom{4}{2}$ ways to choose the positions of the letter that is used twice and $2!$ ways to arrange the remaining letters in the remaining two positions. Hence, there are
$$\binom{2}{1}\binom{2}{1}\binom{4}{2}2!$$
admissible arrangements in this case.
Exactly one I is used and three different letters are each used once: Then four different letters are each used once. They can be arranged in $4!$ ways.
Case 2: Exactly two Is are used: There are two subcases.
- Exactly two Is are used and another letter is also used twice.
- Exactly two Is are used and two different letters are each used once.
Exactly two Is are used and another letter is also used twice: The other letter must be an S or a P since only one M is available. Thus, we have two choices for the other letter that appears twice and $\binom{4}{2}$ ways to choose which two positions are occupied by that letter. The remaining positions must be filled with Is. Hence, there are
$$\binom{2}{1}\binom{4}{2}$$
admissible arrangements in this case.
Exactly two Is are used and two different letters are each used once: There are
$\binom{3}{2}$ ways to select which two of the other three letters are each used once. There are $\binom{4}{2}$ ways to select the positions of the two Is and $2!$ ways to arrange the remaining letters in the remaining two positions. Hence, there are
$$\binom{3}{2}\binom{4}{2}2!$$
admissible arrangements in this case.
Case 3: Exactly three Is are used: There are three ways to choose which of the other letters will be used in the word and four ways to choose the position of that letter. The remaining positions must be filled with Is. Hence, there are
$$\binom{3}{1}\binom{4}{1}$$
admissible arrangements in this case.
Case 4: Four Is are included.
There is only one way to do this since we must fill all four positions with an I.
Total Since these cases are mutually exclusive and exhaustive, the number of four-letter words that can be formed from the letters of the word MISSISSIPPI is
$$\binom{4}{3} + \binom{2}{1}\binom{2}{1}\binom{4}{2}2! + 4! + \binom{2}{1}\binom{4}{2} + \binom{3}{2}\binom{4}{2}2! + \binom{3}{1}\binom{4}{1} + \binom{4}{4}$$
Best Answer
Leaving out the $S's$ for the moment, there are $\frac{7!}{4!2!} = 105$ permutations of $PPMIIII$
Of these $\frac{6!}{4!} = 30$ will have the $P's$ together, thus $75$ will have the $P's$ apart.
For the together cases, we need to borrow an $S$ to separate them, e.g. $\boxed{PSP}MIIII$
The remaining $3\; S's$ can be inserted in the gaps between units (including ends) in $\binom73$ ways
For cases with $P's$ already separate, e.g. PMPIIII, the $4\; S's$ can be inserted similarly in $\binom84$ ways.
Thus permissible permutations $= 30\binom73 + 75\binom84 = 6300$
For better or worse, this give a value of $k=1$
Use of heavy artillery
To make assurance doubly sure, I have used Jair Taylor's formula to confirm the answer.
Define polynomials for $k\geq 1$ by $q_k(x) = \sum_{i=1}^k \frac{(-1)^{i-k}}{i!} {k-1 \choose i-1}x^i$.
e.g. for $k=2, q_2(x)$ works out to ${(x^2-2x)}/2!$
For the nonce, we shall take the $I's$ to be distinct, divide by $4!$ at the end of the calculations. So we have five distinct alphabets, one of length $2$ and one of length $4$
The number of permutations will be given by
Wolframalpha gives the answer as $151,200$
Dividing by $4!$ to take care of the $4 I's$, we again get the answer of $6300$