8
$\begingroup$

I have a string ABCCEF and I want to find the number of permutations not counting the duplicates. I ran a piece of python code

   len(set([''.join(i) for i in itertools.permutations('ABCCEF')]))

and the output was 360. This piece of code determines all the permutations of ABCCEF (including the duplicates), creates a set of the permutations, then spits out the length of that set.

I am really rusty in the subject of combinatorics but through the magic guess and check, I BELIEVE that the value 360 is determined from

5*4*3*3*2*1 = 360

I determined this from the string have 6 values but only 5 unique values. So on the first slot I have 5 options to choose from, then 4, then 3. then 3 again (2 C's), then 2, then 1.

I dont really have a firm grasp of this concept. I was wondering if anyone could point out flaws in my logic and/or help me with a better process to solve this problem. Pretty much explain to me why I am correct...OR WRONG!

$\endgroup$
3
  • $\begingroup$ To see that your reasoning may be off, apply the same logic to ABBDEF. $\endgroup$ Jun 4, 2014 at 23:35
  • $\begingroup$ You have a typo saying there are 306 permutations $\endgroup$ Jun 4, 2014 at 23:39
  • 4
    $\begingroup$ ...and you left out 'import itertools'... $\endgroup$
    – copper.hat
    Jun 4, 2014 at 23:53

3 Answers 3

16
$\begingroup$

The correct answer is 360, although your reasoning is a little off. Think of it this way - imagine you're using the symbols $A,B,C_{1},C_{2},E,F$. There are $6! = 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720$ ways to arrange those. Then you can erase the subscripts from the C's to get the symbols $A,B,C,C,E,F$ in some order. But you'll have counted each one twice - $ABC_{1}C_{2}EF$ looks the same as $ABC_{2}C_{1}EF$ after you erase the subscripts. So you should divide by 2 to get 360.

In general, if you have $n$ total symbols, which are $k$ different symbols that each appear $a_{1},a_{2}, \ldots a_{k}$ times. respectively, the total number of arrangments of those is $$ \frac{n!}{a_{1}!a_{2}! \ldots a_{k}!}.$$ So, for example, the number of permutations of $A,A,A,B,B,C,C,C,C$ is $\frac{9!}{3!2!4!}$. $a_{1} =3, a_{2} = 2, a_{3} = 4$, and $n = 9$. That formula accounts for all the different ways to arrange the letters if you make the A's, B's, and C's distinct with subscripts (9!), and then compensates for the overcounting after you erase the subscripts (the terms on the bottom count the different ways of putting the A's, B's, and C's in order among themselves).

$\endgroup$
2
$\begingroup$

One way to do this is to do the number of permutations of $ABCDEF$, and then consider the effect of making the change $D \rightarrow C$.

There are $6!$ permutations of $ABCDEF$, i.e. $720$.

If we change all $D$'s to $C$'s then we have counted each permutation exactly twice: something that has $C...C$ could have either come from $C...D$, or $D...C$. So the answer is half of $720$.

This generalizes very easily too, e.g. if it were $ACCCCF$ then there are $4!$ entries in the list of $720$ which map to $ACCCCF$ -- one for each possible ordering of $B,C,D,E$ -- , so the answer is $6! / 4!$.

Since each letter is independent we can do the same thing for each duplicated latter, e.g. $ACCCCA$ has $\frac{6!}{4! 2!}$ permutations.

$\endgroup$
1
$\begingroup$

I agree that the number of ways to permute the multiset {A,B,C,C,E,F} is 360.

What is the number of ways to permute the set {A,B,C,D,E,F}?

720 right?

So change the D into a C in each of the 720 permutations of {A,B,C,D,E,F} and you will see that there are exactly twice as many as we are trying to count.

$\endgroup$

You must log in to answer this question.

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