Combinatorics
Studying this course? Keep your progress in one place.
Key facts
- Multiplicative principle: successive independent stages multiply,
- Permutations (order matters): . Combinations (order does not): .
- A set with elements has subsets, including the empty set.
- Addition principle: exclusive cases add. For "at least one", use total minus none.
- Join the principles: choose first, then arrange.
The multiplicative principle
Multiply the number of ways of each stage.
If a task is done in stages, with ways to do the first, ways to do the second (whatever the first choice), and so on, the total number of ways is This is the multiplicative principle.
A four-digit PIN where each digit is to and repeats are allowed has possibilities.
Where earlier choices reduce later ones, multiply the reduced numbers: four different digits gives .
- 1
1st digit
10 choices
- 2
2nd digit
9 choices left
- 3
3rd digit
8 choices left
- 4
4th digit
7 choices left
- 5
Multiply
A code has 3 letters chosen from A, B, C, D, E with no letter repeated. How many codes are there?
Permutations and combinations
Use permutations when order matters and combinations when it does not.
A permutation is an arrangement where order matters. Choosing and arranging items from gives .
A combination is a selection where order does not matter: .
Always .
Decide by asking: would swapping two chosen items give a different outcome? If yes, use .
| Permutation | Combination | |
|---|---|---|
| Order matters? | Yes | No |
| Formula | ||
| Four from a committee of 12 | four posts: | no roles: |
Permutation
- Order matters?:
- Yes
- Formula:
- Four from a committee of 12:
- four posts:
Combination
- Order matters?:
- No
- Formula:
- Four from a committee of 12:
- no roles:
A prize draw picks 3 winners from 10 people. Each wins the same prize. How many outcomes?
Subsets of a set
A set with elements has subsets, because each element is either in or out.
A set with elements has subsets, including the empty set and the set itself.
The number of subsets with exactly elements is . Excluding the empty set leaves .
A group chosen from athletes has possibilities if it must be non-empty.
Forgetting that includes the empty set is a common slip, as it is often not allowed.
- All subsets of elements
- Non-empty subsets
How many subsets does {a, b, c, d} have that contain at least one element?
Addition and subtraction principles
Add the counts of exclusive cases; for "at least one", subtract the opposite case from the total.
If a task can be done in one of several ways that cannot happen together, add the numbers (the addition principle).
For "at least" questions it is often easier to subtract the opposite case from the total.
PINs with at least one : .
Teams of from goalkeepers and outfield players with at least one goalkeeper: .
- At least onetotal none
Worked example
How many positive integers less than 1000 contain the digit 3 at least once?
- 1
Write each integer as a string to . There are strings.
- 2
Strings with no : each of the three places has choices, so .
- 3
This count includes , which is not positive, so positive integers have no .
- 4
There are positive integers less than .
How many 3-digit strings (000 to 999) contain at least one 5?
Combined counting problems
Choose first, then arrange; for "at least ", split into cases and add.
Many problems join the principles: choose first, then arrange.
For "at least " of a type, make a case split (exactly , exactly , and so on) and add.
At least girls in a training group chosen from girls and boys, where any number of boys may join: choose or girls and any subset of the boys, so .
Split into non-overlapping cases; counting the same selection twice is a common mistake.
- 1
Choose
use combinations for each group
- 2
Multiply
the choices for each group
- 3
Arrange
multiply by the orders if order matters
Worked example
A relay team of 4 is chosen from 4 girls and 6 boys with exactly 2 girls. How many teams can be made, with the order of running counted?
- 1
Choose the girls: .
- 2
Choose the boys: .
- 3
Number of groups: .
- 4
Arrange each group in orders.
Choose 3 people from 5 men and 4 women with exactly 1 woman. How many ways?
Try an exam question
A committee of 4 is chosen from 5 men and 6 women. Find the number of committees that contain at least one man.
[4 marks]
- [1]Total committees .
- [1]Committees with no men (all women): .
- [1]Uses total minus none.
- [1].
That's the notes covered.
Carry on to the next subtopic.
Try a question
In how many ways can a committee of 4 members, with no special roles, be chosen?
1 mark, marked against the mark scheme
In how many ways can a committee of 4 members, with no special roles, be chosen?
1 mark, marked against the mark scheme