Lesson 16: Combinatorics: Permutations and Combinations

Combinatorics is the art of counting without listing. Its two engines are the permutation (arrangements, where order matters) and the combination (selections, where order does not), both built from factorials and the multiplication principle. This lesson sharpens the order-matters judgement, computes both formulas fluently, counts with restrictions, and finishes with the binomial theorem — where combinations reappear as the coefficients of (a + b)^n.

The multiplication principle and factorials

If a task is done in stages with n_1, n_2, … independent choices, the total count is the product n_1 · n_2 · …. The number of ways to arrange n distinct objects is n! = n · (n − 1) · … · 1 (with 0! = 1 by definition). A number plate with 3 letters followed by 3 digits, repetition allowed, has 26^3 · 10^3 = 17,576 · 1,000 = 17,576,000 possibilities — multiplication principle, three letter-stages and three digit-stages.

Permutations: order matters

The number of ways to arrange r objects chosen from n distinct objects is nPr = n!/(n − r)!.

Worked Example 1. A club with 8 members elects a president, a vice-president and a secretary. The offices differ, so order matters: 8P3 = 8 · 7 · 6 = 336 outcomes. The falling-factorial view (8 · 7 · 6) is the formula n!/(n−r)! with the tail cancelled — 8!/5! — and it is how you should compute: never expand a full factorial to cancel it.

Combinations: order does not matter

The number of ways to choose r objects from n, order irrelevant, is nCr = n!/(r!(n − r)!). Every unordered group of r was counted r! times in the permutation count (once per ordering), and dividing by r! removes exactly that overcount — the formula is the correction, not a new idea.

Worked Example 2. The same club chooses a 3-person committee (no offices): 10 members this time, so 10C3 = (10 · 9 · 8)/(3 · 2 · 1) = 720/6 = 120. Contrast with Worked Example 1: offices → permutations; committees → combinations. Choosing 3 from 8 as a committee would be 8C3 = 56, not 336 — the factor of 6 = 3! between them is the six orderings of each trio.

Worked Example 3 — restrictions by multiplication. A panel needs 3 of 5 teachers and 2 of 4 students: C(5,3) · C(4,2) = 10 · 6 = 60 panels. Independent sub-choices multiply, exactly as the multiplication principle demands. For "at least one" restrictions, count the complement instead: committees of 4 from 10 with at least one teacher (6 teachers, 4 students) = total − none = C(10,4) − C(4,4) = 210 − 1 = 209. (Check C(10,4) = 210: (10·9·8·7)/24 = 5040/24 = 210 ✓.)

The binomial theorem

The expansion of (a + b)^n has n + 1 terms; the coefficient of a^(n−k) b^k is C(n, k) — Pascal's triangle is a table of combinations.

Worked Example 4. Expand (x + 2)^4. Coefficients C(4, k) = 1, 4, 6, 4, 1 applied to x^(4−k) · 2^k:

(x + 2)^4 = x^4 + 4·x^3·2 + 6·x^2·4 + 4·x·8 + 16
          = x^4 + 8x^3 + 24x^2 + 32x + 16

Check at x = 1: (1 + 2)^4 = 81, and 1 + 8 + 24 + 32 + 16 = 81 ✓. A single middle term is often all a problem wants: the x^2 term of (x + 2)^6 is C(6, 4) · x^2 · 2^4 = 15 · 16 = 240, so the term is 240x^2 (note C(6,4) = C(6,2) = 15 — symmetry halves the work).

Modelling: lottery odds and poker probabilities

A 6/49 lottery asks for 6 numbers from 49: C(49, 6) = 13,983,816 combinations, so one ticket wins the jackpot with probability 1/13,983,816 ≈ 0.0000000715. Buying 100 tickets still leaves the probability near 1 in 140,000 — combinatorics as financial literacy. In five-card poker, the probability of a full house (three of one rank, two of another) is

[C(13,1)·C(4,3) · C(12,1)·C(4,2)] / C(52,5) = (13·4 · 12·6)/2,598,960 = 3,744/2,598,960 ≈ 0.144%

Each factor tells its story: choose the rank for the triple (13), choose its 3 suits (C(4,3) = 4), choose the pair's rank from the remaining 12, choose its 2 suits (C(4,2) = 6). Probability is counting twice — favourable over total — and every probability in Lesson 15's world rests on counts built exactly like this. Security offers a last application: a 4-digit PIN with repetition allowed has 10^4 = 10,000 options; forbidding repetition leaves 10 · 9 · 8 · 7 = 5,040 — repetition rules are permutation/combination decisions with real consequences.

