Enumerative combinatorics

Builds on

Required prerequisites, all the way down: 32

You will learn to

• Use exponential generating functions to count labelled structures such as set partitions and derangements.
• Prove Euler's theorem that partitions into odd parts are equinumerous with partitions into distinct parts.
• Count colourings up to symmetry with Burnside's lemma and Pólya's theorem.

Definition

• A partition of n is a way of writing n as an unordered sum of positive integers.
• The exponential generating function of (aₙ) is Σ aₙxⁿ/n!.
• Burnside's lemma: a finite group G acting on a finite set X has (1/|G|) Σ_{g∈G} |Fix(g)| orbits.

Theorem

• The number of partitions of n into odd parts equals the number of partitions of n into distinct parts.
• The number of derangements of n objects is n! Σ_{k=0}^{n} (−1)ᵏ/k!.
• Burnside's lemma (also called the Cauchy–Frobenius lemma).

Common misconceptions

• Counting colourings up to symmetry by dividing by the size of the group; this fails when some colourings are themselves symmetric.

Optional discoveries

• Representation theory of finite groups Partitions of n index the irreducible complex representations of the symmetric group Sₙ.
• ← Combinatorics

Further reading

• Richard P. Stanley, Enumerative Combinatorics, Volume 1
• Herbert S. Wilf, generatingfunctionology (1990)