Pascal's Triangle

Pascal’s triangle is a triangle of numbers where each number is the sum of the two above it. It looks simple, but it’s full of patterns, and it answers two big questions you’ll meet again: how to expand powers like $(x + y)^5$, and how many ways there are to choose things.

Key ideas

Building the triangle

Start with $1$ at the top. Each row begins and ends with $1$, and every other number is the sum of the two numbers diagonally above it.

$$\begin{array}{ccccccccccccc} & & & & & & 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 \end{array}$$

The rows are numbered from row 0 at the top, so the bottom row shown is row 6. Within a row, positions are also numbered from $0$. We write $t_{n, r}$ for the entry in row $n$, position $r$. For example, $t_{6, 2} = 15$.

The building rule is a recursion formula:

$$t_{n, r} = t_{n - 1, r - 1} + t_{n - 1, r}$$

Patterns to look for

• Symmetry: each row reads the same forwards and backwards.
• Row sums: the numbers in row $n$ add up to $2^n$. Row 3: $1 + 3 + 3 + 1 = 8 = 2^3$.
• Diagonals: the first diagonal is all $1$s, the second is the counting numbers $1, 2, 3, \dots$, and the third is the triangular numbers $1, 3, 6, 10, 15, \dots$
• Hockey stick: add any run of numbers down a diagonal, starting from a $1$, and the total is the number just below and to the side of where you stopped: $1 + 2 + 3 + 4 = 10$.
• Fibonacci: adding along the shallow diagonals gives $1, 1, 2, 3, 5, 8, \dots$

Counting paths and choices

Pascal’s triangle counts routes. On a grid of streets, the number of shortest routes to each corner is the sum of the routes to the corner above it and the corner to its left, the same adding rule as the triangle.

The entry $t_{n, r}$ is also the number of ways to choose $r$ items from $n$. In Data Management you’ll write this as $\dbinom{n}{r}$, read ”$n$ choose $r$”. For example, there are $\dbinom{6}{2} = t_{6, 2} = 15$ ways to choose $2$ people from a group of $6$.

Worked examples

Example 1: The next row

Use row 6 to write row 7.

Solution. Row 6 is $1, 6, 15, 20, 15, 6, 1$. Add neighbouring pairs, and put a $1$ at each end:

$$1, \quad 1 + 6 = 7, \quad 6 + 15 = 21, \quad 15 + 20 = 35, \quad 20 + 15 = 35, \quad 21, \quad 7, \quad 1$$

Row 7 is $1, 7, 21, 35, 35, 21, 7, 1$. Its sum is $128 = 2^7$, as expected.

Example 2: Row sums

What is the sum of the numbers in row 10?

Solution. Row $n$ sums to $2^n$, so row 10 sums to $2^{10} = 1024$.

Example 3: Routes on a grid

How many shortest routes are there from the top-left corner of a street grid to a corner $3$ blocks right and $2$ blocks down?

Solution. Write a $1$ at every corner along the top edge and the left edge: there’s only one way to reach them (straight along the edge). Every other corner is the sum of the corner above and the corner to the left:

$$\begin{array}{cccc} 1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 4 \\ 1 & 3 & 6 & \mathbf{10} \end{array}$$

There are $10$ shortest routes. Notice that $10$ is $t_{5, 2}$ in Pascal’s triangle: every route is $5$ blocks long, and you choose which $2$ of them go down.

Example 4: Triangular numbers and the hockey stick

Find the triangular numbers in the triangle, and use the hockey-stick pattern to add $1 + 3 + 6 + 10$.

Solution. The triangular numbers $1, 3, 6, 10, 15, \dots$ run down the third diagonal: $t_{2, 2}, t_{3, 2}, t_{4, 2}, t_{5, 2}, \dots$

$1 + 3 + 6 + 10$ is a run down that diagonal from row 2 to row 5. The hockey stick says the sum is the entry just below the last one, on the next diagonal: $t_{6, 3} = 20$. Check: $1 + 3 + 6 + 10 = 20$. ✓

Common mistakes

Numbering rows from 1. The single $1$ at the top is row 0. Row 5 is $1, 5, 10, 10, 5, 1$, which has $6$ entries.

Numbering positions from 1. In row 6, position $0$ is $1$ and position $2$ is $15$.

Adding the wrong pair. Each entry comes from the two numbers directly above it (up-left and up-right), not from its neighbours in the same row.

Forgetting the symmetry check. If a row you’ve built isn’t symmetric, there’s an arithmetic error.

Practice

1. (Warm-up) Write rows 0 to 5 of Pascal’s triangle.

Solution

Row 0: $1$; row 1: $1, 1$; row 2: $1, 2, 1$; row 3: $1, 3, 3, 1$; row 4: $1, 4, 6, 4, 1$; row 5: $1, 5, 10, 10, 5, 1$.

2. (Warm-up) What is the sum of row 8?

Solution

$2^8 = 256$.

3. (Warm-up) Row 7 is $1, 7, 21, 35, 35, 21, 7, 1$. Write row 8.

Solution

$1, 8, 28, 56, 70, 56, 28, 8, 1$

4. (Core) Find $t_{7, 3}$.

Solution

Row 7 is $1, 7, 21, 35, \dots$, so position $3$ is $t_{7, 3} = 35$.

5. (Core) How many shortest routes are there from one corner of a street grid to a corner $4$ blocks right and $2$ blocks down?

Solution

Fill in the grid by adding the corner above and the corner to the left:

$$\begin{array}{ccccc} 1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 4 & 5 \\ 1 & 3 & 6 & 10 & \mathbf{15} \end{array}$$

There are $15$ routes. (That’s $t_{6, 2}$: routes are $6$ blocks long, and you choose which $2$ go down.)

6. (Core) Use the hockey-stick pattern to find $1 + 4 + 10 + 20$ (a run down the fourth diagonal, starting at row 3), then check by adding.

Solution

These are $t_{3, 3}, t_{4, 3}, t_{5, 3}, t_{6, 3}$. The hockey stick gives the entry below the last one, on the next diagonal: $t_{7, 4} = 35$.

Check: $1 + 4 + 10 + 20 = 35$. ✓

7. (Core) A row of Pascal’s triangle starts $1, 12, 66, \dots$ Which row is it, and what is the next entry?

Solution

The second entry of row $n$ is $n$, so it’s row 12. The next entry is $t_{12, 3}$. Using the row above (row 11 starts $1, 11, 55, 165$): $t_{12, 3} = t_{11, 2} + t_{11, 3} = 55 + 165 = 220$.

8. (Challenge) Add the numbers along the shallow diagonals of the triangle (start at the left edge and go up and to the right, one row up and one place over each step). Show that the first six sums are Fibonacci numbers.

Solution

$$\begin{aligned} &1 \\ &1 \\ &1 + 1 = 2 \\ &1 + 2 = 3 \\ &1 + 3 + 1 = 5 \\ &1 + 4 + 3 = 8 \end{aligned}$$

The sums are $1, 1, 2, 3, 5, 8$: the start of the Fibonacci sequence.

9. (Challenge) Explain why each row sum is double the previous one.

Solution

When you build row $n + 1$, each number in row $n$ is added into two entries below it: the one down-left and the one down-right. So every number in row $n$ is counted twice in row $n + 1$, and the row sum doubles. Starting from row 0’s sum of $1$, row $n$ sums to $2^n$.