3
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Sergey Dovgal Jun 2 '17 at 13:38
  • $\begingroup$ @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. $\endgroup$ – Jon Noel Jun 2 '17 at 22:34
  • $\begingroup$ 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. $\endgroup$ – esg Jun 3 '17 at 15:56
  • $\begingroup$ Perhaps... But this doesn't seem to tell me how many vertices are at maximum distance from the root. $\endgroup$ – Jon Noel Jun 5 '17 at 22:19
  • $\begingroup$ (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? $\endgroup$ – esg Jun 6 '17 at 18:43
1
$\begingroup$

The asymptotic distribution of the number of nodes at maximal height in a random tree is known.

The following was known as "Wilf's conjecture" (H. S. Wilf stated it in 1991, evidently unaware of the fact that it had been popularized among Russian combinatorialists by V. F. Kolchin earlier):

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$$

This conjecture was settled by Kesten and Pittel in 1996, see http://www.dx.doi.org/10.1002/(SICI)1098-2418(199607)8:4<243::AID-RSA1>3.0.CO;2-Y

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$$

$\endgroup$
  • $\begingroup$ Awesome, thanks for the reference! This may not answer my question 100%, but it is very useful to me :-). $\endgroup$ – Jon Noel Jul 4 '17 at 8:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.