78 Chapter 1. Groups I is reasonable to identify a flag with an orbit of a 6-tuple. For example, the orbit consisting of the 6-tuples (r, w, b, r, w, b) and (b, w, r, b, w, r) describes the flag in Figure 1.11. The number of flags is thus the number N of orbits by Burnside’s Lemma, N = 1 2 [Fix((1)) + Fix(τ)]. The identity permutation (1) fixes every x X, and so Fix((1)) = 36 (there are three colors). Now τ fixes a 6-tuple x if it is a “palindrome,” that is, if the colors in x read the same forward as backward. For example, x = (r, r, w, w, r, r) is fixed by τ. Conversely, if x = (c1,c2,c3,c4,c5,c6) is fixed by τ = (1 6)(2 5)(3 4), then c1 = c6, c2 = c5, and c3 = c4 that is, x is a palindrome. It follows that Fix(τ) = 33, for there are three choices for each of c1, c2, and c3. The number of flags is thus N = 1 2 (36 + 33) = 378. Let us make the notion of coloring more precise. Definition. If a group G acts on X = {1,...,n}, and C is a set of q colors, then G acts on the set Cn of all n-tuples of colors by τ(c1,...,cn) = (cτ1,...,cτn) for all τ G. An orbit of (c1,...,cn) Cn is called a (q, G)-coloring of X. Color each square in a 4 × 4 grid red or black (adjacent squares may have the same color indeed, one possibility is that all the squares have the same color). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 13 9 5 1 14 10 6 2 15 11 7 3 16 12 8 4 Figure 1.12. Chessboard and a rotation. If X consists of the 16 squares in the grid, and C consists of the two colors red and black, then the cyclic group G = R of order 4 acts on X, where R is clockwise rotation by 90◦ Figure 1.12 shows how R acts: the right square is R’s
Previous Page Next Page