# Multivariate Generating Function Related to Lambert $W$ Function and Counting Trees with a Certain Property

First, define a sequence $F_0,F_1,\dots$ of functions by $$F_0(x,z) = z,$$ $$F_k(x,z)=x\exp\left(F_{k-1}(x,z)\right) \quad \text{for }k\geq1.$$ So, for example, $$F_1(x,z) = x e^z, \quad F_2(x,z)=xe^{xe^z},\dots$$ etc. Also, set $F_{-1}(x,z)=0$. Now, let $$G(x,z) = \sum_{k=0}^\infty \left(F_k(x,z) - F_{k-1}(x,x)\right).$$ That is, $$G(x,z) = z + \left(xe^z - x\right)+\left(xe^{xe^z} - xe^x\right) + \dots$$

What I would like to do is to get some information (it doesn't have to be amazingly strong information...) about the asymptotics of the coefficient of the $x^{n-j}z^j$ term in the power series for $G(x,z)$.

Question: Does anyone know whether I have any hope in extracting any information from this generating function? If so, any ideas about what I should do/try? Even a pointer to something in the literature which might help me would be great!

By the way, the function $G(x,z)$ is closely linked to the Lambert $W$ Function. In particular, (I think) it is not hard to see that $$G(x,x)=\sum_{n=1}^\infty \frac{n^{n-1} x^n}{n!}$$ and it is well known that this function is the solution to the functional equation $$G(x,x) = x\exp(G(x,x)).$$ The thing that makes this question tricky therefore seems to be the presence of the second variable, $z$.

Remark: By the way, the coefficient of $x^{n-j}z^j$ in $$F_k(x,z)-F_{k-1}(x,x)$$ counts the number $n$-vertex trees rooted at vertex $1$ of height exactly $k$ such that there are exactly $j$ vertices at distance $k$ from the root. Therefore, the coefficient of $x^{n-j}z^j$ in $G(x,z)$ is the number of $n$-vertex trees (of any height) in which there are $j$ vertices at maximum distance from vertex $1$. If anyone knows anything about the number of such trees (independently of the generating function), then that would also be useful!

• Did you take a look at "The average height of binary trees and other simple trees" by Flajolet and Odlyzko? hal.archives-ouvertes.fr/inria-00076505/document This is not exactly the same model, but might be relevant – Sergey Dovgal Jun 2 '17 at 13:38
• @SergeyDovgal Thanks. Yes, I have come across that paper. This one cambridge.org/core/services/aop-cambridge-core/content/view/… by Renyi and Szekeres is actually even more relevant (in fact, the function $F_k(x,z)$ appears in that paper; see equation (2.9)). It looks to me like their methods probably can't be directly applied here. However, I'm not completely sure... I am not an expert in analytic methods and find their paper really tough to read... also the same goes for the Flajolet and Odlyzko paper... really tough. – Jon Noel Jun 2 '17 at 22:34
• The height $H_n$ of a random rooted Cayley tree with $n$ nodes is of order $\sqrt{n}$, more precisely: the distribution of $H_n/\sqrt{n}$ converges to the Kolmogorov-Smirnov distribution as $n\longrightarrow \infty$. This is a special case of the results here epubs.siam.org/doi/10.1137/1128044. – esg Jun 3 '17 at 15:56
• Perhaps... But this doesn't seem to tell me how many vertices are at maximum distance from the root. – Jon Noel Jun 5 '17 at 22:19
• (1) True, but it shows that the order of the no. of nodes at maximal height is not higher than $\sqrt{n}$. (2) It is plausible that $\sqrt{n}$ is the correct order, since by the results of Stepanov (see epubs.siam.org/doi/10.1137/1114007) and Meir&Moon (see cms.math.ca/10.4153/CJM-1978-085-0) asymptotically each layer (stratum) at height $x\sqrt{n}$ of a rooted random tree with $n$ nodes contains of order $\sqrt{n}$ nodes, moreover asymptotically a randomly chosen node lies at a height of order $\sqrt{n}$. Question: how precise do you need this information to be made? – esg Jun 6 '17 at 18:43

Choose a labeled tree of $n$ vertices uniformly among all $n^{n-2}$ labeled trees and let $L_n$ be the number of vertices at maximal graph distance from its root (the vertex with label $1$).
Then $L_n$ converges in distribution as $n\rightarrow \infty$, i.e., there exists a probability distribution $(q_\ell)_{\ell\geq 1}$ such that $$\mathbb{P}(L_n=\ell)\longrightarrow q_\ell,\;\;\ell\ge 1$$
Kesten and Pittel proved (Corollary 2, page 8) that the conjecture is true, and that $$q_\ell=\pi_\ell e^{-\ell}$$ where $(\pi_\ell)_{\ell\geq 1}$ is the unique solution of $$\pi_\ell\geq 0,\;\;\;\;\pi_\ell=\sum_{k=1}^\infty \pi_k\,e^{-k}\frac{k^\ell}{\ell!},\;\;\;\,\sum_{\ell=1}^\infty \pi_{\ell}e^{-\ell} =1$$