Walk across a grid of streets from one corner to the far one, only ever going right or up, and count the different routes. It feels like a fresh choice at every corner — right or up, so two to the power of the steps — but it is really one choice made once: which of the equal-length steps go right.
Every route across an m-by-n grid is exactly the same length: m steps right and n steps up, m + n steps in all. So a route is nothing more than a choice of WHICH of those steps are the rights — and that choice is a combination, (m + n) choose m. The move that makes it countable is seeing that the drawing is a choice in disguise: you never list a single path, you count the ways to place the rights among the steps.
Why this sheet works
The tempting wrong answer is 2 to the power of (m + n): at each step you go right or up, two choices, so surely two multiplied that many times. It over-counts wildly, because it allows more than m rights or more than n ups — routes that march straight off the edge of the grid and never arrive. The real count is far smaller, and the gap between the two is the whole lesson: free choices at every step are not the same as choices that have to add up to a fixed destination.
Count the routes across a grid, moving only right or up, and show why it is a combination, not a power of two.
1A counter crosses a board 7 blocks wide and 2 blocks tall, moving only right or up one block at a time from the bottom-left corner to the top-right corner.How many different routes are there?Why
2A counter crosses a board 3 blocks wide and 9 blocks tall, moving only right or up one block at a time from the bottom-left corner to the top-right corner.How many different routes are there?Why
Lattice pathsGrids up to 10
Name: Date:
Count the routes across a grid, moving only right or up, and show why it is a combination, not a power of two.
3An ant walks a park 5 blocks wide and 2 blocks tall, from one corner to the opposite one, only ever going right or up one block at a time.How many different routes are there?Why
4An ant walks a park 3 blocks wide and 8 blocks tall, from one corner to the opposite one, only ever going right or up one block at a time.How many different routes are there?Why
Lattice paths · Grids up to 10Answer key
1. Every route is 9 steps — 7 to the right and 2 up — so a route is just which 2 of the 9 steps go up. That is 9 choose 2, built up one factor at a time: 1 × 9 = 9, 9 ÷ 1 = 9, 9 × 8 = 72, 72 ÷ 2 = 36. So 36 routes. It is not 512 (two choices at every step would count routes that run off the grid).2. Every route is 12 steps — 3 to the right and 9 up — so a route is just which 3 of the 12 steps go right. That is 12 choose 3, built up one factor at a time: 1 × 12 = 12, 12 ÷ 1 = 12, 12 × 11 = 132, 132 ÷ 2 = 66, 66 × 10 = 660, 660 ÷ 3 = 220. So 220 routes. It is not 4096 (two choices at every step would count routes that run off the grid).3. Every route is 7 steps — 5 to the right and 2 up — so a route is just which 2 of the 7 steps go up. That is 7 choose 2, built up one factor at a time: 1 × 7 = 7, 7 ÷ 1 = 7, 7 × 6 = 42, 42 ÷ 2 = 21. So 21 routes. It is not 128 (two choices at every step would count routes that run off the grid).4. Every route is 11 steps — 3 to the right and 8 up — so a route is just which 3 of the 11 steps go right. That is 11 choose 3, built up one factor at a time: 1 × 11 = 11, 11 ÷ 1 = 11, 11 × 10 = 110, 110 ÷ 2 = 55, 55 × 9 = 495, 495 ÷ 3 = 165. So 165 routes. It is not 2048 (two choices at every step would count routes that run off the grid).
