Generating Functions, Combinatorial Enumeration & the Probabilistic Method

Generating functions encode combinatorial sequences as power series, making enumeration problems algebraic; the probabilistic method proves existence of combinatorial objects by showing a random construction succeeds with positive probability. Together they form two of the most powerful nonconstructive tools in discrete mathematics.

Concepts

Combinatorics asks two questions: "how many?" and "does one exist?" The answers use completely different techniques. Generating functions convert counting sequences into algebraic equations that can be solved symbolically; the probabilistic method bypasses counting entirely by showing a random construction succeeds with positive probability, guaranteeing existence without constructing the object.

Ordinary and Exponential Generating Functions

The ordinary generating function (OGF) of a sequence $(a_n)$ is the formal power series:

$A(x) = \sum_{n=0}^{\infty} a_n x^n$

Addition of sequences corresponds to addition of OGFs; convolution of sequences $(c_n = \sum_{k=0}^n a_k b_{n-k})$ corresponds to multiplication: $C(x) = A(x) \cdot B(x)$. This algebraic structure makes GFs ideal for counting objects built from independent parts.

The convolution rule $C(x) = A(x) \cdot B(x)$ is why power series are the natural representation for counting: most combinatorial structures are built by splitting into a left component of size $k$ and a right component of size $n - k$. Multiplying OGFs algebraically encodes this splitting — the coefficient of $x^n$ in the product is the sum over all splits, which is exactly the count by inclusion over partition points. The EGF uses $x^n/n!$ to handle labeling: labeled structures of size $n$ split in $\binom{n}{k}$ ways (choosing which labels go left), and the EGF product absorbs this binomial coefficient automatically via the product rule for EGFs.

For labeled structures where order matters, the exponential generating function (EGF) is:

