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

Surjective function : when co- domain = range so X={1,2,3,4} to Y={a,b,c} i

s from 4 element choose any two and map to element 'a' of Y so 4c2 = 6 posibility

from remaining 2 choose 1 map to any other element to Y = 2c1= 2

remaing one may directly one way     only so 6*2*1= 12 ways

now from 4 element choose any two and map to element 'b' of Y so 4c2 = 6 posibility

from remaining 2 choose 1 map to any other element to Y = 2c1= 2 r

emaing one may directly one way     only so 6*2*1= 12 ways

from 4 element choose any two and map to element 'b' of Y so 4c2 = 6 posibility

from remaining 2 choose 1 map to any other element to Y = 2c1= 2

remaing one may directly one way only so 6*2*1= 12 ways

total ways = 12+12+12=36

Answer 2

My approach to solve this is some story, sorry plz!

Let, 'a' our boss so he can rule on 2 elements possibly {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)} (try to make pair only in this direction 1-->2-->3-->4)

now remaining two slaves 'b' and 'c' can have only one of two elements.

so this way total 12 ways possible for ex { [a-1,2 , b-3 , c-4 , a-1,2 , b-4 , c-3],...}  12 possibilities 

Now, it's time to make 'b' as a boss and 12 possibilities 

Now, it's time to make 'c' as a boss and 12 possibilities 

so, total 12+12+12=36

P.S. this may sound weired but story is the medicine to remember something!

Comments

good:))

Answer 3

Another way to solve this problem. 

$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	Total (Row wise)
a	a	b	c	$\frac{(4!)}{(2!)(1!)(1!)}$
a	b	b	c	$\frac{(4!)}{(2!)(1!)(1!)}$
a	b	c	c	$\frac{(4!)}{(2!)(1!)(1!)}$
			Final Total	3*(3*4) = 36

Comments

I thought in the same way.

There are $4$ distinct places and $3$ distinct elements. So there must have 2 same elements e.g.

$aabc,~bbac,~ccab$. Therefore, the answer is $3\times \frac{4!}{2!}=36$.

Answer 4

One way of solving it can be:

Choose two numbers from X to be mapped to one element in Y -> $\binom{4}{2} * 3$
Now we are left with 2 elements in X and 2 elements in Y we can have only two possible ways.

Total =>  $\binom{4}{2} * 3$ * 2 = 36