Permutations and Combinations formulas
At a glance
AND → × OR → + nPr = n!/(n−r)! n^r with repeats Repeats: n!/(p! q! …) Round table: (n−1)! Necklace: (n−1)!/2 nCr = n!/(r!(n−r)!) Together: glue Apart: gaps b! × (b+1)Pg Identical to r people: (n+r−1)C(r−1) At least 1 each: (n−1)C(r−1) Different items to r people: rⁿ Unnamed equal groups: divide by k! D(n): 0, 1, 2, 9, 44, 265
The counting principle: slots and trees
Task done in steps (this AND that) → multiply Task done one way OR another → add
Arrangements: with and without repetition
No repeats: nPr = n! / (n − r)! All n in a row: n! Repeats: n^r
Shortcut: If one slot has a rule (no 0 in front, must be even), fill it first. Then fill the free slots from what is left.
Identical items: divide out the repeats
n! / (p! × q! × r! …)
Circular arrangements
n people round a table: (n − 1)! Necklace or garland (n ≥ 3): (n − 1)! / 2
Shortcut: Seat one person anywhere. Now the seats are no longer alike, so the other n − 1 people fill a row: (n − 1)!.
Selections: nCr and Pascal's triangle
nCr = n! / (r! (n − r)!) nCr = nC(n − r) nCr = (n−1)C(r−1) + (n−1)Cr nC0 + nC1 + … + nCn = 2^n
Shortcut: Use the mirror to shorten work: 12C10 = 12C2 = 66. And 'choose at least one from n things' = 2ⁿ − 1.
Restrictions: together, apart and the gap method
All g together: (b + 1)! × g! No two together: b! × (b+1)P(g)
Sharing identical items: stars and bars
Each gets 0 or more: (n + r − 1)C(r − 1) Each gets 1 or more: (n − 1)C(r − 1)
Shortcut: If each must get at least k, hand out k to everyone first. Then share what is left with no rule.
Derangements: nothing in its place
D(n) = n! (1 − 1/1! + 1/2! − 1/3! + … ± 1/n!) D(1..6) = 0, 1, 2, 9, 44, 265 Exactly k right = nCk × D(n − k)
Shortcut: Learn D(2) to D(6) by heart: 1, 2, 9, 44, 265. CAT rarely goes beyond 6, and the table saves a whole minute.
Distributing items into groups
| Situation | Count | Example |
|---|---|---|
| n different items in a row | n! | ABCD: 24 |
| r of n different items in a row | nPr = n!/(n − r)! | 5P3 = 60 |
| r slots, each from n choices, repeats allowed | nʳ | 4-digit PINs: 10⁴ |
| n items, with p alike, q alike, r alike | n!/(p! q! r!) | BANANA: 6!/(3! 2!) = 60 |
| n people round a table | (n − 1)! | 5 people: 24 |
| n beads on a necklace or garland | (n − 1)!/2 | 5 beads: 12 |
| n identical items → r named groups, empty allowed | (n + r − 1)C(r − 1) | 7 sweets, 3 children: 9C2 = 36 |
| n identical items → r named groups, none empty | (n − 1)C(r − 1) | 7 sweets, 3 children: 6C2 = 15 |
| n different items → r named groups, empty allowed | rⁿ | 5 books, 3 people: 3⁵ = 243 |
| n different items → r named groups, none empty | rⁿ − rC1(r − 1)ⁿ + rC2(r − 2)ⁿ − … | 4 balls, 3 boxes: 81 − 48 + 3 = 36 |
| n different items → named groups of sizes p, q, r | n!/(p! q! r!) | 9 people into teams of 2, 3, 4: 1260 |
| n different items → k unnamed groups of m each | n!/((m!)ᵏ × k!) | 6 people into 3 pairs: 720/48 = 15 |
| nothing in its own place (derangement) | D(n) = n!(1 − 1/1! + 1/2! − … ± 1/n!) | D(4) = 9 |
Identical items into identical groups has no neat formula: list the splits by hand (7 = 5 + 1 + 1 = 4 + 2 + 1 = …).
Formulas stick when you use them
The Permutations and Combinations lesson has worked problems and quick checks for every formula here. Free to start.
Start free