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

We have $3$ elements in set $B$ and $4$ elements in set $A$ and surjection means every element in $B$ must be mapped to. So, this problem reduces to distributing $4$ distinct elements $(r = 4)$ among $3$ distinct bins $(n = 3)$ such that no bin is empty, which is given by $n! S(r, n),$ where $S(r, n)$ is Stirling's number of 2nd kind. So, here we need $S(4, 3).$

We have $S(r+1, n) = n* S(r, n) + S(r, n-1)$

So, Stirling numbers of second kind can be generated as follows:

$1$

$1\quad1$

$1\quad 3\quad 1$

$1\quad 7\quad 6\quad 1$

So, $S(4,3) = 6$ and $3! = 6$ giving, number of surjective functions $= 6*6 = 36.$

Ref: See Theorem 9:

http://www.cse.iitm.ac.in/~theory/tcslab/mfcs98page/mfcshtml/notes1/partset.html 

---

Alternative approach , 

Answer is $36.$
For onto function from a set A(m-element) to a set B(n-element), $m \geq n.$

Number of onto function $= n^m - ^nC_1(n-1)^m + ^nC_2(n-2)^m  -  ^nC_3(n-3)^m+\ldots +^nC_n(n-n)^m$

$(+,- $ alternative$)$

$$\bf{=\sum_{i=0}^n (-1)^i \;nC_i\;(n-i)^m}$$
Here $m=4$ and $n=3 $
So, number of onto functions

$\quad \quad = 3^4 - ^3C_1(3-1)^4 + ^3C_2(3-2)^4  -  ^3C_3(3-3)^4$
$\quad \quad = 81 - 3*16 +3*1 - 1*0$
$\quad \quad = 36.$
ref@ http://www.cse.iitd.ac.in/~mittal/stirling.html

Comments

Nice paper on counting functions

http://www.imsc.res.in/~vikram/DiscreteMaths/2011/twelvefold.pdf

---

@Arjun sir:As per your explanation

 

I think problem reduces to distributing 4 distinct elements among 3 non distinct bins (not distinct bins)such that no bin is empty.Stirling number of 2nd kind says that only.

 

Please clear my doubt

---

@Arjun

Sir Stirling number of second kind is defined for distinguishable and indistinguishable object as given in keneth rosen. Help me out to clear this doubt as you have mentioned that both should be distinct.

Answer 2

$\bf{Alternatively\; this\; is\; equivalent\; to\; putting \; 4 \; different\;balls \; into\; 3\; different\; boxes}$

$\bf{Such\; that\; each \; box\; contain\; atleast\; one\; ball}$

$\bf{So\; Possible\; arrangements\; as \; (2,1,1)\; and \; its \; Permutation\;.}$

$\bf{So\; Total\; no.\; of\; ways\; \displaystyle = \binom{4}{2}\times \binom{2}{1}\times \binom{1}{1}\times 3 = 36}$

Comments

best way to solve this type of questions.

---

Won’t there be 3! = 6 permutations?

---

@Amcodes We are choosing which one of the three boxes should we put the 2 balls initially (either a or b or c) which is 3 choices. It is the same as the number of permutations of (2,1,1) which is 3!/2! = 3.

Answer 3

hope this helps.....

Comments

thanku ...............very much i much waiting for solution like  it .

---

why +16+16+16-1-1-1?

why not -16-16-16-1-1-1?

---

that is bcz of inclusion exclusion principle.

---

i am waitng for unique explaination …...very clear now

Answer 4

Total number of Onto Functions from a set of $n$ elements to a set of $k$ elements is given by :

so in this case