How to compute $\sum^n_{k=0}(-1)^k\binom{n}{k}k^n$ When trying to answer this question I arrived at
$$\int^\infty_0\frac{\sin(nx)\sin^n{x}}{x^{n+1}}dx=\frac{\pi}{2}\frac{(-1)^n}{n!}\sum^n_{k=0}(-1)^k\binom{n}{k}k^n$$
After using Wolfram Alpha to evaluate the sum for several values of $n$, it seems that
$$\sum^n_{k=0}(-1)^k\binom{n}{k}k^n\stackrel?=(-1)^nn!$$
The best I can do is to express the sum as
$$\left(x\frac{d}{dx}\right)^n(1-x)^n\Bigg{|}_{x=1}$$
but that is as far as I can go. May I know how one can compute the sum? Thanks.
 A: 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.
A: 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!.
$$
A: Here is a contribution using basic complex variables.

Suppose we are trying to show that
$$\sum_{k=0}^n {n\choose k} (-1)^k k^n = (-1)^n n!$$
Observe that
$$k^n = \frac{n!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp(kz) \; dz.$$
This gives for the sum the integral
$$\frac{n!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} 
\sum_{k=0}^n {n\choose k} (-1)^k \exp(kz) \; dz$$
which is
$$\frac{n!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} 
(1-\exp(z))^n \; dz.$$
But we have $$1-\exp(z) =
- \frac{z}{1!} - \frac{z^2}{2!} - \frac{z^3}{3!} - \cdots$$
(starts at $z$ with no constant term)
so the only term that contributes to the coefficient 
$[z^n] (1-\exp(z))^n$ is the product of the $n$ initial terms.
The coefficient on these is $-1,$ giving the final answer
$$(-1)^n n!$$
A: $\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\ol}[1]{\overline{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

There is a 'surprising' result of
  Borwein & Borwein:
  \begin{equation}
\int_{0}^{\infty}\prod_{k = 0}^{n}{\sin\pars{a_{k}x} \over x}\,\dd x =
{\pi \over 2}\prod_{k = 1}^{n}a_{k}\,,\qquad a_{k} \in \mathbb{R}\,,\quad
a_{0} \geq \sum_{k = 1}^{n}\verts{a_{k}}
\end{equation}

With 
$\ds{\quad a_{0} = n\quad\mbox{and}\quad a_{1} = a_{2} = \cdots = a_{n} = 1}$, we'll have
$\ds{a_{0} = n = \sum_{k = 1}^{n}a_{k}}$ such that
\begin{align}
\color{#f00}{\int_{0}^{\infty}
{\sin\pars{nx}\sin^{n}\pars{x} \over x^{n + 1}}\,\dd x} & =
\int_{0}^{\infty}{\sin\pars{nx} \over x}\,\ \overbrace{{\sin\pars{x} \over x}
\,{\sin\pars{x} \over x}\ldots{\sin\pars{x} \over x}}
^{\ds{n\ \mbox{terms}}}\ \,\dd x
\\[5mm] & =
{\pi \over 2}\prod_{k = 1}^{n}1 = \color{#f00}{\pi \over 2}
\end{align}
A: 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!
$$
A: Using inclusion-exclusion principle.
Indeed, let $F$ be the set of all functions from $\{1,2,...,n\}$ into $\{1,2,...,n\}$.
And let $A_{k}$ be the set of all $f \in F$ such that $k \notin \text{image}(f)$
A: The sum indeed evaluates to $(-1)^nn!$ and here is one possible derivation. In the (final) expression you got in the question, you can substitute $y=x-1$, and observe that for any function $f$ one has $\def\d{\mathrm d}\frac\d{\d x}f(x-1)=f'(x-1)$, which is the result of setting $y=x-1$ in $\frac\d{\d y}f(y)$; then you need to find
$$
  c_n=\left.\left((y+1)\circ\frac\d{\d y}\right)^n((-y)^n)\right|_{y=0}.
$$
The operator $E=(y+1)\circ\frac\d{\d y}$ satisfies $E(y^k)=ky^k+ky^{k-1}$, from which one easily proves by induction that $E^m(y^k)|_{y=0}=0$ whenever $k>m$. Now  one computes
$$
  c_n = E^n\bigl((-y)^n\bigr)|_{y=0}
      = E^{n-1}\Bigl(n(-y)^n)-n(-y)^{n-1}\Bigr)|_{y=0}
      = -nE^{n-1}\bigl((-y)^{n-1}\bigr)|_{y=0}=-nc_{n-1}
$$
from which  $c_n=(-1)^nn!$ follows by induction.
A: It is convenient to use the coefficient of operator $[t^k]$ to denote the coefficient of $t^k$ in a series. This way we can write e.g.
\begin{align*}
  [t^k](1+t)^n=\binom{n}{k}\qquad\text{and}\qquad n![t^n]e^{kt}=k^n
  \end{align*}

We obtain
  \begin{align*}
  \sum_{k=0}^n(-1)^k\binom{n}{k}k^n&=\sum_{k=0}^\infty(-1)^k[u^k](1+u)^nn![t^n]e^{kt}\tag{1}\\
  &=n![t^n]\sum_{k=0}^\infty\left(-e^t\right)^k[u^k](1+u)^n\tag{2}\\
  &=n![t^n](1-e^t)^n\tag{3}\\
  &=(-1)^nn!\tag{4}
  \end{align*}
  and the claim follows.

Comment:


*

*In (1) we apply the coefficient of operator twice. We also extend the upper range of the series to $\infty$ without changing anything since we are adding zeros only.

*In (2) we do some rearrangements and use the linearity of the coefficient of operator.

*In (3) we use the substitution rule of the coefficient of operator with $u=-e^t$
\begin{align*}
  A(t)=\sum_{k=0}^\infty a_kt^k=\sum_{k=0}^\infty t^k[u^k]A(u)
  \end{align*}

*In (4) we select the coefficient of $t^n$ from $(1-e^t)^n=(t-\frac{t^2}{2!}\pm\cdots)^n$.
A: It is a partial case ($x=0$) of the Tepper's identity
$$
\sum^n_{k=0}(-1)^k\binom{n}{k}(x-k)^n=n!.
$$
