Lesson 14: Combinatorics — Counting

Counting is the foundation of probability (Lesson 15) and a discipline in itself. China has loved it for millennia: the I Ching's 64 hexagrams enumerate 2⁶ combinations, and Jia Xian's triangle (11th century) tabulated the binomial coefficients 350 years before Pascal. The Gaokao tests counting inside probability questions, where the probability is easy and the counting is the whole battle. This lesson builds the two principles (addition, multiplication), permutations and combinations, the binomial theorem, inclusion–exclusion, and the pigeonhole principle — the complete school toolkit, with the strategic judgement of when each applies.

Principles and formulas

Multiplication principle: if a task decomposes into independent stages with n₁, n₂, … options, the total is the product n₁n₂…. Addition principle: if a task splits into disjoint cases, the total is the sum. Nearly every counting problem is these two principles wearing a costume.

Permutations (order matters): A(n, k) = n!/(n − k)! arrangements of k chosen from n. Combinations (order irrelevant): C(n, k) = n!/(k!(n − k)!), satisfying C(n, k) = C(n, n − k) (choosing the committee = choosing the excluded) and Pascal's rule C(n, k) = C(n − 1, k − 1) + C(n − 1, k) (split by whether one fixed element is in or out). The binomial theorem: (a + b)ⁿ = Σ C(n, k) aⁿ⁻ᵏ bᵏ — the coefficient of each term counts the ways to choose which factors contribute b. Setting a = b = 1 gives Σ C(n, k) = 2ⁿ.

Worked examples

Worked example 1 — the multiplication principle. A canteen offers 4 starters, 5 mains and 3 desserts. Meals: 4 × 5 × 3 = 60. If instead a student takes a starter or a dessert but not both alongside a main, cases split: starter meals 4 × 5 = 20, dessert meals 5 × 3 = 15, total 35 by addition. Stages multiply; cases add.

Worked example 2 — permutations with a block. Five students line up. In how many ways can two particular students, Li and Wang, stand adjacent? Glue them into one block: 4 objects line up in 4! = 24 ways, and the block's internal order gives × 2: total 48. Non-adjacent arrangements: 5! − 48 = 120 − 48 = 72. Block for "together", complement for "apart" — the two standard moves for adjacency conditions.

Worked example 3 — combinations with a restriction. From 8 boys and 7 girls, choose a committee of 5 with at least 2 girls. Direct by cases on girls g = 2, 3, 4, 5: C(7,2)C(8,3) + C(7,3)C(8,2) + C(7,4)C(8,1) + C(7,5)C(8,0) = 21 × 56 + 35 × 28 + 35 × 8 + 21 × 1 = 1176 + 980 + 280 + 21 = 2457. Verify by complement: total C(15,5) = 3003; bad cases g = 0: C(8,5) = 56, and g = 1: C(7,1)C(8,4) = 7 × 70 = 490; 3003 − 56 − 490 = 2457 ✓. Two routes agreeing is your proof of correctness; when cases multiply, prefer the complement.

Worked example 4 — binomial coefficients. (a) The coefficient of x² in (x + 2)⁵: the general term is C(5, k) x⁵⁻ᵏ 2ᵏ; x² needs k = 3: C(5, 3) × 2³ = 10 × 8 = 80. (b) The sum of all coefficients in (x + 2)⁵: set x = 1: 3⁵ = 243. (c) In (1 + x)⁶, the coefficient of x³ is C(6, 3) = 20 — Jia Xian's triangle, row 6: 1, 6, 15, 20, 15, 6, 1.

Worked example 5 — pigeonhole. (a) Among any 13 people, two share a birth month: 13 pigeons, 12 holes. (b) A drawer holds socks of 3 colours (loose, not paired). How many socks guarantee a matching pair? Worst case: 3 socks, one of each colour; the 4th must match one — answer 4. Pigeonhole answers are worst-case arguments: exhibit the largest failing configuration, then add one.

Challenge problem — Gaokao standard

Problem. How many integers from 1 to 1000 are divisible by none of 2, 3, 5?

Solution. Count the complement with inclusion–exclusion. Divisible by 2: 500; by 3: 333; by 5: 200. Pairwise overlaps: by 6: 166; by 10: 100; by 15: 66. Triple overlap: by 30: 33. Union = (500 + 333 + 200) − (166 + 100 + 66) + 33 = 1033 − 332 + 33 = 734. Answer: 1000 − 734 = 266. The sign pattern (+ singles − pairs + triple) is the theorem: each layer corrects the previous layer's over/undercount. Floor values (⌊1000/3⌋ = 333, not 333.3) are where the arithmetic must be exact.

Common mistakes

• Order confusion. A 3-person committee from 10 is C(10, 3) = 120; a president–secretary–treasurer selection is A(10, 3) = 720. Ask: "would swapping two chosen people change the outcome?" If yes, permutations.
• Case explosion on "at least". "At least 2 girls" done directly took four cases (Worked example 3); the complement took two. Default to complement for "at least one" especially — bad case is a single term.
• Double counting symmetric objects. Arrangements around a round table: rotations coincide, so divide by n: (n − 1)!. Whenever arrangements are identified up to symmetry, count first, then divide.
• Jia Xian coefficients misread. C(6, 3) = 20 is the middle of row 6; C(n, k) = C(n, n − k) lets you always compute the smaller side.
• Pigeonhole off-by-one. The guarantee is (largest failing number) + 1: 3 unmatched socks fail, 4 succeed (Worked example 5b).

Exam Experience

Multiple choice. The value of C(10, 3) is: A. 720 B. 120 C. 30 D. 1000 Answer: B. 10!/(3!7!) = (10 × 9 × 8)/6 = 120. Option A is A(10, 3) — order does not matter here.

Fill in the blank. The coefficient of x³ in the expansion of (1 + x)⁶ is ____. Answer: 20. C(6, 3) = 20 (Jia Xian's triangle, row 6).

Solution question (10 marks). From 6 men and 4 women, a committee of 4 is chosen. (1) How many committees contain at least one woman? (2) How many contain exactly two women? Marking scheme. (1) Total committees: C(10, 4) = 210 — 2 marks. Committees with no women: C(6, 4) = 15 — 2 marks. Answer: 210 − 15 = 195 — 1 mark. [5 marks] (2) Choose the 2 women: C(4, 2) = 6 — 2 marks. Choose the 2 men: C(6, 2) = 15 — 2 marks. Multiply (independent stages): 6 × 15 = 90 — 1 mark. [5 marks] Total: 10 marks. Part (1) is the complement principle; part (2) is the multiplication principle across groups — the two ideas that run all of competition counting.

Going deeper — stars and bars, and derangements

Stars and bars counts distributions: the number of solutions of x₁ + x₂ + … + xₖ = n in nonnegative integers is C(n + k − 1, k − 1). Picture n stars in a row with k − 1 bars inserted to split them into k groups; each arrangement of the n + k − 1 symbols is one solution. Worked: x + y + z = 10 in nonnegative integers: C(12, 2) = 66. In positive integers, substitute x = x′ + 1 etc. first: x′ + y′ + z′ = 7 gives C(9, 2) = 36. Applications are everywhere once seen: distributing 10 identical prizes among 3 students (66 ways), or counting monomials of degree 10 in 3 variables (also 66 — the same count, which is why polynomial rings and combinatorics speak to each other).

Derangements count permutations with no element in its natural place (the hat-check problem). By inclusion–exclusion over the set of elements that stay fixed: D(n) = n! × (1 − 1/1! + 1/2! − 1/3! + … + (−1)ⁿ/n!). For n = 4: 24 × (1 − 1 + 1/2 − 1/6 + 1/24) = 24 × (9/24) = 9. As n grows the bracket tends to 1/e ≈ 0.368, so a random permutation is a derangement about 37% of the time — the secretary problem's constant (Lesson 15's world) appearing early. Notice which tools did the work: the Challenge problem's inclusion–exclusion and this lesson's factorials. Competition counting is a small kit used with precision.

Second look — digits, handshakes and a round table

Digit counting. How many three-digit numbers have all distinct digits? Stages: hundreds digit — 9 choices (1–9, no zero); tens digit — 9 choices (0–9 excluding the hundreds digit); units digit — 8 choices. Total: 9 × 9 × 8 = 648. The leading-digit restriction is the only subtlety; every "how many numbers" problem begins by asking whether zero is allowed in front.

Handshakes. Twelve people at a meeting each shake hands with every other exactly once: C(12, 2) = 66 handshakes — each handshake is an unordered pair of people, so combinations, not permutations. (Counting "each of 12 people shakes 11 hands" gives 132 and double-counts: divide by 2. The double-count-and-divide route and the combination route must agree — 132/2 = 66 ✓.)

Round table. Six people sit around a circular table; seatings that differ only by rotation are the same. Fix one person's seat to break the symmetry: (6 − 1)! = 120. If two particular people must sit together: glue them into a block, giving 5 objects around the circle: (5 − 1)! × 2 = 48 seatings. The same block-and-complement machinery as Worked example 2, with the circle's division by n added — tools compose, and fluency is recognising old tools in new costumes.

One last drill — the round table, with a feud. Five people sit around a circular table, but two of them refuse to sit together. Count the seatings. Total (Lesson 14's extension): (5 − 1)! = 24. Bad seatings (the two together): glue the pair into a block — 4 objects around the circle: (4 − 1)! × 2 = 12. Answer: 24 − 12 = 12. The complement principle and the block method, combined in two lines: together-count subtracted from total. Restrictions in counting problems almost always factor into these primitives — block for together, complement for apart, gap method (arrange the unrestricted, then insert) when a third pattern appears.