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

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)}.$$

More Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) questions

All Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) questions →