Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/