Generating Functions for Competitive Combinatorics
How algebraic manipulation of power series solves combinatorial recurrences instantly.
Generating functions turn counting problems into algebra. That's the whole pitch, and it holds up under real contest pressure: a recurrence that looks hopeless as a direct combinatorial argument becomes a few lines of symbol manipulation once it's written as a power series, and coefficient extraction becomes a mechanical last step rather than a fresh insight a competitor has to conjure up.
Herbert Wilf, in the UCLA olympiad handout that most competitive programmers eventually stumble into, calls a generating function "a clothesline on which we hang up a sequence of numbers for display." That image does more work than any formal definition could. It sets the right posture toward the object: x isn't a number to plug things into, it's a placeholder holding a position open so a coefficient can sit there. Nobody asks whether the series converges, and nobody should, since convergence is an analyst's question. In a formal power series, x never gets evaluated, so radius of convergence never enters the picture, and that omission is precisely what makes the method usable under a contest clock.
The technique is old. Abraham de Moivre used it in 1730 to solve general linear recurrences, so the method was built, from its very first application, to do what contest problems keep asking for. Three centuries later, the target hasn't moved. A recurrence comes in, a generating function goes out, and the coefficients fall out of the algebra.
The three generating function types a competitor needs: OGF, EGF, and Dirichlet series
Most problems only need one of three flavors, and picking the right one before writing a single line of algebra saves a lot of wasted work later. Picking the wrong type turns a recurrence that would collapse in four lines into a page of unmanageable cross-terms. Get the type right, and the problem practically writes its own solution.
The ordinary generating function (OGF) is the default, and it should be the first thing a competitor reaches for unless the problem gives a specific reason not to. Write F(x) = Σ aₙxⁿ, and the coefficient of xⁿ is just aₙ, no rescaling involved. This is the natural language for unlabelled combinatorics: constant-coefficient recurrences, tiling problems, integer partitions, anything where the objects being counted don't come with distinguishable labels attached.
The exponential generating function (EGF) writes F(x) = Σ aₙxⁿ/n!, and it takes over the moment labels start mattering, once the order or identity of elements affects the count. Permutations, labelled trees, strings built from distinguishable symbols: all of these carry a factorial's worth of bookkeeping if counted directly. The EGF absorbs that bookkeeping into its definition, so multiplying two EGFs together produces the binomial coefficients automatically, with nothing tracked by hand. Forcing a recurrence involving factorials or binomial coefficients into an OGF causes the algebra to seize up almost immediately. Write the same recurrence with an EGF instead, and it often collapses into something solvable in a handful of steps, because the factorial weight the OGF was fighting against is the weight the EGF was built to carry. There's no ambiguity here: if labels matter, use the EGF, full stop.
Dirichlet series divide each term by nˢ instead of multiplying by xⁿ, and their home turf is number theory: multiplicative functions and Möbius inversion show up in number-theory subtasks rather than in the median contest problem. They come up less often in mainstream rounds, but when a problem leans on multiplicativity, nothing else on this list does the job as cleanly.
The operation dictionary: how algebraic moves on GFs correspond to combinatorial constructions
Generating functions are built from only two operations, addition and multiplication, and both map onto counting logic almost too cleanly to be a coincidence.
Addition, F(x) + G(x), encodes disjoint union: an object is either an F-structure or a G-structure. That's an OR statement, translated directly into algebra.
Multiplication, F(x)·G(x), encodes the Cartesian product: an ordered pair consisting of independent F- and G-structures. In the EGF setting this operation distributes labels between the two components via binomial coefficients without anyone having to compute those coefficients by hand. The algebra just produces them as a side effect of multiplying series together.
Then there's the geometric series, 1/(1 − F(x)), which stands for a sequence of F-structures of any length, the combinatorial version of a repeated-choice construction. Any construction that says "zero or more of these, one after another" turns into this single expression. Once these three moves, sum, product, geometric series, are second nature, most combinatorial specifications translate into GF equations almost by inspection.
Recurrences as the first contest application: from Fibonacci to the Catalan OGF
The Fibonacci recurrence is the training example everyone meets first, and for good reason: it shows the whole workflow in miniature. Starting from fₙ = fₙ₋₁ + fₙ₋₂, multiplying through by xⁿ, and summing over all valid n turns the recurrence into an algebraic equation. Collecting terms into F(x) = Σ fₙxⁿ and solving gives F(x) = x/(1 − x − x²). This walkthrough, laid out in zscoder's Codeforces tutorial on the subject, is the template every later recurrence problem in this space follows: multiply, sum, collect, solve.
The Catalan numbers push the same idea further, and this is where the "just solve the algebra" story starts to strain. The functional equation is self-referential: a Catalan generating function C(x) satisfies xC(x)² − C(x) + 1 = 0, encoding the recursive structure being counted (a balanced parenthesis, a binary tree's root, a triangulation's first cut). Solving this quadratic for F(x) gives F(x) = (1 − √(1 − 4C(x))) / (2C(x)), and now there's a square root sitting where a competitor needs a coefficient.
Extracting coefficients from an expression containing √(1 − 4x) is not an algebra-class operation. It calls for the generalized binomial theorem, which extends binomial expansion to non-integer exponents, and getting that expansion right by hand is exactly the kind of ad hoc work generating functions are supposed to eliminate. Lagrange inversion is the cleaner route, and it's the one worth reaching for by default: the theorem gives a direct formula for the coefficients of a compositional inverse, and applying it to the Catalan functional equation confirms cₙ = (1/(n+1))·C(2n, n) without ever expanding the square root by hand. The formula falls out of the functional equation itself, not out of a clever series manipulation.
Labeled structures and the EGF convolution property
The convolution property of EGFs is where the "automatic bookkeeping" claim from the operations section earns its keep. Multiplying two EGFs, F(x)·G(x), makes the nth coefficient of the product sum, over every way to split n labels into a group of size k and a group of size n − k, the product of the corresponding coefficients from each series weighted by C(n, k). Nobody writes that binomial coefficient down by hand. It's just there, produced by the algebra of power series multiplication.
The Part 1 tutorial on generating functions in competitive programming works through a derivation that shows how much leverage this buys. Faced with a difficult EGF B(x), the trick is to differentiate first: xB′(x) = xB(x)eˣ. Rearranging gives B′(x)/B(x) = eˣ, and integrating both sides gives ln B(x) = eˣ − 1. Exponentiate, and B(x) = exp(eˣ − 1). Four lines, start to finish, no combinatorial argument required at any step.
That closed form is not just an algebraic curiosity. B(x) = exp(eˣ − 1) is the EGF for the Bell numbers, the count of ways to partition an n-element set into non-empty subsets. The exp-of-EGF pattern, sometimes called the exponential formula, produces exactly this kind of result whenever the underlying construction is "a set of unordered groups." Any problem phrased as "in how many ways can n distinguishable objects be split into groups with property P" is a strong candidate for an EGF of the shape exp(P(x)), where P(x) is the EGF for a single group. Recognizing that shape on sight saves a lot of derivation time, and missing it is usually what separates a four-line solution from a forty-minute one.
Integer partitions: Euler's product, the pentagonal theorem, and efficient recursion
Partitions are where OGFs show their reach most clearly. Euler's product for the partition function p(n) is ∏_{j≥1} 1/(1 − xʲ), and each factor does exactly one job: encoding "any number of parts of size j," the geometric-series construction from the operations dictionary, applied once per part size and multiplied together across all sizes.
That product is elegant, but computing it term by term is still too slow at scale to be worth writing. The pentagonal number theorem is what fixes that: ∏{k=1}^∞ (1 − xᵏ) expands to 1 + Σ{k≥1} (−1)ᵏ (x^(k(3k+1)/2) + x^(k(3k−1)/2)), a series that is almost entirely zero. Only the generalized pentagonal numbers carry nonzero coefficients. That sparsity turns into a recursion, p(n) = Σ_{k≠0} (−1)^(k+1) · p(n − k(3k−1)/2), where the sum runs over O(√n) terms instead of over all of n. Against a brute-force convolution, that speedup means a subtask finishes instead of timing out.
The GF framing also gives away proofs that would otherwise demand real combinatorial cleverness. Take the theorem that the number of partitions of n into distinct parts equals the number of partitions of n into odd parts. The distinct-parts OGF and the odd-parts OGF can be shown equal by a short algebraic manipulation: multiplying through by ∏(1 − xʲ) inside the distinct-parts product cancels down to ∏(1/(1 − x^(2j−1))), precisely the odd-parts OGF. Two OGFs, one cancellation, proof done. A purely combinatorial bijection exists for this result too, but it takes far more setup to construct than the generating function argument takes to write down. Reach for the algebra first, and save the bijection for when a problem specifically demands one.
Polynomial multiplication via NTT: making GF operations implementable at contest scale
Everything above is only useful if it actually runs inside a time limit, and every one of those operations, sum, product, geometric series, EGF convolution, eventually reduces to multiplying two polynomials together. Multiplying naively is quadratic in the degree, fine for small n and a dead end for anything at contest scale.
The Fast Fourier Transform is what breaks that ceiling. Cooley and Tukey published the algorithm in 1965, dropping polynomial multiplication down to O(n log n). The idea wasn't new even then: Runge and König had described something similar in 1924, and Gauss had worked out the same structure in 1805 without ever publishing it. But the 1965 paper is the one that put the technique into circulation in computing, and it's the version every modern implementation traces back to.
Contest code should almost never use the floating-point FFT directly, though. Floating-point error is a real risk once degrees get large, and a wrong answer from rounding error is a much worse failure mode than a slow one, because a slow solution at least fails honestly. The Number Theoretic Transform (NTT) does the same job over integers, so results come out exact with no rounding. Under modulus 998244353, NTT supports transform lengths up to 2²³, which covers essentially every polynomial-size problem a contest is going to throw at a competitor. That modulus isn't arbitrary: it's a prime of the form 2ᵏ·c + 1 with a known primitive root, exactly the algebraic structure NTT needs to run correctly. 998244353 appears as the default modulus across so much competitive programming code because it was chosen to fit the transform, not the other way around.
Hard contest problems: descent permutations, roots-of-unity filtering, and the shape of a GF solution
zscoder's Part 2 tutorial poses a problem that shows what all of the above looks like when it's actually load-bearing rather than illustrative. A permutation p₁,..., pₙ of [n] is called k-good if pᵢ > p_{i+1} holds exactly when k divides i. The task is to count k-good permutations of length n, with both n and k as large as 5·10⁵.
A direct dynamic program runs in roughly O(n²/k), and at these constraints that's simply not fast enough. This is precisely the situation generating functions exist for: the combinatorial search space is too large to explore directly, so the problem has to get rebuilt as an algebraic one instead.
The roots-of-unity filter is the tool that does the rebuilding. Evaluating a generating function at roots of unity and combining the results isolates coefficients at selected index classes: a standard olympiad trick on its own. Generalize it to the k-th roots of unity instead of just ±1, and the same idea filters out coefficients at every position divisible by k, exactly the structural constraint the k-good condition imposes. The solution then expresses the final count in terms of polynomial operations computable in O(n log n) time using NTT. What started as a search over an exponentially large set of permutations ends as two polynomial computations and a division.
The Lagrange inversion theorem as a systematic coefficient-extraction tool
Lagrange inversion deserves to be named as its own tool rather than treated as a footnote to the Catalan derivation above, because its scope runs far beyond that one example. Given a functional equation of the form A(x) = xΦ(A(x)), the theorem hands over an explicit formula for the coefficients of A(x), written in terms of powers of Φ, without ever requiring A(x) to be solved for in closed form first. That last clause carries the entire value of the theorem: it skips the step that broke down for Catalan numbers, the one where a square root had to be expanded by hand.
That form, φ(x) = x·g(φ(x)), appears constantly in combinatorics, because it's the algebraic signature of one root, plus a set or sequence of substructures hanging off it. Trees decompose that way. So do many classes of planar maps, and a long list of other recursively defined objects. Anywhere a structure is built from a distinguished first piece followed by an arbitrary number of smaller copies of itself, this functional equation is waiting to be written down.
What Lagrange inversion buys a competitor is a shortcut past the usual combinatorial argument. For trees, permutations, and planar maps, the theorem produces an explicit counting formula straight from the functional equation, no bijective proof required. It's computation replacing insight, exactly the trade generating functions have been making since de Moivre first ran the same play in 1730.
The theorem is also not simply a finished piece of classical machinery sitting untouched in a textbook. A preprint submitted to arXiv in June 2025 (arXiv:2506.23214) revisits Lagrange inversion in the context of power series defined implicitly through functional equations, including the same classical equation x·g(φ(x)) = φ(x) discussed here. Nearly three centuries after de Moivre, the underlying idea, turning a self-referential definition into an explicit formula, is still generating new work, not just new applications of old work.
