80 Chapter 1. Groups I There is a generalization of this technique, due to olya (Biggs, Discrete Math- ematics, p. 403), giving formulas of the sort that count the number of red, white, blue, and green flags having 20 stripes exactly 7 of which are red and 5 of which are blue. Exercises 1.110. How many flags are there with n stripes of equal width, each of which can be colored any one of q given colors? Hint. The parity of n is relevant. 1.111. Let X be the squares in an n × n grid, and let ρ be a rotation by 90o. Define a chessboard to be a (q, G)-coloring, where the cyclic group G = ρ of order 4 is acting on X. Show that the number of chessboards is 1 4 qn2 + q (n2+1)/2 + 2q (n2+3)/4 , where x is the greatest integer in the number x. 1.112. Let X be a disk divided into n congruent circular sectors, and let ρ be a rotation by (360/n)o. Define a roulette wheel to be a (q, G)-coloring, where the cyclic group G = ρ of order n is acting on X. Prove that if n = 6, then there are 1 6 (2q +2q2 +q3 +q6) roulette wheels having 6 sectors. (The formula for the number of roulette wheels with n sectors is 1 n d|n φ(n/d)qd, where φ is the Euler φ-function.) 1.113. Let X be the vertices of a regular n-gon, and let the dihedral group G = D2n act on X [as the usual group of symmetries (Examples 1.30 and 1.31)]. Define a bracelet to be a (q, G)-coloring of a regular n-gon, and call each of its vertices a bead. (Not only can we rotate a bracelet, we can also flip it: that is, turn it upside down by rotating it in space about a line joining two beads.) (i) How many bracelets are there having 5 beads, each of which can be colored any one of q available colors? Hint. The group G = D10 is acting. Use Example 1.31 to assign to each symmetry a permutation of the vertices, and then show that the number of bracelets is 1 10 ( q5 + 4q + 5q3 ) . (ii) How many bracelets are there having 6 beads, each of which can be colored any one of q available colors? Hint. The group G = D12 is acting. Assign a permutation of the vertices to each symmetry, and then show that the number of bracelets is 1 12 ( q6 + 2q4 + 4q3 + 3q2 + 2q ) .
Previous Page Next Page