생일 문제

개요

여러 사람이 모였을 때 이 사람들 중 생일이 같은 사람이 존재할 확률을 구하는 문제를 생일 문제(birthday problem)라고 한다.

풀이

편의상 1년은 항상 365일이라고 가정하자. \(n\)명의 생일이 모두 다를 확률을 [math]\displaystyle{ Q(n) }[/math]이라고 하자. 만약 [math]\displaystyle{ n\ge 366 }[/math]이면, 비둘기집의 원리에 의해 반드시 생일이 같은 두 명이 존재하므로 [math]\displaystyle{ Q(n)=0 }[/math]이다. [math]\displaystyle{ n\lt 366 }[/math]이라고 하자. 그러면 \(n\)명의 생일을 정하는 경우의 수는 [math]\displaystyle{ 365^n }[/math]이고, \(n\)명의 생일을 모두 다르게 배치하는 경우의 수는 [math]\displaystyle{ n!\binom{365}{n} }[/math]이므로, [math]\displaystyle{ Q(n)=\frac{n!\binom{365}{n}}{365^n} }[/math]이다. 따라서 \(n\)명 중 생일이 같은 한 쌍이 존재할 확률을 [math]\displaystyle{ P(n) }[/math]이라 하면

[math]\displaystyle{ P(n)=1-Q(n)=\begin{cases} 1,&\text{if }n\ge 366\\ 1-\frac{n!\binom{365}{n}}{365^n},&\text{if }n\lt 366 \end{cases} }[/math]

이다.