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¶

\[ \binom{n}{k} = \frac{n!}{(n-k)!\,k!} \]

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!\).)

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:

\[ \frac{n!}{k_1!\,k_2!\cdots k_m!} \]

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.

\[ \binom{n + k - 1}{k - 1} \qquad (n \text{ identical objects}, \; k \text{ distinct recipients}) \]

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).

\[ S(n, k) = S(n-1, k-1) + k \cdot S(n-1, k) \]

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:

\[ (\text{what you want}) = (\text{everything}) - (\text{the opposite of what you want}) \]

"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\).

\[ \underbrace{9 \cdot 10^4}_{\text{all}} - \underbrace{9 \cdot 9 \cdot 8 \cdot 7 \cdot 6}_{\text{all distinct}} = 62784 \]

(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):

\[ \underbrace{9}_{\text{5 times}} + \underbrace{5 \cdot 9 \cdot 9}_{\text{4 times}} + \underbrace{10 \cdot 9^3}_{\text{3 times}} = 7704 \]

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.

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:

\[ P(A) = \frac{\lvert A \rvert}{\lvert \Omega \rvert} \]

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¶

\[ P(A \mid B) = \frac{P(A \cap B)}{P(B)}, \qquad P(B) > 0 \]

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.