Proof of the summation $n!=\sum_{k=0}^n \binom{n}{k}(n-k+1)^n(-1)^k$?

Let $A=\{1,2,\ldots, n\}$. The number of bijective functions $f:A\to A$ is clearly $n!$.
On the other hand, the number of functions from $A$ to a set with $n-k+1$ elements is $(n-k+1)^n$ and there are $\binom{n}{k}$ ways for choosing a subset of $A$ with $n-k$ elements.
So the given formula directly follows from the inclusion-exclusion principle.

Another chance is to use the forward difference operator $\delta$ bringing a polynomial $p(x)$ to $p(x+1)-p(x)$. If $p$ is not a constant we have that the degree of $\delta p$ is the degree of $p$ minus one, and the leading term of $\delta p$ equals the leading term of $p'$. It follows that $\delta^n$ applied to $p(x)=x^n$ gives the constant $n!$ for any $x$, with $(\delta^{n}p)(1)$ being the given sum.


Note that, by commutativity, $$\sum_{k=0}^{n}\dbinom{n}{k}\left(n-k+1\right)^{n}\left(-1\right)^{k}=\sum_{k=0}^{n}\dbinom{n}{k}\left(k+1\right)^{n}\left(-1\right)^{n-k} $$ so let us consider $$\sum_{k=0}^{n}\dbinom{n}{k}x^{k+1}\left(-1\right)^{n-k}=x\left(x-1\right)^{n} $$ then if we differentiate and we multiply by $x$ we get $$\sum_{k=0}^{n}\dbinom{n}{k}\left(k+1\right)x^{k+1}\left(-1\right)^{n-k}=nx^{2}\left(x-1\right)^{n-1}+x\left(x-1\right)^{n} $$ and if we repeat the process $$\sum_{k=0}^{n}\dbinom{n}{k}\left(k+1\right)^{2}x^{k+1}\left(-1\right)^{n-k}=n\left(n-1\right)x^{3}\left(x-1\right)^{n-2}+2x^{2}n\left(x-1\right)^{n-1}+nx^{2}\left(x-1\right)^{n-1}+x\left(x-1\right)^{n} $$ and so if we repeat the process $n$ times we get $$\sum_{k=0}^{n}\dbinom{n}{k}\left(k+1\right)^{n}x^{k+1}\left(-1\right)^{n-k}=n!x^{n}+\textrm{addends with a positive power of }\left(x-1\right) $$ so if we evaluate the sum at $x=1$ we get

$$\sum_{k=0}^{n}\dbinom{n}{k}\left(k+1\right)^{n}\left(-1\right)^{n-k}=\color{red}{n!} $$

as wanted.


Another variation of the theme. In the following we use the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$ in a series. This way we can write e.g. \begin{align*} \binom{n}{k}=[z^k](1+z)^n\qquad\text{and}\qquad k^n=n![z^n]e^{kz} \end{align*}

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

Comment:

  • In (1) we exchange the order of summation $k\rightarrow n-k$

  • In (2) we extend the limit to infty without changing anything since we are adding zeros only. We apply the coefficient of operator to $\binom{n}{k}$ and to $(k+1)^n$ using $e^{(k+1)x}$.

  • In (3) we do a simple rearrangement

  • In (4) we use the substitution rule of the coefficient of operator \begin{align*} A(x)=\sum_{k=0}^\infty a_k x^k=\sum_{k=0}^\infty x^k [z^k]A(z) \end{align*}

  • In (5) we consider the series expansion \begin{align*} e^x(1-e^x)^n&=(1+x+\cdots)\left(-x+\frac{x^2}{2}-\cdots\right)^n\\ &=\left((-x)^n\pm\text{powers of }x\text{ greater than }n\cdots\right) \end{align*} and need only to respect the $x$-term with power equal to $n$.


Suppose we seek to evaluate

$$\sum_{k=0}^n {n\choose k} (-1)^k (n-k+1)^n.$$

Introduce

$$(n-k+1)^n = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp((n-k+1)z) \; dz.$$

We get for the sum

$$\frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp((n+1)z) \sum_{k=0}^n {n\choose k} (-1)^k \exp(-kz) \; dz \\ = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp((n+1)z) (1-\exp(-z))^n \; dz \\ = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp(z) (\exp(z)-1)^n \; dz.$$

This is $$n! [z^n] \exp(z) (\exp(z)-1)^n.$$

Now $$\exp(z)-1 = z + \frac{z^2}{2} + \frac{z^3}{6} +\cdots$$ and hence

$$(\exp(z)-1)^n = z^n + \cdots.$$

Therefore the result is

$$n! [z^0] \exp(z) = n!.$$