In a $10$-member family, what is the probability that the birthdays of the members include all seven days of the week?

Question

Is my solution for the following textbook problem correct?

In a 10-member family, what is the probability that the birthdays of the members include all seven days of the week?

My solution:

All possible combinations are equal to $7^{10}$, which is akin to the problem of distributing $10$ different objects into 10 distinct boxes with repetitive objects allowed.

Now, we select $7$ objects (i.e., people) ${10 \choose 7}$, put them in the boxes (i.e., days) so that we have at least one birthday on each day. Accounting for internal permutation, we have ${10 \choose 7}\cdot7!$

Three objects are left. These could be put in the same box or in different boxes. We break down the possibilities:

• All three in different boxes. We have $7$ choices for the first object, $6$ for the seven and $5$ for the third. In other words, ${7 \choose 1}\cdot {6 \choose 1}\cdot {5 \choose 1}$. Now, we have three $2$-member boxes each having a $2!$ internal permutation. Hence, we have

$$\frac{{7 \choose 1}\cdot {6 \choose 1}\cdot {5 \choose 1}}{2!\cdot2!\cdot2!}$$

• Two in the same box. We choose a pair put them in any of the seven boxes and there's six choices for the remaining object. Again, factoring in repeated cases, we get

$$\frac{{3 \choose 2}\cdot {7 \choose 1}\cdot {6 \choose 1}}{3!\cdot2!}$$

• All three one the same day. This is easy: $$ \frac{{7 \choose 1}}{4!}$$

Now, employing the rule of sum (since the above cases are mutually exclusive), we compute the probability

$$ \frac {{10 \choose 7} \cdot 7! \cdot [\frac{{7 \choose 1}\cdot {6 \choose 1}\cdot {5 \choose 1}}{2!\cdot2!\cdot2!} + \frac{{3 \choose 2}\cdot {7 \choose 1}\cdot {6 \choose 1}}{3!\cdot2!} +\frac{{7 \choose 1}}{4!}]} {7^{10}} $$ which is almost $0.08$.

Also, can you think of a better, more systematic (or perhaps general) solution for the above problem? I suspect there's one and that this could be done through computing the complement cases. I have been trying to no avail. I can't eliminate repetitive distributions.

Update: Thanks for the replies gentlemen. All were very helpful. Case closed.

Answer 1

It's very nearly right. The only issue is that when you divide out to account for counting a particular combination multiple times, you don't need the factorials. So that means case 2, say, should be $$\frac{\binom 32\binom 71\binom 61}{3\times2}.$$ This is because when counting combinations where three people have birthdays on Monday and two have birthdays on Saturday, say, there are $3\times 2$ ways to choose your initial seven people who cover all the days, not $3!\times 2!$.

Making this change will give you just over $10\%$. A more general way to do it is to use the inclusion-exclusion principle. The number of ways to miss out at least one day is $$\binom71\times6^{10}-\binom 72\times5^{10}+\binom 73\times4^{10}-\binom 74\times3^{10}+\binom 75\times2^{10}-\binom 76\times1^{10},$$ so we can subtract this from $7^{10}$ to get the number of ways to cover all days.

Answer 2

We may label any configuration with a function from $[1,10]$ to $[1,7]$. There are $7^{10}$ functions between these sets, and $7!{10\brace 7}$ of them are surjective, with ${10 \brace 7}=5880$ being a Stirling number of the second kind. The wanted probability is so $$ \frac{7!{10\brace 7}}{7^{10}}=\frac{86400}{823543}\approx \color{red}{10.49\%}. $$

Answer 3

Not quite. Selecting 7 people and giving them a distinct day, then distributing the remaining 3 over those seven days, over counts many common cases. You don't have mutually exclusion so cannot employ the rule of sum.

(Assigning Mary to Monday, six other people for the rest of the week, then assigning Tom, Dick, and Hellen to Monday, is the same event as assigning Hellen to Monday, the same six other people to the rest of the week, then Tom, Dick, and Mary to Monday, and so on.)

---

We want to select days for ten people such that each day is selected at least once.

We can select

• One day common to four people, one day for each of the six other people. $$\binom7 {1,6}\binom {10}{4,1,1,1,1,1,1}$$
• One day common to three people, one day common to two, one for each of five others. $$\binom{7}{1,1,5}\binom{10}{3,2,1,1,1,1,1}$$
• Three days each common to two people, one day for each of the four others $$\binom {7}{3,4}\binom{10}{2,2,2,1,1,1,1}$$

So the required probability is $$\dfrac{7!\,10!}{7^{10}}\left(\dfrac{1}{6!\,4!}+\dfrac{1}{5!\,3!\,2!}+\dfrac{1}{3!\,4!\,2!^3}\right)\\~\\= \dfrac{86400}{823543}\\~\\\approx 0.104{\small 9}$$

Which agrees with Jack D'Aurizio's answer (as this approach is along the path to introducing Stirling numbers).