M5.1.6 Chapter 6

Pascal's triangle and choosing

In how many ways can I choose 2 friends from 4?

Your guess

Pick one before you read on. It is fine to be wrong.

Your guess

A 8, because 4 × 2.
You picked A. Read on. At the end, the chapter comes back to your guess.
B 6.
You picked B. Read on. At the end, the chapter comes back to your guess.
C 12, because 4 × 3.
You picked C. Read on. At the end, the chapter comes back to your guess.

By the end you can

Build Pascal's triangle and link it to (a + b)ⁿ
Find nCr, the number of ways to choose r things from n

Start with powers of a + b. (a + b)¹ = a + b. And (a + b)² = a² + 2ab + b². To get (a + b)³, multiply (a + b)² by (a + b).

(a + b)(a² + 2ab + b²) = a³ + 2a²b + ab² + a²b + 2ab² + b³ = a³ + 3a²b + 3ab² + b³. Look at the numbers in front: 1 and 1, then 1, 2, 1, then 1, 3, 3, 1.

Every term of (a + b)ⁿ has total power n. The power of a goes down from n to 0, and the power of b goes up from 0 to n. Only the numbers in front, the coefficients, need work.

Pascal's triangle lists these coefficients. Row 0 is the single number 1. Every row starts and ends with 1. Every other number is the sum of the two numbers just above it. We count the rows and the places in a row from 0.

Row n gives the coefficients of (a + b)ⁿ. Row 3 reads 1, 3, 3, 1, as in the expansion above.

Each entry is the sum of the two above it: 4 + 6 = 10.

Why does the rule work? Take (a + b)ⁿ and multiply by (a + b) to get (a + b)ⁿ⁺¹. (In this book ^ means "to the power", because the font has no raised r.) A term a^(n + 1 − r) b^r in the result can arise in two ways. It comes from a times the term a^(n − r) b^r, or from b times the term a^(n + 1 − r) b^(r − 1). So its coefficient is the sum of two neighbouring coefficients of row n. That is the rule.

Worked example

Use Pascal's triangle to expand (a + b)⁵.

Row 4 is 1, 4, 6, 4, 1. Build row 5 from it. Each entry is the sum of two above it: 1 + 4 = 5, then 4 + 6 = 10.
The rest follows by symmetry. The coefficients are 1, 5, 10, 10, 5, 1.
The power of a goes down from 5 to 0, and the power of b goes up from 0 to 5. Each term has total power 5.
Write the terms: a⁵, 5a⁴b, 10a³b², 10a²b³, 5ab⁴, b⁵.
Check with a = 1 and b = 1: the left side is 2⁵ = 32. The coefficients add to 1 + 5 + 10 + 10 + 5 + 1 = 32.

Answer: a⁵ + 5a⁴b + 10a³b² + 10a²b³ + 5ab⁴ + b⁵

The triangle gets long. For a high row, or for one entry, we want a formula. For that we count ways of choosing.

Suppose Amina, Ravi, Mei and Kofi are to be paired. Choosing 2 from 4 gives 6 pairs. In general, the number of ways to choose r things from n, when the order does not matter, is written nCr and read "n choose r". It is called a binomial coefficient.

The last row shows the raised and lowered form on a line: ⁵C₂ is the same number as 5C2. Two more ways are given in words. Other books print n and r one above the other in tall brackets. Others write n small and raised before the C, and r small and lowered after it. All mean the same number.

The 6 pairs from A, B, C and D: 3 pairs contain A, and 3 do not.

This picture shows Pascal's rule for choosing. Choose 2 from 4 people. Either A is in the pair: then choose 1 more from the other 3, which is 3C1 = 3 ways. Or A is out: choose 2 from the other 3, which is 3C2 = 3 ways. So 4C2 = 3C1 + 3C2 = 6.

In general nCr = (n − 1)C(r − 1) + (n − 1)Cr. That is the same sum as the triangle makes, so the entry in row n and place r of Pascal's triangle is nCr.

