Associated Topics || Dr. Math Home || Search Dr. Math

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/
```
Associated Topics:
College Discrete Math
High School Discrete Mathematics
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search