🔢 Catalan Numbers
Written by MySimulator Team · Reviewed by MySimulator Editorial Review
Last updated: 5 July 2026
One count, many shapes. Balanced parentheses, Dyck paths, binary trees, polygon
triangulations and non-crossing chord diagrams are all counted by the same number Cₙ
because there are bijections between them. A "(" is an up-step and a tree's left
subtree; a ")" is a down-step and the right subtree. Triangulating an (n+2)-gon by
choosing the triangle on a fixed edge splits it exactly like the recurrence
Cₙ₊₁ = Σ Cᵢ·Cₙ₋ᵢ. So solving one problem solves all five.
About Catalan Numbers
The Catalan numbers C₀ = 1, C₁ = 1, C₂ = 2, C₃ = 5, C₄ = 14, C₅ = 42, … are one of the most pervasive sequences in combinatorics, arising in dozens of apparently unrelated counting problems. The formula Cₙ = (2n)! / ((n+1)! n!) was studied by Euler, Segner, and Catalan in the 18th–19th centuries. The key insight, proved by the existence of explicit bijections (one-to-one correspondences), is that balanced bracket strings, Dyck lattice paths, full binary trees, triangulations of a convex polygon, and non-crossing chord diagrams are all counted by exactly the same number Cₙ — so a solution to any one problem automatically solves all the others.
This simulation lets you explore all five bijections simultaneously for n = 0 to 8. Choose "Show all" to display every Cₙ object at once, or "Sample" to animate a random walk through the set. The bar chart below shows the Catalan sequence C₀ … Cₙ growing exponentially (Cₙ ~ 4ⁿ / (n^(3/2) √π)), and the formula panel updates live as you step through objects, showing both the explicit formula and the ratio C_(n+1)/Cₙ converging towards 4.
Frequently Asked Questions
What is a Catalan number?
Cₙ is the number of ways to perform a combinatorial task that has a certain recursive structure — specifically, any task that can be split into two independent sub-tasks of sizes 0 and n–1, or 1 and n–2, …, or n–1 and 0. The closed form is Cₙ = (2n)! / ((n+1)! n!) = C(2n, n) / (n+1), where C(2n, n) is the central binomial coefficient. The first few values are 1, 1, 2, 5, 14, 42, 132, 429, 1430, and the sequence grows asymptotically as Cₙ ~ 4ⁿ / (n^(3/2) √π).
What are balanced bracket (parenthesis) strings and how do they relate to Cₙ?
A balanced bracket string of length 2n is a sequence of n opening brackets "(" and n closing brackets ")" such that no prefix contains more ")" than "(". For n = 3 there are exactly C₃ = 5 such strings: ((())), (()()), (())(), ()(()), ()()(). These strings arise in parsing expressions, valid HTML nesting, and the stack-sortable permutations problem. The bijection to Dyck paths is direct: "(" maps to an up-step and ")" to a down-step, so the no-negative-prefix rule becomes the no-below-axis rule.
What is a Dyck path?
A Dyck path of length 2n is a lattice path from (0, 0) to (2n, 0) that takes n up-steps (+1) and n down-steps (–1) and never dips below the x-axis. There are Cₙ such paths. They were studied by the German mathematician Walther von Dyck and appear in the analysis of ballot sequences (the probability that candidate A is strictly ahead throughout a vote count), random walks that must stay non-negative, and the enumeration of sequences in formal language theory (e.g. valid Lisp programs with matched parentheses).
How does triangulation of a convex polygon give Cₙ?
A convex (n+2)-gon can be divided into triangles by drawing n–1 non-crossing diagonals; the number of ways to do this is Cₙ. For a quadrilateral (n = 2): two triangulations. For a pentagon (n = 3): five triangulations. The bijection to bracket strings works by fixing one edge of the polygon as the "root" and noticing that the triangle on that edge splits the remaining polygon into two smaller polygons, mirroring the Catalan recurrence Cₙ = Σᵢ₌₀ⁿ⁻¹ Cᵢ Cₙ₋₁₋ᵢ. Triangulations arise in computational geometry (optimal polygon triangulation, Delaunay triangulation), numerical methods (finite-element meshing), and compiler design (syntax trees).
What are non-crossing chord diagrams?
A non-crossing chord diagram consists of 2n points on a circle connected by n non-intersecting chords. The C₃ = 5 ways to connect 6 points with 3 non-crossing chords are exactly the five Catalan objects for n = 3. These diagrams appear in RNA secondary structure prediction (base pairs are non-crossing chords on the sequence), knot theory (Temperley–Lieb algebras), and free probability (non-crossing partitions define the free cumulants of probability distributions). The number of non-crossing partitions of {1, …, n} is also Cₙ.
What is the recurrence relation for Catalan numbers?
The Catalan numbers satisfy the recurrence C₀ = 1 and Cₙ₊₁ = Σᵢ₌₀ⁿ Cᵢ Cₙ₋ᵢ. This formula reflects the "divide at the root" structure common to all five bijective families: for a bracket string, the root "(" is closed at some position, splitting the string into two independent balanced sub-strings of lengths 2i and 2(n–i). Summing over all split positions gives the recurrence. The generating function C(x) = Σ Cₙ xⁿ satisfies x C(x)² – C(x) + 1 = 0, with solution C(x) = (1 – √(1 – 4x)) / (2x).
Why do so many combinatorial problems produce Catalan numbers?
The unifying reason is that all Catalan families share the same recursive structure: an object of size n can be uniquely constructed by choosing a "root" that splits the remaining data into two independent sub-objects of sizes i and n–1–i (or similar), summing over all splits. This is exactly the Catalan recurrence. Bijections between these families are often elegant: a "(" in a bracket string becomes a left-child edge in a binary tree and an up-step in a Dyck path, so the combinatorial data is literally the same object in three different costumes.
How fast do Catalan numbers grow?
Catalan numbers grow exponentially: by Stirling's approximation, Cₙ ~ 4ⁿ / (n^(3/2) √π). The ratio Cₙ₊₁/Cₙ = 2(2n+1)/(n+2) converges to 4, so each successive Catalan number is roughly four times the previous one. C₁₀ = 16,796; C₂₀ ≈ 6.56 × 10¹⁰; C₅₀ ≈ 1.37 × 10²⁸. For n = 8 (the maximum in this simulation) C₈ = 1,430 — enough to draw all objects individually. Beyond n ≈ 10 it becomes impractical to enumerate them all and random sampling must be used.
What are full binary trees and how do they count Cₙ?
A full binary tree is a rooted tree in which every internal node has exactly two children (never one). The number of full binary trees with n+1 leaves is Cₙ. For n = 3: C₃ = 5 trees with 4 leaves. The bijection to bracket strings sends each leaf to ")" and each internal node to "(", reading the tree left-to-right in preorder. Full binary trees are the structure of expression parsing, Huffman coding, and the Stern–Brocot tree for fractions. They also count the number of ways to fully parenthesise a product of n+1 factors — Euler's original formulation of the problem (1751).
Who first discovered Catalan numbers?
Euler counted polygon triangulations in 1751 and found the sequence 1, 2, 5, 14, 42, … but did not have the closed form. Segner found the recurrence in 1758. The Belgian mathematician Eugène Charles Catalan gave the closed formula Cₙ = (2n)!/((n+1)!n!) in 1838, and the sequence now bears his name. However, the sequence had been discovered even earlier by the Chinese mathematician Ming Antu around 1730 in connection with trigonometric expansion formulas. The story of their simultaneous, independent discoveries is a vivid example of mathematical universality.
Where do Catalan numbers appear outside pure mathematics?
Catalan numbers appear in computer science (number of stack-sortable permutations, number of distinct binary search trees with n keys, number of monotone Boolean functions on 2 variables), bioinformatics (RNA secondary structures counted by their non-crossing bracket structure), physics (non-crossing Feynman diagrams in planar quantum field theory, moments of the Wigner semicircle law in random matrix theory), and linguistics (number of parse trees for an ambiguous context-free grammar with a specific rule structure). Stanley's "Catalan Numbers" (2015) lists 214 distinct combinatorial interpretations.