how to prove this combinatorial identity I accidentally find? Today when I solve a counting problem using different methods I find the following (seemingly correct) combinatorial identity, but I can't find it on the Internet and I can't prove its correctness neither. But I have verified its correctness with positive integer $n$ within $[0, 1000]$ using a simple computer program. Anyone can give a proof to this identity (or any link to its proof)?
$$\frac{(n+1)n}{2} \cdot n! = \sum\limits_{k=0}^{n} (-1)^k \cdot \frac{n!}{k!\cdot(n-k)!} \cdot (n-k)^{n+1}$$
And equivalently if you want,
$$\frac{(n+1)n}{2} = \sum\limits_{k=0}^{n} (-1)^k \cdot \frac{1}{k!\cdot(n-k)!} \cdot (n-k)^{n+1}$$
 A: The identity can be written
$$n!\binom{n+1}2=\sum_k(-1)^k\binom{n}k(n-k)^{n+1}\;.\tag{1}$$
The righthand side has the look of an inclusion-exclusion calculation, so we can look for a combinatorial interpretation on that basis. If $K$ is a subset of $[n]=\{1,\ldots,n\}$ with $k$ elements, $(n-k)^{n+1}$ can be interpreted as the number of functions from $[n+1]$ to $[n]\setminus K$. If for $k\in[n]$ we let $A_k$ be the set of functions from $[n+1]$ to $[n]\setminus\{k\}$, then for each $K\subseteq[n]$ with $|K|=k$ we have
$$\left|\,\bigcap_{k\in K}A_k\,\right|=(n-k)^{n+1}\;.$$
There are $\binom{n}k$ such subsets of $[n]$, so
$$\begin{align*}
\left|\bigcup_{k=1}^nA_k\right|&=\sum_{\varnothing\ne K\subseteq[n]}(-1)^{|K|+1}\left|\,\bigcap_{k\in K}A_k\,\right|\\
&=\sum_{\varnothing\ne K\subseteq[n]}(-1)^{|K|+1}(n-k)^{n+1}\\
&=\sum_{k=1}^n(-1)^{k+1}\binom{n}k(n-k)^{n+1}\;.
\end{align*}$$
$\bigcup_{k=1}^nA_k$ is the set of functions from $[n+1]$ to $[n]$ that are not surjections, so the number of surjections from $[n+1]$ to $[n]$ must be
$$\begin{align*}
n^{n+1}-\left|\bigcup_{k=1}^nA_k\right|&=n^{n+1}-\sum_{k=1}^n(-1)^{k+1}\binom{n}k(n-k)^{n+1}\\
&=n^{n+1}+\sum_{k=1}^n(-1)^k\binom{n}k(n-k)^{n+1}\\
&=\sum_{k=0}^n(-1)^k\binom{n}k(n-k)^{n+1}\;.
\end{align*}$$
To complete the proof of $(1)$ we need only show that there are $n!\binom{n+1}2$ surjections from $[n+1]$ to $[n]$. 
If $f:[n+1]\to[n]$ is a surjection, there must be distinct $k,\ell\in[n+1]$ such that $f(k)=f(\ell)$, while $f$ is injective on $[n+1]\setminus\{k,\ell\}$. Let $D=[n+1]\setminus\{\ell\}$; each surjection $g$ from $D$ to $[n]$ extends to a unique surjection $f:[n+1]\to[n]$ with $f(k)=f(\ell)$, the function defined by
$$f(i)=\begin{cases}
g(i),&\text{if }i\in D\\
g(k),&\text{if }i=\ell\;.
\end{cases}$$
Every surjection $f:[n+1]\to[n]$ such that $f(k)=f(\ell)$ arises in this way from a surjection from $D$ to $[n]$, and $|D|=n$ so there are $n!$ surjections from $D$ to $[n]$ and hence $n!$ surjections $f:[n+1]\to[n]$ such that $f(k)=f(\ell)$. Finally, there are $\binom{n+1}2$ ways to choose the $k$ and $\ell$ that $f$ is to send to the same element of $[n]$, so there are altogether $n!\binom{n+1}2$ surjections from $[n+1]$ to $[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}$

$\ds{\sum_{k = 0}^{n}\pars{-1}^{k}{n! \over k!\pars{n - k}!}
\,\pars{n - k}^{n + 1}\ =\
{\pars{n + 1}n \over 2}\,n!:\ ?}$

