Difficult combinatorics question?

I started with fixing the location of one spot and getting 8C2 X 6C3 = 28 x 20 = 560, but that's overly simplistic. It works if the items are different but distinguishable, like boys and girls, or numbered colored chairs. In your problem, 560 is too many since some of those can be rotated into another, as the links you provided indicates.

I wrote a program to list all 560 permutations that begin with a red chair, and then to find how many are equivalent.

To explain the results, look at it this way. We start with a red chair at a given position, and then rotate all the chairs so that the other red chairs assume that position. There are only 2 arrangements of the 560 where the rotation gives you exactly the same arrangement: RGBRGBRBG and RBGRBGRBG. That's as expected, since those are the only ones where all 3 of the colors have rotational symmetry. Rotating any R chair to any other R chair also rotates any G or B chair to a spot occupied by another G or B chair.

That leaves 560 - 2 = 558 other permutations. Each of those do NOT have complete rotational symmetry. Every 3rd chair may be R, or G, or B, or two of them may be, but not all three. [Strike "or two of them." If two sets are symmetric, the 3rd must be. Thanks for pointing that out.] What that gives you is that each any of the 558 permutations is the same as exactly 2 others. They are different permutation of the colors, so they show up separately in the list of 560. So there are 558/3 = 186 fundamentally different arrangements without the symmetry of the first 2. So add the other 2 to get the answer, 2+186 = 188.

560 = 2 + 558 is the sum of the sequences

186 = 2(1) + 558/3 gives you the number of non-equivalent sequences.

This is a great question. I was thinking that there were only the two arrangements that weren't equivalent to some others, but actually seeing and counting them convinced me that this approach would lead to the right answer.

I'd have to think about a general approach to this, but if you have p chairs of p colors, where p is prime, I think you only have (p-1)! arrangements that have the needed symmetry, and rotating by 360/p gives you the same arrangement. Each other arrangement I think will have p equivalent permutations.

If you have n chairs of n colors, where n is composite, then you have other symmetric arrangements. If n = 4, rotating through 90 may give you the same, but for some others, rotating 90 won't, but rotating 180 will. So you have to examine n and its factors carefully to see what you will get. The more factors and powers in n, the more possibilities there are, so it can get very complicated.

Perhaps this is a bit late now but I have been on holiday and as it happens this is exactly the kind of problem I have been reading about whilst away. So here you go:

This is a necklace problem under cyclic group C_9.

For a necklace of 9 beads under C_9 there are 4 types of permutation:

(1)(2)(3)(4)(5)(6)(7)(8)(9) 0° rotation [type z(1)^9]

(123456789) +40° rotation [type z(9)^1]

(198765432) -40° rotation [type z(9)^1]

(135792468) + 80° rotation [type z(9)^1]

(186429753) - 80° rotation [type z(9)^1]

(147)(258)(369) +120° rotation [type z(3)^3]

(174)(963)(852) -120° rotation [type z(3)^3]

(159483726) +160° rotation [type z(9)^1]

(162738495) -160° rotation [type z(9)^1]

These are rotations of counterclockwise labelled beads 1-9 given in cycle notation, the types have the notation:

z(# of beads in permutation)^(cycles with this # of beads)

The "cycle index" P_G(z(1),z(2),z(3)) of a 9 bead necklace is therefore given via Burnside's Lemma:

P_G(z(1),z(3),z(9)) = (1/9)*(1*z(1)^9 + 2*z(3)^3 + 6*z(9)^1)

For 3 colours: red, blue and green (r,b,g) Polya's pattern theorem replaces:

z(1) with r^1 + b^1 + g^1

z(3) with r^3 + b^3 + g^3

z(9) with r^9 + b^9 + g^9

giving a pattern inventory generating function:

P_G = (1/9)*(1*(r^1 + b^1 + g^1)^9 + 2*(r^3 + b^3 + g^3)^3 + 6*(r^9 + b^9 + g^9)^1)

The number of necklaces with 3 red, 3 blue and 3 green beads is then the coefficient of the r^3*b^3*g^3 term in P_G.

We can see that the first brackets contributes a term 1*(9!/(3!3!3!))*r^3*b^3*g^3 and that the second contributes 2*(3!/(1!1!1!))r^3*b^3*g^3. The last brackets contributes nothing as all r, b, g indeterminates are raised to the power of 9.

Hence the appropriate coefficient of our generating function is:

[r^3*b^3*g^3]P_G = (1/9)*( 1*(9!/(3!3!3!) + 2*(3!/(1!1!1!)) ) = (1/9)*(1680 + 12) = 1692/9 = 188 <----

https://en.m.wikipedia.org/wiki/Burnside%27s_lemma

https://en.m.wikipedia.org/wiki/P%C3%B3lya_enumera...