Polya Enumeration Theorem

Pólya Enumeration Theorem (PET): counts distinct configurations under a group of symmetries by substituting a generating-function "figure inventory" into the cycle index of the group. One-line statement: the generating function for inequivalent colorings is

Z_{G} (\sum x_{i}, \sum x_{i}^{2}, \dots)

. Applies wherever you must count things up to symmetry (necklaces, graphs, chemical isomers, switching functions). Due to George Pólya (1937), with foundations by J. H. Redfield (1927).

The Pólya Enumeration Theorem is a powerful refinement of Burnside's Lemma that counts equivalence classes of functions (colorings) under a group action, while simultaneously tracking how many objects of each type appear. Its central device is the cycle index $Z_{G}$ , a polynomial in variables $s_{1}, s_{2}, \dots$ that encodes the cycle structure of every permutation in a group $G$ . By substituting power sums of a figure-counting series into the cycle index, PET produces a generating function whose coefficients count distinct configurations refined by content. The surprising fact is that a single polynomial — built only from cycle data — simultaneously solves an entire infinite family of weighted counting problems (e.g., all necklaces of every color-composition at once). It transforms tedious case-by-case symmetry counting into a mechanical algebraic substitution.

The Core Insight

Burnside's Lemma tells you the number of orbits is the average number of fixed colorings. Pólya's leap is to notice that a permutation $g$ fixes a coloring precisely when the coloring is constant on each cycle of $g$ . So a cycle of length $k$ forces $k$ positions to share one color — contributing the power sum $x_{1}^{k} + x_{2}^{k} + \dots$ in a weighted count. Replacing each cycle-index variable $s_{k}$ by this power sum automatically averages over the group with full weight bookkeeping, yielding the complete generating function for orbits in one stroke.

Formal Statement

Group Action, Colorings, and Weight

Let a finite group $G$ act on a finite set $D$ of $n$ positions (the "domain", e.g. beads of a necklace). Let $R$ be a set of colors (the "range"). A coloring is a function $f : D \to R$ . Two colorings $f_{1}, f_{2}$ are equivalent if there exists $g \in G$ with $f_{1} (g \cdot d) = f_{2} (d)$ for all $d \in D$ ; equivalence classes are orbits under the induced action on $R^{D}$ .

Assign each color $r \in R$ a weight $w (r)$ (typically a monomial in formal variables). The weight of a coloring is the product over positions:

W (f) = d \in D \prod w (f (d)) .

⟳weight is multiplicative across positions; equivalent colorings have equal weight since

g

merely permutes the factors of the product.

Cycle Index of a Permutation Group

For $g \in G$ acting on $D$ with $n = ∣ D ∣$ , let $j_{k} (g)$ be the number of cycles of length $k$ in the cycle decomposition of $g$ (so $\sum_{k} k j_{k} (g) = n$ ). The cycle index of $G$ is the polynomial in indeterminates $s_{1}, s_{2}, \dots, s_{n}$ :

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

⟳each

g

contributes one monomial recording its cycle type; the prefactor

1/∣ G ∣

averages over the group, mirroring Burnside's averaging.

Pólya Enumeration Theorem

Let $G$ act on $D$ ( $∣ D ∣ = n$ ) and let $R$ have a weight function $w$ . Define the figure-counting series (the "inventory" of colors) by the power sums

p_{k} = r \in R \sum w (r)^{k} .

⟳

p_{k}

is the value of substituting

w^{k}

into the simple color inventory

\sum_{r} w (r)

; raising to the

k

-th power matches a cycle of length

k

forcing

k

positions equal.

Then the generating function for orbits, weighted by $W$ , is obtained by substituting $s_{k} \mapsto p_{k}$ in the cycle index:

orbits O \sum W (O) = Z_{G} (p_{1}, p_{2}, \dots, p_{n}) = Z_{G} (r \sum w (r), r \sum w (r)^{2}, \dots) .

⟳this is Burnside's Lemma applied to the weighted count, with the fixed-coloring count for

g

factoring over its cycles into

\prod_{k} p_{k}^{j_{k} (g)}

Unweighted corollary. Setting every

w (r) = 1

gives

p_{k} = ∣ R ∣ = m

for all

k

, so the number of inequivalent colorings is

N = Z_{G} (m, m, \dots, m) .

⟳with all weights

1

W (O) = 1

so the left side of [4] simply counts orbits; each

p_{k}

collapses to

m

Why It Holds / Derivation

From Burnside's Lemma to Pólya

We prove [4]. Define the weighted fixed-point sum for each $g \in G$ :

Fix_{w} (g) = f \in R^{D} g \cdot f = f \sum W (f) .

⟳this generalizes the count of fixed colorings to a weighted sum; the unweighted version

