# How many $3$-character strings can be formed using the letters of word MISSISSIPPI? [duplicate]

Only the letters that repeat in the original word can be repeated. I've tried $$\frac{11!}{4!4!2!}$$ and the for n = then result of the previous permutation I did $$\binom{n}{3}$$. Just feels like there are way more values than necessary.

• Does the order of the characters in the 3 character strings matter ? Jan 21 at 8:23
• @trueblueanil yes. Jan 21 at 8:27
• Have you studied exponential generating functions ? Jan 21 at 8:54
• @trueblueanil nope. Jan 21 at 9:01

Hint

Since you don't know exponential g.f's, an easy mechanical alternative is outlined below:

There are $$4 S's, 4 I's, 2 P's \;and\; 1 M$$

Form $$4$$ digit numbers from largest to smallest, (from the characters available), each row summing to $$3$$, eg

$$3000\;2100\;2010\;2001\;1200\;1110 ...\;$$ and add their permutations, viz

$$3!(\frac 1{3!} +\frac1{2!1!} +\frac 1{2!1!} + \frac1{2!1!}+\frac1{1!2!}+\frac1{1!1!1!}...)$$

Rather than coming up with a single expression, it is easier to enumerate different possibilities. We can start with M: either there is one, or there isn't.

If there is no M, the three characters can be any combination of I, S and P, with just one exception: it can't be PPP. So there are $$3^3 - 1 = 26$$ possibilities.

If there is a M, then there are three possibilities for its position. The other two characters can be any combination of I, S and P. So there are $$3 \times 3^2 = 27$$ possibilities.

Conclusion: in total there are $$26 + 27 = 53$$ possibilities.

The first letter can be any of 4 possibilities (I, M, P, or S).

The second letter can also be any of those four except that MM is not a valid combination (as MISSISSIPPI has only one M). So there are $$4 \times 4-1=15$$ valid permutations for the first two letters.

Having the same 4 options for the third letter brings us up to $$15 \times 4 = 60$$ permutations, but we must exclude PPP (since we're limited to two P's), and six permutations that already have an M in the first two letters (IMM, MIM, MPM, MSM, PMM, and SMM).

This leaves us with 53 valid permutations: III, IIM, IIP, IIS, IMI, IMP, IMS, IPI, IPM, IPP, IPS, ISI, ISM, ISP, ISS, MII, MIP, MIS, MPI, MPP, MPS, MSI, MSP, MSS, PII, PIM, PIP, PIS, PMI, PMP, PMS, PPI, PPM, PPS, PSI, PSM, PSP, PSS, SII, SIM, SIP, SIS, SMI, SMP, SMS, SPI, SPM, SPP, SPS, SSI, SSM, SSP, and SSS.

Answer: We see that there is 1 M, 4 I's, 4 S's, and 2P's in MISSISSIPPI.

As we want 3 letters, we, technically, have 1 M, 3 I's, 3 S's and 2P's now.

We have MIS, MIP, MSP, MSI, MPI, MPS, MII, MSS, MPP - 9 for M

IMS,ISM,IMP,IPM,ISP,IPS,ISS,IPP,IIM,IIS,IIP,III,IMI,IPI,ISI - 15 for I, and 15 again for S.

PMI,PIM,PMS,PMP,PIP,PSP,PSM,PIS,PSI,PII,PSS,PPM,PPI,PPS - 14.

Therefore, our answer will be $$9+15+15+14=53$$.

• You missed some combinations: IMI, IPI, ISI, PMP, PIP, PSP. Jan 21 at 17:12
• And how do you know that you aren't missing any others, in addition to what Aetol pointed out? Jan 21 at 17:13