Number of surjective functions from A to B

$\left\lbrace{4\atop 3}\right\rbrace=6$ is the number of ways to partition $A$ into three nonempty unlabeled subsets. For each partition, there is an associated $3!$ number of surjections, (We associate each element of the partition with an element from $B$). Thus, the total number of surjections is $3! \times \left\lbrace{4\atop 3}\right\rbrace= 36.$

More generally, the number S(a,b) of surjective functions from a set A={1,...,a} into a set B={1,...,b} can be expressed as a sum :

$S(a,b) = \sum_{i=1}^b (-1)^{b-i} {b \choose i} i^a$

where ${b \choose i} = \frac{b!}{i! (b-i)!}$ is the number of different ways to choose i elements in a set of b elements.

To see this, first notice that $i^a$ counts the number of functions from a set of size $a$ into a set of size $i$. Therefore, our result should be close to $b^a$ (which is the last term in our sum). If we want to keep only surjective functions, we have to remove functions that only go into a subset of size $b-1$ in $B$. There are ${b \choose {b-1}}$ such subsets, and for each of them there are $(b-1)^a$ functions. If we just keep $b^a - {b \choose {b-1}} (b-1)^a$ as our result, there are some functions that we removed more than once, namely all functions that go into a subset of size $< b-1$. Therefore, we have to add them back, etc. This leads to the result claimed: $b^a - {b \choose {b-1}} (b-1)^a + {b \choose {b-2}} (b-2)^a - ...$

This is an old question, but I recently came across the same problem and solved it in a different way which I find a bit easier to comprehend.

Say you have a $k$ letter alphabet, and want to find the number of possible words with $n_1$ repetitions of the first letter, $n_2$ of the second, etc. The equation for the number of possible words is, as demonstrated in this paper:

$$ P(n:n_1,n_2,...,n_k)=\frac{n!}{n_1!\times n_2! \times\cdots\times n_k!} $$

Now, think of the elements of $B$ as our alphabet of 3 letters, one of which is repeated in its mapping on to our 4 elements of $A$. Since the repeated letter could be any of $a$, $b$, or $c$, we take the $P(4:1,1,2)$ three times. Then the number of surjections is

$$ 3\times P(4:1,1,2)=36 $$

I came out with the same solution as the accepted answer, but I may still be erroneous somewhere in my reasoning. Please let me know if you see a mistake ;)