Let U = {1, 2,...,n}, where n is a large positive integer greater than 1000.…
2023
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?
- A.
\(n!\) - B.
\(\binom{n}{2k} (n - 2k)! \) - C.
\(\binom{n}{2k} (n - 2k)! (k!)^2 \) - D.
\(2 \binom{n}{2k} (n - 2k)! (k!)^2 \)
Attempted by 39 students.
Show answer & explanation
Correct answer: D
We count permutations in which all elements of A appear before all elements of B, and then double to account for the opposite order.
Step 1: Choose which 2k positions (out of n) in the permutation are occupied by elements of A∪B: C(n,2k).
Step 2: If all members of A come before all members of B, then among those chosen 2k positions the first k (earliest) are occupied by the k elements of A in k! orders and the last k by the k elements of B in k! orders, giving k! · k! ways.
Step 3: Arrange the remaining n−2k elements in the leftover positions in (n−2k)! ways.
Putting these together, the number of permutations with A before B is C(n,2k) · (k!)^2 · (n−2k)!. Since B before A is a distinct scenario with the same count, multiply by 2.
Final answer: 2 · C(n,2k) · (k!)^2 · (n−2k)!. This can also be written in closed form as 2 · n! · (k!)^2 / (2k)!.