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 be a set of exactly k elements from U. Let B = U \ A (the complement of A in U). We say a permutation of U separates A from B if all members of A appear before any member of B, OR all members of B appear before any member of A. How many permutations of U separate A from B?
A. k!(n-k)!
B. 2 * k!(n-k)!
C. C(n,k)
D. 2 * C(n,k)
GATE 2023 · Discrete Mathematics · Counting · medium
Answer: 2 * k!(n-k)!
Choose which group occupies the first block: Either all of A comes first (followed by all of B), or all of B comes first (followed by all of A). That gives 2 ways to assign the block order.
Arrange elements within each block: The k elements of A can be arranged within their block in k! ways. The n-k elements of B can be arranged within their block in (n-k)! ways. By the product rule these multiply: k! * (n-k)!.
Combine block order with internal arrangements: Total = (block order choices) * (A internal arrangements) * (B internal arrangements) = 2 * k! * (n-k)!.