Probability and counting: GATE CS question with solution

Method: count the complement with inclusion-exclusion.

All arrangements: $5!=120$.

Let $A$ = arrangements with $P$ leftmost and $B$ = arrangements with $Q$ rightmost.

• $|A|=4!=24$ (fix $P$, arrange the other four).
• $|B|=4!=24$.
• $|A\cap B|=3!=6$ ($P$ leftmost and $Q$ rightmost, arrange the middle three).

Bad arrangements: $|A\cup B|=24+24-6=42$. Good arrangements: $120-42=78$.

Check by direct counting. If $P$ is rightmost, $Q$ cannot be rightmost, so the other four go anywhere: $4!=24$. If $P$ is in one of the three middle positions, $Q$ has 3 allowed positions out of the remaining 4, and the other three books fill the rest in $3!$ ways: $3\times 3\times 6=54$. Total $24+54=78$.

Trap. Subtracting $24+24$ from 120 gives 72: the 6 arrangements that break both rules were removed twice and must be added back once. Applying only one rule gives 96.

What was tested: turning "not this and not that" into a complement and applying two-set inclusion-exclusion correctly.