Simplify binomial sum It is well-known that for any integer $j$
$$
\sum _{i=0}^k (-1)^{i} \binom{k}{i} (j-i)^k = k!
$$
But I wonder if there's a closed form for the following sum
$$
\sum _{i=j}^k (-1)^{i} \binom{k}{i} (j-i)^k
$$
The following table gives the value for this $k = 1,\cdots, 6$ and $j = 0, \cdots k$.
1   0                   
2   1   0               
6   5   1   0           
24  23  12  1   0       
120 119 93  27  1   0   
720 719 662 360 58  1   0

 A: Suppose we seek an alternate representation of
$$\sum_{p=q}^k (-1)^p {k\choose p} (q-p)^k.$$
This is
$$\sum_{p=0}^k (-1)^p {k\choose p} (q-p)^k
- \sum_{p=0}^{q-1} (-1)^p {k\choose p} (q-p)^k.$$
We get for the first piece
$$k! [z^k] \sum_{p=0}^k (-1)^p {k\choose p} \exp((q-p)z)
\\ = k! [z^k] \exp(qz) 
\sum_{p=0}^k (-1)^p {k\choose p} \exp(-pz)
\\ = k! [z^k] \exp(qz) (1-\exp(-z))^k.$$
Now $(1-\exp(-z))^k = z^k + \cdots$ so this evaluates to $k!.$
We thus have
$$k!- \sum_{p=0}^{q-1} (-1)^p {k\choose p} (q-p)^k.$$
Using an Iverson bracket we get for the sum component
$$[w^{q-1}] \frac{1}{1-w}
\sum_{p\ge 0} (-1)^p {k\choose p} (q-p)^k w^p
\\ = k! [z^k] [w^{q-1}] \frac{1}{1-w}
\exp(qz) (1-w\exp(-z))^k
\\ = k! \;\underset{z}{\mathrm{res}}\; \frac{1}{z^{k+1}}
\;\underset{w}{\mathrm{res}}\; \frac{1}{w^q} \frac{1}{1-w} \exp(qz)
(1-w\exp(-z))^k.$$
We now apply Jacobi's Residue Formula.  We put $w=v \exp((1-v)u)$ and $z
= (1-v)u$. The scalar to obtain a non-zero constant term in $u$ and $v$
for $z$ and $w$  is $u$ for $z$ and $v$ for $w.$
Using the determinant of the Jacobian we obtain
$$ \begin{vmatrix} 1 & 0 \\ 0 & 1 \end{vmatrix}^{-1}
\begin{vmatrix}
1-v & -u \\
v (1-v) \exp((1-v)u) & \exp((1-v)u) - u v \exp((1-v)u) \\
\end{vmatrix}
\\ = \exp((1-v)u)
\begin{vmatrix}
1-v & - u \\
v (1-v) & 1 - uv \\
\end{vmatrix}
\\ = \exp((1-v)u) (1 - uv - v + uv^2 + uv - uv^2)
\\ = \exp((1-v)u) (1 - v).$$
Doing the substitution we find
$$k! \;\underset{u}{\mathrm{res}}\;
\frac{1}{u^{k+1}} \frac{1}{(1-v)^{k+1}}
\;\underset{v}{\mathrm{res}}\; \frac{1}{v^q} \frac{1}{\exp(q(1-v)u)}
\\ \times \frac{1}{1-v\exp((1-v)u)} \exp(q(1-v)u)
(1-v\exp((1-v)u)\exp(-(1-v)u))^k
\\ \times \exp((1-v)u) (1-v)
\\ = k! \;\underset{u}{\mathrm{res}}\;
\frac{1}{u^{k+1}} \frac{1}{(1-v)^{k+1}}
\;\underset{v}{\mathrm{res}}\; \frac{1}{v^q}
\frac{1}{1-v\exp((1-v)u)} (1-v)^k
\\ \times \exp((1-v)u) (1-v)
\\ = k! \;\underset{u}{\mathrm{res}}\; \frac{1}{u^{k+1}}
\;\underset{v}{\mathrm{res}}\; \frac{1}{v^q}
\frac{1}{1-v\exp((1-v)u)} \exp((1-v)u)
\\ = k! \;\underset{u}{\mathrm{res}}\; \frac{1}{u^{k+1}}
\;\underset{v}{\mathrm{res}}\; \frac{1}{v^q}
\frac{1}{\exp((v-1)u)-v}.$$
Consider on the other hand the quantity
$$\sum_{p=0}^{q-1} \left\langle k \atop p \right\rangle.$$
This is
$$k! [z^k] \sum_{p=0}^{q-1} [w^p] \frac{1-w}{\exp((w-1)z)-w}
\\ = k! [z^k] [w^{q-1}] \frac{1}{1-w} \frac{1-w}{\exp((w-1)z)-w}
\\ = k! [z^k] [w^{q-1}] \frac{1}{\exp((w-1)z)-w}
\\ = k! \;\underset{z}{\mathrm{res}}\; \frac{1}{z^{k+1}}
\;\underset{w}{\mathrm{res}}\; \frac{1}{w^q} \frac{1}{\exp((w-1)z)-w}.$$
This is the same as the sum term and we conclude the argument having
shown that
$$\sum_{p=q}^k (-1)^p {k\choose p} (q-p)^k
= k! - \sum_{p=0}^{q-1} \left\langle k \atop p \right\rangle$$
which is
$$\bbox[5px,border:2px solid #00A000]{
\sum_{p=q}^k (-1)^p {k\choose p} (q-p)^k
= \sum_{p=q}^k \left\langle k \atop p \right\rangle.}$$
Reference, as per request. The Jacobi Residue Formula is Theorem 3
in  the paper  A Combinatorial  Proof of  the Multivariable  Lagrange
Inversion Formula by I. Gessel.
A: This answer is a(nother) supplement to @MarkoRiedel's great derivation. This time we look at some details of his proof of
\begin{align*}
\color{blue}{\sum_{p=0}^{q-1} \left\langle k \atop p \right\rangle = \sum_{p=0}^{q-1} (-1)^p {k\choose p} (q-p)^k}\tag{1}
\end{align*}
which is the crucial part in his answer. The most important aspect is the usage of multidimensional residues and how to find a proper substitution for simplification. We use the classic Integral Representation and the Computation of Combinatorial Sums by G. P. Egorychev. We cite and use substitution formulas of multi-dimensional residues and obtain this way Markos derivation. I also use his  notation in order to ease comparison.


First part:
We start with the right-hand side of (1) and obtain
\begin{align*}
\color{blue}{\sum_{p=0}^{q-1}}&\color{blue}{(-1)^p \binom{k}{p}(q-p)^k}\\
&=\sum_{p=0}^\infty (-1)^p\binom{k}{p}(q-p)^k[[p\leq q-1]]\tag{2}\\
&=[w^{q-1}]\frac{1}{1-w}\sum_{p=0}^\infty(-1)^p\binom{k}{p}(q-p)^kw^p\tag{3}\\
&=[w^{q-1}]\frac{1}{1-w}\sum_{p=0}^\infty(-1)^p\binom{k}{p}k![z^k]e^{(q-p)z}w^p\tag{4}\\
&=k![z^k][w^{q-1}]\frac{e^{qz}}{1-w}\sum_{p=0}^\infty (-1)^p\binom{k}{p}\left(e^{-z}\right)^pw^p\\
&\,\,\color{blue}{=k![z^k][w^{q-1}]\frac{e^{qz}}{1-w}\left(1-\frac{w}{e^{z}}\right)^k}\tag{5}\\
\end{align*}
In (5) we have a representation with two-dimensional residues (note $[z^k]A(z)=res_{z=0}\frac{A(z)}{z^{k+1}}$) which can be considerably simplified using a proper substitution. This substitution was nicely used by Marko, but how to come to it might not be that obvious. We'll have a look at it in the Intermezzo section where we will see how to automagically derive the appropriate substitution next to the comments below.

