in Set Theory & Algebra
6,499 views
36 votes
36 votes
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)$
in Set Theory & Algebra
by
513 802 798
6.5k views

5 Comments

Refer 8. Advanced Counting Techniques $\rightarrow$ 8.6 Application of Inclusion-Exclusion, Discrete Mathematics, Rosen.

3
3

A possible exam approach:-

Take n=2 , here now we have $f:[a,b]\rightarrow [c,d]$ (where a,b,c,d be any 4 elements)

now Number of possible Onto functions are

  1. $f(x, f(x,y))= [ (a,c), (b,d)]$
  2. $f(x, f(x,y))= [ (a,d), (b,c)]$

Hence only 2 possiblities putting n=2 in options which give 2 is only (C).

0
0
Thanks @ Vysakh Ramesh for the reference. Quite easy to understandd.
0
0
edited by
This question can also be solved using distribution approach. Let the function be $f:X\rightarrow Y$

where $|X| = n$ and $|Y| = 2$ and $n>=2$ (essential condition for $f$ to be an onto function, size of domain has to be greater than equal to size of co-domain)

Let the elements of $Y$ be two distinct boxes and elements of $X$ be n distinct objects, we have to distribute n distinct objects over 2 different boxes where each box has at least one object. There can be following cases:

$(n-1, 1) = \binom{n}{n-1}$ ways

$(n-2, 2) = \binom{n}{n-2}$ ways

$(n-3, 3) = \binom{n}{n-3}$ ways

and so on until $(1, n-1) = \binom{n}{1}$ ways

adding all the cases, we will get $ \binom{n}{n-1} + \binom{n}{n-2} + $ .. $ \binom{n}{2} + \binom{n}{1} $

which is equal to

$ (\binom{n}{n} + \binom{n}{n-1} + $ .. $ \binom{n}{1} + \binom{n}{0} )$  – $ (\binom{n}{n} + \binom{n}{0} )$

= $2^n – 2$
0
0

………………………

1
1

Subscribe to GO Classes for GATE CSE 2022

4 Answers

39 votes
39 votes
 
Best answer

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

edited by
by
538 796 1013

5 Comments

can u pls tell me how u took that probability using bernouilli

i  mean how u did the 2nd last step @Prateek Raghuvanshi

see this please if it is correct!!

# of onto fn= total fn - into fn

=2n- {atleast one of rhs is not mapped}

=2n - {1- all elements in rhs are mapped}

now am not able to solve it further;

the way u did is also good, but i was thinking if the elements in set B are large,then we cant chk for every case right, we have to do it like this.

 

can u pls tell me how to solve it further. It would be  a great help!

0
0

Gate Fever check this out-

3
3
reshown by

@Prateek Raghuvanshi

Which book is this? Rosen?

0
0
@Manu Shaurya yes
0
0
24 votes
24 votes

$2^{n} - 2$

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

edited by
by
49 96 161
9 votes
9 votes

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

edited by
by
11 61 134
7 votes
7 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

by
28 47 70
Answer:

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