Lattice paths, step by step
Walk across a grid of streets from one corner to the far one, only ever going right or up.
How many different routes are there?
Count the routes without drawing them
- One grid to start from: 7 wide and 2 tall, walking only right or up from one corner to the far one. Drawing every route is exactly what this walk is avoiding.
- Every route is the SAME length — 7 steps right and 2 up, 7 + 2 = 9 in all. So a route is nothing but a choice of WHICH 2 of those 9 steps go up. That turns drawing into counting.
- That count is 9 choose 2, and here it is built one factor at a time so it stays a whole number the whole way.
- So 36 routes. It is NOT 512: "right or up at every step" would be 9 free choices, but most of those run off the grid — too many rights, or too many ups.
How it works.
- 01
One grid to start from: 7 wide and 2 tall, walking only right or up from one corner to the far one. Drawing every route is exactly what this walk is avoiding.
- 02
Every route is the SAME length — 7 steps right and 2 up, 7 + 2 = 9 in all. So a route is nothing but a choice of WHICH 2 of those 9 steps go up. That turns drawing into counting.
- 03
That count is 9 choose 2, and here it is built one factor at a time so it stays a whole number the whole way.
- 04
So 36 routes. It is NOT 512: "right or up at every step" would be 9 free choices, but most of those run off the grid — too many rights, or too many ups.