Counting and equally likely outcomes

Lesson 1 showed that when a sample space has finitely many equally likely outcomes, the probability of an event is the number of outcomes in it divided by the total number. That turns probability into counting, and counting turns out to be hard enough to deserve a lesson of its own. The sample spaces of real problems are far too large to list: there are about \(8 \times 10^{67}\) orderings of a deck of cards and nearly 14 million tickets in a 6-from-49 lottery. This lesson develops the tools that count such sets without listing them, proves the identities that make the tools work, and applies them to cards, lotteries, quality control samples, birthdays and matching problems.

The multiplication principle

Everything in combinatorics rests on one rule. If a procedure has \(k\) stages, the first stage can be done in \(n_1\) ways, and for each way of doing the earlier stages the next stage can be done in \(n_2\), then \(n_3\), and so on up to \(n_k\) ways, then the whole procedure can be done in \(n_1 n_2 \cdots n_k\) ways. The rule is proved by induction on \(k\): the outcomes of a two-stage procedure can be laid out in a table with \(n_1\) rows and \(n_2\) columns, and a \(k\)-stage procedure is a two-stage procedure whose first stage is the first \(k - 1\) stages.

The important phrase is 'for each way'. The number of choices at a stage may depend on which choices were made earlier, but the count must not. A license plate with three letters followed by three digits can be made in \(26^3 \times 10^3 = 17{,}576{,}000\) ways. A three-letter code with no repeated letter can be made in \(26 \times 25 \times 24 = 15{,}600\) ways: the second letter has 25 choices whatever the first letter was.

Permutations

A permutation of \(n\) distinct objects is an arrangement of them in order. By the multiplication principle there are \(n!\) permutations: \(n\) choices for the first position, \(n - 1\) for the second, and so on. More generally, the number of ordered selections of \(k\) objects from \(n\), without repetition, is

This is sometimes written \(P(n, k)\) or \({}_nP_k\); we use the falling factorial \((n)_k\) to avoid confusion with probabilities. With repetition allowed, the number of ordered selections is simply \(n^k\). Factorials grow very fast. Stirling's formula, \(n! \approx \sqrt{2\pi n}\,(n/e)^n\), gives their size: \(52!\) is about \(8.07 \times 10^{67}\), which is why no two well-shuffled decks in history have almost certainly ever been in the same order.

Combinations

A combination is an unordered selection. The number of ways to choose a set of \(k\) objects from \(n\) is the binomial coefficient

The proof is a double count, a technique worth knowing in its own right. Count the ordered selections of \(k\) from \(n\) in two ways. Directly, there are \((n)_k\). Alternatively, first choose the set of \(k\) objects, in \(\binom{n}{k}\) ways, and then arrange it, in \(k!\) ways. So \((n)_k = \binom{n}{k} k!\), which gives the formula. The convention \(0! = 1\) makes \(\binom{n}{0} = \binom{n}{n} = 1\), as it should: there is exactly one way to choose nothing, and one way to choose everything.

Binomial coefficients satisfy many identities, and most have both an algebraic proof and a counting proof. The counting proofs are usually more illuminating.

• Symmetry: \(\binom{n}{k} = \binom{n}{n - k}\). Choosing the \(k\) objects to take is the same as choosing the \(n - k\) to leave.

• Pascal's rule: \(\binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k}\). Fix one object. A \(k\)-set either contains it, and then the other \(k - 1\) come from the remaining \(n - 1\), or it does not, and then all \(k\) come from the remaining \(n - 1\).

• The binomial theorem: \((x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n - k}\). Expanding the product of \(n\) factors \((x + y)\), each term chooses \(x\) from some set of \(k\) factors and \(y\) from the rest.

• Vandermonde's identity: \(\binom{m + n}{r} = \sum_{k} \binom{m}{k}\binom{n}{r - k}\). Choose \(r\) people from a room with \(m\) women and \(n\) men by splitting on the number of women chosen.

Setting \(x = y = 1\) in the binomial theorem shows that a set of \(n\) objects has \(2^n\) subsets. Setting \(x = -1\), \(y = 1\) shows that it has as many subsets of even size as of odd size, a fact we used in lesson 1 to justify inclusion–exclusion.

Multinomial coefficients

The number of ways to divide \(n\) distinct objects into groups of sizes \(n_1, n_2, \ldots, n_r\), with \(n_1 + \cdots + n_r = n\), where the groups are labeled, is

Proof: choose the first group in \(\binom{n}{n_1}\) ways, the second from what remains in \(\binom{n - n_1}{n_2}\) ways, and so on; the product telescopes to the formula. The same number counts the distinct arrangements of a word with repeated letters. The letters of MISSISSIPPI, with one M, four I's, four S's and two P's, can be arranged in \(11!/(1!\,4!\,4!\,2!) = 34{,}650\) distinct ways.

Stars and bars

How many ways are there to put \(n\) identical objects into \(k\) labeled boxes? Represent a distribution by a row of \(n\) stars separated into boxes by \(k - 1\) bars: the arrangement ★★|★||★★★ puts 2, 1, 0 and 3 objects into four boxes. Every arrangement of \(n\) stars and \(k - 1\) bars corresponds to exactly one distribution and vice versa, so the count is

Requiring every box to be non-empty gives \(\binom{n - 1}{k - 1}\): put one object in each box first, then distribute the rest. Stars and bars counts unordered selections with repetition, such as the number of ways a customer can buy 12 doughnuts from 5 flavors, \(\binom{16}{4} = 1{,}820\). One warning: these distributions are not equally likely when objects are placed at random, so stars and bars counts outcomes but is rarely the right sample space for a probability.

Sampling with and without replacement

A box contains \(N\) items, of which \(K\) are defective. An inspector draws \(n\) at random without replacement. What is the probability that exactly \(k\) are defective? The sample space is the set of all \(\binom{N}{n}\) samples, equally likely. A favorable sample is made by choosing \(k\) of the defectives and \(n - k\) of the good items, so

This is the hypergeometric distribution, which we meet again in lesson 7. If instead each drawn item is put back before the next draw, the draws are independent, each defective with probability \(p = K/N\), and the probability becomes \(\binom{n}{k}p^k(1 - p)^{n - k}\), the binomial distribution. When \(N\) is large compared with \(n\), replacement hardly matters and the two agree closely, which is why surveys of a few thousand people from a population of millions can use the simpler binomial formulas.

The birthday problem

In a room of \(n\) people, what is the probability that at least two share a birthday? Assume 365 equally likely birthdays and ignore leap years. The complement, that all birthdays differ, is easier. Ordered lists of \(n\) birthdays form the sample space, with \(365^n\) equally likely outcomes, and the lists with no repeat number \((365)_n\). So

The answer passes one half at \(n = 23\) and reaches about 0.97 at \(n = 50\). The surprise comes from counting pairs rather than people: 23 people form \(\binom{23}{2} = 253\) pairs, each with a 1 in 365 chance of a match. A useful approximation follows from \(1 - x \approx e^{-x}\): the probability of no match is about \(\exp(-n(n-1)/730)\). The same calculation, with 365 replaced by the number of possible values, governs collisions in hash tables and the security of digital signatures, where it is called the birthday bound.

from math import comb, exp, prod
import random

def p_shared(n, days=365):
    return 1 - prod((days - i) / days for i in range(n))

for n in (10, 20, 23, 30, 50):
    approx = 1 - exp(-n * (n - 1) / (2 * 365))
    print(f"n = {n:2d}: exact {p_shared(n):.4f}   approx {approx:.4f}")

rng = random.Random(251)
trials, n = 100_000, 23
hits = sum(len(set(rng.randrange(365) for _ in range(n))) < n for _ in range(trials))
print(f"simulated, n = 23: {hits / trials:.4f}")

# acceptance sampling from the example, exact and simulated
exact = comb(46, 5) / comb(50, 5)
boards = [1] * 4 + [0] * 46
acc = sum(sum(rng.sample(boards, 5)) == 0 for _ in range(trials))
print(f"accept shipment: exact {exact:.4f}, simulated {acc / trials:.4f}")

n = 10: exact 0.1169   approx 0.1160
n = 20: exact 0.4114   approx 0.4058
n = 23: exact 0.5073   approx 0.5000
n = 30: exact 0.7063   approx 0.6963
n = 50: exact 0.9704   approx 0.9651
simulated, n = 23: 0.5101
accept shipment: exact 0.6470, simulated 0.6468

Matching and derangements

A secretary puts \(n\) letters into \(n\) addressed envelopes at random. What is the probability that no letter goes into its own envelope? A permutation with no fixed point is called a derangement. Let \(A_i\) be the event that letter \(i\) lands in envelope \(i\). Any \(k\) specified letters land correctly in \((n - k)!\) of the \(n!\) permutations, so the intersection of any \(k\) of the events has probability \((n - k)!/n!\), and there are \(\binom{n}{k}\) such intersections. Inclusion–exclusion gives

so the probability of no match is \(\sum_{k=0}^{n} (-1)^k/k!\), the partial sum of the series for \(e^{-1}\). The answer settles almost immediately to \(1/e \approx 0.3679\) and hardly depends on \(n\): the chance that no one gets their own coat back at a large party is about the same as at a party of six. This result, due to Pierre Rémond de Montmort in 1708, is one of the earliest uses of inclusion–exclusion.

Lotteries and poker

In a 6-from-49 lottery, such as the Canadian Lotto 6/49, a player chooses 6 numbers from 1 to 49 and the draw selects 6. The jackpot needs all six: one ticket in \(\binom{49}{6} = 13{,}983{,}816\). Matching exactly three numbers needs three of the six winning numbers and three of the 43 others, \(\binom{6}{3}\binom{43}{3} = 246{,}820\) tickets, so about 1 in 57. This is a hypergeometric probability in disguise.

A five-card poker hand is one of \(\binom{52}{5} = 2{,}598{,}960\) equally likely hands. A full house is three of one rank and two of another: choose the rank of the three (13 ways) and its suits (\(\binom{4}{3} = 4\)), then the rank of the pair (12 ways) and its suits (\(\binom{4}{2} = 6\)), for \(3{,}744\) hands and a probability of about 0.00144. A common mistake is to choose the two ranks together with \(\binom{13}{2}\), which forgets that the roles of the two ranks differ and undercounts by a factor of 2.

Two ways to count the same hands

Counting arguments are easy to get wrong, and the best check is to count the same set in two different ways. How many 5-card hands contain at least one card of every suit? Directly: one suit must appear twice and the other three once each. Choose the doubled suit (4 ways), its two cards (\(\binom{13}{2} = 78\)), and one card from each of the other suits (\(13^3 = 2197\)), giving \(4 \times 78 \times 2197 = 685{,}464\). By inclusion–exclusion on the complement: the hands missing at least one suit number \(4\binom{39}{5} - 6\binom{26}{5} + 4\binom{13}{5} = 2{,}303{,}028 - 394{,}680 + 5{,}148 = 1{,}913{,}496\), so the hands with all four suits number \(2{,}598{,}960 - 1{,}913{,}496 = 685{,}464\). The two methods agree, and the probability is about 0.264. When two independent arguments give the same number, double counting or a missed case is unlikely; when they disagree, a short enumeration by computer on a smaller deck usually locates the error.