GATE CS 2023 Q38 — Combinatorics: Counting, Recurrence Relations, Generating Functions

To find the number of permutations of $U$ that separate $A$ from $B$, we can break down the construction of any such permutation into three independent steps:

1. Choose the positions for the elements of $A \cup B$:

   The total number of elements in $A \cup B$ is $|A| + |B| = 2k$ (since $A \cap B = \emptyset$). Out of the $n$ available positions in the permutation, we choose $2k$ positions to place the elements of $A \cup B$.

   Number of ways to choose these positions = $\dbinom{n}{2k}$

2. Arrange the remaining elements:

   The remaining $n - 2k$ elements of $U \setminus (A \cup B)$ must be placed in the remaining $n - 2k$ positions.

   Number of ways to arrange these elements = $(n - 2k)!$

3. Arrange the elements of $A$ and $B$ in the chosen $2k$ positions:

   According to the definition of separation, there are two mutually exclusive cases:

   • Case 1: All elements of $A$ appear before all elements of $B$.
     The first $k$ of the chosen $2k$ positions must be occupied by elements of $A$, and the remaining $k$ positions by elements of $B$.
     Number of ways = $k! \times k! = (k!)^2$
   • Case 2: All elements of $B$ appear before all elements of $A$.
     The first $k$ of the chosen $2k$ positions must be occupied by elements of $B$, and the remaining $k$ positions by elements of $A$.
     Number of ways = $k! \times k! = (k!)^2$

   Total ways to arrange $A$ and $B$ in the chosen positions = $(k!)^2 + (k!)^2 = 2(k!)^2$

By the product rule, the total number of such permutations is:

Hence, the correct option is D.