# Why can't I calculate the result of the birthday paradox using n choose k?

The birthday paradox says, if you have 23 people in the same room, the odds are greater than half that two people will share a birthday. I tried to calculate it using 1 - (number of ways 23 people can have birthdays that are ALL DIFFERENT)/(number of ways 23 people can have birthdays).

Here's how 23 people can have birthdays that are all different: it is just 365 choose 23.

To calculate all the different ways 23 people can have birthdays is more complicated. In this case, order doesn't matter, but it is okay for multiple people to have the same birthdays. The formula for this is (n + k - 1) choose k, so in this case: (387 choose 23).

However, 1 - (365 choose 23) / (387 choose 23) = 75%, not 50%. What am I doing wrong?

• The various results in your denominator are not in fact equally likely to occur. It is much more likely to have the birthdays $Jan1,Jan2,Jan3,\dots,Jan23$ than it is to have all twenty three people have birthday on $Jan1$, yet you are implying with your calculations that these should have the same weight in your calculations. Number of favorable outcomes divided by total number of outcomes is only valid in equiprobable situations. – JMoravitz Nov 13 '16 at 6:44
• This may be useful.math.stackexchange.com/questions/1020490/… – Tyler Nov 13 '16 at 7:17

The formula for this is ${n + k - 1 \choose k}$,

Okay, no.   The "stars and bars" formula counts the distinct arrangements by which $k$ indistinguishable items may be assigned to $n$ distinguishable items (eg balls in boxes).   It does not, however, consider the probability weighting of those outcomes, and they are not all equally probable.

For instance, counting by "stars and bars" the ways two balls may be fairly dropped into two boxes labelled $\sf H, T$, gives $3$ ways:   "$\sf HH, HT, TT$", but you should be quite aware that the probability weights of these are $\tfrac 14, \tfrac 24, \tfrac 14$ respectively.

Although it has its uses, don't be tempted to use "stars and bars" in to measure probability as it does not count equally probable outcomes.

First, the total number of ways is $365^{23}$, because each person can have a birthday on any day.

Second, your complementary calculation is also wrong. The number of combinations $23$ people don't share a birthday is $365\times364\times\cdots\times343$. So the probability becomes $$1-\frac{365\times364\times\cdots\times343}{365^{23}}\approx 1-0.492702765676015=0.507297234323985$$

• ...and the assumption in the birthday problem IS each day is equally likely to be a birthday. – msm Nov 13 '16 at 7:06