# 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!

-

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.

-

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}.$$

-