Birthday problem: why not: combinations without/with replacement?? 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?

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. 
