# Second-order Eulerian numbers, Lambert's W function, and Schröder's fourth problem

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.

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.