Probability that $n$ persons share their birthdays on exactly/at most $k < n$ months?

Question

I have two exercises.

1. What is the probability that $n$ independent persons share their birthdays on exactly $k<n$ months?

2. What is the probability that $n$ independent persons share their birthdays on at most $k<n$ months?

Assume that all months are equally likely.

First, is one of the two questions considerately easier to solve?

Let $X$ be the number of months all $n$ people share their birthdays on. For concreteness, let's look at the case where $n=6$ and the first question.

I was able to find the solutions to the first two cases:

$$P(X=1) = \binom{12}{1}\frac{1}{12^6}$$ $$P(X=2) = \binom{12}{2}\frac{(2^6-2)}{12^6}$$

But I'm stuck with the cases where $X\geq 3$. I don't see how this generalizes yet and all the expressions I came up with have way to high probability (according to a little program that I wrote to approximately compute the probabilities).

Answer 1

Your use of the word “share” is a bit confusing to me, so I’ll reformulate the questions to make sure we mean the same thing:

1. What is the probability $p_k$ that there are exactly $k\le n$ months that contain at least one of $n$ birthdays independently uniformly randomly distributed over the months?

2. What is the probability $q_k$ that there are at most $k\le n$ months that contain at least one of $n$ birthdays independently uniformly randomly distributed over the months?

(I switched $\lt$ to $\le$ because we can also ask the questions for $k=n$.)

The two questions are roughly similarly difficult. The easy question in this context is:

What is the probability $b_k$ that the $n$ birthdays independently uniformly randomly distributed over the months all lie in one of $k\le n$ particular months?

This is just the $n$-th power of the probability that one of the birthdays lies in one of these months, so

$$ b_k=\left(\frac k{12}\right)^n\;. $$

The answers to your questions can be calculated from these probabilities $p_k$ using inclusion–exclusion in the form of a Generalised inclusion-exclusion principle. For your first question:

$$ p_j=\sum_{k=0}^j(-1)^{k-j}\binom{n-k}{n-j}\binom nkb_k\;. $$

If you write this out for $j=1$ and $j=2$, you get your two results for $n=6$.

Summing over $j$ yields the answer to your second question:

\begin{eqnarray} q_j &=& \sum_{\ell=0}^jp_\ell \\ &=& \sum_{\ell=0}^j\sum_{k=0}^\ell(-1)^{k-\ell}\binom{n-k}{n-\ell}\binom nkb_k\;. \\ &=& \sum_{k=0}^j\sum_{\ell=k}^j(-1)^{k-\ell}\binom{n-k}{n-\ell}\binom nkb_k\;. \\ &=& \sum_{k=0}^j(-1)^{k-j}\binom{n-k-1}{n-j-1}\binom nkb_k\;. \end{eqnarray}

So this is the same sort of sum as for the first question, just with the upper and lower indices of one of the binomial coefficients both decremented. If you write this out for $j=1$ and $j=2$, you get

$$ q_1=\binom{12}1\left(\frac1{12}\right)^n $$

and

$$ q_2=\binom{12}2\left(\frac2{12}\right)^n-\binom{10}9\binom{12}1\left(\frac1{12}\right)^n $$

which is also what you would have obtained if you’d added your results for $j=1$ and $j=2$ to get $q_2=p_1+p_2$.

Answer 2

It seems your question is about finding the probability that $n$ people's birthdays are in $k$ different months where each of the $m=12$ months is equally likely and birthdays are independent of one another

This probability satisfies the recurrence $$\mathbb P_{m,n}(K=k) = \frac{m-k+1}{m}\mathbb P_{m,n-1}(K=k-1) + \frac{k}{m}\mathbb P_{m,n-1}(K=k)$$

starting at $\mathbb P_{m,0}(K=0) =1$ and $\mathbb P_{m,0}(K=k)=0$ for $k>0$. It has the solution

$$\mathbb P_{m,n}(K=k) = \dfrac{m! \, S_2(n,k)}{(m-k)!\, m^n}$$ where $S_2(m,k)$ are Stirling numbers of the second kind

In your example with $m=12$ and $n=6$, so $m^n=248832$, you get

k              P(K=k)                     P(K<=k)
-  -------------------------    ------------------------
1       1/248832    0.000004         1/248832   0.000004
2     341/248832    0.001370       342/248832   0.001374
3    9900/248832    0.039786     10242/248832   0.041160
4   64350/248832    0.258608     74592/248832   0.299769
5  118800/248832    0.477431    193392/248832   0.777199
6   55440/248832    0.222801    248832/248832   1