Mathematics.

algebraic combinatorics

Pólya Enumeration

Combinatorics40 minDifficulty3 out of 10

You should know: group mathematics, permutations

Overview

Pólya enumeration counts distinct colorings or arrangements of objects when configurations related by a symmetry (such as rotation or reflection) are considered identical. It builds on Burnside's lemma, which computes the number of distinct colorings as the average, over all symmetries in a group, of the number of colorings fixed by that symmetry. This technique is the standard tool for counting things like distinct necklaces, dice colorings, or molecular structures up to rotational symmetry.

Intuition

Naively counting colorings of, say, the 4 vertices of a square with 2 colors gives 2⁴=16 colorings, but many of these become identical once you allow rotating the square — e.g. all-one-color-on-two-adjacent-vertices colorings that are rotations of each other should be counted once, not four times. Burnside's lemma fixes this by averaging: for each symmetry (each of the 4 rotations of the square), count how many colorings are left unchanged by that rotation, then average over all 4 rotations. Rotations that move things around a lot (like 90°) fix very few colorings, while the identity rotation fixes all of them — averaging accounts for exactly how much 'overcounting' each symmetry causes.

Formal Definition

Definition

Burnside's lemma (the counting foundation behind Pólya's theorem) states that the number of distinct colorings under a symmetry group G is:

∣X/G∣=1∣G∣∑g∈G∣Xg∣|X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g|
Burnside's lemma
∣Xg∣=number of colorings fixed by symmetry g|X^g| = \text{number of colorings fixed by symmetry } g
Fixed colorings under g

Worked Examples

  1. The rotation group has 4 elements: identity, 90°, 180°, 270°. Count colorings fixed by each.

    ∣Xe∣=24=16 (identity fixes all colorings)|X^{e}| = 2^4 = 16 \text{ (identity fixes all colorings)}

  2. A 90° or 270° rotation fixes a coloring only if all 4 vertices share the same color (since rotation cycles all 4 vertices in one 4-cycle).

    ∣X90°∣=2,∣X270°∣=2|X^{90°}| = 2, \quad |X^{270°}| = 2

  3. A 180° rotation swaps vertices in 2 pairs, so it fixes colorings where each pair matches: 2 choices per pair.

    ∣X180°∣=22=4|X^{180°}| = 2^2 = 4

  4. Average by Burnside's lemma.

    ∣X/G∣=16+2+4+24=244=6|X/G| = \frac{16+2+4+2}{4} = \frac{24}{4} = 6

Answer: There are 6 distinct 2-colorings of a square's vertices up to rotation.

Practice Problems

Difficulty 5/10

Using Burnside's lemma with the rotation group of the square (identity, 90°, 180°, 270°), confirm the average (16+2+4+2)/4 equals 6.

Difficulty 4/10

How many colorings are fixed by the 180° rotation of the square (2 colors, 4 vertices, pairs (1,3) and (2,4) swapped)?

Difficulty 6/10

How many colorings are fixed by a 90° (or 270°) rotation of the square's 4 vertices with 2 colors?

Quiz

Burnside's lemma computes the number of distinct colorings under a group G as:
For the square's rotation group and 2-colorings of its 4 vertices, the number of distinct colorings up to rotation is:
Under a 90° rotation of a square's 4 vertices, a coloring is fixed only if:

Summary

  • Pólya enumeration (via Burnside's lemma) counts colorings/arrangements up to symmetry by averaging fixed-point counts over a symmetry group.
  • Burnside's lemma: |X/G| = (1/|G|) ∑_g |X^g|, where |X^g| is the number of colorings unchanged by symmetry g.
  • Verified example: 2-colorings of a square's 4 vertices under rotation give 6 distinct colorings, from (16+2+4+2)/4.

References

  1. WebsiteWikipedia — Pólya enumeration theorem