Introduction to Polya Enumeration

How many genuinely different ways are there to color the six faces of a cube using three colors? We agree that two colorings are "the same" whenever one can be rotated into the other. A naive count of 36=7293^6 = 729 colorings wildly overcounts. This is because rotating the cube produces many colorings we would call identical. This is the central question of counting under symmetry. It appears whenever a finite group acts on a finite set of configurations. Examples include necklaces under rotation, molecules under spatial symmetry, switching networks. It also includes graphs on labeled vertices considered up to relabeling. The idea that resolves this is deceptively simple. Instead of counting configurations directly, count how many configurations each symmetry fixes. Then average over the group. This averaging principle is Burnside's Lemma (also called the Cauchy–Frobenius lemma). It converts an intractable-looking counting problem into a sum of much simpler fixed-point counts. When the configurations are functions from a set of positions to a set of colors, the fixed-point counts have a beautiful structure. This structure is controlled entirely by the cycle type of each permutation. It is encoded compactly in a single polynomial: the cycle index of the group. Pólya enumeration takes this one step further. Rather than merely counting equivalence classes of colorings, it produces a full generating function. This function tracks how many times each color is used. It simultaneously handles all weighted counting questions at once. This upgrade from Burnside's raw counting to a weighted generating function is the Pólya Enumeration Theorem. It was also independently found by de Bruijn. It is one of the crown jewels of enumerative combinatorics. It unifies group theory, generating functions, and combinatorial counting. This article builds the theory from the ground up. It states and proves Burnside's Lemma. It introduces the cycle index polynomial of a permutation group. It proves the Pólya Enumeration Theorem itself. Along the way we compute the cycle index of the cyclic and dihedral groups. We count necklaces and cube colorings by hand. We highlight exactly where the machinery needs each of its hypotheses.

Key takeaways
  • Configurations related by a symmetry group should be counted once per equivalence class, not once per raw configuration.
  • Burnside's Lemma: the number of orbits equals the average number of fixed points of the group elements.
  • The cycle index ZG(x1,…,xn)=1∣G∣∑g∈G∏ixici(g)Z_G(x_1,\dots,x_n) = \frac{1}{|G|}\sum_{g\in G} \prod_i x_i^{c_i(g)} packages the cycle-type data of every group element into one polynomial.
  • Pólya's Theorem substitutes a generating function for colors into the cycle index to produce the full weighted count of colorings, all at once.
  • The theorem specializes both to plain orbit-counting (Burnside) and to counting by exact color multiset (via coefficient extraction).
  • Key idea: average fixed-point counts over a symmetry group, and track color-usage by substituting power sums of a generating function into the group's cycle index.

Where this lives today

Pólya enumeration is the standard tool for counting combinatorial structures up to symmetry, and it appears across many fields. In chemistry, it counts distinct isomers of molecules (e.g. substituted benzene rings, or alkanes) where atoms occupying symmetric positions can be swapped by the molecule's point-group symmetries — Pólya's original motivation. In graph theory, it counts non-isomorphic labeled structures such as graphs on nn vertices up to relabeling, colorings of graph vertices/edges up to automorphism, and necklaces/bracelets (related to counting binary strings up to rotation and reflection, connecting to The Twelvefold Way and to counting formulas involving Stirling Numbers of the First Kind when cycle-index computations of the symmetric group arise). In computer science, it underlies counting distinct Boolean functions up to variable permutation (switching theory, circuit enumeration), counting distinct states in combinatorial games with board symmetries (e.g. tic-tac-toe boards up to the dihedral group of order 8), and hashing/canonicalization schemes that must respect symmetry classes. In statistics and design theory, cycle-index methods count non-isomorphic block designs and combinatorial designs under relabeling of treatments. In physics, closely related cycle-index and generating-function techniques appear in statistical mechanics partition function computations for systems with symmetric configurations (e.g. counting distinguishable spin configurations on symmetric lattices). The theorem's core mechanism — replace each formal variable in a symmetric function by a power sum of a generating variable — also foreshadows deeper connections to symmetric function theory and representation theory of the symmetric group, areas built directly on the Permutations and cycle-type ideas introduced here.

Ask the tutor: Can you walk me through computing the cycle index for coloring the edges (not faces) of a cube under rotation?

DefinitionGroup action, orbits, cycle index, and colorings

Let GG be a finite group acting on a finite set XX. For g∈Gg \in G, write g⋅xg\cdot x for the action of gg on x∈Xx \in X.

  • The orbit of x∈Xx \in X is Orb(x)={g⋅x:g∈G}\mathrm{Orb}(x) = \{g \cdot x : g \in G\}. Orbits partition XX.
  • The fixed-point set of g∈Gg \in G is Xg={x∈X:g⋅x=x}X^g = \{x \in X : g \cdot x = x\}, and ∣Xg∣|X^g| is the number of points fixed by gg.
  • Now let GG act on a finite set DD (the "positions," e.g. beads on a necklace, faces of a cube), acting by permutations. Let RR be a finite set of "colors." The set of colorings is RDR^D, the set of functions f:D→Rf : D \to R, and GG acts on RDR^D by
(g⋅f)(d)=f(g−1⋅d),d∈D.(g \cdot f)(d) = f(g^{-1} \cdot d), \qquad d \in D.

