How many of these are surjective? Let $A=\{a,b,c,d\}$ and $B=\{e,f,g\}$.


*

*How many maps are there from A to B?

*How many of these maps are surjective?


$\textbf{Part 1:}$ There are 4 elements in A and 3 elements in B. Thus there are $3^4=81$ maps from A to B.
$\textbf{Part 2:}$ I can listed in order pair form the outputs for the function $f:A \to B$. For example, $f(a)=e$, $f(b)=e$, $f(c)=e$, and $f(d)=e$ can be written $(e,e,e,e)$. Is there a better way of finding how many maps are surjective than this way?
 A: If $h:A\rightarrow B$ is a function then it induces a partition $\mathcal P_h$ on $A$. Elements of $\mathcal P_h$ are the sets of the form $\{a\in A\mid h(a)=b\}$ where $b$ belongs to the image of $h$. Notations for this sets are $h^{-1}(\{b\})$ or shortly $h^{-1}(b)$. $\mathcal P_h$ and the image of $h$ have equal cardinality, so if $h$ is surjective then $|\mathcal P|=|B|$. Searching for the number of maps $h:A\rightarrow B$ that are surjective two questions rise:


*

*How many partitions $\mathcal P$ exist on $A$ with $|\mathcal P|=|B|$?

*How many surjections $h:A\rightarrow B$ exist with $\mathcal P_h=\mathcal P$?
Here we drop some generality by assuming that $A$ and $B$ are finite sets. Then the second question is not too difficult: $|B|!$ (so in your case $3!=6$). The first question is more difficult. However, in your case we are dealing with partitions of a set $A$ that contains $4$ elements and the partition itself has $3$ elements. Under these conditions any partition has a determining unique element that has $2$ elements, so the answer is $\binom{4}{2}=6$. Then the total number of surjections is: $$3!\binom{4}{2}=36$$
