Section 1.8. Counting 77 x1 x2 · · · xr+1 xr+2 · · · τ1 f1,1 f1,2 · · · f1,r+1 f1,r+2 · · · τ2 f2,1 f2,2 · · · f2,r+1 f2,r+2 · · · τi fi,1 fi,2 · · · fi,r+1 fi,r+2 · · · τn fn,1 fn,2 · · · fn,r+1 fn,r+2 · · · Figure 1.10. Burnside’s Lemma. Now Fix(τi), the number of x fixed by τi, is the number of 1’s in the ith row of the array therefore, τ∈G Fix(τ) is the total number of 1’s in the array. Let us now look at the columns. The number of 1’s in the first column is the number of τi that fix x1 by definition, these τi comprise Gx1 . Thus, the number of 1’s in column 1 is |Gx1 |. Similarly, the number of 1’s in column 2 is |Gx2 |. By Exercise 1.109 on page 76, |Gx1 | = |Gx2 |. By Theorem 1.107, the number of 1’s in the r columns labeled by the xi O(x1) is thus r|Gx1 | = |O(x1)| · |Gx1 | = (|G|/|Gx1 |) |Gx1 | = |G|. The same is true for any other orbit: its columns collectively contain exactly |G| 1’s. Therefore, if there are N orbits, there are N|G| 1’s in the array. We conclude that τ∈G Fix(τ) = N|G|. We are going to use Burnside’s Lemma to solve problems of the following sort. How many striped flags are there having six stripes (of equal width) each of which can be colored red, white, or blue? Clearly, the two flags in Figure 1.11 are the same: the bottom flag is just the top one rotated about its center. r w b r w b b w r b w r Figure 1.11. Striped flags. Let X be the set of all 6-tuples of colors if x X, then x = (c1,c2,c3,c4,c5,c6), where each ci denotes either red, white, or blue. Let τ be the permutation that reverses all the indices: τ = 1 2 3 4 5 6 6 5 4 3 2 1 = (1 6)(2 5)(3 4) (thus, τ “rotates” each 6-tuple x of colored stripes). The cyclic group G = τ acts on X since |G| = 2, the orbit of any 6-tuple x consists of either one or two elements: either τ fixes x or it does not. Since a flag is unchanged by rotation, it
Previous Page Next Page