How Many Ways Can You Walk to School?: Math Further 6–8

Your cousin has moved to a new housing colony at the edge of town, where the lanes were laid out in neat squares, like the lines on a page of graph paper. Her house is on one corner. Her school is 3 blocks east and 2 blocks north.

She is never late, so she never walks west or south: every block takes her nearer. But she gets bored of the same walk. On Sunday she went east, east, east, then north, north. On Monday north first, then all the way east. She wants a different route every school day. How many days can she keep it up before she has to repeat one?

Walk it yourself on the map below. Each time you reach school, the page keeps your route and tells you whether it is new.

Walk from home to school with East and North (or tap the next corner). Find as many different routes as you can, then try the smaller and bigger maps.

Map:

Different routes found: 0
This walk: –

Walk from home to school, one block at a time: east or north, never back.

Guess before you read on. On a bigger map, school is 5 blocks east and 5 blocks north. How many different routes are there, never walking west or south?

Pick an answer to see why.

Try it

Small maps first

On the 3 × 2 map there are 10 routes, so your cousin has 10 school days before she must repeat one. Did you find them all? If you stopped at 7 or 8, you are in good company: it is hard to be sure you haven’t missed one, or walked one twice. A careful list helps. Write each route as its turns, E for a block east and N for a block north:

Starts EEE	Starts EEN	Starts EN	Starts NE	Starts NN
EEENN	EENEN, EENNE	ENEEN, ENENE, ENNEE	NEEEN, NEENE, NENEE	NNEEE

That is 1 + 2 + 3 + 3 + 1 = 10, and listing them by how they start means none is missed. Now try the smaller maps in the widget and fill in a table like this one before you look at the last column.

Map (east × north)	Blocks walked	Routes
1 × 1	2	2
2 × 1	3	3
2 × 2	4	6
3 × 2	5	10
4 × 3	7	35

Listing gets slow. The 4 × 3 map has 35 routes and the 5 × 5 map 252. Is there a quicker way to count than writing them all out?

Pick an answer to see why.

Write a number on every corner

Think about the very last block of a walk. To arrive at a corner, you came either along the lane from the west or along the lane from the south. There is no third way in: you never walk south or west, so you can’t arrive from the north or the east.

So the routes to a corner are of two kinds. Some come in from the west, and there are as many of those as there are routes to the corner just west. The rest come in from the south, as many as there are routes to the corner just south. Add them:

routes to a corner = routes to the corner to its west + routes to the corner to its south.

Along the bottom edge and the left edge there is only one way in, straight along the edge, so every corner there has 1. Home gets 1 too: there is one way to be at home, which is to stay there. Now fill in the map, corner by corner.

Tap a corner next to the numbers you have, or press Fill the next. The arrows show which two numbers it adds.

Map:

Home has 1 route to itself: stay put. Tap a corner next to it, east or north.

The 4 × 3 map comes out like this, the top row first:


1	4	10	20	35
1	3	6	10	15
1	2	3	4	5
1	1	1	1	1

The school corner says 35, the number you get by listing. And the corner 3 east and 2 north says 10, the opening’s map, inside this bigger one. Twelve additions did the work of listing 35 routes. On the 5 × 5 map, 25 additions give 252; listing them by hand would take an afternoon.

On the 5 × 5 map, the corner 4 blocks east and 5 north has 126 routes, and so does the corner 5 east and 4 north. What goes in the school corner?

Pick an answer to see why.

Every route to school arrives along one of the two last lanes: from the corner to the west (126 routes reach it) or from the corner to the south (126 routes). So 126 + 126 = 252. The answer is “two times 126” here only because the two corners happen to have the same number; the rule is to add them. 126 alone forgets the routes that come in by the other lane, and 126 × 126 would pair every route to one corner with every route to the other, which is not a way of walking to school.

What’s going on

Turn the map round

Now turn the map so that home is at the top and school at the bottom. East runs down to one side and north down to the other, and every corner the same number of blocks from home sits on one level.

Figure 12.1 The corner numbers of a big map, turned so that home is at the top. Each level holds the corners the same number of blocks from home, and each number is the two above it added. The ringed 10 is the school of the opening, 3 blocks east and 2 north.

The numbers make a triangle. Its edges are all 1s, and every other number is the two numbers just above it added, which is our rule for corners, turned round. This is Pascal’s triangle, named after the French mathematician Blaise Pascal, who wrote a book about it in 1654. Each level is a row: row 0 is the single 1 at the top, row 1 is 1 1, row 2 is 1 2 1, and so on.

