Catalan Numbers — Dyck Paths & the Convolution Recurrence

Cₙ = C(2n,n)/(n+1) counts balanced parentheses, binary trees, triangulations, and Dyck paths.

Recurrence O(n²) Closed form O(n) Cₙ ~ 4ⁿ / (n^1.5 √π)
slow fast

Visualization

n = 3 Cₙ = 5 example 1/5 string = ((()))
up-step "(" down-step ")" current baseline (height 0)

Convolution: Cₙ = Σ Cᵢ · Cₙ₋₁₋ᵢ

Info

Press Play to trace a Dyck path, or Step through it. Toggle the interpretation to see the same n as a tree or a triangulated polygon.

Complexity

MethodTimeSpaceNote
Convolution recurrenceO(n²)O(n)builds the whole table
Closed form (incremental)O(n)O(1)Cₙ = Cₙ₋₁·2(2n-1)/(n+1)
Modular Cₙ mod pO(1)*O(n)after O(n) factorial precompute
Enumerate all structuresO(Cₙ·n)O(n)exponential ~4ⁿ
First values: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862

Operation Log