Birthday paradox question

Question

I am solving the question:

How large must a class be to make the probability of finding two people with the same birthday at least 50%?

The first solution I came up with is rather simple. It's based on finding $N$ people such that any pair amongst the $N$ people have different birthdays. This can be simply solved as multiplying probabilities of $N$ people have different birthdays. The first person has a probability of 1 of having a different birthday. The 2nd person has a probability of (364/365) of having a different birthday from the first person. The 3rd has a probability of (363/365) of having a different birthday from the first 2 people, and so on.

$$ \frac{365}{365}\frac{364}{365}\cdots\frac{365-N+1}{365} < \frac{1}{2} \\ = \frac{^{365} P_N}{365^N} $$ It turns out $N=23$. This is the correct answer based on what I saw on Google.

I'm now trying to think of this problem in terms of combinatorics. So I first started with thinking of 365 distinguishable objects into $N$ bins without replacement. Order doesn't matter, so this is combinations, and we get $\binom{365}{N}$. Now I want to find the number of combinations of 365 birthdays into $N$ bins WITH replacement, and this is simply $\frac{(365+N-1)!}{N!(365-1)!}$. So then I was thinking the probability of less than half of getting $N$ people with different birthdays is then

$$ \frac{\binom{365}{N}}{\frac{(365+N-1)!}{N!(365-1)!}} < \frac{1}{2} $$

But if I plug in $N=23$, I don't get the $\approx \frac{1}{2}$ that is expected. I get $\approx \frac{1}{4}$. What is wrong with my thinking using the combinations approach?

Answer 1

SHORT ANSWER: As @Ned said, the balls and bins should be distinguishable in your calculation.

LONG ANSWER:

First, recall that you should specify whether the balls are distinguishable and whether the bins are; in this case, both should be, because Eve being born on December 24 and Sam being born on July 4 is meaningfully different than having them switch birthdays. More to the point, consider the list of birthdays held by Eve and Sam; there should be twice as many ways for that list to be $\{\text{Dec 24}, \text{July 4}\}$ as for it to be $\{\text{Dec 24}\}$, which would require them both to have that same birthday. If you regard them as indistinguishable, then you're effectively regarding those two lists as being equally probable, when in reality they should not be.

A similar problem that may be easier to understand is: when you roll two dice, you are twice as likely to get a 2 and a 6 as you are to get double 6's. This comes from the fact that dice are distinguishable, and it's why that formula you applied doesn't work here.

The cardinal sin here is the confusion of whether "order" matters and what counts as "balls" and "bins". For the numerator, I don't think I see how you're thinking of distributing 365 balls into $N$ bins, because that would morally be like assigning every birthday to a person; instead, you should assign each person to a birthday, so you're distributing $N$ balls into $365$ bins (without replacement). But since the balls are people and are distinguishable, the order does matter, because the order corresponds to which person has which birthday. That is, having ball 1 go into the Dec 24 box and ball 2 go into the July 4 box is not the same thing as switching the two.

If you really want to go a route that has a combinatorial feel, I'd shy away from the balls / bins interpretation at all, because correctly applying that will lead you immediately back to permutations and a computation that looks like the correct approach you outlined originally. A combinatorial route would need to be weighted by how many times each term should appear -- i.e., correcting for the distinguishable / indistinguishable problem above -- and this will be much more laborious than it's worth.