Enumerative combinatorics

Se basa en

Requisitos previos obligatorios, hasta el fondo: 32

Aprenderás a

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

Definición

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

Teorema

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

Errores frecuentes

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

Descubrimientos opcionales

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

Lecturas complementarias

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