Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 36 ยท Partitions and Catalan Numbers

Catalan Numbers

Learn the Catalan numbers 1, 1, 2, 5, 14, 42: derive the recurrence, use the binomial formula, count balanced parentheses and draw Dyck paths in Python.

The Catalan numbers 1, 1, 2, 5, 14, 42, 132, 429, 1430, ... are among the most common sequences in counting. They count balanced parentheses, binary trees, ways to triangulate a polygon, paths that stay below a diagonal, and dozens of other objects. If a counting problem has a "never go negative" flavor, think Catalan.

Balanced parentheses: the model problem

A string of n pairs of parentheses is balanced if every prefix has at least as many ( as ), and the totals are equal. For n = 3 there are 5:

((())), (()()), (())(), ()(()), ()()()

Let C_n be the number of balanced strings with n pairs.

The recurrence

Every non-empty balanced string starts with (, and that bracket is matched by some ) at a unique position. Inside the pair is a balanced string with i pairs; after the pair, a balanced string with n-1-i pairs. Summing over all i:

C_0 = 1, C_n = C_0 C_{n-1} + C_1 C_{n-2} + ... + C_{n-1} C_0.

This is a full-history convolution, so the generating function C(x) satisfies C(x) = 1 + x C(x)^2, which gives C(x) = (1 - sqrt(1 - 4x))/(2x) and, by the binomial series, the closed form:

C_n = (1/(n+1)) * binom(2n, n) = binom(2n, n) - binom(2n, n+1).

There is also a pleasant ratio recurrence C_{n+1} = C_n * 2(2n+1)/(n+2), which computes the sequence with integer arithmetic only.

Python Three ways to compute C(n)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

C_30 = 3,814,986,502,092,304. The recursion is quadratic time with memoization, the formula and ratio forms are fast.

Why binom(2n,n) / (n+1): the cycle lemma idea

There are binom(2n, n) strings with n opening and n closing brackets. Among the n+1 cyclic rotations of the string ( x n followed by ) x n with one extra ) appended, exactly one is valid. A cleaner version is the reflection principle, shown in the next lesson: count the bad strings and subtract.

Generating and drawing

Generate all balanced strings by backtracking: you may add ( while fewer than n have been opened, and you may add ) only while there are more opens than closes. Never exploring dead ends gives exactly C_n leaves.

A balanced string is the same thing as a Dyck path: read ( as an up step / and ) as a down step \; the path starts and ends at height 0 and never goes below it.

Python Enumerate balanced strings and draw a Dyck path

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The backtracking tree is also a nice picture of the sum rule:

flowchart TD
    S["(  :  opened 1, closed 0"] --> A["((  : opened 2"]
    S --> B["()  : closed 1"]
    A --> A1["(((  or  (()"]
    B --> B1["()(  : only choice besides stopping"]

Each prefix extends with ( if opens remain and with ) if there is an unmatched open bracket.

Growth

C_n grows like 4^n / (n^{3/2} sqrt(pi)). The ratio C_{n+1}/C_n approaches 4, which you can see plotted in Practice Set: Advanced Counting.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is C(5), the number of balanced strings with 5 pairs of parentheses?

    The sequence is 1, 1, 2, 5, 14, 42, so C(5) = 42 = binom(10,5)/6.
  2. 2. Which formula gives the Catalan numbers?

    C(n) = binom(2n,n)/(n+1), for example binom(6,3)/4 = 5.
  3. 3. In the recurrence C(n) = sum of C(i) C(n-1-i), what do i and n-1-i represent?

    The first ( pairs with a ); the part inside has i pairs and the part after has n-1-i.
  4. 4. In the backtracking generator, when may you append a closing bracket?

    A prefix must never have more ) than (, so ) needs an unmatched ( before it.

Summary

  • C_n = binom(2n,n)/(n+1) counts balanced strings of n pairs; the sequence is 1, 1, 2, 5, 14, 42, ...
  • Recurrence C_n = sum C_i C_{n-1-i}; generating function C(x) = 1 + x C(x)^2.
  • Balanced strings are Dyck paths; backtracking generates them without waste.

Next: Catalan Structures