I have a problem of Alice's class problem below:

"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.)" - From Harvard Stat 110 Strategic Practice 2, Fall 2011

finding the probability that Alice has at least one class each day

My answer: Class order is important

Using naive definition of probability:

The number of favourable combinations: $$6^5 \cdot 25\cdot 24 \cdot 7!$$ This is because the five classes that has to be on each of the weekday $(6^5)$. And then the rest of the two classes can be on the rest of the classes $(25\cdot24)$. Finally, within the 7 classes, there are $7!$ combinations.

The number of total possible combinations = $^{30}P_7$

Therefore, answer = $$\frac{6^5 \cdot 25\cdot 24 \cdot 7!}{^{30}P_7} = 2.29$$

Can someone tell me what is wrong with my answer?

I would just like to add as a general advice that whenever possible, seek an analogy of a well-known class of problems.

Here the analogy I would like to draw is a card pack of $30$ with $5$ suits. We need to find the probability of getting a hand that has $3$ of one suit (=day) and $1$ each of the remaining four, or $2$ each of two suits and $1$ each of the remaining three. The answer, then is

$$\frac{\binom63[\binom61^4]\frac{5!}{4!} + [\binom62^2][\binom61^3]\frac{5!}{2!3!}}{\binom{30}7}$$

The algorithm for selecting classes indicated by the figure $$6^5\cdot 25\cdot 24\cdot 7!$$ is overcounting! It suggests that we do as follows:

• Chose one class per day, $6^5$
• Chose one of the remaining $25$ classes
• Chose one of the remaining $24$ classes
• Shuffle the $7$ selected classes, $7!$

So to illustrate the problem with this, let us distribute class indices among days:

• Monday: 1-6
• Tuesday: 7-12
• Wednesday: 13-18
• Thursday: 19-24
• Friday: 25-30

So running you algorithm, we could chose $1,7,13,19,25$ and then for instance $6,12$ to have $1,7,13,19,25,6,12$ before shuffling.

But we could also have chosen $6,7,13,19,25$ and then $1,12$ to have $6,7,13,19,25,1,12$ before shuffling. But shuffled those two yield the exact same combinations thus overcounting.

In fact chosing $12$ on the second day and later $7$ as an additional class yields more overcounting and chosing the two additional classes in reverse order yields yet another overcount.

Cases with two days with two classes yield an overcount by a factor $8$. Cases with three classes in a single day yield an overcount by a factor $3!=6$. Thus it should come as no surprise that your figure is found within 6-8 times the correct figure, namely $$6\cdot0.3024=1.8144<2.29<2.4192=8\cdot 0.3024$$

• I know that '1,7,13,19,25,6,12' is different from '6,7,13,19,25,1,12'. But in the denominator I am using permutation, which should count the two orders above as different. – Joseph Sep 21 '16 at 2:57
• @Joseph: Yes, but you only need one of them in the numerator, say '1,7,13,19,25,6,12', since then the other is included already when shuffling them the $7!$ ways that you do in the numerator as well. It is like you pre-shuffle those two element so that your shuffle becomes $2!7!$ instead of $7!$ as it should be. As I wrote, you actually pre-shuffle three pairs this way so that you have $2!2!2!7!=8\cdot 7!$ so an overcount by a factor $8$. – String Sep 21 '16 at 8:31