Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Combinatorics Problem

  1. Mar 22, 2010 #1
    1. The problem statement, all variables and given/known data
    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?

    2. Relevant equations
    Use of combinatorics

    3. 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 :(
  2. jcsd
  3. Mar 22, 2010 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    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.
  4. Mar 23, 2010 #3
    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?

  5. Mar 23, 2010 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    If you're dividing by 2n-1, that means each pattern repeats 2n-1 times. Why would each pattern repeat that many times?
  6. Mar 24, 2010 #5
    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
  7. Mar 24, 2010 #6


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    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.
  8. Mar 24, 2010 #7
    This is why Polya invented his theorem.
  9. Mar 24, 2010 #8
    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.
  10. Mar 24, 2010 #9
    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: Mar 24, 2010
  11. Mar 24, 2010 #10
    And then note that finding the number of periodic configurations amounts to solving the same problem but now with 2n replaced by the period.
  12. Mar 24, 2010 #11
    So, this suggest an approach involving inclusion/exclusion or Möbius inversion.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook