Combinatorics: Counting Without Enumerating

Most probability questions are secretly counting questions: favorable outcomes over total outcomes. Fluency means recognizing which counting pattern you're looking at within seconds.

The core four

Ordered, no repetition (permutations). Ways to arrange $k$ of $n$ distinct items: $\frac{n!}{(n-k)!}$. All $n$: just $n!$.

Unordered, no repetition (combinations). $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ — choose a committee, a poker hand, a subset. The identity $\binom{n}{k} = \binom{n}{n-k}$ (choosing who's in ≡ choosing who's out) saves arithmetic constantly.

Ordered, with repetition. $n^k$ — passwords, dice sequences (the $6^6$ in the all-faces-distinct question).

Unordered, with repetition (stars and bars). Ways to put $k$ identical balls into $n$ boxes: $\binom{k + n - 1}{n - 1}$. The disguises are many: non-negative integer solutions of $x_1 + \cdots + x_n = k$, dice-sum counts, distributing $10 among 4 traders.

The meta-skill is classification: before computing anything, ask "does order matter? can items repeat?" — two binary questions, four formulas.

Inclusion-exclusion

To count a union, add the pieces, subtract the overlaps, add back the triple overlaps:

$$|A \cup B \cup C| = |A| + |B| + |C| - |A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|$$

The classic application: derangements — permutations with no fixed point ("no one gets their own hat"). Inclusion-exclusion gives

$$D_n = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!} \approx \frac{n!}{e}$$

so the probability a random permutation has no fixed point converges to $1/e \approx 37\%$ — nearly independent of $n$, a genuinely shocking fact that makes it a recurring interview closer. (Companion fact via linearity: the expected number of fixed points is exactly 1, for any $n$.)

Symmetry and overcounting

The professional's move is dividing out overcounting rather than counting directly:

• Circular arrangements: $n$ people around a table: $\frac{n!}{n} = (n-1)!$ — divide by rotations.
• Poker probabilities: P(full house) $= \frac{13 \cdot \binom{4}{3} \cdot 12 \cdot \binom{4}{2}}{\binom{52}{5}} \approx 0.14\%$. Structure: choose the rank triple, its suits, the pair rank, its suits; divide by all hands. Every poker question has this choose-the-structure shape, and SIG in particular loves them.
• Grid paths: lattice paths from $(0,0)$ to $(m,n)$ moving only right/up: $\binom{m+n}{m}$ — arrange the sequence of moves. Add a forbidden diagonal and you're at the reflection principle and Catalan numbers $\frac{1}{n+1}\binom{2n}{n}$ — worth recognizing, rarely required in full.

The interview version

"8 people, split into two teams of 4 — how many ways?" — $\binom{8}{4}/2 = 35$: the division by 2 (unlabeled teams) is the entire point of the question. "How many ways to give 10 identical chips to 4 players?" — stars and bars, $\binom{13}{3} = 286$. "Five letters into five envelopes at random — P(nobody gets theirs)?" — $D_5/5! = 44/120 \approx 0.367 \approx 1/e$. Classify first, compute second, and say the classification out loud — the narration is most of the grade.