Combinatorics — Permutations and Combinations
The mathematics of counting — how many ways to arrange or select things, and the formulas that make it systematic.
Why Counting Is Hard
Counting seems trivial until the numbers get large or the constraints get specific. How many ways can 8 people sit at a round table? How many 5-card poker hands contain exactly one pair? Combinatorics is the systematic answer — methods that work without listing everything out.
The Fundamental Counting Principle
If one event can happen in m ways and a second (independent) event in n ways, both together can happen in m × n ways.
3 shirts × 4 trousers = 12 outfits
6 choices for starter × 5 for main × 3 for dessert = 90 meals
This extends to any number of stages — multiply the choices at each stage.
Factorials
The factorial of n (written n!) is the product of all positive integers up to n:
n! = n × (n−1) × (n−2) × ... × 2 × 1
5! = 5 × 4 × 3 × 2 × 1 = 120
4! = 24
3! = 6
2! = 2
1! = 1
0! = 1 (by convention — the empty product)
Factorials grow extremely fast. 10! = 3,628,800. 20! ≈ 2.4 × 10¹⁸.
Permutations — Order Matters
A permutation is an arrangement where order matters. ABC and BAC are different permutations.
All n items in a row:
n! ways
5 people in a line: 5! = 120 ways.
Choosing r items from n (order matters):
P(n, r) = n! / (n − r)!
Choose 3 from 8, order matters:
P(8, 3) = 8!/5! = 8 × 7 × 6 = 336
Intuition: n choices for first position, n−1 for second, n−2 for third… multiply r terms.
Permutations with repetition
If items can repeat (like digits in a code), each position has n choices:
4-digit PIN from digits 0−9: 10⁴ = 10,000
Permutations with identical items
If some items are identical, divide by the factorial of each repeated group:
Arrangements of MISSISSIPPI (11 letters: 1 M, 4 I, 4 S, 2 P):
11! / (1! × 4! × 4! × 2!) = 34,650
Combinations — Order Doesn’t Matter
A combination is a selection where order doesn’t matter. ABC and BAC are the same combination.
C(n, r) = n! / (r! × (n − r)!)
Also written as ⁿCᵣ or (n choose r) or $\binom{n}{r}$.
Choose 3 from 8, order doesn't matter:
C(8, 3) = 8! / (3! × 5!) = 336 / 6 = 56
The relationship: C(n,r) = P(n,r) / r! — divide permutations by r! because each combination of r items can be arranged r! ways, all of which count as one combination.
Key combination identities
C(n, 0) = 1 (one way to choose nothing)
C(n, 1) = n (n ways to choose one)
C(n, n) = 1 (one way to choose all)
C(n, r) = C(n, n−r) (choosing r is same as leaving out n−r)
Pascal’s Triangle
Each entry is the sum of the two above it. Row n gives the values C(n, 0), C(n, 1), …, C(n, n):
Row 0: 1
Row 1: 1 1
Row 2: 1 2 1
Row 3: 1 3 3 1
Row 4: 1 4 6 4 1
Row 5: 1 5 10 10 5 1
Binomial theorem: the coefficients of (a + b)ⁿ expanded are the nth row of Pascal’s triangle:
(a + b)³ = 1a³ + 3a²b + 3ab² + 1b³
(a + b)⁴ = a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴
The Inclusion-Exclusion Principle
To count |A ∪ B| (elements in A or B or both):
|A ∪ B| = |A| + |B| − |A ∩ B|
Adding |A| and |B| double-counts the overlap, so subtract it once.
For three sets:
|A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|
Example: In a group of 100 students, 60 study maths, 45 study physics, 30 study both. How many study at least one?
60 + 45 − 30 = 75
Common Combinatorics Problems
Poker hands (5 from 52 cards):
Total hands: C(52, 5) = 2,598,960
Four of a kind: C(13,1) × C(4,4) × C(48,1) = 624
Full house: C(13,1) × C(4,3) × C(12,1) × C(4,2) = 3,744
Passwords: 8-character password, uppercase + lowercase + digits (62 chars), no repetition:
P(62, 8) = 62!/54! = 62 × 61 × 60 × ... × 55 ≈ 1.36 × 10¹⁴
Committee selection: 5 people from a group of 4 men and 6 women, at least 2 women:
= C(6,2)×C(4,3) + C(6,3)×C(4,2) + C(6,4)×C(4,1) + C(6,5)×C(4,0)
= 60 + 120 + 60 + 6 = 246
Combinatorics in Probability
Most probability calculations reduce to counting. The probability of event A:
P(A) = (number of favourable outcomes) / (total outcomes)
This only works when all outcomes are equally likely — which is exactly when combinatorics applies. Rolling a fair die, dealing from a shuffled deck, choosing items at random.
Combinatorics is the counting engine; probability is the interpretation.