Birthday problem with at least 3 people

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?

• Think of it as $$P=1 - \sum_{k=0}^\frac n2 P(k,n)$$ where $P(k,n)$ is the probability of having $k$ pairs of people sharing the same birthday and the remaining $(n-2k)$ all having different birthdays – WW1 Nov 28 '17 at 4:07
• Let's $P(k)$ is the chance for exactly $k$ people have the same birthday. So $P(\ge3)=1-(P(2)+P(1)+P(0))$, $P(\ge3)$ means the chance for at least $3$ – Holo Nov 28 '17 at 5:01

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}$$

• When used to find $P(n,>1)$ and set greater than 0.5 this gives 613 rather than 23 as stated in the well-known 'paradox', this is because it find the probability of two or more people sharing a specific birth date (e.g. Jan the 1st) rather than any random date as in the paradox, although to be fair the question didn't specify either way. – Agnes Jan 27 '18 at 20:03
• What's the point of including $P(n, 0)$ in there? I would simply start counting from 1. – SlowerPhoton Nov 3 '18 at 9:43

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$.