# Birthday problem: using $^nC_r$.

In birthday problem say total number of people n < 365, then probability of all person having distinct birthday is given by,

$$\frac{\text{total no. of ways of selecting n numbers from 365 without repetition}} {\text{total number of ways of selecting n object from 365 with repetition}}.$$

$$p = \frac{^{365}C_n}{^{365-1+n}C_n}$$

I know, that this is wrong, but don't know why.

1. I want to know why is it wrong?

2. Can this problem be solved using $^nC_r$ calculations, if not, why?

The number of ways $n$ distinct dates can be selected from $365$ is $\binom{365}{n}$. After you have chosen you can arrange them in $n!$ ways. So total is $n!\times\binom{365}{n}$.

All $n$ people can have birthdays in $365$ possible days so the total ways is $365^n$ hence you get $$\frac{n!\binom{365}{n}}{365^n}$$

The formula you have in the denominator is different from what you intend, it is distributing 365 days among n people. (link) The formula you are using assumes that days and people aren't distinct from one another.

An equivalent number of possible 3 digit binary numbers. In this case the places are all distinct from one another and so are the digits. Hence the formula you use is based on an assumption not relevant to this problem.

• "The formula you have in the denominator is different from what you intend it is distributing 365 days among n people" It is the same as the link you have provided, distributing 365 among n people with repetition. When doing probability calculations for cards say probability of selecting 4 cards of same color is give by ^4c_1*^{13}c_4/^{52}c_4. May 8, 2018 at 4:30
• It is related to distinctness of days and people May 8, 2018 at 4:52

It can't be purely solved by binomial coefficients because the right expression is $$\frac{365}{365} \times \frac{364}{365} \times \cdots \times \frac{365-n+1}{365}=\frac{365!}{(365-n)! 365^n}$$ (first trial doesn't collide with existing birthdays (empty set), second doesn't collide with probability 364/365, etc.) and the power term in the denominator stops it being reduced to only binomial coefficients.

Edit: The process is sequential, so let's compute the probability by taking order into account.

If you take the total number of ways of selecting $r$ objects from $n$ without repetition where the order is important and then divide by the total number of ways of selecting $n$ objects where the order is important you get $$n!/(n-r)!$$ divided by $$n^r$$ which will give the right answer $$\frac{n(n-1)\cdots (n-r+1)}{n^r}$$ (for you $n=365,$ and $r=n$).

• I know the right expression, but what quantity does the expression that I provided calculates, if it doesn't calculate the probability, why it doesn't? May 8, 2018 at 4:17
• If you take the total number of ways of selecting $r$ objects from $n$ without repetition where the order is important and then divide by the total number of ways of selecting $n$ objects where the order is important you get $n!/(n-r)!$ divided by $n^r$ which will give the right answer May 8, 2018 at 4:43
• But why is the order important here? We only need to check for collisions. Pardon my naive-ness. May 8, 2018 at 4:45
• It is a sequential process, if order wasn't important, things would have cancelled out giving the answer you predicted. May 8, 2018 at 5:22

Assuming the question is, what is the probability of n people all having the same birthday, surely this is simply $$\frac{1}{365^{n-1}}$$

For the first person, it is what it is. For the 2nd person it's a $\frac{1}{365}$ probability their birthday is the same. For 3 people it's $\frac{1}{365} * \frac{1}{365}$ etc, etc for $n-1$ times.

You have two questions, the first is "why is this wrong" You're slightly off in that the denominator isn't "total number of ways of selecting n object from 365 with repetition", it's "total number of ways of selecting n objects from 365 [with or without repetition" That is, 365^N. You would treat the numerator as ordered (using a permutation) because, well, it makes that math easier. Otherwise (if using a combination) you have to allow for randomizing the order in the numerator and the denominator, which will end up being a division by n! in both that cancels.

So, for the second question, you can use nCr calculations for the numerator, but not the denominator.