40.06.10 · combinatorics / design-coding-theory

Pólya-Redfield Enumeration and the Cycle Index

shipped3 tiersLean: none

Anchor (Master): van Lint-Wilson 2001 *A Course in Combinatorics* Ch. 35-36 (Pólya theory, the power group, de Bruijn's extension, graphical enumeration); Pólya-Read 1987 *Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds* (Springer) (the annotated translation of Pólya 1937); Harary-Palmer 1973 *Graphical Enumeration* (Academic Press) Ch. 2-4 (the pair group, counting graphs up to isomorphism); de Bruijn 1964 in Beckenbach *Applied Combinatorial Mathematics* Ch. 5 (the power-group enumeration theorem)

Intuition Beginner

Take six beads on a loop of string — say each bead can be black or white — and ask how many genuinely different necklaces you can make. There are $2 \times 2 \times 2 \times 2 \times 2 \times 2 = 64$ ways to colour six labelled positions, but a necklace has no labels: you can rotate it, and a colouring that turns into another by rotation is the same necklace. So $64$ overcounts. The honest count is much smaller. The question of this unit is how to get that honest count without drawing every necklace and crossing out duplicates by hand.

The key idea is to average. Instead of looking at colourings directly, look at the symmetries — the rotations of the necklace — one at a time, and for each symmetry count how many colourings it leaves completely unchanged. A rotation by one position fixes only the all-black and the all-white necklaces, because every other colouring gets shuffled. The do-nothing rotation fixes all $64$ . If you average the number of fixed colourings over all six rotations, you get exactly the number of different necklaces. This averaging rule is the heart of the whole subject.

To make the averaging systematic, we record, for each symmetry, how it breaks the positions into cycles — little loops of positions that the symmetry rotates among themselves. That bookkeeping device is called the cycle index, and once you have it, plugging in the right ingredients counts coloured arrangements of every kind.

Visual Beginner

Picture the six necklace positions as points on a clock face. A rotation by one step sends every point to its neighbour, so all six points form one big loop: a single cycle of length six. A rotation by two steps sends $1 \to 3 \to 5 \to 1$ and $2 \to 4 \to 6 \to 2$ : two loops of length three. A rotation by three steps pairs $1 \to 4$ , $2 \to 5$ , $3 \to 6$ : three loops of length two. The do-nothing rotation leaves every point alone: six loops of length one.

rotation by	cycle picture	number of cycles
$0$ steps	six loops of length $1$	$6$
$1$ step	one loop of length $6$	$1$
$2$ steps	two loops of length $3$	$2$
$3$ steps	three loops of length $2$	$3$
$4$ steps	two loops of length $3$	$2$
$5$ steps	one loop of length $6$	$1$

A colouring is unchanged by a rotation exactly when every loop is painted a single colour. So a rotation with $c$ loops fixes $2^{c}$ two-colour patterns: the do-nothing rotation fixes $2^{6} = 64$ , the single-step rotation fixes $2^{1} = 2$ , and so on. Averaging these counts gives the number of necklaces.

Worked example Beginner

Count the two-colour necklaces on six beads, where two necklaces are the same if one rotates into the other.

Step 1. List the six rotations and how many loops each makes, from the table above: $6, 1, 2, 3, 2, 1$ loops.

Step 2. For each rotation, a colouring survives only when each loop is one solid colour, and there are $2$ colours per loop. So the surviving counts are $2^{6}, 2^{1}, 2^{2}, 2^{3}, 2^{2}, 2^{1}$ , that is $64, 2, 4, 8, 4, 2$ .

Step 3. Add these survivor counts: $64 + 2 + 4 + 8 + 4 + 2 = 84$ .

Step 4. Divide by the number of rotations, which is $6$ : $84 \div 6 = 14$ .

So there are $14$ different two-colour necklaces on six beads. You can check the extremes: there is $1$ all-black and $1$ all-white necklace, and the remaining $12$ account for the mixed ones.

What this tells us: a count that looked like it needed all $64$ colourings sorted into rotation-families came out of a short average over just six symmetries. The work shifted from the colourings to the symmetries, and there were far fewer symmetries.

Check your understanding Beginner

Exercise (easy, multiple choice).

When counting arrangements that are the same under a set of symmetries, the number of genuinely different arrangements equals which of the following?

A. The total number of arrangements, ignoring the symmetries

B. The average, over all the symmetries, of the number of arrangements each one leaves unchanged

C. The number of symmetries

D. The total number of arrangements divided by the number of colours

Hint

The necklace count came from averaging survivor counts over the rotations, not from dividing the raw total by anything fixed.

Answer

B. The number of distinct arrangements is the average number of arrangements fixed by a symmetry, taken over all the symmetries. Feedback-correct: this is the averaging rule used for the necklace. Feedback-wrong: option A overcounts because it ignores that some arrangements match; option D would be right only if every family had the same size, which is usually false.

Exercise (easy, true-false).

True or false: a rotation leaves a coloured arrangement unchanged exactly when every loop of positions made by that rotation is painted a single colour.

Hint

Inside one loop the rotation pushes each position onto the next. For the picture to look the same afterwards, those positions must already match.

Answer

True. Within a loop, the rotation carries each position to the next, so the arrangement looks the same after rotating only if all positions in that loop already share one colour. A rotation making $c$ loops therefore fixes $2^{c}$ two-colour arrangements. Feedback-correct: this loop-is-one-colour rule is what turns the symmetry into a power of the colour count. Feedback-wrong: it is not enough for two positions to match; every position in the loop must agree.

Formal definition Intermediate+

Throughout, $G$ is a finite group acting on a finite set $X$ with $∣ X ∣ = n$ , written on the left as $g \cdot x$ ; each $g \in G$ induces a permutation of $X$ , and we identify $g$ with that permutation. We colour the points of $X$ from a set $R$ of colours; the set of all colourings is $R^{X}$ , and $G$ acts on $R^{X}$ by $(g \cdot f) (x) = f (g^{- 1} x)$ . Two colourings are equivalent when they lie in the same $G$ -orbit, and a pattern is an orbit. The orbit-counting tool is the Burnside / Cauchy-Frobenius lemma, whose group-action home is 01.02.03; we state it and build on it rather than reprove the orbit-stabiliser machinery.

Lemma (Burnside / Cauchy-Frobenius). Let $G$ act on a finite set $S$ , and for $g \in G$ write $Fix (g) = {s \in S : g \cdot s = s}$ . Then the number of orbits is $$ #{\text{orbits}} ;=; \frac{1}{|G|} \sum_{g \in G} |\mathrm{Fix}(g)|. $$ The number of orbits is the average number of fixed points.

Definition (cycle type and cycle index). A permutation $g$ of an $n$ -point set decomposes uniquely into disjoint cycles; let $j_{k} (g)$ be the number of cycles of length $k$ , so $\sum_{k} k j_{k} (g) = n$ . The cycle index of $G$ acting on $X$ is the polynomial in the indeterminates $a_{1}, \dots, a_{n}$ $$ Z(G) ;=; Z(G; a_1, \ldots, a_n) ;=; \frac{1}{|G|} \sum_{g \in G} \prod_{k=1}^{n} a_k^{, j_k(g)} , $$ the average over $G$ of the monomial recording $g$ 's cycle type. The variable $a_{k}$ marks a cycle of length $k$ . Substituting $a_{k} = m$ for every $k$ gives $Z (G; m, \dots, m) = ∣ G ∣^{- 1} \sum_{g} m^{c (g)}$ , where $c (g) = \sum_{k} j_{k} (g)$ is the number of cycles, which by the lemma is the number of orbits of $G$ on the set of $m$ -colourings $R^{X}$ with $∣ R ∣ = m$ .

Definition (figure-counting series and pattern inventory). Assign to each colour $r \in R$ a weight $w (r)$ in a commutative ring (often a monomial in formal variables), and define the figure-counting series $ϕ (t) = \sum_{r \in R} t^{w (r)}$ , or more generally the multivariate inventory $\sum_{r} \prod_{i} x_{i}^{w_{i} (r)}$ . The pattern inventory is the generating function whose coefficient of a given weight monomial counts the patterns (orbits) of that total weight, where the weight of a colouring $f$ is $\sum_{x \in X} w (f (x))$ and is constant on orbits.

Definition (cyclic, dihedral, symmetric cycle indices). For the cyclic group $C_{n}$ acting by rotation on $n$ points, $$ Z(C_n) = \frac{1}{n} \sum_{d \mid n} \phi(d), a_d^{, n/d}, $$ with $ϕ$ Euler's totient. For the dihedral group $D_{n}$ of order $2 n$ one adds the reflection contribution: $Z (D_{n}) = \frac{1}{2} Z (C_{n}) + \frac{1}{2} R_{n}$ , where $R_{n} = a_{1} a_{2}^{(n - 1) /2}$ for $n$ odd and $R_{n} = \frac{1}{2} (a_{1}^{2} a_{2}^{(n - 2) /2} + a_{2}^{n /2})$ for $n$ even. For the symmetric group $S_{n}$ acting on itself, $$ Z(S_n) = \sum_{\lambda \vdash n} \prod_{k \geq 1} \frac{a_k^{, m_k}}{k^{, m_k}, m_k!}, $$ the sum over partitions $λ$ of $n$ with $m_{k}$ parts equal to $k$ .

Counterexamples to common slips Intermediate+

"The cycle index counts orbits by itself." It is a polynomial in formal variables; only a substitution turns it into a number. The orbit count of $m$ -colourings is $Z (G; m, \dots, m)$ , not $Z (G)$ as written.
" $a_{k}$ counts cycles of any length." The subscript is load-bearing: $a_{k}$ marks cycles of length exactly $k$ . The exponent $j_{k} (g)$ is how many length- $k$ cycles $g$ has, and $\sum_{k} k j_{k} (g) = n$ always.
"Rotations and reflections give the same count." The bracelet group $D_{n}$ identifies a necklace with its mirror image, so $Z (D_{n})$ produces fewer (or equal) patterns than $Z (C_{n})$ ; the two indices differ by the reflection terms, and conflating them double-identifies or under-identifies arrangements.
"Pólya's theorem needs equal-weight colours." The figure-counting series carries arbitrary weights $w (r)$ ; weighting lets one count, for instance, necklaces with a prescribed number of black beads as a single coefficient, not just the total.

Key theorem with proof Intermediate+

The central result substitutes the figure-counting series into the cycle index and recovers the full pattern inventory; the unweighted orbit count is the special case where every colour has weight zero.

Theorem (Pólya-Redfield enumeration). Let $G$ act on an $n$ -set $X$ , let $R$ be a set of colours with figure-counting series $ϕ (t) = \sum_{r \in R} t^{w (r)}$ , and give a colouring $f \in R^{X}$ the weight $W (f) = \sum_{x \in X} w (f (x))$ . Then the pattern inventory — the generating function $\sum_{patterns P} t^{W (P)}$ counting $G$ -orbits of colourings by weight — equals $$ \sum_{\text{patterns } P} t^{W(P)} ;=; Z\big(G;, \phi(t),, \phi(t^2),, \phi(t^3),, \ldots,, \phi(t^n)\big), $$ the cycle index with $a_{k}$ replaced by $ϕ (t^{k})$ . In particular, setting $t = 1$ and $∣ R ∣ = m$ gives the number of patterns $Z (G; m, \dots, m)$ ^{[van Lint-Wilson Ch. 35]}.

Proof. The group $G$ acts on $R^{X}$ , and patterns are its orbits. To count orbits by weight, apply the Burnside / Cauchy-Frobenius lemma in a weighted form: the number of orbits of weight giving $t^{W}$ , summed into a generating function, equals $$ \frac{1}{|G|} \sum_{g \in G} \sum_{\substack{f \in R^X \ g \cdot f = f}} t^{W(f)}, $$ because each orbit of weight $W$ contributes $t^{W}$ once on the left, while on the right every colouring fixed by $g$ is counted with its weight and the averaging over $G$ collapses each orbit to a single contribution (the stabiliser sizes cancel against the orbit sizes exactly as in the unweighted lemma).

Fix $g$ and evaluate the inner sum over colourings fixed by $g$ . A colouring $f$ satisfies $g \cdot f = f$ precisely when $f$ is constant on each cycle of $g$ : if $x$ and $g^{- 1} x$ lie in a common cycle, $f (x) = f (g^{- 1} x)$ forces one colour per cycle. A cycle of length $k$ contributes $k$ points all coloured by a single $r \in R$ , hence contributes weight $k w (r)$ and a factor $t^{k w (r)}$ to $t^{W (f)}$ . Summing over the colour choice $r$ for that cycle gives $\sum_{r \in R} t^{k w (r)} = ϕ (t^{k})$ . The cycles of $g$ are independent, so the total over all colourings fixed by $g$ is the product over cycles, $$ \sum_{\substack{f : g \cdot f = f}} t^{W(f)} ;=; \prod_{k=1}^{n} \phi(t^k)^{, j_k(g)}, $$ one factor $ϕ (t^{k})$ per length- $k$ cycle. Substituting into the averaged sum, $$ \sum_{\text{patterns}} t^{W} ;=; \frac{1}{|G|}\sum_{g \in G} \prod_{k=1}^{n} \phi(t^k)^{, j_k(g)} ;=; Z\big(G; \phi(t), \phi(t^2), \ldots, \phi(t^n)\big), $$ which is the cycle index with $a_{k} \mapsto ϕ (t^{k})$ . Setting $t = 1$ makes $ϕ (1) = ∣ R ∣ = m$ , recovering $Z (G; m, \dots, m)$ as the unweighted pattern count. $□$

Bridge. This theorem builds toward every concrete enumeration in the unit: choosing $ϕ$ and the acting group instantiates necklaces, cubes, graphs, and isomers as one substitution. The foundational reason it works is that fixed colourings of $g$ are exactly the colourings constant on $g$ 's cycles, so the cycle index — a pure record of cycle structure — already contains all the colouring information once the colours are fed in through $ϕ$ . This is exactly the weighted refinement of the Burnside lemma of 01.02.03: there one averaged $∣ Fix (g) ∣$ , here one averages the weight-generating function of $Fix (g)$ , and putting these together the orbit count and the orbit inventory become a single formula evaluated at $t = 1$ versus general $t$ . The construction generalises from a single colour set to functions between two symmetric structures, where it appears again in the power-group theorem, and it is dual to the substitution that reads multiplication of figure-series as composition of cycle indices in the plethystic calculus.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Derive the cyclic cycle index $Z (C_{n}) = \frac{1}{n} \sum_{d ∣ n} ϕ (d) a_{d}^{n / d}$ by determining the cycle type of the rotation $ρ^{j}$ (rotation by $j$ steps).

Hint

The rotation $ρ^{j}$ on $n$ points splits into $g cd (n, j)$ cycles, each of length $n / g cd (n, j)$ . Group the $j$ by the value $d = n / g cd (n, j)$ and count how many give each $d$ .

Answer

The rotation $ρ^{j}$ ( $0 \leq j < n$ ) sends $x \mapsto x + j (mod n)$ ; its orbit on a point has length equal to the order of $j$ in $Z / n$ , namely $n / g cd (n, j)$ , and there are $g cd (n, j)$ such cycles. Set $d = n / g cd (n, j)$ , so each cycle has length $d$ and there are $n / d$ of them, contributing the monomial $a_{d}^{n / d}$ . The number of $j \in {0, \dots, n - 1}$ with $n / g cd (n, j) = d$ — equivalently $g cd (n, j) = n / d$ — is the number of $j$ with $j = (n / d) j^{'}$ and $g cd (d, j^{'}) = 1$ , which is $ϕ (d)$ . Averaging over the $n$ rotations, $Z (C_{n}) = \frac{1}{n} \sum_{d ∣ n} ϕ (d) a_{d}^{n / d}$ . Rubric: full credit for the cycle-length computation $n / g cd (n, j)$ and the totient count of $j$ producing each $d$ .

Exercise 4 (medium, symbolic).

Compute the pattern inventory for two-colour necklaces on six beads with colours black ( $w = 1$ ) and white ( $w = 0$ ), so $ϕ (t) = 1 + t$ . Read off how many necklaces have exactly three black beads.

Hint

Substitute $a_{k} = ϕ (t^{k}) = 1 + t^{k}$ into $Z (C_{6}) = \frac{1}{6} (a_{1}^{6} + a_{2}^{3} + 2 a_{3}^{2} + 2 a_{6})$ and expand. The coefficient of $t^{3}$ counts three-black necklaces.

Answer

Substituting $a_{k} = 1 + t^{k}$ : $$ Z = \tfrac16\big((1+t)^6 + (1+t^2)^3 + 2(1+t^3)^2 + 2(1+t^6)\big). $$ Expanding, $(1 + t)^{6} = 1 + 6 t + 15 t^{2} + 20 t^{3} + 15 t^{4} + 6 t^{5} + t^{6}$ ; $(1 + t^{2})^{3} = 1 + 3 t^{2} + 3 t^{4} + t^{6}$ ; $2 (1 + t^{3})^{2} = 2 + 4 t^{3} + 2 t^{6}$ ; $2 (1 + t^{6}) = 2 + 2 t^{6}$ . Summing and dividing by $6$ gives $1 + t + 3 t^{2} + 4 t^{3} + 3 t^{4} + t^{5} + t^{6}$ . The coefficient of $t^{3}$ is $4$ : there are $4$ necklaces with exactly three black beads, and the total $1 + 1 + 3 + 4 + 3 + 1 + 1 = 14$ recovers Exercise 1. Rubric: full credit for the substitution, the expansion, and the correct coefficient extraction.

Exercise 6 (medium, symbolic).

Using the same cube-face cycle index with $ϕ (t) = 1 + t$ (black/white), find the pattern inventory and report how many cube colourings have exactly three black faces.

Hint

Set $a_{k} = 1 + t^{k}$ . You only need the coefficient of $t^{3}$ after dividing by $24$ ; track the $t^{3}$ contributions from each term.

Answer

With $a_{k} = 1 + t^{k}$ , the $t^{3}$ coefficients of the five terms are: from $(1 + t)^{6}$ , $(3 6) = 20$ ; from $6 (1 + t)^{2} (1 + t^{4})$ , the $t^{3}$ coefficient of $(1 + t)^{2} (1 + t^{4}) = (1 + 2 t + t^{2}) (1 + t^{4})$ is $0$ , times $6$ gives $0$ ; from $3 (1 + t)^{2} (1 + t^{2})^{2}$ , expanding $(1 + 2 t + t^{2}) (1 + 2 t^{2} + t^{4})$ the $t^{3}$ coefficient is $2$ (the $2 t \cdot 2 t^{2}$ contribution wait: $2 t \cdot t^{2}$ term), more carefully $(1 + 2 t + t^{2}) (1 + 2 t^{2} + t^{4})$ has $t^{3}$ coefficient $2 \cdot 2 = 4$ from $2 t \cdot 2 t^{2}$ , times $3$ gives $12$ ; from $8 (1 + t^{3})^{2}$ , the $t^{3}$ coefficient is $2$ , times $8$ gives $16$ ; from $6 (1 + t^{2})^{3}$ , the $t^{3}$ coefficient is $0$ . Summing: $20 + 0 + 12 + 16 + 0 = 48$ , divided by $24$ gives $2$ . There are $2$ distinct three-black-face colourings (the three faces meeting at a vertex, and three faces forming a band). Rubric: full credit for the substitution and a correct $t^{3}$ total of $48/24 = 2$ .

Exercise 7 (hard, symbolic).

Derive the symmetric-group cycle index $Z (S_{n}) = \sum_{λ ⊢ n} \prod_{k} a_{k}^{m_{k}} / (k^{m_{k}} m_{k}!)$ by counting how many permutations of $S_{n}$ have a given cycle type $λ = (1^{m_{1}} 2^{m_{2}} \dots)$ .

Hint

The number of permutations with $m_{k}$ cycles of length $k$ for each $k$ is $n! / \prod_{k} (k^{m_{k}} m_{k}!)$ . Average the monomial $\prod_{k} a_{k}^{m_{k}}$ over $S_{n}$ .

Answer

Fix a cycle type $λ$ with $m_{k}$ cycles of length $k$ , so $\sum_{k} k m_{k} = n$ . To count permutations of this type, fill the cycle slots with the $n$ symbols in $n!$ ordered ways, then divide by the overcounting: each cycle of length $k$ can be written starting at any of its $k$ positions ( $k^{m_{k}}$ over all length- $k$ cycles), and the $m_{k}$ cycles of length $k$ can be permuted among themselves ( $m_{k}!$ ). Hence the number of permutations of type $λ$ is $n! / \prod_{k} (k^{m_{k}} m_{k}!)$ . Each contributes the monomial $\prod_{k} a_{k}^{m_{k}}$ , so $$ Z(S_n) = \frac{1}{n!} \sum_{\lambda \vdash n} \frac{n!}{\prod_k k^{m_k} m_k!} \prod_k a_k^{m_k} = \sum_{\lambda \vdash n} \prod_k \frac{a_k^{m_k}}{k^{m_k} m_k!}. $$ Rubric: full credit for the orbit-stabiliser count $n! / \prod_{k} (k^{m_{k}} m_{k}!)$ of permutations of a fixed cycle type and the resulting cancellation of $n!$ .

Exercise 8 (hard, symbolic).

Count the number of non-isomorphic simple graphs on four vertices using the pair group $S_{4}^{(2)}$ , the image of $S_{4}$ acting on the $(2 4) = 6$ edges of $K_{4}$ . Its cycle index is $Z (S_{4}^{(2)}) = \frac{1}{24} (a_{1}^{6} + 9 a_{1}^{2} a_{2}^{2} + 8 a_{3}^{2} + 6 a_{2} a_{4})$ .

Hint

A simple graph on four labelled vertices is a two-colouring (edge present / absent) of the six edge-slots; counting up to vertex relabelling is counting orbits of $S_{4}^{(2)}$ . Substitute $a_{k} = 2$ .

Answer

$11$ . A graph chooses, for each of the $6$ edges, present or absent: a two-colouring of the edge set, and isomorphism classes are orbits of the pair group. So the count is $Z (S_{4}^{(2)}; 2, \dots, 2) = \frac{1}{24} (2^{6} + 9 \cdot 2^{2} \cdot 2^{2} + 8 \cdot 2^{2} + 6 \cdot 2 \cdot 2) = \frac{1}{24} (64 + 144 + 32 + 24) = \frac{264}{24} = 11$ . The eleven graphs on four vertices range from the empty graph to $K_{4}$ . The figure-counting refinement $ϕ (t) = 1 + t$ (with $t$ marking an edge) yields $1 + t + 2 t^{2} + 3 t^{3} + 2 t^{4} + t^{5} + t^{6}$ , the edge-count distribution. Rubric: full credit for identifying graphs with edge-set two-colourings, the pair-group substitution, and the value $11$ .

Advanced results Master

The substitution theorem is the entry point to a structured calculus. The cycle index is multiplicative and compositional, the power group extends enumeration to symmetric ranges, and the pair-group construction reduces graphical enumeration to a single index evaluation.

Theorem 1 (product and the figure series). For groups $G$ on $X$ and $H$ on $Y$ acting on the disjoint union $X ⊔ Y$ (the direct product $G \times H$ acting coordinatewise), $Z (G \times H) = Z (G) Z (H)$ as polynomials in a shared variable set, because a permutation $(g, h)$ has cycle multiset the union of those of $g$ and $h$ . Consequently the pattern inventory of a product of independent symmetric structures is the product of the inventories, the enumerative analogue of independence ^{[de Bruijn 1964]}.

Theorem 2 (Pólya's theorem in inventory form). With $G$ acting on $X$ , $∣ X ∣ = n$ , and colours weighted by a multivariate figure series $c (x_{1}, x_{2}, \dots) = \sum_{r} \prod_{i} x_{i}^{w_{i} (r)}$ , the full pattern inventory is $$ \sum_{\text{patterns}} \prod_i x_i^{W_i} ;=; Z\big(G;, c(x_1,x_2,\ldots),, c(x_1^2, x_2^2, \ldots),, c(x_1^3,\ldots),,\ldots\big), $$ substituting $a_{k} \mapsto c (x_{1}^{k}, x_{2}^{k}, \dots)$ . The single-variable form of the Key theorem is the case $c (t) = \sum_{r} t^{w (r)}$ , and the bare orbit count is $c \equiv m$ ^{[van Lint-Wilson Ch. 35]}.

Theorem 3 (power-group enumeration; de Bruijn). Let $A$ act on a domain $X$ and $B$ act on a range $Y$ , and consider the set $Y^{X}$ of functions with the power group $B^{A}$ acting by $(β, α) \cdot f = β \circ f \circ α^{- 1}$ . The number of orbits of $B^{A}$ on $Y^{X}$ is $$ \frac{1}{|A|,|B|}\sum_{\alpha \in A}\sum_{\beta \in B} \prod_{k \geq 1} \Big(\sum_{d \mid k} d, j_d(\beta)\Big)^{ j_k(\alpha)}, $$ the average over both groups of a product that pairs each $k$ -cycle of $α$ against the cycle structure of $β$ . When $B$ is the one-element group this collapses to the orbit count $Z (A; ∣ Y ∣, \dots, ∣ Y ∣)$ , recovering ordinary Pólya counting; the symmetry on the range is the new ingredient ^{[de Bruijn 1964]}. The general weighted statement substitutes a figure series and yields the inventory of functions modulo symmetries on both sides.

Theorem 4 (graphical enumeration via the pair group). The number of non-isomorphic simple graphs on $p$ vertices is $Z (S_{p}^{(2)}; 2, 2, \dots)$ , where $S_{p}^{(2)}$ is the pair group induced by $S_{p}$ on the $(2 p)$ unordered vertex-pairs; the edge-count generating function is obtained with $ϕ (t) = 1 + t$ . The cycle index of $S_{p}^{(2)}$ is computed from that of $S_{p}$ by a combinatorial rule expressing the cycle type of a permutation's action on pairs in terms of its action on points: a pair of points in cycles of lengths $r$ and $s$ generates cycles whose lengths are determined by $lcm (r, s)$ and the parity of the within-cycle case ^{[Harary-Palmer Ch. 4]}. Digraphs, multigraphs, and graphs with bounded degree follow by changing the figure series, and the same machinery counts trees through Otter's dissimilarity formula.

Theorem 5 (chemical isomer enumeration). Pólya's 1937 motivation was chemistry: the number of structural isomers of a substituted molecule is the number of orbits of its symmetry group acting on the substitution sites, weighted by a figure series recording the available substituents. For the benzene ring $C_{6} H_{6}$ with hydrogens replaced by two kinds of group, the symmetry group on the six ring positions is $D_{6}$ , and $Z (D_{6}; 1 + t, \dots)$ enumerates the substituted benzenes by substituent count — reproducing the classical ortho/meta/para distinctions as coefficients. Alkane enumeration $C_{k} H_{2 k + 2}$ uses Pólya's tree-counting via the rooted-tree functional equation, the historical origin of the cycle-index method ^{[Pólya-Read 1987]}.

Synthesis. The cycle index is the foundational reason that counting under symmetry, weighted enumeration, graphical isomorphism, and isomer chemistry are one subject: each is the substitution of an appropriate figure series into $Z (G)$ for an appropriate group $G$ , and this is exactly the weighted Burnside average of 01.02.03 made into a generating function. The central insight is that a colouring fixed by $g$ is constant on $g$ 's cycles, so all colouring information factors through the cycle type, and putting these together the inventory $Z (G; ϕ (t), ϕ (t^{2}), \dots)$ at $t = 1$ returns the orbit count while at general $t$ it returns the refined distribution. The product rule $Z (G \times H) = Z (G) Z (H)$ generalises the multiplicativity of independent figure series, and the power-group theorem of de Bruijn generalises Pólya's theorem to functions whose source and target both carry symmetry — the case where the range group is the one-element group is dual to ordinary Pólya counting, recovered by collapsing $B$ . The bridge from this algebra to graph theory is the pair group $S_{p}^{(2)}$ : graph isomorphism classes are orbits of vertex-permutations on edge-slots, so the entire census of small graphs is a single cycle-index evaluation, and the same substitution counts the isomers that first drove Pólya to the theory.

Full proof set Master

Proposition 1 (weighted Burnside / Cauchy-Frobenius lemma). Let $G$ act on a finite set $S$ , and let $w : S \to M$ be a $G$ -invariant weight into a commutative monoid ring, so $w (g \cdot s) = w (s)$ . Then $\sum_{orbits O} w (O) = \frac{1}{∣ G ∣} \sum_{g \in G} \sum_{s : g \cdot s = s} w (s)$ , where $w (O)$ is the common weight of the orbit $O$ .

Proof. Count pairs $(g, s)$ with $g \cdot s = s$ , weighting each by $w (s)$ . Summing first over $g$ gives $\sum_{g} \sum_{s : g \cdot s = s} w (s)$ . Summing first over $s$ gives $\sum_{s} ∣ G_{s} ∣ w (s)$ , where $G_{s}$ is the stabiliser of $s$ . By orbit-stabiliser 01.02.03, $∣ G_{s} ∣ = ∣ G ∣/∣ O_{s} ∣$ for the orbit $O_{s}$ of $s$ , so $\sum_{s} ∣ G_{s} ∣ w (s) = ∣ G ∣ \sum_{s} w (s) /∣ O_{s} ∣$ . Grouping the inner sum by orbits, each orbit $O$ contributes $∣ O ∣$ points of common weight $w (O)$ , giving $\sum_{O} ∣ O ∣ \cdot w (O) /∣ O ∣ = \sum_{O} w (O)$ . Equating the two evaluations and dividing by $∣ G ∣$ yields the stated identity; the case $w \equiv 1$ is the unweighted lemma. $□$

Proposition 2 (fixed colourings are cycle-constant). For $g$ a permutation of $X$ and $f \in R^{X}$ , one has $g \cdot f = f$ if and only if $f$ is constant on each cycle of $g$ . The number of colourings fixed by $g$ with weight tracked by $ϕ$ is $\prod_{k} ϕ (t^{k})^{j_{k} (g)}$ .

Proof. The action is $(g \cdot f) (x) = f (g^{- 1} x)$ , so $g \cdot f = f$ means $f (x) = f (g^{- 1} x)$ for all $x$ , i.e. $f$ is invariant under following $g^{- 1}$ . Iterating, $f$ is constant on every $g$ -orbit in $X$ , and those orbits are exactly the cycles of $g$ . Conversely a cycle-constant $f$ is fixed. A length- $k$ cycle is coloured by a single $r \in R$ contributing weight $k w (r)$ and factor $t^{k w (r)}$ ; summing over $r$ gives $ϕ (t^{k})$ , and independence of cycles multiplies these, with $j_{k} (g)$ factors of $ϕ (t^{k})$ . Hence the weighted count of fixed colourings is $\prod_{k} ϕ (t^{k})^{j_{k} (g)}$ . $□$

Proposition 3 (Pólya substitution theorem). The pattern inventory equals $Z (G; ϕ (t), ϕ (t^{2}), \dots, ϕ (t^{n}))$ .

Proof. Apply Proposition 1 to $S = R^{X}$ with $G$ -action and weight $t^{W (f)}$ , which is $G$ -invariant since $W (g \cdot f) = \sum_{x} w (f (g^{- 1} x)) = \sum_{y} w (f (y)) = W (f)$ by reindexing. The left side is $\sum_{patterns} t^{W (P)}$ . The right side is $\frac{1}{∣ G ∣} \sum_{g} \sum_{f : g \cdot f = f} t^{W (f)}$ , and Proposition 2 evaluates the inner sum as $\prod_{k} ϕ (t^{k})^{j_{k} (g)}$ . Therefore the inventory is $\frac{1}{∣ G ∣} \sum_{g} \prod_{k} ϕ (t^{k})^{j_{k} (g)}$ , which is $Z (G; a_{1}, \dots, a_{n})$ with $a_{k} = ϕ (t^{k})$ . $□$

Proposition 4 (cube-face rotation cycle index). The rotation group of the cube acting on its $6$ faces has cycle index $\frac{1}{24} (a_{1}^{6} + 6 a_{1}^{2} a_{4} + 3 a_{1}^{2} a_{2}^{2} + 8 a_{3}^{2} + 6 a_{2}^{3})$ .

Proof. The rotation group has order $24$ . Classify the $24$ rotations by axis. The identity fixes all six faces: type $a_{1}^{6}$ (one element). Rotations by $\pm 9 0^{\circ}$ about the three face-axes fix the two faces on the axis and four-cycle the equatorial faces: type $a_{1}^{2} a_{4}$ ( $3$ axes $\times 2 = 6$ elements). Rotations by $18 0^{\circ}$ about the three face-axes fix the two axis faces and swap the equatorial faces in two transpositions: type $a_{1}^{2} a_{2}^{2}$ ( $3$ elements). Rotations by $\pm 12 0^{\circ}$ about the four vertex (body-diagonal) axes cycle the faces in two $3$ -cycles: type $a_{3}^{2}$ ( $4$ axes $\times 2 = 8$ elements). Rotations by $18 0^{\circ}$ about the six edge-axes swap faces in three transpositions: type $a_{2}^{3}$ ( $6$ elements). The counts $1 + 6 + 3 + 8 + 6 = 24$ check, and averaging the cycle-type monomials gives the stated index. $□$

Proposition 5 (power-group orbit count). The number of orbits of $B^{A}$ on $Y^{X}$ is $\frac{1}{∣ A ∣∣ B ∣} \sum_{α, β} \prod_{k} (\sum_{d ∣ k} d j_{d} (β))^{j_{k} (α)}$ .

Proof. Apply the unweighted Proposition 1 to $S = Y^{X}$ under $B^{A}$ . A function $f$ is fixed by $(β, α)$ when $β \circ f \circ α^{- 1} = f$ , i.e. $f (α x) = β (f (x))$ . Restrict to one $k$ -cycle $(x, α x, \dots, α^{k - 1} x)$ of $α$ : the values are determined by $f (x) = y_{0}$ through $f (α^{i} x) = β^{i} (y_{0})$ , and consistency around the cycle requires $β^{k} (y_{0}) = y_{0}$ , i.e. $y_{0}$ lies in a $β$ -cycle whose length divides $k$ . The number of such $y_{0}$ is $\sum_{d ∣ k} d j_{d} (β)$ (points on $β$ -cycles of length $d ∣ k$ ). Choices on distinct $α$ -cycles are independent, giving $\prod_{k} (\sum_{d ∣ k} d j_{d} (β))^{j_{k} (α)}$ fixed functions for $(β, α)$ . Averaging over $A \times B$ yields the formula; the one-element $B$ leaves only $j_{1} (β) = ∣ Y ∣$ , collapsing the product to $∣ Y ∣^{c (α)}$ and recovering $Z (A; ∣ Y ∣, \dots, ∣ Y ∣)$ . $□$

Connections Master

The orbit-counting engine is the Burnside / Cauchy-Frobenius lemma whose proof and group-action foundations live at 01.02.03; this unit takes the orbit-stabiliser relation $∣ G_{s} ∣ = ∣ G ∣/∣ O_{s} ∣$ proved there as given and refines the lemma into a weighted, generating-function form. The cycle index is the per-element record of fixed points that the lemma averages, so Pólya theory is exactly the lemma fitted with a figure-series bookkeeping device, and every cube, necklace, and graph count is an instance of that single averaging principle.
The pattern inventory is a generating function, and the figure-counting series $ϕ (t)$ and its substitution $a_{k} \mapsto ϕ (t^{k})$ are operations in the same formal-power-series calculus developed for ordinary and exponential generating functions at the co-produced 40.01.03: products of inventories correspond to disjoint unions of structures, and the cycle-index substitution is a plethystic composition. The exponential formula and the species/symmetric-function viewpoint connect the cyclic, dihedral, and symmetric cycle indices to the power-sum symmetric functions, where $Z (S_{n})$ is the image of the complete homogeneous symmetric function under $p_{k} \mapsto a_{k}$ .
Graph enumeration through the pair group $S_{p}^{(2)}$ ties this unit to the structural graph theory of the chapter and beyond: the census of simple graphs, digraphs, and trees up to isomorphism is a sequence of cycle-index evaluations, and the same weighted machinery underlies the asymptotic enumeration of graphs and the random-graph threshold phenomena studied in probabilistic combinatorics, where the average number of automorphisms governs the symmetry corrections.

Historical & philosophical context Master

The orbit-counting lemma that drives the theory has a tangled attribution. It was used by Cauchy (1845) for the special case of the regular action and stated in general by Frobenius (1887), then popularised in Burnside's 1897 Theory of Groups of Finite Order, where Burnside credited Frobenius; the persistent name "Burnside's lemma" prompted the corrective "the lemma that is not Burnside's," and "Cauchy-Frobenius lemma" is now common ^{[van Lint-Wilson Ch. 35]}. The enumerative theory built on it has an equally layered origin. John Howard Redfield published the cycle-index method and the main enumeration theorem in 1927 in the American Journal of Mathematics ("The theory of group-reduced distributions"), but the paper was overlooked for decades.

Independently, George Pólya developed the same theory in his 1937 Acta Mathematica memoir Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen ^{[Pólya-Read 1987]}, driven by the problem of counting chemical isomers and graphs; Pólya's systematic use of the cycle index (his Zyklenzeiger), the figure-counting series, and applications to trees, graphs, and the substituted benzenes made the method central, and the result is now the Pólya-Redfield enumeration theorem in recognition of Redfield's priority, established by Frank Harary and others in the 1960s. N. G. de Bruijn gave the generating-function formulation and the power-group extension in his 1964 survey ^{[de Bruijn 1964]}, handling symmetry on both domain and range. The graphical applications were systematised by Harary and Palmer in Graphical Enumeration (1973) ^{[Harary-Palmer Ch. 4]}, whose pair-group computations underlie the modern census of small graphs.

Bibliography Master

@article{redfield1927,
  author  = {Redfield, J. Howard},
  title   = {The theory of group-reduced distributions},
  journal = {American Journal of Mathematics},
  volume  = {49},
  number  = {3},
  pages   = {433--455},
  year    = {1927}
}

@article{polya1937,
  author  = {P\'{o}lya, George},
  title   = {Kombinatorische Anzahlbestimmungen f\"{u}r Gruppen, Graphen und chemische Verbindungen},
  journal = {Acta Mathematica},
  volume  = {68},
  pages   = {145--254},
  year    = {1937}
}

@book{polyaread1987,
  author    = {P\'{o}lya, George and Read, Ronald C.},
  title     = {Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds},
  publisher = {Springer-Verlag},
  year      = {1987}
}

@incollection{debruijn1964,
  author    = {de Bruijn, N. G.},
  title     = {P\'{o}lya's theory of counting},
  booktitle = {Applied Combinatorial Mathematics},
  editor    = {Beckenbach, Edwin F.},
  publisher = {Wiley},
  pages     = {144--184},
  year      = {1964}
}

@book{hararypalmer1973,
  author    = {Harary, Frank and Palmer, Edgar M.},
  title     = {Graphical Enumeration},
  publisher = {Academic Press},
  year      = {1973}
}

@book{vanlintwilson2001,
  author    = {van Lint, J. H. and Wilson, R. M.},
  title     = {A Course in Combinatorics},
  edition   = {2nd},
  publisher = {Cambridge University Press},
  year      = {2001}
}

@article{burnside1897,
  author    = {Burnside, William},
  title     = {Theory of Groups of Finite Order},
  publisher = {Cambridge University Press},
  year      = {1897}
}

@book{stanley2012ec1,
  author    = {Stanley, Richard P.},
  title     = {Enumerative Combinatorics, Volume 1},
  edition   = {2nd},
  publisher = {Cambridge University Press},
  year      = {2012}
}

Prerequisites

none — this is a leaf unit

Tier anchors

beginner: Brualdi 2010 *Introductory Combinatorics* (Pearson) Ch. 14 (necklaces, the Burnside count, colouring beads under rotation by hand); 3Blue1Brown / Mathologer 'counting under symmetry' style treatments of the cube-colouring problem
intermediate: van Lint-Wilson 2001 *A Course in Combinatorics* 2e (Cambridge) Ch. 35 (the cycle index, the Burnside/Cauchy-Frobenius lemma, Pólya's theorem and the pattern inventory, necklaces and the cube); Stanley 2012 *Enumerative Combinatorics* Vol. 1 2e (Cambridge) §7.24 (the exponential and cycle-index formalism)
master: van Lint-Wilson 2001 *A Course in Combinatorics* Ch. 35-36 (Pólya theory, the power group, de Bruijn's extension, graphical enumeration); Pólya-Read 1987 *Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds* (Springer) (the annotated translation of Pólya 1937); Harary-Palmer 1973 *Graphical Enumeration* (Academic Press) Ch. 2-4 (the pair group, counting graphs up to isomorphism); de Bruijn 1964 in Beckenbach *Applied Combinatorial Mathematics* Ch. 5 (the power-group enumeration theorem)

References

van Lint, J. H. & Wilson, R. M. — A Course in Combinatorics · Cambridge University Press, 2nd edition (2001). Chapter 35 develops counting under a group action: the Burnside / Cauchy-Frobenius orbit-counting lemma (number of orbits equals the average number of fixed points), the cycle index $Z(G)$ of a permutation group $G$ on $n$ points as a polynomial in $a_1, \ldots, a_n$ recording cycle types, Pólya's enumeration theorem obtained by substituting a figure-counting series into the cycle index, the pattern inventory, and the worked enumeration of necklaces, bracelets, cube colourings, and chemical isomers; Chapter 36 treats graphical enumeration via the pair group acting on edges.
Pólya, G. & Read, R. C. — Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds · Springer-Verlag (1987). Read's annotated English translation of Pólya's 1937 *Acta Mathematica* memoir 'Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen', the founding paper of the theory: the cycle index (Zyklenzeiger), the main enumeration theorem, and applications to counting trees, graphs, and the isomers of the alkanes and benzene derivatives.
Harary, F. & Palmer, E. M. — Graphical Enumeration · Academic Press (1973). Chapters 2-4 develop the configuration-counting series, Pólya's theorem, the pair group $G^{(2)}$ acting on the $\binom{n}{2}$ edges of $K_n$, and the resulting count of graphs, digraphs, and trees up to isomorphism; the power-group enumeration theorem is presented as the tool for enumerating functions modulo symmetries on both domain and range.
de Bruijn, N. G. — Pólya's theory of counting · Chapter 5 of E. F. Beckenbach (ed.), *Applied Combinatorial Mathematics* (Wiley, 1964). The systematic generating-function formulation of Pólya theory and the power-group enumeration theorem: counting orbits of the set of functions $Y^X$ under a group $A$ acting on $X$ and a group $B$ acting on $Y$, with the cycle index of the power group $B^A$ expressed through those of $A$ and $B$.

Estimated time

beginner: 18m
intermediate: 45m
master: 85m