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

edited | 8.1k views
0
It could be related to derangement problem.
+2
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 )
0

@minal how u got this?

0
its distribution of m different things to  n different boxs with atleast 1 thng
0

@minal any general formula ? can u pls explain it a bit more...

0

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

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:

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

by Veteran (431k points)
edited by
+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 4C2= 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
How did we derive alternative approach ? or is this closed formula for Striling numbers ?
+2
0
0

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.

+10

This might help ...

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.

$\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}$
by Junior (521 points)
+1
best way to solve this type of questions.

hope this helps.....

by Boss (42.4k points)
+1
thanku ...............very much i much waiting for solution like  it .
0
why +16+16+16-1-1-1?

why not -16-16-16-1-1-1?
+4
that is bcz of inclusion exclusion principle.

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

$Onto(n,k)=k^n - {k \choose 1}(k-1)^n + {k \choose 2}(k-2)^n - {k \choose 3}(k-3)^n + \dots$

so in this case

$\fn_cs \small Onto(4,3) = 3^4 - {3 \choose 1} (3-1)^4 + {3 \choose 2} (3-2)^4 - {3 \choose 3} (3-3)^4 = 81-16 \times 3+3-0 = 36$

by Boss (30.8k points)

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

by Veteran (63k points)
edited

Another way to solve this problem.

 $x_{1}$ $x_{2}$ $x_{3}$ $x_{4}$ Total (Row wise) a a b c $\frac{(4!)}{(2!)(1!)(1!)}$ a b b c $\frac{(4!)}{(2!)(1!)(1!)}$ a b c c $\frac{(4!)}{(2!)(1!)(1!)}$ Final Total 3*(3*4) = 36
by Boss (13.6k points)
0
I thought in the same way.

There are $4$ distinct places and $3$ distinct elements. So there must have 2 same elements e.g.

$aabc,~bbac,~ccab$. Therefore, the answer is $3\times \frac{4!}{2!}=36$.

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!

by Active (4.9k points)
0
good:))

One way of solving it can be:

Choose two numbers from X to be mapped to one element in Y -> $\binom{4}{2} * 3$
Now we are left with 2 elements in X and 2 elements in Y we can have only two possible ways.

Total =>  $\binom{4}{2} * 3$ * 2 = 36

by Active (3.5k points)