Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

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 not 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.

share|improve this answer
    
Care to post an example? –  Sérgio Carvalho Feb 1 '13 at 14:41
    
I got it on my own. I'll correct the text. –  Sérgio Carvalho Feb 1 '13 at 14:48

This can be computed directly in GAP by the following code:

L:=["m","i","s","s","i","s","s","i","p","p","i"];;
S:=PermutationsList(L);;
n:=Size(L);;
T:=Filtered(S,M->not ForAny([1..n-2],i->M[i]="p" and M[i+1]="s" and M[i+2]="i"));;
Print(Size(T),"\n");

This returns 25200 anagrams of "mississippi" that don't contain "psi", confirming countinghaus' answer.

share|improve this answer

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

share|improve this answer
    
I believe that the second term should be $-9\cdot\dfrac{8!}{3!3!}$, with a factor of $9$, not $8$: PSI can start in positions $1$ through $9$. If my arithmetic is correct, it then comes to $25,200$. –  Brian M. Scott Jan 30 '13 at 21:01
    
With Brian's correction, your answer is OK. –  Byron Schmuland Jan 30 '13 at 21:14
    
thanks for checking up on it! agreed that it's 9 and not 8, changing the answer now. –  user29743 Jan 30 '13 at 23:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.