Discrete Math · Undergraduate
Counting Lattice Paths on a Grid
Quick answer
A shortest path on a grid from (0, 0) to (m, n) uses m steps right and n steps up in some order. Choosing which m of the m + n steps go right fixes the path, so there are C(m + n, m) paths. To count paths through a point, multiply the paths to it by the paths from it. To count paths that avoid a point, subtract those from the total. The same count gives shortest taxi routes on a city grid.
What you'll learn
- Count lattice paths with a binomial coefficient
- Count paths through a given point
- Count paths that avoid a point
- Extend the count to three dimensions
Steps in some order
A lattice path moves along grid lines, one unit right () or up () at a time. Every shortest path from to uses exactly s and s. The path to below is .
Why a path is a choice of positions
Write a path as a word of letters. Once we decide which positions hold an , the rest are s and the path is fixed, so paths match one-to-one with ways to choose positions from . That is the combination . For paths through a point , every path splits at into a first part and a second part, chosen independently, so the counts multiply.
Worked examples
Common mistakes
Practice problems
-
Count the paths from to .
Answer
Full solution
.
-
Count the paths from to .
Answer
Full solution
.
-
Count the paths from to .
Answer
Full solution
.
-
Count the paths from to through .
Answer
Full solution
.
-
Count the paths from to that avoid .
Answer
Full solution
.
-
Count the shortest paths from to in space.
Answer
Full solution
The three different steps can go in orders.
-
A taxi drives blocks east and blocks north on a city grid. How many shortest routes are there?
Answer
Full solution
.
-
A student counts the paths from to as . How many are there?
Answer
Full solution
.
Frequently asked questions
How many lattice paths go from (0, 0) to (m, n)?
C(m + n, m): choose which m of the m + n steps go right.
How do I count paths through a point?
Multiply the number of paths from the start to the point by the number from the point to the end.
How do I count paths that avoid a point?
Subtract the paths through the point from the total.
What about three dimensions?
A path to (a, b, c) has a + b + c steps, and there are (a + b + c)!/(a! b! c!) of them.