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)