A Stirling number identity representing the second-order Eulerian numbers.

Graham, Knuth, and Patashnik give in CMath a thorough introduction to the Stirling numbers. On table 250 and table 251, they compile two pages of Stirling number identities.

Of course, there are many more such identities. We give here one which is not included and which we could not find anywhere else (which means little), but Knuth would perhaps like. They can be proved with the techniques from CMath. Maybe someone enjoys showing us the proof?

As in CMath, the Stirling cycle numbers are unsigned. {n, k} and [n, k] are defined for 0 <= k <= n, and for this range the following identity holds:

$$ \sum \limits_{j\,=\,0}^{k} (-1)^{k-j}\binom{2n+1}{k-j} {n+j \brace j} = \sum \limits_{j\,=\,0}^{n-k} (-1)^j \binom{2n+1}{j} {n+m \brack m} $$

For better readability we use the shortcut $ m = n-k-j+1$.

References to the OEIS are A132393, A048993, and A340556.

We seek to show that with $0\le k\le n$ the following identity holds:

$$\sum_{j=0}^k (-1)^{k-j} {2n+1\choose k-j} {n+j\brace j} = \sum_{j=0}^{n-k} (-1)^j {2n+1\choose j} {2n-k-j+1\brack n-k-j+1}.$$

We will start with the LHS. The chapter 6.2 on Eulerian Numbers of Concrete Mathematics by Knuth et al. proposes the formula

$${n\brace m} = (-1)^{n-m+1} \frac{n!}{(m-1)!} \sigma_{n-m}(-m)$$

where $\sigma_n(x)$ is a Stirling polynomial and we have the identity

$$\left(\frac{1}{z} \log\frac{1}{1-z}\right)^x = x \sum_{n\ge 0} \sigma_n(x+n) z^n.$$

We get

$$[z^{n-m}] \left(\frac{1}{z} \log\frac{1}{1-z}\right)^x = x \sigma_{n-m}(x+n-m)$$

and hence

$$[z^{n-m}] \left(\frac{1}{z} \log\frac{1}{1-z}\right)^{-n} = -n \sigma_{n-m}(-m)$$

which implies that for $n\ge m\ge 1$

$$\bbox[5px,border:2px solid #00A000]{ {n\brace m} = (-1)^{n-m} \frac{(n-1)!}{(m-1)!} [z^{n-m}] \left(\frac{1}{z} \log\frac{1}{1-z}\right)^{-n}.}$$

This gives for the LHS

$$\sum_{j=1}^k (-1)^{k-j} {2n+1\choose k-j} (-1)^n \frac{(n+j-1)!}{(j-1)!} [z^n] \left(\frac{1}{z} \log\frac{1}{1-z}\right)^{-n-j} \\ = (-1)^{n-k+1} n! [z^n] \left(\frac{1}{z} \log\frac{1}{1-z}\right)^{-n-1} [w^{k-1}] (1+w)^{2n+1} \\ \times \sum_{j=1}^k {n+j-1\choose n} (-1)^{j-1} w^{j-1} \left(\frac{1}{z} \log\frac{1}{1-z}\right)^{-j+1}.$$

Now the coefficient extractor in $w$ enforces the upper limit of the sum and we may extend $j$ to infinity, getting

$$(-1)^{n-k+1} n! [z^n] \left(\frac{1}{z} \log\frac{1}{1-z}\right)^{-n-1} [w^{k-1}] (1+w)^{2n+1} \frac{1}{(1+w/(\frac{1}{z} \log\frac{1}{1-z}))^{n+1}} \\ = (-1)^{n-k+1} n! [z^n] [w^{k-1}] (1+w)^{2n+1} \frac{1}{(w+\frac{1}{z} \log\frac{1}{1-z})^{n+1}}.$$

Continuing,

$$ (-1)^{n-k+1} n! [z^n] [w^{n+k}] (1+w)^{2n+1} \frac{1}{(1+\frac{1}{w} \frac{1}{z} \log\frac{1}{1-z})^{n+1}} \\ = (-1)^{n-k+1} n! [z^n] [w^{n+k}] (1+w)^{2n+1} \sum_{q\ge 0} {n+q\choose n} (-1)^q \frac{1}{w^q} \left(\frac{1}{z} \log\frac{1}{1-z}\right)^q \\ = (-1)^{n-k+1} n! [z^n] \sum_{j=n+k}^{2n+1} {2n+1\choose j} {n+j-(n+k)\choose n} (-1)^{j-(n+k)} \\ \times \left(\frac{1}{z} \log\frac{1}{1-z}\right)^{j-(n+k)} \\ = (-1)^{n-k+1} n! [z^n] \sum_{j=0}^{n-k+1} {2n+1\choose j+n+k} {n+j\choose n} (-1)^{j} \left(\frac{1}{z} \log\frac{1}{1-z}\right)^{j} \\ = (-1)^{n-k+1} n! \sum_{j=0}^{n-k+1} {2n+1\choose j+n+k} {n+j\choose n} (-1)^{j} [z^{n+j}] \left(\log\frac{1}{1-z}\right)^{j} \\ = (-1)^{n-k+1} n! \sum_{j=0}^{n-k+1} {2n+1\choose j+n+k} {n+j\choose n} (-1)^{j} \\ \times \frac{j!}{(n+j)!} \times (n+j)! [z^{n+j}] \frac{1}{j!} \left(\log\frac{1}{1-z}\right)^{j} \\ = (-1)^{n-k+1} \sum_{j=0}^{n-k+1} {2n+1\choose j+n+k} (-1)^j {n+j\brack j} \\ = (-1)^{n-k+1} \sum_{j=0}^{n-k+1} {2n+1\choose 2n-j+1} (-1)^{n-k-j+1} {2n-k-j+1\brack n-k-j+1} \\ = \sum_{j=0}^{n-k+1} {2n+1\choose j} (-1)^j {2n-k-j+1\brack n-k-j+1}.$$

The Stirling number is zero for $j=n-k+1$ and we get at last

$$\sum_{j=0}^{n-k} {2n+1\choose j} (-1)^j {2n-k-j+1\brack n-k-j+1}.$$

This is the RHS and we have the claim.