Stirling numbers combinatorial proof: $S(m,n)=\frac 1{n!} \sum_{k=0}^{n} (-1)^k\binom nk (n-k)^m$

Question

This is a Homework Question.

I am required to give a Combinatorial proof for the following.

$$S(m,n)=\frac 1{n!} \sum_{k=0}^{n} (-1)^k\binom nk (n-k)^m$$

Hint given is : Show that $n!S(m,n)$ equals the number of onto functions $f\colon A \rightarrow B$ when $ |A|=m$ and $|B|=n. $

There were some other combinatorial proof questions on the assignment which I found easier to do but this one not so much. Could use help.

Answer 1

Let $T$ denote the set of functions from $f:A\to B$ where $|A|=m$ and $|B|=n$ and $$S=\{f\in T \mid f \text{ is surjective}\}$$

If $f$ is surjective, then $f^{-1}(b)$ is non-empty for all $b\in B$. There are $S(m,n)$ many ways, to partition $m$ elements into $n$ non-empty set. For each such partition $A_1,\dots, A_n$, there are $n!$ ways to assign the pre-images $f^{-1}(b_1),\dots,f^{-1}(b_n)$, so $$|S| = n!S(m,n)$$

Now count the elements of $S$ again in an other way: For each $b\in B$, define $$M_b = \{ f: A\to B \mid f^{-1}(b)=\varnothing\}$$ Then $$S = T \setminus\bigcup\limits_{b\in B}M_b$$ Now use the Inclusion-exclusion principle to calculate $|S|$.