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

Please see the below Link for more understanding.

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

Comments

example of N={1,2,3}  with A={1,2} and B={2,3} we see that a permutation can act on N=A∪B in six ways. Of these, one-third will map 2∈A∩B to the minimum position. Therefore the total number of permutations such that min(ρ(A))=min(ρ(B)) is six times one-third according to answer given answer comes out to be 2 what does it represent does it mean that out of 6 permutation of N only 2 permutation satisfy for condition

Answer 2

n! |A ∩ B|/|A ∪ B|

Permutations are bijective functions. Hence min(π(A)) = min(π(B)) is possible iff the element in A which gives the lowest value of π(A) is also present in B and gives the lowest value of π(B). Thus we want min(π(A ∩ B)) = min(π(A ∪ B)). For each permutation, there is |A ∩ B|/|A ∪ B| probability that min(π(A ∪ B)) is provided by an element which is present in A ∩ B. Hence the total number of such permutations is n! |A ∩ B|/|A ∪ B|.

Source: https://www.quora.com/Given-a-set-of-elements-N-1-2-n-and-two-arbitrary-subsets-A-and-B-how-many-of-the-n-permutations-p-from-N-to-N-satisfy-min-p-A-min-p-B

Answer 3

easy to understand!

https://www.geeksforgeeks.org/gate-gate-cs-2006-question-24/