In a room of $n \geq 7$ people, what is the probability that, for each day of the week, there is at least one person whose birthday falls on that day?

Question

In a room of $n \geq 7$ people, what is the probability that, for each day of the week, there is at least one person whose birthday falls on that day? Assume each day of the week has equal probability.

I am thinking about allocating each day one person and then stars and bars the rest? But cant think of the sample space.

I also consider using complement: $$1- \binom{7}{1}\left(\frac{6}{7}\right)^n - \binom{7}{2}\left(\frac{5}{7}\right)^n \ldots$$ but then I will double count. I tried inclusion-exclusion, but I can't figure it out.

Answer 1

Ways to select one person for each day is ${n \choose 7}$

Stars and bars for $n-7$ people in 7 groups is $\frac{(n-1)!}{6!}$

Hence the number of possible combinations is

$$\frac{n!}{7!(n-7)!}\cdot\frac{(n-1)!}{6!}$$

The denominator is a stars and bars of $n$ people into 7 group ie $\frac{(n+6)!}{6!}$

$$P = \frac{n!(n-1)!}{7!(n-7)!(n+6)!}$$

Answer 2

If there are $n$ people, each of the $7^n$ functions mapping persons to a day of the week are equally likely. The question can thus be restated as: how many of those functions are surjective (call this number $F$).

Now, if we have a partition of the $n$ people into $7$ unlabeled non-empty classes, there are $7!$ ways to make a surjective function (mapping classes to a specific day of the week). On the other hand, if we have a surjection, the pre-image of each day of the week gives us a unique partition of the $n$ people into $7$ non-empty classes.

The number of ways to partition $n$ objects into $k$ non-empty classes is given by the Stirling numbers of the second kind $S(n,k)$. So we find $F = S(n,7)\cdot 7!$. Therefore the requested probability is $$P=\frac{S(n,7)\cdot 7!}{7^n}$$ These Stirling numbers don't really have a "simple form", so you will have to use recurrence relations or summations to find their values.

Answer 3

Since there are seven possible days of the week on which each person could have been born, there are $7^n$ possible birthday assignments.

If at least one person is born on each day of the week, we must exclude those birthday assignments in which at least one day is missing. There are $\binom{7}{k}$ ways to exclude $k$ days of the week and $(7 - k)^n$ ways to distribute the $n$ birthdays to the remaining $7 - k$ days of the week. Hence, by the Inclusion-Exclusion Principle, the number of favorable cases is $$\sum_{k = 0}^{7} (-1)^k\binom{7}{k}(7 - k)^n = 7^n - \binom{7}{1}6^n + \binom{7}{2}5^n - \binom{7}{3}4^n + \binom{7}{4}3^n - \binom{7}{5}2^n + \binom{7}{6}1^n - \binom{7}{7}0^n$$ Hence, the probability that at least one person is born on each day of the week is $$\frac{7^n - \dbinom{7}{1}6^n + \dbinom{7}{2}5^n - \dbinom{7}{3}4^n + \dbinom{7}{4}3^n - \dbinom{7}{5}2^n + \dbinom{7}{6}1^n - \dbinom{7}{7}0^n}{7^n}$$