Skip to content
Tutorials Center
My learning

Topics

Lesson 184 of 225 ยท Math and Bit Manipulation

Burnside's Lemma and Counting Necklaces

Count objects up to symmetry with Burnside lemma in Python: necklaces under rotation, bracelets with reflection and grid colorings, checked by brute force.

How many different necklaces can you make from 4 beads in 2 colors? There are 2^4 = 16 ways to color 4 positions in a row. But a necklace can be rotated, so RRBB and RBBR are the same necklace. Counting objects while treating symmetric copies as one is a classic counting problem, and Burnside's lemma solves it without listing anything.

The lemma turns "count the distinct classes" into "average how many colorings each symmetry leaves unchanged". Once you see it, necklaces, bracelets, rotating board games and colored cubes become short formulas. We will check every formula against a brute-force count in Python.

Symmetries and orbits

A symmetry (or group element) is a transformation such as "rotate by one position". The set of all allowed symmetries forms a group G: doing two of them in a row is another symmetry, there is a "do nothing" symmetry, and every symmetry can be undone.

Two colorings are equivalent if some symmetry maps one into the other. The set of colorings equivalent to a given one is its orbit. We want the number of orbits.

For 4 beads and rotations, G has 4 elements: rotate by 0, 1, 2 or 3 positions.

flowchart LR
  A["RRBB"] -->|rotate 1| B["BRRB"]
  B -->|rotate 1| C["BBRR"]
  C -->|rotate 1| D["RBBR"]
  D -->|rotate 1| A

These four colorings form one orbit: they are the same necklace.

Burnside's lemma

For each symmetry g, let fix(g) be the number of colorings that do not change when g is applied. Then

TEXT
number of orbits = (1 / |G|) * sum of fix(g) over all g in G

In words: the number of distinct objects is the average number of fixed colorings. The identity fixes everything (k^n colorings), and every other symmetry fixes fewer, which pulls the average down toward the true count.

Brute force first

Before trusting a formula, let us count necklaces by brute force: for each coloring compute its canonical form (the smallest among all its rotations) and count distinct canonical forms. This is O(k^n * n * n) so only suitable for small inputs, which is exactly what we need as a checker.

Python Brute-force necklace count and Burnside by fixed points

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 approaches agree, but the second still enumerates colorings. The real power comes from knowing fix(g) without enumerating.

Counting fixed colorings with cycles

A rotation by s positions splits the n positions into cycles. A coloring is fixed exactly when every cycle is a single color. So if g has c(g) cycles, fix(g) = k^c(g).

For a rotation by s positions of n beads, the number of cycles is gcd(n, s). Summing over s = 0..n-1:

TEXT
necklaces(n, k) = (1 / n) * sum for s = 0..n-1 of  k^gcd(n, s)

Here gcd(n, 0) = n. Grouping the terms by the divisor d = gcd(n, s) gives the equivalent form with Euler's totient (see number theory):

TEXT
necklaces(n, k) = (1 / n) * sum over d | n of  phi(n / d) * k^d
Python Necklace formula in O(n log n)

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.

The first line prints the binary necklace sequence 2, 3, 4, 6, 8, 14, 20, 36, ... Note that division by n is exact over the integers, and for modular answers you multiply by the inverse of n instead.

Bracelets: rotations plus reflections

A bracelet can also be flipped over. The group now has 2n elements: n rotations and n reflections. The reflection cycles depend on whether n is odd or even:

  • n odd: every reflection fixes one bead and swaps (n-1)/2 pairs, so it has (n+1)/2 cycles.
  • n even: n/2 reflections go through two opposite beads (n/2 + 1 cycles) and n/2 reflections go between beads (n/2 cycles).
TEXT
bracelets(n, k) = ( rotation_sum + reflection_sum ) / (2n)
Python Bracelets with Burnside, checked 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.

For example 6 beads in 2 colors give 14 necklaces but only 13 bracelets: one necklace is a mirror image of another, and flipping merges them.

Beyond necklaces: colorings of a grid

Burnside works for any group. Take a 2 by 2 grid whose cells are colored with k colors, where rotating the board by 90 degrees gives the same board.

  • Rotate 0: 4 cycles of length 1, so k^4 fixed colorings.
  • Rotate 90 or 270: one cycle of 4 cells, so k fixed colorings each.
  • Rotate 180: two cycles of 2 cells, so k^2.
TEXT
boards(k) = (k^4 + 2*k + k^2) / 4

The recipe is always the same: list the symmetries, count cycles of each on the positions, and average k^cycles.

Python Rotating boards: Burnside on a grid

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.

The 4 by 4 case with 2 colors has 65,536 boards for the brute force, but Burnside needs only four cycle counts.

Choosing the right tool

Situation Group Formula
Necklace, rotations only n rotations (1/n) * sum k^gcd(n, s)
Bracelet, rotations and flips 2n elements rotation sum plus reflection sum, divided by 2n
Square board, turns only 4 rotations (1/4) * sum of k^cycles over the four turns
Count everything, ignore symmetry identity only k^n

Common mistakes:

  • Forgetting the identity element (shift 0).
  • Dividing by the wrong group size (it is n for rotations, 2n with reflections).
  • Mixing up "number of cycles" with "length of cycles": fix(g) = k^(number of cycles).
  • Counting symmetric objects twice when the question asks for distinct objects only; that is exactly what Burnside prevents.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does Burnside's lemma say the number of orbits equals?

    Orbits = (1/|G|) * sum of fix(g). The division by the group size is what removes the over-counting.
  2. 2. For a rotation of n beads by s positions, how many cycles do the positions form?

    Each cycle has length n / gcd(n, s), so there are gcd(n, s) of them. A coloring is fixed when every cycle has one color, giving k^gcd(n, s).
  3. 3. How many distinct necklaces can 3 beads make with 3 colors (rotations only)?

    (3^3 + 3^1 + 3^1) / 3 = 33 / 3 = 11. The identity fixes 27 colorings and each of the other two rotations fixes 3.
  4. 4. Why is the group of a bracelet of n beads of size 2n?

    A bracelet can be turned (n rotations) and flipped over (n reflections), so the group has 2n elements and the final division is by 2n.

Summary

  • Burnside's lemma: the number of objects up to symmetry equals the average number of objects fixed by each symmetry.
  • A symmetry that splits the positions into c cycles fixes k^c colorings.
  • Necklaces under rotation: (1/n) * sum over s of k^gcd(n, s). Bracelets add n reflections and divide by 2n.
  • Always sanity-check a symmetry formula against a brute-force canonical-form count on small inputs.
  • Include the identity, and remember modular versions need the inverse of the group size.

Next: Primitive Roots and Discrete Logarithm