The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
1.6k views
How many onto (or surjective) functions are there from an $n$-element $(n ≥ 2)$ set to a $2$-element set?

  1. $ 2^{n}$
  2. $2^{n} – 1$
  3. $2^{n} – 2$
  4. $2(2^{n} – 2)$
asked in Set Theory & Algebra by Boss (18.1k points) | 1.6k views

4 Answers

+24 votes
Best answer

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

answered by Boss (42.6k points)
edited by
+13
$\sum_{i=0}^{n-1} (-1)^i{n \choose i}(n-i)^m $ =
${n \choose 0}n^m - {n \choose 1}(n-1)^m + {n \choose 2}(n-2)^m - \cdots \pm {n \choose n-2}2^m \mp {n \choose n-1}1^m $
0
@akash can you please show how to do this question with that alternate approach of distribution ?
+1
Total number of functions $f: A\rightarrow B$ possible where |A| = n and |B|= 2 is $2^n$, out of which only 2 functions are there that are not onto-
1. When all n elements of $A$ mapped to $1^{st}$ element of $ B$.
2. When all n elements of $A$ mapped to $2^{nd}$ element of $ B$.

So $2^n - 2$ onto functions are possible.
+1

Onto functions
+20 votes

$2^{n} - 2$

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

answered by Boss (14.2k points)
edited by
+6 votes

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

answered by Active (3.5k points)
+3 votes

Number of onto functions = 2r=1 (-1)2-r  2C rn   

(-1)2-1  2C1 (1)n + (-1)2-2 (2)n = 2n - 2 so option C

answered by Loyal (6.6k points)


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

38,009 questions
45,506 answers
131,661 comments
48,695 users