6.3: Counting

We saw previously that the size of an orbit is equal to \(|G|/\mathord |G_s|\). We can use this to figure out how many orbits there are in a \(G\)-set in all. This is a very useful thing to count: It's useful for counting things 'up to symmetry.' We'll denote the orbits of \(S\) by \(S/\mathord G\), and thus the number of orbits is \(|S/\mathord G|\). The notation should be read '\(S\)-mod-\(G\)'; it's useful when two things are 'the same' in \(S\) if they are related by an application of an element of \(G\).

For example, let's suppose we wanted to count all of the ways of painting the sides of a cube with three colors. We would naturally think of two ways of painting as being the same if we could rotate the cube to line up the colors in the same way. Then the group \(G\) might be symmetries of the cube, and the set \(S\) would be all ways of painting the cube in fixed position: What we're really trying to count is \(|S/\mathord G|\).

Let \(S^g\) denote the set \(\{s\in S \mid g\cdot s=s\}\). This is like the stabilizer in reverse: we're collecting up all of the elements of the set \(S\) that are fixed by \(g\).

Theorem 6.2.0:

(Burnside's Lemma) The number of orbits in a \(G\)-set \(S\) is \(|S/\mathord G| = \frac{1}{|G|} \sum_{g\in G} |S^g|\).

(Note that there's ample evidence that Burnside didn't actually invent Burnside's lemma; we include the name because it's what everyone knows it by.)

Proof 6.2.1:

Let \(G\cdot s\) denote the orbit of \(s\) under \(G\). First notice that the sum of the size of the fixed sets \(S^g\) is equal to the sum of the size of the stabilizer groups \(G_s\): Both are counting the number of pairs \((g,s)\) such that \(g\cdot s=s\). Then:

\( \sum_{g\in G} |S^g| = \sum_{s\in S} |G_s| \) \( = \sum_{s\in S} |G|/\mathord |G\cdot s|\) \( = |G| \sum_{s\in S} \frac{1}{|G\cdot s|} \) \( = |G| \sum_{S/\mathord G} 1\) \( = |G| |S/\mathord G|\)

Then dividing both sides by \(|G|\) gives the desired result.

Let's try an example. We mentioned earlier the question of the number of ways to color a cube with three colors. Let's try it out. There is an initial question of which group of symmetries we're interested in: Do we allow reflections of the cube or only rotations? Since we can't naturally reflect things in three-dimensional space, we'll stick with the rotation group of the cube. (This choice, by the way, has consequences in chemistry. And here's an excellent Radiolab piece on the topic.)

The rotation group has \(24\) elements: From a base-position of the cube, you can rotate a marked face to any other face (there are six choices), and from there four rotations are available, making \(24\) symmetries in all. Every rotation in 3-dimensional space has an axis of rotation. So each rotational symmetry will have an axis of rotation; we can identify the symmetries by their axis and amount of rotation. We classify these symmetries into five classes, and determine the number of fixed points for each class.

The types of rotational axis for a cube which produce symmetries. From left to right, a 'face' axis, a 'vertex' axis, and an 'edge' axis.

There are \(3^6\) colorings of the base cube to consider in all; for each symmetry, we determine the number of colorings that the symmetry fixes.

1. The identity permutation. This permutation fixes all \(3^6\) colorings.
2. Face rotations by \(\pm 90^\circ\). These are formed by rotating around the axis through the center of two opposite faces. There are six such rotations. In order to fix a coloring, the coloring must have the four 'moving' sides all colored with the same color. The other two sides may be colored in any way. Thus, each of these symmetries fixes \(3^3\) colorings.
3. Face rotations by \(\pm 180^\circ\). Rotation by \(180^\circ\) about the axis through opposite faces. There are three such symmetries. Each requires that opposite 'moving' faces be the same color, while the 'fixed' faces may be colored arbitrarily. Thus, there are \(3^4\) fixed points for these rotations.
4. Vertex rotations by \(\pm 120^\circ\). Rotation through an axis between opposite vertices of the cube. There are four such axes, with two non-trivial rotations through each such axis, for a total of eight symmetries in this class. To fix a coloring, the coloring must have same-colored faces touching the vertices of rotation. There are thus \(3^2\) fixed points for these rotations.
5. Edge rotations by \(\pm 180^\circ\). Rotation through the axis connecting the centers of opposite edges. There are six such rotations. To fix a coloring, such a rotation needs all opposite sides to have the same color. Thus, each one fixes \(3^3\) colorings.

We can then use Burnside's Lemma to find the total number of colorings up to rotation: \(\frac{1}{G}(1\cdot 3^6 + 6\cdot 3^3 + 3\cdot 3^4 + 8\cdot 3^2 + 6\cdot 3^3)=57\).

Exercise 6.2.2

1. Find the number of colorings of the cube with \(n\) colors up to rotation.
2. Find the number of colorings of the octahedron with \(n\) colors up to rotation.

Up to rotation or flip, how many colorings of the board are possible? How about for a \(k \times k\) board?

Contributors and Attributions

• Tom Denton (Fields Institute/York University in Toronto)