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 ]
and in d the second-order Eulerian polynomials
were introduced.
$$ \left\langle\!\left\langle x \right\rangle\!\right\rangle_n =
\sum_{k=0}^n \left\langle\!\!\left\langle n\atop k \right\rangle\!\!\right\rangle \, x^k $$
These polynomials can be computed recursively, starting $ \left\langle\!\left\langle x \right\rangle\!\right\rangle_{0} \, = \, 1 $, and then proceeding
$$ \left\langle \! \left\langle x \right\rangle \! \right\rangle _n =
x\,(x-1)^{2n}\
\left(\frac{ \left\langle \! \left\langle x \right\rangle \! \right\rangle _{n-1}}{(1-x)^{2n-1}} \right)'
\quad (n \ge 1). $$
With this formula the polynomials can not only be calculated efficiently but also
may simplify the derivation of combinatorial identities.
For instance from Marko Riedel's thorough proof
we know the following identity for Euler's tree function
$\operatorname{T}(z) = – \operatorname{W}(-z)$, where $\operatorname{W}$
is the principal branch of Lambert's function A000169:
$$ m^{m+n} \, = \,
m!\, [x]^{m} \frac{\left\langle \! \left\langle \, \operatorname{T}(x) \, \right\rangle \! \right\rangle _n} {(1-\operatorname{T}(x))^{2n+1}} \quad ( n \ge 0) $$
The reader may enjoy to investigate what happens if we evaluate the function
at $ x = (2 \sqrt{e})^{-1}$, (A225170, A006351).
Is someone willing to show us a proof of the recurrence of the second-order Eulerian polynomials
given above?
Best Answer
This is the same as in the Tree function Eulerian identity. Observe that
$$x (1-x)^{2n} \left(\frac{1}{(1-x)^{2n-1}} \sum_{k=0}^{n-1} \left\langle\!\! \left\langle n-1 \atop k \right\rangle\!\! \right\rangle x^k\right)'.$$
gives with $n\ge 2$ for $\left\langle\! \left\langle x \right\rangle\! \right\rangle_n$
$$x(1-x)^{2n} \frac{2n-1}{(1-x)^{2n}} \sum_{k=0}^{n-1} \left\langle\!\! \left\langle n-1 \atop k \right\rangle\!\! \right\rangle x^k +x(1-x)^{2n} \frac{1}{(1-x)^{2n-1}} \sum_{k=1}^{n-1} \left\langle\!\! \left\langle n-1 \atop k \right\rangle\!\! \right\rangle k x^{k-1} \\ = \sum_{k=0}^{n-1} \left\langle\!\! \left\langle n-1 \atop k \right\rangle\!\! \right\rangle (2n-1) x^{k+1} + \sum_{k=1}^{n-1} \left\langle\!\! \left\langle n-1 \atop k \right\rangle\!\! \right\rangle k x^k - \sum_{k=1}^{n-1} \left\langle\!\! \left\langle n-1 \atop k \right\rangle\!\! \right\rangle k x^{k+1} \\ = \sum_{k=1}^{n} \left\langle\!\! \left\langle n-1 \atop k-1 \right\rangle\!\! \right\rangle (2n-1) x^{k} + \sum_{k=1}^{n-1} \left\langle\!\! \left\langle n-1 \atop k \right\rangle\!\! \right\rangle k x^k - \sum_{k=2}^{n} \left\langle\!\! \left\langle n-1 \atop k-1 \right\rangle\!\! \right\rangle (k-1) x^{k}.$$
We may lower $k$ to zero in all three terms (zero contribution) and raise it to $n$ in the second term (also a zero contribution). We find
$$\sum_{k=0}^n \left(\left\langle\!\! \left\langle n-1 \atop k-1 \right\rangle\!\! \right\rangle (2n-k) + \left\langle\!\! \left\langle n-1 \atop k \right\rangle\!\! \right\rangle k \right) x^k.$$
Now apply the recurrence for the Eulerian numbers to get
$$\sum_{k=0}^n \left\langle\!\! \left\langle n \atop k \right\rangle\!\! \right\rangle x^k$$
as desired. Note that the case $n=1$ for the initial recursion goes through by inspection with $\left\langle\! \left\langle x \right\rangle\! \right\rangle_0 = 1.$