A. Counting and Probability · Permutations and Combinations

Counting Routes on a Grid

A2.4 A2.3About 70 minutes

Learning goals

I can count the shortest routes on a street grid by drawing, by Pascal's triangle and by combinations.
I can explain why a route with a moves one way and b moves the other way can be chosen in C(a + b, b) ways.
I can count routes that must pass through, or must avoid, a particular corner.
I can connect routes on a grid to Pascal's identity.

Words to know

shortest route
A route on a street grid that never moves away from the destination; here, one that only goes west or south.

lattice path
A path on a grid made of unit steps in allowed directions; a shortest route is a lattice path.

checkpoint
A corner that a route must pass through. Routes through a checkpoint are counted in two stages and multiplied.

The walk to school

The Ontario curriculum poses this problem: a school is 5 blocks west and 3 blocks south of a student's home. How many different routes can the student take from home to school by going west or south at each corner? You are asked to solve it in a variety of ways: by drawing the routes, by using Pascal's triangle, and by using combinations.

In Grade 11 (Sequences and Series) you saw that route counts on a grid follow Pascal's triangle. Now you can explain the answer with combinations, and handle routes with conditions.

Method 1: draw and add at each corner

Every shortest route only moves west or south. So you can reach any corner only from the corner just east of it or the corner just north of it. That means:

routes to a corner = routes to the corner east of it + routes to the corner north of it

Every corner along the top street or the east edge can be reached in only 1 way (go straight). Fill in the rest by adding. The numbers that appear are Pascal's triangle, tilted.

Each corner shows the number of shortest routes from home. Every inside number is the sum of the number to its east and the number to its north. The school corner gets 56.

Method 2: routes as arrangements

Every route is a sequence of 8 moves: 5 W (west) and 3 S (south), in some order. For example W S W W S W W S is one route. Different orders give different routes, and every order of 5 W's and 3 S's gives a valid route.

So the number of routes is the number of arrangements of WWWWWSSS: 8!/(5! × 3!) = 56 (lesson 6).

Method 3: choose the south moves

Of the 8 moves, choose which 3 are south; the rest must be west. That is C(8, 3) = 56, or equivalently choose the 5 west moves: C(8, 5) = 56.

In general: with a blocks one way and b blocks the other, there are C(a + b, b) = (a + b)!/(a! b!) shortest routes.

One of the 56 routes, written as a string of moves. Every route uses exactly 5 W's and 3 S's.

Why the grid builds Pascal's triangle

The adding rule at each corner is Pascal's identity. A corner that is i blocks west and j blocks south can be reached in C(i + j, j) ways. Adding the corners east and north of it gives C(i + j − 1, j) + C(i + j − 1, j − 1) = C(i + j, j). Look along any diagonal of the grid from upper-left to lower-right and you will read a row of Pascal's triangle: for example 1, 4, 6, 4, 1 on the corners 4 moves from home.

Worked example

Example 1: The curriculum's walk to school

Find the number of routes 5 blocks west and 3 blocks south three ways.

Drawing: add at each corner as shown in the first diagram; the school corner gets 56.
Arrangements: 8!/(5! 3!) = 40 320/(120 × 6) = 56.
Combinations: choose the 3 south moves from 8: C(8, 3) = 56.

56 routes.

Worked example

Example 2: Passing a checkpoint

The student wants to stop at a coffee shop at the corner 2 blocks west and 1 block south of home. How many routes to school pass that corner?

Stage 1, home to the coffee shop: 2 W and 1 S: C(3, 1) = 3 routes.
Stage 2, coffee shop to school: the remaining 3 W and 2 S: C(5, 2) = 10 routes.
Multiplicative principle: 3 × 10 = 30.

30 routes.

Worked example

Example 3: Avoiding a corner

That same corner is closed for construction. How many routes avoid it?

Indirect counting: all routes minus routes through the closed corner.
56 − 30 = 26.
Check by redrawing the grid with a 0 at the closed corner and adding again (second diagram below).

26 routes.

The closed corner (×) counts as 0, so no route passes through it. Adding as before gives 26 at the school, matching 56 − 30.

Worked example

Example 4: Two checkpoints

How many routes from home to school pass through both the corner 1 W, 1 S and the corner 3 W, 2 S?

Home to (1 W, 1 S): C(2, 1) = 2.
(1 W, 1 S) to (3 W, 2 S): 2 W and 1 S: C(3, 1) = 3.
(3 W, 2 S) to school: 2 W and 1 S: C(3, 1) = 3.
2 × 3 × 3 = 18.

18 routes.

