Unique Arrangements of n As and Bs in a Circle | Combinatorics Homework

[simpleton]

Homework Statement

You are given n identical As and n identical Bs. You are supposed to arrange them in a circle. How many unique arrangements are there?

Homework Equations

Use of combinatorics

The Attempt at a Solution

At first, I tried working out the answer if I arrange them in a row. The answer is (2*n)!/(n!*n!). Then I tried to multiply something to this to get the answer. However, I cannot find a way to do so. For example, I tried dividing it by 2*n, but this does not work, because not all the arrangements repeated 2*n times.

I worked out some answers below in case someone needs them.

for n = 1, there is only 1 way {AB}
for n = 2, there are 2 ways {AABB, ABAB}
for n = 3, there are 4 ways. {ABABAB, AABBAB, AABABB, AAABBB}
for n = 4, there are 9 ways if I did not count wrongly {AAAABBBB, AAABBBAB, AAABBABB, AAABABBB, AABAABBB, AABBAABB, AABABABB, AABABBAB, AABBABAB}

Sorry, my combinatorics is not that good. This is all I can do :(

 

[vela]

Homework Statement

You are given n identical As and n identical Bs. You are supposed to arrange them in a circle. How many unique arrangements are there?

Homework Equations

Use of combinatorics

The Attempt at a Solution

At first, I tried working out the answer if I arrange them in a row. The answer is (2*n)!/(n!*n!). Then I tried to multiply something to this to get the answer. However, I cannot find a way to do so. For example, I tried dividing it by 2*n, but this does not work, because not all the arrangements repeated 2*n times.

I worked out some answers below in case someone needs them.

for n = 1, there is only 1 way {AB}
for n = 2, there are 2 ways {AABB, ABAB}
for n = 3, there are 4 ways. {ABABAB, AABBAB, AABABB, AAABBB}
for n = 4, there are 9 ways if I did not count wrongly {AAAABBBB, AAABBBAB, AAABBABB, AAABABBB, AABAABBB, AABBAABB, AABABABB, AABABBAB, AABBABAB}

Sorry, my combinatorics is not that good. This is all I can do :(

You missed one in the n=4 case, namely ABABABAB.

You should be able to see a pattern between the results of your formula and the actual numbers for these four cases.

 

[simpleton]

Oh right, I missed that case

So let f(n) be the answer
f(1) = 1
f(2) = 2
f(3) = 4
f(4) = 10

Hmm, is the answer (2n)!/(n!*n!*(2*n-1))?

If that is the answer, can I know how to prove that?

Thanks.

 

[vela]

If you're dividing by 2n-1, that means each pattern repeats 2n-1 times. Why would each pattern repeat that many times?

 

[simpleton]

I have no idea actually :(. It just seems that it fits the pattern, so I thought that is the answer.

Sorry, I am not too sure how to do these kinds of combinatorics problems :S

 

[vela]

No need to be sorry. This problem is more complicated than I thought, too. The formula doesn't work for n=1. It seems the counting is complicated because the some of the n!n! permutations are the same as cyclic permutations. For example, from abAB, you can get ABab by swapping 1, 3 and 2, 4, or by shifting by 2.

 

[Count Iblis]

This is why Polya invented his theorem.

 

[Count Iblis]

Although with only A and B, the problem is rather simple as you can only have one type of pattern that maps onto itself under rotations.

 

[Count Iblis]

You can try this approach. You an try to account for all the (2n)!/n!^2 configurations when the A's and B's are arranged in a row, using the configurations on the circle in which two related by rotations are identified.

Most configurations on the circle give rise to 2n configurations when rotated in all possible ways. The exceptions are the periodic ABABABABABA.. ,AABBAABBAA, AAABBBAAABBB, etc. configuration. These configurations give rise to k row configurations, where k is the length of the period.

 

[Count Iblis]

And then note that finding the number of periodic configurations amounts to solving the same problem but now with 2n replaced by the period.

 

[Count Iblis]

So, this suggest an approach involving inclusion/exclusion or Möbius inversion.