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

Cn=1n+1(2nn):1, 1, 2, 5, 14, 42, 132, 429, …C_n = \frac{1}{n + 1}\binom{2n}{n}: \qquad 1,\ 1,\ 2,\ 5,\ 14,\ 42,\ 132,\ 429,\ \ldots

starting from C0=1C_0 = 1. Each of these is counted by CnC_n:

ObjectsExample for n=3n = 3
strings of nn balanced pairs of parentheses((())), (()()), (())(), ()(()), ()()()
paths from (0,0)(0, 0) to (n,n)(n, n) with steps right and up, never above y=xy = x55 paths
ways to cut a convex (n+2)(n + 2)-gon into triangles with diagonals55 for a pentagon
binary trees with nn nodes55 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 (2nn)\binom{2n}{n} paths from (0,0)(0, 0) to (n,n)(n, n) in all. Take a bad path, one that touches the line y=x+1y = x + 1. Reflect the part of it after the first touch across that line. The path now ends at (n−1,n+1)(n - 1, n + 1) instead. Every path to (n−1,n+1)(n - 1, n + 1) arises this way exactly once, so bad paths number (2nn+1)\binom{2n}{n + 1}. Subtracting:

Cn=(2nn)−(2nn+1)=1n+1(2nn)C_n = \binom{2n}{n} - \binom{2n}{n + 1} = \frac{1}{n + 1}\binom{2n}{n}

Worked examples

Common mistakes

Practice problems

  1. Find C8C_8.

    Answer

    14301430

    Full solution

    19(168)=128709\tfrac{1}{9}\binom{16}{8} = \tfrac{12870}{9}.

  2. Find C6C_6.

    Answer

    132132

    Full solution

    17(126)=9247\tfrac{1}{7}\binom{12}{6} = \tfrac{924}{7}.

  3. How many strings of 44 pairs of balanced parentheses are there?

    Answer

    1414

    Full solution

    C4=14C_4 = 14.

  4. How many ways can a convex heptagon (77 sides) be cut into triangles by non-crossing diagonals?

    Answer

    4242

    Full solution

    n=7−2=5n = 7 - 2 = 5, and C5=42C_5 = 42.

  5. How many paths from (0,0)(0, 0) to (4,4)(4, 4) with right and up steps go above the diagonal at some point?

    Answer

    5656

    Full solution

    All paths: (84)=70\binom{8}{4} = 70. Good paths: 1414. Bad: 70−14=5670 - 14 = 56, which is (85)\binom{8}{5}.

  6. Find C7C_7.

    Answer

    429429

    Full solution

    18(147)=34328\tfrac{1}{8}\binom{14}{7} = \tfrac{3432}{8}.

  7. How many binary trees have 22 nodes?

    Answer

    22

    Full solution

    C2=2C_2 = 2: the second node hangs left or right of the root.

  8. A student says a convex pentagon has C5=42C_5 = 42 triangulations. How many does it have?

    Answer

    55

    Full solution

    A pentagon has 5=n+25 = n + 2 sides, so n=3n = 3 and C3=5C_3 = 5.

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.

What to learn next