# Proof Involving Sigmas

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!

• Notice: $$\text{S}=\sum_{k=0}^m (-1)^k\binom{m}{k}(m-k)^n=m!\cdot\mathcal{S}_{n}^{(m)}$$ Where $\mathcal{S}_{n}^{(m)}$ is the Stirling number of the second kind. mathworld.wolfram.com/StirlingNumberoftheSecondKind.html – Jan Aug 15 '16 at 18:14
• I’ve updated my earlier answer by adding a link to an answer that shows in considerable detail the operation of the PIE. Try to combine it with the informal explanation in the first link that I gave, and if you get stuck, let me know where, and we’ll try to sort it out. – Brian M. Scott Aug 15 '16 at 18:20

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$.
• @MathMuse: The statement that you make about $\binom{m}k$ is correct, but it doesn’t really get you anywhere. It looks to me as if the fundamental problem is that you don’t understand how the inclusion-exclusion principle works. The first answer to which I linked gives a very informal explanation of the idea, and the last shows in detail how an inclusion-exclusion argument can be carried out for a similar question. The former gives some idea of why such arguments work; the latter shows how the details work even if one is merely going through them mechanically. And the very first link ... – Brian M. Scott Aug 15 '16 at 19:03