The GATE Grind

GATE 2023 CS – Question 48

Engineering Mathematics · Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) · 2 marks · Multiple choice

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?

  1. $n!$
  2. $\binom{n}{2k}(n-2k)!$
  3. $\binom{n}{2k}(n-2k)!\,(k!)^2$
  4. $2\binom{n}{2k}(n-2k)!\,(k!)^2$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $2\binom{n}{2k}(n-2k)!\,(k!)^2$

Explanation

Choose the 2k positions for A∪B in C(n,2k) ways. Fill the first k of them with A and the last k with B (or the reverse, giving factor 2), in (k!)² ways, and arrange the other n−2k elements in (n−2k)! ways.