Skip to content
Tutorials Center
My learning

Topics

Lesson 36 of 68 · Counting

Counting with Symmetry: Burnside's Lemma

Count objects up to symmetry with Burnside's lemma: orbits, fixed points, necklaces and colored cubes, all verified against brute force in Python.

How many different necklaces can you make from 6 beads in 2 colors? There are 2⁶ = 64 ways to color six positions in a row, but a necklace can be rotated, so RRRBBB and RBBBRR are the same necklace. Counting "up to symmetry" is a different problem, and naive division fails: you cannot just divide 64 by 6, because some colorings (like all red) look the same after every rotation.

Burnside's lemma, sometimes called the Cauchy-Frobenius lemma, solves the problem exactly. It uses only the idea of a group of symmetries, introduced in Groups and Symmetry, and a simple count.

Orbits and fixed points

Let a group G of symmetries act on a set X of objects (here: all colorings). Two objects are equivalent if some symmetry turns one into the other. The equivalence classes are called orbits, and the number we want is the number of orbits.

For a symmetry g, let Fix(g) be the set of objects that g leaves unchanged. Burnside's lemma states:

number of orbits = (1 / |G|) · Σ over g in G of |Fix(g)|

In words: average the number of fixed colorings over all symmetries. Intuitively, an object with lots of symmetry is fixed by many g, so it is counted by many terms but lives in a small orbit; the average compensates exactly.

Burnside in four steps

List symmetries Write every element of the group.
Count fixed For each, count colorings it leaves unchanged.
Add up Sum all the fixed counts.
Divide Divide by the group size.

The result is the number of essentially different objects.

1 / 2

Necklaces under rotation

Take n beads on a circle with k available colors, where only rotations count. The group has n elements: rotate by 0, 1, ..., n-1 positions. A rotation by r positions splits the beads into gcd(n, r) cycles, and a coloring is fixed exactly when every cycle is a single color. That gives k^gcd(n, r) fixed colorings, so:

necklaces(n, k) = (1/n) · Σ_{r=0}^{n-1} k^gcd(n, r)

For n = 6 and k = 2: the rotations contribute 2⁶, 2¹, 2², 2³, 2², 2¹ = 64 + 2 + 4 + 8 + 4 + 2 = 84, and 84 / 6 = 14 distinct necklaces.

Python Necklaces: Burnside against 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.

Both columns match in every row. Brute force needs kⁿ colorings and a canonical form for each; Burnside needs only n terms.

Bracelets: rotations and flips

A bracelet can also be flipped over, so the group is the dihedral group with 2n elements: the n rotations plus n reflections. For n beads:

  • If n is odd, each of the n reflections passes through one bead and fixes k^((n+1)/2) colorings.
  • If n is even, half the reflections pass through two beads (fixing k^(n/2 + 1)) and half pass between beads (fixing k^(n/2)).
Python Bracelets with rotations and reflections

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.

For 6 beads in 2 colors there are 14 necklaces but only 13 bracelets, because one necklace and its mirror image merge into a single bracelet.

Coloring a cube

How many ways can you paint the six faces of a cube with 3 colors, treating rotated cubes as the same? The rotation group of the cube has 24 elements:

Type of rotation How many Cycles on faces Fixed colorings
Identity 1 6 k⁶
90° or 270° about a face axis 6 1 + 1 + 4 k³
180° about a face axis 3 1 + 1 + 2 + 2 k⁴
120° or 240° about a corner axis 8 3 + 3 k²
180° about an edge axis 6 2 + 2 + 2 k³

Summing: (k⁶ + 6k³ + 3k⁴ + 8k² + 6k³) / 24 = (k⁶ + 3k⁴ + 12k³ + 8k²) / 24. For k = 3: (729 + 243 + 324 + 72) / 24 = 1368 / 24 = 57.

Python Colored cubes by 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.

Both give 1, 10 and 57 for one, two and three colors. Burnside's formula needs a table of 24 rotations; the brute force needs k⁶ colorings, which grows quickly.

When to use it

Use Burnside whenever the question is "how many essentially different arrangements" under rotations, reflections or relabelings: chemical isomers, graph colorings up to isomorphism, board positions up to symmetry, puzzle solutions. The hard part is identifying the group and its cycle structure on the object; after that the lemma is arithmetic.

Do not divide the total count by the group size directly. That gives the right answer only when no object is fixed by a non-identity symmetry, which is rarely the case.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What does Burnside's lemma compute?

    The lemma averages the fixed-point counts over the group and the result equals the number of orbits.
  2. 2. For 4 beads in 2 colors with rotations only, how many distinct necklaces are there?

    (2^4 + 2^1 + 2^2 + 2^1) / 4 = 24 / 4 = 6.
  3. 3. How many colorings of n beads in k colors does a rotation by r positions fix?

    The rotation splits the beads into gcd(n, r) cycles, and each cycle must be one color.
  4. 4. Why is dividing the total number of colorings by the group size generally wrong?

    An all-red necklace is alone in its orbit, so orbits differ in size and a plain division undercounts.

Summary

  • An orbit is a set of objects equivalent under the symmetries of a group; Burnside counts orbits.
  • Number of orbits = average over the group of the number of objects each symmetry fixes.
  • Necklaces: (1/n) Σ k^gcd(n, r). Bracelets add reflections and a group of size 2n.
  • The cube with 3 face colors has 57 colorings up to rotation.
  • Always verify small cases by brute force when you set up a new group.

Continue with Probability Basics.