∣ Fix (g) ∣

recovers ordinary Burnside.

Step 1 — Weighted Burnside. The weighted Cauchy–Frobenius (Burnside) identity states that summing weights over orbits equals the group-average of weighted fixed points:

orbits O \sum W (O) = \frac{1}{∣ G ∣} g \in G \sum Fix_{w} (g) .

⟳all colorings in an orbit share weight

W (O)

; double-count pairs

(g, f)

with

g \cdot f = f

, using that each orbit's stabilizers have total size

∣ G ∣/∣ O ∣ \cdot ∣ O ∣ = ∣ G ∣

contributions summing per orbit.

Step 2 — A coloring is fixed iff it is constant on cycles. If

g \cdot f = f

, then

f (g^{t} \cdot d) = f (d)

for all

t

, so

f

is constant along each orbit of

⟨ g ⟩

D

— that is, on each cycle of

g

. Conversely any cycle-constant coloring is fixed. Step 3 — Factor the weighted fixed sum over cycles. A fixed coloring chooses one color per cycle. A cycle of length

k

, all

k

positions sharing color

r

, contributes weight

w (r)^{k}

. Summing over the color choice gives factor

\sum_{r} w (r)^{k} = p_{k}

. Since choices on distinct cycles are independent:

Fix_{w} (g) = k = 1 \prod n (r \in R \sum w (r)^{k})^{j_{k} (g)} = k = 1 \prod n p_{k}^{j_{k} (g)} .

⟳independence of cycles makes the weighted fixed sum a product; each length-

k

cycle contributes the

k

-th power sum

p_{k}

, one factor per such cycle.

Step 4 — Assemble. Substitute [8] into [7]:

orbits O \sum W (O) = \frac{1}{∣ G ∣} g \in G \sum k = 1 \prod n p_{k}^{j_{k} (g)} = Z_{G} (p_{1}, \dots, p_{n}) .

⟳the right side is exactly the cycle index [2] with

s_{k}

replaced by

p_{k}

— the substitution in [4].

■

George Pólya | 1887–1985

Hungarian-American mathematician of extraordinary breadth, contributing to probability, combinatorics, number theory, complex analysis, and mathematical pedagogy (How to Solve It, 1945). His 1937 paper "Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen" introduced the cycle-index substitution method, motivated explicitly by counting chemical isomers and graphs. Pólya's work unified scattered enumeration techniques into a single mechanical procedure. Decades later it emerged that J. Howard Redfield had published essentially the same theorem in 1927 in an obscure paper; the result is now often credited as the Redfield–Pólya Theorem. Pólya's name endures largely because of the clarity and reach of his exposition and applications.

Building Intuition

Picture a necklace of $n$ beads you can rotate. A rotation $g$ permutes the bead positions in cycles. If $g$ is a rotation by one step, all $n$ beads form a single $n$ -cycle — and the only colorings unchanged by it are those where every bead is the same color. That's why a length- $n$ cycle contributes $p_{n} = \sum_{r} w (r)^{n}$ : there are $m$ monochromatic choices, each weighted by $w (r)^{n}$ .

The cycle index is a "symmetry fingerprint" of the group: it forgets which positions cycle together and remembers only how many cycles of each length each symmetry produces. Pólya's substitution then injects the color palette ( $p_{k}$ ) into this fingerprint. The genius is that the same $Z_{G}$ answers every coloring problem — change the palette, re-substitute, done. The unweighted formula [5] is just the special case "all colors weigh one," collapsing the inventory to $m$ everywhere.

Rotational symmetry of a 6-bead necklace and its cycle decomposition under rotation by 2 steps

<svg viewBox="0 0 460 300" xmlns="http://www.w3.org/2000/svg">
<rect width="460" height="300" fill="#0a0e17"/>
<text x="230" y="28" fill="#e2e8f0" font-size="16" text-anchor="middle">Necklace C6, rotation by 2 positions</text>
<!-- hexagon beads -->
<g stroke="#94a3b8" stroke-width="2" fill="none">
<circle cx="230" cy="80" r="14" fill="#d4a853"/>
<circle cx="310" cy="125" r="14" fill="#94a3b8"/>
<circle cx="310" cy="215" r="14" fill="#d4a853"/>
<circle cx="230" cy="260" r="14" fill="#94a3b8"/>
<circle cx="150" cy="215" r="14" fill="#d4a853"/>
<circle cx="150" cy="125" r="14" fill="#94a3b8"/>
</g>
<text x="230" y="85" fill="#0a0e17" font-size="13" text-anchor="middle">0</text>
<text x="310" y="130" fill="#0a0e17" font-size="13" text-anchor="middle">1</text>
<text x="310" y="220" fill="#0a0e17" font-size="13" text-anchor="middle">2</text>
<text x="230" y="265" fill="#0a0e17" font-size="13" text-anchor="middle">3</text>
<text x="150" y="220" fill="#0a0e17" font-size="13" text-anchor="middle">4</text>
<text x="150" y="130" fill="#0a0e17" font-size="13" text-anchor="middle">5</text>
<!-- cycle arrows: 0->2->4->0 -->
<g stroke="#d4a853" stroke-width="2" fill="none" marker-end="url(#a)">
<path d="M243,90 Q300,140 305,200"/>
<path d="M300,225 Q230,260 165,225"/>
<path d="M155,200 Q160,140 217,90"/>
</g>
<defs>
<marker id="a" markerWidth="8" markerHeight="8" refX="6" refY="3" orient="auto">
<path d="M0,0 L6,3 L0,6 Z" fill="#d4a853"/>
</marker>
</defs>
<text x="40" y="285" fill="#e2e8f0" font-size="12">Two 3-cycles: (0 2 4)(1 3 5)  →  cycle index term s₃²</text>
</svg>

Worked Examples

Two-color necklaces with 4 beads under rotation

Given.

n = 4

beads in a ring; symmetry group

G = C_{4} = {e, r, r^{2}, r^{3}}

(rotations only). Colors

R = {black, white}

with weights

w (black) = b

w (white) = w

. Step 1 — Cycle types.

$e$ : four fixed points → $s_{1}^{4}$
$r$ (rotate 1): one 4-cycle → $s_{4}$
$r^{2}$ (rotate 2): two 2-cycles → $s_{2}^{2}$
$r^{3}$ (rotate 3): one 4-cycle → $s_{4}$

Step 2 — Cycle index.

Z_{C_{4}} = \frac{1}{4} (s_{1}^{4} + s_{2}^{2} + 2 s_{4}) .

⟳average the four monomials from each group element by [2].

Step 3 — Substitute

s_{k} \mapsto b^{k} + w^{k}

Z_{C_{4}} (b + w, b^{2} + w^{2}, b^{4} + w^{4}) = \frac{1}{4} [(b + w)^{4} + (b^{2} + w^{2})^{2} + 2 (b^{4} + w^{4})] .

⟳replace each

s_{k}

in [10] with the power sum

p_{k} = b^{k} + w^{k}

per [3].

Step 4 — Expand. Computing term by term and dividing by 4:

b^{4} + b^{3} w + 2 b^{2} w^{2} + b w^{3} + w^{4} .

⟳

(b + w)^{4} = b^{4} + 4 b^{3} w + 6 b^{2} w^{2} + 4 b w^{3} + w^{4}

; add

(b^{2} + w^{2})^{2} = b^{4} + 2 b^{2} w^{2} + w^{4}

and

2 (b^{4} + w^{4})

, then divide by 4.

Reading the answer. Coefficients give counts by composition: 1 all-black, 1 with three black, 2 with two of each, 1 with one black, 1 all-white.

Total necklaces = 1 + 1 + 2 + 1 + 1 = 6 (or Z_{C_{4}} (2, 2, 2) = \frac{1}{4} (16 + 4 + 4) = 6) .

Coloring the faces of a cube with 3 colors

Given. Color the 6 faces of a cube with

R = {1, 2, 3}

colors, equivalent under the rotation group of the cube,

∣ G ∣ = 24

. Use unweighted count (

w \equiv 1

, so

p_{k} = 3

). Step 1 — Cycle index of the cube's rotation group acting on faces (standard result):

Z_{G} = \frac{1}{24} (s_{1}^{6} + 6 s_{1}^{2} s_{4} + 3 s_{1}^{2} s_{2}^{2} + 8 s_{3}^{2} + 6 s_{2}^{3}) .

⟳classify the 24 rotations — identity (1), face rotations ±90° (6), face rotations 180° (3), vertex rotations ±120° (8), edge rotations 180° (6) — and record each one's cycle structure on the 6 faces.

Step 2 — Substitute $s_{k} = 3$ :

N = \frac{1}{24} (3^{6} + 6 \cdot 3^{2} \cdot 3 + 3 \cdot 3^{2} \cdot 3^{2} + 8 \cdot 3^{2} + 6 \cdot 3^{3}) .

⟳each

s_{k} \mapsto 3

; e.g.

s_{1}^{6} \to 3^{6}

s_{1}^{2} s_{4} \to 3^{2} \cdot 3 = 3^{3}

s_{3}^{2} \to 3^{2}

Step 3 — Arithmetic.

3^{6} = 729

;

6 \cdot 27 = 162

;

3 \cdot 81 = 243

;

8 \cdot 9 = 72

;

6 \cdot 27 = 162

