Pascal's Triangle

Lesson 4 of 11 · 7 min · Free, no account needed

What you will learn

Routes that go only right or up: the count at a crossing is the sum of the counts from the left and from below.
Turned on its corner, the grid of counts is Pascal's triangle: every number is the sum of the two above it.
The number in row n, place k is C(n, k): 6 in row 4 is C(4, 2).
Building a new row from the last one is what programmers call dynamic programming.

Walking to school, you only go right or up.
How many different routes are there through this town? Drag to your bet.
A smaller town first. Walk every different route.
Tap the glowing crossing to take a step. Each finished route goes into the gallery.
Count routes without walking them.
For each glowing crossing, tap how many routes reach it.
Now turn the town on its corner.
Watch where the numbers land.
This is Pascal's triangle.
Rows start and end with 1. Every other number is the sum of the two above it.
This is Pascal's triangle, known in China, India and Persia centuries before Pascal.
Row 4, place 2 is 6 = C(4, 2): the routes with 2 rights out of 4 steps. Rows and places count from 0.
Grow the triangle: fill rows 5 and 6.
Tap a slot, then a tile. Some tiles are traps.
Each place is reached from the two places above it, so it is their sum: 10 + 10 = 20 in the middle of row 6.
Game: road works. Close one crossing to leave the target number of routes.
Tap a crossing for the cone, then Close it. The numbers show what's left.
A program builds each row from the row before.
It builds row 4 from row 3. Drag the pin to the number it prints, then Run.
The loop runs 3 times and adds 1 + 3, 3 + 3, 3 + 1, so new becomes 1 4 6 4 1, and 1 + 4 + 6 + 4 + 1 = 16. Every row sums to a power of 2.
Each number is the sum of the two above it.
Run the triangle down to row 15 and colour the odd numbers.

Lessons are interactive and need JavaScript. Turn it on to play them.