Explanation of the recursion for number of surjections I have a question about the recursion of the number of surjections from $\{1,\ldots,n\}$ to $\{1,\ldots,k\}$: $$\mathrm{Sur}(n,k) = k \cdot \mathrm{Sur}(n-1,k-1) + k \cdot \mathrm{Sur}(n-1,k).$$
My explanation of this is: We look at the element $k$ from $\{1,\ldots,k\}$. $k$ can be hit either by $1$ element from $\{1,\ldots,n\}$, or by $2$ or more.
In the first case, we remove that $k$ and that element from $\{1,\ldots,n\}$, and we're left with $n-1$ elements in the domain, and $k-1$ elements in the range. It also has to be a surjection, so we can pick them in $\mathrm{Sur}(n-1,k-1)$ ways.
In the second case, we remove that element from the domain, and we're left with $n-1$ elements in domain, and $k$ elements in the range. So we can pick the number of surjections in $\mathrm{Sur}(n-1,k)$ ways.
But, why is that factor $k$ there in both cases?
 A: You didn't account for the $n$ different choices of elements mapped to $k$. In your first case, that leads to a factor of $n$. The second case is more complicated because you also have a choice which of the elements mapped to $k$ to remove. To avoid these complications, you can derive the recurrence as in polkjh's answer instead.
A: Let $f(n)$ be the image of element $n$. 
If $n$ is the only element with $f(n)$ as it's image, then we can remove $n$ and $f(n)$ and look at $S(n-1,k-1)$. But there are $k$ ways to pick $f(n)$. So this accounts for $k.S(n-1,k-1)$ ways. 
If $n$ is not the only element with $f(n)$ as it's image, then we can just remove $n$ and look at $S(n-1,k)$. And $f(n)$ can again be chosen in $k$ different ways. This gives another $k.S(n-1,k)$ surjections.
In your argument, in the case when $k$ has exactly one element hitting it, you can choose that element in $n$ ways. So that accounts for $n.S(n-1,k-1)$ surjections. But the other case gets more complicated. If there are $r$ elements pointing to $k$, there are $\binom{n}{r}$ ways to pick those $r$ elements. Then we can remove those $r$ elements and $k$ and look at $S(n-r,k-1)$. We cannot just remove one of these elements and look at surjections from $n-1$ to $k$ as these are not any general surjections (in these surjections, you need $r-1$ elements pointing to $k$).
This gives
$$
S(n,k) = \sum _{r=1}^{n} \binom{n}{r} S(n-r,k-1)
$$
A: This is just my quick impression, but it seems to be all about permutations.
First, we have our sets
$A = \{a_1,...,a_n\}$,
$B = \{b_1,...,b_k\}$ and some $f:A \rightarrow B$.
Try to think about what happens to $a_n$ in all the possible surjections.
My further thoughts are below in the spoiler:

If $a \epsilon A$, $b \epsilon B$ and we let $f(a)=b$, then there are two possibilities for our surjections: some other $a' \epsilon A$ also maps to $b$ or not. In the case where $f(a)$ uniquely maps to $b$, there are clearly $Sur(n-1,k-1)$ ways to do this.

Then

In the other case, $f(a')=b=f(a)$ for some arbitrary $a' \epsilon A$. That is, our surjection is $f(a)=b$ along with some surjection $g: A \backslash a \rightarrow B$. So the number of ways of doing this should be $Sur(n-1,k)$. 

So

 The number of surjections where $f(a)=b$ should come to $Sur(n-1,k-1) + Sur(n-1,k)$. But clearly the above arugment is symmetric across all $b$--of which there are $k$ of them--so multiply by $k$.

Q.E.D.
A: In generating surjections for S(n,k), start by choosing each of the k elements.  These will obviously all create different surjections.  The k cases all have two sub-cases.  You can choose combinations of all k elements from the remaining n-1 choices, giving S(n-1,k) surjections.  Alternatively, since you have already selected an element from k, you can complete the remaining S(n-1,k - 1) surjections that do not have that element.
