The birthday problem poses the following problem:
Calculate the probability that at least two people share a birthday out of $k$ people, assuming $365$ days in a year.
My attempt was to fix two people's birthdays to match. There are $k(k – 1)$ ways to do this. For the remaining $k – 2$ people, any birthday is fine, so there are $k(k – 1)365^{k – 2}$ ways to do dole out the birthdays where there is a match. I divided that by $365^k$, all the ways the birthdays can be distributed, and figured that would be the probability.
However, I am wrong. The answer is $1 – \frac{365(364)\cdots(365 – k + 1)}{365^k}$ from counting the complement. Where am I going wrong? Thanks.
Best Answer
There are several problems in your approach:
The first problem is that your consider ordered pair instead of unordered. Really the cases $(1, 2)$ and $(2, 1)$ are the same and should be replaced by $\{\,1, 2\,\}$. The number of unordered pairs is $\frac{k(k - 1)}{2}$.
The second problem is that you allow other people to have the same birthday as the selected pair. Therefore you count the same combination several times. For example, if there are $k = 5$ people with the same birthday, you will count this option $\frac{k(k - 1)}{2} = 10$ times. However just removing for all others this one day is not enough, because there are cases when two pairs share birthday (unique for each pair). And the problem is still the same: you count the same combination several times. Therefore you should make all other birthdays to be pairwise distinct, and probability is $\frac{k(k - 1)}{2} \cdot \frac{365 \cdot 364 \cdots (365 - (k - 2))}{365^k}$.
The third problem follows from the second one, but it is the most significant. You should consider also cases when $3, 4, \ldots, k$ people have the same birthday. This is not a big deal: if exactly $\ell$ people share birthday and all others have pairwise distinct birthdays the probability is $\binom{k}{\ell} \cdot \frac{365 \cdot 364 \cdots \cdot (365 - (k - \ell))}{365^k}$. However there are more complicated cases, when there are two pairs sharing birthday (unique for each pair), when there are such pair and triple, when there are ten such pairs, six triples and three quadruples and so on. The number of cases you should consider is exponential of $k$ and there is no simple way to consider them all.