An old printed table of numbers in a staircase of squares, 1s along the top and left edges, the numbers growing towards the diagonal — **Figure 12.2** Pascal’s own “arithmetic triangle”, from his treatise of 1654. He drew it as squares, like our map: each square is the one above it plus the one to its left. Photo: Blaise Pascal, Public domain

In the turned triangle, a number can be named by its row and its place along the row, counting from 0 at the left. Row 4 is 1 4 6 4 1, so the number in row 4, place 2 is 6. On the map it is the corner 2 blocks one way and 2 the other: 4 blocks from home.

A route is a word

There is another way to see the number 10, which explains why the triangle’s numbers count routes and also how to work out a number with no triangle at all.

Figure 12.3 One route on the 3 × 2 map, written as the word E E N E N.

Every route on the 3 × 2 map is 5 blocks long, and you can write it down as a word of 5 letters: 3 E’s and 2 N’s, in some order. E E N E N is the route in Figure 12.3. And every such word is a route: start at home, follow the letters, and you arrive at school, because you have walked 3 blocks east and 2 north whatever the order.

So counting routes is the same as counting words. And a word of 3 E’s and 2 N’s is fixed as soon as you know where the 2 N’s go. The 5 places are 1st, 2nd, 3rd, 4th, 5th, and you choose two of them for the N’s:

1st & 2nd, 1st & 3rd, 1st & 4th, 1st & 5th, 2nd & 3rd, 2nd & 4th, 2nd & 5th, 3rd & 4th, 3rd & 5th, 4th & 5th.

Ten choices, ten routes. Mathematicians call this number “5 choose 2”: the number of ways to choose 2 things out of 5, when the order you choose them in doesn’t matter (How Many Handshakes at a Party of 30? counted pairs of people the same way). It is written

$\binom{5}{2} = 10,$

and on calculators as ${}^5C_2$ or nCr. Every number in Pascal’s triangle is one of these: the number in row n, place k is “n choose k”, written $\binom{n}{k}$ . Row 4, place 2 is $\binom{4}{2} = 6$ : six words of 4 letters with 2 N’s, six routes to the corner 2 blocks each way.

School is 5 blocks east and 1 block north. How many routes?

Pick an answer to see why.

Counting without the triangle

Here is how to find “7 choose 3”, the routes of the 4 × 3 map, without drawing anything. A route is 7 blocks with 3 N’s. Choose the places of the N’s one at a time:

the first N can go in any of 7 places;
the second in any of the 6 left;
the third in any of the 5 left.

That is 7 × 6 × 5 = 210 ways to choose, one after another. But this counts each route several times. The route with N’s in places 1, 4 and 6 was counted when you chose 1, then 4, then 6, and also when you chose 4, then 1, then 6, and so on: 146, 164, 416, 461, 614, 641. Three places can be put in order in 3 × 2 × 1 = 6 ways, so every route was counted 6 times:

$\binom{7}{3} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = \frac{210}{6} = 35.$

The same way, the 5 × 5 map has 10 blocks with 5 N’s, $\frac{10 \times 9 \times 8 \times 7 \times 6}{5 \times 4 \times 3 \times 2 \times 1} = 252$ , and a map 10 blocks each way has $\binom{20}{10} = 184{,}756$ routes: enough for a different walk every day of the year for more than 500 years.

In higher grades you will see this written with factorials, 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1, as $\binom{7}{3} = \frac{7!}{3! \times 4!}$ . It is the same calculation: the 4 × 3 × 2 × 1 below cancels the end of the 7! above.

Patterns in the triangle

Pascal’s triangle is full of patterns, and every one of them has a reason on the map. Play with the triangle below, then read on.

Tap a number to see the two it is made from and what its row adds up to. Then color the odd numbers, and try 16 and 32 rows.

Rows:

Color:

Made from: 3 + 3
Its row adds up to: 16 = 2⁴

Row 4, place 2: 6. On the turned map this is the corner 2 blocks one way and 2 the other from home, and 6 routes lead to it.

Each row reads the same both ways, 1 5 10 10 5 1: swapping east and north (the think box above).
The second diagonal counts 1, 2, 3, 4, 5…: a walk with just one block north, and that block can be any one of the walk’s blocks.
The third diagonal is 1, 3, 6, 10, 15…, the triangular numbers of How Many Handshakes at a Party of 30?, the dots in a triangle of 1, 2, 3, 4… rows. Bhaskara listed these as “sums” in the Lilavati, and the next diagonal, 1, 4, 10, 20, 35, as “summed sums”.
Each row adds up to double the row above: 1, 2, 4, 8, 16, 32… Row 4 adds to 1 + 4 + 6 + 4 + 1 = 16.

