# Birthday problem, want about using unordered counting?

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?

• I am not sure what you mean by "order matters", but $n \choose k$ gives the number of possibilities to choose $k$ different elements from $n$ elements. As you are exactly interested in multiples, your approach does not make much sense (to me). – Klaus Jan 23 at 17:35
• @Klaus I believe OP is using the stars and bars method. – Kevin Long Jan 23 at 17:36
• In "this calculation" order does not matter. – user Jan 23 at 17:36
• "In this calculation, we treat the n birthdays we selected as a sequence where their order matters. " But its a completely arbitrary sequence so the arbitrary order does not matter. – fleablood Jan 23 at 20:08

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.

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.

• For the problem, we can model by throwing $n$ balls uniformly randomly into $365$ boxes. Essentially, there are $n$ balls and $365-1$ box walls that we are looking at, this is how I come up with the ${365+n-1\choose n}$. – Xiao Jan 23 at 18:01
• @Xiao My mistake- you were right. – Kevin Long Jan 23 at 22:48

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$$.
• As Mike pointed out, the formula "probability = number of desired outcomes / number of total outcomes" only holds when each event in the sample space happens with equal probability. If we make our sample space the collection of unordered dates, this would not work. Take $n=2$, the probability of selecting $\{1,1\}$ is not equal to the probability of $\{1,2\}$. – Xiao Jan 23 at 21:55