GATE 2023 CS – Question 48
Let $U = \{1, 2, \ldots, n\}$, where n is a large positive integer greater than 1000. Let k be a positive integer less than n. Let A, B be subsets of U with $|A| = |B| = k$ and $A \cap B = \emptyset$. We say that a permutation of U separates A from B if one of the following is true. - All members of A appear in the permutation before any of the members of B. - All members of B appear in the permutation before any of the members of A. How many permutations of U separate A from B?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (D) $2\binom{n}{2k}(n-2k)!\,(k!)^2$
Explanation
Let $|A|=|B|=k$ and count permutations of the $n$ elements that put all of $A$ before all of $B$ (or all of $B$ before all of $A$).
1. Choose which $2k$ of the $n$ positions will be occupied by elements of $A\cup B$: $\binom n{2k}$ ways.
2. Fill the **first $k$** of these positions with $A$ (in $k!$ orders) and the **last $k$** with $B$ ($k!$ orders): $(k!)^2$ ways. Or put $B$ first and $A$ last: another $(k!)^2$ ways. That gives a factor $2(k!)^2$.
3. Arrange the other $n-2k$ elements in the remaining positions: $(n-2k)!$ ways.
$$\text{Total}=2\binom n{2k}(n-2k)!\,(k!)^2:\text{ option (D)}.$$