GATE CSE 2012 | Question: 37

Question

How many onto (or surjective) functions are there from an $n$-element $(n ≥ 2)$ set to a $2$-element set?

• A. $ 2^{n}$
  
• B. $2^{n} – 1$
  
• C. $2^{n} – 2$
  
• D. $2(2^{n} – 2)$

Comments

...

---

@Rohit139 if no elements are mapped, it violates the definition of a function.

---

option elimination
let n=2
f : A-> B
num(A)=2 and Num(B)=2

onto function 1 :
1-> 1
2->2

onto function 2 :
1-> 2
2->1

so only two onto function for n=2

A 2^2= 4 wrong
B 2^2-1 = 3 wrong
C 2^2-2 = 2 can be
D 2(2^2-2)=4 wrong

so answer is C   
 

Answer 1

No. of onto (or surjective) functions are there from an $n$-element $(n\geq 2)$ set to a $2$-element set $=$ Total No of functions $-$ (No of functions with $1$ element from RHS not mapped) $+$ (No of functions with $2$ element from RHS not mapped)$\ldots$(So on Using Inclusion Excusion principle $= 2^{n}$ (Total no of functions ) $-$ $2 * 1^{n}$ ( No of functions in which one element is excluded) $+ 0$ (No element in RHS is selected) $= 2^{n} -2.$

Hence, Ans is (C).

alternate 

https://gateoverflow.in/8212/gate2015-2_40

Comments

@ Gate Fever check this out-

---

@Prateek Raghuvanshi

Which book is this? Rosen?

---

@Manu Shaurya yes

Answer 2

$2^{n} - 2$

in words (Total functions $-$ 2 functions where all elements maps exactly one element).

Comments

Short and crisp answer. Good 👍

Answer 3

$Onto function :\space$ $x$  $\longrightarrow$ $y$

$x\space is\space preimage\space of\space y\space ,\space y\space is\space image\space of\space x\space$

$\textbf {Step 1:}Find\space non\space onto\space function \space is\space relatively\space easythan\space find\space onto\space function\space so\space -\space$

$non\space onto\space function\space =\space Either\space a\space not\space mapped\space OR\space B\space not\space mapped\space OR\space C\space not\space mapped\space$

${So\space we\space need\space to\space find\space}$ $|$$S_a$ $\cup$ $S_b$ $\cup$  $S_c$$|$ $=\space ?$ 

$\textbf{Step 2:}\space According\space to\space \textbf{Principal of Mutual Inclusion and Exclusion}$

$|$ $S_a$ $\cup$  $S_b$ $|$ = $|$ $S_a$ $|$ $+$  $|$ $S_b$ $|$ $-$ $|$ $S_a$ $\cap$ $S_b$ $|$

$|$ $S_a$ $|$ $=$ $It$ $means\space a\space not\space mapped$ $=$ $1^n$ 

$|$ $S_b$ $|$ $=$ $It$ $means\space b\space not\space mapped$ $=$ $1^n$ 

$if\space both\space not\space mapped$ $=$ $0^n$

$|$ $S_a$ $\cup$  $S_b$ $|$ = $1\space +\space 1\space -\space 0\space =\space 2$

$\textbf{Step 3:}\space So\space Onto\space functions\space =\space Total\space functions\space -\space non\space onto\space functions $

$And\space as\space we\space know\space total\space functions\space =\space 2^n$

$So\space onto\space functions\space are\space =\space 2^n - 2$

$Hence\space Option\space C\space is\space right\space one$

Comments

Great explanation!! Thanks.

---

Niceee

Answer 4

Consider |A| = a, |B| = b, then Number of relations from A to B is $2^{a \times b }$, as each element is A can map to every element is B, and each mapping may exist or not.

Now in case of a function its one - one or many to one. Hence total functions possible is $b^{a}$, as each value in A can map to only one value in B, and this is applicable 'a' times.

With this information in mind, number of functions from A to B in this case is $2^n$ But two of the functions are not onto i.e. the ones where all map to only 1st or 2nd element in B.

Hence answer is C

Answer 5

 

The number of onto functions from A→B where |A|=m and |B|=n is given by the formula

 

Here, m=3 and n=2
Substituting in above formula we get,
2^3−2C1(2−1)3^+2C2(2−2)^3

8-2 = 6

Hence answer is C

2^n-2 = 2^3-2 = 8-2=6

Answer 6

interesting view of this