Arranging the letters $I,I,I,I,M,P,P,S,S,S,S$, what is the rank of the word MISSISSIPPI?

Question

All words that contain the letters $I,I,I,I,M,P,P,S,S,S,S$ are listed alphabetically so that the first two letters must be distinct, (i.e. the first word in the list is IMIIIPPSSSS, the second word in the list is IMIIIPSPSSS, ..., and the last word in the list is SPSSSPMIIII).

What is the rank of the word MISSISSIPPI?

I know the total number of words that can be formed uning those letters, $=\frac{11!}{4! \cdot 2! \cdot 4!}=34650$ words.

I do not know how to exclude the bad words that have non-distinct first two letters, and how to find the rank of any word I want.

Any help would be appreciated. THANKS!

Answer 1

The letter $M$ must be in front, so we have to discard all possibilities starting with an $I$. How many are there? Well, fixing the first letter, we can either have $M$, $P$ or $S$ for the second letter. Then, the remaining letters can be divided using multinomial coefficients. The number of valid combinations starting with an $I$ thus equals:

$${9 \choose 3, 2, 4} + {9 \choose 3, 1, 1, 4} + {9 \choose 3, 1, 2, 3} = 1260 +2520 + 5040 = 8820$$

Then, we can fix $MI$ since $I$ is the lowest letter. How many words start start with $MII$? We find:

$${8 \choose 2, 2, 4} = 420$$

How many start with $MIP$? We find:

$${8 \choose 3, 1, 4} = 280$$

Now we can move on to $MISI$ and $MISP$, with ${7 \choose 2, 2, 3} = 210$ and ${7 \choose 3, 1, 3} = 140$ combinations, respectively. Using the same approach for the remaining combinations starting with $MISSI$, we eventually find:

$$8820 + 420 + 280 + 210 + 140 + 30 + 30 + 12 +12 + 3 = 9957$$

This can be confirmed using the following Python code:

from itertools import permutations

d = {}
rank = 0
for p in permutations("MISSISSIPPI"):
  if p not in d and p[0] != p[1]:
    d[p] = 1
    if "".join(p) <= "MISSISSIPPI":
      rank += 1
print(rank)