Section 1.8. Counting 79 action on the left square. In cycle notation, R = (1, 4, 16, 13)(2, 8, 15, 9)(3, 12, 14, 5)(6, 7, 11, 10), R2 = (1, 16)(4, 13)(2, 15)(8, 9)(3, 14)(12, 5)(6, 11)(7, 10), R3 = (1, 13, 16, 4)(2, 9, 15, 8)(3, 5, 14, 12)(6, 10, 11, 7). A red and black chessboard does not change when it is rotated it is merely viewed from a different position. Thus, we may regard a chessboard as a 2-coloring of X the orbit of a 16-tuple corresponds to the four ways of viewing the board. By Burnside’s Lemma, the number of chessboards is 1 4 Fix((1)) + Fix(R) + Fix(R2) + Fix(R3) . Now Fix((1)) = 216, for every 16-tuple is fixed by the identity. To compute Fix(R), note that squares 1, 4, 16, 13 must all have the same color in a 16-tuple fixed by R. Similarly, squares 2, 8, 15, 9 must have the same color, squares 3, 12, 14, 5 must have the same color, and squares 6, 7, 11, 10 must have the same color. We conclude that Fix(R) = 24 note that the exponent 4 is the number of cycles in the complete factorization of R. A similar analysis shows that Fix(R2) = 28, for the complete factorization of R2 has 8 cycles, and Fix(R3) = 24, because the cycle structure of R3 is the same as that of R. Therefore, the number N of chessboards is N = 1 4 216 + 24 + 28 + 24 = 16,456. We now show, as in the discussion of the 4 × 4 chessboard, that the cycle structure of a permutation τ allows one to calculate Fix(τ). Lemma 1.125. Let C be a set of q colors, and let G be a subgroup of Sn. If τ G, then Fix(τ) = qt(τ), where t(τ) is the number of cycles in the complete factorization of τ. Proof. Since τ(c1,...,cn) = (cτ1,...,cτn) = (c1,...,cn), we see that cτi = ci for all i, and so τi has the same color as i. It follows, for all k, that τ ki has the same color as i, that is, all points in the orbit of i acted on by τ have the same color. If the complete factorization of τ is τ = β1 · · · βt(τ), and i occurs in βj, then Example 1.101 shows that the orbit containing i is the set of symbols occurring in βj. Thus, for an n-tuple to be fixed by τ, all the symbols involved in each of the t(τ) cycles must have the same color as there are q colors, there are thus qt(τ) n-tuples fixed by τ. Theorem 1.126. Let G act on a finite set X. If N is the number of (q, G)-colorings of X, then N = 1 |G| τ∈G qt(τ), where t(τ) is the number of cycles in the complete factorization of τ. Proof. Rewrite Burnside’s Lemma using Lemma 1.125.
Previous Page Next Page