The Gateway to Computer Science Excellence
+30 votes
7.7k views
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 by Veteran (105k points)
edited by | 7.7k views
0
It could be related to derangement problem.
+1
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

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

10 Answers

+45 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

by Veteran (425k points)
edited by
+2

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
@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
+8

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.

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

hope this helps.....

by Boss (41.9k 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?
+2
that is bcz of inclusion exclusion principle.
+14 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 

by Boss (30.7k points)
+5 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

by Veteran (62.7k points)
edited by
+4 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!

by Active (4.9k points)
0
good:))
+4 votes

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.3k 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$.
+2 votes

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)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,508 answers
195,519 comments
100,952 users