Dyck paths, polygon triangulations, and balanced parentheses
The Catalan numbers 1, 1, 2, 5, 14, 42, 132, ... are one of the most ubiquitous sequences in combinatorics. They count an astonishing variety of seemingly unrelated structures: paths that stay below a diagonal, ways to triangulate a polygon, matched parenthesizations, and full binary trees, among over 200 known interpretations.
The n-th Catalan number is Cₙ = C(2n, n) / (n+1). In this lesson, you will explore three of its most visual incarnations and discover the bijections connecting them.
A Dyck path of order n is a lattice path from (0, 0) to (n, n) using right and up steps that never crosses above the diagonal y = x. The number of such paths is exactly the Catalan number Cₙ. Step through all valid paths and see how the diagonal constraint shapes the count.
Dyck paths use R (right) and U (up) steps from (0,0) to (n,n) without crossing above the diagonal. The count equals the Catalan number C(n).
Key insight: The reflection principle proves the formula. Total paths from (0,0) to (n,n) = C(2n,n). Bad paths (those crossing the diagonal) biject with paths from (0,0) to (n-1,n+1) = C(2n,n-1). So valid paths = C(2n,n) - C(2n,n-1) = C(2n,n)/(n+1).
How many ways can you divide a convex (n+2)-gon into triangles using non-crossing diagonals? The answer is Cₙ, the n-th Catalan number. A triangle needs no diagonals (C₁ = 1), a quadrilateral has 2 triangulations (C₂ = 2), a pentagon has 5 (C₃ = 5), and so on.
Each triangulation divides the polygon into non-overlapping triangles using non-crossing diagonals. The count equals C(n-2), the Catalan number.
Key insight: The recurrence mirrors the Catalan recurrence: fixing one edge of the polygon, each triangulation splits the remaining polygon into two smaller polygons, giving Cₙ = Σ Cᵢ · Cₙ₋₁₋ᵢ.
Perhaps the most elegant aspect of Catalan numbers is that their many interpretations are connected by explicit bijections. Balanced parenthesizations of n pairs correspond one-to-one with Dyck paths of length 2n and with full binary trees having n internal nodes. Click any row to see the same structure across all three representations.
Each balanced parenthesization maps bijectively to a Dyck path and a full binary tree. All three are counted by the Catalan number.
Key insight: The bijection works by reading a parenthesization left to right: "(" becomes a right step (or a "go down to left child"), and ")" becomes an up step (or "go back up"). This same encoding connects dozens of Catalan structures.