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.

up vote 3 down vote accepted

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$

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.