Route-counting checklist

Count the moves each way: a one way, b the other.
No conditions: C(a + b, b).
Through a corner: split the trip at that corner and multiply.
Avoid a corner: total minus through it (or put a 0 there and add on the grid).
Through at least one of two corners: inclusion and exclusion (through P + through Q − through both).

Just for fun

All 56 shortest routes to school are exactly 8 blocks long. You could take a different one every school day for about 11 weeks, and you could never once blame the route for being late.

Hands-on activity

Coin-flip walks on grid paper

You need: grid paper (or draw a 4 by 3 grid of streets), a pencil and a coin.

Mark Home at the top-left corner and School 4 blocks east and 3 blocks south.
Fill in the number of routes at each corner by adding, as in the first diagram. What do you get at School? Check with C(7, 3).
Take a random walk: at each corner flip the coin, heads = east, tails = south. If you reach the east edge or the bottom, you must keep going the only way possible. Trace the walk lightly.
Write your walk as a string of E's and S's. How many E's and S's must it have?
Find the number of routes that pass through the corner 2 blocks east and 1 block south. What fraction of all routes is that?

What to look for: C(7, 3) = 35 routes at School. Every walk has exactly 4 E's and 3 S's. Through the corner (2 E, 1 S): C(3, 1) × C(4, 2) = 3 × 6 = 18 routes, which is 18/35 ≈ 51% of all routes. (Coin-flip walks are not all equally likely, because the forced moves at the edges skip the coin, so do not use your walks to estimate this fraction.)

Your turn

How many shortest routes go 4 blocks east and 2 blocks south?

How many shortest routes go 6 blocks east and 4 blocks south?

On a 4 east by 3 south grid, how many routes pass through the corner 2 E, 1 S?

On the same grid, how many routes avoid that corner?

A route goes 5 blocks west and 3 blocks south. How many letters are in its W/S string, and how many of each letter?

How many routes go 3 blocks east and 3 blocks south? Where does this number appear in Pascal's triangle?

On the 5 W by 3 S grid, how many routes pass through both the corner 1 W, 1 S and the corner 3 W, 2 S?

More practice: warm-up

How many shortest routes go 2 blocks east and 2 blocks south?

How many shortest routes go 3 blocks east and 1 block south?

How many shortest routes go 1 block east and 1 block south?

How many shortest routes go 3 blocks east and 2 blocks south?

A route goes 4 blocks one way and 5 the other. How many moves does it have?

More practice: on your own

How many shortest routes go 5 blocks east and 5 blocks south?

On a 4 by 4 grid, how many routes pass through the centre corner (2, 2)?

On a 3 by 3 grid the corner 1 E, 1 S is blocked. How many routes avoid it?

Of the routes going 6 blocks east and 4 blocks south, how many start with a move east?

In a peg board, a marble bounces left or right at each of 4 rows of pegs, landing in one of 5 bins. How many paths lead to each bin?

Challenge

A city is built in blocks stacked in 3-D. How many shortest paths lead from one corner of a 2 × 2 × 2 cube of blocks to the opposite corner, moving only east, north or up?

On the 5 W by 3 S grid, the street segment from the corner (2 W, 1 S) west to (3 W, 1 S) is closed. How many routes avoid that segment?

On the 5 W by 3 S grid, P is the corner (2 W, 1 S) and Q is the corner (4 W, 2 S). How many routes pass through P or Q (or both)?

Check your understanding

Quiz

A school is 5 blocks west and 3 blocks south of home. How many shortest routes are there?

How many shortest routes go 4 blocks east and 2 blocks south?

Why does C(8, 3) count the routes 5 west and 3 south?

Which fact explains why each corner's count is the sum of the counts at the corners east and north of it?

On the 5 W by 3 S grid, how many routes pass through the corner 2 W, 1 S?

How many shortest routes go 3 blocks east and 3 blocks south?

For parents and teachers

Big idea (A2.4, A2.3): a shortest route with a moves one way and b the other is an arrangement of letters, so there are C(a + b, b) routes. Adding at each corner builds Pascal's triangle, which is Pascal's identity in disguise. Checkpoints multiply; blocked corners subtract.

How to help: Sketch a small grid together and fill in the corner counts. Then ask your teen to get the same answer with C(a + b, b). If you live on a street grid, the curriculum's walk-to-school problem is a great real example.

Common difficulties:

Counting corners or streets instead of moves.
Adding the two stages of a checkpoint route instead of multiplying.
Forgetting that the edge corners have only one route.
With two checkpoints, not checking whether a route can pass both (inclusion and exclusion).