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 ].
A special property unfolds when these numbers are interpreted as coefficients of polynomials:
$$ \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 $$
If we evaluate these polynomials at the point $ x = 1/2 $, we get
a sequence whose exponential generating function is based on
the amazing Lambert W function.
$$ 2^n \left\langle\!\!\left\langle \frac{1}{2} \right\rangle\!\!\right\rangle_n
= n! \, [x^n]\, ({2 + 2\operatorname{W}(- \exp((x-1)\,/\,2)\,/\,2))^{-1}} $$
Not only that: the sequence represents the solution of a
famous combinatorial problem, Schröder's fourth problem
(see A000311)!
It would be great if someone could show us a proof of this formula.
Best Answer
We seek to show that the following identity holds:
$$2^{n+1} \sum_{k=0}^n \left\langle\!\! \left\langle n \atop k \right\rangle\!\! \right\rangle \frac{1}{2^k} = n! [x^n] \frac{1}{1 + W(-\exp((x-1)/2)/2)}.$$
We will be using data from Wikipedia on Lambert W and work with the combinatorial branch which is $W_0(z)$.
Recall that
$$W'(z) \frac{z}{W(z)} = \frac{1}{1+W(z)}.$$
We obtain
$$[z^m] \frac{1}{1+W(z)} = \frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{1}{z^{m}} \frac{1}{W(z)} W'(z) \; dz.$$
Putting $W(z) = v$ we find
$$\frac{1}{2\pi i} \int_{|v|=\gamma} \frac{1}{v^{m} \exp(mv)} \frac{1}{v} \; dv = \frac{1}{2\pi i} \int_{|v|=\gamma} \frac{1}{v^{m+1}} \exp(-mv) \; dv = \frac{(-1)^m m^m}{m!}.$$
so that
$$\frac{1}{1+W(z)} = \sum_{m\ge 0} (-1)^m m^m \frac{z^m}{m!}.$$
We get for the original RHS
$$n! [x^n] \sum_{m\ge 0} \frac{m^m}{m!} \exp(m(x-1)/2) \frac{1}{2^m} \\ = n! [x^n] \sum_{m\ge 0} \frac{m^m}{m!} \frac{\exp(-m/2)}{2^m} \exp(mx/2) \\ = \sum_{m\ge 0} \frac{m^{m+n}}{m!} \frac{\exp(-m/2)}{2^{m+n}}.$$
First part. Introduce the tree function $T(z)$ from combinatorics where $T(z) = z \exp T(z)$ and $T(z) = - W_0(-z).$ Note that we have by Cayley's theorem that $T(z) = \sum_{m\ge 1} m^{m-1} \frac{z^m}{m!}.$ We claim that with $n\ge 1$
$$Q_n(z) = \sum_{m\ge 0} m^{m+n} \frac{z^m}{m!} = \frac{1}{(1-T(z))^{2n+1}} \sum_{k=1}^n \left\langle\!\! \left\langle n \atop k \right\rangle\!\! \right\rangle T(z)^k.$$
This means the RHS is $\frac{1}{2^n} Q_n(\exp(-1/2)/2).$ To verify this last identity note that $Q_{n+1}(z) = z \frac{d}{dz} Q_n(z)$ so we may prove it by induction.
We get for the RHS of the series identity on differentiating and multiplying by $z$
$$\frac{(2n+1) z T'(z)}{(1-T(z))^{2n+2}} \sum_{k=1}^n \left\langle\!\! \left\langle n \atop k \right\rangle\!\! \right\rangle T(z)^k + \frac{z}{(1-T(z))^{2n+1}} \sum_{k=1}^n \left\langle\!\! \left\langle n \atop k \right\rangle\!\! \right\rangle k T(z)^{k-1} T'(z)$$
Extracting the term $z T'(z)/(1-T(z))^{2n+2}$ in front leaves us with
$$(2n+1) \sum_{k=1}^n \left\langle\!\! \left\langle n \atop k \right\rangle\!\! \right\rangle T(z)^k + (1-T(z)) \sum_{k=1}^n \left\langle\!\! \left\langle n \atop k \right\rangle\!\! \right\rangle k T(z)^{k-1} \\ = (2n+1) \sum_{k=1}^n \left\langle\!\! \left\langle n \atop k \right\rangle\!\! \right\rangle T(z)^k + \sum_{k=0}^{n-1} \left\langle\!\! \left\langle n \atop k+1 \right\rangle\!\! \right\rangle (k+1) T(z)^{k} - \sum_{k=1}^n \left\langle\!\! \left\langle n \atop k \right\rangle\!\! \right\rangle k T(z)^{k} \\ = \sum_{k=1}^n \left\langle\!\! \left\langle n \atop k \right\rangle\!\! \right\rangle (2n+2-(k+1)) T(z)^k + \sum_{k=0}^{n-1} \left\langle\!\! \left\langle n \atop k+1 \right\rangle\!\! \right\rangle (k+1) T(z)^{k}.$$
We may include $k=0$ in the first sum and $k=n$ in the second. Now the Eulerian number recurrence (second order) according to OEIS A349556 is
$$\left\langle\!\! \left\langle n \atop k \right\rangle\!\! \right\rangle = \left\langle\!\! \left\langle n-1 \atop k \right\rangle\!\! \right\rangle k + \left\langle\!\! \left\langle n-1 \atop k-1 \right\rangle\!\! \right\rangle (2n-k)$$
We have shown that
$$Q_{n+1}(z) = \frac{z T'(z)}{(1-T(z))^{2n+2}} \sum_{k=0}^n \left\langle\!\! \left\langle n+1 \atop k+1 \right\rangle\!\! \right\rangle T(z)^k \\ = \frac{z T'(z)}{T(z) (1-T(z))^{2n+2}} \sum_{k=1}^{n+1} \left\langle\!\! \left\langle n+1 \atop k \right\rangle\!\! \right\rangle T(z)^k.$$
Now we just have to verify that
$$\frac{z T'(z)}{T(z) (1-T(z))^{2n+2}} = \frac{1}{(1-T(z))^{2n+3}} \quad\text{or}\quad z T'(z) (1-T(z)) = T(z).$$
The functional equation tells us that $T'(z) = \exp T(z) + z \exp T(z) T'(z)$ so that $T'(z) (1 - T(z)) = \exp T(z) = T(z) / z$ which is just what we need. It remains to verify the base case so the induction starts properly. We seek
$$Q_1(z) = \sum_{m\ge 0} m^{m+1} \frac{z^m}{m!} = \frac{T(z)}{(1-T(z))^3}.$$
We verify this by coefficient extraction. We get
$$m! [z^m] Q_1(z) = \frac{m!}{2\pi i} \int_{|z|=\varepsilon} \frac{1}{z^{m+1}} \frac{T(z)}{(1-T(z))^3} \; dz.$$
With $T(z) = z + \cdots$ this integral will produce the correct value zero for $m=0.$ For $m\ge 1$, we put $T(z) = w$ so that $z = w \exp(-w)$ and $dz = \exp(-w) (1-w) \; dw$ and obtain
$$\frac{m!}{2\pi i} \int_{|w|=\gamma} \frac{\exp((m+1)w)}{w^{m+1}} \frac{w}{(1-w)^3} \exp(-w) (1-w) \; dw \\ = \frac{m!}{2\pi i} \int_{|w|=\gamma} \frac{\exp(mw)}{w^{m}} \frac{1}{(1-w)^2} \; dw.$$
This is
$$m! \sum_{q=0}^{m-1} \frac{m^q}{q!} (m-q) = m! \sum_{q=0}^{m-1} \frac{m^{q+1}}{q!} - m! \sum_{q=1}^{m-1} \frac{m^q}{(q-1)!} \\ = m! \sum_{q=0}^{m-1} \frac{m^{q+1}}{q!} - m! \sum_{q=0}^{m-2} \frac{m^{q+1}}{q!} = m! \frac{m^m}{(m-1)!} = m^{m+1}$$
as desired.
Sequel. Note that in the identity for $Q_n(z)$ we have by the definition of the Eulerian numbers that $\left\langle\!\! \left\langle n \atop 0 \right\rangle\!\! \right\rangle$ is zero when $n\ge 1.$ Therefore we may extend $k$ to include zero (with $n\ge 1$ for the moment) which yields
$$\bbox[5px,border:2px solid #00A000]{ Q_n(z) = \sum_{m\ge 0} m^{m+n} \frac{z^m}{m!} = \frac{1}{(1-T(z))^{2n+1}} \sum_{k=0}^n \left\langle\!\! \left\langle n \atop k \right\rangle\!\! \right\rangle T(z)^k.}$$
Now observe that this will produce $Q_0(z) = \sum_{m\ge 0} m^m \frac{z^m}{m!} = \frac{1}{1-T(z)}$ due to $\left\langle\!\! \left\langle 0 \atop 0 \right\rangle\!\! \right\rangle = 1$ which is in fact correct because unlike $Q_n(z)$ with $n\ge 1$, $Q_0(z)$ has a constant term, which is one (this is because $m^{m+n} = 0$ for $m=0$ and $n\ge 1$ and $m^{m+n} = 1$ for $m=0$ and $n=0$). Therefore $$Q_0(z) = 1 + z T'(z) = 1 + \frac{T(z)}{1-T(z)} = \frac{1}{1-T(z)}$$ as obtained from the boxed version of the main identity, which is seen to hold for all $n\ge 0.$
Conclusion. We are now ready to answer the original question. We have shown that the RHS is $\frac{1}{2^n} Q_n(\exp(-1/2)/2).$ By our formula for $Q_n(z)$ in terms of the tree function we obtain with $T(\exp(-1/2)/2) = \frac{1}{2}$ at last the closed form
$$\frac{1}{2^n} \frac{1}{(1-1/2)^{2n+1}} \sum_{k=0}^n \left\langle\!\! \left\langle n \atop k \right\rangle\!\! \right\rangle \frac{1}{2^k} = 2^{n+1} \sum_{k=0}^n \left\langle\!\! \left\langle n \atop k \right\rangle\!\! \right\rangle \frac{1}{2^k}$$
which is the LHS and hence the claim.