Fundamental principle of counting
Multiplication principle: if one event can happen in m ways, and after that a second event can happen in n ways, then both can happen one after the other in m × n ways. It extends to three or more events.
Example: a lock has 3 rings, each with digits 0–9. Codes = 10 × 10 × 10 = 1000.
Addition principle: if a job can be done in m ways or in n other ways (not both), it can be done in m + n ways. ‘And’ means multiply, ‘or’ means add.
Factorial notation
n! (read ‘n factorial’) = 1 × 2 × 3 × … × n for a natural number n. So 3! = 6, 4! = 24, 5! = 120, 6! = 720.
- We define 0! = 1. This keeps formulas like ⁿPₙ = n!/0! correct.
- n! = n × (n − 1)!, so 7!/5! = 7 × 6 = 42. Cancel instead of multiplying everything.
Permutations: the nPr formula
A permutation is an arrangement in a definite order. Arranging r objects from n different objects (no repeats): the first place has n choices, the second n − 1, …, the r-th has n − r + 1. So
ⁿPᵣ = n(n − 1)(n − 2)…(n − r + 1) = n!/(n − r)!, 0 ≤ r ≤ n.
- ⁿPₙ = n! (arrange all). ⁿP₀ = 1.
- If repetition is allowed, the number of arrangements is nʳ.
- If among n objects, p are alike of one kind, q alike of another, and so on, the arrangements of all n are n!/(p! q! …). Example: MISSISSIPPI has 11 letters with I×4, S×4, P×2, so 11!/(4!·4!·2!) = 34650.
Combinations: the nCr formula and its link to nPr
A combination is a selection where order does not matter. Every selection of r objects can be arranged in r! ways, and doing this for every selection gives all ⁿPᵣ arrangements. So
ⁿPᵣ = ⁿCᵣ × r!, which gives ⁿCᵣ = n!/(r!(n − r)!).
- ⁿC₀ = ⁿCₙ = 1.
- ⁿCᵣ = ⁿCₙ₋ᵣ: choosing r to take = choosing n − r to leave (step 5 of the 3D). So if ⁿCₐ = ⁿC_b, then a = b or a + b = n.
- ⁿCᵣ + ⁿCᵣ₋₁ = ⁿ⁺¹Cᵣ (Pascal’s rule, used again in the Binomial Theorem).
Simple uses: which one do I use?
Ask: does order change the outcome? Seating, ranking, forming numbers or words, passwords → permutation. Teams, committees, handshakes, choosing questions, groups of fruits → combination.
- Handshakes among 10 people: ¹⁰C₂ = 45.
- Diagonals of an n-sided polygon: ⁿC₂ − n.
- Words from the letters of a word with conditions (vowels together: treat them as one block, then multiply by their own arrangements).
- At least / at most questions: add the separate cases.
Board exam focus
Expect: find n from an equation like ⁿP₄ = 12 · ⁿP₂ (2–3 marks), arranging letters with repetition or conditions (3–4 marks), committees with ‘at least’ (3–4 marks), and ⁿCᵣ = ⁿCₙ₋ᵣ style questions (1–2 marks). Show the counting reason in words before the numbers.
Key formulas and definitions
- Counting principle: m ways then n ways → m × n ways
- n! = 1 × 2 × … × n, 0! = 1, n! = n(n − 1)!
- ⁿPᵣ = n!/(n − r)!; with repetition nʳ
- Alike objects: n!/(p! q! r! …)
- ⁿCᵣ = n!/(r!(n − r)!), ⁿPᵣ = ⁿCᵣ · r!
- ⁿCᵣ = ⁿCₙ₋ᵣ; ⁿCᵣ + ⁿCᵣ₋₁ = ⁿ⁺¹Cᵣ
Worked examples
1. How many 3-digit numbers can be formed from the digits 1, 2, 3, 4, 5 if (i) digits may repeat (ii) digits may not repeat?
(i) Each place has 5 choices: 5 × 5 × 5 = 125. (ii) 5 choices, then 4, then 3: 5 × 4 × 3 = 60 = ⁵P₃.
2. Find 8!/(6! × 2!).
8! = 8 × 7 × 6!, so 8!/6! = 56. Divide by 2! = 2: 56/2 = 28 (this is ⁸C₂).
3. In how many ways can 6 people sit in a row of 6 chairs? In how many of these do two friends A and B sit together?
All: 6! = 720. Together: glue A and B into one block, giving 5 units, arranged in 5! = 120 ways. Inside the block A and B can swap: 2! = 2. Total 120 × 2 = 240.
4. How many different words (with or without meaning) can be made from all the letters of BANANA?
6 letters: B×1, A×3, N×2. Words = 6!/(3! · 2!) = 720/12 = 60.
5. Find n if ⁿP₅ = 42 · ⁿP₃ (n > 4).
n(n−1)(n−2)(n−3)(n−4) = 42 · n(n−1)(n−2). Cancel: (n − 3)(n − 4) = 42 = 7 × 6. So n − 3 = 7, n = 10.
6. A committee of 3 men and 2 women is to be chosen from 6 men and 5 women. In how many ways?
Men: ⁶C₃ = 20. Women: ⁵C₂ = 10. Both are needed (‘and’), so multiply: 20 × 10 = 200.
7. If ⁿC₉ = ⁿC₈, find ⁿC₁₇.
ⁿCₐ = ⁿC_b with a ≠ b means a + b = n, so n = 17. Then ¹⁷C₁₇ = 1.
8. From 4 red and 5 blue balls, how many ways to choose 3 balls with at least 2 red?
Case 2 red + 1 blue: ⁴C₂ × ⁵C₁ = 6 × 5 = 30. Case 3 red: ⁴C₃ = 4. Cases are separate (‘or’), so add: 30 + 4 = 34.
Common mistakes
- Using nPr for teams or committees. If swapping two chosen people gives the same group, use nCr.
- Adding when you should multiply. ‘This and then that’ multiplies; ‘this or that’ adds.
- Forgetting to divide by the factorials of repeated letters in words like APPLE or BANANA.
- Thinking 0! = 0. By definition 0! = 1.