Common mistakes

• Permuting a committee. Choosing a team, a hand of cards, or a sample is a combination. The 336-vs-56 gap in the worked examples is the most expensive confusion in the topic.
• Dividing by r! twice. nCr already contains the correction. nPr/r! is nCr — computing n!/(r!(n − r)!) again after using nPr double-corrects.
• "At least one" counted directly. Cases (exactly 1, exactly 2, …) invite omissions; total minus none is one subtraction.
• Binomial term misalignment. In (x + 2)^6, the x^2 term pairs x^2 with 2^4 (the exponents must sum to 6), and its coefficient is C(6, 4), chosen by the second term's exponent as well — both are 4 here; keep the pairing (n − k, k) straight.
• Expanding full factorials. 12!/9! is 12 · 11 · 10 = 1,320 by cancellation. Writing out 479,001,600 invites arithmetic errors for zero benefit.

Exam Experience

1. 7P2 equals

• (A) 42
• (B) 21
• (C) 49
• (D) 14

Answer: (A). 7P2 = 7 · 6 = 42. (B) is 7C2 — the permutation/combination distinction in its purest form.

2. C(9, 4) equals

• (A) 36
• (B) 126
• (C) 3,024
• (D) 84

Answer: (B). (9 · 8 · 7 · 6)/(4 · 3 · 2 · 1) = 3,024/24 = 126. (C) is the numerator alone — forgetting to divide by 4!.

3. Two cards are drawn from a standard 52-card deck without replacement. The probability both are aces is

• (A) 4/52 · 4/52
• (B) 1/221
• (C) 8/52
• (D) 1/169

Answer: (B). C(4, 2)/C(52, 2) = 6/1,326 = 1/221. (A) wrongly assumes replacement (and independence); (D) is (1/13)^2, the with-replacement answer.

Constructed response. A school council is formed from 6 teachers and 8 students. (a) How many councils of 5 people can be formed in total? (b) How many councils contain exactly 2 teachers? (c) A council of 5 is chosen at random. Find the probability it contains exactly 2 teachers, as a fraction in lowest terms and as a decimal. (d) Explain why the count in (b) uses a product of two combinations rather than a single combination.

Scoring guide. (a) 1 point: C(14, 5) = 2,002. (b) 2 points: 1 for choosing the teachers C(6, 2) = 15 and the students C(8, 3) = 56; 1 for the product 15 · 56 = 840. (c) 1 point: 840/2,002 = 60/143 ≈ 0.420. (d) 1 point: the selection splits into two independent sub-choices (which teachers, which students); each sub-choice is unordered (a combination), and the multiplication principle combines independent stages — a single C(11, 5)-style count cannot express the "exactly 2 from this group" restriction.

Going deeper: identical objects, circles and "at least one"

Arrangements with repeated items. The letters of BANANA can be arranged in 6!/(3! · 2!) = 720/12 = 60 distinct ways: start with 6! arrangements of six distinct letters, then divide by 3! for the three identical A's and by 2! for the two N's, whose internal shuffles change nothing. The division-by-overcount logic is the same one that built nCr — combinations were just the first application.

Circular arrangements. Five people around a round table: rotations of the whole seating are the same arrangement, so fix one person's seat and arrange the rest: (5 − 1)! = 24. The general rule is (n − 1)! for n people in a circle — division by n, the number of rotations, another controlled overcount correction.

"At least one" by complement. The probability of at least one six in four rolls of a die: counting directly means cases (exactly one, two, three, four sixes) — instead compute 1 − P(no sixes) = 1 − (5/6)^4 = 1 − 625/1,296 = 671/1,296 ≈ 51.8%. Better than even odds — a result that surprises most people and launched a famous 17th-century correspondence between Pascal and Fermat about dice. The complement principle (count the opposite and subtract) applies to combinations as it did in Worked Example 3, and to probability as here: whenever "at least one" appears, reach for "none" first.

The birthday problem: combinations meet astonishment

In a class of 23 students, what is the probability that at least two share a birthday? Count the complement — all birthdays different: the first student has any of 365 days, the second 364, …, the 23rd has 343, out of 365^23 equally likely assignments: P(no match) = (365 · 364 · … · 343)/365^23 ≈ 0.493. So P(a match) ≈ 50.7% — better than even odds with only 23 people, against most intuition (which fixates on matching *your* birthday: that needs 253 people for the same odds, because it is C(23, 2) = 253 pairs that can match, not 23 birthdays). The count of pairs — a combination — is the hidden engine. Combinatorics repeatedly punishes linear intuition about quadratic counts; this is its most famous ambush.