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 unique strings can be formed by the letters in "aaamottu"?

As a totally incompetent math student, I simply wrote a program to calculate it. And I ended up with 3360 unique strings:

import itertools
unique = {}
for p in itertools.permutations(list("aaamottu"), 8):
    unique[p] = True

len(unique)

I'd like to know how to get that number using plain ol' math.

nPr(8,8) gives 40,320. Obviously, lots of duplicates are being counted. How to I remove them?

share|improve this question
    
You should note that you're using Python. :) –  J. M. Aug 29 '10 at 0:07
add comment

1 Answer

up vote 3 down vote accepted

First pretend that the letters which are the same are different, then stop pretending. Let us suppose that the string is $a_1 a_2 a_3 m o t_1 t_2 u$; then there really would be $8! = 40320$ different words we could form. The key insight is that we can group these words according to how they use the $a$s and the $t$s; for example, we can group together the words

$$a_1 a_2 a_3 m o t_1 t_2 u, a_1 a_2 a_3 m o t_2 t_1 u$$

because the words are the same except for the order of the $t$s. Since it is true that any word has a "brother" where the order of the $t$s is reversed, to account for the fact that we labeled the $t$s we have to divide by $2! = 2$.

Next we can group together according to how the $a$s are used; for example, we can group together the words

$$a_1 a_2 a_3 m o t_2 t_1, a_1 a_3 a_2 m o t_2 t_1, a_2 a_1 a_3 m o t_2 t_1, a_2 a_3 a_1 m o t_2 t_1, a_3 a_1 a_2 m o t_2 t_1, a_3 a_2 a_1 m o t_2 t_1$$

because the words are the same except for the order of the $a$s. Since it is true that any word has five "partners" where the order of the $a$s are different, to account for the fact that we labeled the $a$s we have to divide by $3! = 6$.

So the answer is $\frac{8!}{3! 2!} = \frac{40320}{12} = 3360$ as desired. This function is an example of a multinomial coefficient.

share|improve this answer
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.