The formula
P(any match) = 1 − (365/365 × 364/365 × … × (365−n+1)/365)
Where it comes from
It is worked out through the complement because that is far easier: the probability that everyone has a different birthday is the product of knocking one day off for each person. What is left after subtracting from one is the probability of at least one match.
How to work it out by hand
- Work out the chance that everyone has different days: 365/365 × 364/365 × 363/365…
- Multiply as many factors as there are people
- Subtract the result from 1
What is worth knowing
It feels wrong because the brain compares everyone against oneself, and for that you do need around 253 people to reach 50 %. But the question is a different one: every possible pair is compared against every other, and a group of 23 holds 253 pairs. Hence the coincidence of figures, which is no coincidence at all. Cryptography uses it under the name birthday attack: it explains why an n-bit hash function falls to a collision in the order of 2^(n/2) attempts rather than 2^n.