Explore Catalan numbers, generating functions, and the surprising connections between binary trees, Dyck paths, and parenthesizations
How many binary trees have n nodes? How many ways can we parenthesize an expression? These questions lead to the beautiful Catalan numbers, one of the most ubiquitous sequences in combinatorics.
Even more remarkably, generating functions let us solve counting problems algebraically. Instead of counting directly, we encode counts as coefficients of a power series, then manipulate the series to extract formulas automatically.
In this section, you'll discover the bijections between trees, paths, and parentheses, see generating functions in action, and explore how memoization transforms exponential recursion into efficient algorithms.
The nth Catalan number Cn counts binary trees with n internal nodes, Dyck paths of length 2n, and balanced parenthesizations with n pairs. These are all in bijection — select any structure and see its counterparts!
These three structures are in bijection — there's a one-to-one correspondence between them. Each binary tree corresponds to exactly one Dyck path and one parenthesization. The Catalan number Cn counts all of them!
The generating function C(x) = Σ Cnxn satisfies the equation C(x) = 1 + x·C(x)². Solving this quadratic algebraically derives the closed form for Catalan numbers — no counting required!
A binary tree is either empty (1) or a root with two subtrees (x · C(x)²)
This is a quadratic in C(x)!
We need C(0) = 1, so we take the minus sign (the plus would give ∞ at x=0)
The binomial series of √(1-4x) gives us the Catalan numbers!
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| Cn | 1 | 1 | 2 | 5 | 14 | 42 | 132 | 429 | 1430 |
The coefficient of xn in C(x)² is Σi=0n Ci·Cn-i
Instead of counting directly, we encode counts as coefficients of a formal power series. Algebraic manipulation (solving the quadratic) automatically derives the formula! This technique handles complex recurrences that would be hard to solve directly.
Many counting recurrences (Fibonacci, Catalan, binomial coefficients) have overlapping subproblems. Memoization transforms exponential recursive trees into polynomial DAGs. Watch the computation unfold and count the actual work done.
Without memoization, recursive calls form a tree with exponential nodes. With memoization, we only compute each unique subproblem once. The call structure becomes a DAG (Directed Acyclic Graph), reducing exponential time to polynomial time.
The Bell number Bn counts ways to partition a set of n elements into non-empty subsets. The Stirling numbers S(n,k) refine this count by number of blocks. These appear in clustering and database optimization.
S(n, k) = number of ways to partition n elements into exactly k non-empty blocks
| n\k | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 |
| 2 | 0 | 1 | 1 | 0 | 0 |
| 3 | 0 | 1 | 3 | 1 | 0 |
| 4 | 0 | 1 | 7 | 6 | 1 |
First element of each row = Bell number Bn
Bell numbers grow super-exponentially: B1=1, B5=52, B10=115,975. This rapid growth appears in clustering problems, database query optimization, and anywhere we need to consider all possible groupings.
You now have powerful tools for counting structures:
Next: We'll analyze divide-and-conquer algorithms with the Master Theorem, understanding exactly when T(n) = aT(n/b) + f(n) gives O(n log n) versus O(n²).