Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 36 ยท Applications

Burnside's Lemma

Count objects up to symmetry with Burnside's lemma: necklaces, bracelets and cube colorings, with the group action explained and every count checked by brute force.

How many different necklaces can you make with 6 beads in 3 colors, if rotating a necklace gives the same necklace? Counting all 3^6 = 729 colorings overcounts: many are rotations of each other. Burnside's lemma counts colorings up to symmetry without listing them.

Groups acting on objects

A symmetry group G is a set of transformations that can be composed and undone: rotations of a necklace, rotations of a cube, reflections of a bracelet. Two colorings are equivalent if some element of G turns one into the other. We want the number of equivalence classes (called orbits).

Burnside's lemma: the number of orbits is the average number of colorings fixed by a group element: (1/|G|) * sum over g in G of Fix(g).

Fix(g) is the number of colorings that do not change when g is applied. For a coloring to be unchanged, all positions in the same cycle of the permutation g must have the same color, so Fix(g) = k^(c(g)) where k is the number of colors and c(g) the number of cycles of g.

Necklaces

For n beads and k colors, the group is the n rotations. Rotation by i positions splits the beads into gcd(n, i) cycles. So:

necklaces(n, k) = (1/n) * sum_{i=0}^{n-1} k^gcd(n,i).

Bracelets allow flipping too (group of 2n elements). For odd n every reflection has (n+1)/2 cycles; for even n, half the reflections have n/2 + 1 cycles and half have n/2.

Python Necklaces and bracelets: Burnside vs brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With 3 colors there are 130 necklaces and 92 bracelets of length 6. In every row brute force and Burnside agree. The brute-force method picks, for each coloring, a canonical representative (the smallest string among all its symmetric images) and counts distinct representatives; that works but needs k^n steps, while Burnside needs only n.

Coloring the faces of a cube

The 24 rotations of a cube act on its 6 faces. Burnside gives the number of distinct colorings. We could classify the 24 rotations by hand (identity, 6 quarter-turns about face axes, 3 half-turns about face axes, 8 third-turns about corners, 6 half-turns about edges) but we can also let the computer generate the group from two generators and compute cycle counts.

Python Generate the cube rotation group and count colorings

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Faces are numbered 0 top, 1 bottom, 2 front, 3 back, 4 left, 5 right. The closure loop finds exactly 24 rotations. The answers are 10 colorings with 2 colors, 57 with 3 colors, and 240 with 4 colors; the Burnside count and the brute-force orbit count agree. The closed form is (k^6 + 3k^4 + 12k^3 + 8k^2)/24.

flowchart LR
    A["Group G of symmetries"] --> B["For each g: count cycles c(g)"]
    B --> C["Fix(g) = k^c(g)"]
    C --> D["Average over G"]
    D --> E["Number of distinct colorings"]

Burnside in four steps.

Why the lemma works

Count pairs (g, x) with g fixing x. Summing over g gives sum Fix(g). Summing over x gives sum |Stab(x)|, and by orbit-stabilizer |Stab(x)| = |G|/|orbit(x)|. Each orbit of size s has s members, each contributing |G|/s, so an orbit contributes |G| in total. Dividing by |G| leaves one per orbit.

Count cycles of the permutation on the positions being colored (beads, faces), not on the colors. And remember to include the identity: it fixes all k^n colorings.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Burnside's lemma says the number of orbits equals...

    Number of orbits = (1/|G|) * sum of Fix(g).
  2. 2. How many colorings of a necklace with n beads and k colors are fixed by rotation by i positions?

    The rotation splits the beads into gcd(n,i) cycles; each cycle must be one color.
  3. 3. How many distinct 2-colorings of the faces of a cube are there up to rotation?

    Burnside over the 24 rotations gives 10.
  4. 4. Why is k^n / |G| usually NOT the answer?

    Colorings fixed by non-identity elements lie in smaller orbits; Burnside corrects for them.

Summary

  • Burnside: orbits = average number of fixed colorings; Fix(g) = k^(number of cycles of g).
  • Necklaces: (1/n) sum k^gcd(n,i); bracelets add reflections.
  • Cube faces: 24 rotations give 10, 57, 240 colorings for 2, 3, 4 colors.
  • Brute force with canonical representatives is the reliable cross-check.

Next: Stirling Numbers