# Remove duplicates from a permutation

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?

-
You should note that you're using Python. :) – J. M. Aug 29 '10 at 0:07

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.

-