Birthday Problem Confusion Using the Counting Rule

Question

I am stumped by the below confusion:
Question: How many people do we need in a class to make the probability that (at least) two people have the same birthday more than 1/2? (For simplicity, assume 365 days a year.)
I know that the answer to this question is $n=23$ people, but I was wondering why the following method does not work using the counting rule:
Out of $n$ people, choose any 2 people to share the same birthday. For that same birthday, there are 365 choices. For the other $n-2$ people, each one has 365 choices of birthdays. Therefore, the probability that at least two people have the same birthday is $$ \frac{\binom{n}{2} 365 \times 365^{n-2}}{365^n} = \binom{n}{2} \times \frac{1}{365} = 0.5 $$ which solving for gives us roughly $n=20$.
Where did I go wrong here? Thank you very much!

Answer 1

To elaborate on Joshua Wang's comment, your approach considers each possible pair of people, and correctly calculates the probability that they share a birthday to be $\frac{1}{365}$. However, when you sum over all pairs, you may be overcounting the number of possible situations where this occurs.

In particular, if three people $A,B,C$ all share the same birthday, then this situation is triple-counted: once for the pair $A,B$, once for the pair $B,C$ and once for the pair $A,C$.