GATE CS 2020 Set 1 — Question 52

The word is LILAC. The positions are 1, 2, 3, 4, 5.
Original characters at positions: $P_1=L, P_2=I, P_3=L, P_4=A, P_5=C$.
We need a permutation $t_1 t_2 t_3 t_4 t_5$ such that $t_i$ is not the character originally at $P_i$.
Specifically:

• $t_1 \neq L$
• $t_2 \neq I$
• $t_3 \neq L$
• $t_4 \neq A$
• $t_5 \neq C$

Since the two L's are indistinguishable, the conditions $t_1 \neq L$ and $t_3 \neq L$ mean that neither of the two L's can be placed at position 1 or position 3. The L's must be placed in the set of allowed positions $\{2, 4, 5\}$.Since there are two L's, we choose 2 positions from $\{2, 4, 5\}$. There are 3 cases:Case 1: L's at positions 2 and 4.
Remaining positions: 1, 3, 5. Remaining characters: I, A, C.
Constraint: $t_5 \neq C$ (constraints for 1 and 3 are satisfied as L is not there).
Permutations of $\{I, A, C\}$ in positions $\{1, 3, 5\}$:
Total $3! = 6$. Subtract cases where $t_5 = C$. If $t_5=C$, remaining I, A in 1, 3 ($2! = 2$ ways).
Valid ways = $6 - 2 = 4$.Case 2: L's at positions 2 and 5.
Remaining positions: 1, 3, 4. Remaining characters: I, A, C.
Constraint: $t_4 \neq A$.
Total $3! = 6$. Subtract cases where $t_4 = A$. If $t_4=A$, remaining I, C in 1, 3 ($2! = 2$ ways).
Valid ways = $6 - 2 = 4$.Case 3: L's at positions 4 and 5.
Remaining positions: 1, 2, 3. Remaining characters: I, A, C.
Constraint: $t_2 \neq I$.
Total $3! = 6$. Subtract cases where $t_2 = I$. If $t_2=I$, remaining A, C in 1, 3 ($2! = 2$ ways).
Valid ways = $6 - 2 = 4$.Total valid permutations = $4 + 4 + 4 = 12$.