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

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.

• The idea that I have is to first consider the number of $3$-combinations of MISSISSIPPI, and then multiply the resulting number by $3!$ to order the combs. However, this would use the inclusion-exclusion principle extensively and is tedious. Oct 6, 2014 at 0:45
• You can also split it into specific cases, which would probably be easier. Consider the $3$-perms of MII, MSS, MPP, MIS, MIP, SSS, III, PPS, PSS, etc. (Not sure if I got them all.) Then you can use the formula $$\frac{n!}{n_1 ! n_2 ! \cdots n_k !}$$ where $\sum_{k \le n} n_k = n$, for each specific case. Oct 6, 2014 at 0:49
• From the way the question is worded I would say $11 \choose 3$ = $165$ Aug 28, 2016 at 14:55

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.

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$: $$x+y+z+w=3$$

• $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$$

• Welcome to Math StackExchange! Great first post!
– JnxF
Jan 30, 2016 at 17:06
• Thanks JnxF ! It is an amazing community! happy to be here, among you. Jan 30, 2016 at 19:24
• there is a spelling mistake in my solution above: I have spelled MISSISSIPI instead of the correct MISSISSIPPI. But i hope the method is clear (even with a single P !) Jan 30, 2016 at 20:33
• Adding the additional P introduces three more cases: $(1, 0, 0, 2)$, $(0, 1, 0, 2)$, $(0, 0, 1, 2)$, each of which has the form $\frac{3!}{1!2!}$, which yields the correct answer of $53$. Apr 17, 2016 at 9:09

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