Four Colors, Eighths of a Circle

Date: 10/15/2001 at 17:03:05
From: Steve
Subject: Circular combinations

Take a circle, divide into eighths. You may use 4 colors to color the 
segments. Colors may be repeated as long as you use all 4 colors at 
least once. What are the total combinations possible?

Date: 10/16/2001 at 06:43:29
From: Doctor Anthony
Subject: Re: Circular combinations

You could model this as making a necklace with 8 beads of 4 different 
colours. And the necklace can be viewed from either side so that 
reflective symmetries must be considered.

We make use of Burnside's lemma in answering this question. Namely, 
the number of distinct configurations is the sum of the group actions 
(acting on the symmetries of an octagon) that keep colours fixed, 
divided by the order of the group (16 in this case).

We first require the cycle index for an octagon. This is obtained by 
simply counting the rotational and reflective symmetries in terms of 
cyclical permutations of the vertices (1) to (8)

We have:

(1)(2)(3)(4)(5)(6)(7)(8)   =  (x1)^8
(12345678)                 =  (x8)
(18765432)                 =  (x8) 
(1357)(2468)               =  (x4)^2     Rotations
(1753)(2864)               =  (x4)^2
(14725836)                 =  (x8)
(16385274)                 =  (x8) 
(15)(26)(37)(48)           =  (x2)^4
------------------------------------------
(1)(5)(28)(37)(46)         =  (x1)^2.(x2)^3    (4 like this)
(12)(38)(47)(56)           =  (x2)^4           (4 like this)


The cycle index for an octagon is

P(G)(x1,x2,..,x8) =(1/16)[x1^8 +4(x8) + 5x2^4 + 2x4^2 + 4x1^2.x2^3]

and in this example to get the unrestricted number of configurations 
we replace each of the xi by 4 (the number of colours available).  
This will give the total number including those with only 1, 2, or 3 
colours. We shall have to expand the expression to get the number with 
each colour appearing at least once.

    = (1/16)[4^8 + 4(4) + 5(4^4) + 2(4^2) + 4(4^2)(4^3)]

    = 70960/16

    =  4435  (unrestricted configurations)

If the colours are a, b, c, d then we get

P(G) = (1/16)[(a+b+c+d)^8 + 4(a^8+b^8+c^8+d^8) + 5(a^2+b^2+c^2+d^2)^4
            + 2(a^4+b^4+c^4+d^4)^2 + 4(a+b+c+d)^2.(a^2+b^2+c^2+d^2)^3]

and we must pick out terms in which all four letters appear.

    = (1/16)[40824 + 120 + 960]  =  (1/16)(41904)

    = 2619

So there are 2619 non-equivalent configurations in which each colour 
appears at least once.

An alternative method to finding the configurations with at least one 
of each colour is to use the inclusion-exclusion principle as follows:

 4-colour = (1/16)[4^8 + 4(4) + 5(4^4) + 2(4^2)(4^3)] =  4435
-3-colour = (1/16)[3^8 + 4(3) + 5(3^4) + 2(3^2)(3^3)] = -1992
+2-colour = (1/16)[2^8 + 4(2) + 5(2^4) + 2(2^2)(2^3)] = + 180
-1-colour = (1/16)[1^8 + 4(1) + 5(1^4) + 2(1^2)(1^3)] = -   4
                                                     ----------
                                                         2619

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/