Two colorings are considered equivalent iff they lie in the same GG-orbit.

  • For g∈Gg \in G acting on DD with ∣D∣=n|D| = n, write the disjoint cycle decomposition of gg (as a permutation of DD) and let ci(g)c_i(g) denote the number of cycles of length ii, so ∑i=1ni ci(g)=n\sum_{i=1}^n i\, c_i(g) = n.
  • The cycle index of GG (acting on DD, ∣D∣=n|D|=n) is the polynomial in indeterminates x1,…,xnx_1,\dots,x_n defined by
ZG(x1,…,xn)  =  1∣G∣∑g∈G∏i=1nxi ci(g).Z_G(x_1,\dots,x_n) \;=\; \frac{1}{|G|}\sum_{g \in G} \prod_{i=1}^n x_i^{\,c_i(g)}.

Intuition

Picture a square with four corners, and the group GG of its four rotations (by 0∘,90∘,180∘,270∘0^\circ, 90^\circ, 180^\circ, 270^\circ) acting on the corners. If we 2-color the corners, the raw count of colorings is 24=162^4 = 16, but many of these are rotations of each other. Burnside's insight is that we don't need to explicitly find the orbits and count them — we only need to know, for each single rotation, how many colorings that rotation leaves unchanged, and then average. A rotation fixes a coloring exactly when the coloring is constant on each of the rotation's cycles (as a permutation of the corners). The identity has 4 cycles of length 1 (fixes all 16 colorings); the 90∘90^\circ and 270∘270^\circ rotations are single 4-cycles (fix colorings constant on all 4 corners: 22 colorings each); the 180∘180^\circ rotation is two 2-cycles (fixes colorings constant on each pair: 22=42^2=4 colorings). Averaging: (16+2+4+2)/4=24/4=6(16+2+4+2)/4 = 24/4 = 6 genuinely different colorings. The cycle index packages exactly this cycle-count data — for every group element, record its cycle type as a monomial, then average the monomials. Substituting xi↦(number of colors)x_i \mapsto (\text{number of colors}) recovers Burnside's count; substituting a full generating function for colors gives the finer weighted count that is Pólya's theorem.

Figure
Fixed colorings of a square under its four rotations; each rotation's cycle structure controls which colorings it fixes
e (0°): 1⁴ fixes 2⁴ = 16 r (90°): 4¹ fixes 2¹ = 2 r² (180°): 2² fixes 2² = 4 r³ (270°): 4¹ fixes 2¹ = 2 average = (16+2+4+2)/4 = 6 orbits
TheoremBurnside's Lemma (Cauchy–Frobenius)

Let GG be a finite group acting on a finite set XX. Let X/GX/G denote the set of orbits. Then

∣X/G∣  =  1∣G∣∑g∈G∣Xg∣.|X/G| \;=\; \frac{1}{|G|} \sum_{g \in G} |X^g|.
Proof

We use the technique of double counting: we count the set

S={(g,x)∈G×X:g⋅x=x}S = \{(g,x) \in G \times X : g \cdot x = x\}

in two different ways.

Counting by gg. For a fixed g∈Gg \in G, the number of pairs (g,x)∈S(g,x) \in S with that gg is exactly ∣Xg∣|X^g|, the number of points fixed by gg. Hence

∣S∣=∑g∈G∣Xg∣.|S| = \sum_{g \in G} |X^g|.

Counting by xx. For a fixed x∈Xx \in X, the set of g∈Gg \in G with g⋅x=xg \cdot x = x is the stabilizer Gx={g∈G:g⋅x=x}G_x = \{g \in G : g\cdot x = x\}, which is a subgroup of GG (closed under the group operation and inverses, since g⋅x=xg\cdot x = x and h⋅x=xh \cdot x = x imply (gh)⋅x=g⋅(h⋅x)=g⋅x=x(gh)\cdot x = g\cdot(h\cdot x) = g \cdot x = x, and applying g−1g^{-1} to g⋅x=xg\cdot x=x gives x=g−1⋅xx = g^{-1}\cdot x). Hence

∣S∣=∑x∈X∣Gx∣.|S| = \sum_{x \in X} |G_x|.

By the Orbit–Stabilizer Theorem, for each x∈Xx \in X the map gGx↦g⋅xgG_x \mapsto g \cdot x is a well-defined bijection from the set of left cosets of GxG_x in GG to Orb(x)\mathrm{Orb}(x). (Well-defined and injective: g⋅x=h⋅x  ⟺  h−1g∈Gx  ⟺  gGx=hGxg\cdot x = h \cdot x \iff h^{-1}g \in G_x \iff gG_x = hG_x. Surjective onto the orbit by definition of orbit.) By Lagrange's theorem, the number of cosets of GxG_x is ∣G∣/∣Gx∣|G|/|G_x|, so

∣Orb(x)∣=∣G∣∣Gx∣,i.e.∣Gx∣=∣G∣∣Orb(x)∣.|\mathrm{Orb}(x)| = \frac{|G|}{|G_x|}, \qquad \text{i.e.} \qquad |G_x| = \frac{|G|}{|\mathrm{Orb}(x)|}.

Substituting,

∣S∣=∑x∈X∣G∣∣Orb(x)∣.|S| = \sum_{x \in X} \frac{|G|}{|\mathrm{Orb}(x)|}.

Group this sum by orbit. Fix an orbit O∈X/GO \in X/G; every x∈Ox \in O contributes the same term ∣G∣/∣O∣|G|/|O| to the sum, and there are ∣O∣|O| such xx, so the orbit OO contributes exactly ∣O∣⋅∣G∣∣O∣=∣G∣|O| \cdot \frac{|G|}{|O|} = |G| to the total. Summing over all orbits,

∣S∣=∑O∈X/G∣G∣=∣G∣⋅∣X/G∣.|S| = \sum_{O \in X/G} |G| = |G| \cdot |X/G|.

Equating the two expressions for ∣S∣|S|:

∑g∈G∣Xg∣=∣G∣⋅∣X/G∣,\sum_{g \in G} |X^g| = |G| \cdot |X/G|,

and dividing by ∣G∣|G| (nonzero since GG is a group, hence nonempty) gives the claimed formula. ■\blacksquare

∎
LemmaCycle-counting formula for fixed colorings

Let GG act on a finite set DD with ∣D∣=n|D| = n by permutations, and let GG act on RDR^D as in the Definition, where ∣R∣=m|R| = m. For g∈Gg \in G, let c(g)c(g) denote the total number of cycles in the disjoint cycle decomposition of gg as a permutation of DD (cycles of every length, including fixed points as 11-cycles). Then

∣(RD)g∣=mc(g).|(R^D)^g| = m^{c(g)}.
Proof

A coloring f∈RDf \in R^D satisfies g⋅f=fg \cdot f = f iff f(g−1⋅d)=f(d)f(g^{-1}\cdot d) = f(d) for all d∈Dd \in D, equivalently (replacing dd by g⋅dg \cdot d) f(d)=f(g⋅d)f(d) = f(g\cdot d) for all dd. Iterating, ff must be constant along every cycle of gg: if d,g⋅d,g2⋅d,…d, g\cdot d, g^2 \cdot d, \dots is a cycle, then ff takes the same value on every element of that cycle. Conversely, if ff is constant on each cycle of gg, then trivially f(d)=f(g⋅d)f(d) = f(g \cdot d) for all dd, so g⋅f=fg \cdot f = f. Thus gg-fixed colorings correspond bijectively to functions from the set of cycles of gg to RR: choose a color independently for each cycle. Since gg has c(g)c(g) cycles and ∣R∣=m|R|=m, there are exactly mc(g)m^{c(g)} such choices. ■\blacksquare

∎
TheoremPólya Enumeration Theorem

Let GG be a finite group acting on a finite set DD of positions, ∣D∣=n|D| = n, with cycle index

ZG(x1,…,xn)=1∣G∣∑g∈G∏i=1nxici(g).Z_G(x_1,\dots,x_n) = \frac{1}{|G|}\sum_{g\in G}\prod_{i=1}^n x_i^{c_i(g)}.

Let RR be a set of colors, and to each color r∈Rr \in R assign a formal weight w(r)w(r) lying in a commutative ring of formal power series (e.g. polynomials in variables y1,…,yky_1,\dots,y_k, or a single variable yy if colors are unweighted by type). Define the color generating function

C(y)=∑r∈Rw(r).C(y) = \sum_{r \in R} w(r).

Extend the weight to colorings f∈RDf \in R^D multiplicatively: W(f)=∏d∈Dw(f(d))W(f) = \prod_{d \in D} w(f(d)). Then the generating function for GG-orbits of colorings, weighted by total color content, is

∑[f]∈RD/GW(f)  =  ZG(C(y), C(y2), C(y3),…),\sum_{[f] \in R^D/G} W(f) \;=\; Z_G\big(C(y),\, C(y^2),\, C(y^3), \dots\big),

meaning: substitute xi=C(yi)=∑rw(r)ix_i = C(y^i) = \sum_{r} w(r)^i into the cycle index, for each i=1,…,ni = 1,\dots,n. In particular, if every color has weight 11 (unweighted counting), then C(yi)=∣R∣=mC(y^i) = |R| = m for every ii, and the theorem reduces to

∣RD/G∣=ZG(m,m,…,m),|R^D/G| = Z_G(m,m,\dots,m),

which recovers the count of orbits via Burnside's Lemma applied to X=RDX = R^D.

Proof

We first establish that the weighted orbit sum equals the weighted sum of fixed colorings, averaged over GG; this is a weighted refinement of Burnside's Lemma, proved by the identical double-counting technique.

Step 1 (weighted Burnside). For a GG-orbit O⊆RDO \subseteq R^D, all colorings f∈Of \in O have the same weight W(f)W(f): if f′=g⋅ff' = g\cdot f for some g∈Gg \in G, then

W(f′)=∏d∈Dw(f′(d))=∏d∈Dw(f(g−1⋅d))=∏d′∈Dw(f(d′))=W(f),W(f') = \prod_{d\in D} w(f'(d)) = \prod_{d \in D} w\big(f(g^{-1}\cdot d)\big) = \prod_{d' \in D} w(f(d'))= W(f),

where the last equality is a re-indexing of the product over d′=g−1⋅dd' = g^{-1}\cdot d, which is a bijection D→DD \to D. So WW is constant on orbits; call this common value W(O)W(O). Now consider the sum

T=∑g∈G∑f∈(RD)gW(f).T = \sum_{g \in G} \sum_{f \in (R^D)^g} W(f).

Group the inner sum by orbit: exactly as in the proof of Burnside's Lemma, for fixed ff, the number of g∈Gg \in G fixing ff is ∣Gf∣=∣G∣/∣Orb(f)∣|G_f| = |G|/|\mathrm{Orb}(f)|. So

T=∑f∈RD∣Gf∣ W(f)=∑f∈RD∣G∣∣Orb(f)∣W(f).T = \sum_{f \in R^D} |G_f|\, W(f) = \sum_{f\in R^D} \frac{|G|}{|\mathrm{Orb}(f)|} W(f).

Grouping by orbit OO: each f∈Of \in O contributes ∣G∣∣O∣W(O)\frac{|G|}{|O|}W(O), and there are ∣O∣|O| such ff, contributing ∣G∣⋅W(O)|G|\cdot W(O) per orbit. Hence

T=∣G∣∑O∈RD/GW(O)=∣G∣∑[f]∈RD/GW(f).T = |G| \sum_{O \in R^D/G} W(O) = |G| \sum_{[f]\in R^D/G} W(f).

Therefore

∑[f]∈RD/GW(f)=1∣G∣∑g∈G∑f∈(RD)gW(f)=1∣G∣∑g∈G(∑f∈(RD)gW(f)).\sum_{[f] \in R^D/G} W(f) = \frac{1}{|G|} \sum_{g\in G} \sum_{f \in (R^D)^g} W(f) = \frac{1}{|G|}\sum_{g \in G} \left(\sum_{f \in (R^D)^g} W(f)\right).

Step 2 (evaluating the inner sum via cycle structure). Fix g∈Gg \in G and recall from the proof of the Lemma above that ff is gg-fixed iff ff is constant on each cycle of gg. So gg-fixed colorings correspond to a free choice of color for each cycle of gg. If gg has cycles γ1,…,γc(g)\gamma_1,\dots,\gamma_{c(g)} of lengths ℓ1,…,ℓc(g)\ell_1,\dots,\ell_{c(g)}, then a gg-fixed coloring ff assigns a color rj∈Rr_j \in R to every position in cycle γj\gamma_j, and

W(f)=∏j=1c(g)∏d∈γjw(rj)=∏j=1c(g)w(rj)ℓj.W(f) = \prod_{j=1}^{c(g)} \prod_{d \in \gamma_j} w(r_j) = \prod_{j=1}^{c(g)} w(r_j)^{\ell_j}.

Summing over all choices of (r1,…,rc(g))∈Rc(g)(r_1,\dots,r_{c(g)}) \in R^{c(g)}, the sum factors across cycles (since each rjr_j ranges independently over RR):

∑f∈(RD)gW(f)=∏j=1c(g)(∑r∈Rw(r)ℓj)=∏j=1c(g)C(yℓj),\sum_{f \in (R^D)^g} W(f) = \prod_{j=1}^{c(g)} \left(\sum_{r \in R} w(r)^{\ell_j}\right) = \prod_{j=1}^{c(g)} C(y^{\ell_j}),

using the definition C(yℓ)=∑rw(r)ℓC(y^\ell) = \sum_r w(r)^\ell. Since gg has exactly ci(g)c_i(g) cycles of length ii for each i=1,…,ni=1,\dots,n, we can regroup this product by cycle length:

∑f∈(RD)gW(f)=∏i=1nC(yi)ci(g).\sum_{f\in (R^D)^g} W(f) = \prod_{i=1}^n C(y^i)^{c_i(g)}.

Step 3 (assemble). Substituting into Step 1,

∑[f]∈RD/GW(f)=1∣G∣∑g∈G∏i=1nC(yi)ci(g)=ZG(C(y),C(y2),…,C(yn)),\sum_{[f]\in R^D/G} W(f) = \frac{1}{|G|}\sum_{g \in G} \prod_{i=1}^n C(y^i)^{c_i(g)} = Z_G\big(C(y), C(y^2), \dots, C(y^n)\big),

which is precisely the cycle index polynomial with each formal variable xix_i replaced by C(yi)C(y^i) — since ZGZ_G is by definition 1∣G∣∑g∏ixici(g)\frac{1}{|G|}\sum_g \prod_i x_i^{c_i(g)}. This proves the general formula.

Step 4 (unweighted specialization). If w(r)=1w(r) = 1 for every r∈Rr \in R (i.e. we only care whether colorings are distinguishable, with a trivial one-variable weight y0=1y^0=1, or equivalently we simply set y=1y=1 from the start and read C≡∣R∣=mC \equiv |R|=m), then C(yi)=∑r∈R1=mC(y^i) = \sum_{r\in R} 1 = m for every ii, independent of ii. So the formula becomes ZG(m,m,…,m)Z_G(m,m,\dots,m), and W(f)=1W(f) = 1 for every ff, so the left side is just ∣RD/G∣|R^D/G|, the number of orbits — matching Burnside's Lemma applied with X=RDX = R^D, since ∣Xg∣=mc(g)|X^g| = m^{c(g)} by the Lemma above and 1∣G∣∑gmc(g)=1∣G∣∑g∏imci(g)=ZG(m,…,m)\frac{1}{|G|}\sum_g m^{c(g)} = \frac1{|G|}\sum_g \prod_i m^{c_i(g)} = Z_G(m,\dots,m). ■\blacksquare

∎

Worked examples

Example 1: Necklaces with two colors of unequal weight, cyclic group of length 6. Consider a necklace of n=6n = 6 beads arranged in a circle, and let G=C6={e,r,r2,r3,r4,r5}G = C_6 = \{e, r, r^2, r^3, r^4, r^5\}, the cyclic group of rotations, act on the 66 bead-positions. We want to count necklaces with beads colored Red or Blue, and specifically we want the generating function tracking the number of Red beads used — this distinguishes it from plain Burnside counting. First we need the cycle index of C6C_6 acting on 66 points by rotation. The rotation rkr^k (rotating by kk positions, k=0,…,5k=0,\dots,5) decomposes into gcd⁡(k,6)\gcd(k,6) cycles, each of length 6/gcd⁡(k,6)6/\gcd(k,6). Compute gcd⁡(k,6)\gcd(k,6) for each kk:

  • k=0k=0 (ee): gcd⁡=6\gcd=6, so 66 cycles of length 11: type x16x_1^6.
  • k=1k=1: gcd⁡=1\gcd=1, one cycle of length 66: type x61x_6^1.
  • k=2k=2: gcd⁡=2\gcd=2, two cycles of length 33: type x32x_3^2.
  • k=3k=3: gcd⁡=3\gcd=3, three cycles of length 22: type x23x_2^3.
  • k=4k=4: gcd⁡=2\gcd=2, two cycles of length 33: type x32x_3^2.
  • k=5k=5: gcd⁡=1\gcd=1, one cycle of length 66: type x61x_6^1.

So

ZC6(x1,…,x6)=16(x16+2x6+2x32+x23).Z_{C_6}(x_1,\dots,x_6) = \frac{1}{6}\Big(x_1^6 + 2x_6 + 2x_3^2 + x_2^3\Big).

Now assign weight yy to Red and weight 11 to Blue, so C(y)=y+1C(y) = y + 1, and in general C(yi)=yi+1C(y^i) = y^i + 1. By the Pólya Enumeration Theorem,

∑[f]W(f)=ZC6(C(y),C(y2),C(y3),C(y6))=16[(y+1)6+2(y6+1)+2(y3+1)2+(y2+1)3].\sum_{[f]} W(f) = Z_{C_6}(C(y), C(y^2), C(y^3), C(y^6)) = \frac{1}{6}\Big[(y+1)^6 + 2(y^6+1) + 2(y^3+1)^2 + (y^2+1)^3\Big].

Let us expand each term. (y+1)6=y6+6y5+15y4+20y3+15y2+6y+1.(y+1)^6 = y^6+6y^5+15y^4+20y^3+15y^2+6y+1. 2(y6+1)=2y6+2.2(y^6+1) = 2y^6 + 2. (y3+1)2=y6+2y3+1(y^3+1)^2 = y^6 + 2y^3 + 1, so 2(y3+1)2=2y6+4y3+2.2(y^3+1)^2 = 2y^6 + 4y^3+2. (y2+1)3=y6+3y4+3y2+1.(y^2+1)^3 = y^6+3y^4+3y^2+1. Sum all four:

y6-terms: 1+2+2+1=6  ⟹  6y6.y^6\text{-terms: } 1+2+2+1 = 6 \implies 6y^6.
y5-terms: 6  ⟹  6y5.y^5\text{-terms: } 6 \implies 6y^5.
y4-terms: 15+3=18  ⟹  18y4.y^4\text{-terms: } 15 + 3 = 18 \implies 18y^4.
y3-terms: 20+4=24  ⟹  24y3.y^3\text{-terms: } 20 + 4 = 24 \implies 24y^3.
y2-terms: 15+3=18  ⟹  18y2.y^2\text{-terms: } 15 + 3 = 18 \implies 18y^2.
y1-terms: 6  ⟹  6y.y^1\text{-terms: } 6 \implies 6y.
y0-terms: 1+2+2+1=6  ⟹  6.y^0\text{-terms: } 1+2+2+1=6 \implies 6.

So the bracket totals 6y6+6y5+18y4+24y3+18y2+6y+66y^6+6y^5+18y^4+24y^3+18y^2+6y+6, and dividing by 66:

∑[f]W(f)=y6+y5+3y4+4y3+3y2+y+1.\sum_{[f]} W(f) = y^6+y^5+3y^4+4y^3+3y^2+y+1.

Interpretation. The coefficient of yky^k is the number of distinct necklaces (up to rotation) with exactly kk Red beads and 6−k6-k Blue beads. So: 11 necklace with 66 Red, 11 with 55 Red, 33 with 44 Red, 44 with 33 Red, 33 with 22 Red, 11 with 11 Red, 11 with 00 Red. As a check, the total number of necklaces (setting y=1y=1, i.e. plain Burnside with m=2m=2 colors) is 1+1+3+4+3+1+1=141+1+3+4+3+1+1 = 14, matching ZC6(2,2,2,2,2,2)=16(64+2⋅2+2⋅4+8)=16(64+4+8+8)=846=14Z_{C_6}(2,2,2,2,2,2) = \frac16(64+2\cdot 2+2\cdot 4+8) = \frac16(64+4+8+8)=\frac{84}{6}=14. Also, as a sanity check on total beads, ∑k(6k)=64\sum_k \binom{6}{k} = 64 raw 2-colorings, and indeed ∑k(orbit count for k)⋅(orbit size divides 6)\sum_k(\text{orbit count for }k)\cdot(\text{orbit size divides }6) is consistent with Burnside's total.

Example 2: Cube face colorings with three colors, rotation group. Let DD be the 66 faces of a cube, and let GG be the rotation group of the cube, ∣G∣=24|G|=24, acting on faces. We compute the cycle index of this action and then count 33-colorings up to rotation (the motivating question from the overview), plus the weighted refinement tracking how many faces get each of the three colors. The rotation group of the cube consists of the following conjugacy classes, acting on the 66 faces:

  • Identity: 11 element, cycle type on faces: six 11-cycles ⇒x16\Rightarrow x_1^6.
  • Face-axis rotations by 90∘90^\circ or 270∘270^\circ (through centers of opposite faces): there are 33 axes × 2\times\ 2 nontrivial quarter-turns =6= 6 elements. Each such rotation fixes the 22 faces on its axis (two 11-cycles) and cycles the remaining 44 side faces in one 44-cycle: type x12x4x_1^2 x_4.
  • Face-axis rotations by 180∘180^\circ: 33 elements (one per axis). Each fixes the 22 axis faces and swaps the 44 side faces in two 22-cycles: type x12x22x_1^2 x_2^2.
  • Vertex-axis rotations by 120∘120^\circ or 240∘240^\circ (through opposite vertices): there are 44 axes × 2\times\ 2 nontrivial rotations =8=8 elements. Each such rotation permutes all 66 faces in two 33-cycles (the three faces around each of the two vertices on the axis): type x32x_3^2.
  • Edge-axis rotations by 180∘180^\circ (through midpoints of opposite edges): there are 66 axes, 11 nontrivial rotation each =6= 6 elements. Each permutes the 66 faces in three 22-cycles: type x23x_2^3.

Check the count: 1+6+3+8+6=24=∣G∣1+6+3+8+6 = 24 = |G|. ✓. So the cycle index is

ZG(x1,…,x6)=124(x16+6x12x4+3x12x22+8x32+6x23).Z_G(x_1,\dots,x_6) = \frac{1}{24}\Big(x_1^6 + 6x_1^2x_4 + 3x_1^2x_2^2 + 8x_3^2 + 6x_2^3\Big).

Plain count with 3 colors (Burnside). Set every xi=3x_i = 3:

ZG(3,3,3,3,3,3)=124(36+6⋅32⋅3+3⋅32⋅32+8⋅32+6⋅33).Z_G(3,3,3,3,3,3) = \frac{1}{24}\Big(3^6 + 6\cdot 3^2\cdot 3 + 3\cdot 3^2\cdot 3^2 + 8\cdot 3^2 + 6\cdot 3^3\Big).

Compute each term: 36=7293^6=729; 6⋅32⋅3=6⋅9⋅3=1626\cdot 3^2\cdot 3 = 6\cdot 9\cdot 3=162; 3⋅32⋅32=3⋅9⋅9=2433\cdot 3^2\cdot 3^2 = 3\cdot 9 \cdot 9 = 243; 8⋅32=8⋅9=728\cdot 3^2 = 8\cdot 9=72; 6⋅33=6⋅27=1626\cdot 3^3=6\cdot 27=162. Sum: 729+162+243+72+162=1368729+162+243+72+162 = 1368. Divide by 2424:

1368/24=57.1368/24 = 57.

So there are 57 distinct colorings of a cube's faces using (up to) three colors, up to rotation — a classical, checkable answer.

Weighted refinement. Now assign weight yy to color 11 and weight 11 to each of colors 2,32,3, so C(y)=y+2C(y) = y+2 and C(yi)=yi+2C(y^i) = y^i+2. Pólya's theorem gives the generating function for the number of faces colored with color 11:

G(y)=124[(y+2)6+6(y+2)2(y4+2)+3(y+2)2(y2+2)2+8(y3+2)2+6(y2+2)3].G(y) = \frac{1}{24}\Big[(y+2)^6 + 6(y+2)^2(y^4+2) + 3(y+2)^2(y^2+2)^2 + 8(y^3+2)^2 + 6(y^2+2)^3\Big].

As a partial check, we verify the coefficient of y0y^0 (colorings using none of color 11, i.e. using only colors 2,32,3 — a 22-coloring count). Setting y=0y=0:

G(0)=124[26+6⋅22⋅2+3⋅22⋅22+8⋅22+6⋅23]=124[64+48+48+32+48]=24024=10.G(0) = \frac1{24}\big[2^6 + 6\cdot 2^2\cdot 2 + 3\cdot 2^2\cdot 2^2 + 8\cdot 2^2 + 6\cdot 2^3\big] = \frac{1}{24}\big[64+48+48+32+48\big] = \frac{240}{24}=10.

Indeed, the number of 22-colorings of a cube's faces up to rotation is a well-known value, 1010, consistent with the classical count of cube 22-colorings (this can be independently checked directly: colorings by number of "color-1" faces 0,…,60,\dots,6 give 1,1,2,2,2,1,11,1,2,2,2,1,1, summing to 1010). This cross-check confirms the cycle index and the substitution were both computed correctly.

CounterexampleWhy the group must act on the set of positions, not on an unrelated set

The proof of the weighted Burnside step (Step 1 of the Pólya proof) crucially used that W(f)W(f) is constant on orbits, which followed from WW being built as a product ∏dw(f(d))\prod_d w(f(d)) over a bijective re-indexing d′=g−1⋅dd' = g^{-1}\cdot d of the position set DD under the same group action that defines the coloring action on RDR^D. If instead we let a group GG act on the colorings RDR^D in some way not induced by a permutation action on DD, the cycle-index machinery collapses. Concretely: let D={1,2}D = \{1,2\}, R={Red,Blue}R = \{\text{Red},\text{Blue}\}, so RDR^D has 44 colorings: RR, RB, BR, BB. Let G={e,σ}≅C2G = \{e,\sigma\}\cong C_2 act on RDR^D not by permuting positions, but by the "color-flip" rule σ(f)=\sigma(f) = (swap Red↔\leftrightarrowBlue at both positions simultaneously, without touching position labels): so σ(RB)=BR\sigma(\text{RB}) = \text{BR} is not what happens; instead σ(RB)=BR\sigma(\text{RB}) = \text{BR} under color flip is actually σ(RB)\sigma(\mathrm{RB}) recolors position 1 from R to B and position 2 from B to R, giving BR — this happens to coincide with a position-swap in this toy case, so let's make it clearly different: define σ\sigma to swap colors only at position 1, leaving position 2 fixed: σ(RR)=BR\sigma(\mathrm{RR})=\mathrm{BR}, σ(RB)=BB\sigma(\mathrm{RB})=\mathrm{BB}, σ(BR)=RR\sigma(\mathrm{BR})=\mathrm{RR}, σ(BB)=RB\sigma(\mathrm{BB})=\mathrm{RB}. This σ\sigma is a perfectly good involution of RDR^D (it's its own inverse), so G={e,σ}G=\{e,\sigma\} acts on X=RDX = R^D and Burnside's Lemma itself still applies fine to count orbits of this action (orbits: {RR,BR}\{\mathrm{RR,BR}\}, {RB,BB}\{\mathrm{RB,BB}\}, so 22 orbits; check: ∣Xe∣=4|X^e|=4, ∣Xσ∣=0|X^\sigma|=0 since no coloring is fixed, average =(4+0)/2=2=(4+0)/2=2 ✓). But σ\sigma is not induced by any permutation of the position set D={1,2}D=\{1,2\} — it cannot be written as (σ⋅f)(d)=f(g−1⋅d)(\sigma\cdot f)(d) = f(g^{-1}\cdot d) for any permutation gg of DD, since such position-induced actions always send a "constant" coloring (RR or BB) to another constant coloring, whereas here σ(RR)=BR\sigma(\mathrm{RR}) = \mathrm{BR} is not constant. Consequently the cycle-index / Pólya apparatus does not apply to this action at all: there is no cycle type on positions to record, no factorization of fixed colorings into "one free choice per cycle," and the weight-multiplicativity argument in Step 2 of the proof (which relied on gg-fixed colorings being exactly those constant on position-cycles) breaks down completely. This shows the hypothesis that GG acts on RDR^D via a permutation action on DD (not an arbitrary action on the coloring set) is essential to Pólya's theorem, even though the weaker Burnside's Lemma survives unchanged for an arbitrary action on any finite set.

Scope, edge cases & common traps

SituationWhat to watch for
GG trivial ({e}\{e\})Cycle index is x1nx_1^n; Pólya reduces to ordinary generating function C(y)nC(y)^n, no collapsing occurs.
DD infiniteTheorem requires ∣D∣=n|D|=n finite; cycle index polynomial is undefined otherwise.
Colors weighted with multiple variables y1,…,yky_1,\dots,y_kStill valid: substitute xi↦∑rw(r)ix_i \mapsto \sum_r w(r)^i where w(r)iw(r)^i means each yjy_j raised to its exponent times ii (i.e. C(y1i,…,yki)C(y_1^i,\dots,y_k^i)).
Action not induced by permuting positionsPólya's theorem (cycle-index substitution) fails; only the cruder Burnside's Lemma on the coloring set may still apply.
Confusing c(g)c(g) (total cycles) with ci(g)c_i(g) (cycles of length ii)The unweighted Lemma uses total cycle count c(g)=∑ici(g)c(g)=\sum_i c_i(g); the cycle index tracks each length separately — necessary for the weighted theorem.

The mathematician behind it

Origins · 1 minGeorge Pólya and how this was discovered
GP
George Pólya
1887–1985 · Hungarian–American mathematician, Stanford University

Pólya made foundational contributions across combinatorics, probability, number theory, and mathematical pedagogy — he is equally famous for his 1945 book How to Solve It on problem-solving heuristics. His 1937 paper "Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen" introduced the cycle-index enumeration technique now bearing his name, originally motivated by counting distinct chemical isomers (molecules related by rotational symmetry). The counting lemma underlying his theorem had actually been found earlier by William Burnside (who himself attributed it to Cauchy and Frobenius), but Pólya's generating-function upgrade — substituting power sums of a color generating function into the cycle index — was genuinely new and vastly more powerful for applications.

History
- 1887: George Pólya born in Budapest, Hungary.
- 1897: Cauchy–Frobenius style counting-by-averaging ideas circulate in group theory (predating Burnside's textbook statement).
- 1911: William Burnside's Theory of Groups of Finite Order popularizes the orbit-counting lemma later named after him.
- 1937: Pólya publishes the cycle-index enumeration theorem, motivated by counting chemical isomers under symmetry.
- 1959: Nicolaas de Bruijn independently generalizes and extends the theorem (now sometimes called the Pólya–de Bruijn enumeration theorem).
Is Burnside's Lemma the same thing as the Pólya Enumeration Theorem?

No. Burnside's Lemma is a general statement about any finite group acting on any finite set: the number of orbits equals the average number of fixed points. Pólya's theorem is a specialization to the particular situation where the set being acted on is a set of colorings RDR^D, and it goes further by producing a full generating function (tracking exact color usage) rather than a single orbit count. Setting all cycle-index variables to ∣R∣|R| recovers the Burnside orbit count as a special case of Pólya's formula, so Pólya's theorem strictly contains and refines Burnside's Lemma in this coloring context, but Burnside's Lemma itself is more general in the sense that it applies to arbitrary group actions, not just coloring actions.

Why does the cycle index need variables x1,…,xnx_1,\dots,x_n instead of just one variable?

Because the weighted version of the counting problem needs to track cycles of every possible length separately: a cycle of length ℓ\ell forces ℓ\ell positions to share one color, contributing a term C(yℓ)=∑rw(r)ℓC(y^\ell) = \sum_r w(r)^\ell rather than C(y)ℓC(y)^\ell. If we used only one variable, we would lose the information distinguishing "one cycle of length 6" from "six cycles of length 1," which correspond to very different color-usage patterns and give different generating functions. The multivariable cycle index is exactly the data needed to substitute C(yi)C(y^i) for xix_i in the proof's Step 2 and 3.

How do you actually compute the cycle index of a group acting on a set, in practice?

List every group element (or, more efficiently, every conjugacy class of elements acting the same way, since conjugate permutations have the same cycle type), determine its cycle type as a permutation of the position set, write the corresponding monomial ∏ixici(g)\prod_i x_i^{c_i(g)}, sum these monomials over all group elements, and divide by ∣G∣|G|. In practice one groups elements by conjugacy class or by geometric type (as done for the cube's rotation group: identity, face-quarter-turns, face-half-turns, vertex-third-turns, edge-half-turns), computes the cycle type once per class, and multiplies by the class size before summing.

Does Pólya's theorem require the color set RR to be finite?

The theorem as proved here assumes RR is finite so that C(y)=∑r∈Rw(r)C(y) = \sum_{r\in R} w(r) is a finite sum and all manipulations (finite products, finite sums) are unconditionally valid. In practice the theorem is often stated with RR replaced directly by a formal generating function C(y)C(y) (e.g. C(y)=11−yC(y) = \frac{1}{1-y} for "infinitely many colors, one per positive integer weight"), and the same substitution formula ZG(C(y),C(y2),… )Z_G(C(y),C(y^2),\dots) continues to hold as an identity of formal power series, but this requires separately justifying convergence/well-definedness in the formal power series ring — a routine but real extension beyond the finite-RR proof given here.

What is the relationship between Pólya enumeration and the Twelvefold Way?

The The Twelvefold Way classifies counting problems for functions f:D→Rf: D \to R according to whether DD, RR, or neither/both are considered "up to symmetry" (identical elements or distinguishable), and whether functions must be injective/surjective. Pólya enumeration handles the specific slice of this classification where positions in DD are acted on by a specified symmetry group GG (not just treated as fully identical or fully distinct) while colors in RR remain distinguishable but weighted; it is a vast generalization of the "distinct domain, distinct range, no group" and "fully symmetric domain" corners of the Twelvefold Way, filling in the intermediate cases where the symmetry is neither trivial nor total.

Can Pólya's theorem count colorings using a fixed exact number of colors, e.g. "exactly 3 colors must all be used at least once"?

Yes, via inclusion-exclusion layered on top of Pólya's theorem. First use Pólya's theorem to count colorings (up to symmetry) using at most kk available colors for every kk, then apply inclusion–exclusion over subsets of the color palette to isolate colorings that use every one of a fixed set of colors at least once. This is analogous to how ordinary surjection counts are derived from ordinary function counts using Stirling Numbers of the First Kind-adjacent inclusion–exclusion arguments (specifically Stirling numbers of the second kind govern plain surjections; the same inclusion-exclusion idea composes cleanly with the symmetrized Pólya counts).

Why does the proof of Pólya's theorem redo Burnside's double-counting argument instead of just citing Burnside's Lemma directly?

Because the plain (unweighted) Burnside's Lemma only tells you the count of orbits, ∣X/G∣|X/G|; it says nothing about how orbits are weighted or what data (like color usage) distinguishes one orbit from another. The proof needs the finer weighted version, summing W(f)W(f) rather than 11 over each orbit, which requires re-running the identical double-counting argument with weights inserted throughout. The unweighted Lemma is recovered only afterward, as the special case where every weight equals 11.

Before this