A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
The Catalan numbers Cₙ = (1/(n+1))C(2n,n) count binary trees, proper parenthesizations, non-crossing matchings, plane partitions, and more. The generating function C(x) = (1 - √(1-4x))/2x satisfies xC(x)² - C(x) + 1 = 0, encoding recursive structure. Catalan numbers exemplify how generating functions reveal hidden recursive patterns.
Derive the Catalan recurrence Cₙ₊₁ = Σ CᵢCₙ₋ᵢ by analyzing how structures decompose, then verify the closed form via generating functions.
Catalan numbers appear in many contexts, but each involves a specific recursive decomposition; not every sequence of sizes gives Catalan numbers.
The Catalan numbers Cₙ (1, 1, 2, 5, 14, 42, 132, …) appear in an astonishing variety of counting problems. The unifying thread is not a surface-level similarity between the objects being counted, but a shared recursive decomposition structure. Once you see the pattern, you start recognizing Catalan numbers in new settings almost automatically.
Start with balanced parenthesizations: C₃ = 5 counts the 5 ways to write 3 pairs of matched parentheses (()()(), (())(), ()(()), (()()), ((()))). Why 5? Think about the first open parenthesis — it must match some specific closing parenthesis, splitting the string into an inner part and a right part. If the matching close is position 2k, the inner part has k−1 pairs and the right part has n−k pairs. Summing over all possible positions gives the Catalan recurrence: Cₙ = C₀Cₙ₋₁ + C₁Cₙ₋₂ + ⋯ + Cₙ₋₁C₀. The same decomposition counts full binary trees (split at the root into left and right subtrees), non-crossing handshakes among 2n people on a circle, and paths beneath the diagonal on a grid — different objects, identical recurrence.
From your study of generating functions, you know that a recurrence like Cₙ = Σᵢ CᵢCₙ₋₁₋ᵢ translates into an equation for the generating function C(x) = Σ Cₙxⁿ. The recurrence says C(x) satisfies xC(x)² = C(x) − 1, a quadratic in C(x) whose solution is C(x) = (1 − √(1−4x)) / (2x). Extracting the coefficient of xⁿ using the binomial series gives the closed form Cₙ = (1/(n+1))C(2n,n). This is the power of generating functions: the infinite tower of recurrence relations collapses to a single algebraic equation, and the closed form falls out from the algebra of power series.
The growth rate of Catalan numbers is roughly 4ⁿ/n3/2 (up to constants), growing faster than polynomials but slower than n!. This puts Catalan numbers in a distinct complexity class: the combinatorial structures they count are more numerous than polynomial but far fewer than all possible arrangements. Recognizing that a counting problem has this growth rate — or noticing that its objects decompose by splitting at a "first element" into two independent sub-problems of all possible sizes — is often the first sign that Catalan numbers are at work.