Number of surjective functions from A to B Am I on the right track? I am not sure about my reasoning...
Number of surjective functions from $A$ to $B$
$$A = \{1,2,3,4\} ; B = \{a,b,c\}$$
We must count the surjective functions, meaning the functions for which for all $b \in B$, $\exists~a \in A$ such that $f(a) = b$, $f$ being one of those functions. In order for a function $f:A\rightarrow B$ to be a surjective function, all 3 elements of $B$ must be mapped.
We need to count how many ways we can map those 3 elements. We will subtract the number of functions from $A$ to $B$ which only maps 1 or 2 elements of $B$ to the number of functions from $A$ to $B$ (computed in 4.c : 81).
Only 1 element of $B$ is mapped
The first $a \in A$ has three choices of $b \in B$. The others will then only have one. Total functions from $A$ to $B$ mapping to only one element of $B$ : 3.
Exactly 2 elements of $B$ are mapped
Similarly, there are $2^4$ functions from $A$ to $B$ mapping to 2 or less $b \in B$. However, these functions include the ones that map to only 1 element of $B$. So there are $2^4-3 = 13$ functions respecting the property we are looking for.
In the end, there are $(3^4) - 13 - 3 = 65$ surjective functions from $A$ to $B$.
 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 ;)
A: $\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.$
A: 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 - ...$
A: Let a(n,m) be the number of surjections of En = {1,2,...,n} to Em = {0,1,...,m}. Choose an element L of Em. This can be done in m ways. There are two possibilities. (1) L has 1 original in En (say K). The other (n - 1) elements of En are mapped onto the (m - 1) elements of Em (other than L). Number of ways mxa(n-1,m-1). (2) L has besides K other originals in En. The other (n-1) elements of En are in that case mapped onto the m elements of Em. Here is the number of ways mxa(n-1,m). Conclusion: we have a recurrence relation a(n,m) = m[a(n-1,m-1)+a(n-1,m)]. a(n,n) = n!, a(n,1) =1 for n>=1 and   a(n,m)= 0 for m>n. One verifies that a(4,3)=36.