$A(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$

The EGF of permutations is $\sum_{n\geq 0} n! \cdot x^n/n! = 1/(1-x)$. The EGF of derangements (permutations with no fixed points) is $e^{-x}/(1-x)$, since the derangement count is $D_n = n!\sum_{k=0}^n (-1)^k/k!$. The EGF of labeled rooted trees is the solution to $T(x) = x e^{T(x)}$ (by Lagrange inversion, $T(x) = \sum_{n \geq 1} n^{n-1} x^n/n!$, recovering Cayley's formula).

Fibonacci and Catalan Numbers via Generating Functions

Fibonacci: The recurrence $F_n = F_{n-1} + F_{n-2}$ with $F_0 = 0$, $F_1 = 1$ gives $F(x) = x/(1-x-x^2)$. Partial fractions with roots $\phi = (1+\sqrt{5})/2$, $\psi = (1-\sqrt{5})/2$ yield Binet's formula $F_n = (\phi^n - \psi^n)/\sqrt{5}$.

Catalan numbers: $C_n$ counts binary trees with $n$ internal nodes, triangulations of an $(n+2)$-gon, and Dyck paths of length $2n$. The recurrence $C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}$ says "split at the root." Taking OGF:

$C(x) = 1 + x \cdot C(x)^2$

Solving: $C(x) = (1 - \sqrt{1-4x})/(2x)$. Expanding via the generalized binomial theorem and using the saddle point method gives $C_n \sim 4^n / (n^{3/2}\sqrt{\pi})$.

The Probabilistic Method

The probabilistic method (Erdős, 1947) shows existence of a combinatorial object by constructing a probability space over all candidate objects and proving $\Pr[\text{object has desired property}] > 0$. Since the probability is positive, at least one such object exists — without constructing it.

Basic form: To show a graph with $n$ vertices and $m$ edges has chromatic number $\chi \geq k$, exhibit a probability distribution over colorings and show all have a monochromatic edge with positive probability.

Alteration method: First apply a random construction, then fix the small number of violations. Example: take a random subset of vertices by including each independently with probability $p$; vertices violating independence are removed. Optimizing $p$ gives the independence number lower bound $\alpha(G) \geq n/(2d)$ for $d$-regular graphs.

Lovász Local Lemma (LLL): Let $A_1, \ldots, A_m$ be "bad" events, each with probability at most $p$, and each depending on (sharing probability space structure with) at most $d$ other events. If:

$ep(d+1) \leq 1$

then $\Pr[\bigcap_i \overline{A_i}] > 0$ — all bad events can be avoided simultaneously. Here $e$ is Euler's number.

Ramsey Numbers and Graph Coloring Bounds

The Ramsey number $R(k,k)$ is the minimum $n$ such that every 2-coloring of the edges of $K_n$ contains a monochromatic $k$-clique. Ramsey (1930) showed $R(k,k)$ is finite; the probabilistic method gives the lower bound:

$R(k,k) > 2^{k/2}$

Proof: Color each edge of $K_n$ red or blue independently with probability $1/2$. For a fixed set of $k$ vertices, the probability all $\binom{k}{2}$ edges are the same color is $2 \cdot (1/2)^{\binom{k}{2}} = 2^{1-\binom{k}{2}}$. By union bound over $\binom{n}{k}$ sets:

$\Pr[\text{monochromatic } k\text{-clique exists}] \leq \binom{n}{k} \cdot 2^{1-\binom{k}{2}} < 1$

when $n < 2^{k/2}$. For such $n$, there exists a 2-coloring with no monochromatic $k$-clique, so $R(k,k) > n$.

For $k$-SAT: a CNF formula where each clause has exactly $k$ literals and each variable appears in at most $2^{k-2}$ clauses is always satisfiable. By LLL with $p = (1/2)^k$ (probability a random assignment falsifies one clause) and $d \leq k \cdot 2^{k-2}$ dependencies: $ep(d+1) \leq e \cdot 2^{-k} \cdot (k \cdot 2^{k-2} + 1) \leq ek/4 < 1$ for $k \geq 4$.

Worked Example

Catalan numbers via OGF. Start from $C(x) = 1 + x C(x)^2$. Rearranging: $xC^2 - C + 1 = 0$. Quadratic formula gives $C(x) = (1 \pm \sqrt{1-4x})/(2x)$. The minus sign is chosen so $C(0) = 1$ (use L'Hôpital: as $x \to 0$, $(1-\sqrt{1-4x})/(2x) \to 1$). Expanding $\sqrt{1-4x}$ via the generalized binomial theorem:

$\sqrt{1-4x} = \sum_{n=0}^{\infty} \binom{1/2}{n}(-4x)^n$

Extracting the coefficient of $x^n$ in $C(x)$ yields $C_n = \frac{1}{n+1}\binom{2n}{n}$. For $n = 4$: $C_4 = \frac{1}{5}\binom{8}{4} = 70/5 = 14$. The saddle-point asymptotics follow from the dominant singularity at $x = 1/4$: $C_n \sim 4^n/(n^{3/2}\sqrt{\pi})$.

Ramsey lower bound. For $k = 4$: the bound gives $R(4,4) > 2^2 = 4$. In fact $R(4,4) = 18$; the first moment calculation only gives $n < 4$, which is weak — the probabilistic bound is loose for small $k$ but becomes asymptotically tight in the logarithmic sense. For $k = 10$: $R(10,10) > 2^5 = 32$, while the true value is unknown (between 798 and 23556). The lower bound is exponential in $k/2$; the upper bound from the Erdős-Szekeres theorem is $\binom{2k-2}{k-1} \sim 4^k/\sqrt{k}$ — the gap between $2^{k/2}$ and $4^k$ remains a major open problem.

Applying LLL to 3-SAT. A 3-CNF formula has each clause with $k=3$ literals. Each clause is falsified by exactly one of $2^3 = 8$ assignments; a random assignment falsifies it with probability $p = 1/8$. Each clause shares variables with at most $3 \cdot (l-1)$ other clauses where $l \leq 2^{k-2} = 2$ clauses per variable: $d \leq 3 \cdot 1 = 3$. Check: $ep(d+1) = e \cdot (1/8) \cdot 4 = e/2 \approx 1.36 > 1$. The symmetric LLL fails here; the asymmetric LLL with variable-specific bounds is needed, confirming that 3-SAT satisfiability is more delicate than 4-SAT.

Connections

Where Your Intuition Breaks

The probabilistic lower bound gives $R(k,k) > 2^{k/2}$, and the recursion upper bound gives $R(k,k) \leq 4^k$. These bounds are separated by an exponential, and for $k \geq 5$ the true value of $R(k,k)$ is unknown. The gap has resisted decades of effort. The key misconception is that the probabilistic argument can be "made constructive" by analyzing its proof — it cannot. The proof shows a random coloring avoids a monochromatic clique with positive probability, but provides no way to identify which coloring is good. Derandomizing this argument (finding an explicit good coloring) is an open problem that would require fundamentally new combinatorial insights, not just tighter analysis of the probabilistic proof. The probabilistic method proves good objects are common without letting you find one.