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

15 Answers

Best answer
61 votes
61 votes

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

edited by
55 votes
55 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}$
44 votes
44 votes

hope this helps.....

18 votes
18 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 

Answer:

Related questions

38 votes
38 votes
5 answers
1
32 votes
32 votes
4 answers
2
go_editor asked Feb 12, 2015
6,724 views
Consider a function $f(x) = 1- |x| \text{ on } -1 \leq x \leq 1$. The value of $x$ at which the function attains a maximum, and the maximum value of the function are:$0, ...