Expressing a factorial as difference of powers: $\sum_{r=0}^{n}\binom{n}{r}(-1)^r(l-r)^n=n!$? The successive difference of powers of integers leads to factorial of that power. Here's the formula:

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

Can anyone give a proof of this result?
Note: The original question was to prove the more general

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

for an integer $l$, which some of the answers address.
 A: Using the definition of  the Exponential Series, 
$$e^x=\sum_{0\le r<\infty}\frac{x^r}{r!} \implies e^x-1=x+\frac{x^2}{2!}++\frac{x^3}{3!}+\cdots$$
Taking $n$th power, $$ (e^x-1)^n=\left(x+\frac{x^2}{2!}++\frac{x^3}{3!}+\cdots\right)^n$$
$$\text{Now, }(e^x-1)^n=e^{nx}-\binom n1e^{(n-1)x}+\binom n2e^{(n-2)x}-\cdots$$
$$=\sum_{0\le r<\infty}\frac{(nx)^r}{r!}-\binom n1\sum_{0\le r<\infty}\frac{\{(n-1)x\}^r}{r!}+\binom n2\sum_{0\le r<\infty}\frac{\{(n-2)x\}^r}{r!}-\cdots$$
So, the coefficient of $x^r$ in $(e^x-1)^n$
$$\frac{n^r}{r!}-\binom n1\frac{(n-1)^r}{r!}+\binom n2\frac{(n-2)^r}{r!}-\cdots$$
$$\text{ Again, } \left(x+\frac{x^2}{2!}++\frac{x^3}{3!}+\cdots\right)^n=x^n+\text{ the higher powers of } x$$
Equating we get
$$\frac{n^r}{r!}-\binom n1\frac{(n-1)^r}{r!}+\binom n2\frac{(n-2)^r}{r!}-\cdots=\begin{cases} 0 &\mbox{if } 0\le r< n \\
1 & \mbox{if } r=n  \end{cases} $$
A: Suppose we are trying to evaluate
$$\sum_{q=0}^n {n\choose q} (-1)^q (k-q)^n.$$
Observe that
$$(k-q)^n =
\frac{n!}{2\pi i}\int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp((k-q)z) \; dz.$$
This gives for the sum the integral
$$\frac{n!}{2\pi i}\int_{|z|=\epsilon} \frac{1}{z^{n+1}} 
\sum_{q=0}^n {n\choose q} (-1)^q \exp((k-q)z) \; dz
\\ = \frac{n!}{2\pi i}\int_{|z|=\epsilon} \frac{\exp(kz)}{z^{n+1}} 
\sum_{q=0}^n {n\choose q} (-1)^q \exp(-qz) \; dz
\\ = \frac{n!}{2\pi i}\int_{|z|=\epsilon} \frac{\exp(kz)}{z^{n+1}} 
(1-\exp(-z))^n \; dz.$$
Observe that $$1-\exp(-z) = z-\frac{1}{2}z^2+\frac{1}{6}z^3-\cdots$$
so $(1-\exp(-z))^n$ starts at $z^n$, which means that the residue is one ($\exp(kz)$ starts at $z^0$),
giving $$n!$$ as the end result.
A: In the following we use the coefficient of operator $[z^r]$ to denote the coefficient of $z^r$ in a series. This way we can write e.g.
\begin{align*}
\binom{n}{r}=[z^r](1+z)^n\qquad\text{and}\qquad  r^n=n![z^n]e^{rz}
\end{align*}

We obtain for $n\geq 0$ and $l\in\mathbb{C}$
  \begin{align*}
\sum_{r=0}^n&\binom{n}{r}(-1)^r(l-r)^n\\
&=\sum_{r=0}^\infty[z^r](1+z)^n(-1)^rn![u^n]e^{(l-r)u}\tag{1}\\
&=n![u^n]e^{lu}\sum_{r=0}^\infty\left(-e^{-u}\right)^r[z^r](1+z)^n\tag{2}\\
&=n![u^n]e^{lu}\left(1-e^{-u}\right)^n\tag{3}\\
&=n![u^n]u^n\tag{4}\\
&=n!\\
\end{align*}
  and the claim follows.
Please note the formula is valid for any $l$.

