Counting — Product & Sum Rules, Permutations & Combinations
Why counting matters, the product rule, the sum rule, inclusion–exclusion for counting, tree diagrams, combinations ⁿCᵣ, and permutations with and without repetition.
▶Lecture videos
Click any timestamp — here or inside the notes — to jump the video to that moment. Your position is remembered.
Lesson 8 – Counting, Permutations & Combinations
Counting principles and how to choose between permutations and combinations.
00:01Lesson 8: counting, permutations and combinations02:43The product rule03:41Example: Lily's shirts and pants07:13Counting functions: nᵐ10:03Counting one-to-one functions15:43The sum rule: 37 + 83 representatives18:36Subtraction rule (inclusion–exclusion)20:28Tree diagrams: bit strings with no two consecutive 1s23:19Permutations vs combinations26:02Combinations: ⁿCᵣ and the magician example28:36Permutations: ⁿPᵣ32:13Example: picking the top three goals (720 ways)35:51Self-assessment questions1Why counting?
How many passwords of 6–8 characters (digits or letters) contain at least one digit? Questions like this need counting techniques. Counting appears all over maths and CS:
- Probability: count the successful outcomes and all possible outcomes.
- Algorithm complexity: count the operations an algorithm performs.
There are two basic principles: the product rule and the sum rule.
2The product rule ("AND", then multiply)
If a procedure breaks into a sequence of two tasks, with n₁ ways to do the first and n₂ ways to do the second (for each way of doing the first), then there are n₁ × n₂ ways to do the procedure.
Shirts: red, purple, blue (3). Pants: black, white (2). Outfits = 3 × 2 = 6.
| Shirt | Red | Blue | Purple | Red | Blue | Purple |
|---|---|---|---|---|---|---|
| Pants | Black | Black | Black | White | White | White |
Each of the m domain elements independently picks one of n codomain elements: n · n · … · n = nᵐ.
e.g. from a 3-element set to a 5-element set there are 5³ = 125 functions.
32 microcomputers × 24 ports each = 768 ports.
- If m > n: there are none (two elements would have to share an image).
- If m ≤ n:
- a₁ has n choices.
- a₂ has n − 1 (it can't reuse a₁'s value).
- …
- aₘ has n − m + 1.
Total = n(n − 1)⋯(n − m + 1). e.g. from a 3-set to a 5-set: 5 × 4 × 3 = 60.
3The sum rule ("OR", then add)
If a task can be done in one of n₁ ways OR one of n₂ ways, and no way is in both sets, then there are n₁ + n₂ ways.
The representative is either a maths faculty member (37) or a maths major (83). Nobody is both, so there are 37 + 83 = 120 choices.
Inclusion–exclusion (the subtraction principle)
If some ways are common to both sets, adding double-counts them, so subtract the overlap:
This is the same principle you met with sets in Week 2.
- Do this AND then that (a sequence of steps) → multiply.
- Do this OR that (separate, non-overlapping cases) → add.
- If the cases overlap → add, then subtract the overlap.
4Tree diagrams
A tree has a root, branches for each possible choice, and leaves (endpoints with no further branches), which are the possible outcomes. Count the leaves.
- First bit: 1 or 0.
- If a bit is 1, the next must be 0.
- If it's 0, the next can be 0 or 1.
Following the tree gives 8 strings: 1010, 1001, 1000, 0101, 0100, 0010, 0001, 0000.
When you use a tree, the number of choices on the way to each leaf can vary. That's why trees help where the plain product rule doesn't.
5Combinations — order doesn't matter
Two kinds of question:
- Arrange 3 of 5 students in a line for a photo → order matters → permutation.
- Choose a committee of 3 from 4 students → order doesn't matter → combination.
A selection of objects where the order doesn't matter and no repetition is allowed:
ⁿCᵣ = C(n, r) = n! / ( r! (n − r)! )
where n! = 1 × 2 × 3 × ⋯ × (n − 1) × n (and 0! = 1). Valid for 0 ≤ r ≤ n.
Choose 2 people from an audience of 10. Picking John and Alice is the same pair as Alice and John.
¹⁰C₂ = 10! / (2! · 8!) = (10 × 9) / (2 × 1) = 45
10!/(2!·8!): cancel the 8! so only 10 × 9 is left on top, then divide by 2!. You never need to work out 10! in full.
6Permutations — order matters
A permutation is an ordered arrangement of distinct objects. "top" and "pot" are different permutations of the same three letters.
Case 1: repetition allowed
Each of the r positions has n choices independently, so by the product rule:
e.g. 4-digit PINs: 10⁴ = 10,000.
Case 2: repetition not allowed
The choices shrink by one each time: n, then n − 1, then n − 2, …
¹⁰P₃ = 10!/(10 − 3)! = 10 × 9 × 8 = 720
Which person gets which prize matters, so this is a permutation:
¹⁰⁰P₃ = 100 × 99 × 98 = 970,200
ⁿPᵣ = ⁿCᵣ × r!. Choose the group (C), then arrange it in r! orders. e.g. ¹⁰P₂ = 45 × 2 = 90.
Decide first:
- Does order matter? → P or C.
- Is repetition allowed? → nʳ.
- Is it a sequence of steps or separate cases? → product or sum rule.
Then show the formula, the substitution and the cancellation. Typical questions: outfits and plates (product rule); a representative from disjoint groups (sum rule); bit strings (tree diagram); prize winners (P); committees (C).
7Quick revision sheet
| Concept | Remember it as |
|---|---|
| Product rule | Sequence of tasks → n₁ × n₂ (shirts × pants = 6) |
| Functions m → n | nᵐ (5³ = 125) |
| One-to-one m → n | n(n−1)⋯(n−m+1); 0 if m > n (5·4·3 = 60) |
| Sum rule | Disjoint alternatives → n₁ + n₂ (37 + 83 = 120) |
| Inclusion–exclusion | |A∪B| = |A| + |B| − |A∩B| |
| Tree diagram | Leaves = outcomes; length-4 bit strings without "11" = 8 |
| Combination | ⁿCᵣ = n!/(r!(n−r)!); order doesn't matter (¹⁰C₂ = 45) |
| Permutation | ⁿPᵣ = n!/(n−r)!; order matters (¹⁰P₃ = 720, ¹⁰⁰P₃ = 970,200) |
| With repetition | nʳ |
| Link | ⁿPᵣ = ⁿCᵣ · r! |
?Self-check quiz
12 questions on this week. Answer them all, then press Check my answers. Your best and latest scores are saved and shown on the subject page.