Combinatorics¶
Job: Count and construct discrete configurations; use generating functions, bijections, and Pólya-type symmetry reduction.
Core¶
Twelvefold way (sketch): count functions \(N\to X\) under restrictions (injective/surjective) and identification of domain/codomain up to permutation — yields \(x^n\), \(x^{\underline n}\), Stirling, Bell, partitions, etc.
Binomial / multinomial: $$ \binom{n}{k_1,\ldots,k_m}=\frac{n!}{k_1!\cdots k_m!},\quad \sum k_i=n. $$
Recurrences: Fibonacci-type linear recurrences \(\leftrightarrow\) rational OGF. Catalan \(C_n=\frac1{n+1}\binom{2n}{n}\): Dyck paths, binary trees, noncrossing partitions; \(C(x)=\sum C_n x^n=(1-\sqrt{1-4x})/(2x)\).
Generating functions.
- OGF: \(A(x)=\sum a_n x^n\), product \(\leftrightarrow\) convolution of unlabeled structures.
- EGF: \(\hat A(x)=\sum a_n x^n/n!\), labeled products / set constructions (Joyal species).
- Pólya enumeration: for a group \(G\) acting on colorings of a set \(X\), number of orbits is
$$
\frac1{|G|}\sum_{g\in G} k^{c(g)}
$$
(\(k\) colors, \(c(g)=\#\) cycles of \(g\) on \(X\)) — cycle index specialization. Burnside is the \(k\)-color case.
Extremal (pointer): Erdős–Ko–Rado, Turán \(T(n,r)\) ex for \(K_{r+1}\)-free graphs, Szemerédi regularity.
Probabilistic method: show \(\mathbb{P}(X\in\mathcal{P})>0\) for random constructions \(\Rightarrow\) existence; Lovász Local Lemma for rare dependent events; alteration method.
Double counting / bijections: preferred over pure induction when structure is available (e.g. Prüfer codes \(\leftrightarrow\) trees on \(n\) labeled vertices: \(n^{n-2}\)).
See it¶
Burnside on necklaces: \(n\) beads, \(k\) colors, rotations \(C_n\): number of distinct necklaces $$ \frac1n\sum_{d\mid n}\varphi(d)\,k^{n/d}. $$ (Dihedral case adds flips — full Pólya cycle index of \(D_n\).)
Check¶
Derive the Catalan OGF equation \(C=1+xC^2\).
First return decomposition of Dyck paths / binary trees: empty or root with left/right Catalan factors. Solve quadratic: \(C(x)=(1-\sqrt{1-4x})/(2x)\) with \(C(0)=1\).
Why does Burnside average fixed colorings rather than count stabilizers directly?
Orbit-stabilizer: \(|G|=|\mathrm{Orb}(x)||\mathrm{Stab}(x)|\). Averaging \(|\mathrm{Fix}(g)|\) equals number of orbits (Burnside lemma). Stabilizer route requires orbit representatives first.
Pitfalls¶
- Labeled vs unlabeled: EGF vs OGF mismatch is the standard error.
- Pólya counts orbits of colorings, not up to color permutation unless the group includes recoloring.
- Asymptotics from GF singularities need transfer theorems — ratio tests alone are crude.
Refs¶
Stanley EC1–2; Flajolet–Sedgewick; van Lint–Wilson; Aigner, A Course in Enumeration; Cameron.