Skip to content

Pascal's triangle

Counting and combinations · level 5, lesson 3 of 6

A question to start

A ball is dropped onto a board of pegs. Each time it hits a peg it bounces either left or right, and then falls onto a peg in the next row. After four rows of pegs it lands in one of five bins at the bottom.

1 11 121 1331 146 41

The numbers show how many different routes reach each peg and each bin. The middle bin can be reached in 6 ways, but each end bin in only 1 way, which is why balls pile up in the middle. Where do 1, 4, 6, 4, 1 come from? They are \(\dbinom{4}{0}, \dbinom{4}{1}, \dbinom{4}{2}, \dbinom{4}{3}, \dbinom{4}{4}\), and they sit in one of the most famous pictures in mathematics.

The idea

Building the triangle

Write a 1 at the top. Each new row starts and ends with 1, and every other number is the sum of the two numbers just above it, one to the upper left and one to the upper right.

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

The green 4 and 6 add to the orange 10 below them. The rows continue for ever:

Row Numbers
7 1, 7, 21, 35, 35, 21, 7, 1
8 1, 8, 28, 56, 70, 56, 28, 8, 1
9 1, 9, 36, 84, 126, 126, 84, 36, 9, 1
10 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1

The triangle is named after the French mathematician Blaise Pascal, who wrote a long study of it in the 1600s. But it was known centuries earlier in India, Persia and China; in China it is called Yang Hui's triangle, after a mathematician of the 1200s.

The triangle is a table of choose numbers

Number the rows from 0 at the top (so the single 1 is row 0), and number the places in each row from 0 on the left. Then:

The number in row \(n\), place \(r\), is \(\dbinom{n}{r}\).

Check a few. Row 5, place 2 is 10, and \(\dbinom{5}{2} = \dfrac{5 \times 4}{2} = 10\). ✓ Row 6, place 3 is 20, and \(\dbinom{6}{3} = \dfrac{6 \times 5 \times 4}{6} = 20\). ✓ Row 10 is exactly the table from lesson 2.

But checking a few cases is not a reason. Why should "add the two above" produce "the number of ways to choose"?

Why: is Dee on the team or not?

Look at \(\dbinom{5}{2}\): choose 2 people from A, B, C, D, E. Fix your attention on one person, say D (Dee). Every team of 2 either includes Dee or does not.

  • Dee is in. Then you only have to choose her partner from the other 4: \(\dbinom{4}{1} = 4\) teams (AD, BD, CD, DE).
  • Dee is out. Then both members come from the other 4: \(\dbinom{4}{2} = 6\) teams (AB, AC, AE, BC, BE, CE).

No team is in both lists, and every team is in one of them. So \(\dbinom{5}{2} = 4 + 6 = 10\). And 4 and 6 are exactly the two numbers above the 10 in row 5!

The same argument works for any \(n\) and \(r\). Choose \(r\) people from \(n\), and look at one particular person.

  • If that person is in, choose the other \(r - 1\) from the remaining \(n - 1\): \(\dbinom{n-1}{r-1}\) ways.
  • If that person is out, choose all \(r\) from the remaining \(n - 1\): \(\dbinom{n-1}{r}\) ways.
\[\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}\]

This is called Pascal's rule. In the triangle, \(\dbinom{n-1}{r-1}\) and \(\dbinom{n-1}{r}\) are the two numbers just above \(\dbinom{n}{r}\) (row \(n - 1\), places \(r - 1\) and \(r\)). So the choose numbers obey the same adding rule as the triangle.

The ends match too: \(\dbinom{n}{0} = 1\) and \(\dbinom{n}{n} = 1\). So the choose numbers and the triangle start with the same top, have the same 1s down both edges, and are built row by row by the same rule. Then they must agree in every row, all the way down: row 1 agrees, so row 2 (made from row 1) agrees, so row 3 agrees, and so on for ever. This "and so on for ever" kind of proof is called induction.

Every row adds up to a power of 2

Add the rows: \(1\), \(1 + 1 = 2\), \(1 + 2 + 1 = 4\), \(1 + 3 + 3 + 1 = 8\), \(1 + 4 + 6 + 4 + 1 = 16\). They double each time, so row \(n\) adds up to \(2^n\). Two reasons, both worth knowing:

  • By counting. Row \(n\) lists how many groups of each size you can choose from \(n\) things: groups of 0, of 1, of 2, ..., of \(n\). Added together, that is the number of all possible groups, of any size. And to make a group, you go through the \(n\) things and say "in" or "out" to each one: 2 choices, \(n\) times, so \(2^n\) groups (level 3).
  • By adding. Every number in a row is used twice when you build the next row: once by the number below-left and once by the number below-right. So the next row's total is twice this row's total.

A group chosen from a set, of any size, is called a subset. So a set of \(n\) things has \(2^n\) subsets, and row \(n\) of Pascal's triangle sorts them by size.

Paths down the triangle

The peg board explains another meaning. To reach row \(n\), place \(r\) from the top, a ball makes \(n\) bounces, and exactly \(r\) of them must be to the right. A route is fixed by choosing which \(r\) of the \(n\) bounces go right: \(\dbinom{n}{r}\) ways. And the adding rule is clear here too: every route to a peg arrives from the peg above-left or the peg above-right. This idea, "choose which steps go which way", is the key to the next lesson.

