Catalan Numbers — Mathematics Knowledge System

Overview

The Catalan numbers Cₙ form a sequence 1, 1, 2, 5, 14, 42, 132, … that counts an enormous variety of combinatorial structures: the number of valid balanced-parenthesis sequences with n pairs, the number of ways to triangulate a convex polygon with n+2 sides, the number of full binary trees with n+1 leaves, and the number of monotonic lattice paths from (0,0) to (n,n) that never rise above the diagonal. Despite the apparent diversity of these problems, they all satisfy the same recurrence and closed form, making the Catalan numbers one of the most ubiquitous sequences in combinatorics.

Intuition

The formula C_n = C(2n,n)/(n+1) comes from a reflection/cycle-lemma argument: among all C(2n,n) lattice paths with n up-steps and n down-steps, only a fraction 1/(n+1) never dip below the starting level. The recursive form C_{n+1} = ∑ C_i C_{n-i} reflects a 'split at the first return to zero' idea — any balanced parenthesis sequence of length 2(n+1) can be uniquely written as '(' + (a balanced sequence of length 2i) + ')' + (a balanced sequence of length 2(n-i)), for some split point i, and summing over all possible splits reproduces the full count.

Formal Definition

Definition

The n-th Catalan number has the closed form and recurrence:

C_n = \frac{1}{n+1}\binom{2n}{n}

Closed form

C_n = \binom{2n}{n} - \binom{2n}{n+1}

Equivalent closed form

C_{n+1} = \sum_{i=0}^{n} C_i\,C_{n-i}

Recursive (convolution) formula

Worked Examples

Apply the formula with n=3.
$C_3 = \frac{1}{4}\binom{6}{3} = \frac{1}{4}(20) = 5$

Answer: C_3 = 5, matching the 5 ways to fully parenthesize a product of 4 factors, e.g. ((ab)c)d, (a(bc))d, (ab)(cd), a((bc)d), a(b(cd)).

Practice Problems

Difficulty 3/10

Compute C_5 using the closed form C_n = C(2n,n)/(n+1).

Difficulty 4/10

How many valid sequences of 3 pairs of balanced parentheses are there (e.g. ()()() is one)?

Difficulty 5/10

In how many ways can a convex hexagon (6 sides) be divided into triangles by non-crossing diagonals?

Quiz

Summary

Catalan numbers 1,1,2,5,14,42,... satisfy C_n = C(2n,n)/(n+1) and the convolution recurrence C_{n+1}=∑C_iC_{n-i}.
They count balanced parenthesizations, polygon triangulations, non-crossing lattice paths, and full binary trees, among many other structures.
The same closed form and recurrence apply across all these seemingly different combinatorial problems.

References

WebsiteWikipedia — Catalan number