in Set Theory & Algebra edited by
16,045 views
48 votes
48 votes
The number of onto functions (surjective functions) from set $X = \{1, 2, 3, 4\}$ to set $Y=\{a,b,c\}$ is ______.
in Set Theory & Algebra edited by
16.0k views

4 Comments

edited by

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

0
0

hope you find this helpful 

you can also refer → https://www.youtube.com/watch?v=h9BZFnWQ46A&ab_channel=NPTEL-NOCIITM

2
2

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

0
0

12 Answers

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

edited by
by

4 Comments

0
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
0
0

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

1
1
52 votes
52 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}$

3 Comments

best way to solve this type of questions.
2
2
Won’t there be 3! = 6 permutations?
0
0

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

0
0
43 votes
43 votes

hope this helps.....

3 Comments

thanku ...............very much i much waiting for solution like  it .
2
2
why +16+16+16-1-1-1?

why not -16-16-16-1-1-1?
0
0
that is bcz of inclusion exclusion principle.
6
6
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