# Birthday problem (combinatorics), without using inverse solution

There is that classic question about how many people in a room is required so that at least one pair of people share a birthday, with > 50% probability, the answer is 23. The standard textbook solution is to solve it using:

$$\mathbb{P}\left(\text{At least one shared birthday}\right) = 1 - \mathbb{P}\left(\text{zero shared birthdays}\right)$$

Since the probability of zero shared birthdays is easier to calculate/derive. From what I know, this is calculated as the series:

$$\mathbb{P}\left(\text{zero shared birthdays}\right)=\frac{365-1}{365}\times\frac{365-2}{365}\times\ldots\times\frac{365-22}{365}$$

the above makes sense, because for each successive person in the group, they can't share any birthday with any previous person, so the number of available days diminishes by 1 each time.

However, I am really struggling to derive $$\mathbb{P}\left(\text{At least one shared birthday}\right)$$, without using the inverse. Some sort of recursion/series is the way to go, something like:

$$\mathbb{P}\left(\text{23 people share at least 1 birthday}\right)=x+\mathbb{P}\left(\text{22 people share at least 1 birthday}\right)$$

I believe the base cases are: $$\mathbb{P}\left(\text{1 person share a birthday}\right)=0$$ $$\mathbb{P}\left(\text{2 person share a birthday}\right)=1/365$$

Can someone help me derive it, perhaps by spelling out the series?

Indeed, just take $$p_1=0\quad \quad p_n=p_{n-1}+\frac {n-1}{365}\times (1-p_{n-1})$$

The logic being: in order to have at least one pair with $$n$$ people, you must either have a pair with the first $$n-1$$ of them, or you must have no pair with the first $$n-1$$ but the $$n^{th}$$ person must match one of the prior $$n-1$$ birthdays. And of course these two events are mutually exclusive.

• pretty intense, I think it makes sense Nov 1, 2020 at 23:50
• correct answer, but I guess I don't quite understand how the OR here gets rid of the extra intersection of the 2 events? usually there's a subtraction component in the formula, aka P(A or B) = P(A) + P(B) - P(A and B) Nov 2, 2020 at 0:02
• @AlexanderMills There is no intersection, since my second event presupposes that the first does not occur.
– lulu
Nov 2, 2020 at 0:03
• Be sure you are clear on the meaning of my two events. My first event is "there is at least one match amongst the first $n-1$ people". My second event is "there is no match amongst the first $n-1$ people but the $n^{th}$ person matches one of the first $n-1$". Those events are clearly mutually exclusive.
– lulu
Nov 2, 2020 at 0:05
• @AlexanderMills No. Say $A=B$, and that neither $P(A)$ nor $P(A^c)=0$.
– lulu
Nov 2, 2020 at 0:15