How to prove $\sum_{r=0}^{n}\left(-1\right)^r\binom{n}{r}\left(n-r\right)^n=n!$ [duplicate]

Solution 1:

An alternative approach. First note that by putting $s=n-r$ we get \begin{align} \sum_{r=0}^{n}{(-1)^r\binom{n}{r}\left(n-r\right)^n} &=\sum_{s=0}^{n}{(-1)^{n-s}\binom{n}{n-s}s^n}\\ &=\sum_{s=0}^{n}{(-1)^{n-s}\binom{n}{s}s^n}\\ &=(-1)^n\sum_{s=0}^{n}(-1)^s\binom{n}{s}s^n \end{align} hence it is equivalent to show: $$\sum_{s=0}^{n}(-1)^s\binom{n}{s}s^n=(-1)^nn!$$ Let consider the linear mapping \begin{align} \varphi&:\Bbb Z[x]\to\Bbb Z[x]& &f\mapsto (x+1)f'(x) \end{align} Then $\varphi^{\circ n}((x+1)^s)=s^n(x+1)^s$, hence \begin{align} \sum_{s=0}^{n}(-1)^s\binom{n}{s}s^n(x+1)^s &=\varphi^{\circ n}\left(\sum_{s=0}^{n}(-1)^s\binom{n}{s}(x+1)^s\right)\\ &=\varphi^{\circ n}((-x)^n)\\ &=(-1)^n\varphi^{\circ n}(x^n) \end{align} We claim that $$\varphi^{\circ k}(x^n)\equiv(x+1)^k\frac{n!}{(n-k)!}x^{n-k}\pmod{x^{n-k+1}}$$ This is easily proven by induction since: \begin{align} \varphi^{\circ(k+1)}(x^n) &\equiv k(x+1)^k\frac{n!}{(n-k)!}x^{n-k}+(x+1)^{k+1}\frac{n!}{(n-k)!}(n-k)x^{n-k-1}\\ &\equiv(x+1)^{k+1}\frac{n!}{(n-k-1)!}x^{n-k-1}\pmod{x^{n-k}} \end{align} Consequently, $\varphi^{\circ n}(x^n)=(x+1)^nn!$ and evaluating at $x=0$ the identity will follows.

Solution 2:

Let $\nabla_h$ be the backward finite difference operator with step size $h>0$: $$\nabla_hf(x)=f(x)-f(x-h)$$ Then the $n$-th iteration of this operator is given by $$\nabla_h^nf(x)=\sum_{r=0}^n(-1)^r {n \choose r}f(x-rh)\tag{1}$$ Finally, it's not too hard to prove that derivatives and finite differences are related when $h\rightarrow 0$: $$f^{(n)}(x)=\lim_{h\rightarrow 0}\frac{\nabla_h^nf(x)}{h^n}\tag{2}$$ Applying $(1)$ and $(2)$ at $x=0$ for $f(x)=x^n$, $$n!=\lim_{h\rightarrow 0}\sum_{r=0}^n(-1)^r {n \choose r}\left(\frac 0 h - r\right)^n=\sum_{r=0}^n(-1)^r {n \choose r}\left(- r\right)^n$$ In other words $$n!=\sum_{r=0}^n(-1)^{n-r} {n \choose r}r^n=\sum_{r=0}^n(-1)^{r} {n \choose r}(n-r)^n$$

Solution 3:

By the first answer in this question about the number of surjective functions we have

$$|S| = n^m - {n \choose 1}(n-1)^m + {n \choose 2}(n-2)^m - \dots \pm {n \choose n}(n-n)^m,$$ where $S=S_{m,n}$ denotes the number of surjective functions $f\colon M\to N$ and $M, N$ have cardinalities $m,n$ respectively. Since every surjective function from the finite set $N$ to itself is bijective we have $|S_{n,n}|=n!$. This is the desired result.