# Birthday Problem in Probability

What is the probability that in a group of $n$ people, every month of the year has at least one birthday.

This is my approach:

We have 12 months, and the probability that a month has at least one birthday =$1-(11/12)^n$.

And to find the probability that every month has at least 1 birthday I am trying to use the inclusion exclusion formula. But I am not able to proceed for the probability that there is at least one birthday for each of 2 months. Is my approach correct?

• Are you assuming that months have equal lengh? – 5xum Oct 4 '16 at 11:24
• yes, I am assuming that all months have equal days – anil jack Oct 4 '16 at 11:25
• Have you done the question specifically for $n = 11, 12$ and $13$? That might give you insight into how to do it generally. – Arthur Oct 4 '16 at 11:26
• For n=13 is this the right answer? (12c1)*(13c2)*(11!)/(12)^13. That is i am selecting one month which will have 2 birthdays and then selecting two people out of 13 for that month and remaining 11 people in 11! ways – anil jack Oct 4 '16 at 11:33
• Duplicate of (math.stackexchange.com/q/141655) – Jean Marie Oct 4 '16 at 12:50

The probability that $n$ people miss $k$ months is $N_n(k)=\binom{12}{k}\left(\frac{12-k}{12}\right)^n$. Therefore, by Inclusion-Exclusion, the probability of missing at least one month is $$\sum_{k=1}^{12}(-1)^{k-1}\binom{12}{k}\left(\frac{12-k}{12}\right)^n\tag{1}$$ Therefore, the probability of getting all months is $$\bbox[5px,border:2px solid #C0A000]{\sum_{k=0}^{12}(-1)^k\binom{12}{k}\left(\frac{12-k}{12}\right)^n}\tag{2}$$
We can simplify $(2)$ using Stirling Numbers of the Second Kind \newcommand{\stirtwo}[2]{\left\{{#1}\atop{#2}\right\}} \begin{align} \sum_{k=0}^{12}(-1)^k\binom{12}{k}\left(\frac{12-k}{12}\right)^n &=\frac1{12^n}\sum_{k=0}^{12}(-1)^k\binom{12}{k}\,k^n\tag{3}\\ &=\frac1{12^n}\sum_{k=0}^{12}(-1)^k\binom{12}{k}\sum_{j=0}^n\binom{k}{j}\stirtwo{n}{j}j!\tag{4}\\ &=\frac1{12^n}\sum_{j=0}^n\sum_{k=0}^{12}(-1)^k\binom{12}{j}\binom{12-j}{k-j}\stirtwo{n}{j}j!\tag{5}\\ &=\frac1{12^n}\sum_{j=0}^n[j=12]\binom{12}{j}\stirtwo{n}{j}j!\tag{6}\\ &=\bbox[5px,border:2px solid #C0A000]{\frac{12!}{12^n}\stirtwo{n}{12}}\tag{7} \end{align} Explanation:
$(3)$: substitute $k\mapsto12-k$
$(4)$: $k^n=\sum\limits_{j=0}^n\binom{k}{j}\stirtwo{n}{j}j!$
$(5)$: $\binom{12}{k}\binom{k}{j}=\binom{12}{j}\binom{12-j}{k-j}$
$(6)$: $\sum\limits_{k=0}^{12}(-1)^k\binom{12-j}{k-j}=[j=12]$ using Iverson Brackets
$(7)$: evaluate the sum (set $j=12$)