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

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2010 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.