Calculating the probability of the 'common birthday problem' differently yields a different result?

Question

Everyone is calculating the birthday problem here by multiplying the probabilities of each person's birthday. Like the following "first oe has $365/365$ the second has $364/365$..... and so on..." . And this is the complementary of the probability so you take $1$ minus it.

This is fine from a probability point of view. But once you go to combinatorics I get confused.

The thing that bothers me is that the formula you get in the end is similar to the combinatorial formula of choosing $k$ from $n$ if order matters divided by all possible selections of $k$.

My problem is that the formula should be calculated the same but when order doesnt matter. That is, I want to choose $k$ days from a year of $365$ so I got ${365}\choose{k}$ all divided by $k+n-1 \choose k$ which is the formula for choosing $k$ from $n$ with repetitions allowed and order doesn't matter.

I don't understand why it does not yield the same result. Even though this seems to me to be the correct way to solve it. Because I dont care about order, all what matters is that I choose k different days out of the year which is the complementary of the probability.

Answer 1

Okay maybe the best way to treat this is to look at an easy example. Let's say each year has only two days $\{1,2\}$ and there are two people. What is the probability that they share the same birthday?

Let's look at the probability that they have birthdays on different days. Following the logic of the birthday problem we have that the answer is $1/2$. Easily we note that this is correct, i.e. let $a$ and $b$ denote the birthday dates of person $A$ and $B$ respectively, we have there following equally likely possibilities for the tuple $(a,b)$: $(1,1)$, $(1,2)$, $(2,1)$ and $(2,2)$. And only two of them show different values, hence the answer is $2/4=1/2$.

Now using your approach we have that ${2}\choose{2}$ $=1$, namely the case $\{a,b\}=\{1,2\}$, and the number of possibilities with repetition when order doesn't matter is $3$, i.e. "$(1,1)$", "$(1,2)$ or $(2,1)$" and "$(2,2)$". So the answer would be $1/3$, which is clearly wrong.

I feel like the problem here is that trying to divide by outcomes with repetition where order doesn't matter means implicitly assigning the same probability to outcomes like "$(1,1)$" and "$(1,2)$ or $(2,1)$", which is mistaken.

So the best approach here seems to be to take into account order.

Answer 2

The birthday probability can be written as:

$$\prod_{k=1}^{n-1}(1-k/365)=\frac{364!/(365-n)!}{365^{n-1}}=\frac{\binom{365}{n}}{365^{n}/n!}.$$

To use binomial coefficients, you can reason as follows. If you have $n$ people, you need to choose $n$ distinct birthdays, which can be done in $\binom{365}{n}$ ways. The total number of ways of picking birthdays, when order in which you pick the people doesn't matter, is $365^{n}/n!$.

Answer 3

The number of ways we can pick $k$ days from $365$ is, of course, $365 \choose k$.

The number of ways that $N$ people can have their birthdays distributed over $k$ days, allowing for repetition, ignoring order, and requiring at least one on each day is $N-1 \choose k-1$. This can be proven via induction on $k$.

The number of ways of ordering $N$ people, is, of course $N!$.

The number of ways $N$ people can have birthdays, counting different orders is $365^N$.

Thus, the probability that $N$ people have, between them, $k$ birthdays is:

$$p(k,N) = {{{365 \choose k} {N-1 \choose k-1} N! \over 365^N}} $$

For the case of $k=N$, this reduces to the known result.