Catalan Numbers and Lattice Paths: The Reflection Principle and Bijective Proofs

We prove the formula C_n = (1/(n+1)) C(2n, n) for the Catalan numbers using the reflection principle, state the Lindstr\"{o}m--Gessel--Viennot lemma, construct bijections among five combinatorial interpretations of the Catalan numbers, solve the ballot problem, and introduce Narayana numbers.

Folio Official

March 1, 2026

1 Lattice Paths and Binomial Coefficients

Definition 1 (Lattice path).

A lattice path from

(a, b)

(c, d)

Z^{2}

is a sequence of unit steps, each going either right

(1, 0)

or up

(0, 1)

Theorem 2.

The total number of lattice paths from

(0, 0)

(m, n)

(m m + n)

Proof.

A path consists of

m + n

steps in total, of which exactly

m

must be rightward. Choosing which

m

of the

m + n

steps go right gives

(m m + n)

paths. □

2 The Reflection Principle and Catalan Numbers

Definition 3 (Dyck path).

A Dyck path of length

2 n

is a lattice path from

(0, 0)

(2 n, 0)

using steps

(1, 1)

(up) and

(1, - 1)

(down), that never dips below the

x

-axis (i.e., satisfies

y \geq 0

throughout).

Theorem 4.

The number of Dyck paths of length

2 n

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

Proof.

The total number of paths from

(0, 0)

(2 n, 0)

with

n

up-steps and

n

down-steps is

(n 2 n)

. We subtract the number of "bad" paths that reach

y < 0

at some point.

