How many ways: factorials and the birthday problem
Tonight's idea
Multiply the choices. Four shirts and three pairs of trousers make \(4 \times 3 = 12\) outfits, because each shirt goes with each pair. Add two pairs of shoes and it is \(4 \times 3 \times 2 = 24\). Whenever choices are made one after another and do not interfere, the number of combinations is the product.
Arrangements. In how many orders can five books stand on a shelf? Five choices for the first slot, then four left for the second, three, two, one: \(5 \times 4 \times 3 \times 2 \times 1 = 120\). This product has a name, five factorial, written \(5!\). In general \(n!\) is the number of ways to put \(n\) different things in a row.
Factorials grow absurdly fast. \(10! = 3{,}628{,}800\). \(20!\) is about \(2 \times 10^{18}\). And \(52!\), the number of orders for a deck of cards, is about \(8 \times 10^{67}\). That is more than the number of seconds since the Big Bang times the number of atoms in the Earth, so a well-shuffled deck is almost certainly an order nobody has ever held.
Choosing without order is different: picking 2 books from 5 to take on holiday is \(\binom{5}{2} = 10\) (said "five choose two"), the Pascal's triangle number, because the order you pick them in does not matter. Arranging cares about order. Choosing does not.
Watch one: the birthday problem
How likely is it that in a group of 23 people, at least two share a birthday? Counting the ways it can happen is a nightmare. Counting the ways it cannot is easy, so do that and subtract from 1.
Line the people up. The first can have any birthday: \(\tfrac{365}{365}\). The second must avoid one day: \(\tfrac{364}{365}\). The third must avoid two: \(\tfrac{363}{365}\). Keep going to the 23rd person, who must avoid 22 days: \(\tfrac{343}{365}\). Multiply all 23 fractions together and you get \(0.493\). That is the chance of no shared birthday. So the chance of at least one match is \(1 - 0.493 = 0.507\), just over a half.
| people | 10 | 23 | 30 | 50 |
|---|---|---|---|---|
| chance of a match | 11.7% | 50.7% | 70.6% | 97.0% |
Why so few? Because what matters is not the number of people but the number of pairs, and 23 people make \(\binom{23}{2} = 253\) pairs, each with a 1 in 365 chance.
Your turn
- A café offers 3 breads, 4 fillings and 2 sauces. How many different sandwiches? If they add a fifth filling, how many more sandwiches does that create?
- How many ways can 6 friends line up for a photo? How many if the two tallest insist on standing at the two ends? (The two tallest can swap ends, so count both ways.)
- A 4-digit PIN uses digits 0 to 9. How many PINs are there? How many have no repeated digit? What fraction of all PINs is that?
- Six people sit around a round table. Two seatings count as the same if everyone has the same left and right neighbours (so rotating the whole table changes nothing). Explain why the answer is \(5!\) and not \(6!\).
- Five people in a room. Compute the chance that they all have different birthdays, as a product of five fractions, to the nearest percent. (Use a calculator.) So what is the chance of a match?
- How many pairs of people are there in a room of 10? Of 23? Of 50? Use this to explain in a sentence why the table in the example climbs so quickly.
Stretch: 99% sure
How many people do you need before a shared birthday is 99% likely? Keep multiplying fractions (a spreadsheet helps) until the no-match product drops below 0.01.
Most people, asked this cold, say something like 183, half of 365. What reasoning leads to 183, and why is it wrong even for the easier question of someone sharing your birthday? (Hint: with 183 other people, is it really a coin flip that one of them matches you? Try the no-match product \((364/365)^{183}\).) Then find how many people are needed for a 50% chance that someone shares your birthday, and notice how different it is from 23.
Answers
- \(3 \times 4 \times 2 = 24\). With five fillings, \(3 \times 5 \times 2 = 30\), so 6 more.
- \(6! = 720\). With the tallest two fixed at the ends: 2 ways to place them, then \(4! = 24\) ways for the middle, total 48.
- \(10^4 = 10{,}000\) PINs. No repeats: \(10 \times 9 \times 8 \times 7 = 5{,}040\). That is \(50.4\%\), just over half.
- Sit the first person anywhere; rotating the table makes every seat the same for them, so that choice does not count. The remaining five fill the other seats in order: \(5! = 120\). Equivalently, \(6!\) counts each arrangement 6 times, once per rotation, and \(720 / 6 = 120\).
- \(\tfrac{365}{365} \times \tfrac{364}{365} \times \tfrac{363}{365} \times \tfrac{362}{365} \times \tfrac{361}{365} \approx 0.973\), so about 97% all different and about 3% chance of a match.
- \(\binom{10}{2} = 45\), \(\binom{23}{2} = 253\), \(\binom{50}{2} = 1{,}225\). Pairs grow roughly with the square of the number of people, and each pair is a fresh chance at a match, so the probability climbs much faster than the headcount.
Stretch. 57 people: the no-match product is about 0.0099, so a match is 99.0% likely. (56 people gives 98.8%.) The guess of 183 comes from thinking “half the days, so half a chance”: 183 people, each a 1 in 365 shot at your birthday, feels like 183/365, about one half. But chances do not add like that, because two people can both miss, and both can hit the same day. The no-match probability is \((364/365)^{183} \approx 0.605\), so 183 people give you only about a 39% chance of a match with your birthday. The no-match product drops below one half at \(n = 253\) (252 people give 49.9%, 253 give 50.05%). Matching a fixed date is hard; matching any pair is easy, because there are so many pairs.