Counting under symmetry: Burnside's lemma and Polya's enumeration theorem

When objects related by rotation or reflection are considered identical -- as with necklaces -- naive counting fails. Using the language of group actions, Burnside's lemma reduces the problem to a clean formula: the number of distinct objects equals the average number of fixed points across the group.

Folio Official

March 1, 2026

"How many distinct necklaces can be made from four beads using three colors?" The difficulty is not in the counting itself but in the requirement that necklaces related by rotation be considered identical. In the presence of symmetry, naive enumeration breaks down. Burnside's lemma resolves the problem by reducing the count to a single, elegant formula: the average number of colorings fixed by each symmetry.

1 Why naive counting fails

Example 1 (Necklace coloring).

A necklace of four beads is to be colored using three colors. How many distinct necklaces are there, where two colorings are considered the same if one can be rotated into the other?

Ignoring rotations, there are

3^{4} = 81

colorings. The four rotations (

0°

90°

180°

270°

) identify some of these, so one might try dividing by

4

. But

81/4 = 20.25

, which is not an integer.

Remark 2.

The failure of naive division stems from the fact that different colorings have orbits of different sizes. The monochromatic coloring "all red" is unchanged by every rotation (its orbit has size

1

), whereas a coloring with four distinct colors generates four different colorings under rotation (orbit of size

4

). Dividing by

4

implicitly assumes all orbits have the same size, which is false.

2 Group actions and orbits

Definition 3 (Group action).

A group

G

acts on a set

X

if for each

g \in G

there is a map

g : X \to X

such that

$e \cdot x = x$ for all $x \in X$ (the identity acts trivially), and
$(g h) \cdot x = g \cdot (h \cdot x)$ for all $g, h \in G$ and $x \in X$ (compatibility with the group operation).

Definition 4 (Orbit).

The orbit of

x \in X

under the action of

G

Orb (x) = {g \cdot x ∣ g \in G}

– the set of all elements reachable from

x

by applying elements of

G

Remark 5.

In the necklace example,

G = Z /4 Z

(the cyclic group of rotations) and

X

is the set of all

3^{4} = 81

colorings. Two colorings that are related by a rotation belong to the same orbit. The quantity we seek is the number of orbits.

3 Burnside's lemma

Definition 6 (Fixed-point set).

For

g \in G

, the fixed-point set of

g

Fix (g) = {x \in X ∣ g \cdot x = x}