Why do the rows double? Row 4 holds every corner 4 blocks from home, so its total is the number of all walks of 4 blocks, east or north, ending anywhere. Each block is a choice of 2, so there are 2 × 2 × 2 × 2 = 16 walks: the same doubling as the rice on the chessboard. Row n adds up to $2^n$ .

Color the odd numbers with 16 rows, then 32. What do they make?

Pick an answer to see why.

The odd numbers make the Sierpinski triangle, a pattern made of smaller copies of itself: each triangle of odd numbers is three smaller ones with an upside-down hole between them, and so on, as far as you draw. It comes from adding alone. Odd + odd is even, odd + even is odd, so each number’s oddness depends only on the two above it. Now look at row 16: 1, then fifteen even numbers, then 1. Below it, each of those two 1s starts the same pattern again, as the single 1 at the top did, with only evens between them; so rows 16 to 31 hold two copies of rows 0 to 15 side by side, with an upside-down hole between. The same happens at rows 2, 4, 8, 16, 32…, so the pattern is made of copies of itself. Stripes, a random scatter, or one hole and nothing else can’t come from that. In 32 rows, only 243 of the 528 numbers are odd: 243 = 3⁵, three copies five times over.

(a + b), again and again

In Grade 8 you meet (a + b)² = a² + 2ab + b². Look at its numbers: 1, 2, 1. That is row 2 of the triangle, and it is no accident.

Multiply out (a + b)(a + b)(a + b) by taking one letter from each bracket, every way you can, and multiplying them. Choosing a or b from each of three brackets is like choosing E or N for each of three blocks, so there are 2 × 2 × 2 = 8 choices:

aaa, aab, aba, abb, baa, bab, bba, bbb.

Group the ones that multiply to the same thing. a²b comes from the 3 words with one b: 3 is “3 choose 1”. ab² from the 3 with two b’s. So

$(a + b)^3 = a^3 + 3a^2b + 3ab^2 + b^3,$

with the numbers 1, 3, 3, 1 of row 3. And (a + b)⁴ has 1, 4, 6, 4, 1. This is the binomial theorem (a binomial is a sum of two terms, like a + b): the numbers in (a + b) to the power n are row n of Pascal’s triangle, which is why its numbers are also called binomial coefficients.

When the map changes

A lane is closed

The lane east from the corner (1, 1), one block east and one north, to the next corner is dug up for a new water pipe. How many routes are left on the 4 × 3 map? Turn on Close a lane in the corner widget above and fill it again.

The rule still works, with one change: the corner just past the closed lane can only be reached from the south, so it gets only that number. On the 4 × 3 map school then gets 23 instead of 35.

You can check this another way. A route uses the closed lane if it reaches the corner (1, 1), by 2 routes, walks the lane, and goes on from the corner after it, from where school is still 2 blocks east and 2 north: 6 routes. So 2 × 6 = 12 routes used the lane, and 35 − 12 = 23 don’t.

On the 4 × 3 map your cousin must stop at the shop on the corner 2 east and 1 north to buy a notebook. How many routes go past the shop?

Pick an answer to see why.

There are 3 routes from home to the shop (2 east, 1 north: $\binom{3}{1} = 3$ ), and from the shop to school she still has 2 east and 2 north: 6 routes. Each way to the shop can go on by each way from it, so 3 × 6 = 18 routes, about half of the 35. 3 + 6 = 9 adds where it should multiply, and 35 − 3 = 32 or 35 count routes that miss the shop. You add when a route takes one way or another, and multiply when it takes one way and then another.

A path across the park

The twist: the colony makes a park in one block, with a path straight across it from its south-west corner to its north-east corner. Now a walker has three ways to leave some corners: east, north, or diagonally.

At the corner on the far side of the park path, a third lane arrives, so its number is three numbers added: from the west, from the south, and from the corner across the park. The triangle’s rule doesn’t hold there any more, and every corner beyond it, to the east and north, changes too: on the 3 × 2 map, one park path across the block just east of home (from the corner 1 east to the corner 2 east, 1 north) makes 12 routes instead of 10, the 10 old ones and 2 that cross the park. If every block were a park with a path across it, the 2 × 2 map would have 13 routes instead of 6, and the 3 × 3 map 63 instead of 20. These are the Delannoy numbers, named after Henri Delannoy, a French army officer and amateur mathematician.

Paths for a falling ball

Figure 12.4 A ball dropped on four rows of pegs. The number on each peg counts the paths that reach it, and the bins at the bottom get 1, 4, 6, 4 and 1 of the 16 paths. The dashed path bounces left, right, right, left.

