Birthday problem with at least 3 people

Question

Question: whats the probability that at least 3 out of a group of n people have the same birthday.

I am confused as to where to start. I know that it would be complementary probability, but even then I dont know exactly. Would it be;

P(at least 3 have the same bday) = 1 - (|all 3 have different| + (2 have the same|)? Any directions and suggestions?

Answer 1

If $P(n,k)$ is the probability for exactly $k$ people out of $n$ have the same birthday and $P(n,\ge t)$ is the probability for at least $t$ people out of $n$ have the same birthday then:

$P(n, \ge3)=P(n,3)+P(n,4)+\cdots+P(n,n)=\sum\limits_{i=3}^n P(n,i)=1-\left(\sum\limits_{j=0}^2 P(n,j)\right)=1-(P(n,2)+P(n,1)+P(n,0))$

Now to get $P(n,k)$ we have $$P(n,k)={n\choose k}\cdot\left(\frac1{365}\right)^k\cdot\left(1-\frac1{365}\right)^{n-k}$$

Answer 2

Consider the complementary event, i.e. there is no group of three or more people with the same birthday. Then there can only be pairs of people (possibly zero pairs) with the same birthday; let's say there are exactly $i$ pairs of people with the same birthday, where $ 0 \le i \le \lfloor n/2 \rfloor$. If we consider the people as numbered from $1$ to $n$, then their birthdays form a sequence of $n$ integers in the range $1$ to $365$, so there are $365^n$ such sequences, all of which we assume are equally likely.

If exactly $i$ pairs have the same birthday, then there are $\binom{365}{i}$ ways to pick their birthdays and $\binom{365-i}{n-2i}$ ways to pick the birthdays of the remaining people. The collection of birthdays can then be arranged in $n!/2^i$ ways. So in all, there are $$\binom{365}{i} \binom{365-i}{n-2i} \frac{n!}{2^i}$$ sequences of birthdays possible in which $i$ pairs of people have the same birthday, for $i = 0,1, 2, \dots , \lfloor n/2 \rfloor$.

Therefore the probability that there is no group of three or more people with the same birthday is $$p = \frac{1}{365^n}\sum_{i=0}^{\lfloor n/2 \rfloor}\binom{365}{i} \binom{365-i}{n-2i} \frac{n!}{2^i}$$ and the probability that at least three people have the same birthday is $1-p$.