How many surjective functions from set A to B? Let $A = \{1, 2, 3, 4\}$ and $B = \{a, b, c\}$
How many surjective functions are there from $A \to B$?
My first thought is 3*3*2*1, but I've already written 19 out by hand.
 A: We will use Inclusion/Exclusion.
There are $3^4$ functions from $A$ to $B$. From $3^4$ we must subtract the number of functions that are not surjective. 
There are $2^4$ functions from $A$ to $\{a,b\}$, also $2^4$ from $A$ to $\{b,c\}$, also $2^4$ to $\{a,c\}$. 
So are there $3\cdot 2^4$ non-surjective functions? No, because $2^4+2^4+2^4$ double-counts the $3$ constant functions. So the number of non-surjective functions is $3\cdot 2^4-3$.
Remark: The idea generalizes nicely. But with numbers as small as these, we can count in other ways.
Two of the numbers from $1$ to $4$ will be mapped to the same thing, and the others to different things. The two that are mapped to the same thing can be chosen in $\binom{4}{2}$ ways. What they are mapped to can be chosen in $3$ ways. And now there are $2$ ways to decide where the remaining two numbers go, for a total of $\binom{4}{2}\cdot 3\cdot 2$.
A: Consider the set $f^{-1}(a),f^{-1}(b),f^{-1}(c)$.Possible cardinalities of the sets should be say $2,1,1$ otherwise it fails to be surjective.
Let us assume first that $|f^{-1}(a)|=2$ then from the four choices we have $\{1,2,3,4\}$ we have $4C_2$ choices for $f^{-1}(a)$.
For $f^{-1}(b)$ we have $2$ choices and for $f^{-1}(c)$ only one .So we have $6\times 2\times 1$ choices .
repeating the arguements for $|f^{-1}(b)|=2$ and $|f^{-1}(c)|=2$ we have $12*3$ choices
