What is my error in solving the birthday problem for $k$ people?

Question

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.

Answer 1

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.

Answer 2

The number of possible combinations of birthdays such that nobody shares a birthday out of $k$ individuals (assuming that $k<365$) is ${365(364)(363)…(365-k+1)}$.

The total number of possible birthdays is $365^k$.

Therefore, the probability that nobody shares a birthday will be $\frac{365(364)…(365-k+1)}{365^k}$.

We can then work out the probability that at least $2$ people share a birthday by simply computing $1-\frac{365(364)…(365-k+1)}{365^k}$ - giving us the required answer to your problem.

Now that begs the question of what is wrong with your solution. The issue is that you shouldn’t multiply $k(k-1)$, you should be multiplying the number of possible positions available for an individuals birthday. For example, if we fix the first person’s birthday, then there are now 364 choices for the second person’s birthday to lie on (assuming that they do not share a birthday).