An associated Stirling number identity related to the second-order Eulerian numbers.

A similar Stirling number identity representing the second-order Eulerian numbers can be found at this question.

We denote the associated Stirling cycle numbers as $\left[\!\left[ n\atop k\right] \! \right] $ A008306, A106828 and the associated Stirling set numbers as $\left\{\!\! \left\{ n\atop k\right\} \!\! \right\} $ A008299, A137375. Second-order Eulerian numbers as we use them are defined in A340556. They differ slightly from the second-order Eulerian numbers as defined by Graham, Knuth, and Patashnik in CMath.

In the range $0 \le k \le n$ the following identity holds:

$$ \sum_{j=0}^{k} (-1)^{k-j} \binom{n-j}{k-j} \left\{ \!\! \left\{ n+j\atop j\right\} \!\! \right\} = \sum_{j=0}^{n-k+1} (-1)^{n-k-j+1} \binom{n-j}{k-1} \left[\! \left[ n+j\atop j\right] \! \right] $$

Maybe someone enjoys showing us the proof?

Solution 1:

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

$$ \sum_{j=0}^{k} (-1)^{k-j} {n-j \choose k-j} \left\{ \!\! \left\{ n+j\atop j\right\} \!\! \right\} = \sum_{j=0}^{n-k+1} (-1)^{n-k-j+1} {n-j\choose k-1} \left[\! \left[ n+j\atop j\right] \! \right] $$

where we have associated Stirling numbers of the first and second kind.

Now from the combinatorial meaning of these numbers (cancel fixed points resp. singleton sets) we have that

$$\left[\! \left[ n\atop k\right] \! \right] = \sum_{q=0}^k (-1)^q {n\choose q} {n-q\brack k-q}$$

and

$$\left\{ \!\! \left\{ n\atop k\right\} \!\! \right\} = \sum_{q=0}^k (-1)^q {n\choose q} {n-q\brace k-q}.$$

Consult OEIS A008306 and OEIS A008299 for more information. We will only use the second of these but we show the pair to illustrate the similarity in their construction (PIE). The combinatorial classes for these are $\def\textsc#1{\dosc#1\csod}\def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}(\mathcal{U}\times\textsc{CYC}_{\ge 2}(\mathcal{Z}))$ and $\textsc{SET}(\mathcal{U}\times\textsc{SET}_{\ge 2}(\mathcal{Z})).$

We start with the LHS and obtain

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

With $n\ge 1$ this is

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

Recall e.g. from Concrete Mathematics chapter 6.2. that

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

We find for the LHS

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

Now the coefficient extractor enforces the upper limit of the inner sum and we may extend $q$ to infinity, getting

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

The inner term is $$[w^{j-1}] (1+w)^{n+j} \frac{1}{(\frac{1}{z}(\log\frac{1}{1-z}-z)+1+w)^{n+1}} \\ = [w^{j-1}] (1+w)^{j-1} \frac{1}{(1+\frac{1}{1+w} \frac{1}{z}(\log\frac{1}{1-z}-z))^{n+1}}.$$

Re-expanding the series,

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

The upper limit on the inner sum results from $[z^n]$ because $\frac{1}{z} (\log\frac{1}{1-z}-z) = \frac{1}{2} z + \cdots$ and the lower one from the fact that $[w^{j-1}] (1+w)^{j-1-q} = 0$ when $1\le q\le j-1$; $q=0$ produces a constant. Continuing,

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

It remains to simplify the binomial coefficients:

$$(-1)^{n-k} \sum_{j=1}^{k} [u^k] u^j (1+u)^{n-j} \sum_{q=j}^n (-1)^{q-j} {q-1\choose q-j} \left[\! \left[ n+q\atop q\right] \! \right].$$

We see that we may raise $j$ to $n$ owing to $[u^k]$:

$$(-1)^{n-k} \sum_{j=1}^{n} [u^k] u^j (1+u)^{n-j} \sum_{q=j}^n (-1)^{q-j} {q-1\choose q-j} \left[\! \left[ n+q\atop q\right] \! \right] \\ = (-1)^{n-k} \sum_{q=1}^n \left[\! \left[ n+q\atop q\right] \! \right] [u^k] (1+u)^n \sum_{j=1}^q {q-1\choose q-j} (-1)^{q-j} u^j (1+u)^{-j}.$$

The inner term is $$[u^k] (1+u)^n \frac{u^q}{(1+u)^q} \sum_{j=0}^{q-1} {q-1\choose j} (-1)^{j} \frac{(1+u)^j}{u^j} \\ = [u^k] (1+u)^{n-q} u^q \left(1-\frac{1+u}{u}\right)^{q-1} \\ = [u^k] (1+u)^{n-q} u (-1)^{q-1} = (-1)^{q-1} [u^{k-1}] (1+u)^{n-q}.$$

This yields

$$\sum_{q=0}^{n-k+1} (-1)^{n-k-q+1} {n-q\choose k-1} \left[\! \left[ n+q\atop q\right] \! \right]$$

which is the claim. (Here we must have $n-q\ge k-1$ or $n-k+1\ge q$ else the binomial coefficient vanishes and we may lower the upper limit from $n$ to $n-k+1.$)