Why the Catalan numbers appear everywhere: parenthesizations, binary trees, and lattice paths

The Catalan number $C_n = \frac{1}{n+1}\binom{2n}{n}$ answers questions about balanced parentheses, binary trees, lattice paths, polygon triangulations, and ballot sequences. Through the reflection principle and explicit bijections, we explain why all these problems share the same answer.

Folio Official

March 1, 2026

Combinatorics has its celebrities – numbers that show up again and again in problems that bear no apparent relation to one another. The undisputed star is the Catalan number. Balanced parenthesizations, binary tree shapes, lattice paths that stay below the diagonal, triangulations of convex polygons, ballot sequences – solve any one of these counting problems and the same sequence $1, 1, 2, 5, 14, 42, 132, \dots$ emerges. Why?

1 Definition

Definition 1 (Catalan number).

The

n

-th Catalan number is

C_{n} = \frac{1}{n + 1} (n 2 n) .

The first several values are

C_{0} = 1

C_{1} = 1

C_{2} = 2

C_{3} = 5

C_{4} = 14

C_{5} = 42

Remark 2.

Since

(n 2 n)

is an integer, one might wonder why dividing by

n + 1

still yields an integer. The combinatorial interpretations make integrality obvious – the number of binary trees with

n

internal nodes must be a non-negative integer – but an algebraic proof requires a small argument. The identity

C_{n} = (n 2 n) - (n + 1 2 n)

, which expresses

C_{n}

as the difference of two binomial coefficients, settles the matter.

2 Five combinatorial incarnations

The Catalan number $C_{n}$ is simultaneously the answer to each of the following problems.

Example 3 (Balanced parenthesizations).

The number of ways to arrange

n

pairs of parentheses so that they are correctly matched is

C_{n}

. For

n = 3

, the five valid strings are

((()))

(() ())

(()) ()

() (())

() () ()

, confirming

C_{3} = 5

Example 4 (Binary trees).

The number of distinct binary trees with

n

internal nodes is

C_{n}

Example 5 (Lattice paths below the diagonal).

The number of shortest lattice paths from

(0, 0)

(n, n)

that never cross above the diagonal

y = x

(i.e., satisfying

y \leq x

at every step) is

C_{n}

Example 6 (Triangulations of a convex polygon).

The number of ways to dissect a convex

(n + 2)

-gon into triangles using non-crossing diagonals is

C_{n}

Example 7 (Ballot sequences).

The number of sequences of

2 n

steps –

n

up-steps (

↗

) and

n

down-steps (

↘

) – that never dip below the starting height is

C_{n}

. This is a visual rendering of the balanced parenthesization problem.

3 Derivation via the reflection principle

We derive the Catalan formula from the lattice path interpretation.

Theorem 8.

The number of shortest lattice paths from

(0, 0)

(n, n)

that never cross above the diagonal is

C_{n} = \frac{1}{n + 1} (n 2 n)

Proof.

Without any constraint, the total number of shortest paths from

(0, 0)

(n, n)

(n 2 n)

(choose which

n

of the

2 n

steps go right).

A "bad" path – one that crosses above the diagonal – must touch the line

y = x + 1

at some point. At the first such touching point, reflect the remainder of the path across the line

y = x + 1

This reflection establishes a bijection between bad paths from

(0, 0)

(n, n)

and all paths from

(0, 0)

(n - 1, n + 1)

, so the number of bad paths is

(n - 1 2 n)

The desired count is therefore

(n 2 n) - (n - 1 2 n) = (n 2 n) - \frac{n}{n + 1} (n 2 n) = \frac{1}{n + 1} (n 2 n) = C_{n} .

□

Remark 9.

The power of the reflection principle lies in the construction of a bijection. Rather than counting bad paths directly, we map them one-to-one onto paths with a different endpoint, whose count we already know. This technique extends to a wide variety of lattice path problems.

4 Why the same number: bijections between interpretations

The reason $C_{n}$ appears in so many guises is that there exist explicit bijections between the solution sets of these problems.

Remark 10.

For instance, the bijection between balanced parenthesizations with

n

pairs and lattice paths below the diagonal from

(0, 0)

(n, n)

is constructed as follows:

