Number of surjections between sets This is an exercise from the book Modern Algebra by Warner. If $n$ is a positive integer and $m$ is a positive integer with $m\leq n$, define $\sigma_{n}\left(m\right)$ to be the number of surjections from a set with $n$ elements onto a set with $m$ elements. Show that for every $m$ with $m\leq n$, $$\sigma_{n}\left(m\right)=m^{n}-\sum_{k=0}^{m-1}\dbinom{m}{k}\sigma_{n}\left(k\right).$$ Infer from this that $$\sigma_{n}\left(m\right)=\sum_{k=0}^{m-1}\left(-1\right)^{k}\dbinom{m}{m-k}\left(m-k\right)^{n}=\sum_{j=1}^{m}\left(-1\right)^{m-j}\dbinom{m}{j}j^{n}.$$
I'm not quite sure how to approach this problem. I've tried proving the first formula by induction on $m$, but I wasn't able to prove the case for $m+1$. I was also unable to show how the first formula could be used to prove the second formula.
 A: This "answer" is really just a hint for the first question, but hopefully it gets things moving in the right direction. Rather than give away the answer, I want to motivate the idea of always looking for "meaningful interpretations" of the algebraic expressions at hand, rather than just diving straight for proof by induction; I think that you have all the tools you need, you just need to figure out how they fit together, and a hint will help with this more than a fully-worked solution. Below I'll write "$[a]$" for $\{1,...,a\}$, so that $\sigma_n(m)$ is counting the number of surjective functions from $[n]$ to $[m]$.

Note that $m^n$ is the cardinality of the set of all functions from $[n]$ to $[m]$. So we have $$\sigma_n(m)=m^n-\mathsf{NONSURJ}_n(m)$$ where $\mathsf{NONSURJ}_n(m)$ is the set of all non-surjective functions from $[n]$ to $[m]$. We now use two tricks: first, that if $f:[n]\rightarrow[m]$ is non-surjective then $im(f)$ is a subset of $[m]$ of size at most $m-1$; and second, that every function is surjective - onto its image. (Finally, it's not a trick per se, but it's important to keep in mind what the "choose" function is actually doing ...)
