Permutations & Combinations
1. Selections vs Arrangements
Used everywhere: transport logistics, proteins in genetic engineering, sorting algorithms, and cryptography (passwords, e-commerce).
Permutation = selecting and arranging in a particular order — order does matter.
Permutations: AB, BA, AC, CA, BC, CB → 6 ways
Key words: arranged ⇒ permutation. chosen, selected ⇒ combination. e.g. choosing strawberries + ice-cream = choosing ice-cream + strawberries → same combination.
2. The Factorial Function
Say "n factorial". On the calculator it is the n! or x! button.
6!4! = 6×5×4×3×2×14×3×2×1 = 6 × 5 = 30
5! − 4! = 4!(5 − 1) = 4! × 4 = 96 (take out the common factor 4!)
3!0! = 3×2×11 = 6
Why is 0! = 1? Go down the list: each term = previous ÷ next number. 1! ÷ 1 = 1, so 0! must be 1.
3. Permutations of n Distinct Objects
A permutation = objects arranged in a line. All methods use factorials.
Digits 5, 6, 7: list → 567, 576, 657, 675, 756, 765 → 6 numbers. Lists and tree diagrams are fine for small n only (7 letters ⇒ 5040 branches!). Use the choices method:
In how many ways can five boys be arranged in a row?
Could also work right → left: 1×2×3×4×5 = 5! — same answer.
Nine elephants and four mice in a line — how many ways?
All 13 animals are distinct ⇒ arrange 13 different things.
Big answers: give to 3 s.f. → 6.23 × 10⁹.
4. Permutations with Repeated Objects
If some objects are identical, there are fewer than n! arrangements — swapping two identical objects gives the same arrangement.
Steps: ① count total letters n ② list the repeated letters and how many of each ③ n! ÷ (product of those factorials).
Capital of Burkina Faso: OUAGADOUGOU. Distinct arrangements of all its letters?
11 letters: O×3, U×3, A×2, G×2 (D only once ⇒ ignore).
5. Permutations with Restrictions
- Fixed place (e.g. oldest at the left end) → 1 choice there, arrange the rest.
- Must stay together → glue them into one object; arrange the objects; × arrangements inside the glue.
- Must be separated → total − (together) or place the others first, put the separated ones in the gaps.
- Even / odd, > some number → do the units digit (or first digit) first; split into cases if the choices overlap.
- "At least / more than" → list every case, add (cases are mutually exclusive).
No restriction: 6! = 720. With restrictions fewer than 720. Find the number of ways if…
a) oldest man at far left → 1 choice, other 5 in 5P5:
b) two youngest at the far right → they fill the 2 end places in 2P2, other 4 men in 4P4:
c) shortest man at neither end → only 5 men can go far left, then only 4 can go far right; remaining 4 places filled in 4P4:
How many odd four-digit numbers greater than 3000 from digits 1, 2, 3, 4, each used once?
First digit must be 3 or 4; last digit must be 1 or 3. The digit 3 can fit either place ⇒ split into two cases.
Two mangoes (M) and three watermelons (W) in a line, all five distinguishable. Find the ways if the mangoes…
a) must not be separated: mangoes side by side in 2P2 ways; glued pair + 3 W = 4 objects in 4P4 ways.
b) must be separated: total 5! = 120, and in 48 the mangoes are together.
(a) women separated: together = 2! × 4! = 48 ⇒ 120 − 48 = 72 ✓ correct.
(b) men separated: 120 − 3!×3! = 84 is flawed ✗. 3!×3! counts only "all three men side by side", but "not separated" also includes two together and one apart. Truly separated (no two men adjacent) is only the pattern M W M W M ⇒ 3! × 2! = 12. Lesson: "3 objects all separated" ≠ "not all together".
6. Permutations of r Objects from n
Now select some objects and arrange them. Choose and arrange 3 of A, B, C, D, E: choices 5 × 4 × 3 = 60 — that is 5! but the last 2! is missing ⇒ 5!(5−3)! = 5!2! = 60.
Check: nPn = n!/0! = n! ✓.
Three-digit numbers from 3, 4, 5, 6, 7, 8, 9, each used at most once?
Five cards from a standard 52 arranged in a row?
4 of 18 girls on a four-seat sofa; the oldest girl must have a seat.
4 seats for the oldest; then select & arrange 3 of the other 17.
4 boys and 3 girls in a row, no two girls adjacent.
Arrange the 4 boys (⁴P₄); they make 5 gaps; the 3 girls pick 3 of the 5 gaps and are ordered there (⁵P₃).
Objects that must be separated go individually between / beside the objects that can be together.
7. Combinations
A combination = a selection where order does not matter. Choosing r from n. Each selection can be arranged in r! ways, so
Three facts to remember:
- nCr = nCn−r
- nCr ≤ nPr (fewer selections than arrangements)
- bottom numbers add to the top: r + (n−r) = n
- AND (both selections happen) ⇒ × · OR (separate cases) ⇒ +
3 fish from a bowl with 7 fish and 2 potatoes?
The potatoes are irrelevant — select 3 from the 7 fish.
5 books and 3 magazines from 8 books and 6 magazines?
Select 5 of 8 books AND 3 of 6 magazines — independent ⇒ multiply.
Team of 5 from 6 women and 5 men — how many teams have more women than men?
| 6 women | 5 men | no. teams | |
|---|---|---|---|
| 3 | 2 | ⁶C₃ × ⁵C₂ = 20 × 10 = 200 | |
| or | 4 | 1 | ⁶C₄ × ⁵C₁ = 15 × 5 = 75 |
| or | 5 | 0 | ⁶C₅ × ⁵C₀ = 6 × 1 = 6 |
Distinct three-digit numbers from five cards: 5, 5, 7, 8, 9.
The repeated 5 forces three separate (mutually exclusive) cases — then add.
| how many 5s | working | numbers |
|---|---|---|
| none | digits 7,8,9 arranged: ³P₃ | 6 |
| one 5 | 2 of {7,8,9} chosen, arranged with a 5: ³C₂ × 3! | 3 × 6 = 18 |
| two 5s | 1 of {7,8,9} chosen, arranged with 5,5: ³C₁ × 3!/2! | 3 × 3 = 9 |
8. Probability with ⁿPᵣ and ⁿCᵣ
If all outcomes are equally likely (equiprobable):
15 identical unlabelled tins: 8 soup (S), 4 beans, 3 peas. Choose 7 at random; find P(exactly 5 soup).
Favourable: 5 from the 8 soup and 2 from the 7 "not soup" (S′ — beans or peas, doesn't matter).
Numerator check: 8 + 7 = 15 ✓ and 5 + 2 = 7 ✓.
Bag: 13 red (R), 7 black (B). Take 5 at random. P(more red than black)?
| red | black | no. ways |
|---|---|---|
| 5 | 0 | ¹³C₅ × ⁷C₀ = 1287 |
| 4 | 1 | ¹³C₄ × ⁷C₁ = 715 × 7 = 5005 |
| 3 | 2 | ¹³C₃ × ⁷C₂ = 286 × 21 = 6006 |
| Total | 12 298 | |
Explore 5.4: conditional probabilities give the same answer (e.g. P(5R) = 13/20 × 12/19 × 11/18 × 10/17 × 9/16 = 1287/15504) but need far more working — combinations are quicker.
Minibus: driver + 7 passenger seats; 7 passengers seated at random. P(A and B sit on (a) the same side, (b) opposite sides)?
9. Past-Paper Style Questions — Solved
11 letters: R×2, E×3, M×2, B, A, N, C. Vowels: E, E, A, E.
i) no restrictions ii) start and finish with M
iii) arrangements not having all 4 vowels together ⇒ total − together.
iv) choose 4 letters, no M, no R, at least 2 E's. Available: E,E,E and 4 different letters B,A,N,C. (selection ⇒ combinations)
a i) 3-digit numbers (100–999), all digits different:
ii) of these, odd and > 700. First digit 7, 8 or 9; last digit odd; middle: 8 choices each time.
b) 7 flowers from 6 roses, 5 tulips, 4 daffodils, at least 2 of each ⇒ (R,T,D) = (3,2,2), (2,3,2) or (2,2,3).
3 identical cola (C), 2 green tea (G), 2 orange juice (O) in a row. (Total = 7!/(3!2!2!) = 210.)
i) first and last cans the same type → three cases:
ii) 3 colas together and 2 green teas apart:
10. Full Chapter Cheat-Sheet
- n! = n(n−1)(n−2)…×2×1 · 0! = 1
- All n arranged: nPn = n!
- r arranged from n: nPr = n!(n−r)!
- With identical objects (p, q, r … of each kind): n!p! q! r! …
- r chosen from n (order irrelevant): nCr = n!r!(n−r)! with nCr = nCn−r, nCr ≤ nPr, nCr × r! = nPr
- Probability = favourablepossible (both counted by perms or both by combs)
- Arranged → permutation · chosen / selected → combination.
- Independent choices: AND → × Separate cases: OR → +.
- Restricted places first; split into cases when choices overlap (e.g. odd numbers > 3000).
- Together → glue as one object, × inside arrangements. Not together → total − together, or gaps method (ⁿ⁺¹Pₖ for k separated objects among n others).
- Repeated digit / letter in selections ⇒ cases by how many of it are used.
- Large answers: 3 s.f. · probability answers: fraction or 3 s.f. decimal.
- Complement: P(not A) = 1 − P(A); "at least one" = total − none.