Counting Colorings of Polyhedra

When we make polyhedral origami models, one aspect that determines how good the final model looks is how we choose to color its units. Since we usually only concern ourselves with colorings when we make units using solid colored paper, define a coloring to be valid if each unit is a single solid color. (Example origami models in this style include my dodecahedron and icosahedron.) Depending on the model, each unit corresponds to a face, an edge, or a vertex of the underlying polyhedron, so coloring the units amounts to coloring the faces, edges, or vertices.

Although we have lots of freedom with colorings, once we fix a palette of \(n\) colors there are only finitely many ways to color the units of the model. Colorings that are rotations of each other are considered the same, but other transformations are not. (For example, a chiral coloring and its mirror image are considered different.) This is why we work with rotation groups rather than symmetry groups that include reflections. On this page, we will derive general formulas for the number of valid colorings of the Platonic solids. Similar methods extend to other polyhedra and higher-dimensional polytopes.

Symmetry groups are heavily used here, so it might help to read my symmetry groups page first if you're not already familiar with the concept.

The Cauchy–Frobenius Lemma

This is the most important result we will use (it is also known as Burnside's Lemma). Since the main difficulty of counting the number of colorings is taking care of rotational symmetry, applying this lemma to the rotation groups of our target polyhedra resolves everything beautifully.

The Cauchy–Frobenius Lemma states that for any finite group \(G\) acting on a finite set \(X\), \[ |X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g| \] where \(|X/G|\) is the number of orbits and \(|X^g|\) is the number of fixed points of \(g\), that is, the size of the set \(X^g\) of elements of \(X\) that \(g\) leaves unchanged. In our context:

• \(G\) is the rotation group of the polyhedron, that is, the set of all rotations that map the polyhedron to itself. \(|G|\) simply denotes the number of elements in \(G\);
• \(X\) is the total set of possible colorings of the polyhedron. Here, rotations count as distinct colorings;
• Each \(g\in G\) is a rotation of the polyhedron, which acts on a coloring by carrying each colored unit to its new position;
• \(|X^g|\) is the number of colorings that stay invariant under the rotation \(g\). For example, for face colorings of a tetrahedron, if \(g\) is the \(120^{\circ}\) clockwise rotation (when viewed from above) about the vertical axis, then \(X^g\) is the set of all colorings whose three lateral faces are the same color;
• \(|X/G|\) is the number of orbits, which is the quantity we're interested in counting. An orbit is the set of all colorings that can be obtained from a given coloring by rotating it, so all colorings in an orbit are rotations of each other. Since rotations count as the same coloring, counting the number of orbits is exactly our goal.

Our computations rely on a key observation. A rotation \(g\) permutes the units (faces, edges, or vertices) of the polyhedron, and a coloring is fixed by \(g\) exactly when every cycle of this permutation is a single color. So if \(g\) splits the units into \(c(g)\) cycles (counting each unmoved unit as a cycle of length \(1\)) and we have \(n\) colors, then \(|X^g|=n^{c(g)}\).

Applying the Cauchy–Frobenius Lemma to Tetrahedron Edges

This will serve as the first example (a second example, for the cube, follows). All results for other polyhedra are derived using a similar method.

We will assume that our color palette consists of \(n\) colors. Each color can be used as many times as we wish, including \(0\) times. We will compute formulas for the number of valid edge colorings using these \(n\) colors.

We claim that the number of valid colorings is \[ \frac{1}{12}(n^6+3n^4+8n^2) \] Recall that the rotation group \(G\) of a tetrahedron is isomorphic to \(A_4\), which has order \(12\). Concretely, \(G\) acts on the four vertices of the tetrahedron by permuting them, and the induced action on the six edges is what we need. If \(g\in A_4\), then \(g\) falls into one of three categories:

• Case 1: \(g\) is the identity. Then, \(|X^g|=n^6\) because any coloring stays invariant under the do-nothing rotation.
• Case 2: \(g\) represents a \(3\)-cycle. On the tetrahedron, \(g\) corresponds to a \(120^{\circ}\) rotation about any axis through a vertex and the opposite face center. Then, \(|X^g|=n^2\) because for this rotation to keep the coloring invariant, the three base edges must have the same color and the three lateral edges must have the same color.
• Case 3: \(g\) represents a double transposition, such as \((12)(34)\). On the tetrahedron, \(g\) corresponds to a \(180^{\circ}\) rotation about any axis through two opposite edge midpoints. The two edges that the axis passes through are each mapped to themselves (their endpoints swap), so each of them can be colored freely. The remaining four edges are swapped in two pairs, and each pair must have the same color. Then, \(|X^g|=n^4\) because there are \(2+2=4\) independent choices of color.

Since there are \(1,8,3\) elements in \(A_4\) belonging to the above three categories, respectively, the Cauchy–Frobenius Lemma gives the desired count.

As a sanity check, \(n=1\) gives \(1\) coloring, as it should. For \(n=2\) the formula gives \(12\). This agrees with a direct count: there are \(11\) ways to choose which edges get the first color if mirror images are treated as the same, and this becomes \(12\) once mirror images count as different, because exactly one of those \(11\) (the path using three edges) is chiral.

Another Example: Cube Faces

Using the same method, we count face colorings of the cube with \(n\) colors. We claim that the number of valid colorings is \[ \frac{1}{24}(n^6+3n^4+12n^3+8n^2) \] The rotation group of the cube has order \(24\) (it is isomorphic to \(S_4\), acting on the four long diagonals of the cube), and its elements fall into five categories:

• Case 1: \(g\) is the identity (\(1\) element). All six faces are fixed, so \(|X^g|=n^6\).
• Case 2: \(g\) is a \(90^{\circ}\) or \(270^{\circ}\) rotation about an axis through two opposite face centers (\(6\) elements). The two faces on the axis are fixed and the four lateral faces form a single cycle, so \(|X^g|=n^3\).
• Case 3: \(g\) is a \(180^{\circ}\) rotation about an axis through two opposite face centers (\(3\) elements). The two faces on the axis are fixed and the four lateral faces are swapped in two pairs, so \(|X^g|=n^4\).
• Case 4: \(g\) is a \(120^{\circ}\) or \(240^{\circ}\) rotation about an axis through two opposite vertices (\(8\) elements). The six faces split into two \(3\)-cycles, so \(|X^g|=n^2\).
• Case 5: \(g\) is a \(180^{\circ}\) rotation about an axis through two opposite edge midpoints (\(6\) elements). No face is fixed and the six faces are swapped in three pairs, so \(|X^g|=n^3\).

The Cauchy–Frobenius Lemma now gives the desired result. As a sanity check, \(n=2\) gives \(10\) colorings.

Summary of Results for Platonic Solids

The table below gives the number of colorings of each Platonic solid using at most \(n\) colors, where colorings that are rotations of each other count as the same. Dual solids (the cube and octahedron, and the dodecahedron and icosahedron) have the same rotation group and swap their face and vertex formulas.

Further Ideas

While we counted the number of colorings without any restrictions, it is perhaps more interesting to count colorings under special restrictions.

Since we prefer colorings to be symmetric rather than random when we make origami models, such restrictions could come from symmetry constraints. For example, the rotation group of a dodecahedron contains five copies of the tetrahedral rotation group \(A_4\). (Think about the Five Intersecting Tetrahedra origami model.) Using at most \(n\) colors, how many edge colorings of a dodecahedron are invariant under some copy of \(A_4\), counted up to rotations of the dodecahedron?