Stirling Number of the Second Kind Identity I'm aware of the identity
\begin{align}
\sum_{i = 0}^{k} i! \binom{n+1}{i + 1} S(k,i) = H_{n,-k},
\end{align}
where $H_{n,-k}$ is a generalized Harmonic number defined by $H_{n,m} = \sum_{r = 1}^{n} r^{-m}$. I believe the following sum is related to the generalized Harmonic numbers as well,
\begin{align}
\sum_{i = 0}^{k} (-1)^{i} i! \binom{n-i}{k-i} S(j,i)
\end{align}
and should be a nice function of $n, k$ and $j$, where $0 \leq j, k \leq n$. Any hints are certainly welcome!
 A: I'm not sure that you're going to be able to get a nice expression in general (although I would be happy to be proved wrong!).
The special case $j = n$ has a very simple expression in terms of the Eulerian numbers, though.  We have
$$\sum_{i=0}^k (-1)^i i! \binom{n-i}{k-i} \left\{ n \atop i\right\} = \sum_{i=0}^k (-1)^i i! \binom{n-i}{n-k} \left\{ n \atop i\right\} = (-1)^k \left\langle n \atop n-k\right\rangle,$$
where the first step follows from $\binom{n}{k} = \binom{n}{n-k}$ and the second step from a known expression for the Eulerian numbers (see Eq. 6.40, Concrete Mathematics, 2nd edition, p. 269).  The Eulerian number $\left\langle n \atop k\right\rangle$ counts the number of permutations on $n$ elements in which exactly $k$ are larger than the immediately preceding element.
Maybe the case $j = 2$ is of interest as well.  Here we have $$\sum_{i=0}^k (-1)^i i! \binom{n-i}{k-i} \left\{ 2 \atop i\right\} = 2\binom{n-2}{k-2} -\binom{n-1}{k-1} = 2\binom{n-2}{k-2} -\left[\binom{n-2}{k-1} + \binom{n-2}{k-2}\right] $$
$$= \binom{n-2}{k-2} -\binom{n-2}{k-1},$$
which is the just the triangle you get when you take differences of neighboring entries in Pascal's triangle.  This triangle can also be thought of as two copies of Catalan's triangle, one positive and one negative, although the numbers are shifted and rotated.
A: By way  of enrichment  of this discussion  we give a  purely algebraic
proof that does not use Eulerian numbers.
Suppose we seek to prove that
$$\sum_{q=0}^n q! {m+1\choose q+1} {n\brace q} = H_{m,-n}$$
with $m\ge n.$
Recall  the bivariate generating  function $G(z,  u)$ of  the Stirling
numbers of the second kind which is
$$G(z, u) = \exp(u(\exp(z)-1)).$$
This yields for the sum that
$$\sum_{q=0}^n q! {m+1\choose q+1} n! [z^n] [u^q] \exp(u(\exp(z)-1))
\\= n! [z^n] \sum_{q=0}^n q! {m+1\choose q+1} \frac{(\exp(z)-1)^q}{q!}
= n! [z^n] \sum_{q=0}^n {m+1\choose q+1} (\exp(z)-1)^q.$$
An important observation at this point is that $\exp(z)-1$ starts at
$z$, so  we may  extend the summation  to $m$ without  affecting the
coefficient of $z^n,$ getting
$$n! [z^n] \sum_{q=0}^m {m+1\choose q+1} (\exp(z)-1)^q.$$
Rewrite this as
$$(m+1) \times n! [z^n] 
\sum_{q=0}^m {m\choose q} \frac{(\exp(z)-1)^q}{q+1}
\\= (m+1) \times n! [z^n] \frac{1}{\exp(z)-1}
\sum_{q=0}^m {m\choose q} \frac{(\exp(z)-1)^{q+1}}{q+1}.$$
Stop for a moment to perform a formal power series integration.
We have $$(1+x)^m = \sum_{q=0}^m {m\choose q} x^q$$
so that
$$\frac{1}{m+1}(1+x)^{m+1} - \frac{1}{m+1}
=\frac{1}{m+1}\left((1+x)^{m+1} - 1\right)
\\= \sum_{q=0}^m {m\choose q} \frac{x^{q+1}}{q+1}.$$
Apply this to the sum to obtain
$$(m+1) \times n! [z^n] \frac{1}{\exp(z)-1}
\frac{1}{m+1}\left(\exp(z(m+1)) - 1\right)$$
which is
$$n! [z^n] \frac{\exp(z(m+1)) - 1}{\exp(z)-1}
= n! [z^n] \sum_{k=0}^m \exp(zk)
\\= n! \sum_{k=0}^m \frac{k^n}{n!} = \sum_{k=0}^m k^n = H_{m, -n}.$$
