Catalan Numbers: The Sequence That Counts Everything

The definition

The nth Catalan number, written C(n), is defined as one divided by (n+1), multiplied by the binomial coefficient (2n choose n). Equivalently it can be written without any division at all as (2n choose n) minus (2n choose n+1), which is the same integer arrived at from two binomial coefficients that sit next to each other in Pascal's triangle. The sequence begins C(0) = 1, C(1) = 1, C(2) = 2, C(3) = 5, C(4) = 14, C(5) = 42, C(6) = 132, and grows quickly from there — every term is a whole number even though the formula involves division, which is itself a small piece of mathematical magic worth noticing.

C(n) = 1/(n+1) * C(2n, n) = C(2n, n) - C(2n, n+1)

worked example, n = 3:
  C(6, 3) = 20
  C(3) = 20 / (3+1) = 20 / 4 = 5

n :  0   1   2   3   4    5    6
Cn:  1   1   2   5  14   42  132

The recurrence — and why it shows up everywhere

Catalan numbers also satisfy a recurrence: C(0) = 1, and C(n+1) equals the sum, as i runs from 0 to n, of C(i) times C(n-i). This convolution falls directly out of splitting a structure of size n+1 at its "root" into a left part of size i and a right part of size n-i — the two parts are independent, so the number of ways to build the whole thing is the product of the ways to build each half, summed over every possible split point. This single idea is why the exact same sequence turns up in structures that look nothing alike: any object that can be decomposed the same way, a smaller piece nested or attached to a smaller remaining piece, ends up obeying this recurrence and therefore ends up counted by Catalan numbers.

Balanced parentheses and Dyck paths

C(n) counts the number of ways to arrange n pairs of balanced parentheses. For n = 3 there are exactly 5: ((())), (()()), (())(), ()(()), ()()(). A Dyck path is a lattice path from (0,0) to (2n,0) built from up-steps of (1,1) and down-steps of (1,-1) that never dips below the x-axis, and it is in direct bijection with a balanced parenthesis string — an up-step stands for an open parenthesis and a down-step stands for a close parenthesis, so "never below the axis" is exactly "never more closes than opens so far."

Binary trees

C(n) is also the number of structurally distinct full binary trees with n internal nodes, equivalently n+1 leaves. Every such tree splits at its root into a left subtree and a right subtree, and if the left subtree has i internal nodes then the right subtree must have n-i — which is precisely the convolution recurrence above, applied to trees instead of parentheses.

Polygon triangulations and non-crossing chords

The number of ways to triangulate a convex polygon with n+2 sides using only non-crossing diagonals is also C(n). This was Euler's original 18th-century question — he worked out the pattern for small polygons before the sequence was formalised in the 19th century by Eugène Catalan, whose name it now carries. A closely related object is the non-crossing chord diagram: the number of ways to connect 2n points spaced around a circle with n chords such that no two chords cross is also exactly C(n), and it too decomposes at one designated point into two smaller non-crossing problems, giving the same recurrence again.

How fast the sequence grows

As n grows large, C(n) is asymptotically 4 raised to the n, divided by n to the power 1.5 and by the square root of pi. Consequently the ratio between consecutive terms, C(n+1) divided by C(n), climbs steadily toward 4 without ever quite reaching it — C(6)/C(5) is 132/42, which is already about 3.14, and later ratios creep closer to 4 while always staying just under it, only reaching exactly 4 in the limit as n approaches infinity.

Frequently asked questions

Try it live

Everything above runs in your browser — open Catalan Numbers and step through increasing n to watch the count of trees, paths and triangulations grow in lockstep. Nothing is installed, nothing is uploaded, the whole model lives in one tab.