\begin{align}
&\color{#f00}{\sum_{k = 0}^{n}\pars{-1}^{k}\,{n! \over k!\pars{n - k}!}
\,\pars{n - k}^{n + 1}}\ =\
\sum_{k = 0}^{n}\pars{-1}^{k}\,{n \choose k}\
\overbrace{\pars{n + 1}!
\oint_{\verts{z}\ =\ 1}{\expo{\pars{n - k}z} \over z^{n + 2}}
\,{\dd z \over 2\pi\ic}}^{\ds{\pars{n - k}^{n + 1}}}
\\[5mm] = &
\pars{n + 1}!\oint_{\verts{z}\ =\ 1}\,\,
{\expo{nz} \over z^{n + 2}}\,\,
\sum_{k = 0}^{n}{n \choose k}\pars{-\expo{-z}}^{\, k}\,{\dd z \over 2\pi\ic}
\\[5mm] = &\
\pars{n + 1}!\oint_{\verts{z}\ =\ 1},\,\,
{\expo{nz} \over z^{n + 2}}\,\pars{1 - \expo{-z}}^{n}\,{\dd z \over 2\pi\ic} =
\pars{n + 1}!\oint_{\verts{z}\ =\ 1}\,\,
{\pars{\expo{z} - 1}^{n} \over z^{n + 2}}\,{\dd z \over 2\pi\ic}\tag{1}
\end{align}

$\ds{\pars{\expo{z} - 1}^{n}}$ is related, as a generating function, to the
Stirling Numbers of the Second Kind. Namely,
\begin{equation}
\pars{\expo{z} - 1}^{n} =
n!\sum_{j = 0}^{\infty}\braces{j \atop n}\,{z^{\, j} \over j!}
\tag{1.1}
\end{equation}
$\ds{\braces{j \atop n}}$ is a Stirling Number of the Second Kind. 
With this expression, $\ds{\pars{1}}$ is reduced to:
\begin{align}
&\color{#f00}{\sum_{k = 0}^{n}\pars{-1}^{k}\,{n! \over k!\pars{n - k}!}
\,\pars{n - k}^{n + 1}}\ =\
\pars{n + 1}!\, n!\sum_{j = 0}^{\infty}{\braces{j \atop n} \over j!}\
\overbrace{\oint_{\verts{z}\ =\ 1}\,\,
{1 \over z^{n + 2 - j}}\,\,{\dd z \over 2\pi\ic}}
^{\ds{\delta_{n + 2 - j,1}}}
\\[5mm] = &\
\pars{n + 1}!\, n!\sum_{j = 0}^{\infty}{\braces{j \atop n} \over j!}\,
\delta_{j,n + 1} =
\pars{n + 1}!\, n!\,{\braces{n + 1 \atop n} \over \pars{n + 1}!} =
n!\braces{n + 1 \atop n}\tag{2}
\end{align}

