Counting

How many people must be in a room before two of them probably share a birthday? Guess, then watch the room fill.

Counting pairs

Most people guess far too high. The answer is 23: in a room of 23 people, a shared birthday is slightly more likely than not, with a chance of 0.507.

The usual mistake is to think about your own birthday: how many people would it take for someone to share mine? That needs a lot of people. But the question is about any two people in the room, and that is a question about pairs.

Watch the lines in the room. With 23 people, each person can pair with 22 others. That counts every pair twice, once from each end, so there are

pairs. Each of them is a chance for a shared birthday.

After the clip, drag the number of people and watch the pairs readout. Double the people and the pairs roughly quadruple: 10 people make 45 pairs, 20 make 190, 40 make 780.

To get the exact chance, I need to count carefully. That takes two tools.

The multiplication rule

A bike lock has 4 dials, and you set a code with 4 different digits, 0 to 9. How many codes are there? The first digit can be any of 10. Whatever it was, the second can be any of the 9 left, then 8, then 7:

This is the multiplication rule: when a choice is made in steps, and each step has the same number of options whatever came before, multiply the numbers of options.

Arranging all $n$ things of a set in a row gives $n\times(n-1)\times\dots\times2\times1$ orders. This product is written $n!$ and read ”$n$ factorial”; $3!=6$ and $4!=24$. By agreement $0!=1$.

Arranging only $k$ of the $n$ things, in order, stops the product after $k$ steps:

The lock’s codes are $10!/6!=5040$.

Order, or no order

Now choose a committee of 3 people from 8. A committee has no first or second member: Ana, Ben, Cai is the same committee as Cai, Ana, Ben.

Count in order first: $8\times7\times6=336$ ordered lists. Each committee of 3 shows up in $3!=6$ of them, once for each order of its members. So the number of committees is $336/6=56$.

The number of ways to choose $k$ things from $n$, when order does not matter, is the binomial coefficient, read ”$n$ choose $k$”:

The $(n-k)!$ stops the ordered count after $k$ steps, and the $k!$ removes the orders.

There is a second way to build these numbers. Pick one of the $n$ people, say Ana. Every committee of $k$ either includes Ana, and then picks $k-1$ more from the other $n-1$, or it leaves Ana out and picks all $k$ from the other $n-1$:

Write the numbers in rows, row $n$ holding $\binom{n}{0}$ to $\binom{n}{n}$, and each number is the sum of the two above it. This is Pascal’s triangle.

The birthday product

Back to the room. I assume every person’s birthday is one of 365 days, each as likely as the others, and that nobody’s birthday depends on anyone else’s. So I ignore 29 February and twins.

Line the $k$ people up and write down their birthdays in order. By the multiplication rule there are $365^k$ such lists, all equally likely. In how many do all the birthdays differ? The first person can have any of 365 days, the second any of the other 364, and so on:

The chance that no two of the $k$ people share a birthday is the share of lists with all birthdays different:

The symbol $\prod$ means “multiply together”, as $\sum$ means “add together”. By the complement rule of What probability measures, the chance of at least one shared birthday is $1-\Pr\{\text{no match}\}$.

For 23 people this is 0.507, and for 22 it is 0.476. So 23 is the smallest room where a shared birthday is more likely than not.

A check with pairs. Each of the 253 pairs shares a birthday with chance $1/365$. So over many rooms of 23, there are on average $253/365=0.69$ shared pairs per room, close to one. If the pairs could not affect each other, the chance that none of them matched would be $(364/365)^{253}=0.4995$, a match chance of $0.5005$. That is close to the exact 0.507; the pairs share people, so they are not quite separate.

Worked example

1. Codes. A code of 4 different digits: $10\times9\times8\times7=5040$ codes. Allow repeated digits and every dial has 10 options: $10^4=10\,000$ codes.

2. A lottery. Choose 6 numbers from 1 to 49; the order of the draw does not matter.

One ticket wins with chance $1/13\,983\,816=7.15\times10^{-8}$, about one in 14 million.

3. Rooms of different sizes. The birthday product, worked out for a few rooms:

With 57 people a shared birthday is 99 % likely. It becomes certain only at 366 people: with 366 people and 365 days, two must share.

Try it yourself. A poker hand is 5 cards from 52, with order not mattering. There are $\binom{52}{5}=2\,598\,960$ hands.

Where you’ll meet this

Hash collisions. A computer often files items by a short code computed from each one, a hash. A 32-bit hash has $2^{32}$, about 4.3 billion, possible codes. By the same count as for birthdays, two items are more likely than not to share a code after only about 77 000 items. Programs that rely on hashes are designed for that, not for the 4.3 billion.

The rule of thumb behind this works for any number of codes: a shared code becomes likely once the number of pairs reaches about 0.693 times (that is, $\ln 2$ times) the number of codes. For birthdays that is $0.69\times365=253$ pairs, 23 people.

Lotteries, codes and passwords. The size of a lottery, a PIN or a password space is a count by the multiplication rule or a binomial coefficient. Each extra character multiplies the number of passwords an attacker must try.

Choosing teams and samples. The number of ways to pick a team, a jury or a survey sample is a binomial coefficient. It returns in Discrete random variables, where it counts the ways to get $k$ heads in $n$ flips.

Reference card