Birthday Problem with a Twist

Average number of pairs, triples etc among n people

You must have all heard (and solved) the birthday problem that is usually posed. What is the probability that two people share the same birthday from among n people? If you do not know the answer, there are many sites on the internet that discuss this problem. But here is a Birthday problem with a twist. What is the average number of pairs of people with the same birthday among n people? How about triples :three people with the same birthday? What is average number of triples among n people. Can you find a general solution: What is the average number of k people with the same birthday among n people?

Solution: We first consider pairs. Choose two people. The probability that they both will have the same birthday on a specific day of the year is

\(\frac{1}{365^2}\)

The probability that they will have the same birthday on some day of the year is:

\(\frac{365}{365^2}=\frac{1}{365}\)

There are:

\(\frac{n(n-1)}{2}\)

ways to choose the pairs. Hence the average number of pairs with the same birthday will be the product of these or

\(\frac{n(n-1)}{2}\frac{1}{365}\)

This number is greater than 1 if n is greater or equal to 28.

A similar argument shows that the average number of triples (three people with the same birthday) from among n people will be:

\(\frac{n(n-1)(n-2)}{3!}\frac{1}{365^2}\)

This exceeds 1 if n is greater than or equal to 94.

The general solution for the average number k of people who have the same birthday among n people is:

\(\frac{n(n-1)(n-2)\ldots(n-k+1)}{k!}\frac{1}{365^{k-1}}\)

.