retagged by
1,442 views

2 Answers

Best answer
11 votes
11 votes

Number of surjective funtions (onto or co-domain = range) from a set of $m$ elements to a set of $n$ elements is same as putting $m$ distinct balls to $n$ distinct buckets such that no bucket is empty. For $m=6, n= 5$, this is given by $S(6,5)*5! = 15 * 120 = 1800$.

But, here we have an additional constarint that $f(6) =3$ for all the functions. So, our answer must be less than 1800. 

To find this, we can consider 2 cases

  1. Let no element map to 3 from $A-\{6\}$, and then add the mapping $(6,3)$.
  2. Let all elements from $A-\{6\}$ map to all elements of $B$ and then add the mapping $(6,3)$.

Since in each case we are considering surjective mappings (co-domain = range) we are sure that both these cases are mutually exclusive and for the total cases, simple addition is enough. (In the first case 3 is mapped to by just 6, in in the second case 3 is mapped to by at least two elements including 6).

So, now for 1, it is same as number of surjective functions from a set of 5 elements to a set of 4 elements which is $S(5,4)*4! = 10*24= 240$.

For 2, it is same as the number of surjective functions from a set of 5 elements to a set of 5 elements which is $5! = 120$.

Thus totally we can have $240+120=360$ such surjective functions.


$S(m,n)$ is Stirling's number of second kind and is given by the number of ways of partitioning a set of $m$ elements to $n$ partitions. So,

$S(m,1) = S(m,m) = 1$

$S(m,n) = S(m-1, n-1) + n S(m-1, n)$ // This needs explanation

So, $S(3,2) = S(2,1) + 2S(2,2) = 1+ 2 = 3$. 

So, we get the triangle

1
1 1
1 3 1
1 7 6 1
1 15 25 10 1

which can be extended as required using the formula $S(m,n) = S(m-1, n-1) + n S(m-1, n)$

edited by
5 votes
5 votes

Given A = { 1 , 2 , 3 , 4 , 5 , 6 }

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

so cardinality of A , say m  =  6 and

   cardinality of  B , say n   =  5.

Now we have to calculate no of surjective functions f : A --> B with the additional constraint that f(6) = 3.

Thus we have to ensure that 6 of A is not mapped to any other element of B except 3.

So there are two ways :

1. map 6 to 3 then consider other 5 elements from set A maps to Any elemets to B.(3 is mapped by other also)

2.map 6 to 3 then consider other 5 elements from set A maps to 4 elemets to B except 3.(3 is not mapped by other also)

Let m = 5 (excluded the element 6) and n = 5.We know if a set A contains m elements and B contains n elements , then number of onto (surjective) functions from A to B :

=  nm  -  nC1(n-1)m  + nC2(n-2)m........[We continue finding sum till n - k does not becomes 0 and this result comes from inclusion exclusion principle ]

1st case: So substituting n = 5 , m = 5 , we have :

No of onto functions = 55   -   5C1(4)5 +  5C2(3)5  -  5C3(2)5  +  5C4(1)5

                                        = 3125  -  5 * 1024  +  10 * 243  -  10 * 32  +  5

                              = 120

2nd case: So substituting n = 5 , m = 4 , we have :

No of onto functions = 45   -   4C1(3)5 +  4C2(2)5  -  4C3(1)5 

                                        = 1024  -  4 * 243  +  6 * 32  -  4 

                              = 240

Therefore ,

Total number of onto functions from A to B  =  120 + 240 = 360

edited by

Related questions

3 votes
3 votes
2 answers
1
shikharV asked Dec 31, 2015
578 views
Let $A = \left \{1, 2, 3, 4 \right \}$. Number of functions possible on $A$ which are neither $1-1$ nor on-to is _________.
3 votes
3 votes
1 answer
2
Shashank Chandekar asked Oct 20, 2016
527 views
Given $x,y,z$ are Boolean variables and $f(x,y,z)=f(y',x',z)$. How many such functions are possible with $x, y, z$?$0$$2^2$$2^4$$2^6$