Birthday problem: using $^nC_r$.

Question

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?

Answer 1

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$).

Answer 2

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.

Answer 3

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.

Answer 4

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.