Four Colors, Eighths of a CircleDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/