Theorem 7 (Burnside's lemma).

Let a finite group

G

act on a finite set

X

. Then the number of orbits

∣ X / G ∣

∣ X / G ∣ = \frac{1}{∣ G ∣} g \in G \sum ∣ Fix (g) ∣,

the average number of fixed points over all group elements.

Proof.

Define

S = {(g, x) \in G \times X ∣ g \cdot x = x}

and count

∣ S ∣

in two ways.

Summing over

g

first:

∣ S ∣ = \sum_{g \in G} ∣ Fix (g) ∣

Summing over

x

first: for a fixed

x

, the set of

g

satisfying

g \cdot x = x

is the stabilizer

Stab (x)

. By the orbit–stabilizer theorem,

∣ Orb (x) ∣ \cdot ∣ Stab (x) ∣ = ∣ G ∣

, so

∣ Stab (x) ∣ = ∣ G ∣/∣ Orb (x) ∣

. Therefore

∣ S ∣ = x \in X \sum ∣ Stab (x) ∣ = x \in X \sum \frac{∣ G ∣}{∣ Orb ( x ) ∣} .

For each orbit

O

, the sum

\sum_{x \in O} 1/∣ O ∣ = 1

, so

∣ S ∣ = ∣ G ∣ \cdot (number of orbits)

Equating the two expressions for

∣ S ∣

and dividing by

∣ G ∣

yields the result. □

4 Solving the necklace problem

Returning to four beads in three colors with the rotation group $G = {r^{0}, r^{1}, r^{2}, r^{3}}$ (where $r$ denotes $90°$ rotation):

Example 8.

We compute the number of fixed colorings for each group element:

$r^{0}$ (identity): every coloring is fixed, so $∣ Fix (r^{0}) ∣ = 3^{4} = 81$ .
$r^{1}$ ( $90°$ rotation): a coloring is fixed only if all four beads share the same color, so $∣ Fix (r^{1}) ∣ = 3$ .
$r^{2}$ ( $180°$ rotation): a coloring is fixed if opposite beads match, so $∣ Fix (r^{2}) ∣ = 3^{2} = 9$ .
$r^{3}$ ( $270°$ rotation): same constraint as $r^{1}$ , so $∣ Fix (r^{3}) ∣ = 3$ .

By Burnside's lemma,

∣ X / G ∣ = \frac{1}{4} (81 + 3 + 9 + 3) = \frac{96}{4} = 24.

5 Polya's enumeration theorem

Polya's enumeration theorem refines Burnside's lemma by tracking the cycle structure of each group element.

Definition 9 (Cycle index).

Let

G

act on

{1, 2, \dots, n}

. For each

g \in G

, decompose the permutation induced by

g

into disjoint cycles and let

c_{k} (g)

denote the number of cycles of length

k

. The cycle index of

G

Z (G; s_{1}, s_{2}, \dots, s_{n}) = \frac{1}{∣ G ∣} g \in G \sum k = 1 \prod n s_{k}^{c_{k} (g)} .

Theorem 10 (Polya's enumeration theorem).

The number of distinct colorings using

m

colors is

Z (G; m, m, \dots, m)

. Moreover, by substituting appropriate monomials for the

s_{k}

, one can track the number of beads of each color.

Example 11 (Cycle index of the rotation group).

For the cyclic group

Z /4 Z

acting on four beads, the cycle index is

Z (Z /4 Z) = \frac{1}{4} (s_{1}^{4} + s_{4} + s_{2}^{2} + s_{4}) .

Setting

s_{k} = m

for all

k

gives

\frac{1}{4} (m^{4} + 2 m + m^{2})

. For

m = 3

\frac{1}{4} (81 + 6 + 9) = 24

, consistent with our earlier computation.

6 Takeaway

Counting under symmetry amounts to counting orbits of a group action.
Burnside's lemma: $∣ X / G ∣ = \frac{1}{∣ G ∣} \sum_{g} ∣ Fix (g) ∣$ – the average number of fixed points.
Polya's enumeration theorem refines Burnside's lemma using the cycle index.
These tools are indispensable for problems involving rotational or reflective symmetry, such as necklace colorings.

In the final article, we explore the deep relationship between combinatorics and dynamic programming, and take a retrospective view of the entire series.

Combinatorics Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Counting under symmetry: Burnside's lemma and Polya's enumeration theorem

Folio Official

March 1, 2026

1 Why naive counting fails

Example 1 (Necklace coloring).

A necklace of four beads is to be colored using three colors. How many distinct necklaces are there, where two colorings are considered the same if one can be rotated into the other?

Ignoring rotations, there are

3^{4} = 81

colorings. The four rotations (

0°

90°

180°

270°

) identify some of these, so one might try dividing by

4

. But

81/4 = 20.25

, which is not an integer.

Remark 2.

The failure of naive division stems from the fact that different colorings have orbits of different sizes. The monochromatic coloring "all red" is unchanged by every rotation (its orbit has size

1

), whereas a coloring with four distinct colors generates four different colorings under rotation (orbit of size

4

). Dividing by

4

implicitly assumes all orbits have the same size, which is false.

2 Group actions and orbits

Definition 3 (Group action).

A group

G

acts on a set

X

if for each

g \in G

there is a map

g : X \to X

such that

$e \cdot x = x$ for all $x \in X$ (the identity acts trivially), and
$(g h) \cdot x = g \cdot (h \cdot x)$ for all $g, h \in G$ and $x \in X$ (compatibility with the group operation).

Definition 4 (Orbit).

The orbit of

x \in X

under the action of

G

Orb (x) = {g \cdot x ∣ g \in G}

– the set of all elements reachable from

x

by applying elements of

G

Remark 5.

In the necklace example,

G = Z /4 Z

(the cyclic group of rotations) and

X

is the set of all

3^{4} = 81

colorings. Two colorings that are related by a rotation belong to the same orbit. The quantity we seek is the number of orbits.

3 Burnside's lemma

Definition 6 (Fixed-point set).

For

g \in G

, the fixed-point set of

g

Fix (g) = {x \in X ∣ g \cdot x = x}

Theorem 7 (Burnside's lemma).

Let a finite group

G

act on a finite set

X

. Then the number of orbits

∣ X / G ∣

∣ X / G ∣ = \frac{1}{∣ G ∣} g \in G \sum ∣ Fix (g) ∣,

the average number of fixed points over all group elements.

Proof.

Define

S = {(g, x) \in G \times X ∣ g \cdot x = x}

and count

∣ S ∣

in two ways.

Summing over

g

first:

∣ S ∣ = \sum_{g \in G} ∣ Fix (g) ∣

Summing over

x

first: for a fixed

x

, the set of

g

satisfying

g \cdot x = x

is the stabilizer

Stab (x)

. By the orbit–stabilizer theorem,

∣ Orb (x) ∣ \cdot ∣ Stab (x) ∣ = ∣ G ∣

, so

∣ Stab (x) ∣ = ∣ G ∣/∣ Orb (x) ∣

. Therefore

∣ S ∣ = x \in X \sum ∣ Stab (x) ∣ = x \in X \sum \frac{∣ G ∣}{∣ Orb ( x ) ∣} .

For each orbit

O

, the sum

\sum_{x \in O} 1/∣ O ∣ = 1

, so

∣ S ∣ = ∣ G ∣ \cdot (number of orbits)

Equating the two expressions for

∣ S ∣

and dividing by

∣ G ∣

yields the result. □

4 Solving the necklace problem

Returning to four beads in three colors with the rotation group $G = {r^{0}, r^{1}, r^{2}, r^{3}}$ (where $r$ denotes $90°$ rotation):

Example 8.

We compute the number of fixed colorings for each group element:

$r^{0}$ (identity): every coloring is fixed, so $∣ Fix (r^{0}) ∣ = 3^{4} = 81$ .
$r^{1}$ ( $90°$ rotation): a coloring is fixed only if all four beads share the same color, so $∣ Fix (r^{1}) ∣ = 3$ .
$r^{2}$ ( $180°$ rotation): a coloring is fixed if opposite beads match, so $∣ Fix (r^{2}) ∣ = 3^{2} = 9$ .
$r^{3}$ ( $270°$ rotation): same constraint as $r^{1}$ , so $∣ Fix (r^{3}) ∣ = 3$ .

By Burnside's lemma,

∣ X / G ∣ = \frac{1}{4} (81 + 3 + 9 + 3) = \frac{96}{4} = 24.

5 Polya's enumeration theorem

Polya's enumeration theorem refines Burnside's lemma by tracking the cycle structure of each group element.

Definition 9 (Cycle index).

Let

G

act on

{1, 2, \dots, n}

. For each

g \in G

, decompose the permutation induced by

g

into disjoint cycles and let

c_{k} (g)

denote the number of cycles of length

k

. The cycle index of

G

Z (G; s_{1}, s_{2}, \dots, s_{n}) = \frac{1}{∣ G ∣} g \in G \sum k = 1 \prod n s_{k}^{c_{k} (g)} .

Theorem 10 (Polya's enumeration theorem).

The number of distinct colorings using

m

colors is

Z (G; m, m, \dots, m)

. Moreover, by substituting appropriate monomials for the

s_{k}

, one can track the number of beads of each color.

Example 11 (Cycle index of the rotation group).

For the cyclic group

Z /4 Z

acting on four beads, the cycle index is

Z (Z /4 Z) = \frac{1}{4} (s_{1}^{4} + s_{4} + s_{2}^{2} + s_{4}) .

Setting

s_{k} = m

for all

k

gives

\frac{1}{4} (m^{4} + 2 m + m^{2})

. For

m = 3

\frac{1}{4} (81 + 6 + 9) = 24

, consistent with our earlier computation.

6 Takeaway

Counting under symmetry amounts to counting orbits of a group action.
Burnside's lemma: $∣ X / G ∣ = \frac{1}{∣ G ∣} \sum_{g} ∣ Fix (g) ∣$ – the average number of fixed points.
Polya's enumeration theorem refines Burnside's lemma using the cycle index.
These tools are indispensable for problems involving rotational or reflective symmetry, such as necklace colorings.

In the final article, we explore the deep relationship between combinatorics and dynamic programming, and take a retrospective view of the entire series.

Combinatorics Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Counting under symmetry: Burnside's lemma and Polya's enumeration theorem

1 Why naive counting fails

2 Group actions and orbits

3 Burnside's lemma

4 Solving the necklace problem

5 Polya's enumeration theorem

6 Takeaway

Share your expertise with the world

More from Folio Official

Recurrences and generating functions: what happens when you turn a sequence into a function

Combinatorics meets dynamic programming: when counting becomes computation

Inclusion--exclusion: why the alternating signs work

What does it mean to count? Addition, multiplication, and surjections

Counting under symmetry: Burnside's lemma and Polya's enumeration theorem

1 Why naive counting fails

2 Group actions and orbits

3 Burnside's lemma

4 Solving the necklace problem

5 Polya's enumeration theorem

6 Takeaway

Share your expertise with the world

More from Folio Official

Recurrences and generating functions: what happens when you turn a sequence into a function

Combinatorics meets dynamic programming: when counting becomes computation

Inclusion--exclusion: why the alternating signs work

What does it mean to count? Addition, multiplication, and surjections