How to compute $\sum^n_{k=0}(-1)^k\binom{n}{k}k^n$

You can derive the result using the sum you get.

Let $x = e^\theta$, we have

$$ \left.\left(x\frac{d}{dx}\right)^n(1-x)^n\right|_{x=1} = \left.\frac{d^n}{d\theta^n}\left(1-e^\theta\right)^n\right|_{\theta=0} = (-1)^n \left.\frac{d^n}{d\theta^n}\left[\theta^n\left(\frac{e^\theta-1}{\theta}\right)^n\right]\right|_{\theta=0} $$ Recall the General Leibniz rule for the $n^{th}$ derivative for a product of two functions:

$$(fg)^{(n)} = \sum_{k=0}^n \binom{n}{k} f^{(k)} g^{(n-k)}$$ If one substitute $$f = \theta^n \quad\text{ and }\quad g = \begin{cases} \left(\frac{e^\theta-1}{\theta}\right)^n,&\theta \ne 0\\ 1, & \theta = 0 \end{cases} $$ and notice

• $f^{(m)}(0) = 0$ for $m = 0, 1, \ldots, n-1$,
• $g(\theta)$ is a smooth function over a neighborhood of $\theta = 0$.

We find under the General Leibniz rule, only the $k = n$ term survive and

$$\text{RHS} = (-1)^n \binom{n}{n} \left.\left( \frac{d^n}{d\theta^n}\theta^n \right)\right|_{\theta=0} g(0) = (-1)^n n! $$

Suppose that I want to count the permutations of the set $[n]=\{1,\ldots,n\}$. For each $k\in[n]$ let $A_k$ be the set of functions from $[n]$ to $[n]\setminus\{k\}$. A function from $[n]$ to $[n]$ is a permutation iff it is not in $A_1\cup\ldots\cup A_n$, so there are $n^n-|A_1\cup\ldots\cup A_n|$ permutations. By a standard inclusion-exclusion argument

$$\begin{align*} |A_1\cup\ldots\cup A_n|&=\sum_{1\le k\le n}|A_k|\\ &\quad-\sum_{1\le k<\ell\le n}|A_k\cap A_\ell|\\ &\quad+\sum_{1\le j<k<\ell\le n}|A_j\cap A_k\cap A_\ell|\\ &\quad\;\vdots\\ &\quad+(-1)^{n+1}|A_1\cap\ldots\cap A_n|\;. \end{align*}\tag{1}$$

Let $K\subseteq[n]$, and let $k=|K|$. Then

$$\left|\bigcap_{i\in K}A_i\right|=(n-k)^n\;,$$

because $\bigcap_{i\in K}A_i$ is the set of functions from $[n]$ to $[n]$ whose ranges are disjoint from $K$. There are $\binom{n}k$ such sets $K$, so $(1)$ can be rewritten

$$\begin{align*} |A_1\cup\ldots\cup A_n|&=\binom{n}1(n-1)^n\\ &\quad-\binom{n}2(n-2)^n\\ &\quad+\binom{n}3(n-3)^n\\ &\quad\;\vdots\\ &\quad+(-1)^{n+1}\binom{n}n(n-n)^n\\ &=\sum_{k=1}^n(-1)^{k+1}\binom{n}k(n-k)^n\;. \end{align*}$$

Of course we know that the number of permutations of $[n]$ is $n!$, so

$$\begin{align*} n!&=n^n-\sum_{k=1}^n(-1)^{k+1}\binom{n}k(n-k)^n\\ &=n^n+\sum_{k=1}^n(-1)^k\binom{n}k(n-k)^n\\ &=\sum_{k=0}^n(-1)^k\binom{n}k(n-k)^n\\ &=\sum_{k=0}^n(-1)^k\binom{n}{n-k}(n-k)^n\\ &=\sum_{k=0}^n(-1)^{n-k}\binom{n}kk^n\\ &=(-1)^n\sum_{k=0}^n(-1)^k\binom{n}kk^n\;, \end{align*}$$

and multiplication by $(-1)^n$ yields the desired result.

Another approach is to recognise $\sum^n_{k=0}(-1)^k\binom{n}{k}k^n$ as the result of taking the sequence $(i^n)_{i\in\Bbb N}$ of $n$-th powers, applying $n$ times $-\Delta$, where $\Delta$ is the difference operator $(a_i)_{i\in\Bbb N}\mapsto(a_{i+1}-a_i)_{i\in\Bbb N}$, and then taking the initial term at $i=0$. For the difference operator applied to polynomial sequences it is convenient to use the basis of so called falling factorial powers defined by $$ x^{\underline k} = x(x-1)\ldots(x-k+1) $$ which satisfy $\Delta\bigl((i^{\underline k})_{i\in\Bbb N}\bigr)=k(i^{\underline{ k-1}})_{i\in\Bbb N}$ for $k>0$, and $\Delta\bigl((i^{\underline 0})_{i\in\Bbb N}\bigr)=\Delta\bigl((1)_{i\in\Bbb N}\bigr)=0$. Since $x^{\underline k}$ is a monic polynomial of degree $k$ in $x$, it is clear that expressing the sequence $(i^n)_{i\in\Bbb N}$ as linear combination of falling factorial power sequences $(i^{\underline k})_{i\in\Bbb N}$ for $k=0,1,\ldots,n$ will involve the final sequence $(i^{\underline n})_{i\in\Bbb N}$ with coefficient$~1$. All other terms are killed by $\Delta^n$, so $\Delta^n\bigl((i^n)_{i\in\Bbb N}\bigr)=\Delta^n\bigl((i^{\underline n})_{i\in\Bbb N}\bigr)$, which by the above relations is the constant sequence $(n!i^{\underline 0})_{i\in\Bbb N}=(n!)_{i\in\Bbb N}$. It then follows that $$ \sum^n_{k=0}(-1)^k\binom{n}{k}k^n = (-\Delta)^n\bigl((i^n)_{i\in\Bbb N}\bigr)\Bigm|_{i=0} =(-1)^n n!. $$