Stirling Number of the Second Kind Identity

Question

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!

Answer 1

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.