Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry

Starting from the definitions of group actions, orbits, and stabilizers, we prove Burnside's lemma (the Cauchy--Frobenius theorem), introduce the cycle index of a permutation group, and derive P\'olya's enumeration theorem. Applications to necklace and bracelet counting are given.

Folio Official

March 1, 2026

1 Group Actions, Orbits, and Stabilizers

Definition 1 (Group action).

A group

G

acts on a set

X

if there is a map

G \times X \to X

(written

(g, x) \mapsto g \cdot x

) satisfying:

$e \cdot x = x$ for all $x \in X$ , where $e$ is the identity element of $G$ ;
$(g h) \cdot x = g \cdot (h \cdot x)$ for all $g, h \in G$ and $x \in X$ .

Definition 2 (Orbit and stabilizer).

The orbit of

x \in X

under

G

G \cdot x = {g \cdot x ∣ g \in G}

. The stabilizer of

x

G_{x} = {g \in G ∣ g \cdot x = x}

Theorem 3 (Orbit–stabilizer theorem).

∣ G \cdot x ∣ = \frac{∣ G ∣}{∣ G _{x} ∣} = [G : G_{x}]

Proof.

The map

g G_{x} \mapsto g \cdot x

is a well-defined bijection from the set of cosets

G / G_{x}

to the orbit

G \cdot x

. Indeed,

g G_{x} = h G_{x}

if and only if

h^{- 1} g \in G_{x}

, which holds if and only if

g \cdot x = h \cdot x

. Surjectivity is immediate. □

Definition 4 (Fixed-point set).

For

g \in G

, the fixed-point set of

g

X^{g} = {x \in X ∣ g \cdot x = x}

2 Burnside's Lemma