However, $\ds{\braces{n + 1 \atop n}}$ satisfies the 'simple identity'
$\ds{\braces{n + 1 \atop n} = {n + 1 \choose 2} = {\pars{n + 1}n \over 2}}$ such that the expression $\ds{\pars{2}}$ becomes:
$$
\color{#f00}{\sum_{k = 0}^{n}\pars{-1}^{k}\,{n! \over k!\pars{n - k}!}
\,\pars{n - k}^{n + 1}} =
\color{#f00}{{\pars{n + 1}n \over 2}\,n!}
$$


ADDENDA:
  
  Following @MarkoRiedel comment ( see below ), we can 'jump directly' from expression $\ds{\pars{1}}$:
  \begin{align}
&\color{#f00}{\sum_{k = 0}^{n}\pars{-1}^{k}\,{n! \over k!\pars{n - k}!}
\,\pars{n - k}^{n + 1}} =
\pars{n + 1}!\bracks{z^{n + 1}}\bracks{\pars{\expo{z} - 1}^{n}}
\\[5mm] = &
\pars{n + 1}!\bracks{n!\,{\braces{n + 1 \atop n} \over \pars{n + 1}!}} =
n!\braces{n + 1 \atop n} =
\color{#f00}{{\pars{n + 1}n \over 2}\,n!}
\end{align}
  where we used the generating function $\ds{\pars{1.1}}$.

A: Another way is to consider that the backward finite difference (backward Delta) is defined as
$$
\nabla _x \,f(x) = f(x) - f(x - 1)
$$
and we have that its $n$-th iteration is:
$$
\nabla _x ^n \,f(x) = \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left( { - 1} \right)^k \left( \begin{gathered}
  n \\ 
  k \\ 
\end{gathered}  \right)\;f(x - k)} 
$$
therefore the RHS is:
$$
\sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left( { - 1} \right)^k \left( \begin{gathered}
  n \\ 
  k \\ 
\end{gathered}  \right)\;\left( {n - k} \right)^{n + 1} }  = \left. {\nabla _x ^n \,x^{n + 1} } \right|_{\,x = n} 
$$
Now $x^{\,n + 1} $ is a polynomial of degree $n+1$ and we can express it in terms
of the Stirling Numbers of $2$nd kind and Falling Factorials of $x$ as
$$
x^{\,n + 1}  = \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left\{ \begin{gathered}
  n + 1 \\ 
  k \\ 
\end{gathered}  \right\}\;x^{\,\underline {\,k\;} } } 
$$
The backward Delta of the falling factorial is given by:
$$
\begin{gathered}
  \nabla _x \;x^{\,\underline {\,m\;} }  = \left( {x\left( {x - 1} \right) \cdots \left( {x - m + 1} \right)} \right) - \left( {\left( {x - 1} \right)\left( {x - 2} \right) \cdots \left( {x - m} \right)} \right) = m\left( {x - 1} \right)^{\,\underline {\,m - 1\;} }  \hfill \\
  \nabla _x ^{\,n} \;x^{\,\underline {\,m\;} }  = m^{\,\underline {\,n\;} } \left( {x - n} \right)^{\,\underline {\,m - n\;} } \quad  \Rightarrow \quad \nabla _x ^{\,n} \;x^{\,\underline {\,m\;} }  = 0\quad \left| {\;m < n} \right. \hfill \\ 
\end{gathered} 
$$
therefore:
$$
\begin{gathered}
  \nabla _x ^n \,x^{n + 1}  = \nabla _x ^n \,\sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left\{ \begin{gathered}
  n + 1 \\ 
  k \\ 
\end{gathered}  \right\}\;x^{\,\underline {\,k\;} } }  = \nabla _x ^n \,\left( {\left\{ \begin{gathered}
  n + 1 \\ 
  n + 1 \\ 
\end{gathered}  \right\}\;x^{\,\underline {\,n + 1\;} }  + \left\{ \begin{gathered}
  n + 1 \\ 
  n \\ 
\end{gathered}  \right\}\;x^{\,\underline {\,n\;} } } \right) =  \hfill \\
   = \left( {\left\{ \begin{gathered}
  n + 1 \\ 
  n + 1 \\ 
\end{gathered}  \right\}\;\left( {n + 1} \right)^{\,\underline {\,n\;} } \left( {x - n} \right)^{\,\underline {\,1\;} }  + \left\{ \begin{gathered}
  n + 1 \\ 
  n \\ 
\end{gathered}  \right\}n^{\,\underline {\,n\;} } \;\left( {x - n} \right)^{\,\underline {\,0\;} } } \right) =  \hfill \\
   = \left( {1\;\left( {n + 1} \right)^{\,\underline {\,n\;} } \left( {x - n} \right)^{\,\underline {\,1\;} }  + \left( \begin{gathered}
  n + 1 \\ 
  n - 1 \\ 
\end{gathered}  \right)n^{\,\underline {\,n\;} } \;\left( {x - n} \right)^{\,\underline {\,0\;} } } \right) =  \hfill \\
   = n!\left( {\;\left( \begin{gathered}
  n + 1 \\ 
  n \\ 
\end{gathered}  \right)\left( {x - n} \right) + \left( \begin{gathered}
  n + 1 \\ 
  n - 1 \\ 
\end{gathered}  \right)} \right) \hfill \\ 
\end{gathered} 
$$
which, calculated at $x=n$ gives:
$$
\begin{gathered}
  \sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \,n} \right)} {\left( { - 1} \right)^k \left( \begin{gathered}
  n \\ 
  k \\ 
\end{gathered}  \right)\;\left( {n - k} \right)^{n + 1} }  = \left. {\nabla _x ^n \,x^{n + 1} } \right|_{\,x = n}  =  \hfill \\
   = n!\left( \begin{gathered}
  n + 1 \\ 
  n - 1 \\ 
\end{gathered}  \right) = n!\frac{{\left( {n + 1} \right)n}}
{2} \hfill \\ 
\end{gathered} 
$$
thus proving your assertion, while generalizing it to other values of $x$.
A: Here   is another variation of the theme. 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*}
\binom{n}{k}=[t^k](1+t)^n\qquad\text{and}\qquad  k^n=n![t^n]e^{kt}
\end{align*}

