AdvancedMath for DSADynamic Programming
Catalan numbers: 1, 1, 2, 5, 14, 42…
Valid bracket strings, distinct BSTs, polygon triangulations: all Catalan numbers. Spot it and a hard count becomes a formula.
The idea
Cₙ counts structures that split into a left part and a right part around a root: pick what goes first (the root, the matching pair), then the two sides are independent. That gives Cₙ = Σ Cᵢ · Cₙ₋₁₋ᵢ, with C₀ = 1.
Closed form: Cₙ = C(2n, n) / (n + 1). The sequence grows fast (about 4ⁿ), so generating all of them is exponential even if counting is cheap.
Worked example
How many BSTs hold the values 1, 2, 3?
- Root 1: left has 0 values, right has 2 → C₀ · C₂ = 1 · 2 = 2
- Root 2: 1 value each side → C₁ · C₁ = 1
- Root 3: 2 left, 0 right → 2. Total 5 = C₃.
In code (Python)
def num_trees(n):
catalan = [1] + [0] * n
for nodes in range(1, n + 1):
for left in range(nodes): # left subtree size
catalan[nodes] += catalan[left] * catalan[nodes - 1 - left]
return catalan[n] # num_trees(3) == 5O(n²) with the recurrence, O(n) with the closed form.
How to spot it
- “how many structurally different trees / valid bracket strings / ways to split”, answers 1, 2, 5, 14 for small n.
Common mistakes
- Trying to generate every structure just to count them.
- Off by one: C₃ counts 3 nodes or 3 pairs of brackets.
Where it comes up
Go further
Up next for you · Beginner
“Have I seen this?” is a set →