Counting, and why it is the hard part

Probability is counting, and counting is a decision

Put a fair six-sided die on the table. The probability of an even number is three outcomes over six, one half. Put two dice down and ask for a sum of seven: the answer is six over thirty-six, not one over eleven, and the reason is that sums of seven and sums of two are not equally likely. Notice what happened. The arithmetic was trivial in both cases. What required care was deciding which outcomes to call equally likely, and then counting them without missing any or counting any twice.

That is the whole subject in miniature. A probability problem on a finite, symmetric sample space is an accounting problem. You write down the sample space $\Omega$, you choose a subset $A$, and then $P(A)=|A|/|\Omega|$, provided the outcomes are symmetric enough that "equally likely" is a reasonable model. Everything that follows in this part is a technique for computing those two cardinalities.

The difficulty is that the sizes grow explosively and the descriptions of the sets are slippery. A five-card poker hand lives in a space of about two and a half million equally likely deals. A password of eight characters lives in a space of hundreds of trillions. A hash table with a thousand buckets receiving thirty keys has a space too large to write down at all. In each case the useful question is not "list the outcomes" but "count them by structure", and the structure is almost always a choice: how many ways to fill the first slot, then the second, and so on.

The subtle part is a single fork in the road. Sometimes the order in which you make the choices matters and sometimes it does not. A gold-silver-bronze podium is a different result from the same three runners in a different order. A committee of three is the same committee no matter who was named first. Counting the first kind is called a permutation and counting the second is called a combination, and the entire gap between them is a factor of $k!$. Every double-counting error in the subject can be traced back to losing track of that factor, so we will make it visible rather than memorise it.

From there the counting machinery pays off in places that do not look like dice at all. The birthday problem asks how many people are needed before two share a birthday, and the answer surprises everyone; the same calculation governs how many hash keys it takes to cause a collision, how many random samples a robust estimator needs, and how many draft tokens a speculative decoder can gamble on. The unifying quantity is the number of pairs among m objects, which grows like $m^2/2$ while the group size grows only like m. Coincidences are common because pairs are cheap.

Fill the slots, one decision at a time

Forget formulas and imagine filling slots with your hands. You have n distinct objects in front of you and k labelled positions to fill, one object per position. For the first position you may take any of the n objects. Whatever you take, the pool has shrunk by one, so the second position offers $n-1$ choices. The third offers $n-2$, and by the time you reach position k the pool offers $n-k+1$. The number of completed arrangements is the product of those choice counts, because each first choice can be paired with each second choice and so on.

This is the multiplication principle: if a construction can be decomposed into stages, and the number of choices at each stage does not depend on the earlier choices, then the total count is the product of the stage counts. The independence clause is easy to skip past and it is the whole content of the rule. Selecting objects without replacement makes the stage counts depend on the past — that is precisely why the product $n(n-1)(n-2)\cdots$ shrinks, and why a naive $n^k$ would be wrong.

The factorial shorthand is the extreme case. If you arrange all n objects, then $P(n,n)=n!$. Three books can be ordered in $3!=6$ ways, a deck of cards in $52!$ ways, a number with sixty digits. The falling factorial $n!/(n-k)!$ should be read as "start at n! and divide away the arrangements of the objects you never used", because those unused $n-k$ objects would contribute $(n-k)!$ spurious orderings if you had counted them.

Small cases keep you honest. With $n=5$ and $k=2$, the tree has five branches at the first level and four at the second, giving twenty ordered pairs. With $k=3$ it is $5\cdot4\cdot3=60$. With $k=5$ it is $5!=120$. The demo below draws that tree: one node per prefix, and each node at level j sprouting $n-j$ children. The final row is the population of complete ordered selections, and the readout multiplies the branch factors as the sliders move.

Two boundary cases are worth naming because they clean up formulas later. If $k=0$ there is exactly one selection: the empty one. So $P(n,0)=1$. If $k>n$ there is no selection at all, because the pool runs dry, so $P(n,k)=0$. Both follow from $n!/(n-k)!$ once you agree that $0!=1$, which is the convention that makes the factorial recurrence $m!=m\cdot(m-1)!$ hold all the way down to $m=1$.

A last habit, and the one that prevents most errors: before computing anything, ask whether a swap of two chosen items would produce a different outcome. If yes, you are counting ordered selections and the answer is $P(n,k)$. If no, order is irrelevant, and you will over-count by exactly the number of orderings of each selection — which is the subject of the next section.

Divide by how many times you said the same thing

A committee does not care who was named first. Yet the slot-filling procedure of the previous section insists on an order, so it counts every committee once for each ordering of its members. A committee of k people was counted $k!$ times, because $k$ distinct names can be arranged in $k!$ ways. To recover the number of genuine sets, divide the ordered count by that redundancy.

The symbol $\binom{n}{k}$, read "n choose k", is the binomial coefficient. It counts k-element subsets of an n-element set. The factor $k!$ in the denominator is not a correction or a fudge; it is the exact multiplicity of the overcount, and understanding it is the difference between being able to derive the formula and being able to use it. It is also the place where the classic mistake lives: dividing by $k!$ when order does matter, or forgetting to divide when it does not.

Two symmetries fall out immediately. Choosing a committee of k is the same act as choosing the $n-k$ people to leave out, so $\binom{n}{k}=\binom{n}{n-k}$; the algebra agrees because swapping k and $n-k$ in the formula exchanges the two factors in the denominator. And the two ends are fixed: $\binom{n}{0}=\binom{n}{n}=1$, one empty set and one full set. The interior values form Pascal's triangle through the recurrence $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$, which is itself a one-line counting argument: every k-subset either contains a distinguished element or does not.

The demo below makes the overcount visible instead of argued. It lists every ordered selection of k items from n, laid out as a grid of cells, and colours each cell by the unordered set it came from. Every colour appears exactly $k!$ times — twice when $k=2$, six times when $k=3$. Collapsing each colour block to one cell gives the combinations, and the ratio of the two totals is $k!$ by construction.

Counting sets rather than sequences is what makes the binomial coefficient the workhorse of elementary probability. The number of five-card poker hands is $\binom{52}{5}=2{,}598{,}960$, and the number of hands containing four aces is $\binom{4}{4}\binom{48}{1}=48$, giving a probability of about $1.8\times10^{-5}$. The number of ways to be dealt two hearts is $\binom{13}{2}\binom{39}{3}$ out of the same denominator. In every case the sample space is declared as a set of unordered hands, because dealing the same five cards in a different order is not a different hand.

That declaration is a modelling choice, and it matters that it is a choice. You could equally declare the sample space to be ordered deals, in which case the numerator and denominator both pick up factors of $5!$ and the ratio is unchanged. Consistency is all that is required: count the favourable outcomes and the total in the same currency. Most counting disasters are currency mismatches, where the numerator is unordered and the denominator is ordered, and the resulting probability is wrong by a clean factor of $k!$.

When the choice is between ordered and unordered, the safe recipe is: choose the space in which the event of interest has the simplest description, then make sure every part of the calculation lives in that space. For hands, committees and hash collisions that means unordered; for passwords, podiums and DNA sequences it means ordered. The next section shows why the unordered choice is the one that makes the complications of coincidence tractable.

Pairs are cheap, so matches are common

Ask a room of twenty-three people whether two share a birthday and you will usually find a pair, even though there are $365$ possible birthdays and only $23$ people. The result is called the birthday paradox, but there is no paradox: the calculation is short, and the intuition that fails is the one that compares 23 to 365 instead of comparing the number of pairs to 365. Twenty-three people form $\binom{23}{2}=253$ pairs, each of which has a roughly $1/365$ chance of matching. Two hundred and fifty-three small chances stack up fast.

The clean way to compute the probability is to count the complement, the event that all birthdays are distinct. Fix an order for the people and assign birthdays one at a time. The first person has 365 choices. The second must avoid the first, leaving 364 of 365. The third must avoid both, and so on. Feeding each person a choice from the remaining birthdays gives the classic product.

The exponential approximation is worth understanding because it is the bridge to hashing. Taking logs of the product converts it to the sum $\sum_{i}\log(1-i/N)$, and for small $i/N$ the logarithm is about $-i/N$. The sum of $i$ from zero to $m-1$ is $m(m-1)/2$, so the log of the no-match probability is about $-m(m-1)/(2N)$, and the match probability is about $1-e^{-m(m-1)/(2N)}$. Setting that to one half and solving gives $m\approx1.177\sqrt N$. For $N=365$ that is about $22.5$, so the threshold is $23$.

The same product describes a hash table. Throw m keys independently and uniformly into N buckets and ask for the chance that two keys land together. This is exactly the birthday calculation with buckets in place of days, and the answer is $1-\prod_{i=0}^{m-1}(1-i/N)$. The consequence is a design rule: a hash function with $N$ buckets is not safe until you have thrown roughly $\sqrt N$ keys at it. A $32$-bit hash collides with decent probability after a few tens of thousands of keys, and a $128$-bit hash pushes the same threshold out past $10^{19}$. The demo computes the product in log space, because multiplying many numbers near one loses precision almost immediately while summing their logs does not.

Nothing in the derivation used birthdays. Replace N=365 with the number of possible hash values and the curve is the collision probability; replace it with the number of frames in a video and it is the chance that two frames are indistinguishable to a checksum. The same complement trick underlies the universal hashing guarantee: if a family of hash functions spreads every pair of distinct keys uniformly, then for any fixed pair the collision probability is $1/N$, and the birthday bound converts that pairwise statement into a bound on the number of keys a table can hold. It is also why randomised algorithms quote success probabilities in terms of the number of random samples rather than the number of data points: the relevant count is always pairs, not singles.

One more connection is worth making explicit because it reappears throughout the guide. Robust model fitting samples a minimal set of correspondences and hopes all of them are inliers; the chance that a random sample of s points is clean is $p^s$ for an inlier ratio p, so the chance that at least one of M trials is clean is $1-(1-p^s)^M$. That is a collision calculation in disguise — trials are "buckets" and a clean sample is a "match" — and it is how the iteration count for RANSAC is chosen. The same shape of argument decides how many draft tokens a speculative decoder can accept before the acceptance probability collapses. In each case the bound is governed by the number of pairs, and the square root is never far away.

Counting under the hood

Every formula in one place

Where to go deeper

• William Feller, An Introduction to Probability Theory and Its Applications, Vol. 1, Chapter 2, "Elements of Combinatorial Analysis" — the classical treatment of permutations, combinations and the birthday problem, with careful attention to the overcount.
• Charles Grinstead and J. Laurie Snell, Introduction to Probability, Chapters 1–3 — a free textbook that builds counting from simulation and includes the birthday problem as a running computational example.
• Dimitri Bertsekas and John Tsitsiklis, Introduction to Probability (MIT 6.041 / 6.431), Chapter 1 — the counting chapter from the MIT probabilistic systems course; the course materials are on OCW.
• Ronald Graham, Donald Knuth and Oren Patashnik, Concrete Mathematics, Chapter 5 — binomial coefficients as generating functions, with the identities and asymptotics used for large n.
• Grant Sanderson, "Binomial coefficients and Pascal's triangle", 3Blue1Brown — the overcount made visual, in the same spirit as the grid above.