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

@Deepak Poonia Sir, it will be helpful if you make a video on this question sir.

---

Is this a question can be solved in actual paper? maybe no, because nothing is trivial or assumable even the options are not understandable. 

But let me explain after reading all the answers the question in simple terms.

Take N = {1,2,3}

now permutation (π) from N to N means that from N to N we have a one-one function such that it is just a permutation.

like 1 mapped to 1 or 1 mapped to 2 or 1 mapped to 3 and so on.

now there are 3 choices for 1 to map ( with any of 1, 2 or 3)

2 choices for 2 to map and 1 choice for 3 to map, for n elements a total of n! choices.

-------------------------------------------------------------------------------------------------------------------------------

now we have to choose two subsets from N (our N has only 3 elements = 1,2,3)

Let A = {1,2} B = {2,3}

--------------------------------------------------------------------------------------------------------------------------------

π(N) : A set of integers that has element after applying permutation to each element of set N

meaning, for let A: 1 is mapped to 2, 2 is mapped to 3 and 3 is mapped to 1

we will have π(N) = {π(1), π(2), π(3)} = {2, 3, 1}

and now min(π(N)) is the min element in π(N) whichi is 1.

 

the question ask that how many permutation are possible such that min(π(A)) = min(π(B)) for two arbitrary subsets of A and B

 

now let's check this

N = {1,2,3}

subset A = {1,2}

subset B = {2,3}

