Double sum identity involving binomial coefficients, possibly connected to umbral calculus I would be interested in seeing an insightful proof, or really, any alternative proof of the identity
$$
\begin{aligned}
&\sum_{j=0}^h(x+1)^j\binom{h}{j}\sum_{k=0}^r\binom{r}{k}x^k(r-k+h-j)!=\sum_{j=0}^h\binom{h}{j}(r+j)!\sum_{i=0}^{j+r}\frac{x^i}{i!}.
\end{aligned}
$$
The only proof I've managed to come up with is surprisingly cumbersome. It can be seen in this answer by searching for the line, "This is the $x=-2$ case of the sum" in the section "Alternative formula of Wyman and Moser".
I ran across this identity in the course of proving the equality of the two expressions,
$$
\varphi(h; n)=\sum_{i=0}^n(-1)^i\frac{2n}{2n-i}\binom{2n-i}{i}\nu(h,h+n-i),
$$
where
$$
\nu(h,h+n)=\sum_{k=0}^h(-1)^k\binom{h}{k}(n+h-k)!,
$$
and
$$
\varphi(h;n)=\sum_{i\ge0}(-1)^i\frac{n}{n-i}\binom{n-i}{i}\sum_{j=0}^h\binom{h}{j}k_{n-2i+j},
$$
where
$$
k_r=r!\sum_{i=0}^r\frac{(-2)^i}{i!}.
$$
The former is a formula of Touchard, related to double derangements and the ménage problem, and the latter is an, empirically discovered, generalization of a formula of Wyman and Moser for the ménage problem.
My feeling that this is connected with umbral calculus is rather vague. It comes from the observation that
$$
\sum_{i\ge0}(-1)^i\frac{n}{n-i}\binom{n-i}{i}x^{n-2i}
$$
is a rescaled Chebyshev polynomial of the first kind, and that the formula for $\varphi(h;n)$ comes from the umbral-style replacement of $x^{n-2i}$ with
$\sum_{j=0}^h\binom{h}{j}k_{n-2i+j}$, while
$$
\sum_{i=0}^n(-1)^i\frac{2n}{2n-i}\binom{2n-i}{i}x^{\frac{1}{2}(2n-2i)}
$$
is a rescaled Chebyshev polynomial of the first kind of twice the index (in the variable $x^{1/2}$), with $\varphi(h;n)$ arising from the different umbral-style replacement of $x^{n-i}$ with $\nu(h,h+n-i)$. I don't know much about umbral calculus, and don't know whether there's any sort of transformation theory that would shed light on how the replacement of $x^n$ by $x_n$ has to change when polynomial identities are used (such as the identity relating Chebyshev polynomials to Chebyshev polynomials of twice the index). Any comments about umbral calculus would be a bonus, but my main question is about proof of the identity.
 A: Here we derive a more general identity:
$$ \sum_{j=0}^{m} \binom{m}{j}(x+y)^j \sum_{k=0}^{n} \binom{n}{k} x^k (m-j+n-k)!
= \sum_{j=0}^{m} \binom{m}{j} y^{m-j} (j+n)! \sum_{i=0}^{j+n} \frac{x^i}{i!}. \tag{*} $$
The proof is fairly simple and relies on the following identity:
$$ \int_{0}^{\infty} (t+x)^n e^{-t} \, \mathrm{d}t = n!\sum_{i=0}^{n} \frac{x^i}{i!}. $$
The above identity can be proved either by the mathematical induction on $n$ or using the Poisson process. Then
\begin{align*}
\text{[LHS of (*)]}
&= \sum_{j=0}^{m} \binom{m}{j}(x+y)^j \sum_{k=0}^{n} \binom{n}{k} x^k \int_{0}^{\infty} t^{m-j+n-k}e^{-t} \, \mathrm{d}t \\
&= \int_{0}^{\infty} (t+x+y)^m (t+x)^n e^{-t} \, \mathrm{d}t \\
&= \sum_{j=0}^{n} \binom{m}{j} y^{m-j} \int_{0}^{\infty} (t+x)^{j+n} e^{-t} \, \mathrm{d}t \\
&= \sum_{j=0}^{n} \binom{m}{j} y^{m-j} (j+n)! \sum_{i=0}^{j+n} \frac{x^i}{i!} \\
&= \text{[RHS of (*)]}.
\end{align*}
A: This is a partial answer. Both, LHS and RHS are polynomials in $x$ of degree $r+h$. We use the coefficient of operator $[x^t]$ to denote the coefficient of $x^t$ of a series. We show the validity of the identity for all coefficients $[x^t]$ with $0\leq t\leq r,h$. In order to do so, we transform and simplify the LHS as well as the RHS proving thereby equality.
We do the easier part first and start with the RHS.

