edited by
11,072 views
58 votes
58 votes

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$?

  1. $(n - |A ∪ B|) |A| |B|$
  2. $(|A|^{2} + |B|^{2})n^{2}$
  3. $n! \frac{|A ∩ B|}{|A ∪ B|}$
  4. $\dfrac{|A ∩ B|^2}{^n \mathrm{C}_{|A ∪ B|}}$
edited by

7 Answers

Best answer
40 votes
40 votes
$\min(π(N)) = 1$, since in a permutation of $n$ elements from $1\dots n$, some element must get $1$.

Similarly, in any subsets $A$ and $B$, $\min(π(A)) = \min(π(B))$ only if $A$ and $B$ has a common element and it is the smallest of all the other elements in $A$ and $B$.

(With this understanding itself we can eliminate options $A$ and $B$)

Now we have n! total permutations and we have to see the number of permutations satisfying the given condition. If $A = B$, all of the n! permutations satisfy the given condition. (This is enough to get the answer as $C$). Otherwise, the fraction of the $n!$ permutations satisfying the given condition

$\qquad =|A \cap B| / | A \cup B|$

This is because without the given restriction, the smallest element (among the $|A \cap B|$ elements) can be any one of the $|A \cup B|$ elements, and with the restriction, the smallest element must be one of the $|A\cap B|$ elements.

So, answer is $C$.
edited by
54 votes
54 votes

I have explained with an example...so it is bit big.

Here is link : https://drive.google.com/open?id=1twqnDTFHKZNFYE3oPLUA8bPOUwhyOvH4

edited by
10 votes
10 votes

First let us understand what question is asking.

So π is a function from N to N, which just permutes the elements of N, so there will be n! such permutations.

Now given a particular π i.e. given a particular permutation scheme, we have to find number of permutations out of these n! permuations in which minimum elements of A and B after applying π to them are same.

So for example, if N = {1,2,3}, π is {2,3,1}, and if A is {1,3}, then π(A) = {2,1}. Now number of elements in A ∪ B is |A ∪ B|.

We can choose permutations for A ∪ B in nC|A∪B| ways. Note that here we are just choosing elements for permutation, and not actually permuting. Let this chosen set be P. Now once we have chosen numbers for permutations, we have to select mapping from each element of A ∪ B to some element of P. So first of all, to achieve required condition specified in question, we have to map minimum number in P to any of the number in A ∩ B, so that min(π(A)) = min(π(B)). We can do this in |A∩B| ways, since we can choose any element of |A∩B| to be mapped to minimum number in P. Now we come to permutation. We can permute numbers in P in |A∪B-1|! ways, since one number (minimum) is already fixed. Moreover, we can also permute remaining n - |A∪B-1| in (n - |A∪B-1|)! ways, so total no. of ways = nC|A∪B|∗|A∩B|∗|A∪B−1|!∗(n−|A∪B−1|)!=n!|A∩B||A∪B| So option (C) is correct. Note: Some answer keys on web have shown answer as option (D), which is clearly incorrect. Suppose |A ∪ B| = 3, and |A ∩ B| = 1, and n = 4, then option (D) evaluates to 14=0.25, which doesn't make sense. Source: http://www.cse.iitd.ac.in/~mittal/gate/gate_math_2006.html

9 votes
9 votes

First of all, out of the $n$ elements in set $Y$ we chose $|A\cup B|$ elements in $^n C_{|A\cup B|}$ ways for the $|A\cup B|$ elements in $X$.Having chosen these $|A\cup B|$ elements we map the remaining $(n-|A\cup B|)$ elements of $X$ to $(n-|A\cup B|)$ elements of $Y$ in all possible ways. This can be done in $(n-|A\cup B|)!$ ways. Out of the $|A\cup B|$ elements chosen from $Y$ we take the least of them and map any one of the $|A\cap B|$ elements present in $A\cap B$ to it. This can be done in $|A\cap B|$ ways. Having assigned the minimum element we take the remaining $(|A\cup B|-1)$ elements of $A\cup B$ in $X$ and map them in all possible ways to the remaining $(|A\cup B|-1)$ of the chosen $|A\cup B|$ of $Y$. This can be done in $(|A\cup B|-1)!$ ways.

So the required answer=

$$^n C_{|A\cup B|}*(n-|A\cup B|)! * |A\cap B|*(|A\cup B|-1)!$$

$$=\frac{n!}{|A\cup B|!*(n-|A\cup B|)!} *(n-|A\cup B|)! *|A\cap B|*(|A\cup B|-1)!$$

$$=\frac{n!}{|A\cup B|!}*|A\cap B|*(|A\cup B|-1)!$$

$$=\frac{n!}{|A\cup B|}*|A\cap B|$$

Hence answer is $(C)$.

Answer:

Related questions

25 votes
25 votes
7 answers
1
Rucha Shelke asked Sep 17, 2014
6,450 views
Let $E, F$ and $G$ be finite sets. Let$X = (E ∩ F) - (F ∩ G)$ and$Y = (E - (E ∩ G)) - (E - F)$.Which one of the following is true?$X ⊂ Y$$X ⊃ Y$$X = Y$$X - Y �...
26 votes
26 votes
3 answers
2
Ishrat Jahan asked Oct 31, 2014
6,439 views
What is the cardinality of the set of integers $X$ defined below?$X=\{n \mid 1 \leq n ≤ 123, n$ is not divisible by either $2$, $3$ or $5\}$$28$$33$$37$$44$
33 votes
33 votes
5 answers
4