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

We are distributing 4 different objects  set x ={1,2,3,4} into 3 different boxes set y= {a,b,c}, corresponding to the letters a,b,c

The base distribution is (1,1,1) where each of a,b,c gets one object. Now, one extra object remains, which must go into one of the boxes.

• If it goes to a we get the distribution (2,1,1)

• If it goes to b we get (1,2,1)

• If it goes to c, we get (1,1,2)

So there are 3 possible cases.

For each case, the number of distinct arrangements of 4 objects with counts (2,1,1) is

4!/(2!⋅1!⋅1!)=12.

Thus, the total number of ways is

3×12=36.

---

Ans

---

Watch the Detailed Video Solution by clicking the button below..!

Watch Detailed Video Solution    

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

@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.

---

alternative approach like button

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

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

---

Same doubt

---

thanku

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 

Answer 5

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 6

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:))

---

Simple, Smart, Excellent

If we want to make that sound more nicely, then we can have the scenario like a small company(1 Boss, 2 employees) has got profits and bought 4 cars of different colours and they want to distribute among themselves such that "Boss gets 2 cars and Each employee gets one".
And applying your appraoch similarly gives 12+12+12