The Birthday Problem: given $n$ people (typically $n<365$), what is the probability that some pair of them share a birthday (omitting Feb 29th, for simplicity)?
The solution: First, find the probability that all $n$ people have different birthdays. Here is where I am confused. The solutions I have seen all say this probability is: $$ \frac{_{365}P_n}{365^n} $$
Why isn't this $_{365}C_n$,instead?
$\endgroup$ 15 Answers
$\begingroup$If you did combinations, you would basically choose the birthdays but not assign them to the $n$ people. However the denominator presumes the birthdays have been assigned (365 choices for Alice, 365 choices for Bob, etc.)
$\endgroup$ 2 $\begingroup$The probability with $n$ people is, by considering the first, then the second, then the third, ..., $$\frac{365}{365}\times \frac{364}{365}\times \frac{363}{365}\times \cdots \times\frac{365-n+1}{365}.$$
Now simplify.
$\endgroup$ $\begingroup$Regarding paw88789's response, it is mathematically correct, but omits the "why" of the question, which is why permutations should be used instead of combinations to determine the number of possibilities of the group's birthdays.
Combinations certainly give the number of possible birthday sets, which seems a reasonable way to solve the problem. However, the birthday problem is for a real group of people, and such groups allow for repetition of birthdays. Once repetition is allowed, the number of ways the group can have birthdays is 365^n, for an n-person group. Combinations with repetition are not calculated by nCr [C(n,r)], nor are they related to permutations by a factor of r!, as in nCr = nPr * r!. Although we could calculate the combinations with repetition, it still misses the correct number of possible ways for the group's set of birthdays because a group with a certain combination of birthdays can be put together in possibly more ways than one, and this affects the probability of the result. The basis for the probability of no repetition of birthdays is the number of possible ways for no repetition of birthdays divided by the number of total possible ways, 365^n, for birthdays.
Only permutation gives the correct number of possible ways a group can have birthdays without repetition.
$\endgroup$ 0 $\begingroup$You could, in principle, use combinations to do this problem, that is, take the people to be indistinguishable from each other. The difficulty is that the corresponding sample space consists of ordered partitions of $n$ into 365 non-negative pieces, and those partitions are NOT EQUALLY LIKELY (and are hard to count). So it will NOT be simply (size of event) / (size of sample space).
In general, situations that involve independent identical trials (like people's birthdays, rolling dice, flipping coins, drawing with replacement) are most easily modeled by ordered (i.e. distinguishable) trials, because it is easier to model the sample space with equally likely outcomes that way. For example, the question what is the probability of getting three different numbers when rolling three dice [which IS the birthday problem with 6,3 in place of 365,$n$] is much easier to do if we imagine the dice as distinguishable (i.e. $6\times 5 \times 4/6^3$) than by enumerating ordered partitions of 3 into 6 pieces and figuring out the relative frequency of each type.
$\endgroup$ 4 $\begingroup$Combinations exclude order, while permutations take order into account.
So when it comes to assigning ($person_0$,$person_1$, $person_2$) birth dates from $\{a,b,c,d\}$
(Arrays used below, index denotes person_number .. so if $a$ has index 0, a has been assigned to $person_0$)
[a,b,c], [c,b,a], [b,c,a] .. would be considered the same one element.
So if you are trying to calculate the length of the favorable outcomes space, you'd see why that would be incorrect
As for the the denominator i.e the length of space of all possible outcomes $365^n$ should not give anyone trouble
So P = $\frac {\text{length of favorable outcome space}}{\text{length of all possible outcomes space}}$
So just $C^{365}_n$ would give you a length of set of assignments where order is not important and that is pretty much it. WHen it comes to probability you are missing the deominator
P.S. $\frac{P^{365}_{n}}{365^{n}}$ is the probability of no one sharing the same birthday
$\endgroup$
