2

This is Blitzstein's Introduction to Probability (2019 2 ed) Ch 1, Exercise 54, p 51.

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.)

My friend's wrong answer is $6^5$ * $25C2$ for the numerator. For this question, the denominator is not of a concern $30C7$. Here's his reasoning:

  1. Monday 6 classes, Tuesday 6 classes etc. $6^5$ shows all the possibilities of choosing one class from each day.
  2. There will be 25 classes left to choose 2 from. So he multiplies by $25C2$.

However, I told him that he is incorrect by pointing out an example (which I hope someone can verify so as to convince him further). Most importantly, how can I tweak (rather than just change) his answer to get the right answer?

  1. Denote $M_i$ as Monday, and $i$ is from 1 to 6 (since there are 6 classes each day). Denote Tuesday as $T_i$ , etc.
  2. You can pick $M_1$,$T_1$,$W_1$,$Th_1$,$F_1$ according to his first point. And pick let say $M_2$,$M_3$ for his second point.
  3. However, there will be a lot of double counting because I can have another permutation with the same classes: $M_2$,$T_1$,$W_1$,$Th_1$,$F_1$ and $M_1$,$M_3$.
  4. Therefore, he is double counting by a factor of $3$. So he should just divide by 3? $\frac{6^5 \times 25C2}{3}$?

I need help with point 4, because it doesn't yield the right answer.

amWhy
  • 209,954
user3814631
  • 115

2 Answers2

3

You have shown that the cases with 3 classes on one day (and one class on each of the other four days) are counted 3 times. There are however also cases where two days have 2 classes, and these cases are counted 4 times in his method.

So there is not a single correction factor you can apply to fix his method. To fix it you would actually have to work out how many possibilities there are of each of those two types, but if you do that then you have already worked out the correct answer to the problem. So really, his method cannot be fixed.

Jaap Scherphuis
  • 13,660
2

As explained in Jaap Scherphuis's answer, your friend's attempt is essentially irreparable.

A correct solution has to consider the possibilities for the sequence of daily class counts.

With that approach, the probability in question is given by $$ {\large{ p = \frac { \binom{5}{1}\binom{6}{3}\binom{6}{1}^4+\binom{5}{2}\binom{6}{2}^2\binom{6}{1}^3 } { \binom{30}{7} } }} = \frac{114}{377} \approx .3023872679 $$ Explanation:

There are$\;{\large{\binom{30}{7}}}\;$possible selections of $7$ classes.

To get $7$ classes with all $5$ days represented, the sequence of daily class counts for the selected classes must be, in some order, either$\;1,1,1,1,3\;$or$\;1,1,1,2,2$.

For the case $1,1,1,1,3$

  • There are ${\large{\binom{5}{1}}}$ choices for the day which will have $3$ classes.$\\[4pt]$
  • There are ${\large{\binom{6}{3}}}$ ways to choose the classes for that day.$\\[4pt]$
  • There are ${\large{\binom{6}{1}^4}}$ ways to choose the classes for other $4$ days.

$\;\;\;\;\;\;$hence$\;{\large{\binom{5}{1}\binom{6}{3}\binom{6}{1}^4}}$ is the count for this case.

For the case $1,1,1,2,2$

  • There are ${\large{\binom{5}{2}}}$ choices for the two days which will have $2$ classes.$\\[4pt]$
  • There are ${\large{\binom{6}{2}^2}}$ ways to choose the classes for those two days.$\\[4pt]$
  • There are ${\large{\binom{6}{1}^3}}$ ways to choose the classes for other $3$ days.

$\;\;\;\;\;\;$hence$\;{\large{\binom{5}{2}\binom{6}{2}^2\binom{6}{1}^3}}\;$is the count for this case.

quasi
  • 58,772