# Birthday problem: no unique birthday (all collide)

I have another variation of a birthday problem to solve. Given $n$ people and $m$ birthdays (let's keep in generic...), what would be the probability that none of the people has a unique birthday date? I've already run out of ways to approach the problem...

• As a further variant, the expected number of days with exactly one person having that birthday is $n\left(1-\frac1m\right)^{n-1}$ Nov 24 '17 at 10:45

The Inclusion-Exclusion principle gives a formula of sorts. Start with a basic $m^n$ possible sets of birthdays.
We want to subtract the number of ways Person1 has a unique birthday. He has one of $m$ birthdays, and everyone else must fit into $m-1$ days. That is $m(m-1)^{n-1}$ ways. In fact, subtract that $n$ times, because there are $n$ people who might have a unique birthday.
But if two people have unique birthdays. There are $m\choose2$ ways to choose the days and $n\choose2$ ways to choose the people. They match up in $2!$ ways. We subtracted that twice (once for A and once for B) and need to add it back in once.
If three people have unique birthdays, we have already subtracted three times (for A,B,C), added back in three times (for AB,AC,BC) and need to subtract off again.
In the end, it comes to $$\frac{m^n-mn(m-1)^{n-1}+2!{m\choose2}{n\choose2}(m-2)^{n-2}-3!{m\choose3}{n\choose3}(m-3)^{n-3}+...}{m^n}$$ EDIT: Here is an approximation for large $n$ and $m$.
The number of people with a given birthday is a Poisson variable with parameter $\lambda=n/m$, so the probability it is not $1$ is $1-\lambda e^{-\lambda}$. So the chance that no birthday is unique is $$\left(1-\frac nme^{-n/m}\right)^m$$ This goes from $0$ to $1$ when $ne^{-n/m}\approx1$, or $m\approx n/\ln n$

• The logic seems fine, but a short simulation or a toy example show that it is incorrect... $m=n=2$ comes up to 0.25, but in fact the probability that both collide is 0.5
– kck
Oct 15 '15 at 15:12
• Now it works! Thank you!
– kck
Oct 15 '15 at 15:15
• Ah. Firstly, the question of $0^0$. If you have no more people to fit into no more days, that should not affect the calculation, so I say $0^0=1$. But the other thing is that, having chosen the 2 people and 2 days, there is $2!$ ways to fill them. Oct 15 '15 at 15:18
• Thanks, Michael. A follow up question: what do you mean by "They match up in 2! ways."?
– kck
Oct 18 '15 at 16:42
• If the people are $A$ and $B$, and the birthdays are $1st$ and $3rd$, then either $A$'s is the first and $B$'s the third, or vice versa. Oct 18 '15 at 18:20