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.

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. :-)

share|improve this question
    
Not [number theory] at –  Arturo Magidin Feb 3 '11 at 14:39
add comment

1 Answer 1

up vote 9 down vote accepted

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

share|improve this answer
    
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? –  George Zhai Feb 3 '11 at 15:00
2  
@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 –  leonbloy Feb 3 '11 at 17:32
    
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. –  George Zhai Feb 4 '11 at 5:44
add comment

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.