Combinatorics & Probability¶
Counting sounds like the easiest thing in mathematics, and that's exactly the trap. The formulas here are short; the difficulty is that it's dangerously easy to count the same thing twice, or to count something you didn't mean to. The professional habit that prevents this is simple: before writing a single number, say out loud what one of the things you're counting actually is. "I'm counting strings of 5 digits where…" — get that sentence right and the formula usually picks itself.
Choosing the right model¶
Almost every counting problem is one of four standard shapes. To find which, ask two questions about the thing you're building:
- Does the order of the choices matter? (Is \(ab\) different from \(ba\)?)
- May a choice repeat? (Can you pick the same element twice?)
| Order matters? | Repetition allowed? | Count | Name |
|---|---|---|---|
| Yes | Yes | \(n^k\) | Sequences / words |
| Yes | No | \(\dfrac{n!}{(n-k)!}\) | Permutations of \(k\) from \(n\) |
| No | No | \(\dbinom{n}{k}\) | Combinations / subsets |
| No | Yes | \(\dbinom{n+k-1}{k}\) | Multisets (stars and bars) |
Get in the habit of answering the two questions first, then reading off the row. Most wrong answers come from grabbing a formula before pinning down these two facts.
Binomial coefficients¶
This counts the number of ways to choose an unordered set of \(k\) things from \(n\).
Where the formula comes from. First line up \(k\) choices in order: \(n\) ways for the first, \(n-1\) for the second, down to \(n-k+1\) — that's \(\frac{n!}{(n-k)!}\). But we didn't want order, and each unordered set of \(k\) got counted once for each of its \(k!\) orderings. So divide by \(k!\) to remove the double-counting. (Meanwhile, arranging all \(n\) objects in a row is just \(n!\).)
Two identities worth having reflexively:
- Symmetry: \(\binom{n}{k} = \binom{n}{n-k}\) — choosing which \(k\) to include is the same as choosing which \(n-k\) to leave out.
- Pascal's rule: \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\) — fix one element; a \(k\)-subset either contains it (choose \(k-1\) from the rest) or doesn't (choose \(k\) from the rest). This is the recurrence that builds Pascal's triangle.
The binomial theorem¶
The binomial coefficients earn their name by being the coefficients when you expand a power of a sum:
Binomial theorem
Why the coefficient is \(\binom{n}{k}\). Expanding \((x+y)^n = (x+y)(x+y)\cdots(x+y)\) means picking either \(x\) or \(y\) from each of the \(n\) factors and multiplying. You get a term \(x^k y^{n-k}\) exactly by choosing \(x\) from \(k\) of the factors — and there are \(\binom{n}{k}\) ways to choose which \(k\). Counting the ways to form each term is the coefficient.
Plugging in numbers collapses the sum into an identity
Special values of \(x, y\) turn the theorem into facts you can quote:
- \(x = y = 1\): \(\ \sum_{k=0}^{n} \binom{n}{k} = 2^n\) — the total number of subsets of an \(n\)-set (each element is in or out).
- \(x = 1, y = -1\): \(\ \sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0\) — a set has equally many even-sized and odd-sized subsets.
Recognising "this sum is a binomial expansion in disguise" is a recurring Part B/C move.
Multinomial coefficients¶
When you order a multiset — a collection with repeated, indistinguishable copies — you use the multinomial coefficient. With \(m\) kinds of object, \(k_i\) copies of kind \(i\), and \(k_1 + \cdots + k_m = n\) total:
Same logic as before. Pretend all \(n\) objects are distinct and line them up: \(n!\) ways. But the \(k_1\) copies of the first kind are actually identical, so every arrangement was counted \(k_1!\) times over (once per shuffle of those copies) — divide it out. Repeat for each kind. The classic instance is counting the distinct rearrangements of a word like MISSISSIPPI.
Stars and bars¶
This is the model for distributing identical objects into distinct boxes — the one people forget exists.
The picture that makes it obvious. Draw the \(n\) objects as stars in a row: \(\star\star\star\dots\) Now drop \(k - 1\) bars among them to slice the row into \(k\) segments; the number of stars in segment \(i\) is how many objects recipient \(i\) gets (a segment can be empty). Every distribution corresponds to one arrangement of stars and bars, and vice versa. You have \(n + k - 1\) symbols in total and just need to choose which \(k - 1\) of the positions are bars — hence \(\binom{n+k-1}{k-1}\).
The question that picks the model: identical or distinct?
This single distinction decides everything, and it's the most common place to go wrong:
- Identical objects → distinct boxes: stars and bars, \(\binom{n+k-1}{k-1}\).
- Distinct objects → distinct boxes: just \(k^n\) — each object independently picks its own box.
- Distinct objects → unlabelled groups: Stirling numbers (next).
Ask "if I swap two of the objects, do I get a genuinely different outcome?" If no, they're identical.
Stirling numbers¶
\(S(n, k)\) counts the ways to split \(n\) distinct elements into \(k\) non-empty unlabelled groups (the groups have no names — only who's with whom matters).
How to read the recursion — think about where the last element, element \(n\), goes:
- Either it sits alone in its own group. Then the other \(n-1\) elements must fill the remaining \(k-1\) groups: \(S(n-1, k-1)\) ways.
- Or it joins an existing group. First arrange the other \(n-1\) into \(k\) groups (\(S(n-1, k)\) ways), then drop element \(n\) into any one of those \(k\) groups: \(k \cdot S(n-1, k)\).
Add the two disjoint cases. Base cases: \(S(n, n) = 1\) (everyone alone) and \(S(n, 1) = 1\) (everyone together).
Why "unlabelled" matters. Because the groups have no names, \(\{\{1,2\},\{3\}\}\) and \(\{\{3\},\{1,2\}\}\) are the same partition — you don't count them twice. If the groups were labelled ("group A", "group B"), you'd multiply by \(k!\).
Counting by complement¶
Here is the highest-yield trick on this whole exam. When a problem asks for "at least one…", counting it head-on usually means slogging through overlapping cases. Instead, count the opposite and subtract from the total:
"At least one" flips to "none", which is often a single clean product.
Exam (May 2024, Problem 4): telephone numbers
Setup: 5-digit telephone numbers, and the first digit can't be \(0\).
(a) How many have a digit occurring more than once?
Head-on, "a digit repeats" splits into many overlapping cases (one pair, two pairs, a triple, …) — painful. The opposite is clean: all five digits distinct. Count that and subtract.
- Total numbers: first digit \(9\) ways (not \(0\)), the other four \(10\) ways each: \(9 \cdot 10^4\).
- All-distinct numbers: first digit \(9\) ways; second digit may be \(0\) but not equal to the first, so \(9\) ways; then \(8\), then \(7\), then \(6\): \(9 \cdot 9 \cdot 8 \cdot 7 \cdot 6\).
(b) How many have a digit occurring more than twice?
Now the opposite is "every digit appears at most twice" — which still needs cases, so the complement trick has stopped paying off. Here it's cleaner to count directly, by how many times the frequent digit appears (it can appear \(5\), \(4\), or exactly \(3\) times):
The real lesson isn't the arithmetic — it's the judgement call. Complement-counting is a tool, not a reflex. In (a) the complement was one tidy product; in (b) the complement was messier than counting directly. Sketch both before committing to one.
Inclusion–exclusion¶
Complement-counting handles "at least one" when the opposite is a single clean count. When it isn't — when you're counting a union of several overlapping sets — you need the general tool. The naive \(\lvert A \cup B \rvert = \lvert A\rvert + \lvert B\rvert\) over-counts everything in both, so you subtract the overlap back off:
Inclusion–exclusion
For two and three sets:
In general: add the singles, subtract the pairwise intersections, add the triple intersections, and so on — alternating signs by the number of sets intersected.
Why the alternating signs. Track one element that lies in exactly \(m\) of the sets. It's counted \(\binom{m}{1}\) times in the singles, subtracted \(\binom{m}{2}\) times in the pairs, added \(\binom{m}{3}\) times in the triples… The net count is \(\sum_{j\ge 1}(-1)^{j-1}\binom{m}{j} = 1\) (that's the "\(x=1,y=-1\)" identity from the binomial theorem, rearranged). So every element in the union is counted exactly once — no matter how many sets it sits in.
The usual exam setup: count by a forbidden property
Inclusion–exclusion shines on "how many things avoid all of properties \(P_1, \dots, P_r\)?". Let \(A_i\) be the things having property \(P_i\); you want the complement of \(\bigcup A_i\):
The intersections \(\lvert A_{i}\cap A_{j}\rvert\) are usually easy products, which is exactly what the formula asks for.
Worked: integers in \(1..100\) divisible by none of 2, 3, 5
Let \(A, B, C\) be the multiples of \(2, 3, 5\) up to \(100\). Counts are floor divisions:
So \(\lvert A\cup B\cup C\rvert = 50+33+20-16-10-6+3 = 74\) numbers are divisible by at least one of \(2,3,5\). The ones divisible by none are
(Sanity check: the density \(\left(1-\tfrac12\right)\left(1-\tfrac13\right)\left(1-\tfrac15\right) = \tfrac{4}{15}\) predicts \(\tfrac{4}{15}\cdot 100 \approx 26.7\). ✓)
The pigeonhole principle¶
Pigeonhole principle
If you put \(n\) items into \(m\) containers and \(n > m\), then some container holds more than one item. (More generally, some container holds at least \(\lceil n/m \rceil\).)
The principle itself is obvious — that's not where the difficulty lives. The skill is choosing what the "pigeons" and "holes" are. The move is almost always: find some quantity that can only take a few values (remainders mod \(n\), possible sums, colours, …) and spread many objects across those few values. Two objects must then collide, and that collision is what you wanted.
Discrete probability¶
Once you can count, discrete probability is mostly counting with a division at the end.
Uniform outcomes¶
When every outcome in the sample space \(\Omega\) is equally likely, the probability of an event \(A\) is just its share of the outcomes:
So a probability question becomes two counting questions: how many outcomes total, and how many are in \(A\). Everything from the counting section applies directly.
The rules¶
| Rule | When it applies | Formula |
|---|---|---|
| Addition | \(A\), \(B\) disjoint (can't both happen) | \(P(A \cup B) = P(A) + P(B)\) |
| Addition (general) | always | \(P(A \cup B) = P(A) + P(B) - P(A \cap B)\) |
| Multiplication | \(A\), \(B\) independent (neither affects the other) | \(P(A \cap B) = P(A)P(B)\) |
| Complement | always | \(P(A^c) = 1 - P(A)\) |
That last row is the probability version of the complement trick above: "at least one" is usually easiest as \(1 - P(\text{none})\).
Conditional probability¶
What it means: you've been told \(B\) definitely happened, so you throw away every outcome outside \(B\) and ask what fraction of what's left is also in \(A\). Conditioning shrinks the sample space to \(B\) and renormalises — that's exactly what dividing by \(P(B)\) does.
Disjoint is NOT the same as independent — they're nearly opposites
A trap worth internalising. If \(A\) and \(B\) are disjoint and both have positive probability, then learning that \(A\) happened tells you \(B\) definitely didn't — so they are strongly dependent, not independent. "Disjoint" is a statement about outcomes not overlapping; "independent" is a statement about one not influencing the other. Check which hypothesis you actually have before reaching for the addition or multiplication rule.