Birthday problem, want about using unordered counting?

Question

Given there are 365 days in a year and $n$ people, the probability that at least two people have the same birthday is given by $$\frac{365^n - 365 \cdot 364 \cdots (365-n+1)}{365^n}.$$ In this calculation, we treat the $n$ birthdays we selected as a sequence where their order matters.

If we think the $n$ dates that randomly selected as a set where the order does not matter, I believe we would have the probability $$\frac{{365+n-1 \choose n} - {365\choose n}}{{365+n-1 \choose n}}.$$

• For the total number of outcomes, we model by throwing $n$ balls uniformly randomly into $365$ boxes. Essentially, there are $n$ balls and $365-1$ walls (between the boxes). For example $$ \circ |\;\;\; |\;\;\;|\circ \circ |\;\;\;|\circ |\cdots |$$ would mean one person was born on day $1$, two people were born on day $4$, one person was born on day $6$, and so on. This is how I came up with the ${365+n-1\choose n}$.

• For the case that everyone has a distinct birthday, it would be ${365 \choose n}$.

What is wrong with this approach?

Answer 1

When you have an event $E$ in a sample space $S$, the formula $P(E)=|E|/|S|$ only works when all the outcomes in $S$ are equally likely. When you forgot about order in the birthday problem, your sample space consisted of all multisets of $n$ birthdays. These are not all equally likely; the probability of two people being born on Jan 1 is $(1/365)^2$, but the probability of two people having the set of birthdays equal to $\{\text{Jan 1 , Jan 2}\}$ is $2(1/365)^2$, since there are two ways it can happen. This is why your formula fails.

The trick of forgetting the order often works in probability, but not here.

---

Side note: If you were to assert that all multisets of birthdays are equally likely, it would imply that the birthdays of the people are dependent in the following way. You can imagine the birthdays being chosen one at a time, where if there are already $n_i$ people whose birthday is the $i^{th}$ day of the year, the probability the next person is born on day $i$ is $$ \frac{n_i+1}{\sum_{i=1}^{365}(n_i+1)} $$ For example, the first person is equally likely to be born on any day, but then the second person has a $2/366$ chance of being born on the same day as the first person, and a $1/366$ chance of being born on any other day.

Answer 2

The first treats the $n$ people as different. The case where two people were born on January $1$st and everyone else had a unique birthday would be counted once by your method, without factoring the possibilities for different people. The first method would count that case in $\binom{n}{2}(n-2)!$ ways, because it matters which people were born on January $1$st, and which were born on the other days. The first method then makes more likely the event that two people share a birthday, because it considers all possible combinations of people.

Answer 3

According to your comment to @KevinLong's anwer, we approach the birthday problem as equivalent to throwing $n$ (undistinguishable) balls into $m=365$ (distinguishable) boxes.

If you throw the balls in the bins then you have a space of $n^m$ equi-probable events. The resulting bin occupancy hystograms will be considered different if any bin has a different amount of balls, but also if the throw sequence order of the balls in it are different.
Instead by arranging the balls in the bins, we mean that we consider the occupancy hystograms different only when the corresponding $m$-tuples are different. That is to say that each hystogram corresponds to a weak composition of $n$ into exactly $m$ parts, which seems to be the scheme you want to consider when telling that "order does not matter".

The number of weak compositions of $n$ into $m$ parts is $$ \binom{n+m-1}{m-1}= \binom{n+m-1}{n} $$ where the second expression is more general, being valid for all $0 \le n,m$.
With a few passages this will lead to your formula.

But the universe of equi-probable events of arranging the balls in the bins does not correspond to that of the birthday problem, which instead corresponds to the throwing scheme.