The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+28 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|}}$
asked in Set Theory & Algebra by Active (3.3k points)
edited by | 2.5k views
please give answer with clear explanation.

Please refer -->π-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.....

3 Answers

+23 votes
Best answer
$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$.
answered by Veteran (407k points)
edited by
The common element has to be minimum in both the subsets, only then we will count it.
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?
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  

Really one of the tough QS.Thanks everyone for nice Ans as well as Discussion.
@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
$\pi$ is a permutation not a function. Else all elements can even map to a single one.
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
@Arjun sir, can you show it pictorially by taking n as 2 or that I can understand it with full confidence...

@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
+7 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:

answered by Loyal (9.3k points)
+2 votes
answered by Loyal (7.5k points)
edited by
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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,535 questions
54,120 answers
71,034 users