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 thinking was to first assign one class to each of the $5$ days , $6^5$ ways of doing that. Then multiply this with the probability of selecting remain $2$ classes such as:

$a)$ either they both are on the same day, or

$b)$ on two different days.

Probability for $(a)=$$ 5\times \binom{5}{2}$ . Prob. of $(b)=$ $\binom{5}{2}\times 5$ . This gives total no. of ways to assign classes as required. Then divide this by $\binom{30}{7}$ $($total no of ways to assign classes randomly$)$. But this gives a probability greater than $1$ . Where is my thinking wrong? All classes are equally likely and I don't think the process of choosing follows order of days.

  • 1
    $\begingroup$ You have to select classes at first, $\binom{30}{7}$ $\endgroup$ – Entrepreneur Jul 6 '18 at 8:04
  • $\begingroup$ What about :$$\binom{30}{30}\times \binom{29}{30}\times \binom{28}{30}...\binom{24}{30}$$ ? For numerator ... $\endgroup$ – Entrepreneur Jul 6 '18 at 8:09

There are $\binom{24}{7}$ selections that are avoiding one of the five days.

There are $\binom{18}{7}$ selections that are avoiding two of the five days.

There are $\binom{12}{7}$ selections that are avoiding three of the five days.

The number of selections that are avoiding one or more days is, by inclusion-exclusion :

$bad = 5\binom{24}{7} - 10 \binom{18}{7} + 10\binom{12}{7} - 0 + 0 = 1420200 $

$\frac {total - bad} {total} = \frac{615600}{2035800} \approx 0.30$


This can be done by two methods.

Direct Method

Inclusion-Exclusion Method

Lets Starts with

Direct Method:- There are two general ways that Alice can have class every day: either she has $2$ days with $2$ classes and $3$ days with $1$ class, or she has $1$ day with $3$ classes, and has $1$ class on each of the other $4$ days. The number of possibilities for the former is $\dbinom{5}{2}\dbinom{6}{2}6^3$ $($choose the $2$ days when she has $2$ classes, and then select $2$ classes on those days and $1$ class for the other days$)$ The number of possibilities for the latter is $\dbinom{5}{1}\dbinom{6}{3}6^4$. So the probability is $$\dfrac{\dbinom{5}{2}\dbinom{6}{2}6^3+\dbinom{5}{1}\dbinom{6}{3}6^4}{\dbinom{30}{7}}=\dfrac{114}{377}\approx0.302$$

Inclusion-Exclusion Method- We will use inclusion-exclusion to find the probability of the complement, which is the event that she has at least one day with no classes.

Let say $B_i=A^c_i.$ Then $$P(B_1\cup B_2....\cup B_5)=\sum _{ i }^{ }{ P(B_ i)- } \sum _{ i<j }^{ }{ P(B_ i)-\sum _{ i<j }^{ }{ P(B_ i\cap B_ j)+\sum _{ i<j<k }^{ }{ P(B_ i\cap B_ j\cap B_ k) } } } $$ Note that terms with the intersection of $4$ or more $B_i$’s are not needed since Alice must have classes on at least $2$ days. Then we have $$P(B_1)=\dfrac{\dbinom{24}{7}}{\dbinom{30}{7}},P(B_1\cap B_2)=\dfrac{\dbinom{18}{7}}{\dbinom{30}{7}},P(B_1\cap B_2\cap B_3)=\dfrac{\dbinom{12}{7}}{\dbinom{30}{7}}$$and similarly for the other intersections. So$$P(B_1\cup B_2....\cup B_5)=5\dfrac{\dbinom{24}{7}}{\dbinom{30}{7}}-\dbinom{5}{2}\dfrac{\dbinom{18}{7}}{\dbinom{30}{7}}+\dbinom{5}{3}\dfrac{\dbinom{12}{7}}{\dbinom{30}{7}}=\dfrac{263}{377}$$ Therefor, $$P(A_1\cap A_2\cap A_3\cap A_4\cap A_5)=\dfrac{114}{377}\approx0.302$$

  • $\begingroup$ What about my process is wrong? $\endgroup$ – Aniruddh Shekhawat Jul 7 '18 at 5:46
  • $\begingroup$ @AniruddhShekhawat your answer is wrong. I had briefly explained along with the reasoning in my answer. $\endgroup$ – Key Flex Jul 7 '18 at 13:32

There are two options:

  1. Select 2 days with two classes and 3 days with one class $$|A|=\binom{5}{2}\binom{6}{2}^2\binom{6}{1}^3=486000$$
  2. Select 1 day with three classes and 4 days with one class $$|B|=\binom{5}{1}\binom{6}{3}\binom{6}{1}^4=129600$$

Of course $A\cap B = \emptyset$ and the full scope of selection $\Omega$ contains $|\Omega|=\binom{30}{7}=2035800$ elements. Thus

$$P = \frac{|A|+|B|}{|\Omega|} = \frac{615600}{2035800} \approx 0.3$$

Your attempt

You're missing some details.

For selecting two days with additional classes:

  1. Select one class for each day ($6^5$)
  2. Select two days ($\binom{5}{2}$)
  3. Select additional classes for these days ($\binom{5}{1}^2$)
  4. Avoid counting situations multiple times by dividing it by the number of possible permutations of selection ($(2!)^2$)

So the number of distinct events in that case is $$|A|=\frac{6^5\binom{5}{2}\binom{5}{1}^2}{(2!)^2}$$

Analogically we can calculate number of distinct events in case, where we select only one day with three classes (divided by number of possible selections of classes in day with three classes as the first selected ($3$)): $$|B|=\frac{6^5\binom{5}{1}\binom{5}{2}}{3}$$

  • $\begingroup$ I selected 5 days with 1 class each. Then selected days for the remaining 2 classes (two cases: 2 classes on the sae day and 2 classes on different days). Where is my thinking wrong. $\endgroup$ – Aniruddh Shekhawat Jul 7 '18 at 5:48
  • $\begingroup$ @AniruddhShekhawat I've expanded my answer. $\endgroup$ – Jaroslaw Matlak Jul 7 '18 at 8:03

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.