A couple weeks back, I was seeing if I could solve the basic formulation of the Birthday Problem (i.e. assuming 365 equally likely birthdays, what's the probability that, given a room of ${n}$ people, at least one pair of people share a birthday). The initial solution that I used was to treat this as a binomial problem. There are $\binom {n} {2}$ ways to pick a pair out of a room of ${n}$ people, and the probability of those two people not sharing a birthday is $\frac{364}{365}$. Thus, the probability of having no pairs of people in the room with a shared birthday is $\left(\frac{364}{365}\right)^\binom{n}{2}$, assuming that the probability of two people sharing a birthday is independent of all other pairs sharing a birthday. Since we are interested in the probability of at least one pair of people, the final answer to the problem would be the complement of the above:
$$ 1 - \left(\frac{364}{365}\right)^\binom{n}{2}$$
In checking my work against the internet, I came across the accepted answer, which hinges on comparing each person in the room against anyone previously analyzed. So the second person has a $\frac{364}{365}$ chance of not colliding with the first birthday, the third person has a $\frac{363}{365}$ chance of not colliding with the first and second birthdays, and so on. Generalizing this comparison process to ${n}$ people, and then taking to complement probability, we get a final answer of:
$$ 1- \frac{\binom{365}{n} {n}!}{365^{n}}$$
My question: What is the initial solution above failing to take into account that makes it produce different results from the accepted answer? I can see that the equations we derive for any room size ${n}$ within both solutions are different, but conceptually where does the initial solution break down?
If I had to take a guess, I would say that the problem with my initial solution lies in "assuming that the probability of two people sharing a birthday is independent of all other pairs sharing a birthday," but I'm still struggling to grasp why that independence assumption is invalid...
Any help would be appreciated. Thanks!
P.S. In case my explanation of the two methods was unclear, both are detailed on the Birthday Problem Wikipedia page. What I termed the "accepted answer" is detailed in the section "Calculating the Probability", while my "initial solution" is under the section "A simple exponentiation."