Let $0\leq t\leq r,h$. We obtain
\begin{align*}
\color{blue}{[x^t]}&\color{blue}{\sum_{j=0}^h\binom{h}{j}(r+j)!\sum_{i=0}^{j+r}\frac{x^i}{i!}}\\
&=\frac{1}{t!}\sum_{j=0}^h\binom{h}{j}(r+j)!\tag{1}\\
&=\frac{1}{t!}\sum_{j=0}^h\frac{h!}{j!(h-j)!}(r+j)!\\
&\,\,\color{blue}{=\frac{r!h!}{t!}\sum_{j=0}^h\binom{r+j}{j}\frac{1}{(h-j)!}}\tag{2}
\end{align*}

Comment:

*

*In (1) we select the coefficient of $x^t$.

And now the somewhat more demanding LHS.

We obtain
\begin{align*}
\color{blue}{[}&\color{blue}{x^t]\sum_{j=0}^h(x+1)^j\binom{h}{j}\sum_{k=0}^r\binom{r}{k}x^k(r-k+h-j)!}\\
&=\sum_{k=0}^t\binom{r}{k}[x^{t-k}]\sum_{j=0}^h(x+1)^j\binom{h}{j}(r-k+h-j)!\tag{3}\\
&=\sum_{k=0}^t\binom{r}{t-k}[x^{k}]\sum_{j=0}^h(x+1)^j\binom{h}{j}(r-t+k+h-j)!\tag{4}\\
&=\sum_{k=0}^t\binom{r}{t-k}\sum_{j=k}^h\binom{j}{k}\binom{h}{j}(r-t+k+h-j)!\tag{5}\\
&=\sum_{k=0}^t\frac{r!}{(t-k)!(r-t+k)!}\sum_{j=k}^h\frac{j!}{k!(j-k)!}\,\frac{h!}{j!(h-j)!}(r-t+k+h-j)!\\
&=\frac{r!h!}{t!}\sum_{k=0}^t\sum_{j=k}^h\binom{t}{k}\binom{r-t+k+h-j}{h-j}\frac{1}{(j-k)!}\\
&=\frac{r!h!}{t!}\sum_{k=0}^t\sum_{j=0}^{h-k}\binom{t}{k}\binom{r-t+h-j}{h-j-k}\frac{1}{j!}\tag{6}\\
&=\frac{r!h!}{t!}\sum_{j=0}^h\sum_{k=0}^{h-j}\binom{t}{k}\binom{r-t+h-j}{h-j-k}\frac{1}{j!}\tag{7}\\
&=\frac{r!h!}{t!}\sum_{j=0}^h\left(\sum_{k=0}^{j}\binom{t}{k}\binom{r-t+j}{j-k}\right)\frac{1}{(h-j)!}\tag{8}\\
&\,\,\color{blue}{=\frac{r!h!}{t!}\sum_{j=0}^h\binom{r+j}{j}\frac{1}{(h-j)!}}\tag{9}
\end{align*}
and the claim follows.

Comment:

*

*In (3) we exchange the sums, rearrange terms and select the coefficient of $x^k$. Since we have $t\leq r$ we can set the upper index of the outer sum to $t$. Other terms do not contribute.


*In (4) we change the order of summation $k\to t-k$.


*In (5)     we select the coefficient of  $x^k$. Since $\binom{j}{k}=0$ if $j<k$, we set the lower index of the inner sum to $k$.


*In (6) we shift the index of the inner sum to start with $j=0$.


*In (7) we exchange the sums.


*In (8) we change the order of summation of the outer sum: $j\to h-j$.


*In (9) we finally apply the Chu-Vandermonde identity to the inner sum.