Map each opening parenthesis "(" to a rightward step $\to$ .
Map each closing parenthesis ")" to an upward step $↑$ .
The condition that the parenthesization is balanced is equivalent to the condition that the path never crosses above the diagonal.

5 Derivation via generating functions

Theorem 11.

The generating function

C (x) = \sum_{n = 0}^{\infty} C_{n} x^{n}

of the Catalan numbers is

C (x) = \frac{1 - 1 - 4 x}{2 x} .

Proof.

Consider the recursive structure of binary trees. Every non-empty binary tree decomposes as a root together with a left subtree and a right subtree. If the left subtree has

k

internal nodes and the right subtree has

n - 1 - k

, then

C_{n} = k = 0 \sum n - 1 C_{k} C_{n - 1 - k} (n \geq 1), C_{0} = 1.

Translating into generating functions:

C (x) = 1 + x C (x)^{2}

, where the

1

accounts for

C_{0}

and the factor

x C (x)^{2}

encodes the recursive decomposition.

Solving the quadratic

x C (x)^{2} - C (x) + 1 = 0

gives

C (x) = \frac{1 \pm 1 - 4 x}{2 x} .

Since

C (0) = C_{0} = 1

must be finite, the

+

sign produces a singularity, so the correct branch is

C (x) = \frac{1 - 1 - 4 x}{2 x}

. □

6 Takeaway

The Catalan number $C_{n} = \frac{1}{n + 1} (n 2 n)$ admits at least five distinct combinatorial interpretations.
The reflection principle is a powerful technique for counting lattice paths by bijecting "bad" paths to paths with a known endpoint.
The reason the same number appears in different problems is the existence of explicit bijections between their solution sets.
The generating function $C (x) = \frac{1 - 1 - 4 x}{2 x}$ arises from the recursive structure of binary trees.

In the next article, we turn to a deceptively simple principle that proves the existence of objects without ever exhibiting them: the pigeonhole principle.

Combinatorics Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Why the Catalan numbers appear everywhere: parenthesizations, binary trees, and lattice paths

Folio Official

March 1, 2026

1 Definition

Definition 1 (Catalan number).

The

n

-th Catalan number is

C_{n} = \frac{1}{n + 1} (n 2 n) .

The first several values are

C_{0} = 1

C_{1} = 1

C_{2} = 2

C_{3} = 5

C_{4} = 14

C_{5} = 42

Remark 2.

Since

(n 2 n)

is an integer, one might wonder why dividing by

n + 1

still yields an integer. The combinatorial interpretations make integrality obvious – the number of binary trees with

n

internal nodes must be a non-negative integer – but an algebraic proof requires a small argument. The identity

C_{n} = (n 2 n) - (n + 1 2 n)

, which expresses

C_{n}

as the difference of two binomial coefficients, settles the matter.

2 Five combinatorial incarnations

The Catalan number $C_{n}$ is simultaneously the answer to each of the following problems.

Example 3 (Balanced parenthesizations).

The number of ways to arrange

n

pairs of parentheses so that they are correctly matched is

C_{n}

. For

n = 3

, the five valid strings are

((()))

(() ())

(()) ()

() (())

() () ()

, confirming

C_{3} = 5

Example 4 (Binary trees).

The number of distinct binary trees with

n

internal nodes is

C_{n}

Example 5 (Lattice paths below the diagonal).

The number of shortest lattice paths from

(0, 0)

(n, n)

that never cross above the diagonal

y = x

(i.e., satisfying

y \leq x

at every step) is

C_{n}

Example 6 (Triangulations of a convex polygon).

The number of ways to dissect a convex

(n + 2)

-gon into triangles using non-crossing diagonals is

C_{n}

Example 7 (Ballot sequences).

The number of sequences of

2 n

steps –

n

up-steps (

↗

) and

n

down-steps (

↘

) – that never dip below the starting height is

C_{n}

. This is a visual rendering of the balanced parenthesization problem.

3 Derivation via the reflection principle

We derive the Catalan formula from the lattice path interpretation.

Theorem 8.

The number of shortest lattice paths from

(0, 0)

(n, n)

that never cross above the diagonal is

C_{n} = \frac{1}{n + 1} (n 2 n)

