MAT9004 · Mathematical Foundations For Data Science And Ai
Combinatorics
Combinatorics is counting without listing — working out how many ways something can happen without writing them all out. It rests on three fundamental counting rules (product, sum and complement) and then on the four selection types, the core of the topic: are you choosing in order or not, and with repetition or not? Getting the right cell of that 2×2 decision table is the biggest exam trap, so the chapter drills one worked example per cell. From there come the binomial coefficients and Pascal's triangle, the binomial theorem, the inclusion-exclusion principle for overlapping sets, and the pigeonhole principle. The whole topic is procedural: identify the structure of the count, pick the matching rule or formula, and compute the exact integer by hand — no calculator, fractions and counts in lowest terms.
What this chapter covers
- 014.1 The three fundamental counting rules (product, sum, complement)
- 024.2 The four selection types — the core of the topic
- 034.3 One worked example for each cell of the table
- 044.4 The decision table — the biggest exam trap
- 054.5 A multi-rule worked count
- 064.6 Binomial coefficients and Pascal’s triangle
- 074.7 The binomial theorem
- 084.8 Inclusion-exclusion (2 and 3 sets)
- 094.9 The pigeonhole principle
Worked example: choosing a committee (unordered, no repetition)
- +1(a) Identify the selection type: order does not matter (a committee is a set) and no one is chosen twice — so this is a combination, C(n, r) = n! / (r!(n − r)!).
- +1(a) Compute: C(8, 3) = 8! / (3!·5!) = (8·7·6)/(3·2·1) = 336/6 = 56.
- +1(b) Fix the required person: they take one of the 3 seats, leaving 2 seats to fill from the remaining 7 people.
- +1(b) Compute: C(7, 2) = (7·6)/(2·1) = 42/2 = 21.
Key terms
- Product rule
- If a task is done in stages with m ways for the first and n for the second, there are m×n ways overall. The 'AND' rule of counting — multiply when independent choices are made in sequence.
- Permutation
- An ordered selection: P(n, r) = n!/(n − r)! ways to arrange r items chosen from n when order matters. Use it when 'first, second, third' or a sequence is implied.
- Combination
- An unordered selection: C(n, r) = n!/(r!(n − r)!) ways to choose r items from n when order does not matter, also written as the binomial coefficient (n choose r).
- Binomial theorem
- The expansion (a + b)n = Σ C(n, k) an−kbk, whose coefficients are the binomial coefficients — the rows of Pascal's triangle.
- Inclusion-exclusion
- To count a union without double-counting overlaps: |A ∪ B| = |A| + |B| − |A ∩ B|, extended to three sets by adding back the triple overlap. Used whenever 'at least one' conditions overlap.
Combinatorics FAQ
How do I pick the right counting formula?
Answer two questions in order. First: does order matter? If yes you are permuting, if no you are combining. Second: can items repeat? If yes use the with-repetition formula, if no the without-repetition one. Those two answers point to exactly one cell of the four-selection-types table — choosing the wrong cell is the single biggest source of lost marks.
When should I use the complement rule?
Use it when 'at least one' or 'not all' appears. Counting the complement (the cases you don't want) and subtracting from the total is often far easier than counting the wanted cases directly: ways = total − (ways with none of the property). It turns a messy direct count into a one-line subtraction.
What does inclusion-exclusion fix?
It stops double-counting when sets overlap. If you add |A| and |B| you have counted everything in both A and B twice, so you subtract the overlap |A ∩ B|. For three sets you add the singles, subtract the pairwise overlaps, then add back the triple overlap. The alternating add/subtract pattern is the marked structure.
Do combinatorics answers need a calculator?
No — the exam supplies no calculator, so keep the arithmetic tidy. Cancel factorials before multiplying (write C(8,3) as (8·7·6)/(3·2·1), not as 40320/720), and give the exact integer. A formula sheet lists the counting formulas, so the marks are in choosing the right one and computing it cleanly by hand.
Exam move
Burn the four selection types decision table into memory and use it as your first move on every counting question: ask 'does order matter?' then 'can items repeat?' and the answer names exactly one formula. That single discipline prevents the most-lost marks in the topic. Practise the complement rule for 'at least one' phrasing — it is usually the short route — and the inclusion-exclusion add/subtract pattern for overlapping sets. Cancel factorials before multiplying so the by-hand arithmetic stays clean, and always give an exact integer. Binomial-coefficient questions reuse C(n, r), so the same combination skill carries the binomial theorem and Pascal's triangle.
