GATE 2023 CS Q.48: solution and answer

GATE 2023 · CSQ.48 · 2 marks · MCQ

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$ ?

(A)
$n!$
(B)
$(2 k n) (n - 2 k)!$
(C)
$(2 k n) (n - 2 k)! (k!)^{2}$
(D)
$2 (2 k n) (n - 2 k)! (k!)^{2}$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The number of permutations that separate $A$ from $B$ is $2 (2 k n) (n - 2 k)! (k!)^{2}$ , option (D).

Official answer: DSource: Official answer key, GATE 2023 CS (IIT Kanpur)

Count the permutations in which every member of $A$ comes before every member of $B$ , then double the count for the symmetric case in which $B$ comes first.
Choose which $2 k$ of the $n$ positions hold the members of $A \cup B$ . This can be done in $(2 k n)$ ways.
Read those $2 k$ positions from left to right. For $A$ to come entirely before $B$ , the first $k$ of them must hold $A$ and the last $k$ must hold $B$ . This is forced, so it adds no extra choice.
Arrange the $k$ members of $A$ in their $k$ positions in $k!$ ways. Arrange the $k$ members of $B$ in their $k$ positions in $k!$ ways.
Arrange the remaining $n - 2 k$ elements of $U$ in the remaining $n - 2 k$ positions in $(n - 2 k)!$ ways.
The number of permutations with $A$ entirely before $B$ is $(2 k n) (n - 2 k)! (k!)^{2}$ .
The number with $B$ entirely before $A$ is the same, by symmetry. The two cases cannot overlap: $A$ and $B$ are disjoint and non-empty, so a permutation cannot have both $A$ before $B$ and $B$ before $A$ .
Total: $2 (2 k n) (n - 2 k)! (k!)^{2}$ , which is option (D).
Check on small cases. For $n = 2$ , $k = 1$ : the formula gives $2 \cdot (2 2) \cdot 0! \cdot 1 = 2$ , and both permutations of ${a, b}$ separate. For $n = 3$ , $k = 1$ : the formula gives $2 \cdot 3 \cdot 1 \cdot 1 = 6 = 3!$ , and every permutation separates two single elements.

KEY IDEA

Pick the positions of $A \cup B$ , and the order within them is forced (the first $k$ for one set, the last $k$ for the other). Then arrange each group and the rest, and multiply by 2 for the two possible orders of the sets.

WATCH OUT FOR

Forgetting the factor 2 for $B$ appearing before $A$ gives option (C). Forgetting the internal orderings $(k!)^{2}$ gives option (B).

From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 6 Counting questions, with notes

GATE 2023 CS Q.48: solution and answer

Answer and solution

More Counting questions