Recipe

Compute a birthday-collision probability

Use when: you're asked for the probability that at least two people (or items) out of $n$ share a birthday, or land in the same one of $D$ equally likely categories

Goal: the exact collision probability, built by first computing the NO-collision product and then subtracting it from 1

Taught in The birthday problem

Quick recipe

Identify n and the number of categories D
Build the no-collision product, one factor per additional person
Subtract from 1 to get the collision probability
Sanity-check against the naive pairs estimate, but don't trust it as exact

1
Read off the group size $n$ and the number of equally likely categories $D$ (365 for an ordinary birthday problem, unless the problem states otherwise, such as a different-sized hash space).

Example

A group of $n=40$ people, ordinary birthdays: $D=365$ .

Why: every later step's formula depends on having the right $D$ ; using 365 for a problem that specifies a different category count is a common source of a wrong final answer.
2
Compute $\prod_{i=0}^{n-1}\frac{D-i}{D}$ : the first person contributes a factor of $D/D=1$ (unconstrained), the second $(D-1)/D$ (must miss the first day already taken), the third $(D-2)/D$ , and so on down to the $n$ th person's factor of $(D-n+1)/D$ .

Example

$n=40$ , $D=365$ : $\frac{365}{365}\cdot\frac{364}{365}\cdot\frac{363}{365}\cdots\frac{326}{365} \approx 0.1088$ .

⚡ Shortcut

For a fast estimate without multiplying out all $n$ terms by hand, $P(\text{collision}) \approx 1-e^{-\binom{n}{2}/D}$ tracks the true product closely (within about a percentage point for moderate $n$ ), since it approximates the same falling-product behavior with an exponential. For $n=40$ , $D=365$ : $\binom{40}{2}=780$ , giving $1-e^{-780/365} \approx 0.882$ , close to the exact $0.891$ from Step 3 below. Treat it as a quick sanity check, not a replacement for the exact product.

Why: each factor is the conditional probability that the next person's birthday misses every day already claimed by the people before them, and independence lets these conditional probabilities multiply straight through.
3
Subtract the Step 2 product from 1.

Example

$1-0.1088 \approx 0.8912$ , about $89.1\%$ .

Why: "no collision" and "at least one collision" are complementary events that must add to 1, and the complement is far easier to compute directly than counting every way a collision could occur.
4
Compare $\binom{n}{2}/D$ to the Step 3 answer.

Example

$n=40$ : $\binom{40}{2}/365 = 780/365 \approx 2.14$ , not even a valid probability (it exceeds 1), while Step 3's exact answer is $\approx 0.891$ : a clear sign the naive sum has badly overestimated.
- the naive estimate is reasonably close to Step 3's answer (small $n$ relative to $D$ ) — it's a fine order-of-magnitude sanity check.
- the naive estimate diverges noticeably from Step 3's answer (larger $n$ , more pairs) — trust Step 3's exact product; the naive sum double-counts overlapping ways several pairs can collide at once and overestimates.
Why: summing each pair's own small collision probability ignores that those events aren't mutually exclusive, so the sum overcounts as soon as multiple pairs can plausibly collide at once.

Common mistakes

Using $n$ (the number of people) in the denominator instead of $D$ (the number of categories) when estimating roughly.
Comparing $n$ directly to $D$ instead of comparing the number of PAIRS, $\binom{n}{2}$ , to $D$ .
Stopping at the no-collision product from Step 2 and forgetting to subtract it from 1.
Trusting the naive pairs estimate from Step 4 as if it were exact, especially once it produces a number that isn't even a valid probability.