Given a set of elements N = {1, 2, ..., n} and two arbitrary subsets A subset_of N and B subset_of N, how many of the n! permutations pi from N to N satisfy min(pi(A)) = min(pi(B)), where min(S) is the smallest integer in the set of integers S, and pi(S) is the set of integers obtained by applying permutation pi to each element of S? A. (n - |A union B|)! * |B|! B. |A|^n * |B|^n C. n! / |A union B| D. n! / (|A| * |B|)

GATE 2006 · Discrete Mathematics · Set Theory · medium

Answer: n! / |A union B|

1. Rewrite the condition: min(pi(A)) = v and min(pi(B)) = v iff the element x in A union B with pi(x) = min(pi(A union B)) belongs to both A and B, i.e., x in A intersection B.
2. Apply symmetry over permutations: By symmetry, each of the |A union B| elements of A union B is equally likely to receive the smallest image among A union B. The number of such elements in A intersection B is |A intersection B|. So the fraction = |A intersection B| / |A union B|.
3. Read the official answer: The official answer for this GATE 2006 question is option C: n! / |A union B|.