Maths › Further Pure 2 › Combinatorics
Combinatorics
Count without listing. Multiply choices when they happen in sequence, and decide whether order matters before reaching for a formula.
Builds on Probability and Venn diagrams and The binomial expansion.
IN THIS TOPIC
- Apply the multiplicative principle, and the addition and subtraction principles.
- Choose between permutations and combinations by asking whether order matters.
- Count subsets, and count by complement when the direct count is awkward.
COMMON MISCONCEPTION
Permutations and combinations are two names for the same calculation.
Multiply the choices
If a task splits into independent stages with m options and then n options, there are mn outcomes. That is the multiplicative principle. The addition principle covers alternatives that cannot happen together, and the subtraction principle counts a complement when the direct count is harder than the total minus the rest.
A set of n elements has 2n subsets, since each element is independently in or out. That is the multiplicative principle applied n times over.
WORKED EXAMPLE
Counting by complement
How many three-digit numbers contain the digit 3 at least once?
Counting directly means splitting into cases by how many 3s appear, which is fiddly. Count the complement instead.
There are 900 three-digit numbers from 100 to 999. Those with no 3 have 8 choices for the leading digit and 9 for each of the others, giving 8 × 9 × 9 = 648.
So the answer is 900 − 648 = 252. The same trick over 1 to 999 gives 999 − 728 = 271, and both took two lines.
Order, or not
Permutations count arrangements, where order matters, and nPr = n!/(n − r)!. Combinations count selections, where it does not, and nCr = n!/(r!(n − r)!). The two differ by the r! ways of ordering each selection, so they are never interchangeable: confuse them and the count is out by that factor.
WORKED EXAMPLE
One squad, two questions
From a squad of 21, how many ways are there to pick a team of 11 if positions do not matter, and if they do?
Positions ignored: 21C11 = 352716.
Positions mattering: 21P11 = 352716 × 11! ≈ 1.41 × 10¹³.
The ratio is 11! = 39916800, since every selection can be lined up in that many orders. Deciding which question is being asked is the whole skill.
GUIDED PRACTICE
Subsets and a symmetry
A set has 8 elements. How many subsets does it have? Also explain why 10C3 equals 10C7.
Show the working
Each element is in or out independently, so there are 2⁸ = 256 subsets, counting the empty set and the whole set.
Choosing 3 to include is the same as choosing 7 to leave out, so the two counts must agree, and both are 120.
That symmetry is why Pascal's triangle reads the same in both directions.
ASSESSMENT FOCUS
- Ask whether order matters before writing any formula; that one decision fixes the whole answer.
- Reach for the complement whenever 'at least one' appears, because the direct count almost always splits into cases.
CHECK YOURSELF
In how many ways can 4 books be chosen from 9, and in how many ways can 4 be arranged in a row from 9?
Show a hint
One question ignores order and one does not.
Show the answer
Chosen: 9C4 = 126. Arranged: 9P4 = 3024, which is 126 × 4! = 126 × 24.
Multiply choices made in sequence, add alternatives, and subtract from the total when 'at least one' appears.
Permutations order the selection and combinations do not, so they differ by exactly r factorial.
WORKBOOK
Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.
Or read them with their worked answers on the combinatorics questions page.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.
- Apply the multiplicative principle, and the addition and subtraction principles.
- Choose between permutations and combinations by asking whether order matters.
- Count subsets, and count by complement when the direct count is awkward.
Open the full revision checklist to see every objective in the course in one place.