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.


1 Answer 1


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .