Enumerative Combinatorics

Counting Problems

Combinatorics answers the question: "How many?" — how many different objects of a given type exist. This is fundamental for algorithm theory, cryptography, and statistics.

The number of surjective functions from an n-element set to an m-element set (m ≤ n): $S(n,m) = \sum_{k=0}^m (-1)^k C(m,k)(m-k)^n$.

Stirling numbers of the second kind $S(n,k)$ denote the number of ways to partition an n-element set into k non-empty subsets. Recurrence: $S(n,k) = k \cdot S(n-1,k) + S(n-1,k-1)$.

The total number of all partitions: $B_n = \sum_k S(n,k)$ — Bell numbers.

Integer Partitions

A partition of a number $n$ is a way of representing $n$ as a sum of natural numbers (without regard to order).

$p(n)$ — the number of partitions. $p(1)=1$, $p(2)=2$, $p(3)=3$, $p(4)=5$, $p(5)=7$, ...

Ramanujan discovered surprising congruences: $p(5k+4) \equiv 0 \pmod{5}$. The Hardy–Ramanujan formula: $p(n) \sim \dfrac{e^{\pi\sqrt{2n/3}}}{4n\sqrt{3}}$ — asymptotics via analytic methods.

Vandermonde's Combinatorial Identity

$C(m+n, r) = \sum_{k=0}^r C(m, k) C(n, r-k)$.

Proof: selection of $r$ people from $m$ men and $n$ women.

Burnside's Lemma

The number of orbits under the action of a group $G$ on a set $X$: $|X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g|$, where $X^g$ are the fixed points of $g$.

Application: the number of necklaces of $n$ beads in $k$ colors (under rotations): $\frac{1}{n} \sum_{d \mid n} \varphi(d) \cdot k^{n/d}$. Pólya’s formula generalizes this to arbitrary permutations.

Combinatorics on Words and Sequences

Combinatorics on words examines finite sequences (words) over an alphabet. de Bruijn words: a cyclic sequence over a $k$-letter alphabet in which each word of length $n$ occurs exactly once. Length — $k^n$. Equivalent to an Eulerian cycle in the de Bruijn graph $B(k,n)$: vertices — words of length $n-1$, edges — words of length $n$. Applications in DNA sequencing and cryptography (LFSR, linear feedback shift registers).

Van der Waerden's theorem: For any coloring of the natural numbers with $k$ colors, some monochromatic subset contains arbitrarily long arithmetic progressions. Van der Waerden numbers $W(r; k)$ — the smallest $N$ with this property. $W(2;3) = 9$, $W(2;4) = 35$, $W(2;5) = 178$, $W(2;6) = 1132$. Growth is catastrophically fast.

The Generating Functions Method for Complex Enumerations

Transfer matrices (Transfer matrix method): For counting paths in a graph, tilings (mosaics), allowable configurations. If $A$ is the transition matrix, then $(A^n)_{ij}$ is the number of paths of length $n$ from $i$ to $j$. For tiling an $m \times n$ rectangle with dominoes: transfer matrix $2^m \times 2^m$, answer — a certain trace.

Kirchhoff’s formula via generating functions: The number of spanning trees $T(G) = \sum_{T} \prod_{e \in T} w_e$ (a weighted sum) is computed as the determinant of the weighted Laplacian. For unit weights, this is the ordinary Kirchhoff theorem. The weighted version is used in statistical physics (Ising model, partitions).

Bell Numbers and Set Partitions

Bell numbers $B_n$ count the number of partitions of an $n$-element set into non-empty subsets: $B_0=1$, $B_1=1$, $B_2=2$, $B_3=5$, $B_4=15$, $B_5=52$. Recurrence via the Bell triangle (same principle as Pascal's triangle). Exponential generating function: $\sum_n B_n x^n / n! = e^{e^x-1}$.

Applications: the number of ways to divide $n$ distinguishable tasks into indistinguishable groups. The number of variable partitions in symbolic computation. Number of equivalent configurations in physical systems.

Pólya's Theorem and Enumeration with Symmetries

Pólya’s theorem generalizes Burnside’s lemma, introducing "weight" for each configuration. The cycle index of a permutation group $G$ acting on $n$ positions: $Z(G; x_1, ..., x_n) = \frac{1}{|G|}\sum_{g \in G} x_1^{c_1(g)} \cdots x_n^{c_n(g)}$, where $c_k(g)$ is the number of $k$-cycles in $g$. For coloring with $m$ colors: substitute $x_k = m$, i.e., $Z(G; m, ..., m)$.

For necklaces of $n$ beads under the rotation group $C_n$: $Z(C_n) = \frac{1}{n} \sum_{d \mid n} \varphi(d) x_d^{n/d}$. For $n=6$, $m=3$ colors: number of necklaces $= \frac{1}{6}(3^6 + 3 + 2\cdot 3^2 + 2 \cdot 3^3) = \frac{1}{6}(729+3+18+54) = 134$. Taking flips into account (dihedral group $D_6$): $(134 + ...) / 2 \approx 92$ necklaces.

Asymptotics of Partitions and the Hardy–Ramanujan Formula

Partition numbers $p(n)$ grow rapidly: $p(1)=1$, $p(5)=7$, $p(10)=42$, $p(100)=190569292$. Hardy–Ramanujan formula (1918): $p(n) \sim \frac{1}{4n\sqrt{3}} e^{\pi\sqrt{2n/3}}$. The first accurate asymptotic expression for a rapidly increasing arithmetic function — one of the triumphs of analytic number theory. The "circle method" — decomposing the generating function via Fourier analysis and estimating it near singular points on the unit circle — has become a universal tool.

Connection to physics: the number of partitions equals the number of states of an ideal gas of fermions/bosons in statistical mechanics. $p(n)$ is the number of energy levels of a system at total energy $n$. This explains physicists’ interest in the exact Hardy–Ramanujan formula.

Symmetry Groups and Applications in Chemistry

In chemistry, the number of isomers of a molecule for a fixed formula is computed as the number of orbits under the action of the symmetry group (rotations and reflections). For alkanes $C_nH_{2n+2}$ (trees with colored edges) — this is an enumeration problem with group $S_4$ (tetrahedron). The Pólya cycle index generating function for counting organic molecules was computed in the 1930s and confirmed experimentally.

Numerical Example: Burnside’s Lemma and Partitions

Problem 1: Partitions for $n=6$ — how many are there? Problem 2: Coloring a necklace of 4 beads with 3 colors, counting rotations.

Step 1 (partitions): List all partitions of 6: {6}, {5+1}, {4+2}, {4+1+1}, {3+3}, {3+2+1}, {3+1+1+1}, {2+2+2}, {2+2+1+1}, {2+1+1+1+1}, {1+1+1+1+1+1}. $p(6)=11$.

Step 2 (partitions): Check by Euler’s recurrence: $p(6)=p(5)+p(4)-p(1)=7+5-1=11$. ✓

Step 3 (necklace): Rotation group of a necklace of 4 beads: $G = {e, r, r^2, r^3}$ (cyclic group $C_4$). $|G|=4$. $|X^e|=3^4=81$; $|X^r|=3$ (all 4 beads are the same color); $|X^{r^2}|=3^2=9$; $|X^{r^3}|=3$.

Step 4: $|X/G| = \frac{1}{4}(81+3+9+3) = 96/4 = 24$ distinct necklaces. Without symmetry, there would be 81; Burnside’s lemma reduced the count by 3.4 times.