# a slightly different birthday problem

Suppose we have a room with $n$ people. What is the probability that the birthdays of the people in the room cover all the days of the year? Let's assume that there are $k$ days in a year and that the probability of being born is equally likely on all days.

Line up the people in order of student number, and record their birthdays. There are $k^n$ possible sequences of answers. If birthdays are independent, then by our assumption the $k^n$ sequences are all equally likely.

We now count the favourables, where all days occur at least once. This is $0$ if $n\lt k$. so we assume that $n\ge k$.

The number of favourables, essentially by definition, is $k!S(n,k)$, where $S(n,k)$ is a Stirling number of the second kind. There is no closed form for $S(n,k)$, but there are useful recurrences.

Finally, our probability is $\dfrac{k!S(n,k)}{k^n}$.

• Could you perhaps provide a proof? It doesn't occur obvious to me that $k!S(n,k)$ is the number of favorable occurrences. – Vincent Warmerdam Dec 30 '15 at 21:37
• That is why I gave the reference. $S(n,k)$ is by definition the number of ways to divide a set of $n$ distinct elements into $k$ non-empty parts. If the parts are to be labelled with the days $1$ to $k$ of the year, then any division into $k$ non-empty parts gives rise to $k!$ divisions into labelled non-empty parts. Hence the number of divisions into $k$ labelled non-empty parts is $k!S(n,k)$. There is an inclusion/exclusion formula for $S(n,k)$ early in the article (not useful for large $k$) and there are recurrences later. – André Nicolas Dec 30 '15 at 21:48

Let S be the set of all assignments of birthdays to the n people, and

let $A_i$ be the set of assignments for which day $i$ is not represented, for $1\le i\le k$.

Then the number of assignments for which every day is represented is given by

$\displaystyle\big|\overline{A}_1\cap\cdots\cap \overline{A}_k\big|=|S|-\sum_i\big|A_i\big|+\sum_{i<j}\big|A_i\cap A_j\big|-\sum_{i<j<k}\big|A_i\cap A_j\cap A_k\big|+\cdots$

$\:\;\;\displaystyle =k^n-\binom{k}{1}(k-1)^n+\binom{k}{2}(k-2)^n-\binom{k}{3}(k-3)^n+\cdots+(-1)^{k-1}\binom{k}{k-1}1^n$,

so the probability that every day is represented as a birthday is equal to

$\:\;\;\displaystyle\frac{k^n-\binom{k}{1}(k-1)^n+\binom{k}{2}(k-2)^n-\binom{k}{3}(k-3)^n+\cdots+(-1)^{k-1}\binom{k}{k-1}1^n}{k^n}$

$\displaystyle=1-\binom{k}{1}\big(1-\frac{1}{k}\big)^n+\binom{k}{2}\big(1-\frac{2}{k}\big)^n-\binom{k}{3}\big(1-\frac{3}{k}\big)^n+\cdots+(-1)^{k-1}\binom{k}{k-1}\big(1-\frac{k-1}{k}\big)^n$