GATE CSE 2015 Set 2 | Question: 40

Question

The number of onto functions (surjective functions) from set $X = \{1, 2, 3, 4\}$ to set $Y=\{a,b,c\}$ is ______.

Comments

hope you find this helpful 

you can also refer → https://www.youtube.com/watch?v=h9BZFnWQ46A&ab_channel=NPTEL-NOCIITM

---

@Mohitdas   i am little bit confused in page number 1, f is onto only when co-domain =Range so far a,b,c “at least 2 element” or  (“At most 2 element”)will be pointing to either ‘a’ or ‘b’ or ‘c’. 

---

$\color{red}{\text{Detailed Video Solution, with Alternative Ways to Solve:}}$ https://youtu.be/-9HQqDyVG5k 

Answer 1

Problem :

we have 4 elements in domain and 3 elements in co-domain. We want to know no of onto functions(Surjective functions) possible.

Concept :

a function from set A to set B is onto if each element of B is associated with atleast one element of A. Here A is domain And B is Co-domain. Also we know that Range is subset of Co-domain such that all elements in it is associated to atleast one element of domain. so in case of onto functions Range = Co-domain.

Generalization of formula for no of onto functions:

look we cant directly derive a formula for it so we go for an indirect approach known as inclusion and exclusion. in this method we calculate total no of functions possible and then subtract the functions that do not follow rule to become onto functions.

so as domain A has 4 elements {1,2,3,4} and co-domain has 3 elements {a,b,c} then total no of functions possible is 3^4 = 81(because every element in domain has 3 choices such that they can be associated to co-domain).

now in all these functions, the functions that has even a single element in co-domain that has no associativity with any element of domain will not be onto so we have to subtract it from total.

scenario 1:  any one of 3 elements of co-domain is isolated(means no one associated to it),hence each 4 element of domain A has only two choices left, so no. of functions possible in this case = 2^4. And it can be done in 3 ways(1. a is isolated, 2. b is isolated , 3. c is isolated)

so for this scenario total no of functions = 3C1*(2^4) = 3*16 = 48.

so at this moment we can say no of required functions may be(suppose X) 81-48 = 33

but scenario 1 included some combinations where All element of domain A is associated to only one element of co-domain B and these scenarios are counted twice in each case like if a is isolated then out of 2^4 possible functions there is a function where all domain elements associated to element b of Co-domain and also there is a function where all domain elements associated to element c of Co-domain B and similarly when b is isolated then there are functions such that all elements of domain A is associated to element c of co-domain B so this function is counted twice and was subtracted twice unnecessarily. now we have to find all such functions and  include in X.

 

scenario 2:  any two of 3 elements of co-domain is isolated,hence each 4 element of domain A has only 1 choices left, so no. of functions possible in this case = 1^4. And it can be done in 3 ways(1. a,b is isolated, 2. b,c is isolated , 3. c,a is isolated)

so total 3C2*(1^4)= 3*1=3.

so including these in X = 33+3=36.

 

so,

total no of onto functions = total no. of function-(no. of functions when 1 element of co-domain is isolated)+(no. of functions when 2 element of co-domain is isolated)

=3^4-[3C1*(2^4)]+3C2*(1^4) = 81-48+3 = 36.

                                                                                                                                                 

In general no. of onto functions if domain has m elements and co-domain has n elements=

 $\sum_{i=0}^{n} (-1)^i * {^nC}i * (n-i)^m$

 

 

 

 

 

Answer 2

.

Answer 3

.