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 direct counting is awkward.
WHAT YOU PROBABLY THINK
Permutations and combinations are two names for the same calculation.
Multiply the choices
If a task splits into independent stages with m and then n options, there are mn outcomes: 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: the multiplicative principle applied n times.
WORKED EXAMPLE
Counting by complement
How many positive integers below 1000 contain the digit 3 at least once?
Counting directly means splitting into cases by how many 3s appear: fiddly. Instead count the complement.
Integers from 1 to 999 number 999. Those with no 3 use 9 digits in each of three places, allowing leading zeros, giving 9³ = 729 strings, one of which is 000 and is not a positive integer: 728.
So the answer is 999 − 728 = 271. Direct enumeration confirms it, and the complement took two lines.
Order, or not
Permutations count arrangements, where order matters: nPr = n!/(n − r)!. Combinations count selections, where it does not: nCr = n!/(r!(n − r)!). The two differ by exactly the r! ways of ordering each selection, so they are never interchangeable and the opening claim 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: every selection can be lined up in that many orders. Deciding which question is being asked is the whole skill.
YOUR TURN
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, including 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: both are 120.
That symmetry is why Pascal's triangle reads the same in both directions.
THE EXAM BIT
- Ask whether order matters before writing any formula; that single decision fixes the whole answer.
- Use the complement whenever 'at least one' appears; the direct count almost always splits into cases.
- State the principle you are applying by name; the marks attach to the reasoning, not the arithmetic.
- Leave large answers in factorial or combination form unless a numerical value is demanded.
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
C
h
o
s
e
n
:
<
s
u
p
>
9
<
/
s
u
p
>
C
<
s
u
b
>
4
<
/
s
u
b
>
=
1
2
6
.
A
r
r
a
n
g
e
d
:
<
s
u
p
>
9
<
/
s
u
p
>
P
<
s
u
b
>
4
<
/
s
u
b
>
=
3
0
2
4
,
w
h
i
c
h
i
s
1
2
6
×
4
!
=
1
2
6
×
2
4
.
Multiply choices made in sequence; add alternatives; subtract from the total when 'at least one' appears.
Permutations order the selection and combinations do not: 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.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device only.
- 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 direct counting is awkward.
Open the full revision checklist to see every objective in the course in one place.
No animated video for this topic yet; these notes stand alone.