Comment:


*

*In (1) we apply the coefficient of operator to $\binom{n}{r}$ and to $(l-r)^n$ using $e^{(l-r)u}$. We also extend the limit to infty without changing anything since we are adding zeros only.

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

*In (3) we apply the substitution rule
\begin{align*}
A(u)=\sum_{r=0}^\infty a_r u^r=\sum_{r=0}^\infty u^r [z^r]A(z)
\end{align*}

*In (4) we consider  the series expansion
\begin{align*}
e^{lu}(1-e^{-u})^n&=(1+lu+\cdots)\left(u-\frac{u^2}{2}+\cdots\right)^n\\
&=1\cdot\left(u^n\mp\text{powers of }u\text{ greater than }n\cdots\right)
\end{align*}
and need only to respect the $u$-term with power equal to $n$.
A: Let $A:=\{ x_1,..,x_n \}$ and $B=\{y_1,..,y_m \}$.
Lets count the number of onto functions $f:A \to B$. There are $m^n$ functions from $A$ to $B$. Lets count now the ones which are not onto:
Define
$$P_i= \{ f : A \to B |y_i \notin f(A) \}$$ 
Then we need to figure out the cardinality of $\cup_i P_i$.
By the inclusion exclusion principle
$$|P_1 \cup P_2 ..\cup P_m |=\sum |P_i|-\sum |P_i \cap P_j|+\sum |P_i \cap P_j \cap P_k| -... \\=\binom{m}{1}(m-1)^n-\binom{m}{2}(m-2)^n+\binom{m}{3}(m-3)^n-...
$$
Thus in total there are 
$$m^n-\binom{m}{1}(m-1)^n+\binom{m}{2}(m-2)^n-\binom{m}{3}(m-3)^n-...=\sum_{k=0}^m (-1)^k\binom{m}{k}(m-k)^n$$
When $n=m$ the number of onto functions is
$$\sum_{k=0}^n (-1)^k\binom{n}{k}(n-k)^n$$
But any function  $f: \{ x_1,..,x_n \} \to\{y_1,..,y_n \}$ is onto if and only if it is a bijection. Thus the number of onto functions is equal to the number of bijections, which is $n!$.
Hence
$$\sum_{k=0}^n (-1)^k\binom{n}{k}(n-k)^n=n!$$
A: This identity also has an algebraic proof. Suppose the sum we are trying to evaluate is given by
$$\sum_{k=0}^n {n\choose k} (-1)^k (n-k)^{n}.$$
Observe that when we multiply two exponential generating functions of the sequences $\{a_n\}$ and $\{b_n\}$ we get that
\begin{align}
 A(z) B(z) &= \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!}
= \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\
&= \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!}
= \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}
\end{align}
i.e. the product of the two generating functions is the generating function of
$$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$
Now in the present case we clearly have
$$A(z) = \sum_{q\ge 0} (-1)^q \frac{z^q}{q!} = \exp(-z).$$
Furthermore we have
$$B_n(z) = \sum_{q\ge 1} q^{n} \frac{z^q}{q!}
 = \exp(z) \sum_{k=1}^{n} {n\brace k} z^k,$$
