GATE CSE 2006 | Question: 24

Question

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

• A. $(n - |A ∪ B|) |A| |B|$
• B. $(|A|^{2} + |B|^{2})n^{2}$
• C. $n! \frac{|A ∩ B|}{|A ∪ B|}$
• D. $\dfrac{|A ∩ B|^2}{^n \mathrm{C}_{|A ∪ B|}}$

Comments

please give answer with clear explanation.

---

Please refer -->

https://math.stackexchange.com/questions/932082/how-many-of-the-n-permutations-π-from-set-n-to-n-satisfy-minπa-minπb

On the above link notice line -->

The permutation ρρ must send A∪BA∪B to any equal-sized subset of NN, and the desired outcome depends only on whether the least element of ρ(A∪B)ρ(A∪B) belongs to ρ(A∩B)ρ(A∩B).

It basically means all elements of A and B will exactly fit( because of 1-1 mapping) in bucket of size |A+B|. Now if common mini. exists it will lie in bucket |A.B|. Now minimum can lie anywhere in |A+B| space but desired space is |A.B| So desired fraction is |A.B|/|A+B| .

---

can someone elobrate i cant understand.....

---

Check this :  https://gateoverflow.in/987/gate2006-24?show=325705#a325705

Answer 1

$\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$.

Comments

@Arjun Sir please verify whether my below understanding is correct or not.

Since permutation of a given set is just arrangement of elements of the set, min(π(A)), min(π(B)) will be constant for any π ( min(π(A)) will be same for any π and similarly min(π(B)) will be same for any π).

So, for given N , A , B either for all of the n! permutations min(π(A))=min(π(B))  or  for all of the n! permutations min(π(A))!=min(π(B)) . So the number of the n! permutations π from N to N satisfy min(π(A)) = min(π(B)) is either n! or 0.

I think here we are actually counting expected value (Expectation) .Let x be a random variable which denotes the number of the n! permutations π from N to N satisfy min(π(A)) = min(π(B) .

E(x) = n! * |A ∩ B|/| A ∪B| + 0* (1 - |A ∩ B|/| A ∪B| ) [ since x  will be either n! or 0, and x will be equal to n! iff  any element from A ∩ B is the smallest element of A as well as B hence, probability of x=n! is  |A ∩ B|/| A ∪B|. Similarly x will be equal to 0 iff smallest element  of A and B are different ]

Hence Expected value= n! * |A ∩ B|/| A ∪B|.

If A and B are given then we can surely count the number of the n! permutations π from N to N satisfy min(π(A)) = min(π(B) (which will be either n! or 0), but since elements of A , B are not particularly mentioned in the question so, only thing which we can do is , do some probabilistic analysis and find out the expected value.

 

---

How this is happening if A is {1,3}, then π(A) = {2,1}.  How permutation of A is giving {2,1} ?? Someone please explain

---

did you got the reason for this permutation?

Answer 2

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

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

Comments

The best explanation out there for this tough question. Surely the Best Answer. @Arjun Sir, make this the best ans.

---

What an explanation with an example! Best Explanation.Thank you very much. Great Effort. _/\_

---

just perfect!

Answer 3

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

Answer 4

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)$.