Birthday problem: why not: combinations without/with replacement??

Question

My first intuition on the birthday problem was:

• The number of ways $k$ people have different birthdays is the combinations $\binom{365}{k}$

• The number of ways $k$ people can have birthdays is the combinations with replacement.

So the probability that all $k$ people have birthdays on different days is

$$ P = \frac{\binom{365}{k}}{\binom{365+k-1}{k}}$$

What is wrong with this logic?

Answer 1

You're considering as the sample space the set of all combinations with replacement of $k$ picks from the $365$ days. Why is your calculation wrong? Because $$P(A)=\frac{\#A}{\#\Omega}$$ is only valid when the sample space $\#\Omega$ is equiprobable, and this one is not.

This is because you're considering combinations instead of variations. For instance, take $k=2$: the case in which everybody (that is, both people) have it's birthday on January 1st only happens with probability $$\left(\frac1{365}\right)\cdot \left(\frac1{365}\right),$$ while the case when one person does so and the other on January 2nd has probability $$\left(\frac1{365}\right)\cdot \left(\frac1{365}\right)+\left(\frac1{365}\right)\cdot \left(\frac1{365}\right),$$ since it can be the case that one person (say person A) has it's birthday on the 1st and person B on the 2nd, or person A on the 2nd and person B on the first. Any of these correspond to the result ''one person has birthday on 1/1 and the other on the 2/1'.

To have an equiprobable space you should take as different situations that one in which 'A' has birthday on 1/1 and 'B'on 2/1 and that one in which 'A' has birthday on 2/1 and 'B'on 1/1.

Answer 2

The calculation $\binom{365}{k}$ only chooses $k$ days; it does not assign particular days to the people. So your first statement is incorrect. I am not sure where your second formula comes from, but you're probably making a similar error.