For fixed positive integers $m$ and $n$, let $$S=\sum_{k=0}^m (-1)^k\binom{m}{k}(m-k)^n.$$Show that $S = 0$ if $n < m$ and $S = n!$ if $n = m$.
I know that I have to use PIE(principle of inclusion and exclusion) and a counting argument. Here's my work so far:
There are $m$ people, $\binom{m}{k}$ represents all the ways to pick $k$ people out of $m$ people. $(m-k)^n$ represents all the ways of giving the people that weren't chosen nn distinguishable objects. What I don't get is how to apply PIE, why the signs are alternating, and how does $S = 0$ if $n < m$ and $S = n!$ if $n = m$. Could anyone offer an answer by the counting argument I started? Thanks!
HINT: Show that $S$ is the number of surjections from $[n]=\{1,\ldots,n\}$ to $[m]=\{1,\ldots,m\}$ counted using an inclusion-exclusion argument. The crucial observation is that for any $I\subseteq[m]$, there are $(m-|I|)^n$ functions from $[n]$ to $[m]$ whose ranges are disjoint from $I$.
If you get stuck, this answer gives an informal explanation, this answer contains a detailed explanation (in the context of a slightly different question), and this answer contains an even more detailed answer to a different but similar question, showing in more detail the application of the inclusion-exclusion principle.