GATE CS 2023 Q.48: Combinatorics, Counting, Recurrence Relations and Generating Functions

Let $U = \{1, 2, \dots, 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$ ?

$n!$

$\binom{n}{2k} (n - 2k)!$

$\binom{n}{2k} (n - 2k)! (k!)^2$

$2 \binom{n}{2k} (n - 2k)! (k!)^2$

Official answer and solution

Official answer: D
From: Official GATE 2023 answer key

Solution

Use combinatorics to choose positions and orderings for subsets $A$ and $B$ .

We want to construct a permutation of $U$ of size $n$ separating $A$ from $B$ , where $|A| = |B| = k$ and $A \cap B = \emptyset$ :

The total number of elements in $A \cup B$ is $2k$ . In any permutation of $n$ elements, we choose $2k$ positions among the $n$ available slots in $\binom{n}{2k}$ ways.
The remaining $n - 2k$ elements of $U \setminus (A \cup B)$ can be placed in the remaining slots in $(n - 2k)!$ ways.
For the $2k$ $2 k$ selected positions:
- Case 1 (All $A$ before all $B$ ): The first $k$ of these positions must be filled by elements of $A$ ( $k!$ ways), and the remaining $k$ positions by elements of $B$ ( $k!$ ways). This gives $(k!)^2$ ways.
- Case 2 (All $B$ before all $A$ ): The first $k$ positions are filled by $B$ ( $k!$ ways) and the remaining $k$ by $A$ ( $k!$ ways). This gives $(k!)^2$ ways.
- Since $k \ge 1$ , these two cases are mutually exclusive.
Combining these gives: $2 \times \binom{n}{2k} \times (n - 2k)! \times (k!)^2$

Thus, Option (D) is correct.

Final answer

Option (D)

Common trap

Omitting the factor of 2 (accounting only for $A$ before $B$ and forgetting $B$ before $A$ ).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2023 Computer Science and Information Technology (CS)
Question: 48 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source