GATE CS 2006 Q24 — Sets, Relations and Functions

To find the number of permutations $\pi$ that satisfy $\min(\pi(A)) = \min(\pi(B))$, let us analyze the behavior of the minimum value over the union of the two sets, $A \cup B$.

Let $S = A \cup B$. For any permutation $\pi$, the minimum value of the image of $S$ is given by: $$\min(\pi(S)) = \min(\pi(A \cup B)) = \min\big(\min(\pi(A)), \min(\pi(B))\big)$$

Let $x \in S$ be the unique element that maps to this minimum value, i.e., $\pi(x) = \min(\pi(S))$.

• If $x \in A$ but $x \notin B$, then $\min(\pi(A)) = \pi(x) < \min(\pi(B))$.
• If $x \in B$ but $x \notin A$, then $\min(\pi(B)) = \pi(x) < \min(\pi(A))$.
• If $x \in A \cap B$, then $\min(\pi(A)) = \pi(x) = \min(\pi(B))$.

Probability/Symmetry Argument:

By symmetry, each of the $|A \cup B|$ elements in the union has an equal probability of being mapped to the minimum value among all elements in $\pi(A \cup B)$.

The number of favorable elements is $|A \cap B|$. Thus, the probability that a randomly chosen permutation satisfies the condition is: $$P = \frac{|A \cap B|}{|A \cup B|}$$

Since there are $n!$ total permutations of the set $N$, the number of permutations satisfying the condition is: $$\text{Number of permutations} = n! \times \frac{|A \cap B|}{|A \cup B|}$$

Hence, the correct option is C.