A necklace is a ring of colored beads, and two necklaces are the same if one can be rotated into the other. How many necklaces have beads, each black or white? Recording the colors at positions counterclockwise gives strings, and Figure 14.1 sorts them into classes of strings that are rotations of one another. There are classes. Dividing by the rotations gives the wrong answer , because the classes have different sizes: BWBW is unchanged by a half turn and has only rotations, and BBBB has only . This note develops the language of group actions, explains the class sizes with the orbit–stabilizer theorem, and counts classes with Burnside’s lemma.
Figure14.1: The black-and-white colorings of four positions, sorted into classes of colorings that are rotations of one another. The number above each column is the size of the class. Position is at the bottom left, and the positions continue counterclockwise.#
After studying these notes, you will be able to do the following.
Recognize a group action, including the action of a group on colorings.
Compute orbits and stabilizers, and use the orbit–stabilizer theorem to find orbit sizes.
State and prove Burnside’s lemma.
Count the colorings fixed by a group element from its number of cycles.
Count strings, necklaces, bracelets, grid colorings, and cube colorings up to symmetry.
Throughout, groups and their notation are as in Lecture Note 14.
A permutation group on acts on by . For instance, acts on the corners of the square.
A group acts on itself by ; these are the permutations of Cayley’s theorem.
A subgroup of acts on by . The rules hold because .
acts on the -element subsets of by .
The action we need for counting moves colorings. Let be a finite set of positions and a set of colors. A coloring is a function ; there are colorings. When we write as the string . If acts on , moving a coloring by carries the color at each position to the position . So is the coloring with , or equivalently
For example, moves the colors of BBWW one position counterclockwise: .
The columns of Figure 14.1 are the orbits of the rotation group on the colorings. A necklace with beads and colors is an orbit of the colorings of the corners of a regular -gon under the rotation group , and a bracelet is an orbit under the full symmetry group , which also allows turning the ring over.
Since , lies in its own orbit. If , say , then and , so ; hence two orbits with a common element are both equal to . For the stabilizer, , and if then . By the subgroup test for finite sets in Lecture Note 14, a nonempty finite subset closed under the operation is a subgroup.
Under , the stabilizer of BWBW is , and its orbit has elements; the stabilizer of BBWW is , and its orbit has ; the stabilizer of BBBB is , and its orbit has . In each case the product of the two numbers is .
For , let . Every lies in exactly one set , namely the one with , so by the sum rule . We show that each has elements. Fix . If , then , so . Conversely, if , then , so . The maps and undo each other, so they are inverse bijections between and . Hence .
The symmetries of a regular -gon act on its corners. A rotation moves corner to any corner, so the orbit of corner has elements. A symmetry fixing corner must send corner to one of the two corners adjacent to , and those two choices determine the symmetry, as for the square; so the stabilizer has elements, and .
The rotations of a cube act on its faces. Any face can be rotated to any other, and the rotations that keep a given face in place are the rotations about the axis through its center. So the cube has rotations.
The orbit–stabilizer theorem also proves Lagrange’s theorem, stated in Lecture Note 14.
Let act on by , as in Example 14.2. If , then , and cancellation gives ; so every stabilizer is , and by the orbit–stabilizer theorem every orbit has exactly elements. The orbits split the elements of into blocks of elements each, so divides .
We count the set of pairs with in two ways. For each there are such pairs, so . For each there are such pairs, and by the orbit–stabilizer theorem . If is an orbit, its elements contribute
pairs. So if there are orbits, , and comparing the two counts gives the formula.
The number of orbits is the average number of elements fixed by a group element. Large orbits have small stabilizers and small orbits have large stabilizers, and the double count gives every orbit the same weight .
For colorings, the fixed sets are determined by cycles. Write for the number of cycles, including fixed points, of the permutation of the positions.
By (14.1), means for all ; replacing by , this says for all . That holds exactly when consecutive positions of every cycle have the same color, that is, when is constant on each cycle. Choosing one color per cycle gives fixed colorings.
Cycle notation omits fixed points, but counts them. For example, has on the corners of the square and fixes colorings, not .
Combining the two theorems, the number of orbits of colorings with colors is
In each example below, the work is to list the elements of and count their cycles on the positions.
Reading a string of length backwards gives its reversal. How many strings of length over letters are there, if a string and its reversal count as the same? The group is , where sends position to position . The cycles of are the pairs , together with the middle position when is odd, so . The answer is
For and , this is : the palindromes are fixed by , and the other strings form pairs.
For the opening problem, the rotations of the square have cycle counts ,, and , so there are
necklaces with beads and colors, as in Figure 14.1.
For beads, the rotation moves every position steps. Its cycles are described by the greatest common divisor , with the convention . We use one fact from elementary number theory: if and have no common divisor greater than and divides , then divides .
Applying to a position times moves it steps, which returns it to its start exactly when divides . So every cycle has length equal to the smallest with . For this is . Otherwise write and , where and have no common divisor greater than ; then exactly when , exactly when . So the cycles have length , and there are of them.
For , the values for are , and with there are necklaces. If is prime, every rotation other than has one cycle, and there are necklaces. Since this number is an integer, divides . This is Fermat’s little theorem, obtained here by counting necklaces.
For bracelets we also need the reflections. Computing with corner labels modulo (so that means corner ), the reflections of the -gon are the permutations
Each places the corners in clockwise order, the maps have different values , and together with the rotations they give all symmetries. Each exchanges the corners and , so its cycles have length or , and its fixed points solve . For the square, ,,,.
If is odd, each has one fixed point, so .
If is even, the reflections with even have two fixed points, so ; the with odd have none, so .
Adding these terms to the rotation terms, the number of bracelets is
With and ,, and there are bracelets, one fewer than necklaces. With and , there are necklaces and bracelets.
14.4.4 Black-and-white images on a three-by-three grid#
How many black-and-white images on a grid of pixels are there, if images that differ by a rotation or reflection of the grid count as the same? The group is , now acting on the cells.
has cycles.
The quarter turns and fix the center and move the four corner cells in one -cycle and the four edge cells in another: cycles.
The half turn fixes the center and exchanges opposite cells in pairs: cycles.
Each of the four reflections fixes the cells on its axis and exchanges the other in pairs: cycles.
By Example 14.7, the cube has rotations. They are sorted by their axes:
the identity: cycles on the faces;
rotations by or about an axis through the centers of two opposite faces ( axes, rotations): the two faces on the axis are fixed and the other four form a -cycle, so cycles;
rotations by about the same axes ( rotations): two fixed faces and two -cycles, so cycles;
rotations by or about an axis through two opposite vertices ( axes, rotations): the three faces at each of the two vertices form a -cycle, so cycles;
rotations by about an axis through the midpoints of two opposite edges ( axes, rotations): the faces are exchanged in pairs, so cycles.
These account for rotations, so the list is complete. With colors, the number of colorings of the faces up to rotation is
For this is , and for it is .
Count the necklaces and the bracelets with beads and colors. Count the black-and-white images on a grid up to rotations and reflections, and check the answer by listing them. Count the colorings of the vertices of a cube with colors up to rotation.