Worked examples

1. Two new rows. Build rows 7 and 8 from row 6 (1, 6, 15, 20, 15, 6, 1).

  • Row 7: \(1\), \(1 + 6 = 7\), \(6 + 15 = 21\), \(15 + 20 = 35\), \(20 + 15 = 35\), \(15 + 6 = 21\), \(6 + 1 = 7\), \(1\).
  • Row 8: \(1\), \(8\), \(7 + 21 = 28\), \(21 + 35 = 56\), \(35 + 35 = 70\), \(56\), \(28\), \(8\), \(1\).
  • Check row 8 adds to \(2^8 = 256\): \(1 + 8 + 28 + 56 + 70 + 56 + 28 + 8 + 1 = 256\). ✓

2. Pascal's rule with bigger numbers. Find \(\dbinom{9}{4}\) from row 8.

\(\dbinom{9}{4} = \dbinom{8}{3} + \dbinom{8}{4} = 56 + 70 = 126\). Check with the formula: \(\dfrac{9 \times 8 \times 7 \times 6}{24} = \dfrac{3024}{24} = 126\). ✓

3. All the subsets of a set. List every subset of {a, b, c, d}, sorted by size.

Size Subsets How many
0 { } (the empty set) 1
1 {a}, {b}, {c}, {d} 4
2 {a,b}, {a,c}, {a,d}, {b,c}, {b,d}, {c,d} 6
3 {a,b,c}, {a,b,d}, {a,c,d}, {b,c,d} 4
4 {a,b,c,d} 1

The counts are row 4, and the total is \(16 = 2^4\). ✓

4. Pizza with any toppings. A shop has 8 toppings and lets you have any number of them, from none (plain) to all eight. How many different pizzas? Each topping is in or out: \(2^8 = 256\). How many have at least 2 toppings? Take away the plain one and the 8 one-topping pizzas: \(256 - 1 - 8 = 247\).

Try it

  1. Build rows 9 and 10 from row 8 (1, 8, 28, 56, 70, 56, 28, 8, 1).
  2. Use Pascal's rule and row 10 to find \(\dbinom{11}{4}\) and \(\dbinom{11}{5}\). Check one with the formula.
  3. You are told \(\dbinom{11}{4} = 330\) and \(\dbinom{11}{5} = 462\). Find \(\dbinom{12}{5}\) without the formula.
  4. What do the numbers in row 12 add up to?
  5. A set has 5 things. How many subsets does it have? How many have at least 2 things?
  6. In a group of 7 people, how many committees of 3 include Ana? How many do not? Check that your two answers add up to \(\dbinom{7}{3}\).
  7. Work out \(1 - 5 + 10 - 10 + 5 - 1\) (row 5 with alternate signs). Explain from the symmetry of the row why the answer is the same for every odd row.
  8. In the peg board, a ball goes through 6 rows of pegs, so it makes 6 bounces. How many bins are there? How many routes end in the middle bin, and how many routes are there altogether?
Answers
  1. Row 9: 1, 9, 36, 84, 126, 126, 84, 36, 9, 1 (for example \(28 + 56 = 84\) and \(56 + 70 = 126\)). Row 10: 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1 (for example \(126 + 126 = 252\)).
  2. Row 10 places 3, 4, 5 are 120, 210, 252. So \(\dbinom{11}{4} = 120 + 210 = 330\) and \(\dbinom{11}{5} = 210 + 252 = 462\). Check: \(\dbinom{11}{4} = \dfrac{11 \times 10 \times 9 \times 8}{24} = \dfrac{7920}{24} = 330\). ✓
  3. \(\dbinom{12}{5} = \dbinom{11}{4} + \dbinom{11}{5} = 330 + 462 = 792\).
  4. \(2^{12} = 4096\).
  5. \(2^5 = 32\) subsets. Take away the empty set and the 5 single ones: \(32 - 1 - 5 = 26\).
  6. With Ana: choose 2 others from 6, \(\dbinom{6}{2} = 15\). Without Ana: choose 3 from 6, \(\dbinom{6}{3} = 20\). \(15 + 20 = 35 = \dbinom{7}{3}\). ✓ This is Pascal's rule for row 7.
  7. \(1 - 5 + 10 - 10 + 5 - 1 = 0\). An odd row has an even number of entries, and the row is a mirror image. The entry in place \(r\) and its mirror in place \(n - r\) are equal, and since \(n\) is odd, one of \(r\) and \(n - r\) is even and the other odd, so they get opposite signs and cancel in pairs. (It also comes out 0 for even rows, such as \(1 - 4 + 6 - 4 + 1 = 0\), but that needs a different reason: see level 7.)
  8. 6 bounces give 7 bins (0 to 6 bounces to the right). The middle bin is 3 rights out of 6: \(\dbinom{6}{3} = 20\) routes. Altogether \(2^6 = 64\) routes.

Common mistake

Counting rows and places from 1 instead of 0. The row 1, 4, 6, 4, 1 is row 4, not row 5, and the 6 is in place 2, not place 3. If you count from 1, every answer is off by one row. A quick check: the second number in row \(n\) is always \(n\).

Adding numbers that are not directly above. Each entry is the sum of the two numbers touching it from above, not two numbers next to each other in its own row. Keep the triangle neatly lined up so the "parents" of each number are clear.

Where it leads