36 votes

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

4

simply 4 different things distribute in 3 different box and each box contain atleast 1 thing

$4! 3!\div 1! 1! 2! 2! = 36$ (bin ball problem )

$4! 3!\div 1! 1! 2! 2! = 36$ (bin ball problem )

0

@Ashwani Yadav C(4,2)C(2,1)C(1,1)+C(4,1)C(3,2)C(1,1)+C(4,1)C(3,1)C(2,2) this is same as suggested by @minal

you will get exact form...

51 votes

Best answer

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

[email protected] http://www.cse.iitd.ac.in/~mittal/stirling.html

3

sir, can do we like this...

x={1,2,3,4}

y={a,b,c}

suppose 1 from x can be mapped to any of three elements i suppose it maps to a elemenet of y

now 2 can be mapped to same a therefore we have pair which contain two elements therefore giving total pairs as ^{4}C_{2= }6 pairs._{. } further we can map 1 of x with any three elements of y giving three ways, 2 of x can be mapped to either b,c giving two ways , 3,4 can be mapped with remaining c element of y giving one way therefore total of 6 ways we have show that already 6 pairs exist in SET X which can be mapped to same element Y therefore 6*6= 36 functions

0

@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

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

42 votes

$\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}$

$\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}$

31 votes

16 votes

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

so in this case

7 votes

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

5 votes

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!**