Drop a ball onto a board of pegs, and at each peg it bounces left or right. Turn a left bounce into “east” and a right bounce into “north”, and a ball’s fall is a walk on our map, one block a row. With 4 rows of pegs, there are $2^4 = 16$ paths, and the bins at the bottom collect them as row 4 does: 1, 4, 6, 4, 1 (Figure 12.4).

If a ball is as likely to bounce left as right, all 16 paths are equally likely. So on average, 6 balls in every 16 land in the middle bin and only 1 in 16 in each end bin. Drop 160 balls and about 60 land in the middle; the more balls, the closer the piles come to these shares. With 10 rows the middle bin gets 252 of the 1,024 paths, about a quarter of the balls, and the piles take the shape of a bell.

This board is called a Galton board, after Francis Galton, who made one for a talk at the Royal Institution in London in 1874 and described it in his book Natural Inheritance in 1889. Science Playground has one: drop a few hundred balls through the Galton Board exhibit and watch Pascal’s triangle pile up.

A story from maths

A story from maths: a triangle found again and again

Pascal’s triangle is much older than Pascal, and it was found in many places.

In India, the poet-scholar Pingala, in the 3rd or 2nd century BCE, counted the rhythms a line of verse can have, each syllable short or long, and how many have one long syllable, two, three. His commentator Halayudha, in the 10th century, explained a way of setting the counts out in a triangle, the meru-prastara, “the pyramid expansion”. In the 6th century Varahamihira had a way of finding the same numbers by adding.

$A page of Chinese characters arranged in a triangle of circles, each holding a number written in Chinese rod numerals$

Figure 12.5 The triangle in Zhu Shijie’s Jade Mirror of the Four Unknowns, China, 1303. In China it is called Yang Hui’s triangle, after the mathematician of the century before. Photo: Zhu Shijie, 1303, Public domain

Bhaskara (born 1114), head of the observatory at Ujjain, put the counting into the Lilavati. One of his examples, in Colebrooke’s translation: “In a pleasant, spacious and elegant edifice, with eight doors, constructed by a skilful architect, as a palace for the lord of the land, tell me the permutations of apertures taken one, two, three, &c.” The answer he gives is row 8 of the triangle, 8, 28, 56, 70, 56, 28, 8, 1, “and the changes … amount to 255”. The next asks for the dishes made from six tastes, “sweet, pungent, astringent, sour, salt and bitter”, taken one, two, three at a time: 6, 15, 20, 15, 6, 1, which make 63.

It was found again in Persia, where al-Karaji (953–1029) described it in a book now lost and Omar Khayyam used it, so that Iranians call it “Khayyam’s triangle”; in China, where Jia Xian knew it in the 11th century and it is called “Yang Hui’s triangle” after Yang Hui (13th century); and in Italy, where it is “Tartaglia’s triangle”.

Blaise Pascal (1623–1662) wrote his Treatise on the Arithmetic Triangle late in 1654. That summer he and Pierre de Fermat had worked out, in letters, how to share the stakes of a game of chance stopped before the end. Pascal used the triangle for that problem, for counting choices and for powers like (a + b)ⁿ, and proved its patterns one by one. The treatise was printed in 1654 but only published in 1665, after his death. The name “Pascal’s triangle” came later, from Pierre Raymond de Montmort in 1708 and Abraham de Moivre in 1730.

Where this is used

Questions

How many routes are there to a school 2 blocks east and 2 blocks north?

Pick an answer to see why.

a.★

Write row 7 of Pascal’s triangle from row 6, 1 6 15 20 15 6 1. Check that it adds up to $2^7$ .

Hint

Answer

A school is 6 blocks east and 2 blocks north. How many routes?

Pick an answer to see why.

b.★★

On the 4 × 4 map, how many routes go through the corner in the very middle, 2 blocks east and 2 north? How many avoid it?

Hint

Answer

c.★★

Bhaskara’s palace has eight doors. In how many ways can some of them be open, from one door to all eight? Use his row, 8, 28, 56, 70, 56, 28, 8, 1, then explain the total a quicker way.

Hint

Answer

d.★★★

Add the numbers down the third diagonal of the triangle, 1 + 3 + 6 + 10. Where is the answer in the triangle? Explain why with routes.

Hint

Answer

e.★★★

If every block of a 2 × 2 map is a park with a path straight across it, south-west to north-east, how many routes are there from home to school? Count by numbering the corners.

Hint

Answer

Quiz yourself on this unit →

Where to go next

