How to find number of arrangements of 18 exams with a specific condition?

Question

Student should take $18$ exams. Three of those are Biology, Chemistry and Physics, no two of which can be taken consecutively. What's the number of arrangements in which student can take these exams.

I figured that the way to solve this is to take the number of arrangements that don't fulfill this condition from the total number of $18!$.

Here I get stuck because we can consider arrangements in which we treat all three as a whole and find that there will be $15! \times 6$, accounting for permutation within their group. Or you can also choose groups of $2$, but my problem is that by doing this some of the arrangements accounted for in the previous part will also be considered.

What's the best way to tackle this problem?

Answer 1

There are different methods we could employ here.

Method 1: We use the Inclusion-Exclusion Principle.

If there were no restrictions, there would be $18!$ possible arrangements of the exams. From these, we must exclude those arrangements in which at least two of the Biology, Chemistry, and Physics exams are consecutive.

Two of the three exams are consecutive: There are $\binom{3}{2}$ ways to choose two of the three subjects Biology, Chemistry, and Physics to be examined consecutively. Place those two exams in a block. Then we have $17$ objects to arrange, the block of two consecutive exams and the other $16$ exams. The objects can be arranged in $17!$ ways. The exams within the block can be arranged in $2!$ ways. Hence, there are $$\binom{3}{2}17!2!$$ such arrangements.

However, if we subtract these $17!2!$ cases from the total, we will have subtracted too much since we will have subtracted each case in which all three exams are consecutive twice, once when we designated the first two of those three consecutive exams as the consecutive exams and once when we designated the last two of those three consecutive exams as the consecutive exams. We only want to subtract such cases once, so we must add them back.

All three of the exams are consecutive: Place the Biology, Chemistry, and Physics exams in a block. We now have $16$ objects to arrange, the block of three exams and the other $15$ exams. The $16$ objects can be arranged in $16!$ ways. The three exams can be arranged within the block in $3!$ ways. Hence, there are $$16!3!$$ such arrangements.

By the Inclusion-Exclusion Principle, the number of admissible arrangements of the exams is $$18! - \binom{3}{2}17!2! + \binom{3}{3}16!3!$$

Method 2: We arrange the Biology, Chemistry, and Physics exams among the other $15$ exams so that no two of the Biology, Chemistry, and Physics exams are consecutive. We can arrange the other $15$ exams in $15!$ ways. This creates $16$ spaces in which we can place the Biology, Chemistry, and Physics exams, $14$ spaces between successive exams, one at the beginning, and one at the end. To ensure that no two of the Biology, Chemistry, and Physics exams are consecutive, we must choose three of these $16$ spaces in which to place the Biology, Chemistry, and Physics exams, then arrange these three exams in the selected spaces. This can be done in $\binom{16}{3}3!$ ways. Hence, there are $$15!\binom{16}{3}3!$$ admissible arrangements of the exams.

Answer 2

The intuition of subtracting from the total number is correct. Now we need to compute how many arrangements there are that don't fullfill the condition.

So, let's count how many arrangements where Chemistry is direcly after Biology. That is $$16!\times 17$$ where the 17 is given by the position the group "BC" has in the arrangements.

We can do the same for any ordered pair, which there are $6$. So we have a total of $$16!\times 17\times 6$$

But we counted some arrangements too many times. For example, if an arrangement contains the sequence $BCT$ it gets counted because it contains $BC$ and it gets counted again as it contains $TC$, so we counted it $2$ times. It follows that we have to add again every arrangement where the three subjects are one after another. In total, they are $$15!\times 6\times 16$$

So the result should be $$18!-16!\times 17\times 6 +15!\times 6\times 16=16!\times (18\times 17-17\times 6+6)=16!\times 35\times 6$$