# What's wrong with my solution for the birthday problem?

So what I decided to do is to start a small case with only 3 people. There are three possible combinations that I could pair up the people, using the symbols A, B, and C to represent the persons involved: A&B, A&C, B&C. The probability of each pair having the same birthday is $1\over365$ (the first guy gets any birthday, and the second guy only gets one birthday to choose from). What my intuition directed me to do next is to find the probability that any of the three events are true, or the union of the three events, which involved adding up the probabilities.

To put this generally, the equation for the probability SHOULD be:

${n \choose 2} \div 365$

However, clearly this is not the case since $n \choose 2$ gets over 365 when $n = 28$. And with 28 people, there is obviously still a chance that they all have different birthdays (Person 1 has Jan. 1, Person 2 has Jan. 2. ... Person 28 has Jan. 28). Could anyone tell me what's wrong with my intuition? I don't want to know what's the right solution, I just want to know what's wrong with my solution .. it makes sense to my intuition, even though it's incorrect.

-
"What my intuition directed me to do next is to find the probability that any of the three events are true, or the union of the three events, which involved adding up the probabilities." Here is were you went wrong. – Daniel Montealegre Mar 20 '12 at 6:51
He/she probably does not know about accepting answers. – fosho Jan 1 '13 at 19:11

You can only add probabilities if the events are mutually exclusive. But if A and B have the same birthday, it's possible that B and C also have the same birthday. No mutual exclusivity, no addition.

-

You need the inclusion-exclusion principle: in your example of three people you would need to subtract the probability of all three having the same birthday to avoid double counting that event.

So the probability that there is a shared birthday is $${3 \choose 2} \frac{1}{365} - {3 \choose 3} \left(\frac{1}{365}\right)^2$$

and this should be $1$ minus the probability there are no shared birthdays

$$1 - \left(\frac{365}{365}\right) \left(\frac{364}{365}\right) \left(\frac{363}{365}\right)$$

which it is.

This can be extended to larger numbers of people, but the first method gets complicated as there may be multiple shared birthdays. The second method is easier to extend.

-

Actually the inclusion-exclusion principle is more involved:

Let A=event that person 1 and person 2 share a birthday.

Let B=event that person 1 and person 3 share a birthday.

Let C=event that person 2 and person 3 share a birthday.

The probability of A or B or C= the probability that at least 2 people in a group of 3 people will have the same birthday (the same day of the year, not necessarily the same year, assuming 365 possible birth dates)=

$$P(A \cup B \cup C)= P(A)+P(B)+P(C)-P(A \cap B)-P(A \cap C)-P(B \cap C)+P(A \cap B \cap C)$$

$$P(A \cup B \cup C)= \frac{1}{365} + \frac{1}{365} + \frac{1}{365} - \frac{1}{365^2} - \frac{1}{365^2} - \frac{1}{365^2} + \frac{1}{365^2}$$ $$\frac{3}{365}-\frac{3}{365^2}+\frac{1}{365^2} = \frac{3}{365} - \frac{2}{365^2} = 0.008204166$$= $1−\frac{365}{365}*\frac{364}{365}*\frac{363}{365}=$ the probability that at least 2 people in a group of 3 people will have the same birthday (the same day of the year, not necessarily the same year, assuming 365 possible birth dates)

-