as can be seen by induction. For $n=1$ we have
$$B_1(z) = \sum_{q\ge 1} q \frac{z^q}{q!}
= z \sum_{q\ge 1} \frac{z^{q-1}}{(q-1)!} = \exp(z)\times  z.$$
Now using the induction hypothesis we have $$B_{n+1}(z) = z \frac{d}{dz} B_n(z)
= z \exp(z) \sum_{k=1}^{n} {n\brace k} k z^{k-1}
+ z \exp(z) \sum_{k=1}^{n} {n\brace k} z^k.$$
This is
\begin{align}
& z \exp(z) \sum_{k=0}^{n-1} {n\brace k+1} (k+1) z^k
+ z \exp(z) \sum_{k=1}^{n} {n\brace k} z^k \\
&= z \exp(z) \left({n\brace 1} +
\sum_{k=1}^{n-1} \left({n\brace k+1} (k+1)+{n\brace k}\right)z^k+
{n\brace n} z^{n}\right) \\ 
&=  z \exp(z) \left({n+1\brace 1} + \sum_{k=1}^{n-1} {n+1\brace k+1} z^k +
{n+1\brace n+1} z^{n}\right) \\ 
&= \exp(z) \left({n+1\brace 1} z + \sum_{k=1}^{n-1} {n+1\brace k+1} z^{k+1} +
{n+1\brace n+1} z^{n+1}\right)
= \exp(z) \sum_{k=1}^{n+1} {n+1\brace k} z^k.
\end{align}
Returning to the original problem we find that the sum has the value
$$n! [z^n] A(z) B_n(z) = n! [z^n] \sum_{k=1}^{n} {n\brace k} z^k
= n! {n\brace n} = n!$$
which was to be shown.
A useful exercise in the algebra of Stirling numbers and binomial coefficients. Here is a MSE link that points to another calculation of the same type.
Addendum. In response to the comment we can actually show that
$$\sum_{k=0}^n {n\choose k} (-1)^k (l-k)^{n}$$
for $l$ an integer.
Observe that $$l-k = (n-k)+(l-n)$$ and put $p=l-n.$
Using the same setup as before we now have
\begin{align}
B(z) &= \sum_{q\ge 0} (q+p)^n \frac{z^q}{q!}
= \sum_{q\ge 0} \sum_{m=0}^n {n\choose m} q^m p^{n-m} \frac{z^q}{q!}
\\
&= \sum_{q\ge 0} p^n  \frac{z^q}{q!} + 
\sum_{q\ge 0} \sum_{m=1}^n {n\choose m} q^m p^{n-m} \frac{z^q}{q!}
=  \exp(z) p^n +\sum_{m=1}^n {n\choose m} p^{n-m} \sum_{q\ge 0} q^m  \frac{z^q}{q!}
\\ 
&=  \exp(z) p^n +
\exp(z) \sum_{m=1}^n {n\choose m} p^{n-m}  \sum_{k=1}^m {m\brace k} z^k.
\end{align}
This formula also holds for $p=0$ if we assume that $0^0=1$, in which case it produces the first formula we derived above.
It follows that
$$n! [z^n] A(z) B_n(z) =
n! [z^n] \left(p^n+\sum_{m=1}^n {n\choose m} p^{n-m}  
\sum_{k=1}^m {m\brace k} z^k\right)
= n! {n\choose n} {n\brace n} = n!$$
thereby showing the result for all $l.$
Addendum Oct 10 2016. There is really nothing to prove here as the formula $$\frac{1}{n!} \sum_{k=0}^n {n\choose k} (-1)^{n-k} k^m$$ by definition gives the Stirling number of the second kind $${m\brace n}.$$
A: In this answer are three different proofs of this cancellation lemma:
$$
\sum_{j=k}^n(-1)^{n-j}\binom{n}{j}\binom{j}{k}
=\left\{\begin{array}{}
1&\text{if }n=k\\
0&\text{otherwise}
\end{array}\right.\tag{1}
$$
Inductively, we can see that any polynomial in $j$ of degree $m$ can be written uniquely as
$$
\sum_{k=0}^mc_k\binom{j}{k}\tag{2}
$$
where the coefficient of $j^m$ is $\dfrac{c_m}{m!}$.
Putting $(1)$ and $(2)$ together, for $m\le n$, we have
$$
\begin{align}
\sum_{j=0}^{n}(-1)^{n-j}\binom{n}{j}\sum_{k=0}^mc_k\binom{j}{k}
&=\sum_{k=0}^m\sum_{j=0}^{n}(-1)^{n-j}\binom{n}{j}\binom{j}{k}\\
&=c_n\tag{3}
\end{align}
$$
If $m\lt n$, then $c_n=0$. If $m=n$, then $c_n$ is $n!$ times the coefficient of $j^n$.

Applying $(3)$
$$
\begin{align}
\sum_{r=0}^n\binom{n}{r}(-1)^r(l-r)^n
&=\sum_{r=0}^n(-1)^{n-r}\binom{n}{r}(r-l)^n\\
&=n!\tag{4}
\end{align}
$$
because, for any $l$, $(r-l)^n$ is a degree $n$ polynomial in $r$ in which the coefficient of $r^n$ is $1$.
