\documentclass[11pt,reqno]{amsart}
\usepackage[charter]{mathdesign}

\begin{document}

\title{Birthday Problem}
\author{Melikamp}
\date{December 2008}
\maketitle
\thispagestyle{empty}

The problem can be stated as follows. In a group of $n$ people whose
birth dates are distributed randomly, independently and uniformly,
what is the probability of the event $B_n$ that at least $2$ people will
have the same birth date? To approach this question, we notice that if
$A_n$ is the event ``no $2$ people have the same birth date'', then $A_n$
and $B_n$ are complimentary events and $P(B_n) = 1 - P(A_n)$. For
simplicity, we will assume that there are always $365$ days in a year.

By the classical approach to probability, $P(A_n)$ is the ratio of the
number of favorable outcomes to the total number of outcomes.  For a
fixed number $n$ of people in our group, the total number of ways to
assign birthdays is $365^n$. On the other hand, the number of ways to
assign birthdays without collision is
$365\cdot364\cdot\ldots\cdot(365-n+1)$ (by the basic principle of
counting). It follows that
\[P(A_n) = \frac{365\cdot364\cdot\ldots\cdot(365-n+1)}{365^n}
= \frac{365!}{365^n(365-n)!},\]
and therefore
\[P(B_n) = 1 - \frac{365!}{365^n(365-n)!}.\]
Following is the table with probabilities of $B_n$ for a few selected
$n$.

\bigskip
\begin{center}
  \begin{tabular}{|c|c|c|c|c|c|c|}
    \hline $n$ & 1 & 2 & 3 & 4 & 5 & 10\\
    \hline $P(B_n)$, $\%$ & $0.00$ & $0.27$ & $0.82$ &
    $1.64$ & $2.71$ & $11.69$\\
    \hline\hline $n$ & 15 & 20 & 30 & 40 & 50 & 100\\
    \hline $P(B_n)$, $\%$ & $25.29$ & $41.14$
    & $70.63$ & $89.12$ & $97.04$ & 99.99\\
    \hline
  \end{tabular}
\end{center}

\bigskip
To summarize, the chances are pretty good ($4:6$) that in a group as
small as 20 people there will be a collision.

For the reference, here is some code in Lisp to compute
$P(B_n)$. It was tested in Emacs and Common Lisp.
\bigskip
\footnotesize
\begin{verbatim}
(defun birthday (n)
  (if (eq n 1) 1 (* (/ (+ 365.0 (- n) 1) 365.0) (birthday (- n 1)))))
(defun nbday (n)
  (- 1 (birthday n)))
\end{verbatim}
\normalsize

\end{document}