Counting the possibilities

When outcomes are equally likely, a probability is a ratio of two counts, and the counts are rarely small enough to list. This lesson builds the three tools that do the counting, checks them against a deck of cards, and then uses them on a question whose true answer almost nobody guesses within a factor of two.

Choices in sequence

Everything here rests on one observation. If a first choice can be made in $a$ ways and, for each of those, a second in $b$ ways, then the pair can be made in $a b$ ways. Lay the possibilities out as a rectangular grid with $a$ rows and $b$ columns and the claim is just the area of a rectangle. Extend to any number of stages and it becomes the product rule: multiply the number of options at each stage, provided the number of options at each stage does not depend on which options were taken earlier.

That proviso is the whole art. Two dice give $6 \times 6 = 36$ sequences because the second die does not care what the first did. A four-character password from the $26$ lowercase letters gives $26^{4} = 456976$ , again because letters may repeat. But drawing two cards from a deck gives $52 \times 51 = 2652$ ordered pairs, not $52^{2}$ , because the second draw has one fewer option: the count at each stage changed, though crucially it changed by the same amount regardless of which card went first, and that is enough for the rule to apply.

Sampling with replacement leaves the pool intact and gives $n^{k}$ sequences of length $k$ . Sampling without replacement shrinks it and gives $n (n - 1) (n - 2) \dots (n - k + 1)$ , a product of $k$ falling terms. When $k = n$ the second product uses up the whole pool and is written $n!$ , read " $n$ factorial", with $0! = 1$ by the convention that there is exactly one way to arrange nothing.

Ordered selections

The falling product has a name. The number of permutations of $k$ items chosen from $n$ distinct items, where order matters and nothing is reused, is

P (n, k) = n (n - 1) \dots (n - k + 1) = \frac{n!}{(n - k)!}

The second form is the first with the unused tail $(n - k)!$ divided away, which is often the easier thing to compute. The five-card deal from a shuffled deck, if you insist on tracking the order they arrived in, gives $P (52, 5) = 52 \times 51 \times 50 \times 49 \times 48 = 311875200$ possibilities.

Repeated items collapse the count. The letters of MISSISSIPPI can be arranged in $11!$ ways if the letters are all treated as distinct, but the four S's are not distinguishable, so every genuine arrangement has been counted $4!$ times over on their account, and likewise $4!$ for the I's and $2!$ for the P's. Divide those out:

\frac{11!}{4! 4! 2! 1!} = 34650

That division, cancelling the orderings you did not want to distinguish, is the single most useful move in combinatorics, and the next section is nothing but the same move applied once.

Unordered selections

A poker hand is a set of five cards, and the order it was dealt in is nobody's business. Each such set of five was counted $5!$ times among the $311875200$ ordered deals, once for each arrangement of the same five cards. So the number of distinct hands is that figure divided by $5! = 120$ , giving $2598960$ .

In general the number of ways to choose $k$ items from $n$ when order is irrelevant is written $C (n, k)$ , read " $n$ choose $k$ ", and

C (n, k) = \frac{P (n, k)}{k!} = \frac{n!}{k! (n - k)!}

Two properties are worth carrying. First, $C (n, k) = C (n, n - k)$ , because choosing which $k$ to take is the same act as choosing which $n - k$ to leave. Second, $C (n, k) = C (n - 1, k - 1) + C (n - 1, k)$ : fix any one item, and every selection either includes it, which leaves $k - 1$ to pick from the other $n - 1$ , or excludes it, which leaves $k$ to pick from the other $n - 1$ . That identity generates Pascal's triangle row by row, and it will return in the lesson on the binomial distribution.

Example. A lottery draws $6$ numbered balls from $49$ , order irrelevant. What is the probability that one particular ticket matches all six?

The number of possible draws is $C (49, 6) = 49! / (6! 43!) = 13983816$ , and exactly one is the ticket, so the probability is $1 / 13983816 \approx 7.15 \times 10^{- 8}$ . Buying one ticket a week, the expected wait for a win is about $269000$ years.

Now you. How many ways are there to choose a committee of $3$ people from a group of $10$ , and what is the probability that a randomly chosen committee contains one particular person?

Answer

$C (10, 3) = 120$ committees. Those containing the given person are the committees made by adding two others from the remaining nine, so there are $C (9, 2) = 36$ , and the probability is $36 / 120 = 0.3$ . Equivalently, the person occupies one of $10$ places and $3$ are taken, so $3 / 10$ .

Poker as a test bench

A ranked list of poker hands is a good check on the machinery, because the ranking was fixed by players long before anyone computed it, and the counts must come out in the same order.

Take two pair. Choose the two ranks that will be paired: $C (13, 2) = 78$ ways. Choose two suits for each of them: $C (4, 2) = 6$ ways each, so $36$ . The fifth card must avoid both chosen ranks, leaving $52 - 8 = 44$ cards. That gives $78 \times 36 \times 44 = 123552$ hands, and

