Number of ways to choose a sequence of three letters from the letters of MISSISSIPPI

Question

How many ways can a sequence of three letters be chosen from the letters of MISSISSIPPI?

I'm just a little confused how to go about this since so many letters repeat I=4 S=4 P=2

So ultimately there are 4 different letters.

Answer 1

For a generating function solution, use exponential generating functions.

Let's take an example that's a bit simpler than yours. How many three-letter words can be made from the letters in AABBB? If you were simply forming a multiset of three letters, but not arranging them in order, you could let $r$ be the number of As and $3-r$ be the number of Bs. Then $r$ could be any of $0,$ $1,$ or $2.$ So the number of such multisets is $3.$ Notice that $3$ is the coefficient in front of $x^3$ in the expansion of $(1+x+x^2)(1+x+x^2+x^3).$ The first factor reflects the fact that you can take $0,$ $1,$ or $2$ As, and the second that you can take $0,$ $1,$ $2,$ or $3$ Bs. Since As are not distinguishable and Bs are not distinguishable, there is only one way to take a particular number of As or Bs. This is why the coefficients in front of the powers of $x$ are all $1.$

Now let's worry about how many ways there are to arrange the letters in a multiset. If our multiset has $r$ As and $n-r$ Bs, there are $\frac{n!}{r!(n-r)!}={}_nC_r$ ways to arrange the letters. We can account for this by using exponential generating functions instead of ordinary generating functions. The way this works is that we expand $$ \left(\frac{1}{0!}+\frac{x}{1!}+\frac{x^2}{2!}\right)\left(\frac{1}{0!}+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}\right). $$ Again we find the coefficient of $x^3$ in the expanded function, but this time we multiply the coefficient by $3!.$ An equivalent way to say this is that we find the coefficient of $\frac{x^3}{3!}$ in the expansion. This coefficient is guaranteed to be a whole number since it is effectively introducing binomial coefficients into the expansion. In the unordered example above, $x^3$ arose as the sum $1\cdot x^3+x\cdot x^2+x^2\cdot x.$ In the ordered case, we get $$ \frac{1}{0!\,3!}1\cdot x^3+\frac{1}{1!\,2!}x\cdot x^2+\frac{1}{2!\,1!}x^2\cdot x=\frac{1}{3!}\left({}_3C_0\cdot 1\cdot x^3+{}_3C_1\cdot x\cdot x^2+{}_3C_2\cdot x^2\cdot x\right), $$ which is exactly what we want. We find that the number of words is $1+3+3=7.$ This is correct: BBB, ABB, BAB, BBA, AAB, ABA, BAA.

You should be able to generalize this idea to your problem.

Answer 2

Our desired $3$-tuples, will consist of $x$ M's, $y$ I's, $z$ S's and $w$ P's. These should be picked among the letters of the word MISSISSIPI and must sum to $3$: \begin{equation} x+y+z+w=3 \end{equation}

• $x$ -> # of M's, thus: $x=0,1$
• $y$ -> # of I's, thus: $y=0,1,2,3,4$ (note that $y=4$, is obviously excluded)
• $z$ -> # of S's, thus: $z=0,1,2,3,4$ (note that $z=4$, is obviously excluded)
• $w$ -> # of P's, thus: $w=0,1$

The possible solutions to the equation $$x+y+z+w=3$$ under the above restrictions on the values of $x,y,z,w$, are displayed in the following table: $$ \begin{array}{c|c|c|c} x & y & z & w \\ \hline 0 & 1 & 2 & 0 \\ 0 & 2 & 1 & 0 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & 3 & 0 \\ 1 & 2 & 0 & 0 \\ 1 & 0 & 2 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 2 & 0 & 1 \\ 0 & 0 & 2 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \end{array} $$ What remains to do, is to perform the following summation: $$\sum_{x+y+z+w=3}\frac{3!}{x!y!z!w!}$$ on the rows of the table above. Consequently we get: $$\frac{3!}{1!2!}+\frac{3!}{2!1!}+\frac{3!}{3!}+\frac{3!}{3!}+\frac{3!}{1!2!}+\frac{3!}{1!2!}+\frac{3!}{1!1!1!}+\frac{3!}{2!1!}+\frac{3!}{2!1!}+\frac{3!}{1!1!1!}+\frac{3!}{1!1!1!}+\frac{3!}{1!1!1!}= \\ =3+3+1+1+3+3+6+3+3+6+6+6=44$$

Answer 3

How many ways can a sequence of three letters be formed from the letters of the word MISSISSIPPI?

The word MISSISSIPPI contains one M, two P's, four I's, and four S's.

We consider cases:

Case 1: Three different letters are used.

We select three of the four letters, then arrange the three selected letters in order. $$\binom{4}{3} \cdot 3!$$

Case 2: Two different letters are used.

In this case, one letter fills two of the three positions. We choose one of the three letters that appears at least twice in the word MISSISSIPPI, then choose two of three positions for that letter. We then fill the remaining open position with one of the other three letters.
$$\binom{3}{1}\binom{3}{2}\binom{3}{1}$$

Case 3: One letter is used.

In this case, all three positions are filled by the same letter. We choose one of the two letters that appears at least three times in the word MISSISSIPPI to fill those three positions. $$\binom{2}{1}$$

Total: Since the three cases are mutually disjoint, the number of sequences of three letters that can be formed from the letters of the word MISSISSIPPI is $$\binom{4}{3} \cdot 3! + \binom{3}{1}\binom{3}{2}\binom{3}{1} + \binom{2}{1}$$