GATE CSE 2015 Set 2 | Question: 40

Question

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

Comments

hope you find this helpful 

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

---

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

---

$\color{red}{\text{Detailed Video Solution, with Alternative Ways to Solve:}}$ https://youtu.be/-9HQqDyVG5k 

Answer 1

Correctly found that there are $3^{4}$ functions from a set with four elements to a set with three elements. However, this counts functions with fewer than three elements in the range. We must exclude those functions. To do so, we can use the Inclusion-Exclusion Principle.

• There are $\binom{3}{1}$ ways of excluding one element in the co-domain from the range and $2^{4}$ functions from a set with four elements to the remaining two elements in the co-domain.
• There are $\binom{3}{2}$ ways of excluding two elements in the co-domain from the range and $1^{4}$ functions from a set with four elements to the remaining element in the co-domain.
• There are $\binom{3}{3}$ ways of excluding two elements in the co-domain from the range and $0^{4}$ functions from a set with four elements to the remaining element in the co-domain.

By the Inclusion-Exclusion Principle, the number of surjective (onto) functions from a set with four elements to a set with four elements is $=3^{4}-\left[\binom{3}{1}\times 2^{4}-\binom{3}{2}\times 1^{4}+\binom{3}{3}\times 0^{4}\right] = 81-45=36$.

Comments

Sir, there is a typo in the final equation; it should be 2^4,1^4.

---

Also in 1st, 5^th,7^th and 9^th line → from a set with five elements to a set with three elements.

it should be four

---

Fixed 👍

Answer 2

As we can see X has all different elements as well as Y too. It is a case of X as distinguishable Objects and Y as distinguishable boxes so for onto functions,  means there should be at least one element

It can be select 2 objects from first then 2nd then 3rd, or select one object then 2 objects and select 1 object or select 1, select 1 and select 2 objects so,

$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)=$

$\frac{4!}{2!\times 2!}\times\frac{2!}{1!1!}+\frac{4!}{3!\times 1!}\times\frac{3!}{2!1!}+\frac{4!}{3!\times 1!}\times\frac{3!}{2!1!}\times \frac{2!}{2!}$

$3\times \frac{4!}{2!1!1!}$ or in other way multiply $2!$ to both numerator and denominator so it becomes $\frac{4!3!}{2!2!1!1!} = 36$
 

Using Stirling number of the second kind : $j!S(4,3)$

$S(n,j) = \frac{1}{j!} \sum_{i=0}^{j-1}(-1)^i\binom{j}{i}(j-i)^n$

$=3!S(4,3) = \begin{bmatrix}\binom{3}{0}3^4-\binom{3}{1}2^4+\binom{3}{2}\end{bmatrix} = 36$

Answer is 36

Comments

Wat hav u done ?? can u explain ??

---

now i have explained very well correct me if i wrong @puja

Answer 3

given X(1,2,3,4) y(a,b,c) thus we will arrange elements of X on Y as permutations of 2,1,1 so selecting 2 elements in  4C2 ways and then arranging 3! so total functions 4C2 * 3! = 36

Answer 4

Refer 8.6: An Alternative Form of Inclusion-Exclusion (Kenneth Rosen) for crystal clear understanding.