32
$\begingroup$

How many 6-letter permutations can be formed using only the letters of the word, MISSISSIPPI? I understand the trivial case where there are no repeating letters in the word (for arranging smaller words) but I stumble when this isn't satisfied. I'm wondering if there's a simpler way to computing all the possible permutations, as an alternative to manually calculating all the possible 6-letter combinations and summing the corresponding permutations of each. In addition, is there a method to generalize the result based on any P number of letters in a set with repeating letters, to calculate the number of n-letter permutations?

Sorry if this question (or similar) has been asked before, but if it has, please link me to the relevant page. I also apologize if the explanation is unclear, or if I've incorrectly used any terminology (I'm only a high-school student.) If so, please comment. :-)

$\endgroup$
4

2 Answers 2

36
$\begingroup$

I can think of a generating function type of approach. You have 1 M, 2 P's, 4 I's and 4 S's in the word MISSISSIPPI. Suppose you picked the two P's and four I's, the number of permutations would be $\frac{6!}{4! 2!}$. However, we need to sum over all possible selections of 6 letters from this group.

The answer will be the coefficient of $x^6$ in

\begin{equation} 6!\left(1 + \frac{x}{1!}\right)\left(1 + \frac{x}{1!} + \frac{x^2}{2!}\right)\left(1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!}\right)^2 \end{equation}

Each polynomial term corresponds to the ways in which you could make a selection of a given letter. So you have $1 + x$ for the letter M and $1 + x + x^2/2$ for the 2 letters P and so on.

The coefficient of $x^6$ comes out to 1610 in this case.

EDIT: (I'm elaborating a bit in response to George's comment).

This is a pretty standard approach to such counting problems. The value of $x$ is not relevant to the problem at all. The benefit of using such polynomials is that it gives you a nice tool to "mechanically" solve the problem. The idea is that by looking at the coefficient of a particular term in the expanded polynomial, you get the answer.

When I wrote a term (1+x) corresponding to the letter M, it captures two possibilities

1) I could either leave out M (which corresponds to the coefficient of x^0 which is 1)

2) I could include M, which corresponds to the coefficient of x^1 which is one.

Suppose you select 1M, 2I's 2P's and 1 S. This is encoded by the term $x^1\cdot x^2 \cdot x^2 \cdot x^1$. The first $x^1$ term corresponds to selecting the single M. The first $x^2$ term corresponds to selecting 2 I's (which are identical). Using similar logic, the next $x^2$ is for 2P's and the last $x^1$ is for 1S. Since you are interested in permutations with repetition, the number of permutations for this case will be $\frac{6!}{2!2!}$, which should be the coefficient of this term.

How would you encode 0 M, 3I's, 2P's and 1S? The term would then be $x^0 \cdot x^3 \cdot x^2 \cdot x^1$. However, this term would have to be multiplied by $\frac{6!}{3!2!}$ to keep the count correct. The $6!$ in the numerator will be common to all such terms. The denominator depends on your selection of letters.

You need to add all such possibilities. Instead of listing them all out, which will be laborious, you represent the possibility of choosing each letter by a polynomial. As an example, for 4 S's. you have $1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!}$. You divide $x^n$ by $n!$ to keep the count correct.

You then multiply the polynomials and look at the appropriate coefficient.

\begin{equation} 6!\left(1 + \frac{x}{1!}\right)\left(1 + \frac{x}{1!} + \frac{x^2}{2!}\right)\left(1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!}\right)^2 \end{equation}

You expand out this polynomial and look at the coefficient of $x^6$ which gives you the answer.

For more powerful uses of this kind of approach, please read the book at http://www.math.upenn.edu/~wilf/gfologyLinked2.pdf (Warning - it a big PDF file).

$\endgroup$
3
  • $\begingroup$ I'm a bit confused as to exactly what value x represents; why we are looking at the coefficients, and what you're referring to by "So you have 1+x for the letter M and 1+x+x^2/2 for the 2 letters P and so on." Can you please elaborate more? $\endgroup$ Feb 3, 2011 at 15:00
  • 2
    $\begingroup$ @George : x does not represent anything. You should read about the methods of counting based on generating functions, they are really powerful users.softlab.ntua.gr/~nidal/discrete/notes/examples/gen2.pdf courses.csail.mit.edu/6.042/fall05/ln11.pdf $\endgroup$
    – leonbloy
    Feb 3, 2011 at 17:32
  • $\begingroup$ Thanks for the extended explanation; after reading it through a few times I understand how it works, and it really is a rather efficient alternative to computing possibilities. @leonbloy: Thanks for the links to the pdfs! They presented many new ideas I hadn't encountered before. $\endgroup$ Feb 4, 2011 at 5:44
2
$\begingroup$

I'll add a "basic" approach to complement the excellent generating function solution given by @svenkatr above.

The difficulty attaches to the repeated letters; getting the number of 6-letter permutations from $ABCDEFGHIJK$ is simply the falling factorial $(11)_6 = 332640$. However taking $6$ letters from the multiset $\{M, I^4, S^4,P^2\}$ means the combinations are far fewer, since repeats are inevitable (there are only $4$ different letters) and may be quite high multiplicity.

For a given unordered repetition pattern in the chosen 6 letters, say $aaaabc$, we can fill this from the choice of letters based on which letters occur at a suitable multiplicity. For the example $aaaabc$, $a$ can be either $I$ or $S$ while then $b$ and $c$ are a free choice from the remaining letters, $\binom 32 = 3$ giving $6$ options to fill this pattern. Then the arrangements of this pattern are the multinomial $\binom {6}{4,1,1} = 30$.

So once we identify all patterns we can assess each in turn to get a total answer: $$\begin{array}{|c|c|} \hline \text{For this pattern:} & \text{options to fill} & \text{arrangements} & \text{total options} \\[1ex] \hline aaaabb & \binom 21 \binom 21 = 4 & \binom{6}{4,2} = 15 & 60 \\[1ex] aaaabc & \binom 21 \binom 32 = 6 & \binom{6}{4,1,1} = 30 & 180 \\[1ex] aaabbb & \binom 22 = 1 & \binom{6}{3,3} = 20 & 20 \\[1ex] aaabbc & \binom 21 \binom 21 \binom 21 = 8 & \binom{6}{3,2,1} = 60 & 480 \\[1ex] aaabcd & \binom 21 \cdot \binom 33 = 2 & \binom{6}{3,1,1,1} = 120 & 240 \\[1ex] aabbcc & \binom 33 = 1 & \binom{6}{2,2,2} = 90 & 90 \\[1ex] aabbcd & \binom 32\cdot \binom 22 = 3 & \binom{6}{2,2,1,1} = 180 & 540 \\[1ex] \hline \end{array}$$

summing to $\fbox{1610}$ overall options.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .