ConceptComplete

Pólya Enumeration Theorem

The Pólya Enumeration Theorem (PET) generalizes Burnside's lemma by incorporating a weight function on colorings. It provides a powerful generating function for counting distinct colorings under group symmetry, with applications throughout combinatorics, chemistry, and computer science.


The Theorem

Definition8.5Figure Counting Series

Given a group GG acting on a set DD of nn positions, and a set RR of colors (range) with a weight function w:RZ0w: R \to \mathbb{Z}_{\geq 0}, the figure counting series enumerates distinct colorings by weight. If the generating function for the colors is f(x)=rRxw(r)f(x) = \sum_{r \in R} x^{w(r)}, then the Pólya Enumeration Theorem expresses the generating function for distinct colorings.

Definition8.6Inventory

The inventory (or pattern inventory) of colorings under a group action is obtained by substituting the figure counting series into the cycle index. If the "figure series" is a+b+c+a + b + c + \cdots (one term per color), the inventory is: ZG(a+b+c+,a2+b2+c2+,,an+bn+cn+).Z_G(a + b + c + \cdots, a^2 + b^2 + c^2 + \cdots, \ldots, a^n + b^n + c^n + \cdots).

ExampleWeighted Necklace Counting

Count 4-bead necklaces with red (rr) and blue (bb) beads, tracked by color composition. Using ZC4=14(x14+x22+2x4)Z_{C_4} = \frac{1}{4}(x_1^4 + x_2^2 + 2x_4), substitute xkrk+bkx_k \to r^k + b^k: 14[(r+b)4+(r2+b2)2+2(r4+b4)]=r4+r3b+2r2b2+rb3+b4.\frac{1}{4}\left[(r+b)^4 + (r^2+b^2)^2 + 2(r^4+b^4)\right] = r^4 + r^3b + 2r^2b^2 + rb^3 + b^4. There is 1 necklace each of types rrrrrrrr, rrrbrrrb, rbbbrbbb, bbbbbbbb, and 2 necklaces of type rrbbrrbb.


The Dihedral Group

Definition8.7Dihedral Cycle Index

The dihedral group DnD_n of order 2n2n acts on nn positions by rotations and reflections. Its cycle index is: ZDn=12ZCn+{12x1x2(n1)/2if n is odd,14(x12x2(n2)/2+x2n/2)if n is even.Z_{D_n} = \frac{1}{2}Z_{C_n} + \begin{cases} \frac{1}{2}x_1 x_2^{(n-1)/2} & \text{if } n \text{ is odd}, \\ \frac{1}{4}\left(x_1^2 x_2^{(n-2)/2} + x_2^{n/2}\right) & \text{if } n \text{ is even}. \end{cases}

ExampleCounting Bracelets

A bracelet is a necklace considered up to both rotation and reflection. For 6-bead bracelets with 3 colors, the total count is ZD6(3,3,3,3,3,3)=112(729+3+9+27+3+81+81+27+27+9+27+27)=130Z_{D_6}(3, 3, 3, 3, 3, 3) = \frac{1}{12}(729 + 3 + 9 + 27 + 3 + 81 + 81 + 27 + 27 + 9 + 27 + 27) = 130 distinct bracelets.

RemarkApplications in Chemistry

The PET is essential in chemical enumeration: counting isomers of molecules. For example, the number of distinct substituted benzene rings C6H6kXkC_6H_{6-k}X_k is computed using ZD6Z_{D_6} with two colors (H and X). For dichlorobenzene (k=2k=2), there are exactly 3 isomers (ortho, meta, para).