Serial number	Total permutations			π(A) = element 1 and 2	π(B) = element 2 and 3	min(π(A) = min (π(B)
1	1 is mapped to 1	2 is mapped to 2	3 is mapped to 3	{1,2}	{2,3}	1 = 2
2	1 is mapped to 1	3 is mapped to 2 (2 domain 3 codomain)	2 is mapped to 3 (3 domain 2 codomain)	{1,3}	3,2}	1 = 2
3	2 is mapped to 1	1 is mapped to 2 (2 domain 1 codomain)	3 is mapped to 3	{2, 1}	{1,3}	1 = 1
4	2 is mapped to 1	3 is mapped to 2 (2 domain 3 codomain)	1 is mapped to 3 (3 domain 1 codomain)	{2,3}	{3,1}	2 = 1
5	3 is mapped to 1	1 is mapped to 2 (2 domain 1 codomain)	2 is mapped to 3 (3 domain 2 codomain)	{3,1}	{1,2}	1 = 1
6	3 is mapped to 1	2 is mapped to 2	1 is mapped to 3 (3 domain 1 codomain)	{3,2}	{2,1}	2 = 1

we can observe that only for two cases minπ(A) = minπ(B)

therefore for n = 3 only 2 permutations make minπ(A) = minπ(B)

checking with options, only option (C) satisfies.

 

---

 

1. Start with the set N

We have:

N = {1, 2, ..., n}

This is a set.

A set has no order. For example:

{1, 2, 3} = {3, 1, 2}

They are the same set.

We are also given two subsets:

A is a subset of N, and B is a subset of N.

For example, suppose:

N = {1, 2, 3, 4, 5}

A = {1, 3, 5}, and B = {2, 3, 4}

Notice:

A intersection B = {3}

and

A union B = {1, 2, 3, 4, 5}

2. What is a permutation pi?

This is the most important part.

A permutation of N is a bijection from N to N.

That means every element gets mapped to another element, with no two elements getting mapped to the same element.

For example, for:

N = {1, 2, 3, 4, 5}

we could have:

pi(1) = 4
pi(2) = 1
pi(3) = 5
pi(4) = 2
pi(5) = 3

We can write this permutation as:

(4, 1, 5, 2, 3)

This means:

1 -> 4
2 -> 1
3 -> 5
4 -> 2
5 -> 3

So your earlier understanding was basically correct:

A permutation gives an arrangement/mapping of the elements.

And there are n! different permutations.

3. What does pi(A) mean?

This is another important point.

If:

A = {1, 3, 5}

then:

pi(A) = {pi(1), pi(3), pi(5)}

Using our permutation:

pi(1) = 4
pi(3) = 5
pi(5) = 3

Therefore:

pi(A) = {4, 5, 3}

Since this is a set, we can write:

pi(A) = {3, 4, 5}

Then:

min(pi(A)) = 3

4. What is the question actually asking?

The question asks us to count permutations satisfying:

min(pi(A)) = min(pi(B))

In words:

After applying the same permutation pi to both A and B, their smallest elements should be the same.

Let's use a simple example.

Suppose:

A = {1, 3, 5}

and

B = {2, 3, 4}

Take the permutation:

pi = (4, 1, 5, 2, 3)

Then:

pi(A) = {pi(1), pi(3), pi(5)}

= {4, 5, 3}

so:

min(pi(A)) = 3

And:

pi(B) = {pi(2), pi(3), pi(4)}

= {1, 5, 2}

so:

min(pi(B)) = 1

Therefore:

min(pi(A)) is not equal to min(pi(B))

This permutation doesn't work.

5. When CAN the two minimums be equal?

This is the key insight.

Suppose:

min(pi(A)) = min(pi(B)) = x

Since x is in pi(A), we know:

x is in pi(A)

Since x is also in pi(B):

x is in pi(B)

Therefore:

x is in pi(A) intersection pi(B)

Because a permutation preserves intersections:

pi(A) intersection pi(B) = pi(A intersection B)

Therefore:

x is in pi(A intersection B)

This means the common minimum MUST come from an element of A intersection B.

That's the central idea.

6. Why does A union B appear?

Now let's think about what is competing to become the minimum.

Every element in either A or B can potentially become the minimum.

Those elements are exactly:

A union B

So we're looking at the elements of:

pi(A union B)

Among them, exactly one will be the smallest.

For the condition:

min(pi(A)) = min(pi(B))

to hold, that smallest element must come from:

pi(A intersection B)

Therefore:

The smallest element of pi(A union B) must belong to pi(A intersection B).

7. Now comes the counting trick

Let:

|A union B| = k

and:

|A intersection B| = r

There are k elements in A union B.

After permutation, any one of those k elements is equally likely to become the smallest.

So there are:

k

possible candidates for the minimum.

Among those k elements, exactly:

r = |A intersection B|

are elements of the intersection.

Therefore, the fraction of cases where the minimum comes from the intersection is:

|A intersection B| / |A union B|

8. But the question asks NUMBER, not probability

This is where n! comes in.

There are:

n!

total permutations of N.

If the required condition happens for the fraction:

|A intersection B| / |A union B|

of all permutations, then the number of successful permutations is:

n! × |A intersection B| / |A union B|

Thus:

n! × |A intersection B| / |A union B|

which is option C.

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

did you got the reason for this permutation?

---

uhuu....not getting

---

Take N = {1,2,3}, A = {1,2}, B = {2,3}. 

"π(S) is the set of integers obtained by applying π to each element of S"

With A = {1,2}: π(A) = {π(1), π(2)}
With B = {2,3}: π(B) = {π(2), π(3)}

"min(S) is the smallest integer in S":
min{π(1), π(2)} = min{π(2), π(3)}

For both minimums to be equal, both sides must contain 1, that is π(A∩B) = π(2) = 1. 

π(1) and π(3) take the remaining labels {2,3}, which gives 2! = 2 ways.

 

Now fastest method for exam is plug the example into the options

Here n = 3, |A| = 2, |B| = 2, |A∪B| = 3, |A∩B| = 1, and the correct count is 2.

• (A) (n − |A∪B|)·|A|·|B| = (3 − 3)·2·2 = 0 ✗
• (B) (|A|² + |B|²)·n² = (4 + 4)·9 = 72 ✗
• (C) n!·|A∩B|/|A∪B| = 6·1/3 = 2 ✓
• (D) |A∩B|² / ³C₃ = 1/1 = 1 ✗

Answer 2

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

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

Comments

Respect ++

---

Made an account just to upvote

---

"Best answer" should be this one 

Answer 3

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 4

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 5

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 6

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

Comments

Easiest of all I have read, this solution is best to understand how to solve it in gate in under 2-3 minutes, thanks for bringing it here from quora🙏