# Probability and Combinatorics intuition behind matching birthday paradox

STATEMENT

Suppose that a room contains $$n$$ people. What is the probability that at least two of them have a common birthday?

Formula is $$P(A^c ) = 365 \times 364 \times· · · \times (365 − n + 1) \div 365^n$$

WHAT I WANT TO UNDERSTAND

I want to understand it practically. So if two people are there then of course there are 364 days that their B'Day won't match. Hence $$P(match) = 1 - \frac {364}{365}$$

Now if we have 3 people, our question remains the same, probability of 2 people's B'Day matching. Let's say P1, P2 and P3 are 3 such people. I know formula says just do $$P(A^c ) = 365 \times 364 \times 363 \div 365^3$$ but I want to know how it fits at a practical level.

Practically, P1 and P2 can match or P1 and P3 can match or P2 and P3 can match. So we have 3 matches to check. Now, we start matching with P1 and P2, then we get $$\frac {364}{365}$$ day of no match. For P1 and P3 , same $$\frac {364}{365}$$ days of no match and exactly same for P2 and P3. Then then the probability is $$P(A^c ) = 364 \times 364 \times 364 \div 365^3$$ which is not correct.

Can you tell me how my reasoning is wrong?

• @Arnuld If events are dependent, their complements are also dependent. Think about from counting perspective to convince yourself. Consider three people, and three days. Number of cases where none of the birthdays match is $3!$, and in total there are $3^3$ cases. So, it is $2/9$. But, in your logic, it would be $8/9$, which is wrong. – gunes May 12 at 19:08
• That went above my head. If there are 3 people and we need to see if 2 of them have matching birthdays, then answer simply is $3 \choose 2$ – Arnuld May 14 at 5:56
• @Arnuld Think about 3 people and a year with 3 days. The cases where none of the birthdays match are (1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1), where $i$-th entry of the tuple represents the day that $i$-th person was born. So, there are six cases. And, there are 27 cases in total. – gunes May 14 at 8:33