Comments:

*

*In (2) we use the Iverson brackets in order to get rid of the upper limit $q-1$ of the sum.


*In (3) we use an equivalent to the Iverson brackets the identity
\begin{align*}
 \color{blue}{\sum_{p=0}^n a_p=\sum_{p=0}^\infty a_p[[p\leq n]]=[w^n]\frac{1}{1-w}\sum_{p=0}^\infty a_p w^p}
 \end{align*}
which is valid, since
\begin{align*}
 \color{blue}{[w^n]}&\color{blue}{\frac{1}{1-w}\sum_{p=0}^\infty a_p w^p}
=[w^n]\sum_{l=0}^\infty w^l\sum_{p=0}^\infty a_p w^p\\
&=\sum_{l=0}^n[w^{n-l}]\sum_{p=0}^\infty a_pw^p=\sum_{l=0}^n[w^{l}]\sum_{p=0}^\infty a_pw^p\\
&\,\,\color{blue}{=\sum_{l=0}^n a_l}
\end{align*}


*In (4) we use the coefficient of operator $[z^k]$ and the identity $a^k=k![z^k]e^{az}$.


*In (5) we apply the binomial theorem.
Intermezzo: Change of variables under the res sign
In order to find a substitution which simplifies (5) we use Rule 5 (change of variables under the res sign) from Egorychev's classic, which is stated as transformation formula for $n$-dimensional residues. Here we state it as two-dimensional identity which readily fits our needs. We have as special case $n=2$ of Rule 5:
\begin{align*}
&[z^{k_1}w^{k_2}]\left(A(z,w)\,\prod_{j=1}^2 f_{j}^{k_j}(z,w)\right)\\
&\ \ =[u^{k_1}v^{k_2}]
\left(\left.\left[A(z,w)\left|\frac{\partial(z,w)}{\partial{(u,v)}}\right|
\prod_{j=1}^2 f_{j}^{-1}(z,w)\right]
\right|_{(z,w)=g(u,v)}\right)\tag{6}
\end{align*}
where we use the substitution:
\begin{align*}
\color{blue}{u=u(z,w)=\frac{z}{f_1(z,w)}\qquad\qquad v=v(z,w)=\frac{w}{f_2(z,w)}}\tag{7}
\end{align*}
In (6) we have $A(z,w)$ a bivariate generating function, $f_j(z,w), j=1,2$ bivariate generating functions with constant term $\ne 0$ and $(z,w)=g(u,v)=(g_1(u,v), g_2(u,v))$ is the (unique) solution of (7).

In the current situation (5) we have
\begin{align*}
A(z,w)=\frac{e^z}{1-w}\qquad f_1^{k_1}(z,w)=\left(1-\frac{w}{e^z}\right)^k\qquad f_2^{k_2}(z,w)=\left(e^{z}\right)^{q-1}
\end{align*}
and use according to (7) the substitution
\begin{align*}
u(z,w)=\frac{z}{1-\frac{w}{e^z}}\qquad\qquad v(z,w)=\frac{w}{e^z}\tag{8}
\end{align*}
We put $v=w/e^z$ in $u(z,w)$ of (8) and obtain
\begin{align*}
u&=\frac{z}{1-v}\qquad \to\qquad \color{blue}{z=u(1-v)}\tag{9}
\end{align*}
We put $z=u(1-v)$ in $v(z,w)$ of (8) and obtain
\begin{align*}
v=\frac{w}{e^{u(1-v)}}\qquad \to\qquad \color{blue}{w=ve^{u(1-v)}}\tag{10}
\end{align*}
et voilà we have automagically found the substitution which was used in Marko's proof. :-)

