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

Dark Mode

16,045 views

48 votes

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

edited
Jul 14, 2019
by Rishi yadav

@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

hope you find this helpful

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

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

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

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

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

@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