Counting Done Right: From the Birthday Paradox to the Binomial Distribution

Discrete probability rests on one sentence: if all outcomes are equally likely, $P(A) = |A|/|\Omega|$. Everything hard about it is therefore counting, and counting fails the moment you are vague about two questions — does order matter, and may an element repeat. Those two binary choices generate the four urn models, and from them the birthday paradox and the binomial distribution follow almost mechanically.

Counting by stages: the multiplication principle

The clause "regardless of the earlier choices" is the entire content. Drawing $k$ balls from $n$ with replacement leaves $m_i = n$ at every stage, giving $n^k$. Without replacement, the pool shrinks by a fixed amount, $m_i = n-i+1$, giving the falling factorial

$n^{\underline{k}} = n(n-1)\cdots(n-k+1) = \frac{n!}{(n-k)!}$

Both are ordered counts: the choice tree has $n^k$ and $n^{\underline{k}}$ leaves respectively, and each leaf is one sequence.

The four urn models

An urn holds $n$ distinguishable balls, and we draw $k$. The two yes/no questions give exactly four counting problems.

The bottom row is easy: every unordered selection of $k$ distinct balls has exactly $k!$ orderings, so the ordered count over-counts by a constant factor, and $\binom{n}{k} = n^{\underline{k}}/k!$. Dividing out the symmetry is the standard route from ordered to unordered — but only because that factor is the same for every selection.

Stars and bars: why one cell is different

For multisets the division fails: $\{a,a,b\}$ has $3$ orderings, $\{a,b,c\}$ has $6$, so no single divisor undoes the over-counting ($n^k/k!$ is not even an integer in general). Re-encode instead: an unordered draw with replacement is determined by the multiplicities $x_1 + \cdots + x_n = k$, $x_i \ge 0$. Write $k$ stars and split the $n$ bins with $n-1$ bars:

$\underbrace{\star\star}_{x_1=2}\;\mid\;\underbrace{\phantom{\star}}_{x_2=0}\;\mid\;\underbrace{\star\star\star}_{x_3=3} \qquad\Longrightarrow\qquad \binom{n+k-1}{k}$

Complement counting: the birthday paradox

Put $k$ people into $n = 365$ equally likely birthdays. The sample space is ordered with replacement, $|\Omega| = 365^k$; the event "all distinct" is ordered without replacement, $365^{\underline{k}}$. So

$P(\text{collision}) = 1 - \frac{365^{\underline{k}}}{365^{\,k}} = 1 - \prod_{i=0}^{k-1}\Big(1 - \frac{i}{365}\Big)$

The paradox is one of framing: intuition answers "who shares my birthday", i.e. $k-1$ comparisons with $P = 1-(364/365)^{k-1}$, which needs a group of $k = 254$. The question instead counts all $\binom{k}{2}$ pairs, and at $k = 23$ that is $253$ pairs — numerically the same $253$, by coincidence. Pretending those pairs were independent gives $(1-\tfrac{1}{365})^{253} \approx 0.4995$; it is close to the exact $0.4927$ but systematically overestimates non-collision, because the pair events are dependent (a shared birthday of $A,B$ and of $B,C$ forces one for $A,C$).

Bernoulli trials and the binomial distribution

Repeat an experiment $n$ times independently, recording success (probability $p$) or failure. One outcome is a word in $\{S,F\}^n$ — ordered with replacement, but not equally likely: by independence a specific word with $k$ successes has probability $p^k(1-p)^{n-k}$. That value depends only on $k$, not on where the successes sit, so we merely count the words — choosing which $k$ of $n$ slots succeed is unordered without replacement.

The binomial coefficient is no fudge factor: it is the urn model appearing inside a probability. Normalisation is the binomial theorem, $\sum_k \binom{n}{k}p^k(1-p)^{n-k} = (p + (1-p))^n = 1$. If instead we sample without replacement from $N$ items containing $K$ successes, independence fails and the count becomes hypergeometric, $P(X=k) = \binom{K}{k}\binom{N-K}{n-k}\big/\binom{N}{n}$ — three binomial coefficients, no $p$ at all.

Worked example: defective parts, with and without replacement

Step 1 — Fix the model. A crate holds $N = 12$ components, $K = 4$ defective; we inspect $n = 5$. Inspection is without replacement and order is irrelevant, so $\Omega$ = all $5$-subsets, $|\Omega| = \binom{12}{5} = 792$, equally likely.

Step 2 — Count the favourable sets. Exactly $2$ defective means choosing $2$ of $4$ and $3$ of $8$: $\binom{4}{2}\binom{8}{3} = 6 \cdot 56 = 336$.

Step 3 — Divide. $P(X=2) = \frac{336}{792} = \frac{14}{33} \approx 0.4242$.

Step 4 — Compare with replacement. Testing and returning each part gives Bernoulli trials with $p = 4/12 = 1/3$, hence $P(Y=2) = \binom{5}{2}\big(\tfrac13\big)^2\big(\tfrac23\big)^3 = 10 \cdot \tfrac{1}{9} \cdot \tfrac{8}{27} = \tfrac{80}{243} \approx 0.3292$.

Step 5 — Read the difference. Both have mean $np = 5/3$, but drawing without replacement is self-correcting, so the variance carries the finite-population correction $\frac{N-n}{N-1} = \frac{7}{11}$ and mass piles up near the mean.

Summary

• Multiplication principle: independent stage-by-stage choices multiply; every formula here follows from it.
• Four urn models: $n^k$, $n^{\underline{k}}$, $\binom{n}{k}$, $\binom{n+k-1}{k}$ — classified by order and replacement.
• Divide by $k!$ only when the symmetry factor is constant; multisets need stars and bars.
• Complement counting turns "at least one" into "none": $k = 23$ birthdays suffice for $P > \tfrac12$ because pairs grow like $k^2$.
• The coefficient in $\mathrm{Bin}(n,p)$ counts arrangements; the same count without replacement gives the hypergeometric law.

Questions & Answers

Why does dividing by $k!$ fail for unordered sampling with replacement?

Why is the birthday result so counter-intuitive?

What does complement counting buy us technically?

Where does independence enter the binomial formula?

Why $\binom{n}{k}$ rather than $n^{\underline{k}}$ in $\mathrm{Bin}(n,p)$?

When may I replace the hypergeometric by the binomial?

How do I decide "ordered or unordered" in a word problem?

What links the birthday paradox to computer science?

The rest of the map

The four urn models are the entrance hall of discrete probability; here is what lies immediately beyond.

Counting, complement counting and independence are the three moves behind nearly every discrete distribution — master the urn table and the rest is bookkeeping.