Theorem 5 (Burnside's lemma (Cauchy–Frobenius theorem)).

When a finite group

G

acts on a finite set

X

, the number of orbits

∣ X / G ∣

∣ X / G ∣ = \frac{1}{∣ G ∣} g \in G \sum ∣ X^{g} ∣.

Proof.

We count the elements of the set

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

in two ways.

Summing over

g

∣ S ∣ = \sum_{g \in G} ∣ X^{g} ∣

Summing over

x

∣ S ∣ = \sum_{x \in X} ∣ G_{x} ∣

. By the orbit–stabilizer theorem,

∣ G_{x} ∣ = ∣ G ∣/∣ G \cdot x ∣

, so

x \in X \sum ∣ G_{x} ∣ = x \in X \sum \frac{∣ G ∣}{∣ G \cdot x ∣} = ∣ G ∣ x \in X \sum \frac{1}{∣ G \cdot x ∣} .

Each orbit

O

contributes

∣ O ∣

terms of

1/∣ O ∣

each, so each orbit contributes exactly

1

. Hence

\sum_{x \in X} 1/∣ G \cdot x ∣ = ∣ X / G ∣

Equating the two expressions gives

\sum_{g \in G} ∣ X^{g} ∣ = ∣ G ∣ \cdot ∣ X / G ∣

, from which the result follows. □

3 The Cycle Index

Definition 6 (Cycle index).

Let a finite group

G

act on

{1, 2, \dots, n}

. For each

g \in G

, regard

g

as a permutation and let

j_{k} (g)

denote the number of

k

-cycles in its cycle decomposition. The cycle index of

G

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

4 Pólya's Enumeration Theorem

Theorem 7 (P\'olya enumeration theorem).

The number of colorings of

n

positions with

m

colors, up to the symmetry group

G

, is

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

More generally, the weighted generating function is obtained by substituting

Z (G; s_{1} = i \sum w_{i}, s_{2} = i \sum w_{i}^{2}, \dots, s_{k} = i \sum w_{i}^{k}, \dots)

where

w_{1}, \dots, w_{m}

are weights assigned to the colors.

Proof.

By Burnside's lemma, the number of orbits is

\frac{1}{∣ G ∣} \sum_{g \in G} ∣ X^{g} ∣

. If the cycle decomposition of

g

consists of cycles of lengths

c_{1}, c_{2}, \dots

, then a coloring is fixed by

g

precisely when all positions within each cycle receive the same color. The number of such fixed colorings is

m^{j_{1} (g) + j_{2} (g) + \dots}

, where the exponent is the total number of cycles. This equals the cycle index evaluated at

s_{k} = m

. □

5 Applications: Necklaces and Bracelets

Example 8 (Counting necklaces).

Consider coloring a necklace of

n

beads with

m

colors, where two colorings are equivalent if one is a rotation of the other. The symmetry group is the cyclic group

C_{n}

, with cycle index

Z (C_{n}) = \frac{1}{n} d ∣ n \sum φ (d) s_{d}^{n / d} .

Substituting

s_{k} = m

yields the number of distinct necklaces:

\frac{1}{n} \sum_{d ∣ n} φ (d) m^{n / d}

Example 9 (Counting bracelets).

If we also allow the necklace to be flipped (turned over), the symmetry group becomes the dihedral group

D_{n}

of order

2 n

. When

n

is odd,

Z (D_{n}) = \frac{1}{2} Z (C_{n}) + \frac{1}{2} s_{1} s_{2}^{(n - 1) /2} .

When

n

is even,

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

Substituting

s_{k} = m

gives the number of distinct bracelets.

Combinatorics Discrete Mathematics Textbook Burnside Polya Enumeration

Folio Official

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

1 followers·107 articles

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry

Folio Official

March 1, 2026

1 Group Actions, Orbits, and Stabilizers

Definition 1 (Group action).

A group

G

acts on a set

X

if there is a map

G \times X \to X

(written

(g, x) \mapsto g \cdot x

) satisfying:

$e \cdot x = x$ for all $x \in X$ , where $e$ is the identity element of $G$ ;
$(g h) \cdot x = g \cdot (h \cdot x)$ for all $g, h \in G$ and $x \in X$ .

Definition 2 (Orbit and stabilizer).

The orbit of

x \in X

under

G

G \cdot x = {g \cdot x ∣ g \in G}

. The stabilizer of

x

G_{x} = {g \in G ∣ g \cdot x = x}

Theorem 3 (Orbit–stabilizer theorem).

∣ G \cdot x ∣ = \frac{∣ G ∣}{∣ G _{x} ∣} = [G : G_{x}]

Proof.

The map

g G_{x} \mapsto g \cdot x

is a well-defined bijection from the set of cosets

G / G_{x}

to the orbit

G \cdot x

. Indeed,

g G_{x} = h G_{x}

if and only if

h^{- 1} g \in G_{x}

, which holds if and only if

g \cdot x = h \cdot x

. Surjectivity is immediate. □

Definition 4 (Fixed-point set).

For

g \in G

, the fixed-point set of

g

X^{g} = {x \in X ∣ g \cdot x = x}

2 Burnside's Lemma

Theorem 5 (Burnside's lemma (Cauchy–Frobenius theorem)).

When a finite group

G

acts on a finite set

X

, the number of orbits

∣ X / G ∣

∣ X / G ∣ = \frac{1}{∣ G ∣} g \in G \sum ∣ X^{g} ∣.

Proof.

We count the elements of the set

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

in two ways.

Summing over

g

∣ S ∣ = \sum_{g \in G} ∣ X^{g} ∣

Summing over

x

∣ S ∣ = \sum_{x \in X} ∣ G_{x} ∣

. By the orbit–stabilizer theorem,

∣ G_{x} ∣ = ∣ G ∣/∣ G \cdot x ∣

, so

x \in X \sum ∣ G_{x} ∣ = x \in X \sum \frac{∣ G ∣}{∣ G \cdot x ∣} = ∣ G ∣ x \in X \sum \frac{1}{∣ G \cdot x ∣} .

Each orbit

O

contributes

∣ O ∣

terms of

1/∣ O ∣

each, so each orbit contributes exactly

1

. Hence

\sum_{x \in X} 1/∣ G \cdot x ∣ = ∣ X / G ∣

Equating the two expressions gives

\sum_{g \in G} ∣ X^{g} ∣ = ∣ G ∣ \cdot ∣ X / G ∣

, from which the result follows. □

3 The Cycle Index

Definition 6 (Cycle index).

Let a finite group

G

act on

{1, 2, \dots, n}

. For each

g \in G

, regard

g

as a permutation and let

j_{k} (g)

denote the number of

k

-cycles in its cycle decomposition. The cycle index of

G

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

4 Pólya's Enumeration Theorem

Theorem 7 (P\'olya enumeration theorem).

The number of colorings of

n

positions with

m

colors, up to the symmetry group

G

, is

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

More generally, the weighted generating function is obtained by substituting

Z (G; s_{1} = i \sum w_{i}, s_{2} = i \sum w_{i}^{2}, \dots, s_{k} = i \sum w_{i}^{k}, \dots)

where

w_{1}, \dots, w_{m}

are weights assigned to the colors.

Proof.

By Burnside's lemma, the number of orbits is

\frac{1}{∣ G ∣} \sum_{g \in G} ∣ X^{g} ∣

. If the cycle decomposition of

g

consists of cycles of lengths

c_{1}, c_{2}, \dots

, then a coloring is fixed by

g

precisely when all positions within each cycle receive the same color. The number of such fixed colorings is

m^{j_{1} (g) + j_{2} (g) + \dots}

, where the exponent is the total number of cycles. This equals the cycle index evaluated at

s_{k} = m

. □

5 Applications: Necklaces and Bracelets

Example 8 (Counting necklaces).

Consider coloring a necklace of

n

beads with

m

colors, where two colorings are equivalent if one is a rotation of the other. The symmetry group is the cyclic group

C_{n}

, with cycle index

Z (C_{n}) = \frac{1}{n} d ∣ n \sum φ (d) s_{d}^{n / d} .

Substituting

s_{k} = m

yields the number of distinct necklaces:

\frac{1}{n} \sum_{d ∣ n} φ (d) m^{n / d}

Example 9 (Counting bracelets).

If we also allow the necklace to be flipped (turned over), the symmetry group becomes the dihedral group

D_{n}

of order

2 n

. When

n

is odd,

Z (D_{n}) = \frac{1}{2} Z (C_{n}) + \frac{1}{2} s_{1} s_{2}^{(n - 1) /2} .

When

n

is even,

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

Substituting

s_{k} = m

gives the number of distinct bracelets.

Combinatorics Discrete Mathematics Textbook Burnside Polya Enumeration

Folio Official

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

1 followers·107 articles

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry

1 Group Actions, Orbits, and Stabilizers

2 Burnside's Lemma

3 The Cycle Index

4 Pólya's Enumeration Theorem

5 Applications: Necklaces and Bracelets

Share your expertise with the world

More from Folio Official

Recurrence Relations and Counting: Solving Linear Recurrences

The Inclusion--Exclusion Principle: Counting by Alternating Sums

Combinatorial Designs and Latin Squares: Balanced Arrangements

Combinatorics: A Complete Summary of Definitions, Theorems, and Proofs

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry

1 Group Actions, Orbits, and Stabilizers

2 Burnside's Lemma

3 The Cycle Index

4 Pólya's Enumeration Theorem

5 Applications: Necklaces and Bracelets

Share your expertise with the world

More from Folio Official

Recurrence Relations and Counting: Solving Linear Recurrences

The Inclusion--Exclusion Principle: Counting by Alternating Sums

Combinatorial Designs and Latin Squares: Balanced Arrangements

Combinatorics: A Complete Summary of Definitions, Theorems, and Proofs