Calculation of the Jacobian gives
\begin{align*}
\left|\frac{\partial(u,v)}{\partial{(z,w)}}\right|^{-1}&=\left|\frac{\partial(z,w)}{\partial{(u,v)}}\right|
=\begin{vmatrix}
\frac{\partial z}{\partial u}&\frac{\partial z}{\partial v}\\
\frac{\partial w}{\partial u}&\frac{\partial w}{\partial v}\\
\end{vmatrix}\\
&=\begin{vmatrix}
1-v&-u\\
(1-v)ve^{u(1-v)}&e^{u(1-v)}-uve^{u(1-v)}\\
\end{vmatrix}\\
&=e^{u(1-v)}\begin{vmatrix}
1-v&-u\\
(1-v)v&1-uv\\
\end{vmatrix}\\
&=(1-v)e^{u(1-v)}\tag{11}
\end{align*}

Second part:
We can now continue with the expression (7). We apply the substitution rule (6) by using the substitution (7) and obtain from (6) with (9) - (11):
\begin{align*}
\color{blue}{k![z^k]}&\color{blue}{[w^{q-1}]\frac{e^{z}}{1-w}\left(1-\frac{w}{e^{z}}\right)^ke^{(q-1)z}}\\
&=k![u^{k}][v^{q-1}]
\left\{\left[\frac{e^z}{1-w}\left|\frac{\partial(z,w)}{\partial{(u,v)}}\right|
\left.\left(1-\frac{w}{e^z}\right)^{-1}e^{-z}
\right]\right|_{(z,w)=g(u,v)}\right\}\\
&=k![u^{k}][v^{q-1}]
\left\{\frac{1}{1-ve^{u(1-v)}}\,(1-v)e^{u(1-v)}\,\frac{1}{1-v}\right\}\\
&=k![u^k][v^{q-1}]\frac{1}{e^{(v-1)u}-v}\\
&=k![u^k][v^{q-1}]\frac{1}{1-v}\frac{1-v}{e^{(v-1)u}-v}\\
&=k![u^k][v^{q-1}]\sum_{p=0}^\infty v^p\frac{1-v}{e^{(v-1)u}-v}\\
&=k![u^k]\sum_{p=0}^{q-1}[v^{q-1-p}]\frac{1-v}{e^{(v-1)u}-v}\\
&=k![u^k]\sum_{p=0}^{q-1}[v^{p}]\frac{1-v}{e^{(v-1)u}-v}\\
&\,\,\color{blue}{=\sum_{p=0}^{q-1} \left\langle k \atop p \right\rangle }
\end{align*}
and the claim follows.

A: This answer is a supplement to @MarkoRiedel's interesting derivation. We provide a somewhat different approach to derive the identity
\begin{align*}
\color{blue}{\sum_{p=0}^{q-1} \left\langle k \atop p \right\rangle = \sum_{p=0}^{q-1} (-1)^p {k\choose p} (q-p)^k}\tag{1}
\end{align*}
which is the crucial one in @MarkoRiedels answer. I also use his  notation to ease comparison.

The numbers $ \left\langle k \atop p \right\rangle$ are the Eulerian numbers as they are defined in Concrete Mathematics
, Section 6.2 by D.E. Knuth, R.L. Graham and O. Patashnik.
Double generating function: In order to show (1) we start with a double generating function $A(t,u)$ of the Eulerian numbers stated as formula [14v] in Advanced Combinatorics by L. Comtet.

We obtain according to formula [5g] in Comtet:
\begin{align*}
\color{blue}{A(t,u)}&=1+\sum_{k=1}^\infty\sum_{q=1}^k \left\langle k \atop q-1 \right\rangle \frac{t^k}{k!}u^q\tag{2}\\
&\,\,\color{blue}{=\frac{1-u}{1-ue^{t(1-u)}}}\\
&=(1-u)\sum_{p=0}^\infty u^pe^{pt(1-u)}\\
&=\sum_{p=0}^\infty u^p\sum_{l=0}^\infty \frac{p^l}{l!}t^l(1-u)^{l+1}\\
&\,\,\color{blue}{=\sum_{p=0}^\infty u^p\sum_{l=0}^\infty\frac{p^l}{l!}t^l\sum_{j=0}^{l+1}\binom{l+1}{j}(-1)^ju^j}\tag{3}
\end{align*}

