Section 2.2

Lattice Paths, Reflection and Catalan Numbers

Monotone lattice paths in 2-D and 3-D (through or avoiding points), the reflection principle, ballot counts, and Catalan structures such as bracket sequences.

Toolkit

A monotone lattice path from $(0,0)$ to $(a,b)$ is a word in its steps, counted by $\binom{a+b}{a}$ ; passing through a checkpoint multiplies the counts of the two sub-paths. For paths constrained by a boundary line, use the reflection principle: reflecting the initial segment of any path that touches or crosses a forbidden line $y=x+c$ gives a bijection between “bad” paths and all paths from the reflected starting point, so

\#\{\text{paths avoiding the line}\} = \#\{\text{all paths}\} - \#\{\text{reflected paths}\}.

Key consequences:

Ballot problem: probability the leader stays strictly ahead throughout is $\dfrac{n-m}{n+m}$ when the final tally is $n:m$ , $n>m$ .
Catalan number $C_n=\frac{1}{n+1}\binom{2n}{n}$ counts Dyck paths of length $2n$ , balanced bracket sequences, and non-crossing pairings of $2n$ points on a circle.
Probability a uniformly random balanced $\pm1$ walk of length $2n$ stays nonnegative throughout is $1/(n+1)$ .

Problems