Discrete Math · Undergraduate
Catalan Numbers: Paths, Parentheses and Triangulations
Quick answer
The Catalan numbers Cₙ = C(2n, n)/(n + 1) give 1, 1, 2, 5, 14, 42, 132, … They count many different things: strings of n pairs of balanced parentheses, lattice paths from (0, 0) to (n, n) that never rise above the diagonal, triangulations of a polygon with n + 2 sides, and binary trees with n nodes. The formula comes from the reflection trick, which counts the bad paths and subtracts them, and the numbers also satisfy the recurrence Cₙ₊₁ = C₀Cₙ + C₁Cₙ₋₁ + … + CₙC₀.
What you'll learn
- Compute Catalan numbers from the formula
- Recognize problems counted by Catalan numbers
- Count bad lattice paths with the reflection trick
- Use the Catalan recurrence
One sequence, many problems
The Catalan numbers are
starting from . Each of these is counted by :
| Objects | Example for |
|---|---|
| strings of balanced pairs of parentheses | ((())), (()()), (())(), ()(()), ()()() |
| paths from to with steps right and up, never above | paths |
| ways to cut a convex -gon into triangles with diagonals | for a pentagon |
| binary trees with nodes | trees |
A parenthesis string is a path in disguise: ”(” is a step right and ”)” is a step up. Staying balanced means never having more ”)” than ”(”, which is never going above the diagonal.
Why the formula works: reflection
There are paths from to in all. Take a bad path, one that touches the line . Reflect the part of it after the first touch across that line. The path now ends at instead. Every path to arises this way exactly once, so bad paths number . Subtracting:
Worked examples
Common mistakes
Practice problems
-
Find .
Answer
Full solution
.
-
Find .
Answer
Full solution
.
-
How many strings of pairs of balanced parentheses are there?
Answer
Full solution
.
-
How many ways can a convex heptagon ( sides) be cut into triangles by non-crossing diagonals?
Answer
Full solution
, and .
-
How many paths from to with right and up steps go above the diagonal at some point?
Answer
Full solution
All paths: . Good paths: . Bad: , which is .
-
Find .
Answer
Full solution
.
-
How many binary trees have nodes?
Answer
Full solution
: the second node hangs left or right of the root.
-
A student says a convex pentagon has triangulations. How many does it have?
Answer
Full solution
A pentagon has sides, so and .
Frequently asked questions
What is the formula for the Catalan numbers?
Cₙ = C(2n, n)/(n + 1), which equals C(2n, n) − C(2n, n + 1).
What are the first few Catalan numbers?
C₀ through C₇ are 1, 1, 2, 5, 14, 42, 132, 429.
What do Catalan numbers count?
Balanced strings of n pairs of parentheses, lattice paths to (n, n) staying on or below the diagonal, triangulations of an (n + 2)-gon, binary trees with n nodes, and many more.
What is the Catalan recurrence?
Cₙ₊₁ = Σ CₖCₙ₋ₖ for k from 0 to n, with C₀ = 1.