Note that Comtet uses a slightly different definition of Eulerian numbers, which results in the lower index $q-1$ of $\left\langle k \atop q-1 \right\rangle$ in (2).
Coefficient comparison:

Coefficient comparison of (2) and (3) gives
\begin{align*}
\color{blue}{\left\langle k \atop q-1 \right\rangle}
&=k![t^ku^q]\sum_{p=0}^\infty u^p\sum_{l=0}^\infty \frac{p^l}{l!}t^l\sum_{j=0}^{l+1}\binom{l+1}{j}(-1)^ju^j\\
&=[u^q]\sum_{p=0}^\infty u^p p^k\sum_{j=0}^{k+1}\binom{k+1}{j}(-1)^ju^j\tag{4}\\
&=\sum_{p=0}^q[u^{q-p}]p^k\sum_{j=0}^{k+1}\binom{k+1}{j}(-1)^ju^j\tag{5}\\
&=\sum_{p=0}^q[u^{p}](q-p)^k\sum_{j=0}^{k+1}\binom{k+1}{j}(-1)^ju^j\tag{6}\\
&\,\,\color{blue}{=\sum_{p=0}^{q-1}(q-p)^k\binom{k+1}{p}(-1)^p}\tag{7}
\end{align*}

Comment:

*

*In (4) we select the coefficient of $t^k$.


*In (5) we use the rule $[u^{p-q}]A(u)=[u^p]u^qA(u)$. We also set the upper index of the outer sum to $q$, since other terms do not contribute.


*In (6) we change the order of summation: $p\to q-p$.


*In (7) we select the coefficient of $u^p$.
The identity (7) is stated in Concrete Mathematics as formula (6.38). The sum in (7) is pretty close to the wanted sum (1) besides the upper index $k+1$ which should be $k$. In order to derive (1) we do some
Telescoping:
We obtain from (7)
\begin{align*}
\left\langle k \atop q-1 \right\rangle&=\sum_{p=0}^{q-1}(q-p)^k\binom{k+1}{p}(-1)^p\\
&=\sum_{p=0}^{q-1}(q-p)^k\binom{k}{p}(-1)^p+\sum_{p=1}^{q-1}(q-p)^k\binom{k}{p-1}(-1)^p\\
&=\underbrace{\sum_{p=0}^{q-1}(q-p)^k\binom{k}{p}(-1)^p}_{a_{k,q}}-\sum_{p=0}^{q-2}(q-1-p)^k\binom{k}{p}(-1)^p\\
&=a_{k,q}-a_{k,q-1}\\
\end{align*}
It follows via telescoping
\begin{align*}
\sum_{p=1}^{q-1}\left\langle k \atop p \right\rangle
&=\sum_{p=1}^{q-1}\left(a_{k,p+1}-a_{k,p}\right)\\
&=\sum_{p=2}^{q}a_{k,p}-\sum_{p=1}^{q-1}a_{k,p}\\
&=a_{k,q}-a_{k,1}\\
\end{align*}
and since
\begin{align*}
a_{k,1}=\sum_{p=0}^0(1-p)^k\binom{k}{p}(-1)^p=1=\left\langle k \atop 0 \right\rangle
\end{align*}
we derive
\begin{align*}
\color{blue}{\sum_{p=0}^{q-1}\left\langle k \atop p \right\rangle} = a_{k,q} 
\color{blue}{= \sum_{p=0}^{q-1}(q-p)^k\binom{k}{p}(-1)^p}
\end{align*}
and the claim (1) follows.