We apply the reflection principle (due to André

y = - 1

for the first time at some point. Reflecting the portion of the path after this first contact across the line

y = - 1

establishes a bijection between bad paths and all paths from

(0, 0)

(2 n, - 2)

. Such a reflected path has

n - 1

up-steps and

n + 1

down-steps, so the number of bad paths is

(n - 1 2 n)

Therefore, the number of Dyck paths is

(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} .

□

3 The Lindström–Gessel–Viennot Lemma

Theorem 5 (Lindstr\"om–Gessel–Viennot lemma).

In a directed acyclic graph, given a tuple of sources

(s_{1}, \dots, s_{n})

and a tuple of sinks

(t_{1}, \dots, t_{n})

, the signed count of

n

-tuples of vertex-disjoint paths is

det (e (s_{i}, t_{j}))_{1 \leq i, j \leq n},

where

e (s, t)

denotes the number of paths from

s

t

Proof.

Expanding the determinant gives

\sum_{σ \in S_{n}} sgn (σ) \prod_{i = 1}^{n} e (s_{i}, t_{σ (i)})

. For each permutation

σ

, consider all

n

-tuples of paths with the

i

-th path running from

s_{i}

t_{σ (i)}

. Any tuple of paths that shares a vertex can be paired, by swapping paths at a shared vertex, with a tuple corresponding to a different permutation

σ^{'}

whose sign is opposite to that of

σ

. These paired contributions cancel. The only surviving terms come from vertex-disjoint path tuples, which (under suitable planarity conditions) correspond to

σ = id

. □

4 Five Interpretations of the Catalan Numbers

Theorem 6.

Each of the following five families of objects is counted by

C_{n}

, and they are connected by explicit bijections:

Well-formed strings of $n$ pairs of parentheses.
Full binary trees with $n + 1$ leaves.
Lattice paths from $(0, 0)$ to $(n, n)$ that do not cross above the diagonal $y = x$ .
Non-crossing partitions of ${1, 2, \dots, n}$ (under the appropriate interpretation).
Triangulations of a convex $(n + 2)$ -gon.

Proof.

(1) Bijection with Dyck paths: map each "(" to an up-step and each ")" to a down-step. The condition that the parentheses are well-formed is equivalent to

y \geq 0

(2) Bijection with Dyck paths: in a depth-first traversal of a full binary tree with

n + 1

leaves, each descent to a left child corresponds to an up-step and each descent to a right child corresponds to a down-step. Conversely, reading up-steps as "go left" and down-steps as "go right" reconstructs the tree.

(3) Bijection with Dyck paths: a lattice path from

(0, 0)

(n, n)

that stays weakly below

y = x

can be transformed into a Dyck path by interpreting a right-step as an up-step and an up-step as a down-step.

(4) Bijection with Dyck paths: scan the elements

1, 2, \dots, n

from left to right. When a new block opens, take an up-step; when a block closes, take a down-step. The non-crossing condition ensures

y \geq 0

(5) Fix one edge of the convex

(n + 2)

-gon and classify triangulations by which triangle contains that edge. This case analysis yields the recurrence

C_{n} = \sum_{k = 0}^{n - 1} C_{k} C_{n - 1 - k}

, which is the Catalan recurrence. □

5 The Ballot Problem

Theorem 7 (Ballot problem).

Suppose candidate

A

receives

a

votes and candidate

B

receives

b

votes, with

a > b

. The probability that

A

is strictly ahead of

B

throughout the entire counting process is

(a - b) / (a + b)

Proof.

Model each vote for

A

as a step

(1, 1)

and each vote for

B

as a step

(1, - 1)

, giving a path from

(0, 0)

(a + b, a - b)

. We seek the fraction of such paths that satisfy

y > 0

at every intermediate step. By the reflection principle, the paths that touch or cross

y = 0

can be placed in bijection with certain reflected paths. Computing the resulting ratio yields

(a - b) / (a + b)

. □

6 Narayana Numbers

Definition 8 (Narayana number).

The Narayana number is

N (n, k) = \frac{1}{n} (k n) (k - 1 n) .

It counts the number of Dyck paths of length

2 n

with exactly

k

peaks.

Theorem 9.

k = 1 \sum n N (n, k) = C_{n}

Proof.

Classifying all Dyck paths of length

2 n

by their number of peaks, we see that the total over all possible peak counts must equal the Catalan number. Hence

\sum_{k = 1}^{n} N (n, k) = C_{n}

. □

The Narayana numbers provide a refinement of the Catalan numbers. By introducing a $q$ -parameter, one obtains the $q$ -Catalan numbers and the Carlitz $q$ -Narayana numbers, opening the door to rich algebraic extensions.

Combinatorics Discrete Mathematics Textbook Catalan Numbers Lattice Paths

Folio Official

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

1 followers·107 articles

Catalan Numbers and Lattice Paths: The Reflection Principle and Bijective Proofs

Folio Official

March 1, 2026

1 Lattice Paths and Binomial Coefficients

Definition 1 (Lattice path).

A lattice path from

(a, b)

(c, d)

Z^{2}

is a sequence of unit steps, each going either right

(1, 0)

or up

(0, 1)

Theorem 2.

The total number of lattice paths from

(0, 0)

(m, n)

(m m + n)

Proof.

A path consists of

m + n

steps in total, of which exactly

m

must be rightward. Choosing which

m

of the

m + n

steps go right gives

(m m + n)

paths. □

2 The Reflection Principle and Catalan Numbers

Definition 3 (Dyck path).

A Dyck path of length

2 n

is a lattice path from

(0, 0)

(2 n, 0)

using steps

(1, 1)

(up) and

(1, - 1)

(down), that never dips below the

x

-axis (i.e., satisfies

y \geq 0

throughout).

Theorem 4.

The number of Dyck paths of length

2 n

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

Proof.

The total number of paths from

(0, 0)

(2 n, 0)

with

n

up-steps and

n

down-steps is

(n 2 n)

. We subtract the number of "bad" paths that reach

y < 0

at some point.

We apply the reflection principle (due to André

y = - 1

for the first time at some point. Reflecting the portion of the path after this first contact across the line

y = - 1

establishes a bijection between bad paths and all paths from

(0, 0)

(2 n, - 2)

. Such a reflected path has

n - 1

up-steps and

n + 1

down-steps, so the number of bad paths is

(n - 1 2 n)

Therefore, the number of Dyck paths is

(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} .

□

3 The Lindström–Gessel–Viennot Lemma

Theorem 5 (Lindstr\"om–Gessel–Viennot lemma).

In a directed acyclic graph, given a tuple of sources

(s_{1}, \dots, s_{n})

and a tuple of sinks

(t_{1}, \dots, t_{n})

, the signed count of

n

-tuples of vertex-disjoint paths is

det (e (s_{i}, t_{j}))_{1 \leq i, j \leq n},

where

e (s, t)

denotes the number of paths from

s

t

Proof.

Expanding the determinant gives

\sum_{σ \in S_{n}} sgn (σ) \prod_{i = 1}^{n} e (s_{i}, t_{σ (i)})

. For each permutation

σ

, consider all

n

-tuples of paths with the

i

-th path running from

s_{i}

t_{σ (i)}

. Any tuple of paths that shares a vertex can be paired, by swapping paths at a shared vertex, with a tuple corresponding to a different permutation

σ^{'}

whose sign is opposite to that of

σ

. These paired contributions cancel. The only surviving terms come from vertex-disjoint path tuples, which (under suitable planarity conditions) correspond to

σ = id

. □

4 Five Interpretations of the Catalan Numbers

Theorem 6.

Each of the following five families of objects is counted by

C_{n}

, and they are connected by explicit bijections:

Well-formed strings of $n$ pairs of parentheses.
Full binary trees with $n + 1$ leaves.
Lattice paths from $(0, 0)$ to $(n, n)$ that do not cross above the diagonal $y = x$ .
Non-crossing partitions of ${1, 2, \dots, n}$ (under the appropriate interpretation).
Triangulations of a convex $(n + 2)$ -gon.

Proof.

(1) Bijection with Dyck paths: map each "(" to an up-step and each ")" to a down-step. The condition that the parentheses are well-formed is equivalent to

y \geq 0

(2) Bijection with Dyck paths: in a depth-first traversal of a full binary tree with

n + 1

(3) Bijection with Dyck paths: a lattice path from

(0, 0)

(n, n)

that stays weakly below

y = x

can be transformed into a Dyck path by interpreting a right-step as an up-step and an up-step as a down-step.

(4) Bijection with Dyck paths: scan the elements

1, 2, \dots, n

from left to right. When a new block opens, take an up-step; when a block closes, take a down-step. The non-crossing condition ensures

y \geq 0

(5) Fix one edge of the convex

(n + 2)

-gon and classify triangulations by which triangle contains that edge. This case analysis yields the recurrence

C_{n} = \sum_{k = 0}^{n - 1} C_{k} C_{n - 1 - k}

, which is the Catalan recurrence. □

5 The Ballot Problem

Theorem 7 (Ballot problem).

Suppose candidate

A

receives

a

votes and candidate

B

receives

b

votes, with

a > b

. The probability that

A

is strictly ahead of

B

throughout the entire counting process is

(a - b) / (a + b)

Proof.

Model each vote for

A

as a step

(1, 1)

and each vote for

B

as a step

(1, - 1)

, giving a path from

(0, 0)

(a + b, a - b)

. We seek the fraction of such paths that satisfy

y > 0

at every intermediate step. By the reflection principle, the paths that touch or cross

y = 0

can be placed in bijection with certain reflected paths. Computing the resulting ratio yields

(a - b) / (a + b)

. □

6 Narayana Numbers

Definition 8 (Narayana number).

The Narayana number is

N (n, k) = \frac{1}{n} (k n) (k - 1 n) .

It counts the number of Dyck paths of length

2 n

with exactly

k

peaks.

Theorem 9.

k = 1 \sum n N (n, k) = C_{n}

Proof.

Classifying all Dyck paths of length

2 n

by their number of peaks, we see that the total over all possible peak counts must equal the Catalan number. Hence

\sum_{k = 1}^{n} N (n, k) = C_{n}

. □

Combinatorics Discrete Mathematics Textbook Catalan Numbers Lattice Paths

Folio Official

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

1 followers·107 articles

Catalan Numbers and Lattice Paths: The Reflection Principle and Bijective Proofs

1 Lattice Paths and Binomial Coefficients

2 The Reflection Principle and Catalan Numbers

3 The Lindström–Gessel–Viennot Lemma

4 Five Interpretations of the Catalan Numbers

5 The Ballot Problem

6 Narayana Numbers

Share your expertise with the world

More from Folio Official

Recurrence Relations and Counting: Solving Linear Recurrences

The Inclusion--Exclusion Principle: Counting by Alternating Sums

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry

Catalan Numbers and Lattice Paths: The Reflection Principle and Bijective Proofs

1 Lattice Paths and Binomial Coefficients

2 The Reflection Principle and Catalan Numbers

3 The Lindström–Gessel–Viennot Lemma

4 Five Interpretations of the Catalan Numbers

5 The Ballot Problem

6 Narayana Numbers

Share your expertise with the world

More from Folio Official

Recurrence Relations and Counting: Solving Linear Recurrences

The Inclusion--Exclusion Principle: Counting by Alternating Sums

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry