I'm having trouble on this question:
Let $f(n,r)$ be the number of surjections from a set $A$ having $n$ elements to a set $B$ having $r$ elements. Show that $$f(n,r)=r\Big(f(n-1,r-1)+f(n-1,r)\Big)\;.$$
Here is my idea about how to start:
Partition each set, $A$ and $B$, such that the top partition consists of $n-1$ or $r-1$ elements (for $A$ and $B$ respectively) and the bottom partitions consists of one element each.
Then there are $f(n-1,r-1)$ surjections from the top partition of $A$ onto the top partition of $B$.
There are $f(n-1,r)$ surjections from the top partition of $A$ to all of $B$.
Now consider the whole of $A$ (i.e. $(n-1)+1$ elements).
The total number of surjections is:
((total number of surjections from top partition of $A$ onto all of $B$) + (extra surjections due to extra element of $A$)) permuted to account for all combinations
But how do you calculate the extra surjections due to the extra element of $A$ and the correct number of permutations?