Lattice paths, the reflection principle and Catalan numbers

A surprising number of interview problems are the same object in different clothing: a sequence of up and down steps, counted subject to a constraint. Once you see a question as a lattice path, the reflection principle counts the constrained cases in one line — and the same argument reappears in random walks and in barrier option pricing.

Definition 4.1

Monotone lattice paths

Lattice path, $\text{paths from } (0,0) \text{ to } (m,n) = \binom{m+n}{n}$ — A path taking only right and up steps is determined entirely by which of its $m+n$ steps go up, so counting paths is choosing a subset. Every grid-walking question reduces to this, and constraints like "avoid this square" are handled by subtracting the paths that pass through it.

Derivation 4.2

The reflection principle

To count paths from $A$ to $B$ that touch a forbidden line, reflect the start across the line.

$\text{Any path from } A \text{ that touches the line}$
Take the first touch, and reflect everything before it.
$\longleftrightarrow \text{a path from } A' \text{ to } B$
This is a bijection: reflecting twice returns the original path, and every path from $A'$ must cross the line.
$\#\{\text{touching}\} = \#\{\text{all paths from } A' \text{ to } B\}$

\#\{\text{never touching}\} = \binom{m+n}{n} - \#\{\text{paths from } A'\}

Equation 4.3

The ballot problem

Candidate A finishes with $a$ votes and B with $b < a$ . Counting the votes in random order, this is the chance A leads throughout.

P(\text{A always ahead}) = \frac{a - b}{a + b}

$a - b$: The final margin.
$a + b$: The total number of votes.

Why the answer is so simple. A formula this clean is usually a bijection in disguise, and it is: the reflection argument pairs every path that ties at some point with a path that starts the other way, so the surviving paths are exactly the ones whose first step is A and which never return to zero. The margin over the total is the residue left when those pairs cancel. It is worth recognising the shape — an answer that depends only on the endpoints, not on the route — because the same phenomenon makes gambler’s ruin and hitting probabilities so tractable.

Equation 4.4

Catalan numbers

Paths of $n$ ups and $n$ downs that never go below zero — and, by bijection, a great many other things.

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

$C_0..C_6$: 1, 1, 2, 5, 14, 42, 132 — worth recognising on sight.
$\binom{2n}{n+1}$: The paths that do dip below, counted by reflection.

Object	The bijection
Balanced bracket sequences of length $2n$	Open is up, close is down; never going negative is never closing too early
Binary trees with $n$ internal nodes	Read a traversal as the path
Triangulations of a convex $(n{+}2)$ -gon	Recursive split on one edge
Ways to parenthesise $n{+}1$ factors	Same recursion
Monotone paths below the diagonal of an $n \times n$ grid	The definition itself
Stack-sortable permutations of $n$ items	Push is up, pop is down

Table 4.5 · Things counted by $C_n$ . If a count comes out 1, 2, 5, 14, 42 you are almost certainly looking at a Catalan problem, and the right move is to find the up-down path hiding inside it.

Lattice paths, the reflection principle and Catalan numbers

After this lesson you should be able to

Monotone lattice paths

The reflection principle

The ballot problem

Catalan numbers

The rest of this lesson is in Premium