. Sum

= 729 + 162 + 243 + 72 + 162 = 1368

N = \frac{1368}{24} = 57 distinct 3-colorings of the cube’s faces.

Common Misconceptions

The group acts on the domain (positions), not the colors. The cycle index is built from the action of

G

D

. A frequent error is to permute colors, or to count

∣ D ∣

as the number of group elements. Also: $j_{k} (g)$ counts cycles of length $k$ , not cycles indexed by $k$ — fixed points are 1-cycles contributing to

s_{1}

, and they are easy to miss. Finally, PET requires a group action (closure, inverses, identity); applying it to a set of symmetries that is not closed under composition gives nonsense. Naïve division by group size fails. One might guess the number of 2-colorings of

n = 4

beads is "total colorings / group size"

= 2^{4} /4 = 4

. But the correct answer from [12] is 6. The simple division ignores colorings with nontrivial stabilizers (e.g. the all-black coloring is fixed by all rotations, so it must not be divided away). PET (via Burnside's averaging) correctly handles these symmetric colorings; plain division by

∣ G ∣

only works when the action on colorings is free, which is rarely the case.

Connections

PET sits atop a tower of related counting tools. It is a weighted, refined generalization of Burnside's Lemma (the Cauchy–Frobenius orbit-counting lemma), which it reduces to when all weights are set to 1. The cycle index is a central object in Symmetric Functions theory — substituting power-sum symmetric functions $p_{k}$ links PET directly to the power-sum basis of the ring of symmetric functions. The unweighted formula is an instance of the broader orbit-counting problem studied in Group Theory and Group Actions. For counting labeled vs. unlabeled structures, PET interfaces with exponential and ordinary Generating Functions, and de Bruijn's generalization extends it to symmetries acting on both domain and range.

Real-World Applications

Chemical isomer counting (Pólya's original motivation): enumerate distinct substituted molecules, e.g. the number of distinct dichlorobenzenes or alcohols $C_{n} H_{2 n + 1} O H$ , accounting for molecular symmetry.
Graph enumeration: count non-isomorphic graphs on $n$ vertices by applying PET with the symmetric group $S_{n}$ acting on the $(2 n)$ possible edges.
Necklace and bracelet combinatorics: count distinct circular arrangements of colored beads under rotation ( $C_{n}$ ) and reflection (dihedral $D_{n}$ ), foundational in combinatorics and music theory (counting distinct chords/scales under transposition).
Boolean/switching function enumeration: count distinct logic circuits or Boolean functions invariant under permutation of input variables, used in digital design and complexity theory.
Crystallography and tiling: enumerate distinct colorings of lattice patterns and tilings under symmetry groups of the plane or crystal.
Phylogenetics & combinatorial chemistry libraries: count distinct molecular scaffolds or labeled tree structures up to symmetry.
Coding theory: count equivalence classes of codewords under coordinate permutations and symbol relabelings.

Historical Development

1845: Cauchy establishes results on the average number of fixed points of permutations, an early form of orbit counting.
1887: Frobenius formalizes the orbit-counting lemma; the result is later misattributed to Burnside.
1897: Burnside includes the orbit-counting lemma in his text on finite groups; it becomes known (mistakenly) as "Burnside's Lemma."
1927: J. Howard Redfield publishes "The Theory of Group-Reduced Distributions," containing the cycle-index enumeration theorem — overlooked for decades.
1937: George Pólya publishes his landmark paper applying the cycle-index method to graphs, trees, and chemical compounds, giving the theorem wide visibility.
1948: Pólya's results spread through chemistry and combinatorics literature; isomer-counting becomes a showcase application.
1959: N. G. de Bruijn generalizes PET to permutation groups acting on both domain and range, vastly broadening its scope.
1960: Frank Harary rediscovers Redfield's 1927 paper, prompting the modern dual attribution Redfield–Pólya Theorem.
1973–87: Harary, Palmer, and others systematize graphical enumeration via cycle indices in standard combinatorics texts.

Subtleties & Limits

PET reduces counting to computing cycle indices, but obtaining $Z_{G}$ for complex groups can itself be hard. For the symmetric group $S_{n}$ , the cycle index involves a sum over all integer partitions of $n$ — explosive growth — and counting non-isomorphic graphs, though solved in principle by PET, has no known simple closed form for the count $g_{n}$ (its asymptotics involve $2^{(2 n)} / n!$ as a leading term). PET also assumes finite $D$ and $R$ and a fixed group action; problems where symmetries act jointly on positions and colors, or where the structure is dynamic, require de Bruijn's extension or further machinery. Determining cycle indices for automorphism groups of arbitrary structures is closely tied to the graph isomorphism problem, whose precise complexity remains a celebrated open question.