A. Counting and Probability · Permutations and Combinations

Pascal's Triangle and Combinations

A2.4About 70 minutes

Learning goals

I can show, through investigation, that the entries of Pascal's triangle are the combinations C(n, r).
I can explain Pascal's identity C(n, r) = C(n − 1, r − 1) + C(n − 1, r) with a counting argument and with algebra.
I can connect the diagonals and row sums of Pascal's triangle to combinations.
I can use Pascal's triangle and its patterns to simplify combination expressions.

Words to know

Pascal's triangle
A triangular array of numbers with 1s on the edges, in which each inside entry is the sum of the two entries above it. Row n (counting the top row as row 0) holds C(n, 0), C(n, 1), …, C(n, n).

Pascal's identity
C(n, r) = C(n − 1, r − 1) + C(n − 1, r), the rule that each entry is the sum of the two above it.

row sum
The sum of the entries in row n of Pascal's triangle, equal to 2ⁿ.

hockey stick identity
C(r, r) + C(r + 1, r) + … + C(n, r) = C(n + 1, r + 1): adding down a diagonal gives the entry just below and to the side.

combinatorial proof
A proof that two expressions are equal by showing they count the same set of objects in two different ways.

Remember from Grade 11

In the unit Sequences and Series (MCR3U) you built Pascal's triangle: 1s down both edges, and every inside entry is the sum of the two entries above it. You wrote this as the recursion tₙ,ᵣ = tₙ₋₁,ᵣ₋₁ + tₙ₋₁,ᵣ, numbering rows and positions from 0. You also found patterns (symmetry, row sums of 2ⁿ, diagonals of natural numbers and triangular numbers) and used the triangle to count routes on a grid and to expand (a + b)ⁿ.

But why do the numbers in this simple addition pattern keep showing up in counting problems? Today you will find out: every entry of Pascal's triangle is a combination.

Investigation: combinations in a triangle

Calculate some combinations and arrange them in rows by n:

n = 2: C(2, 0) = 1, C(2, 1) = 2, C(2, 2) = 1
n = 3: 1, 3, 3, 1
n = 4: C(4, 0) = 1, C(4, 1) = 4, C(4, 2) = 6, C(4, 3) = 4, C(4, 4) = 1
n = 5: 1, 5, 10, 10, 5, 1

These are exactly the rows of Pascal's triangle. The entry in row n, position r, is C(n, r): tₙ,ᵣ = C(n, r).

Rows 0 to 5 written as combinations. Compare with the numbers you know: C(4, 2) sits where the 6 in row 4 is.

Why it works: Pascal's identity

Pascal's triangle is built by the rule "add the two entries above". So combinations must obey the same rule:

C(n, r) = C(n − 1, r − 1) + C(n − 1, r)

A counting argument. Count the committees of r people chosen from n people. Pick one particular person, Alex. Every committee either includes Alex or does not, never both:

Includes Alex: choose the other r − 1 members from the n − 1 other people: C(n − 1, r − 1).
Does not include Alex: choose all r members from the n − 1 other people: C(n − 1, r).

By the additive counting principle, C(n, r) = C(n − 1, r − 1) + C(n − 1, r). Since combinations also have 1s at the edges (C(n, 0) = C(n, n) = 1), they build exactly Pascal's triangle.

This kind of argument, showing two expressions count the same thing, is called a combinatorial proof.

Two examples of Pascal's identity: C(4, 1) + C(4, 2) = 4 + 6 = 10 = C(5, 2), and C(6, 3) + C(6, 4) = 20 + 15 = 35 = C(7, 4).

Worked example

Example 1: Reading combinations from the triangle

Use Pascal's triangle to find C(7, 3) and C(7, 5).

Row 6 is 1, 6, 15, 20, 15, 6, 1. Add neighbouring pairs to get row 7: 1, 7, 21, 35, 35, 21, 7, 1.
Count positions from 0: C(7, 3) is position 3, which is 35.
C(7, 5) is position 5, which is 21 (and by symmetry C(7, 5) = C(7, 2) = 21).

C(7, 3) = 35 and C(7, 5) = 21.

Worked example

Example 2: Using Pascal's identity

Write each as a single combination: (a) C(9, 4) + C(9, 5), (b) C(12, 5) − C(11, 4).

(a) Two neighbours in row 9, positions 4 and 5, add to the entry below them: row 10, position 5. So C(9, 4) + C(9, 5) = C(10, 5).
(b) From the identity, C(12, 5) = C(11, 4) + C(11, 5). Subtract C(11, 4): C(12, 5) − C(11, 4) = C(11, 5).

(a) C(10, 5) (= 252); (b) C(11, 5) (= 462).

Patterns, explained by combinations

Symmetry: each row reads the same both ways because C(n, r) = C(n, n − r).
Diagonals: the diagonal of 1s is C(n, 0); the next diagonal (1, 2, 3, 4, …) is C(n, 1); the next (1, 3, 6, 10, 15, …, the triangular numbers) is C(n, 2), which is also the number of handshakes among n people; the next (1, 4, 10, 20, …) is C(n, 3). (In Grade 11 the diagonals were numbered from 1, starting with the diagonal of 1s. Counting from 0 instead, diagonal r is C(n, r).)
Row sums: C(n, 0) + C(n, 1) + … + C(n, n) = 2ⁿ. Both sides count all the subsets of a set of n objects: the left side counts them by size, and the right side lets each object be in or out.
Hockey stick: C(r, r) + C(r + 1, r) + … + C(n, r) = C(n + 1, r + 1). Add entries down a diagonal, starting from a 1, and the total is the entry just below the last one, on the other side.

The hockey stick. The diagonal entries C(2, 2) to C(6, 2) add to C(7, 3) = 35, just below and to the side.

Worked example

Example 3: Row sums and subsets

How many subsets with at least one element does a set of 10 objects have? Use a row of Pascal's triangle to explain.

Row 10 of Pascal's triangle lists the numbers of subsets of size 0, 1, 2, …, 10. Its sum is 2¹⁰ = 1024.
Remove the empty subset, C(10, 0) = 1.
1024 − 1 = 1023.

1023 subsets.

Worked example

Example 4: Solving with the identity

Find n if C(n, 4) + C(n, 5) = C(11, 5).

By Pascal's identity, C(n, 4) + C(n, 5) = C(n + 1, 5).
So C(n + 1, 5) = C(11, 5), and n + 1 = 11.
Check: C(10, 4) + C(10, 5) = 210 + 252 = 462 = C(11, 5) ✓.

n = 10.

Just for fun

Pascal's triangle has been studied for centuries: Blaise Pascal wrote about it in the 1600s, and in China it is called Yang Hui's triangle after a mathematician of the 1200s. Even so, every entry still only needs two friends above it to hold it up.

Hands-on activity

Subsets of five things

You need: 5 different small objects (for example a spoon, a fork, a cup, a pencil and an eraser), paper and a pencil.

List every possible selection of 0 objects, then 1 object, then 2, 3, 4 and 5 objects. Be systematic (for pairs, pair the first object with each later one, then the second with each later one, and so on).
Record how many selections there are of each size. Compare your list of counts with row 5 of Pascal's triangle.
Add your counts. Compare with 2⁵.
Pick one object, say the spoon. Split your 2-object selections into those with the spoon and those without. How many of each? Match these numbers with entries in row 4.

What to look for: counts 1, 5, 10, 10, 5, 1 (row 5), total 32 = 2⁵. Of the 10 pairs, 4 contain the spoon (C(4, 1)) and 6 do not (C(4, 2)): 4 + 6 = 10, which is Pascal's identity in action.

Your turn

Write row 6 of Pascal's triangle.

Use the triangle to find C(6, 3).

Write C(8, 3) + C(8, 4) as a single combination and evaluate it.

Find n if C(n, 4) + C(n, 5) = C(11, 5).

What is the sum of the entries in row 9?

Which diagonal holds 1, 3, 6, 10, 15, …? What do these numbers count?

Write C(15, 7) − C(14, 7) as a single combination.

More practice: warm-up

Write row 4 of Pascal's triangle.

Find C(5, 2) from the triangle.

What is the sum of row 5?

What is the second entry (position 1) of row 12?

What is C(7, 7)?

More practice: on your own

Write C(20, 8) + C(20, 9) as a single combination.

Find C(3, 3) + C(4, 3) + C(5, 3) + C(6, 3) using the hockey stick, and check by adding.

Evaluate C(6, 0) + C(6, 1) + … + C(6, 6) and say what it counts.

How many subsets with at least 2 elements does a 6-element set have?

Show that 1 − 5 + 10 − 10 + 5 − 1 = 0 and explain using symmetry why this alternating sum is 0 for row 5.

Challenge

Give a combinatorial proof that C(n, r) = C(n − 1, r − 1) + C(n − 1, r), using a class of n students and one particular student, Priya.

Prove the hockey stick identity for r = 1: C(1, 1) + C(2, 1) + … + C(n, 1) = C(n + 1, 2).

Explain why C(n, 0) + C(n, 1) + … + C(n, n) = 2ⁿ by counting the subsets of an n-element set in two ways.

Check your understanding

Quiz

What is the entry in row 6, position 2, of Pascal's triangle (counting from 0)?

Which single combination equals C(9, 4) + C(9, 5)?

What is the sum of the entries in row 8 of Pascal's triangle?

Which statement is Pascal's identity?

The numbers 1, 3, 6, 10, 15 on a diagonal of Pascal's triangle are equal to which combinations?

By the hockey stick identity, 1 + 4 + 10 + 20 equals which combination?

For parents and teachers

Big idea (A2.4): every entry of Pascal's triangle is a combination: row n, position r is C(n, r). The "add the two above" rule is Pascal's identity, and it can be proved by counting committees with and without one particular person.

How to help: Have your teen write the first 8 rows from memory using addition, then check a few entries with the nCr key. Ask them to explain the Alex argument (committees with or without one person) in their own words; explaining it is the best sign of understanding.

Common difficulties:

Counting rows and positions from 1 instead of 0 (row 4 is 1, 4, 6, 4, 1).
Applying Pascal's identity to entries that are not neighbours in the same row.
Mixing up diagonal numbering: name diagonals by the combination they hold (the C(n, 2) diagonal) to avoid confusion.
Forgetting that the row sum 2ⁿ includes the empty set.