Catalan Numbers

Discrete Math · Axiom Academy

EXAMPLE Catalan Numbers: Generating Function Derive the generating function from the recurrence relation and discover the remarkable structures counted by Catalan numbers. What do Catalan Numbers Count? The same sequence counts all of these different structures! Sequence: 1, 1, 2, 5, 14, 42, 132, ... Excellent work! You've derived the generating function for Catalan numbers. Here's what we learned: Universal Sequence: Catalan numbers count diverse combinatorial structures—binary trees, parenthesizations, Dyck paths, and polygon triangulations all follow the same sequence! Recurrence to Generating Function: By multiplying the recurrence C n = ∑C k C n-1-k by x n and summing, we transform it into an algebraic equation. Convolution Structure: The sum ∑C k C n-1-k becomes the product C(x)² in generating function language—this is the power of convolutions! Closed Form: The generating function C(x) = (1 - √(1-4x))/(2x) encodes all Catalan numbers and can be expanded using the binomial series. Boundary Condition: We chose the minus sign in the quadratic formula because C(0) = C₀ = 1, showing how initial conditions guide our solution. This generating function is a powerful tool in combinatorics. You can expand it using the generalized binomial theorem to find the explicit formula C n = (1/(n+1))·(2n choose n). Look for Catalan numbers in your next combinatorial problem—they appear more often than you might think!

This is the written version of the interactive lesson above. See the full Discrete Math course.