P (two pair) = \frac{123552}{2598960} \approx 0.0475

Note the order of the two ranks was never used, which is why $C (13, 2)$ and not $13 \times 12$ appears. Choosing "kings and threes" is the same hand as choosing "threes and kings", and counting it twice would double the answer.

Now a flush. Choose a suit, $4$ ways, then any five of its $13$ cards, $C (13, 5) = 1287$ ways, giving $5148$ . Of those, $40$ are also straights and are ranked higher, so a plain flush has $5108$ hands and probability $5108 / 2598960 \approx 0.0020$ . Two pair is about $24$ times commoner than a flush, and duly ranks below it. The same method gives $3744$ full houses ( $\approx 0.0014$ ) and $624$ four-of-a-kinds ( $\approx 0.00024$ ), and the ranking players arrived at by experience is exactly the ranking these counts produce.

Example. How many five-card hands are three of a kind, meaning exactly three cards of one rank and two other cards of two different ranks?

Pick the tripled rank in $13$ ways and its three suits in $C (4, 3) = 4$ ways. The other two cards must be of two distinct ranks, neither equal to the first: $C (12, 2) = 66$ choices of ranks, and $4 \times 4 = 16$ choices of suit. That gives $13 \times 4 \times 66 \times 16 = 54912$ hands, a probability of about $0.0211$ .

Now you. How many five-card hands contain exactly one pair, meaning two cards of one rank and three others of three different ranks?

Answer

$13 \times C (4, 2) \times C (12, 3) \times 4^{3} = 13 \times 6 \times 220 \times 64 = 1098240$ hands, a probability of about $0.4226$ . Nearly half of all hands, which is why one pair is worth almost nothing.

The birthday problem

Take $23$ people at random. What is the probability that two of them share a birthday? The usual guess is a few percent, on the grounds that $23$ is small next to $365$ . The right answer is slightly over one half.

Count the complement, as always. Ignore leap years and assume all $365$ days equally likely, an assumption examined below. Sequences of $23$ birthdays number $365^{23}$ , all equally likely. Those with no repeat are ordered selections without replacement, $365 \times 364 \times \dots \times 343$ , so

P (no shared birthday) = \frac{365}{365} \times \frac{364}{365} \times \dots \times \frac{343}{365} \approx 0.4927

and the probability of at least one shared birthday is $1 - 0.4927 = 0.5073$ .

The reason intuition fails is that people compare $23$ with $365$ , when the right comparison is with the number of pairs. Twenty-three people form $C (23, 2) = 253$ pairs, and $253$ against $365$ no longer looks small. Each pair matches with probability $1 / 365$ , so the union bound of the previous lesson caps the answer at $253 / 365 \approx 0.693$ , which is loose but already in the right neighbourhood, and it is loose in the right direction: the pairs overlap heavily, since any three people share three pairs among them.

The curve climbs fast. Ten people give $0.117$ , thirty give $0.706$ , fifty give $0.970$ . The real-world assumption of uniform birthdays is not quite true, with seasonal peaks and a deficit around late December in many countries, but the effect only ever pushes the probability up, since any unevenness makes coincidences commoner. The $23$ figure is therefore a safe upper bound on the number of people needed.

Example. What is the probability that among $10$ people at least two share a birthday?

Multiply the falling ratios: $P (no match) = \prod_{k = 0}^{9} (365 - k) / 365 \approx 0.8831$ , so the answer is $1 - 0.8831 = 0.1169$ , about one chance in nine. Small, but far larger than the $10 / 365 \approx 0.027$ that a careless comparison suggests.

Now you. Four fair dice are rolled. What is the probability that at least two show the same number?

Answer

The same structure with $6$ in place of $365$ : $P (all different) = (6 \times 5 \times 4 \times 3) / 6^{4} = 360 / 1296 \approx 0.2778$ , so at least one repeat has probability $\approx 0.7222$ .

What counting assumes, and when it stops working

Every calculation above began by declaring a set of equally likely outcomes and then measuring a subset of it. That is a strong assumption, and it is doing more work than the algebra. If the deck is not well shuffled, or the birthdays are not uniform, or the lottery machine favours a ball, the counts are still right and the probabilities are wrong. Counting is a technique for evaluating a model, not evidence that the model is correct.

There is a second and sharper limit. The whole method treats the sample space as intact: all $2598960$ hands are live, all $365^{23}$ birthday sequences are live. The moment any information arrives, most of them are not. Told that the first two cards dealt are aces, the remaining possibilities are a much smaller set, and the probability of four of a kind is no longer $0.00024$ . Told that one person in the room was born in March, the birthday calculation changes.

Recounting from scratch after every piece of news is unworkable, and it is also unnecessary, because the effect of information on a probability follows one rule that can be derived once. Deriving it, and finding that it makes independence into a definition rather than a feeling, is the next lesson.