4
$\begingroup$

This is a problem from Harvard Stat 110 Probability Homework set 2:

Alice attends a small college in which each class meets only once a week. She is deciding between 30 non-overlapping classes. There are 6 classes to choose from for each day of the week, Monday through Friday. Trusting in the benevolence of randomness, Alice decides to register for 7 randomly selected classes out of the 30, with all choices equally likely. What is the probability that she will have classes every day, Monday through Friday? (This problem can be done either directly using the naive definition of probability, or using inclusion-exclusion.)

I know how to solve the problem (the solution is provided), but I got it wrong on the first attempt and I can't figure out why.

Clearly, ${30 \choose 7}$ is a total number of ways to make a 7-class schedule. Then I need to count how many ways there are to have at least one class every day. First, Alice chooses one class on Monday through Friday, and there are $6^5$ ways to do it. After fixing these five classes, she goes on to choose other two classes among 30-5=25 classes that are left, and there are ${25 \choose 2}$ ways to do it. Thus, by the naive definition of probability, $\frac{{6^5}{25 \choose 2}}{30 \choose 7}$ . This greatly overcounts the number of "favorable" schedules and yields the probability greater than 1, which is impossible. Can anyone explain where exactly my logic fails? I would really appreciate it!

$\endgroup$
3
$\begingroup$

You’re not alone: it’s one of the most common overcounting errors. To see exactly what the problem is, let’s say that she ends up with classes $M_1,M_2,M_3,T_1,W_1,\Theta_1$, and $F_1$, where the first three meet on Monday, and the remaining four meet on Tuesday, Wednesday, Thursday, and Friday, respectively. Your $6^5\binom{25}2$ counts this schedule $3$ times:

  • once with $M_1,T_1,W_1,\Theta_1$, and $F_1$ as the fixed five classes and $M_2$ and $M_3$ as the two extras;
  • once with $M_2,T_1,W_1,\Theta_1$, and $F_1$ as the fixed five classes and $M_1$ and $M_3$ as the two extras; and
  • once with $M_3,T_1,W_1,\Theta_1$, and $F_1$ as the fixed five classes and $M_1$ and $M_2$ as the two extras.

Every schedule that has three classes on one day gets counted $3$ times in this way. It would be a good exercise to see whether can work out how many times a schedule is counted if it has two days on which two classes meet (e.g., one like $M_1,M_2,T_1,T_2,W_1,\Theta_1$, and $F_1$).

$\endgroup$
  • $\begingroup$ @Egg: You're welcome! $\endgroup$ – Brian M. Scott Mar 3 '16 at 13:20
1
$\begingroup$

Apologies, I miscalculated the number of classes.

1) 3 classes in 1 day, 1 in the remaining: $5 \times\binom{6}{3} \times 6^4$

2) 2 classes in 2 days, 1 in the remaining: $\binom{5}{2}(\binom{6}{2})^2 \times 6^3$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.