Recently, some of the remarkable properties of second-order
Eulerian numbers $ \left\langle\!\!\left\langle n\atop k\right\rangle\!\!\right\rangle$ A340556 have been proved on MSE [ a ,
b , c ].
But there are also other notable identities to which these numbers lead.
For instance, we also noticed the following identity, which we haven't seen
elsewhere (reference?):
$$ \sum_{j=0}^{k} \binom{n-j}{n-k}
\left\langle\!\! \left\langle n\atop j\right\rangle\!\! \right\rangle \,=\,
\sum_{j=0}^k (-1)^{j+k} \binom{n+k}{n+j} \left\{ n+j \atop j\right \} \quad ( n \ge 0) $$
If we use the notation $ \operatorname{W}_{n, k} $ for these numbers,
we can also introduce the corresponding polynomials.
$$ \operatorname{W}_{n}(x) = \sum_{k=0}^n \operatorname{W}_{n, k} x^k \quad ( n \ge 0) $$
So far so routine, but then came the surprise:
$$ 3^n W_n\left(-\frac13\right) \, = \, 2^n \left\langle\!\!\left\langle – \frac{1}{2} \right\rangle\!\!\right\rangle_n \quad ( n \ge 0) $$
On the right side are the numbers we recently asked about their
combinatorial significance!
Should I trust this strange equation?
Best Answer
In trying to verify the identity
$$\sum_{j=0}^{k} {n-j \choose n-k} \left\langle\!\! \left\langle n\atop j \right\rangle\!\! \right\rangle = \sum_{j=0}^k (-1)^{j+k} {n+k \choose n+j} \left\{ n+j \atop j\right \}$$
we quote from MSE the following identity
$$\left\langle\!\! \left\langle n\atop k \right\rangle\!\! \right\rangle = \sum_{j=0}^k (-1)^{k-j} {2n+1\choose k-j} {n+j\brace j}.$$
We get for the LHS
$$\sum_{j=0}^{k} {n-j \choose n-k} \sum_{p=0}^j (-1)^{j-p} {2n+1\choose j-p} {n+p\brace p} \\ = \sum_{p=0}^k {n+p\brace p} \sum_{j=p}^k (-1)^{j-p} {2n+1\choose j-p} {n-j\choose n-k}.$$
The inner sum is $$\sum_{j=0}^{k-p} (-1)^j {2n+1\choose j} {n-j-p\choose n-k} \\ = \sum_{j=0}^{k-p} (-1)^j {2n+1\choose j} {n-j-p\choose k-p-j} \\ = [z^{k-p}] (1+z)^{n-p} \sum_{j=0}^{k-p} (-1)^j {2n+1\choose j} \frac{z^j}{(1+z)^j}.$$
Here the coefficient extractor enforces the upper limit of the sum and we may extend $j$ to infinity:
$$[z^{k-p}] (1+z)^{n-p} \sum_{j\ge 0} (-1)^j {2n+1\choose j} \frac{z^j}{(1+z)^j} \\ = [z^{k-p}] (1+z)^{n-p} \left(1-\frac{z}{1+z}\right)^{2n+1} = [z^{k-p}] \frac{1}{(1+z)^{n+p+1}} \\ = (-1)^{k-p} {k-p+n+p\choose n+p} = (-1)^{k-p} {n+k\choose n+p}.$$
Introducing the leading term,
$$\sum_{p=0}^k (-1)^{k+p} {n+k\choose n+p} {n+p\brace p}$$
This is the claim.
As for the polynomials we find$$\sum_{k=0}^n x^k \sum_{j=0}^{k} {n-j \choose n-k} \left\langle\!\! \left\langle n\atop j \right\rangle\!\! \right\rangle = \sum_{j=0}^n \left\langle\!\! \left\langle n\atop j \right\rangle\!\! \right\rangle \sum_{k=j}^n {n-j\choose n-k} x^k \\ = \sum_{j=0}^n \left\langle\!\! \left\langle n\atop j \right\rangle\!\! \right\rangle x^j \sum_{k=0}^{n-j} {n-j\choose n-j-k} x^k = \sum_{j=0}^n \left\langle\!\! \left\langle n\atop j \right\rangle\!\! \right\rangle x^j \sum_{k=0}^{n-j} {n-j\choose k} x^k \\ = \sum_{j=0}^n \left\langle\!\! \left\langle n\atop j \right\rangle\!\! \right\rangle x^j (1+x)^{n-j} = (1+x)^n \sum_{j=0}^n \left\langle\!\! \left\langle n\atop j \right\rangle\!\! \right\rangle \frac{x^j}{(1+x)^j}.$$
Multiplying by $3^n$ and evaluating at $x=-1/3$ we obtain
$$3^n \frac{2^n}{3^n} \sum_{j=0}^n \left\langle\!\! \left\langle n\atop j \right\rangle\!\! \right\rangle \frac{(-1/3)^j}{(2/3)^j} = 2^n \sum_{j=0}^n \left\langle\!\! \left\langle n\atop j \right\rangle\!\! \right\rangle \left(-\frac{1}{2}\right)^j$$
as claimed.
Remark. Maybe we can pause here for a few days. Thanks!