Group Actions, The Burnside Polya Theorem

The Burnside Polya Theorem

Let G be a permutation group on points, and let each point have one of k colors assigned. The number of distinct color assignments can often be calculated. The Burnside Polya theorem gives us a formula, a polynomial in k.

Two assignments are distinct if no group operation transforms one assignment into the other. For instance, we might wish to count the number of distinct cubes where each face is painted one of three colors. Two patterns are not distinct if we can simply rotate the cube to flip between them. All the patterns with 5 faces red and one face blue are essentially the same.

Let S be the set of all possible color assignments, so that each orbit in S is a distinct pattern. In our example, there are 24 rotations of the cube, hence |G| = 24. Apply the burnside counting theorem, and the number of orbits, or distinct cubes, is the sum of χ(a) ÷ |G|. In many cases χ() can be derived.

Returning to the world of colored cubes, the number of patterns preserved by a rotation is always some power of k, so the resulting expression is a polynomial in k. For a given rotation of the cube, we only need know the cycles. If a rotation leaves the top and bottom fixed, and spins the other 4 faces clockwise 90°, we have two trivial cycles (top and bottom) and a 4 cycle. This rotation fixes k³ color assignments, one color for the top, one for the bottom, and one for the four sides.

Review the notation for describing permutations as cycles, then verify that the cubes 24 rotations have the following cycle decomposition.

c₁⁶ + 8c₃² + 6c₁²c₄ + 3c₁²c₂² + 6c₂³

If a transformation has 3 cycles, like the 90° rotation described earlier, it fixes k³ color combinations. In general, we only need count the number of cycles in a permutation. Apply this to the decomposition above to get:

( k⁶ + 3k⁴ + 12k³ + 8k² ) / 24

There are thus 10 cubes with two colors, 57 cubes with three colors, and 240 cubes with four colors.

Consider another example, a necklace with 13 beads. Beads can be any of k colors. The group acting on the beads is the dihedral group D₁₃. Two necklaces aren't really different if you can spin one around or flip it over to make it look like the other. Here is the cycle decomposition, followed by the formula for k colors.

c₁¹³ + 12c₁₃ + 13c₁c₂⁶
(k¹³ + 13k⁷ + 12k) / 26

There are 380 necklaces with just 2 colors, and you have to admit, it would take you quite a while to verify this by hand.

Constrained Color Patterns

When patterns have additional constraints, simple color polynomials p(k) may not suffice. Still, the rotation group often provides the solution.

Imagine we are coloring the faces of a cube with three colors, but we must use all three colors. Terms like c₆, c₅c₁, and c₃² degenerate to 0, since they cannot accommodate three colors. Terms like c₁⁶ cannot be replaced with 3⁶, since some combinations do not use all three colors. Use inclusion exclusion to compute:

c₁⁶ = 3⁶ - 3×2⁶ + 3×1⁶ = 540

The number of three colored cubes with all three colors represented is therefore 30. Other constraints can be incorporated in this manner.