3.4k views

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 | 3.4k views
+1
0

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

+1
can someone elobrate i cant understand.....
+1

$min(π(N)) = 1$, since in a permutation of n elements from $1$..$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

= $|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$.
by Veteran (434k points)
edited
0
thanks @Mayur
+3

@Arjun Sir, I have a silly doubt, suppose A = {1,2,3} then after applying π(A) what is the output? Is it  {123, 132, 213, 231, 312, 321} or something else?

+3
@Vikrant Yes. Those 6 are the possible outputs. i.e., we are just shuffling the numbers 1..n.
+1

I am not able to comprehend the question can someone help with this? Can someone give some example what it is exactly trying to say

+3

@arjun sir

@manoj,@sresath

let  A = {1,2,3} then after applying π(A) =  {123, 132, 213, 231, 312, 321}

let B={2,3,4} then π(B)={234,243,324,342,423,432}

from here what is min(π(A))=min(π(B))....

and given an example where we can find

+6
@Asu $\pi(A)$ is a permutation. So, for your case $\pi (A) = 123$ or any of the other 5 possible permutation but not the set of all permutations. Similarly for B. And $\min (\pi (A)) = 1$ and $\min (\pi (B)) = 2$ irrespective of the permutation given by $\pi$.
+1
thank q sir
0
Can we do like this...

if 1 is the common element then for all other elements we have 2^n-1 choices.

if we take 2 as common then 2^n-2...and so on

I am not able to proceed further
0
Will the same argument work if instead of min it was max or any other function?
0
How can we say that the smallest element of A will be the smallest element of B among the common elements of A and B? let say A has 2,3,4,5 and B has 3,4,5,6. then min(p(A))=2 and min(p(B))=3 i.e. they are not satisfying the condition but according to option we are counting it.
+1
The common element has to be minimum in both the subsets, only then we will count it.
0
for a chosen subset A and B, are wee taking permutations on all the elements, If so then how can this consition vary for different pemutation??

Example: if A={1 2 3} and B={2 3 4}, the condition doesnt hold. What is the exact meaning?
0
to satisfy the condition min(pi(A)) = min(pi(B)) min(A) should be equal to min(B) in that case only for each permutation of A  and B min (pi(A)) = min(pi(B)) it would be valid so in fav outcomes we should  check whether intersection of A and B is equal to  min of both or not and in total outcomes we should union of both sets and it would be valid for each permutation of A and B Therefore answer should be

n!|A∩B|/|A∪B|
+4
Really one of the tough QS.Thanks everyone for nice Ans as well as Discussion.
0
@Arjun Sir

π(S) permutation is defined on N ,say,1234 and A is subset.How when π(A) ,say π(1,2,3) ,now there can be chance that in π permutation 1 is matching to 4,but above you said that π(1,2,3) will have only permutaions from 1,2,3 but in set A ,there is no 4.

As per asu comment above:-

let  A = {1,2,3} then after applying π(A) =  {123, 132, 213, 231, 312, 321}

Now i dont think π(A) will always have permutations from 1,2,3. May be in the N we have a permutations which maps,1->4 and so on.

(1,2,3,4)=>(4,3,1,2)// one example of permutation on N which will be applied to A and B
+1
$\pi$ is a permutation not a function. Else all elements can even map to a single one.
+1
Sir, this is example i am quoting from below solution :-

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

Now here A is having 1,3 ,but it does not mean that π(A) will be {1,3} or {3,1}.It may have elements in N but not in A.I hope you understand my doubt
0
@Arjun sir, can you show it pictorially by taking n as 2 or 3....so that I can understand it with full confidence...
0

@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.

+1
How this is happening if A is {1,3}, then π(A) = {2,1}.  How permutation of A is giving {2,1} ?? Someone please explain
0
did you got the reason for this permutation?

Since explained with an example...so it is bit big

by Active (1.9k points)
+1
Thanks  sourajit. It really  helped  me.
0
thanks !
0
Thanks a lot and hats off If you have done it by yourself :)
0
Welcome :)

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

by Boss (10k points)
by Loyal (8.1k points)
edited by
0
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

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

by Loyal (7.7k points)