Lattice Path — Definition, Formula & Example
A lattice path is a route across a grid that moves from one integer point to another using only fixed unit steps, most often one unit right or one unit up. Counting how many such routes exist is a classic counting problem.
A lattice path from to with step set is a sequence of lattice points in such that each difference belongs to . Each such path corresponds to exactly one arrangement of R's and U's, so the number of paths is .
Key Formula
Where:
- = number of right steps (horizontal distance)
- = number of up steps (vertical distance)
- = binomial coefficient: ways to choose which of the m + n steps go right
Worked Example
Problem: Your town's streets form a grid. Your home is 4 blocks west and 3 blocks south of the library. You walk only east or north along streets. (a) How many shortest routes are there? (b) How many of them pass the corner that is 2 blocks east and 1 block north of your home?
Step 1: Every shortest route uses exactly 4 east steps (E) and 3 north steps (N), for 7 steps in total. A route is just a string of 4 E's and 3 N's.
Step 2: Choose which 3 of the 7 positions are N steps. The other 4 positions are automatically E.
Step 3: For part (b), split each route at the corner . Count routes from home to the corner, then routes from the corner to the library, and multiply.
Answer: (a) There are 35 shortest routes. (b) 18 of them pass through the corner 2 blocks east and 1 block north.
Why It Matters
Lattice paths explain why Pascal's triangle works: the entry counts the paths to the point . Restricted versions lead to the Catalan numbers. For example, the paths from to that never rise above the line number . These counts reappear in combinatorics courses, random-walk probability, and the grid-based sequence alignment used in bioinformatics.
Common Mistakes
Mistake: Counting grid lines or intersections instead of steps. On a grid 4 blocks wide and 3 blocks tall, students often use 5 and 4 because there are 5 vertical and 4 horizontal street lines.
Correction: Use the number of unit steps, which is the number of blocks: and . The count is , not .
