Let U = {1, 2,...,n}, where n is a large positive integer greater than 1000.…

GATE · 2023 · CS · Computer Science & IT

Let U = {1, 2,...,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 ∩ B = ∅. 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. A.

    n!n!

  2. B.

    (n2k)(n−2k)!\binom{n}{2k} (n - 2k)!

  3. C.

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

  4. D.

    2(n2k)(n−2k)!(k!)22 \binom{n}{2k} (n - 2k)! (k!)^2

Attempted by 125 students.

Sign up free to check your answer

Sign up free

Explore the full course: Aptitude For Gate

Loading lesson…