Formula for number of arrangements in a circle?

Now I have been thinking of your problem for more than five days, still I couldn't find a simple formula :(. I doubt there is, but there might be a simplified version of my solution. I have found an easier way to calculate the amount of different arrangements than using a computer. A single calculator will do it that can count (2*n-1)! .

You are interested in the number of distinct circular arrangements of n red and n blue (all together 2n) objects.

Step 1.

Make a list of all divisors of n, including 1 and n.

d1, d2, ..., ds (s divisors, d1 = n, ds = 1).

Step 2. (For better understanding. You can skip this step and continue with step 3.)

For every "d" factor on your list:

Preform prime factorization on n / d.

You will get a1(d), a2(d), ..., a(m-1)(d), am(d) prime numbers for every d (for d = n you will get 0 prime numbers), such that n / d = 1 * a1(d)^r1(d) * a2(d)^r2(d) * ... * am(d)^rm(d). (r ∊ N\{0}, but you can forget the r exponents we won't use them.)

Step 3.

For every "d" divisor on your list count the values of f(d) and g(d).

(m may differ from d to d.)

f(d) = 1 * (1 - 1/a1(d)) * (1 - 1/a2(d)) * ... * (1 - 1/am(d))

.....(and f(n) = 1)

g(d) = (2*d - 1)! / (d!)²

Note: g(d) will be the same for every n that is divisible by d. You can count it once and remember it's value later.

Step 4.

Number of different arrangements:

f(d1) * g(d1) + f(d2) * g(d2) + ... + f(ds) * g(ds)

Examples:

1, n = 6

factors:

6, 3, 2, 1

f(6) = 1;

f(3) = 1 - 1/2 = 1/2; (because 3 = 6 * 1/2)

f(2) = 1 - 1/3 = 2/3; (because 2 = 6 * 1/3)

f(1) = (1 - 1/2) * (1 - 1/3) = 1 / 3 (because 1 = 6 * 1/2 * 1/3)

g(6) = (2*6-1)! / 6!² = 11! / 6!² = 77

g(3) = 5! / 3!² = 10 / 3

g(2) = 3! / 2!² = 1,5

g(1) = 1! / 1!² = 1

Solution = 1 * 77 + 1/2 * 10/3 + 2/3 * 1,5 + 1 * 1/3 = 80

2, n = 12

factors:

12, 6, 4, 3, 2, 1

f(12) = 1; f(6) = 1/2; f(4) = 2/3; f(3) = 1 - 1/2 = 1/2; f(2) = 1/3; f(1) = (1-1/2)*(1-1/3) = 1/3

Note that even when we divided by 2 two times there is only one (1 - 1/2).

g(12) = 23! / 12!² = 112673,16666666

g(6) = 77 (from example 1.)

g(4) = 7! / 4!² = 8,75

g(3) = 10 / 3

g(2) = 1,5

g(1) = 1

Solution: 112673,16666666 + 1/2 * 77 + 2/3 * 8,75 + 1/2 * 10/3 + 1/3 * 1,5 + 1/3 = 112720

I am sure this formula is not correct.

You probably have tried an approach, similar to those for determining the number (n-1)! of all circular arrangements of n distinguishable objects - if we take a circular arrangement, we can break the chain in n possible places (between any two objects), thus obtaining n arrangements of n object in a row. This way every circular arrangement generates n distinct permutations, hence circular arrangements are n times less then linear arrangements. Since the latter are n!, the former are

n!/n = (n-1)!

This approach doesn't work for indistinguishable objects. You are right, there are

C[2n, n] = (2n)!/(n!)²

permutations (linear arrangements) of 2n objects (n indistinguishable of one kind, n of another), but distinct circular arrangements generate different number of linear arrangements - this depends on the symmetry type of the circular arrangement.

Take n = 2, we have C[4, 2] = 6 linear and 2 (up to rotation) circular arrangements (NESW):

1) RRBB, generating 4 linear: RRBB, RBBR, BBRR and BRRB

2) RBRB, generating 2 linear: RBRB and BRBR.

Cases n = 2, 3, 4 lead to 2, 4 and 10 arrangements (the formula yields correct results by pure coincidence), but what about n = 1 when there is a single circular arrangement?

Furthermore, when I checked the case n = 5, I got 26, not 28 circular arrangements - the following table shows the groups of adjacent chairs of the same color:

5+5 - 1 circular arrangement, generates 10 linear;

4+4+1+1 - 2 circular arrangements, generate 20 linear;

4+3+1+2 - 4 circular arrangements, generate 40 linear;

3+3+2+2 - 2 circular arrangements, generate 20 linear;

3+3+1+1+1+1 - 2 circular arrangements, generate 20 linear;

3+2+1+2+1+1 - 4 circular arrangements, generate 40 linear;

