The Birthday Problem and Combinatorics

Walk into a room of 23 people. The chance that at least two of them share a birthday is just over 50%. With 30 people, it rises to 70%. With 57 people, it clears 99%. Nearly every student who hears this for the first time thinks the numbers must be wrong. They aren't, and understanding why is a clean introduction to combinatorial probability.

Why the Naive Estimate Fails

The instinct is to frame the problem like this: pick one person, and ask what is the chance that somebody else in the room matches their birthday. With 22 other people, each with a 1/365 chance of matching, you might expect the probability to be around 22/365, which is about 6%. That is nowhere near 50%, so the result seems impossible.

But this framing is wrong. You are not asking whether anyone matches one specific person. You are asking whether any two people in the room match each other, which is a much larger set of comparisons. With 23 people, the number of possible pairs is 23 x 22 / 2, which equals 253. Each of those pairs has a chance of sharing a birthday. That is a very different calculation.

The Complement Trick

Direct calculation is messy. The clean approach is to calculate the probability that no two people share a birthday, then subtract from 1.

The first person can have any birthday: probability 365/365. The second person must have a different birthday to avoid a match: probability 364/365. The third must avoid both existing birthdays: 363/365. Continue through 23 people.

Multiply all of these together:

P(no match) = (365/365) x (364/365) x (363/365) x ... x (343/365)

Work this out and you get approximately 0.493. So the probability of at least one match is 1 - 0.493 = 0.507, just over 50%.

What the Math Is Actually Saying

Each new person who enters the room adds comparisons not just with one existing person but with every existing person. The third person adds 2 new pairs. The tenth adds 9 new pairs. The 23rd adds 22 new pairs. The total number of pairs grows with the square of the number of people, while the chance of any one pair matching stays constant at 1/365.

This is why the result accumulates so fast. The number of opportunities for a match grows quadratically while your intuition is scaling linearly. Whenever you see probability results that feel impossibly large or small, ask whether the number of relevant comparisons is growing faster than you assumed.

The Generalized Version

The birthday problem is a special case of the collision problem: given n items drawn with replacement from a space of size d, how many draws before a repeat becomes likely? The answer is roughly the square root of d. For birthdays, the square root of 365 is about 19, which is close to the actual answer of 23.

This square root approximation shows up in cryptography, hashing algorithms, and DNA forensics. In each case, the question is how large a sample you need before two items from the same population are likely to collide. The birthday problem gives you the intuition for why the answer is always much smaller than the size of the space.