1The idea in one paragraph

Counting is about not listing. If one decision can be made in 3 ways and the next in 4, the two together can be made in 3 × 4 ways, and everything in the first half of this subtopic is built on that multiplication. Arranging all of n different things is n!; arranging r of them in order is ⁿPᵣ; choosing r of them when order does not matter is ⁿCᵣ, which is ⁿPᵣ divided by the r! orders that no longer count. The second half takes the binomial theorem of 1.9 to powers that are negative or fractions. Then the expansion never ends, and like the geometric series of 1.8 it only adds up to the right answer when x is small enough.

2The two counting principles

The multiplication principle. If one choice can be made in m ways and, for each of those, a second choice can be made in n ways, then the two choices together can be made in m × n ways. The word to listen for is and: a sandwich and a drink, a first digit and a second digit.

The addition principle. If a choice can be made in m ways or in n different ways, with no overlap between the two lists, then it can be made in m + n ways. The word is or: by bus or by train.

Figure 1 draws both: a tree whose 3 branches each split 2 ways, and two lists you pick one item from.

When repetition is allowed, the options do not shrink. A door code of two letters from A to F then three digits has 6² × 10³ = 36 000 possibilities.

3Arranging everything: n factorial

Now take away repetition. Six friends sit in a row of six cinema seats. The first seat can take any of the 6. Once it is filled, the second seat has 5 people left to choose from, the third 4, and so on down to 1.

That product is 6!, read "six factorial". In general, n different objects can be arranged in a row in n! ways. Remember 0! = 1: there is exactly one way to arrange nothing.

Figure 2 shows the idea behind every count in this subtopic: fill the places one at a time, and multiply the number of choices you have at each place. It also shows the next idea coming, since stopping after three places gives 9 × 8 × 7 rather than 9!.

Most questions add a restriction, and three moves handle almost all of them.

Deal with the restricted positions first. If Ana must sit at one end, fill the ends first: Ana takes one of the 2 end seats, then the other 5 people fill the remaining 5 seats in 5! ways. Total 2 × 5! = 240.

Glue together things that must be together. If Ana and Ben must sit next to each other, tie them into a single block, as Figure 3 shows. Now there are 5 units to arrange (the block and the other four people), which is 5! ways, and inside the block Ana and Ben can sit in 2! orders.

Subtract from the total for "not". "Ana and Ben must not sit together" is everything except the arrangements where they do.

4Permutations: choosing some, in order

A permutation is an ordered selection. Nine runners race for gold, silver and bronze. Gold can go to any of 9; silver then to any of the 8 left; bronze to any of 7. The number of possible podiums is 9 × 8 × 7 = 504, as Figure 2 shows.

That is 9! with the unwanted tail 6! divided away, the form the formula booklet uses.

ⁿPᵣ = n! ÷ (n − r)! is the number of ways of choosing r objects from n different objects in order.

So ⁹P₃ = 9! ÷ 6! = 504. In practice you never write the factorials out: ⁿPᵣ is r numbers multiplied together, counting down from n. On Paper 2 the GDC has an nPr function.

Worked example 1. Paper 1. How many four-digit numbers can be made from the digits 1, 2, 3, 4, 5, 6, 7 if no digit may be repeated and the number must be even?

Fill the restricted last place first.

Start from the first digit and you cannot know how many even digits remain.

5Combinations: choosing some, order ignored

A combination is a selection where order does not matter. A committee of three chosen from nine people is the same committee whichever of them you name first.

Figure 4 shows how the two counts are linked. Choosing 3 letters from A, B, C, D in order gives ⁴P₃ = 24 ordered lists. But the lists come in groups of 3! = 6 that contain the same three letters, just in different orders. If order does not matter, each group counts once, so there are 24 ÷ 6 = 4 selections.

ⁿCᵣ = ⁿPᵣ ÷ r! = n! ÷ (r!(n − r)!) is the number of ways of choosing r objects from n different objects when order does not matter.

This is the same ⁿCᵣ you met as a binomial coefficient in 1.9, where it counted the ways of choosing which r brackets supply the b. The committee of three from nine: ⁹C₃ = ⁹P₃ ÷ 3! = 504 ÷ 6 = 84.

Every counting question turns on one decision, and Figure 5 puts it first. Ask "if I swapped two of the chosen items, would I have something different?" A podium, a code, a queue: yes, so use ⁿPᵣ. A committee, a team, a set of lottery numbers: no, so use ⁿCᵣ.

How big these numbers get. A lottery in which you pick 6 numbers from 1 to 49 has ⁴⁹C₆ = 13 983 816 possible tickets. Two tickets a week would take, on average, about 134 000 years to win. The guide asks whether it is ethical to sell such tickets to people who cannot picture numbers that large.

6Harder selections: cases and complements

Exam questions add conditions to selections. There are two tools.

Split into cases for exactly or at least when the cases are few. Cases are joined by or, so add them; within a case, choices from different groups are joined by and, so multiply.

