GATE2015-2-40

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

edited
0
It could be related to derangement problem.
5
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

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.

14

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}$
1
best way to solve this type of questions.
0
Won’t there be 3! = 6 permutations?

hope this helps.....

2
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?
5
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$

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

edited

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!

0
good:))

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

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

Related questions

1
4.2k views
Let $X$ and $Y$ denote the sets containing 2 and 20 distinct objects respectively and $F$ denote the set of all possible functions defined from $X$ to $Y$. Let $f$ be randomly chosen from $F$. The probability of $f$ being one-to-one is ______.
If p, q, r, s are distinct integers such that: $f (p, q, r, s) = \text{ max } (p, q, r, s)$ $g (p, q, r, s) = \text{ min } (p, q, r, s)$ ... Also the same operations are valid with two variable functions of the form $f(p, q)$ What is the value of $fg \left(h \left(2, 5, 7, 3\right), 4, 6, 8\right)$?
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, -1$ $-1, 0$ $0, 1$ $-1, 2$
The cardinality of the power set of $\{0, 1, 2, \dots , 10\}$ is _______