Counting, Permutations & the Binomial Theorem — Print
Expanding a bracket and counting arrangements turn out to be the same question.
What the practice questions cover
These questions use 4 ideas from the course. Follow any of them for a definition, where it is taught, and what it leads to.
- Independent — The first event does not change the second — like rolling a die twice.
- Coefficient — The number multiplying a variable — the 3 in 3n.
- Permutation — An arrangement where order matters. P(n,r) = n!(n-r)!.
- Combination — A selection where order does not matter. C(n,r) = n!r!(n-r)!.
Multiply out (a+b)3 by hand and look at the coefficients.
You get a3 + 3a2b + 3ab2 + b3. The numbers are 1, 3, 3, 1.
Nobody calculated those. Each term comes from picking a or b from each of the three brackets.
There are three ways to pick exactly one b, which is why a2b arrives three times.
So the coefficient is a count of choices, not an arithmetic result. Pascal’s triangle is a counting table, and the binomial theorem is the sentence that says so.
Multiply the choices
If a meal is one of 4 starters and one of 3 mains, there are 4 × 3 = 12 meals.
Every independent decision multiplies the count, because each option of the first pairs with all of the second.
That single principle is behind every formula in this unit.
And means times
Choosing this and then that multiplies. Choosing this or that adds. Getting that backwards is the commonest counting error.
Does the order matter?
Gold, silver and bronze from 8 runners: order matters, so it is a permutation, P(8,3) = 336.
A committee of 3 from 8 people: order does not matter, so it is a combination, C(8,3) = 56.
The combination is smaller by exactly 3! = 6, since each committee was counted once for every way of ordering it.
Ask before you calculate
Would swapping two of the chosen items give a different outcome? Yes means permutation, no means combination — and the two answers differ by a factor of r!.
Pascal’s triangle is a table of combinations
Row n of the triangle lists C(n,0), C(n,1), …, C(n,n).
Each entry is the sum of the two above it, because choosing r from n either includes the new item or does not.
That is a proof, not a pattern: the two cases above are exactly the two ways it can happen.
Symmetry for free
C(n,r) = C(n, n-r), because choosing 3 to take is the same as choosing 5 to leave. Use whichever is the smaller calculation.
The binomial theorem
(a+b)n = ∑r=0n C(n,r) an-r br — each term picks b from r of the brackets.
The powers always add to n, which is a useful check on any term you write.
So the coefficient of a2b3 in (a+b)5 is C(5,3) = 10, with no expanding required.
Finding one term
The term with br is C(n,r)an-rbr. You never have to expand the whole thing to answer a question about one term.
Counting and probability together
A probability is a count of favourable outcomes divided by a count of all outcomes.
So both halves of the fraction are counting problems, usually of the same kind.
The probability of 3 heads in 5 flips is C(5,3)25 = 1032.
Count both, consistently
If the top counts unordered selections, the bottom must too. Mixing ordered and unordered counts is what produces impossible probabilities above 1.
Worked examples
Permutation or combination
From 10 students, how many ways to pick a president, a secretary and a treasurer?
- Swapping two of the three chosen people gives different officers, so order matters. That makes it a permutation.
- P(10,3) = 10 × 9 × 8. Ten choices, then nine, then eight.
- = 720. A committee of three from ten would be 120, six times smaller.
720
One binomial term
Find the coefficient of x3 in (x+2)5.
- The general term is C(5,r)x5-r2r. From the binomial theorem.
- For x3 we need 5-r=3, so r=2. The powers add to 5.
- C(5,2) · 22 = 10 × 4 = 40. The 2 gets raised to a power too.
40
Counting into probability
A bag has 5 red and 3 blue marbles. Two are drawn at once. What is the probability both are red?
- Drawn at once means order does not matter, so count combinations. Same kind top and bottom.
- Both red: C(5,2) = 10. All pairs: C(8,2) = 28. Favourable over total.
- 1028 = 514. About 36%.
514
Words to know
- Permutation
- An arrangement where order matters. P(n,r) = n!(n-r)!.
- Combination
- A selection where order does not matter. C(n,r) = n!r!(n-r)!.
- Factorial
- n! is the product of every whole number from 1 to n. 0! = 1.
- Binomial theorem
- The rule expanding (a+b)n using combinations as coefficients.
- Fundamental counting principle
- If one choice has m options and the next has n, together they have mn.
Mistakes to watch for
Using a permutation where order does not matter. A committee of 3 from 8 is C(8,3)=56, not P(8,3)=336 — the permutation counts each committee six times, once per ordering.
Adding when the choices are independent. Four starters and three mains give 12 meals, not 7. "And" multiplies; only "or" adds.
Forgetting to raise the constant to its power. In (x+2)5 the term with x3 carries 22, so the coefficient is 40, not 10.
Mixing ordered and unordered counts in a probability. If the numerator counts unordered pairs, the denominator must too, or the fraction is meaningless.
Treating 0! as 0. It is 1, which is what makes C(n,n)=1 come out right — there is exactly one way to choose everything.
The triangle was known in China as Yang Hui’s triangle three hundred years before Pascal, and in Persia before that.
Every row sums to a power of two, because choosing any subset of n items can be done in 2n ways.
The shallow diagonals of Pascal’s triangle add up to the Fibonacci numbers, for reasons nobody would guess from either definition.
Problem 1
Evaluate 5!.
Worked answer
120
1 · 2 · 3 · 4 · 5 = 120
Problem 2
Evaluate 0!.
Worked answer
1
0! = 1 by definition
Problem 3
A menu has 4 starters and 3 mains. How many two-course meals?
Worked answer
12
4 × 3 = 12
Problem 4
Evaluate C(5,2).
Worked answer
10
5 × 42 = 10
Problem 5
Evaluate P(5,2).
Worked answer
20
5 × 4 = 20
Problem 6
A committee of 3 is chosen from 8 people. Which applies?
- A combination
- A permutation
- Neither
- Both give the same
Worked answer
A combination
No, so order does not matter
Problem 7
Gold, silver and bronze are awarded to 3 of 8 runners. Which applies?
- A permutation
- A combination
- Neither
- Both give the same
Worked answer
A permutation
Yes, so order matters
Problem 8
How many committees of 3 can be chosen from 8 people?
Worked answer
56
8 × 7 × 66 = 56
Problem 9
How many ways to award gold, silver and bronze among 8 runners?
Worked answer
336
8 × 7 × 6 = 336
Problem 10
Give the sum of row 4 of Pascal’s triangle, which is 1, 4, 6, 4, 1.
Worked answer
16
1+4+6+4+1 = 16 = 24
Problem 11
Give the coefficient of a2b3 in the expansion of (a+b)5.
Worked answer
10
5 × 42 = 10
Problem 12
Find the coefficient of x3 in (x+2)5.
Worked answer
40
Need r=2, so C(5,2)22
10 × 4 = 40
Problem 13
Find the coefficient of x2 in (x+3)4.
Worked answer
54
6 × 9 = 54
Problem 14
A bag has 5 red and 3 blue marbles. Two are drawn at once. What is the probability both are red? Give a fraction in lowest terms.
Worked answer
5/14
C(5,2)C(8,2) = 1028
= 514
Problem 15
C(9,7) equals C(9,k) for which smaller k?
Worked answer
2
C(n,r) = C(n,n-r)
9-7 = 2
Problem 16
What is the probability of exactly 3 heads in 5 fair coin flips? Give a fraction in lowest terms.
Worked answer
5/16
C(5,3)25 = 1032
= 516