GATE CS 2020 Q42 — Combinatorics: Counting, Recurrence Relations, Generating Functions

Let the original positions of the characters in L I L A C be numbered $1, 2, 3, 4, 5$ respectively:

• L is at positions $1$ and $3$.
• I is at position $2$.
• A is at position $4$.
• C is at position $5$.

Since no character can appear in its original position, the two indistinguishable L's cannot be placed at positions $1$ or $3$. Therefore, they must occupy two of the remaining positions: $2, 4,$ or $5$. This gives us $\binom{3}{2} = 3$ cases:

1. L's are placed at positions $2$ and $4$:

   The remaining positions to fill are $\{1, 3, 5\}$ using the characters $\{I, A, C\}$. Since $C$ cannot be at its original position $5$, it must go to position $1$ or $3$ ($2$ choices). The remaining two characters can be arranged in the remaining two positions in $2! = 2$ ways.
   Total ways = $2 \times 2 = 4$.

2. L's are placed at positions $2$ and $5$:

   The remaining positions to fill are $\{1, 3, 4\}$ using the characters $\{I, A, C\}$. Since $A$ cannot be at its original position $4$, it must go to position $1$ or $3$ ($2$ choices). The remaining two characters can be arranged in $2! = 2$ ways.
   Total ways = $2 \times 2 = 4$.

3. L's are placed at positions $4$ and $5$:

   The remaining positions to fill are $\{1, 2, 3\}$ using the characters $\{I, A, C\}$. Since $I$ cannot be at its original position $2$, it must go to position $1$ or $3$ ($2$ choices). The remaining two characters can be arranged in $2! = 2$ ways.
   Total ways = $2 \times 2 = 4$.

Summing the possibilities from all three mutually exclusive cases, we get: