• Support PF! Buy your school textbooks, materials and every day products Here!

Combinatorics Problem

  • Thread starter simpleton
  • Start date
  • #1
58
0

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 :(
 

Answers and Replies

  • #2
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
14,619
1,253

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.
 
  • #3
58
0
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.
 
  • #4
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
14,619
1,253
If you're dividing by 2n-1, that means each pattern repeats 2n-1 times. Why would each pattern repeat that many times?
 
  • #5
58
0
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
 
  • #6
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
14,619
1,253
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.
 
  • #7
1,838
7
This is why Polya invented his theorem.
 
  • #8
1,838
7
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.
 
  • #9
1,838
7
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.
 
Last edited:
  • #10
1,838
7
And then note that finding the number of periodic configurations amounts to solving the same problem but now with 2n replaced by the period.
 
  • #11
1,838
7
So, this suggest an approach involving inclusion/exclusion or Möbius inversion.
 

Related Threads on Combinatorics Problem

  • Last Post
Replies
12
Views
811
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
10
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
4
Views
950
  • Last Post
Replies
2
Views
560
Top