How Much Rice Is on the Chessboard? The doubling that adds up each row of the triangle, square after square.
How Many Number Plates Can a Province Make? Counting by multiplying, as for the routes past the shop, when every choice can go with every other.
How Many Handshakes at a Party of 30? Choosing 2 people out of 30, which is “30 choose 2”, counted three ways.
Which Total Comes Up Most with Two Dice? Counting the equally likely outcomes, as for the Galton board.
How Many Ways Can You Climb the Stairs? (Grades 9–12) One step or two at a time, and the Fibonacci numbers, which also hide in Pascal’s triangle.
Did Poets in Ancient India Count in Binary? (Computing, Going Further 6–8) Pingala’s long and short syllables, the counting behind his triangle. (Coming soon.)
How Far Does a Wandering Ant Get? (Computing, Going Further 6–8) A walk of random steps, like a ball on the Galton board, run by a program.
Probability (Grade 10 Math) Tree diagrams for tossing coins, where each branch is a block of a route.

Where these facts come from

Pascal’s triangle: Pingala, Halayudha’s meru-prastara, Varahamihira, al-Karaji’s lost book and Khayyam (“Khayyam’s triangle”), Jia Xian, Yang Hui (“Yang Hui’s triangle”) and Zhu Shijie’s book of 1303, Tartaglia (“Tartaglia’s triangle”), Pascal’s treatise published in 1665, the name given by Montmort (1708) and de Moivre (1730); row totals 2ⁿ; the odd numbers and the Sierpinski triangle; shortest paths on a grid; Newton and the powers of 11: Wikipedia, “Pascal’s triangle”; the hockey-stick identity and why it is called that: Wikipedia, “Hockey-stick identity”; both read October 2026.
Pascal’s treatise, its square layout and rule (each cell the one before it in its column plus the one before it in its row), “printed 1654, published 1665”, dated near the end of 1654 alongside the letters with Fermat: Pascal, The Arithmetic Triangle, translated by Richard Pulskamp (2009), rhul.ac.uk, read October 2026 (retold in our own words).
Pascal’s life (1623–1662), the five letters with Fermat in the summer of 1654 on the problem of points: MacTutor, “Blaise Pascal”, read October 2026.
Pingala (3rd–2nd century BCE), the Chandaḥśāstra, short and long syllables, Halayudha’s 10th-century commentary and the meru-prastara: Wikipedia, “Pingala”, read October 2026.
Bhaskara’s rule for combinations, the verse of six syllables (6, 15, 20, 15, 6, 1, 64 in all), the palace with eight doors (8 … 1, 255) and the six tastes (63), the “sums” and “summed sums” (§§ 110–116): H. T. Colebrooke, Algebra, with Arithmetic and Mensuration, from the Sanscrit of Brahmegupta and Bháscara (1817, public domain), Internet Archive, read October 2026.
Bhaskara born 1114, head of the observatory at Ujjain; the Lilavati’s chapter on combinations: MacTutor, “Bhaskara II”, read October 2026. The Lilavati written in 1150, with a chapter on combinations: Wikipedia, “Līlāvatī”, read October 2026.
The binomial theorem: (a + b)² known to Euclid, the coefficients as the rows of Pascal’s triangle, the proof by choosing a or b from each bracket: Wikipedia, “Binomial theorem”, read October 2026.
Lattice paths with east and north steps counted by $\binom{n+k}{n}$ , and the grid turned into Pascal’s triangle: Wikipedia, “Lattice path”, read October 2026.
Delannoy numbers (steps east, north and north-east; the rule of three; 63 for 3 × 3), Henri Delannoy a French army officer and amateur mathematician: Wikipedia, “Delannoy number”, read October 2026.
The Galton board: Francis Galton, his board made for a Royal Institution talk of 27 February 1874, Natural Inheritance (1889), paths to each bin as binomial coefficients, the bell shape with many rows: Wikipedia, “Galton board”, read October 2026.
The binomial distribution, the number of successes in n independent tries; sampling and polling, the binomial test: Wikipedia, “Binomial distribution”, read October 2026.
The 6-from-49 lottery’s 13,983,816 combinations, “49 choose 6”: Wikipedia, “Lottery mathematics”, read October 2026.
Every count, row, sum and answer in this topic (the routes of every map, listed by exhaustive search and checked against the adding rule and “choose”, the closed lane, the shop, the park paths, the Galton board, Bhaskara’s rows, the powers of 11, the odd numbers in 32 rows, and every question) was computed in checks/textbooks/math-further-6-8/12/tmp/numbers.py and corners.py.