Proof.

Without any constraint, the total number of shortest paths from

(0, 0)

(n, n)

(n 2 n)

(choose which

n

of the

2 n

steps go right).

A "bad" path – one that crosses above the diagonal – must touch the line

y = x + 1

at some point. At the first such touching point, reflect the remainder of the path across the line

y = x + 1

This reflection establishes a bijection between bad paths from

(0, 0)

(n, n)

and all paths from

(0, 0)

(n - 1, n + 1)

, so the number of bad paths is

(n - 1 2 n)

The desired count is therefore

(n 2 n) - (n - 1 2 n) = (n 2 n) - \frac{n}{n + 1} (n 2 n) = \frac{1}{n + 1} (n 2 n) = C_{n} .

□

Remark 9.

4 Why the same number: bijections between interpretations

The reason $C_{n}$ appears in so many guises is that there exist explicit bijections between the solution sets of these problems.

Remark 10.

For instance, the bijection between balanced parenthesizations with

n

pairs and lattice paths below the diagonal from

(0, 0)

(n, n)

is constructed as follows:

Map each opening parenthesis "(" to a rightward step $\to$ .
Map each closing parenthesis ")" to an upward step $↑$ .
The condition that the parenthesization is balanced is equivalent to the condition that the path never crosses above the diagonal.

5 Derivation via generating functions

Theorem 11.

The generating function

C (x) = \sum_{n = 0}^{\infty} C_{n} x^{n}

of the Catalan numbers is

C (x) = \frac{1 - 1 - 4 x}{2 x} .

Proof.

Consider the recursive structure of binary trees. Every non-empty binary tree decomposes as a root together with a left subtree and a right subtree. If the left subtree has

k

internal nodes and the right subtree has

n - 1 - k

, then

C_{n} = k = 0 \sum n - 1 C_{k} C_{n - 1 - k} (n \geq 1), C_{0} = 1.

Translating into generating functions:

C (x) = 1 + x C (x)^{2}

, where the

1

accounts for

C_{0}

and the factor

x C (x)^{2}

encodes the recursive decomposition.

Solving the quadratic

x C (x)^{2} - C (x) + 1 = 0

gives

C (x) = \frac{1 \pm 1 - 4 x}{2 x} .

Since

C (0) = C_{0} = 1

must be finite, the

+

sign produces a singularity, so the correct branch is

C (x) = \frac{1 - 1 - 4 x}{2 x}

. □

6 Takeaway

The Catalan number $C_{n} = \frac{1}{n + 1} (n 2 n)$ admits at least five distinct combinatorial interpretations.
The reflection principle is a powerful technique for counting lattice paths by bijecting "bad" paths to paths with a known endpoint.
The reason the same number appears in different problems is the existence of explicit bijections between their solution sets.
The generating function $C (x) = \frac{1 - 1 - 4 x}{2 x}$ arises from the recursive structure of binary trees.

In the next article, we turn to a deceptively simple principle that proves the existence of objects without ever exhibiting them: the pigeonhole principle.

Combinatorics Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Why the Catalan numbers appear everywhere: parenthesizations, binary trees, and lattice paths

1 Definition

2 Five combinatorial incarnations

3 Derivation via the reflection principle

4 Why the same number: bijections between interpretations

5 Derivation via generating functions

6 Takeaway

Share your expertise with the world

More from Folio Official

Recurrences and generating functions: what happens when you turn a sequence into a function

Combinatorics meets dynamic programming: when counting becomes computation

Inclusion--exclusion: why the alternating signs work

Counting under symmetry: Burnside's lemma and Polya's enumeration theorem

Why the Catalan numbers appear everywhere: parenthesizations, binary trees, and lattice paths

1 Definition

2 Five combinatorial incarnations

3 Derivation via the reflection principle

4 Why the same number: bijections between interpretations

5 Derivation via generating functions

6 Takeaway

Share your expertise with the world

More from Folio Official

Recurrences and generating functions: what happens when you turn a sequence into a function

Combinatorics meets dynamic programming: when counting becomes computation

Inclusion--exclusion: why the alternating signs work

Counting under symmetry: Burnside's lemma and Polya's enumeration theorem