5.2. Group Actions—Counting Orbits

i

“bookmt” — 2006/8/8 — 12:58 — page 244 — #256

i

i

244

5. ACTIONS OF GROUPS

5.1.19. Give the details of the proof of Example 5.1.20. In particular, define an action of Sn on the set of ordered sequences of k-elements from f1; 2; : : : ; ng, and verify that it is indeed an action. Show that the action is transitive. Calculate the size of the stabilizer of a particular k-element sequence.

5.1.20. Show that the transitive subgroups of S4 are

 S4  A4, which is normal  D4 D h.1 2 3 4/; .1 2/.3 4/i, and two conjugate subgroups  V D fe; .12/.34/; .13/.24/; .14/.23/g, which is normal  Z4 D h.1 2 3 4/; .1 2/.3 4/i, and two conjugate subgroups 5.2. Group Actions—Counting Orbits

How many different necklaces can we make from four red beads, three white beads and two yellow beads? Two arrangements of beads on a circular wire must be counted as the same necklace if one can be obtained from the other by sliding the beads around the wire or turning the wire over. So what we actually need to count is orbits of the action of the dihedral group D9 (symmetries of the nonagon) on the

9Š

4Š3Š2Š

arrangements of the beads.

Let’s consider a simpler example that we can work out by inspection:

Example 5.2.1. Consider necklaces made of two blue and two white beads.

There are six arrangements of the beads at the vertices of the square, but only two orbits under the action of the dihedral group D4, namely, that with two blue beads adjacent and that with the two blue beads at opposite corners. One orbit contains four arrangements and the other two arrangements.

We see from this example that the orbits will have different sizes, so we cannot expect the answer to the problem simply to be some divisor of the number of arrangements of beads.

In order to count orbits for the action of a finite group G on a finite set X , consider the set F D f.g; x/ 2 G  X W gx D xg. For g 2 G, let Fix.g/ D fx 2 X W gx D xg, and let (1 if .g; x/ 2 F 1F .g; x/ D 0 otherwise:

i

i

i

i



i

“bookmt” — 2006/8/8 — 12:58 — page 245 — #257

i

i

5.2. GROUP ACTIONS—COUNTING ORBITS

245

We can count F in two different ways:

X X

X jF j D 1F .x; g/ D

jStab.x/j

x2X g2G

x2X

and

X X

X jF j D 1F .x; g/ D jFix.g/j:

g2G x2X

g2G

Dividing by jGj, we get 1 X

X jStab.x/j

X

1

jFix.g/j D

D

:

jGj

jGj

jO.x/j

g2G

x2X

x2X

The last sum can be decomposed into a double sum:

X

1

X X

1

D

;

jO.x/j

jOj

x2X

O x2O where the outer sum is over distinct orbits. But X X

1

X 1 X

X

D 1 D

1;

jOj

jOj

O x2O

O

x2O

O which is the number of orbits! Thus, we have the following result, known as Burnside’s lemma.

Proposition 5.2.2. (Burnside’s lemma). Let a finite group G act on a finite set X . Then the number of orbits of the action is 1 X jFix.g/j: jGj g2G

Example 5.2.3. Let’s use this result to calculate the number of necklaces that can be made from four red beads, three white beads, and two yellow beads. X is the set of

9Š

D 1260

4Š3Š2Š

arrangements of the beads, which we locate at the nine vertices of a nonagon.

Let g be an element of D9 and consider the orbits of hgi acting on vertices of the nonagon. An arrangement of the colored beads is fixed by g if, and only if, all vertices of each orbit of the action of hgi are of the same color.

Every arrangement is fixed by e.

Let r be the rotation of 2=9 of the nonagon. For any k (1  k  8), rk either has order 9, and hrki acts transitively on vertices, or rk has order i

i

i

i



i

“bookmt” — 2006/8/8 — 12:58 — page 246 — #258

i

i

246

5. ACTIONS OF GROUPS 3, and hrki has three orbits, each with three vertices. In either case, there are no fixed arrangements, since it is not possible to place beads of one color at all vertices of each orbit.

Now consider any rotation j of  about an axis through one vertex v of the nonagon and the center of the opposite edge. The subgroup fe; j g has one orbit containing the one vertex v and four orbits containing two vertices. In any fixed arrangement, the vertex v must have a white bead.

Of the remaining four orbits, two must be colored red, one white and one yellow; there are

4Š

D 12

2Š1Š1Š

ways to do this. Thus, j has 12 fixed points in X . Since there are 9 such elements, there are 1 X

1

jFix.g/j D .1260 C 9.12// D 76

jGj

18

g2G

possible necklaces.

Example 5.2.4. How many different necklaces can be made with nine beads of three different colors, if any number of beads of each color can be used? Now the set X of arrangements of beads has 39 elements; namely, each of the nine vertices of the nonagon can be occupied by a bead of any of the three colors. Likewise, the number of arrangements fixed by any g 2 D9 is 3N.g/, where N.g/ is the number of orbits of hgi acting on vertices; each orbit of hgi must have beads of only one color, but any of the three colors can be used. We compute the following data: n-fold rotation axis, order of

N.g/ number of such n D

rotation group elements



1

9

1

9

9

1

6

9

3

3

2

2

2

5

9

Thus, the number of necklaces is 1 X

1

jFix.g/j D .39 C 2  33 C 6  3 C 9  35/ D 1219:

jGj

18

g2G

Example 5.2.5. How many different ways are there to color the faces of a cube with three colors? Regard two colorings to be the same if they are related by a rotation of the cube.

It is required to count the orbits for the action of the rotation group G of the cube on the set X of 36 colorings of the faces of the cube. For each g 2 G the number of x 2 X that are fixed by g is 3N.g/, where N.g/ is

i

i

i

i