I am completely confused by the following problem.

enter image description here

I understand the basic formula for combinations: $\frac{n!}{k!(n-k)!}$. For example, if the equation was asking about only one quarter with no prerequisites, there would be 45 combinations.

However, with the perquisites and 5 quarters, I am completely lost. I tried making a tree-diagram with the various options (the first quarter is 6 choose 2, after that, it breaks off into 5 choose 2 (if 351 is taken) or 4 choose 2 (if is isn't)... and so on. I multiplied each branch and added them together, but it gave me a ridiculously high number (1944000), which is why I think I'm doing it incorrectly. Can someone walk me through step by step so that I can understand the process here?


I don't see any nice general strategy here, because the problem is very arbitrary. So let us try to solve this problem while trying to keep the amount of considered cases as low as possible.

For convenience, let the courses be named $A,B,C,D,E,F_1,..,F_5$ where we have the dependencies $A$ before $B$, $B$ before $C$ and $D$, and $D$ before $E$. To simplify, the courses $A,B,D$ and $E$ must be followed in that order, and $C$ must be followed after $B$. We consider two cases.

Case 1: Courses $A,B,C,D$ and $E$ are all followed on different days. Their order has to be $ABCDE$, $ABDCE$ or $ABDEC$. With their order fixed, their quarters are also fixed. We then just have to arrange the remaining $5$ courses, which leaves us with $5!$ options per order, so $3\cdot5!=360$ options in total.

Case 2: Course $C$ is followed on the same quarter as either $D$ or $E$. There will be exactly one quarter where none of the courses $A,B,C,D$ and $E$ are followed, for which there are $5$ options. We then choose whether $C$ is followed on the same quarter as $D$ or $E$, which gives $2$ options. Then for each option, we only need to arrange the remaining $5$ courses, which leaves us with $5!/2$ options per order, so $5\cdot2\cdot5!/2=600$ options in total. The divide by two comes from the fact that two of the remaining courses fall on the same day, so their respective order does not matter.

In conclusion, the answer is $360+600=960$.


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.