Enumerative combinatorics

前置知识

32 项必需的前置知识（一直追溯到底）

你将学会

• 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.

定义

• 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.

定理

• 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).

常见误解

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

可选发现

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

延伸阅读

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