Lattice Paths

Count monotonic grid paths using binomial coefficients, and recognize constrained-path (Catalan-style) variants.

1. The idea

A lattice path from $(0, 0)$ to $(a, b)$ using only unit right and up steps consists of $a + b$ total steps, of which $a$ are 'right' and $b$ are 'up.' The number of such paths is the number of ways to choose which of the $a + b$ steps are 'right': $(a a + b)$ .

This is a direct application of combinations: a path is fully determined by choosing the positions of the right-steps (or equivalently the up-steps) among all steps, exactly analogous to arranging a sequence of R's and U's.

Constrained lattice paths — for example those that never cross above the diagonal, used in ballot problems and Catalan number counting — require subtracting off the 'bad' paths (often via a reflection argument) rather than a direct binomial coefficient; this is an advanced extension worth recognizing even if the full derivation isn't required.

2. Why it matters

Lattice path counting connects combinations to grid and sequence problems, and the reflection principle behind constrained paths reappears in random walk and ballot-style probability questions.

3. Core mathematics

Unconstrained lattice paths

(a a + b)

Paths from (0,0) to (a,b) using only right/up unit steps.

Catalan number (paths that never cross the diagonal)

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

Counts, e.g., paths from (0,0) to (n,n) staying weakly below the diagonal.

4. How to recognize it

Think of this when…

A grid or lattice with movement restricted to two directions (right/up, or similar).
The question asks for the number of monotonic paths between two grid points.
Ballot problems ('candidate A stays ahead of B throughout the count') or non-crossing path language.
Catalan numbers appear implicitly: balanced parentheses, non-crossing pairings, or paths that don't dip below a line.

5. Worked example

Worked example

How many lattice paths are there from $(0, 0)$ to $(5, 3)$ using only unit steps right and up?

1
The path requires exactly 5 right-steps and 3 up-steps, in some order, for a total of 8 steps.
2
Choosing which of the 8 step-positions are 'right' determines the path uniquely.
$(5 8) = (3 8)$
3
Compute the binomial coefficient.
$(3 8) = 56$
Answer: 56 lattice paths.

6. Common mistakes

Using $(a a + b)$ for paths that have extra movement constraints (e.g. no crossing a line), when a reflection-principle adjustment is required.
Miscounting the total steps as $a$ or $b$ alone instead of $a + b$ .
Confusing $(a a + b)$ with $(b a + b)$ — these are equal, but plugging the wrong pair into a partially computed expression causes errors.
Applying the plain lattice path formula to diagonal or three-directional grids where the step alphabet is not just right/up.

7. Quick check

How many lattice paths go from (0,0) to (4,4) with unit right/up steps?

The number of paths from (0,0) to (n,n) that never rise above the diagonal is called:

8. Practice

3 QuantSolve questions use this concept.

Practice this concept

9. Related methods

Stars & Bars

Create a free account to save lesson progress.