Worked example 2. Paper 1. A team of 5 is chosen from 7 girls and 6 boys. In how many ways can this be done if the team must contain at least 3 girls?

"At least 3 girls" means 3 girls and 2 boys, or 4 girls and 1 boy, or 5 girls and no boys.

Subtract from the total for at least one or not: the unwanted case is usually one easy count.

Worked example 3. Paper 1. From the same 7 girls and 6 boys, how many teams of 5 contain at least one boy?

The only teams with no boys are all-girl teams.

By cases this would need five products; the complement needs two numbers.

A named person must be in, or out. If Zara must be on the team, put her on it and choose the other 4 from the remaining 12: ¹²C₄ = 495. If she must be left out, choose all 5 from the other 12: ¹²C₅ = 792. The two add to ¹³C₅ = 1287, as they must.

Letters of a word. FRIDAY has six different letters, so 6! = 720 arrangements. To begin and end with a vowel, A and I take the two ends in 2 ways and the other four letters fill the middle in 4! ways: 2 × 24 = 48. Arrangements with repeated letters, and arrangements round a circle, are not on the syllabus.

Solving for n. Once r is fixed, ⁿPᵣ and ⁿCᵣ are polynomials in n, so an equation such as ⁿC₂ = 45 becomes n(n − 1)/2 = 45, a quadratic with the positive integer root n = 10. Reject any root that is negative or too small for the selection to make sense.

7The binomial theorem when n is not a whole number

In 1.9 the expansion of (1 + x)ⁿ, for n a positive integer, could be written without ⁿCᵣ at all:

Each coefficient is ⁿCᵣ written out, and this form never asks you to choose r things from n, so nothing stops you putting in n = −1 or n = ½. The formula booklet gives the extended version.

(a + b)ⁿ = aⁿ(1 + n(b/a) + n(n − 1)/2! (b/a)² + …), n ∈ ℚ. When n is not a positive integer the series is infinite, and it is valid only for |b/a| < 1.

Two things change when n stops being a positive whole number. Figure 6 shows the first.

The expansion never ends. For n = 3, every coefficient from x⁴ on contains the factor (n − 3) = 0. For n = −1 or n = ½ the factors never reach zero, so the series goes on for ever, and you are asked for the first few terms, "up to and including the term in x³".

The expansion is only valid for small x. An infinite series can only equal a finite number if its terms shrink fast enough. Take n = −1:

That is a geometric series with first term 1 and common ratio −x. From 1.8 you know it converges only when |−x| < 1, and then its sum is 1 ÷ (1 − (−x)) = 1 ÷ (1 + x), exactly what it should be. Put x = 2 in and the right-hand side is 1 − 2 + 4 − 8 + …, which settles to nothing, while the left-hand side is ⅓. Figure 7 shows the same thing on a graph: inside −1 < x < 1 more terms bring the polynomial closer to the curve, and outside it more terms make things worse.

For the series in (1 + x)ⁿ the condition is always |x| < 1, whatever the value of n. If x is replaced by something else, the condition applies to that something.

Worked example 4. Paper 1. Expand (1 − 2x)^(1/2) in ascending powers of x up to and including the term in x³, and state the values of x for which the expansion is valid.

Here n = ½ and the "x" of the formula is −2x. Put it in brackets.

The errors to avoid are the ones from 1.9: not raising the −2 to the power, and losing a minus sign.

When the bracket does not start with 1. Take out the first term as a factor, raised to the power n. This is the step the guide writes as (a + b)ⁿ = aⁿ(1 + b/a)ⁿ.

Worked example 5. Paper 1. Find the first three terms in the expansion of (8 + x)^(1/3), and state the values of x for which it is valid.

Two slips live in the first line: the 8 must come out as 8^(1/3) = 2, not 8, and the x inside must be divided by 8. Check by multiplying back: 2(1 + x/8)^(1/3) = (8 + x)^(1/3).

A negative power works the same way. (2 + x)⁻³ = 2⁻³(1 + x/2)⁻³ = ⅛(1 + x/2)⁻³, valid for |x| < 2.

8Approximations from an expansion

Near x = 0 the first few terms of a series are an excellent approximation to the function, because each extra term is a higher power of a small number. The guide mentions approximating √2, and this is how it is done.

Worked example 6. Paper 1. Use the expansion in Worked example 4 with x = 0.01 to find an approximation to √2.

With x = 0.01, the left-hand side is √(1 − 0.02) = √0.98. Now write 0.98 in a way that contains √2.

The true value is 1.41421356…, so four terms are correct to seven decimal places. The chosen x must lie inside the interval of validity, and the smaller it is, the faster the terms shrink. You also need a way back from the left-hand side to the number you want, which is where 98 = 49 × 2 came in.

Worked example 5 gives ∛9 ≈ 2 + 1/12 − 1/288 = 2.07986 the same way (true value 2.08008). The idea returns in AHL 5.19, where Maclaurin series expand eˣ and ln(1 + x) as power series in the same way.