Find $\sum_{m=0}^n\ (-1)^m m^n {n \choose m}$

Solution 1:

The general form of the summation

$$\sum_{m=0}^n(-1)^mm^n\binom{n}m\;,\tag{1}$$

with the alternating sign and the binomial coefficient $\binom{n}m$, suggests that it can be interpreted as an inclusion-exclusion calculation. However, the $m=0$ term is $0$, from which we begin by subtracting a positive quantity $\binom{n}1=n$, which is a bit odd for such a calculation. This suggests letting $k=n-m$ and rewriting as

$$\sum_{k=0}^n(-1)^{n-k}(n-k)^n\binom{n}{n-k}=(-1)^n\sum_{k=0}^n(-1)^k\binom{n}k(n-k)^n\;,$$

where the righthand side has been arranged to look like a more or less typical inclusion-exclusion calculation. The factor $(n-k)^n$ is the one that isn’t part of the inclusion-exclusion machinery. It has a natural interpretation as the number of functions from $[n]$ to $[n]$ whose ranges are disjoint from some $k$-element subset of $[n]$. If for each $k\in[n]$ we let $F_k$ be the set of functions from $[n]$ to $[n]$ whose ranges do not contain $k$, we have

$$\left|\bigcap_{k\in I}F_k\right|=(n-|I|)^n$$

whenever $\varnothing\ne I\subseteq[n]$, so

$$\begin{align*} \left|\bigcup_{k=1}^nF_k\right|&=\sum_{\varnothing\ne I\subseteq[n]}(-1)^{|I|-1}\left|\bigcap_{k\in I}F_k\right|\\ &=\sum_{\varnothing\ne I\subseteq[n]}(-1)^{|I|-1}(n-|I|)^n\\ &=\sum_{k=1}^n(-1)^{k-1}\binom{n}k(n-k)^n\;. \end{align*}$$

This is the number of functions from $[n]$ to $[n]$ that are not surjective, i.e., the number that aren’t bijections. It follows that the number of bijections from $[n]$ to $[n]$ is

$$n^n-\sum_{k=1}^n(-1)^{k-1}\binom{n}k(n-k)^n=\sum_{k=0}^n(-1)^k\binom{n}k(n-k)^n\;.$$

On the other hand, we know that there are $n!$ bijections from $[n]$ to $[n]$, so

$$\sum_{m=0}^n(-1)^mm^n\binom{n}m=(-1)^n\sum_{k=0}^n(-1)^k\binom{n}k(n-k)^n=(-1)^nn!\;.$$

Note that the same basic argument handles the previous part of the problem. The factor $(n-k)^n$ is replaced by $(n-k)^r$, the number of functions from $[r]$ to $[n]$ whose ranges are disjoint from some specified $k$-element subset of $[n]$. The expression

$$\sum_{k=0}^n(-1)^k\binom{n}k(n-k)^r$$

counts the surjective functions from $[r]$ to $[n]$, and if $r<n$, this is of course $0$.

All of this is very closely related to the Stirling numbers of the second kind.

Solution 2:

The following relation encapsulates the Stirling number semantics:

$$m^r = r! [z^r] \exp(mz).$$

This yields for your sum

$$S_r(n) = r! [z^r] \sum_{m=0}^n {n\choose m} (-1)^m \exp(mz) = r! [z^r] (1-\exp(z))^n.$$

Now observe that

$$1-\exp(z) = - z - \frac{z^2}{2} - \frac{z^3}{6} -\cdots$$

which means that $(1-\exp(z))^n$ starts at $[z^r]$ where $r=n$ with coefficient $(-1)^n$, producing for the sum the value

$$(-1)^n\times n!$$

and the coefficients on $[z^r]$ with $r\lt n$ are zero.