OPs identity can be written as
\begin{align*}
\frac{n}{2}(n+1)!=\sum_{k=0}^n&(-1)^k\binom{n}{k}(n-k)^{n+1}\quad\qquad n\geq 0
\end{align*}
We      start with the right-hand side and obtain
  \begin{align*}
\sum_{k=0}^n&(-1)^k\binom{n}{k}(n-k)^{n+1}\\
&=\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}k^{n+1}\tag{1}\\
&=\sum_{k=0}^\infty(-1)^{n-k}[u^k](1+u)^n(n+1)![t^{n+1}]e^{kt}\tag{2}\\
&=(-1)^n(n+1)![t^{n+1}]\sum_{k=0}^\infty(-e^t)^k[u^k](1+u)^n\tag{3}\\
&=(-1)^n(n+1)![t^{n+1}]\left(1-e^t\right)^n\tag{4}\\
&=(n+1)![t^{n+1}]\left(t+\frac{t^2}{2}+\cdots\right)^n\tag{5}\\
&=\frac{n}{2}(n+1)!\tag{6}
\end{align*}
  and the claim follows.

Comment:


*

*In (1) we change the order of  summation: $k\longrightarrow n-k$

*In (2) we apply the coefficient of operator twice. We also extend the range of summation to infinity without changing anything, since we are adding zeros only.

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

*In (4) we use the substitution rule 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 (5) we factor out $(-1)^n$ and expand the exponential series.

*In (6) we note that in order to extract the coefficient of $t^{n+1}$ we have $n$ possibilities to select the term $t$ and one possibility to select the the term $\frac{t^2}{2}$ giving $\frac{n}{2}$.
A: Write $$(n-k)^{n+1}=\sum_{j=0}^{n+1}\,a_j\,\binom{k}{j}$$ for some $a_0,a_1,a_2,\ldots,a_{n+1}\in\mathbb{Z}$.  Clearly, $$a_{n+1}=(-1)^{n+1}\,(n+1)!$$ and $$a_n=(-1)^n\,\frac{n(n+1)}{2}\,n!\,.$$
That is,
$$\sum_{k=0}^{n}\,(-1)^k\,\binom{n}{k}\,(n-k)^{n+1}=\sum_{k=0}^n\,(-1)^k\,\binom{n}{k}\,\sum_{j=0}^{n+1}\,a_j\,\binom{k}{j}=\sum_{j=0}^{n+1}\,a_j\,\sum_{k=0}^n\,(-1)^k\,\binom{n}{k}\,\binom{k}{j}\,.$$
Using the identity $\binom{n}{k}\,\binom{k}{j}=\binom{n}{j}\,\binom{n-j}{k-j}$ for integers $n,k,j$ with $0\leq j\leq k\leq n$, we obtain
$$\sum_{k=0}^n\,(-1)^k\,\binom{n}{k}\,(n-k)^{n+1}=\sum_{j=0}^{n}\,(-1)^j\,a_j\,\binom{n}{j}\,\sum_{k=j}^n\,(-1)^{k-j}\,\binom{n-j}{k-j}\,,$$
or
$$\sum_{k=0}^n\,(-1)^k\,\binom{n}{k}\,(n-k)^{n+1}=(-1)^n\,a_n=\frac{n(n+1)}{2}\,n!\,.$$
P.S. While the term involving $a_{n+1}$ vanishes, the coefficient $a_{n+1}$ need be evaluated in order to determine $a_n$.  In general,
$$\sum_{k=0}^n\,(-1)^k\,\binom{n}{k}\,f(k)=(-1)^n\,b_n\,,$$
where $$f(x)=\sum_{j=0}^d\,b_j\,\binom{x}{j}$$ with $d\in\mathbb{Z}$ greater than or equal to $n$ and $b_0,b_1,b_2,\ldots,b_d\in K$, where $K$ is an extension field of $\mathbb{Q}$.
