In a trial examination session a candidate at a school has to take 18 examination papers including the physics paper, the chemistry paper and the biology paper. No two of these three papers may be taken consecutively. There is no restriction on the order in which the other examination papers may be taken. Find the number of different orders in which these 18 examination papers may be taken.
What I did was:
- Number of possible outcomes when three science papers are together: $3! \times 16!$
- Number of possible outcomes when two science papers are together: $2! \times 17!$
- Therefore, the answer is $18!- 3! \times 16!- 2 \times 17!$
I feel like there's some faulty logic in the second line. Correct answer is $4.39 \times 10^{15}$.
Method 1: If we disregard the scheduling of the biology, chemistry, and physics papers, the remaining papers can be scheduled in $15!$ ways. This creates $16$ slots in which the biology, chemistry, and physics papers can be scheduled, $14$ between successive papers, the slot before those papers, and the slot after them.
$$\square P \square P \square P \square P \square P \square P \square P \square P \square P \square P \square P \square P \square P \square P \square P \square$$
To ensure that no two of the biology, chemistry, and physics papers are consecutive, we must choose three of these $16$ slots for those papers, which can be done in $\binom{16}{3}$ ways, and arrange the papers in the chosen slots, which can be done in $3!$ ways. Hence, there are $$15!\binom{16}{3}3!$$ ways to schedule the $18$ papers in such a way that no two of the biology, chemistry, and physics papers are scheduled consecutively.
Method 2: We use the Inclusion-Exclusion Principle.
There are $18!$ ways of scheduling the papers. From these, we need to exclude those schedules in which two or more pairs of the biology, chemistry, or physics papers are scheduled consecutively.
A pair of consecutive papers: There are $\binom{3}{2}$ ways to choose two of the three subjects to be scheduled consecutively. This gives us $17$ objects to arrange, the block of two consecutive papers and the other $16$ papers. The objects can be arranged in $17!$ ways. The two papers within the block can be arranged in $2!$ ways. Hence, there are $$\binom{3}{2}17!2!$$ such schedules.
However, if we subtract those arrangements from $18!$, we will have subtracted each arrangement with two pairs of consecutive papers (three consecutive papers) twice, once when we designated the first pair as the pair of consecutive papers and once when we designated the last pair as the pair of consecutive papers. Since we only want to subtract such cases once, we must add them back.
Two pairs of consecutive papers: This means that the biology, chemistry, and physics papers are scheduled in a block. This gives us $16$ objects to arrange, the block and the other $15$ papers. The objects can be arranged in $16!$ ways. The three papers within the block can be arranged in $3!$ ways. Hence, there are $$16!3!$$ such arrangements.
By the Inclusion-Exclusion Principle, the number of permissible schedules is $$18! - \binom{3}{2}17!2! + 16!3!$$
Method 3: We correct your attempt.
You correctly counted the total number of cases and the number of cases in which all three of the biology, chemistry, and physics papers are together. As you suspected, your error was in counting those cases in which exactly two papers are together.
Exactly two of the three papers are together: As in method 1, if we disregard the scheduling of the biology, chemistry, and physics papers, the remaining papers can be scheduled in $15!$ ways. This creates $16$ slots in which the biology, chemistry, and physics papers can be scheduled, as shown above. The two papers that are scheduled together can be selected in $\binom{3}{2}$ ways. The block containing those papers can be placed in $16$ ways. The other paper can be placed in one of the $15$ remaining slots. The two papers in the block can be arranged in $2!$ ways. Hence, there are $$15! \cdot \binom{3}{2} \cdot 16 \cdot 15 \cdot 2!$$ ways to schedule the examination papers so that exactly two of the biology, chemistry, and physics papers are together.
Hence, the number of permissible schedules is $$18! - 15! \cdot \binom{3}{2} \cdot 16 \cdot 15 \cdot 2! - 16!3!$$