3+1+1+3+1+1 - 1 circular arrangement, generates 10 linear;

3+2+1+1+1+2 - 2 circular arrangements, generate 20 linear;

2+2+2+2+1+1 - 2 circular arrangements, generate 20 linear;

2+2+1+2+2+1 - 1 circular arrangement, generates 10 linear;

2+2+1+1+1+1+1+1 - 2 circular arrangements, generate 20 linear;

2+1+1+2+1+1+1+1 - 2 circular arrangements, generate 20 linear;

1+1+1+1+1+1+1+1+1+1 - 1 circular arrangement, generates 2 linear;

in general, 26 circular arrangements, generating 252 = C[10, 5] linear;

I'll check the case n = 6 later, please keep the question open, but for the time being I am very skeptical some simple formula for the required number exists, at least I haven't encountered in some books on combinatorics I have read. Possibly the subject is related to some restricted partitions of integers (follow the link in Sources below for details), symmetry considerations may also be important.

P.S. 80 is correct answer for n = 6, read the comments about the number of necklaces and the formula on the following page:

http://www.research.att.com/~njas/sequences/A00323...

P.S.(2) A note to MathMan TG: Hello, MathMan, I followed the links, read Your profile and all Your answers to similar questions, totally agree with Your recommendations and results. The different arrangements never have 2n-1 "cousins", so division by 2n - 1 works only accidentally.

Let us take again the case n = 4, C[8, 4] = 70 linear and 10 circular arrangements, 70/7 = 10 indeed, but the correct enumeration goes like this: 8 circular arrangements generate 8 linear each, one (RRBBRRBB) generates 4 and one (RBRBRBRB) generates 2, or 8*8 + 1*4 + 1*2 = 70

Since the necessary formula (neither very simple, nor that complicated) is on the O.E.I.S. page (link above), we can consider the issue resolved. As to this:

http://answers.yahoo.com/question/index?qid=200912...

it is a perfect example (has happened several times to me too) of the imperfection of Y!A voting system - can we vote for an incorrect or even idiotic answer as Best Answer? Yes, we can! VOX POPULI, VOX DEI!

If all of the different arrangements have 2n-1 "cousins" (i.e. rotations which show up in the list),

then dividing by 2n - 1 works. But that's not always the case.

The arrangement where the n red chairs are all together has n "cousins".

The arrangement where the colors alternate always rotates to itself, so it only shows up once.

(See my other answers linked below for details.)

There is a theorem (or lemma) of Burnside which addresses this with equivalence classes.

http://en.wikipedia.org/wiki/Burnside%27s_lemma

The idea is that depending on the symmetry, various permutations have different numbers of

symmetric arrangements which are the same.

Which is nice theory, but not so much in practice sometimes.

The answer for the n = 6 case is indeed 80 (I generated and counted them).

See my answer here:

http://answers.yahoo.com/question/index?qid=200912...

(you might get a chuckle out of what was selected as Best Answer)

And for n = 4, see this question, where I enumerate the equivalences for that case:

http://answers.yahoo.com/question/index?qid=201001...

For n = 7, my program finds 246 arrangements.

(EDIT: earlier comments about sequences in O E I S removed, since 28 is wrong, replaced by 26.

My number of 246 is thus confirmed.)

Since 7 is prime, all the circular arrangements have 7 "cousins", except the alternating one, which has 1.

For n = 6, you have to deal with arrangements where rotating by 2 or 3 steps produces another arrangement.

If anyone wants my data, send me a message.

NOTE to Duke:

Thanks for your reply to my comments and answers to this and related questions. We are in agreement on all the issues I think.

To the asker: since there is no way to share Best Answer, go ahead and choose Duke's answer. I'm quite happy with "First Runner Up" in this instance.

((((((((((((((((((( *************THE ANSWER IS NOT 2! IT IS 3! or rather 3*2*1 = 6 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! it is harder to exsplain with out paper but will call them A B C so 1 ABC 2 ACB now that is all of the combos with A as the first spot lets see if we can find a Pattern 3 BAC (dont be confused kiddies that is not Blood Alcohol content) 4 BCA Noe that is all the combos with B as the first spot 5 CAB 6 CBA Now we are done since if you do every combo with every person or thing in the first spot you know that they have all been accounted for...... also you should try to rember or how to come up with the logic the 3 things will have the posibble combos of so here it woud be (3)(2)=6 RATHER (3)(2)(1) see of you add a nother "persom" then each group of COMBOS GET ADDED TO THE FIRST GROUPS POSSINILITIES AND THEN WELL SEE IF YO UCAN RATIONALIZE IT OUT think boxes 5*4*3*2*1 would be the answer for 5 things there is a button on your caculator that will do this easily it is maked with a ! so the answer is 3! or 3*2*1 HOPE THAT HELPS