Now the formula. We need the factorial: n! = n × (n − 1) × … × 2 × 1, for a whole number n. So 5! = 5 × 4 × 3 × 2 × 1 = 120. We also define 0! = 1.

Factorials grow quickly. Note that 0! = 1, by definition.

Why define 0! = 1? There is exactly one way to choose nothing from n things. The formula below gives nC0 = n!/(0! × n!), which equals 1 only if 0! = 1.

To find a formula, choose r things in order. There are n ways for the first, n − 1 for the second, and so on down to n − r + 1 for the last: n(n − 1)…(n − r + 1) ways. Each group of r is counted r! times, once for each order. So we divide by r!.

The result is nCr = n!/(r!(n − r)!), for whole numbers n and r with 0 ≤ r ≤ n. Multiplying the top n! by 1/(n − r)! cancels the tail of the factorial: nCr = n(n − 1)…(n − r + 1)/r!.

Two facts help. nCr = nC(n − r), because choosing r to take is the same as choosing n − r to leave behind. And nC0 = nCn = 1, and nC1 = n.

See it three ways

With things

Amina, Ravi, Mei and Kofi. Choose 2 of them for a pair. List every pair: AR, AM, AK, RM, RK, MK. There are 6.

As a picture

In words

Row 4, place 2 of the triangle is the number of ways to choose 2 from 4.

In symbols

4C2 = 4!/(2! × 2!) = 24/(2 × 2) = 6, and also 4C2 = (4 × 3)/(2 × 1) = 6.

Worked example

Work out 7C3. Then write down 7C4 using symmetry.

Use nCr = n(n − 1)…(n − r + 1)/r!. For 7C3 there are 3 numbers on top, starting at 7.
7C3 = (7 × 6 × 5)/(3 × 2 × 1).
The top is 7 × 6 × 5 = 210. The bottom is 3 × 2 × 1 = 6.
210 ÷ 6 = 35. So 7C3 = 35.
Symmetry: 7C4 = 7C(7 − 4) = 7C3, because choosing 4 to take is choosing 3 to leave.
So 7C4 = 35. Check with the formula: 7!/(4! × 3!) = 5040/(24 × 6) = 5040/144 = 35.

Answer: 7C3 = 35 and 7C4 = 35.

Worked example

A club has 5 men and 3 women. A committee of 3 is chosen. How many committees are possible? How many have no women? How many have at least one woman?

Any 3 of the 8 people may be chosen, and the order does not matter. The number of committees is 8C3 = (8 × 7 × 6)/(3 × 2 × 1) = 336/6 = 56.
No women means all 3 come from the 5 men: 5C3 = (5 × 4 × 3)/(3 × 2 × 1) = 60/6 = 10.
"At least one woman" is every committee except the ones with no women: 56 − 10 = 46.
Check by adding the cases. One woman: 3C1 × 5C2 = 3 × 10 = 30. Two women: 3C2 × 5C1 = 3 × 5 = 15. Three women: 3C3 × 5C0 = 1. And 30 + 15 + 1 = 46.

Answer: 56 committees, 10 with no women, and 46 with at least one woman.

Worked example

(a) Show that nC2 = n(n − 1)/2. (b) Hence find n when nC2 = 28.

nC2 = n!/(2! × (n − 2)!).
Write n! = n × (n − 1) × (n − 2)!. The factor (n − 2)! cancels with the one on the bottom.
So nC2 = n(n − 1)/2!. And 2! = 2, so nC2 = n(n − 1)/2. This proves (a).
For (b), solve n(n − 1)/2 = 28. Multiply both sides by 2 and expand the bracket: n² − n = 56.
Rearrange to n² − n − 56 = 0 and factorise: (n − 8)(n + 7) = 0. So n = 8 or n = −7.
But n is a number of things, so n is a whole number from 2 up. Reject −7. So n = 8.
Check: 8C2 = (8 × 7)/2 = 28.

Answer: n = 8

The term of (a + b)⁴ with b to the power r has coefficient 4Cr. Add the five terms to get (a + b)⁴.

This links the two halves of the chapter. In (a + b)ⁿ, each term comes from choosing, in each of the n brackets, either a or b. A term with r letters b comes from choosing which r of the n brackets give b. There are nCr ways to choose them. So the coefficient is nCr.

This gives the binomial theorem for a positive whole number n: (a + b)ⁿ = aⁿ + nC1 aⁿ⁻¹b + nC2 aⁿ⁻²b² + … + bⁿ. The next chapter uses it.

Try it

Build the triangle yourself

You need: paper, a pencil.

Write a single 1 at the top. This is row 0.
Write row 1 under it: 1 and 1.
For each new row, write a 1 at each end. Between them, write the sum of the two numbers above.
Build down to row 5. Ring the entry in row 5, place 2, and check that it equals the sum of the two entries above it.

What you will see: The ringed entry is 10, and it is 4 + 6. Every entry of the triangle is a number of ways to choose.

If you cannot try it, this is what happens.

A wrong idea many people have

(a + b)² = a² + b².

Why it feels right: The square of a product splits, as in (ab)² = a²b², so the square of a sum seems to split too.

The test that breaks it: Put a = 1 and b = 1. Then (a + b)² = 4, but a² + b² = 2.

What is true: There is a middle term: (a + b)² = a² + 2ab + b². In general (a + b)ⁿ has n + 1 terms, with the coefficients from row n of Pascal's triangle.

A wrong idea many people have

0! = 0.

Why it feels right: The factorial multiplies numbers down to 1, and a product that reaches 0 is 0.

The test that breaks it: If 0! were 0, the formula for nC0 would divide by 0. But there is exactly one way to choose nothing, so nC0 = 1.

What is true: 0! = 1. It is defined this way so that the formula n!/(r!(n − r)!) works for r = 0 and r = n.

A wrong idea many people have

Choosing 2 from 4 can be done in 4 × 3 = 12 ways.

Why it feels right: There are 4 choices for the first person and 3 for the second, so multiplying looks right.

The test that breaks it: List the pairs from A, B, C and D. There are only 6: AB, AC, AD, BC, BD, CD. The product 12 counts AB and BA as different.

What is true: When the order does not matter, divide by the number of orders, r!. So 4C2 = (4 × 3)/2! = 6.

A wrong idea many people have

The numbers 1, 3, 3, 1 are row 4, so they give the coefficients of (a + b)⁴.

Why it feels right: There are four numbers, and 4 is the number of numbers.

The test that breaks it: Check (a + b)³ = a³ + 3a²b + 3ab² + b³. The coefficients are 1, 3, 3, 1. And (a + b)⁴ has five terms.

What is true: Count the rows from 0. Row n has n + 1 numbers and gives the coefficients of (a + b)ⁿ. So 1, 3, 3, 1 is row 3.

Key words

Pascal's triangle: a triangle of numbers where each entry is the sum of the two above it. Row n gives the coefficients of (a + b)ⁿ.
binomial coefficient: the number nCr, the coefficient of a^(n − r) b^r in (a + b)ⁿ.
factorial: n! = n × (n − 1) × … × 1, with 0! = 1.

Back to your guess

The answer is B: 6.

Call the friends A, B, C and D. The pairs are AB, AC, AD, BC, BD and CD: 6 pairs. The sum 4 × 3 = 12 counts every pair twice, once in each order, and "A then B" is the same pair as "B then A". The number of ways to choose r things from n is written nCr, and 4C2 = 6.

Keep it

Copy this into your exercise book.

Pascal's triangle: each entry is the sum of the two above; row n gives (a + b)ⁿ. nCr = n!/(r!(n − r)!) counts choices; 0! = 1. nCr = nC(n − r).

Draw: The first six rows of Pascal's triangle, with one entry shown as the sum of the two above it.