To prove: $n!=\sum\limits_{r=0}^n (-1)^r \binom{n}{r} (n-r)^n$ How to algebraically prove that $$n!=\sum\limits_{r=0}^n (-1)^r \binom{n}{r} (n-r)^n$$
I was trying to find number of onto functions from $A$ to $A$ containing $n$ elements.
Using the inclusion-exclusion principle I am getting 
$$\sum\limits_{r=0}^n (-1)^r \binom{n}{r} (n-r)^n.$$
We can also do it by simple combinatorics, as every element has to have a pre-image and number of elements in the domain equal to the number of elements in the codomain, the number of functions is $n!.$ 
Is there an algebraic way to prove these two are equal?
 A: Actually, we have that
$$
n! = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( { - 1} \right)^{\,k} \left( \matrix{
  n \hfill \cr 
  k \hfill \cr}  \right)\left( {n - k} \right)^{\,n} }  = \left. {\sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( { - 1} \right)^{\,k} \left( \matrix{
  n \hfill \cr 
  k \hfill \cr}  \right)\left( {x - k} \right)^{\,n} \;} } \right|_{\,x\, = \,n}  = \left. {\sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( { - 1} \right)^{\,k} \left( \matrix{
  n \hfill \cr 
  k \hfill \cr}  \right)p_{\,n} (x - k)\;} } \right|_{\,x\, = \,n} 
$$
for any $x \in \mathbb R$ or even $x \in \mathbb C$, and for any polynomial in $x$ of degree $n$, with leading coefficient $1$.
That's because the Backward Difference, defined as
$$
\nabla _x f(x) = f(x) - f(x - 1)
$$
and which reiterates as
$$
\nabla _x ^{\,n} f(x) = \nabla _x ^{\,n - 1} f(x) - \nabla _x ^{\,n - 1} f(x - 1) = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( { - 1} \right)^{\,k} \left( \matrix{
  n \hfill \cr 
  k \hfill \cr}  \right)f\left( {x - k} \right)} 
$$
when applied to a polynomial of degree $n$
$$
p_{\,n} (x) = \sum\limits_{0\, \le \,m\, \le \,n} {a_{\,n} x^{\,n} } 
$$
gives
$$
\nabla _n ^{\,n} p_{\,n} (n) = \left. {\nabla _x ^{\,n} p_{\,n} (x)\,} \right|_{\,x\, = \,n}  = a_{\,n} \,n!
$$
as it is easy to verify, if you know Stirling Numbers and Falling factorials.
A: Let $$\Delta f(x)=f(x+1)-f(x),$$ $$Df(x)=f'(x).$$ Since
$$f(x+1)-f(x)=f'(x)+\frac{f''(x)}{2!}+\frac{f'''(x)}{3!}+\cdots,$$
we have
$$\Delta=D+\frac{D^2}{2!}+\frac{D^3}{3!}+\cdots.$$
Hence $$\Delta^nf(x)=\left(D+\frac{D^2}{2!}+\frac{D^3}{3!}+\cdots\right)^nf(x).\label{1}\tag{1}$$
Applying successively the finite difference operator, we obtain
$$\Delta^nf(x)=\sum_{r=0}^{n}(-1)^r {n\choose r}f(x+n-r)\label{2}\tag{2}.$$
If $f(x)=x^n$ then $D^nf(x)=n!$, and $D^mf(x)=0$ if $m>n$. Thus combining \eqref{1} and \eqref{2} we get
$$n!=\sum_{r=0}^{n}(-1)^r {n\choose r}(x+n-r)^n.$$
The desired result follows by setting $x=0$. Note that this works in greater generality.
A: It  is convenient to use the  coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series. This way we can write for instance
$$n![z^n]e^{rz}=r^n$$

We obtain
  \begin{align*}
\color{blue}{\sum_{r=0}^n}&\color{blue}{(-1)^r\binom{n}{r}(n-r)^n}\\
&=\sum_{r=0}^n(-1)^{n-r}\binom{n}{r}r^n\tag{1}\\
&=\sum_{r=0}^n(-1)^{n-r}\binom{n}{r}n![z^n]e^{rz}\tag{2}\\
&=n![z^n]\sum_{r=0}^n\binom{n}{r}\left(e^{z}\right)^r(-1)^{n-r}\tag{3}\\
&=n![z^n](e^{z}-1)^n\tag{4}\\
&=n![z^n](z+\frac{z^2}{2!}+\cdots)^n\tag{5}\\
&\color{blue}{=n!}
\end{align*}
  and the claim follows.

Comment:


*

*In (1) we change the order of summation by setting $r \rightarrow n-r$ and use the binomial identity $\binom{p}{q}=\binom{p}{p-q}$.

*In (2) we apply the coefficient of operator.

*In (3) we use the linearity of the coefficient of operator and do a little rearrangement as preparation for the next step.

*In (4) we apply the binomial theorem.

*In (5) we do the series expansion of $e^{z}$ and see the smallest exponent of $z$ in $(e^{z}-1)^n$ is $\color{blue}{n}$. So, we will only use the constant $\color{blue}{1}$ in the series expansion.
