How would I figure out how many anagrams of mississippi don't contain the word psi?

I'm really confused how I'd calculate this. I know it's the number of permutations of mississippi minus the number of permutations that contain psi, but considering there's repetitions of those letters, I'm not sure how I'd do it.

Solution 1:

The property of "containing a word as a substring" is pretty hard for me to model mathematically without counting it out. I wonder if there is a nicer solution.

Anyway: basic strategy: count permutations of MISSISSIPPI - permutations of the form PSIXXXXXXXX - permutations of the form XPSIXXXXXXX - ... - permutations of the form XXXXXXXXPSI + permutations with two copies of the word PSI (note that we need not worry about permutations with three copies of the word PSI as there are only two Ps in MISSISSIPPI).

Execution:

permutations of MISSISSIPPI = $\dfrac{11!}{4!4!2!}$

permutations of MISSISSIPPI starting with the word PSI = permutations of the remaining letters, which are MPSSSIII = $\dfrac{8!}{3!3!}$

we multiply this number by $9$ for the possible first positions of P.

Now we need to count the double-PSIs.

If there is a double-PSI, there are 21 possibilities for the location of the double-Ps $(1, 4)$ through $(1, 9)$, $(2, 5)$ through $(2, 9)$, ..., $(6, 9)$.

For each such possibility, the remaining letters are just permutations of MSSII of which there are $\dfrac{5!}{2!2!}$.

So the "final" answer, scare quotes because I've probably made a mistake, is

$$ \frac{11!}{4!4!2!} - 9\frac{8!}{3!3!} + 21\frac{5!}{2!2!} $$

Solution 2:

You start out from the permutations of the whole set of letters, and work through eliminating repetitions. Let's start, working slowly.

Your set is composed of the letters in the word: $S={M,I,S,S,I,S,S,I,P,P,I}$ This set has cardinality (element count): $|S|=11$

This set has $P_{11}=11!=39916800$ permutations.

Now, you have to remove repetitions caused by permutations of the same letter. Imagine the permutation: MIIIISSSSPP. You'll have permutations that will look the same when:

• You switch the two Ps
• You switch the four Ss between them
• You switch the four Is between them

How many of these will there be? It's a combinatorics sub problem. There are two Ps, four Ss and four Is, so you have $P_2=2!=2$ permutations for the Ps and $P_4=4!=24$ for the Is and again for the Ss. You have $2\times24\times24=1152$ permutations of equal letters, per pattern.

Note that these repetitions occur for every different pattern. You have $1152$ repetitions that result in MIIIISSSSPP, but you have another $1152$ that result in MIIIIPPSSSS. To remove the repetitions, you have to divide the $39916800$ obtained above by $1152$ instead of subtracting $1152$ from the $39916800$ (which is a common error for beginners).

So, by now, we know how many permutations without repetition there are of $S={M,I,S,S,I,S,S,I,P,P,I}$. There are $\frac{P_{11}}{P_2 \times P_4 \times P_4}=\frac{39916800}{1152}=34650$.

The last part is solving the sub problem of how many permutations of MISSISSIPPI contain PSI. This is quite simple. It's the same problem as above, but with this set $S={PSI,M,I,I,I,S,S,S,P}$. This set has cardinality 9, so has $P_9=9!$ permutations, from which we have to remove repetitions caused by swapping equal letters (three Is, three Ss). These repetitions are $P_3 \times P_3=3!\times3!=36$ per pattern, so just like before, we divide $\frac{P_9}{P_3 \times P_3}=10080$

Now, there's a bit of a snag. The permutations above will produce, for example, this pattern: PSIMIISSPSI. You'll notice that PSI appears twice. For each of these, there will be a repetition, when the first PSI is swapped with the last PSI. We have to remove these. How many are there? Again, the same method: $S={PSI,PSI,M,I,I,S,S}$ cardinality $|S|=7$ with repetitions caused by the two PSIs, the two Is and the two Ss. The number of permutations without repetition is $\frac{P_7}{P_2 \times P_2 \times P_2}=\frac{7!}{8}=630$.

The number of permutations of MISSISSIPPI that do contain PSI is $10080-630=9450$.

The final answer is the number of permutations without repetitions of MISSISSIPPI minus the number of permutations without repetition of PSI and the letters MIIISSSP, after removing the duplicates caused by two PSIs: $34650-(10080-630)=25200$.

Bar any calculation error, this is the answer.

Solution 3:

The simplest solution is very similar to user29743's. The trick to counting permutations containing a given number of copies of "PSI" is to treat each "PSI" as a single symbol. We want

(# of permutations of MISSISSIPPI) - (# of permutations of [PSI]SSSIIIMP) + (# of permutations of [PSI][PSI]SSIIM)

$$= {11\choose 4,4,2,1} - {9\choose 3,3,1,1,1} + {7\choose2,2,2,1} = 25200.$$