Online Course Discussion Forum
Counting Question
How would we do problems like arranging multiple non distinct items on a circle where rotations do not matter?
for example: the letters A,A,A,B,B on a circle
If the problem was to arrange some number of A's on a circle, the answer would be only 1 way, but if we add B's into the problem we could try to arrange all A's and B's in a line and then account for rotations --> (5! / (2!3!)) / 5
another way that gets the same answer is to arrange the 5 items on a circle first assuming they are distinct (5!/5) and then dividing by 3!2! to account for the switching around of A's and B's
--> (5!/5) / 2!3!
is this correct?
thanks
Unfortunately this problem is actually quite a bit harder than it may seem on the surface. There are some nice ways of coming up with answers, but they involve (much) harder techniques that I would not worry about for now.
Your answer in the case with $3$ A's and $2$ B's is numerically correct. The answer is $2$, the circular versions of $AAABB$ and $AABAB$.
Now consider the case of $3$ A's and $3$ B's. Following the rational in your problem you might have an answer of $$\frac{6!}{3!\cdot 3!}\div 6 = \frac{6!}{6} \div (3!\cdot 3!) = \frac{6!}{6\cdot 3!\cdot 3!}.$$ Unfortunately this simplifies to $\dfrac{10}{3}$ which cannot be correct!
There are actually $4$ outcomes, the circular versions of $AAABBB$, $AABABB$, $ABAABB$, and $ABABAB$. The difficulty comes because we have identical objects. For example, in the $ABABAB$ outcome here, the $6$ rotations are not all different, there are only $2$ different ones.
In general it is easiest to break this type of question down into cases based on the "separation" of the letters. For example, in the $3$ A's and $3$ B's case we consider (i) two groups of 3, (ii) two groups of 2, two groups of 1, and (iii) alternating and work it out from there.
If you're curious (do not try to understand this page!) at what a general "solution" looks like, you can see the discussion on mathoverflow here: https://mathoverflow.net/questions/86709/circular-permutations-with-identical-objects
Social networks