Finite sum related to Stirling numbers I am wondering if there is a closed form solution for the following sum:
$$
\sum _{k =0}^{n-1} \frac{(-1)^{k} (n-k)^{n+1} }{(k+1)(k+2)}\binom{n}{k}.
$$
If the the factors $(k+1)(k+2)$ in the denominator weren't there, the sum would equal $n!S(n+1,n)$, where $S(n,m)$ denotes a Stirling number of the second kind. This made me wonder if 'Stirling polynomials' of the form
$$
\mathcal{S}(x)=\sum _{k =0}^{n-1} (n-k)^{n+1}\binom{n}{k}x^k
$$
admit a closed form solution. The value of my sum could then be obtained by integrating $\mathcal{S}$ twice.
Any other strategy to evaluate the sum are also very welcome.
 A: Re-write your sum as follows:
$$\sum_{k=0}^n {n\choose k} \frac{(-1)^k}{(k+1)(k+2)} (n-k)^{n+1}.$$
Observe that when we multiply two exponential generating functions of the sequences $\{a_n\}$ and $\{b_n\}$ we get that
$$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!}
= \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\
= \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!}
= \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$
i.e. the product of the two generating functions is the generating function of
$$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$
Now in the present case we clearly have
$$A(z) = \sum_{q\ge 0} \frac{(-1)^q}{(q+1)(q+2)} \frac{z^q}{q!} =
\frac{1}{z^2} \sum_{q\ge 0} (-1)^{q+2} \frac{z^{q+2}}{(q+2)!} 
= \frac{1}{z^2} \left(\exp(-z) - 1 + z \right).$$
Furthermore we also have
$$B(z) = \sum_{q\ge 0} q^{n+1} \frac{z^q}{q!}
= \exp(z) \sum_{k=1}^{n+1} {n+1\brace k} z^k.$$
It follows that the sum is given by
$$n![z^n] A(z) B(z)
=n! [z^n] \frac{1}{z^2} \left(1 - \exp(z) + z\exp(z)\right) 
\sum_{k=1}^{n+1} {n+1\brace k} z^k$$
This becomes
$$n! [z^{n+2}]
\left(\sum_{k=1}^{n+1} {n+1\brace k} z^k
- \exp(z) \sum_{k=1}^{n+1} {n+1\brace k} z^k
+ z\exp(z) \sum_{k=1}^{n+1} {n+1\brace k} z^k\right)$$
which is
$$n! 
\left(
- \sum_{k=1}^{n+1} {n+1\brace k} \frac{1}{(n+2-k)!}
+ \sum_{k=1}^{n+1} {n+1\brace k} \frac{1}{(n+1-k)!} \right)$$
which further simplifies to
$$n!  \sum_{k=1}^{n+1} {n+1\brace k} \frac{n+1-k}{(n+2-k)!}.$$
The proof for the closed form of $B(z)$ is by induction and quite simple, I posted it at this MSE link.
A: We can get a better closed form using a different technique.
Suppose we seek to evaluate
$$\sum_{k=0}^{n-1} \frac{(-1)^k(n-k)^{n+1}}{(k+1)(k+2)}
{n\choose k}.$$
This is
$$\frac{1}{(n+2)(n+1)}
\sum_{k=0}^{n-1} (-1)^k (n-k)^{n+1}
{n+2\choose k+2}
\\ = \frac{1}{(n+2)(n+1)}
\sum_{k=0}^{n-1} (-1)^{k+2} (n+2-(k+2))^{n+1}
{n+2\choose k+2}
\\ = \frac{1}{(n+2)(n+1)}
\sum_{k=2}^{n+1} (-1)^{k} (n+2-k)^{n+1}
{n+2\choose k}
\\ = -\frac{(n+2)^n}{n+1}
+ (n+1)^n +
\frac{1}{(n+2)(n+1)}
\sum_{k=0}^{n+2} (-1)^{k} (n+2-k)^{n+1}
{n+2\choose k}.$$
Restrict to the sum for a moment and introduce
$$(n+2-k)^{n+1}
= \frac{(n+1)!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+2}} \exp((n+2-k)z) \; dz.$$
Observe that this is zero when $k=n+2$ which is the correct value.
We get for the sum
$$\frac{n!}{(n+2)\times 2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+2}} \exp((n+2)z) 
\sum_{k=0}^{n+2} (-1)^{k}
{n+2\choose k} \exp(-kz) \; dz
\\ = \frac{n!}{(n+2)\times 2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+2}} \exp((n+2)z)
(1-\exp(-z))^{n+2} \; dz
\\ = \frac{n!}{(n+2)\times 2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+2}} 
(\exp(z)-1)^{n+2} \; dz$$
This is
$$\frac{n!}{(n+2)} [z^{n+1}] (\exp(z)-1)^{n+2} = 0$$
because $\exp(z)-1 = z +\frac{1}{2} z^2 + \frac{1}{6} z^3+\cdots.$
We conclude that the initial sum is equal to
$$-\frac{(n+2)^n}{n+1} + (n+1)^n.$$
