Polya Enumeration Theorem

⚡ Key Takeaways

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 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 + \cdots$ 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.

DefinitionGroup 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:

1

\quad W(f) = \prod_{d \in D} w\bigl(f(d)\bigr).

Derivation hint: weight is multiplicative across positions; equivalent colorings have equal weight since $g$ merely permutes the factors of the product.

DefinitionCycle 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$ :

2

\quad Z_G(s_1, s_2, \dots, s_n) = \frac{1}{|G|} \sum_{g \in G} \prod_{k=1}^{n} s_k^{\,j_k(g)}.

Derivation hint: each $g$ contributes one monomial recording its cycle type; the prefactor $1/|G|$ averages over the group, mirroring Burnside's averaging.

TheoremPó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

3

\quad p_k = \sum_{r \in R} w(r)^k.

Derivation hint: $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:

4

\quad \sum_{\text{orbits } O} W(O) = Z_G(p_1, p_2, \dots, p_n) = Z_G\!\left(\sum_r w(r),\ \sum_r w(r)^2,\ \dots\right).

Derivation hint: 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

5

\quad N = Z_G(m, m, \dots, m).

Derivation hint: with all weights $1$ , $W(O)=1$ so the left side of [4] simply counts orbits; each $p_k$ collapses to $m$ .

ProofFrom Burnside's Lemma to Pólya

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

6

\quad \mathrm{Fix}_w(g) = \sum_{\substack{f \in R^D \\ g \cdot f = f}} W(f).

Derivation hint: this generalizes the count of fixed colorings to a weighted sum; the unweighted version $|\mathrm{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:

7

\quad \sum_{\text{orbits } O} W(O) = \frac{1}{|G|} \sum_{g \in G} \mathrm{Fix}_w(g).

Derivation hint: 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 $\langle g \rangle$ on $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:

8

\quad \mathrm{Fix}_w(g) = \prod_{k=1}^{n} \left(\sum_{r \in R} w(r)^k\right)^{j_k(g)} = \prod_{k=1}^{n} p_k^{\,j_k(g)}.

Derivation hint: 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]:

9

\quad \sum_{\text{orbits } O} W(O) = \frac{1}{|G|}\sum_{g \in G} \prod_{k=1}^{n} p_k^{\,j_k(g)} = Z_G(p_1, \dots, p_n).

Derivation hint: the right side is exactly the cycle index [2] with $s_k$ replaced by $p_k$ — the substitution in [4]. $\blacksquare$

∎

mathematician · 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.

🧠 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.

Figure

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

```svg

```

ExampleTwo-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 = \{\text{black}, \text{white}\}$ with weights $w(\text{black}) = b$ , $w(\text{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.

10

\quad Z_{C_4} = \tfrac{1}{4}\bigl(s_1^4 + s_2^2 + 2 s_4\bigr).

Derivation hint: average the four monomials from each group element by [2].

Step 3 — Substitute $s_k \mapsto b^k + w^k$ :

11

\quad Z_{C_4}(b{+}w,\ b^2{+}w^2,\ b^4{+}w^4) = \tfrac14\!\left[(b{+}w)^4 + (b^2{+}w^2)^2 + 2(b^4{+}w^4)\right].

Derivation hint: 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:

12

\quad b^4 + b^3 w + 2\,b^2 w^2 + b\,w^3 + w^4.

Derivation hint: $(b{+}w)^4 = b^4{+}4b^3w{+}6b^2w^2{+}4bw^3{+}w^4$ ; add $(b^2{+}w^2)^2 = b^4{+}2b^2w^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.

\boxed{\text{Total necklaces} = 1+1+2+1+1 = 6 \text{ (or } Z_{C_4}(2,2,2)=\tfrac14(16+4+4)=6).}

ExampleColoring 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):

13

\quad Z_G = \tfrac{1}{24}\bigl(s_1^6 + 6\,s_1^2 s_4 + 3\,s_1^2 s_2^2 + 8\,s_3^2 + 6\,s_2^3\bigr).

Derivation hint: 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$ :

14

\quad N = \tfrac{1}{24}\bigl(3^6 + 6\cdot 3^{2}\cdot 3 + 3\cdot 3^{2}\cdot 3^{2} + 8\cdot 3^{2} + 6\cdot 3^{3}\bigr).

Derivation hint: 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$ .

\boxed{N = \dfrac{1368}{24} = 57 \text{ distinct 3-colorings of the cube's faces.}}

⚠️ Common mistake

The group acts on the domain (positions), not the colors. The cycle index is built from the action of $G$ on $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.

Counterexample

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.

connection

PET sits atop a tower of related counting tools. It is a weighted, refined generalization of <span class="wiki-link-missing">Burnside's Lemma</span> (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 <a class="wiki-link" href="/wiki/generating-functions">Generating Functions</a>, and de Bruijn's generalization extends it to symmetries acting on both domain and range.

🔬 Where this appears

⏳ History

- 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.

open-problem

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^{\binom{n}{2}}/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.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also