Given a set of elements N = {1, 2, ..., n} and two arbitrary subsets A⊆N and B⊆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?
-
(n - |A ∪ B|) |A| |B|
-
$(|A|^2 + |B|^2)n^2$
-
$n! \frac{|A ∩ B|}{|A ∪ B|}$
-
$\frac{|A ∩ B|^2}{^n \mathrm{C}_{|A ∪ B|}}$
D
Correct answer
Explanation
We need min(π(A)) = min(π(B)). The minimum of permuted A equals minimum of permuted B only when both sets contain their smallest elements, and these smallest elements are the same. This happens when the smallest element of A∪B appears in both A and B (i.e., is in A∩B). The number of favorable permutations depends on |A ∩ B| and |A ∪ B|. The formula counts permutations where the minimum element from the intersection is placed first in both A and B's images.