Question

Let $A=\{1$, $2$, $3$, .... $n]$ and $B=\{a$, $b\}$. Then the number of surjections from $A$ into $B$ is

• A. ${}^n{P}_2$
• B. $2^n-2$
• C. $2^n-1$
• D. none of these

Answer 1

Answer: (B)

If $f$ : $A\to B$ is a function, the $f(1)$ can be chosen in two ways, $f(2)$ can be chosen in two ways, ..., $f(n)$ can be chosen in two ways.
Hence, $f$ can be chosen in $2\times 2\times ...\times 2=2^n$ ways
In total there are $2^n$ functions possible. Out of these two functions $f_1$ and $f_2$, defined as $f_1(i)=a\forall i=1$, $2$, $...$, $n$ and $f_2(i)=b\forall i=1$, $2$, $...$, $n$ are not surjective as range of $f_1$ is $\{a\}\ne B$ and $f_2$ is $\{b\}\ne B$.
Hence, the number of surjections from $A$ to $B$ is $2^n-2$.