Given a set of elements N = {1, 2, ..., n} and two arbitrary subsets A ⊆ N and…
2006
Given a set of elements N = {1, 2, ..., n} and two arbitrary subsets A ⊆ N and B ⊆ N, how many of the n! permutations π from N to N satisfy min(π(A)) = min(π(B)), where min(S) is the smallest integer in the set of integers S, and π(S) is the set of integers obtained by applying permutation π to each element of S?
- A.
(n - |A ∪ B|) |A| |B|
- B.
(|A|2 + |B|2)n2
Attempted by 71 students.
Show answer & explanation
To solve this problem, we need to count the number of permutations π of the set N = {1, 2, ..., n} such that min(π(A)) = min(π(B)).
Step 1: The minimum value of π(A) and π(B) must be the same. Let this common minimum be k. For k to be the minimum of both π(A) and π(B), k must be the image of some element x in A ∩ B, because only elements in the intersection can be the smallest in both sets.
Step 2: For a fixed element x in A ∩ B, the condition that π(x) is the minimum of π(A ∪ B) is necessary and sufficient for min(π(A)) = min(π(B)) = π(x). This is because if π(x) is the smallest in π(A ∪ B), it will be the smallest in both π(A) and π(B).
Step 3: The number of permutations where a specific element y in A ∪ B is the smallest in π(A ∪ B) is n! / |A ∪ B|. This is because, among the |A ∪ B| elements in π(A ∪ B), each is equally likely to be the smallest, and there are n! total permutations.
Step 4: For each x in A ∩ B, the number of permutations where π(x) is the smallest in π(A ∪ B) is n! / |A ∪ B|. Since there are |A ∩ B| such elements, the total number of permutations satisfying the condition is |A ∩ B| * n! / |A ∪ B|.
Therefore, the number of permutations π such that min(π(A)) = min(π(B)) is |A ∩ B| * n! / |A ∪ B|.