# The distance to the border of a random tree

Víctor J. Maciá  Departamento de Matemáticas, Universidad Autónoma de Madrid,
Spain<EMAIL_ADDRESS>
###### Abstract.

Given a Galton-Watson process conditioned to have total progeny equal to $n$,
we study the asymptotic probability that this conditioned Galton-Watson
process has distance to the border bigger or equal than $k$, as the number of
nodes $n\rightarrow\infty$. Through this paper we answer a question posed in
[1].

A problem which is akin to this one was solved by Rényi and Szekeres for
Cayley trees, [23], de Bruijn, Knuth, and Rice for plane trees, [6], and
Flajolet, Gao, Odlyzko, and Richmond for binary trees, [9]. The distance to
the border is dual, in a certain sense, to the height. The first of these
distances is the minimum of the distances from the root to the leaves. The
second is the maximum of the distances from the root to the leaves. These are
two extreme complementary cases.

###### Key words and phrases:

Asymptotic formulae, rooted trees, distance to the leaves, distance to the
border, Galton-Watson process, iteration, Branching processes, large powers,
Lagrange’s inversion, coefficients, analytic functions, generating function,
probability generating function.

###### 2020 Mathematics Subject Classification:

05C05, 60J80, 32H50, 05A16

Research of V. Maciá was partially funded by grant MTM2017-85934-C3-2-P2 of
Ministerio de Economía y Competitividad of Spain and European Research Council
Advanced Grant 834728

##  1\. Introduction

For a rooted tree $T$ the distance to the border $\partial(T)$ is the minimum
of the distances from the root to the leaves of $T$. The height, on the other
hand, is the maximum of these distances.

In this paper, we are interested in obtaining asymptotic formulas, as the size
$n$ tends to infinity, for the probability that a random rooted tree,
conditioned to have size $n$, has distance to the border $\partial\geq k$.

More precisely, for a Galton-Watson process $T$ with offspring distribution
given by the random variable $Y$, and conditioned to have total progeny
$\\#(T)=n$, we ask for the probability that this conditioned Galton-Watson
process has distance to the border bigger or equal than $k\geq 0$:

$(\star)\quad\mathbf{P}(\partial(T)\geq k\,|\,\\#(T)=n).$

This question but for the height is a classical one that has been dealt with
by Rényi and Szekeres for Cayley trees, [23], de Bruijn, Knuth, and Rice for
plane trees, [6], and Flajolet, Gao, Odlyzko, and Richmond for binary trees,
[9].

Our interest in the distance to the border of a rooted tree comes from [1], in
that paper just the case of Cayley trees and $k=2,3$ are dealt with, and the
general question is proposed, see [1, p. 312].

The main result of this paper is Theorem 6.3. There an asymptotic formula for
the probability $(\star)$, which depends on some computable constants, is
presented.

The proof of Theorem 6.3 is based on an iteration scheme involving Lagrange’s
equation. An asymptotic formula for the coefficients of the $k$th iterate of
that scheme is the content of Theorem 4.1.

Several results in the literature are related, in a broad sense, to those
presented here. In [12] the authors calculate the asymptotic mean distance to
the border using singularity analysis. In [2], [5] and [13] the authors
calculate some parameters related with the distance to the border of a tree:
[2] gives an asymptotic formula for the probability that a randomly selected
node in a binary search tree of size $n$ its at distance to the border bigger
or equal than $k$, as the size $n$ tends to infinity. The papers [5] and [13]
study the mean distance to the border for certain classes of rooted plane
trees, as the size $n$ tends to infinity.

A wide variety of results, see, for instance, [3], [4] and [7], suggest that
there is a parallel probabilistic approach to that of Flajolet and Sedgewick,
[11]. This theory translates combinatorial results into probabilistic results,
and vice-versa. The dictionary which connects these two fields seems to be
given by the language of the Khinchin families.

###  1.1. Some notations

We denote $\mathbb{D}(0,R)\subset\mathbb{C}$ the open disk with center $z=0$
and radius $R>0$ and $\mathbb{C}$ the complex plane. $\mathbb{D}$ denotes the
unit disk in the complex plane $\mathbb{C}$.

For a power series $A(z)=\sum_{n=0}^{\infty}a_{n}z^{n}$, we denote its $n$th
coefficient by

$a_{n}=\textsc{coeff}_{[n]}(A(z))\,,\quad\mbox{for each $n\geq 0$}\,.$

For a random variable $X$ we denote $\mathbf{E}(X)$ and $\mathbf{V}(X)$ the
expectation and variance of $X$, respectively.

Given two random variables $X$ and $Y$ we write $X\stackrel{{\scriptstyle
d}}{{=}}Y$ to signify equality in distribution.

For integers $q\geq 0$ and $m\in\\{0,1,2,\dots,q-1\\}$ we denote

$\mathbb{N}_{m,q}=\\{n\in\mathbb{N}:n\equiv m,\mod q\\}.$

Given two sequences $a_{n}$ and $b_{n}$, with $b_{n}\not\equiv 0$, we write

$\displaystyle a_{n}\sim b_{n},\quad\text{ as }n\rightarrow\infty\text{ and
}n\in\mathbb{N}_{m,q},$

to mean that

$\displaystyle\lim_{\begin{subarray}{c}n\to\infty;\\\
n\in\mathbb{N}_{m,q}\end{subarray}}\frac{a_{n}}{b_{n}}=1.$

### Acknowledgements

The author would like to thank Prof. José L. Fernández for bringing this
problem to his attention and also for some enlightening discussions.

##  2\. Power series with positive coefficients

###  2.1. Khinchin families

The class $\mathcal{K}$ consists of the nonconstant power series
$f(z)=\sum_{n\geq 0}a_{n}z^{n}$ with nonnegative coefficients and positive
radius of convergence $R>0$, and such that $f(0)=a_{0}>0$.

To each power series $f$ in $\mathcal{K}$ we associate a one-parameter family
of discrete random variables $(X_{t})_{t\in[0,R)}$ taking values in
$\\{0,1,\ldots\\}$. This family of discrete random variables is called the
Khinchin family of $f$ and is given by

$\displaystyle\mathbf{P}(X_{t}=n)=\frac{a_{n}t^{n}}{f(t)},\quad\text{ for all
}n\geq 0\text{ and }t\in(0,R).$

For $t=0$, we define $X_{0}\equiv 0$. For each $t\in(0,R)$, the random
variable $X_{t}$ is not a constant.

For each $t\in[0,R)$, we denote $\mathbf{E}(X_{t})=m(t)$ and
$\mathbf{V}(X_{t})=\sigma^{2}(t)$. It turns out that

$\displaystyle m(t)=\frac{tf^{\prime}(t)}{f(t)},\quad\text{ and
}\quad\sigma^{2}(t)=tm^{\prime}(t).$

The mean function $m(t)$ is an increasing diffeomorphism from $[0,R)$ onto its
image; this follows from the fact that $\sigma^{2}(t)>0$, for all $t\in(0,R)$.

Those $f\in\mathcal{K}$ such that

(2.1) $\lim_{t\uparrow R}m(t)>1$

comprise a subclass $\mathcal{K}^{\star}$ that is quite relevant in what
follows. If $f\in\mathcal{K}^{\star}$, the unique value $\tau\in(0,R)$ such
that $m(\tau)=1$, is called the apex of $f$. This apex $\tau$ is characterized
by $\tau f^{\prime}(\tau)=f(\tau)$. Observe that the existence of apex for
$\psi$ precludes $\psi$ from being a polynomial of degree 1, and, in
particular, implies that $\psi^{\prime\prime}(\tau)>0$.

We refer to [3], [4] and [7], for a detailed exposition of the topic.

To power series $g(z)$ of the form
$g(z)=z^{N}f(z)=\sum_{n=N}^{\infty}b_{n}z^{n}$ with $f\in\mathcal{K}$ (and
radius of convergence $R$) and integer $N\geq 1$ we also associate a family of
random variables $(Y_{t})_{t\in[0,R)}$. These $Y_{t}$ are given by

$\mathbf{P}(Y_{t}=n)=\frac{b_{n}t^{n}}{g(t)}\,,\quad\mbox{for $t\in(0,R)$ and
$n\geq N$}\,,$

and $Y_{0}\equiv N$. Observe that the $Y_{t}$ take values in
$\\{N,N{+}1,\ldots\\}$. If $(X_{t})_{t\in[0,R)}$ is the Khinchin family of $f$
then

$Y_{t}\overset{d}{=}X_{t}+N\,,\quad\mbox{for any $t\in[0,R)$}\,.$

We refer to the family $(Y_{t})_{t\in[0,R)}$ as a shifted Khinchin family.

For any $f(z)=\sum_{n=0}^{\infty}a_{n}z^{n}$ in $\mathcal{K}$, we denote

$\displaystyle
Q_{f}=\gcd\\{n>0:a_{n}>0\\}=\lim_{N\rightarrow\infty}\gcd\left(\\{0<n\leq
N:a_{n}\neq 0\\}\right);$

observe that there is an auxiliary power series $h\in\mathcal{K}$ such that
$f(z)=h(z^{Q_{f}})$.

###  2.2. Meir-Moon Tauberian theorem.

The following Tauberian theorem, due to Meir-Moon, see [17], will be used
later in the proof of Theorem 4.1.

######  Theorem A (Meir-Moon).

Let $B,C$ be power series in $\mathcal{K}$ with Taylor expansions

$\displaystyle B(z)=\sum_{n=0}^{\infty}b_{n}z^{n},\quad
C(z)=\sum_{n=0}^{\infty}c_{n}z^{n},$

and let

$\displaystyle D(z)\triangleq B(z)C(z)=\sum_{n=0}^{\infty}d_{n}z^{n}.$

Assume that the coefficients of $B$ and $C$ satisfy

$\displaystyle b_{n}=O(n^{-\beta}r^{-n})\quad\text{ and }\quad c_{n}\sim
Cn^{-\alpha}r^{-n},\quad\mbox{as $n\rightarrow\infty$},$

where $C,r,\alpha$ and $\beta$ are positive constants. If $\alpha<1<\beta$ and
$B(r)\neq 0$, then

$\displaystyle d_{n}\sim B(r)c_{n},\quad\text{ as }n\rightarrow\infty.$

The Meir-Moon Theorem above is a companion of a result from Schur (and Szász),
see [22, p. 39] and also [11, Theorem VI.12, p. 434], which requires $B$ to
have radius of convergence strictly bigger than $r>0$ and also that
$\lim_{n\rightarrow\infty}c_{n}/c_{n-1}=r$.

For similar results of this kind see [15], [16] and [17].

######  Corollary A.

Let $Q\geq 1$ be a positive integer. Let $B$ and $C$ be two power series in
$\mathcal{K}$ with Taylor expansions

$\displaystyle B(z)=\sum_{j=0}^{\infty}b_{jQ}z^{jQ},\quad
C(z)=\sum_{j=0}^{\infty}c_{jQ}z^{jQ},$

and let

$\displaystyle D(z)\triangleq B(z)C(z)=\sum_{j=0}^{\infty}d_{jQ}z^{jQ}.$

Assume that the coefficients of $B$ and $C$ satisfy

$\displaystyle b_{n}=O(n^{-\beta}r^{-n})\quad\text{ and }\quad c_{n}\sim
Cn^{-\alpha}r^{-n},\quad\mbox{as $n\rightarrow\infty$ and
$n\in\mathbb{N}_{0,Q}$},$

where $C,r,\alpha$ and $\beta$ are positive constants. If $\alpha<1<\beta$ and
$B(r)\neq 0$, then

$\displaystyle d_{n}\sim B(r)c_{n},\quad\text{ as }n\rightarrow\infty\text{
and }n\in\mathbb{N}_{0,Q}$

##  3\. Lagrange’s equation

Let $\psi$ be a power series in $\mathcal{K}^{\star}$ with radius of
convergence $R_{\psi}>0$. Let $g$ the power series which is the (unique)
solution of Lagrange’s equation with data $\psi$, i.e. satisfying:

$g(z)=z\psi(g(z)).$

###  3.1. Coefficients

The coefficients of the solution power series
$g(z)=\sum_{n=0}^{\infty}A_{n}z^{n}$ are given in terms of the data $\psi$ by
Lagrange’s inversion formula:

$A_{n}=\frac{1}{n}\textsc{coeff}_{[n{-}1]}\big{(}\psi(z)^{n}\big{)},\quad\mbox{for
$n\geq 1$},$

and $A_{0}=0$.

Besides the exact formula above for the $A_{n}$ in terms of the data $\psi$,
there is the following asymptotic formula due to Otter, [19] and to Meir-Moon,
[15]. Recall that for any integer $m\in\\{0,1,2,\dots,Q_{\psi}-1\\}$ we denote
$\mathbb{N}_{m,Q_{\psi}}=\\{n\in\mathbb{N}:n\equiv m\,\textrm{
mod}\,Q_{\psi}\\}$. Using this notation:

  * •

for indices $n\notin\mathbb{N}_{1,Q_{\psi}}$, we have that $A_{n}=0$,

  * •

for indices $n\in\mathbb{N}_{1,Q_{\psi}}$, we have that

(3.1)
$A_{n}\sim\frac{Q_{\psi}}{\sqrt{2\pi}}\frac{\tau}{\sigma_{\psi}(\tau)}\frac{1}{n^{3/2}}\Big{(}\frac{\psi(\tau)}{\tau}\Big{)}^{n}\,,\quad\mbox{as
$n\to\infty$ and $n\in\mathbb{N}_{1,Q_{\psi}}$}\,.$

The radius of convergence of the power series solution $g$ is denoted $\rho$.
The asymptotic formula for the $A_{n}$ implies that $\rho=\tau/\psi(\tau)$
and, also, that $g$ extends to be continuous in the closed disk
$\\{|z|\leq\rho\\}$, since the sequence $(A_{n}\rho^{n})_{n\geq 1}$ is
summable.

###  3.2. Function $t/\psi(t)$

Lagrange’s equation gives that $g$ and $z/\psi(z)$ are inverse of each other
and thus that

$g(z/\psi(z))=z\,,\quad\mbox{for $|z|\leq\tau$}\,.$

In particular,

$g(t/\psi(t))=t\,,\quad\mbox{for $t\in[0,\tau]$}\,.$

The image of the interval $[0,\rho]$ by $g$ is the interval
$g([0,\tau/\psi(\tau)])=[0,\tau]$.

For the function $t\mapsto t/\psi(t)$, we have

######  Lemma 3.1.

For $\psi\in\mathcal{K}^{\star}$ with apex $\tau\in(0,R_{\psi})$, the function
$t/\psi(t)$

  1. (1)

is strictly increasing on the interval $[0,\tau)$

  2. (2)

is strictly decreasing on the interval $(\tau,R_{\psi})$

  3. (3)

has a maximum at $t=\tau$.

###### Proof.

The result follows from the identity

$\displaystyle\left(\frac{t}{\psi(t)}\right)^{\prime}=\frac{1}{\psi(t)}(1-m_{\psi}(t)),\quad\text{
for all }t\in[0,R_{\psi}).$

∎

###  3.3. Functions of the solution $g$ of Lagrange’s equation

For a power series $H$ with radius of convergence $R>\tau$ the coefficients of
the power series $H(g)$ are given by

(3.2)
$\displaystyle\textsc{coeff}_{[n]}\left(H(g(z))\right)=\frac{1}{n}\textsc{coeff}_{[n-1]}\left(H^{\prime}(z)\psi(z)^{n}\right),\text{
for }n\geq 1,$

and $\textsc{coeff}_{[0]}\left(H(g(z))\right)=H(0)$.

For the coefficients of functions $H(g)$ of the solution $g$ we have the
following asymptotic formula, see [15, p. 268].

######  Lemma A.

Let $\psi\in\mathcal{K}^{\star}$ with apex $\tau$ and $Q_{\psi}=1$. Let $g$ be
the solution of Lagrange’s equation with data $\psi$. Then, for any
nonconstant power series $H$, with nonnegative coefficients and having radius
of convergence $R>\tau$, the following asymptotic formula holds

$\displaystyle\textsc{coeff}_{[n]}\left[H(g(z))\right]\sim
H^{\prime}(\tau)A_{n},\quad\text{ as }n\rightarrow\infty.$

Observe that $H^{\prime}(\tau)\neq 0$, since $H$ is nonconstant.

Now we generalize Lemma A to power series $\psi\in\mathcal{K}^{\star}$ with
$Q_{\psi}\geq 1$. Before we state and prove this generalization we point out
that for $\psi\in\mathcal{K}^{\star}$ with Khinchin family $(Y_{t})$ and
$Q_{\psi}\geq 1$ we have the equality in distribution

(3.3) $\displaystyle Y_{t}\stackrel{{\scriptstyle d}}{{=}}Q_{\psi}\cdot
W_{t^{Q}},\quad\text{ for all }t\in[0,R_{\psi}),$

where $\psi(z)=\phi(z^{Q_{\psi}})$, for certain auxiliary power series
$\phi\in\mathcal{K}$ with Khinchin family $(W_{t})$.

From (3.3) it follows that

(3.4) $\displaystyle m_{\psi}(t)=Q_{\psi}\cdot m_{\phi}(t^{Q})\quad\text{ and
}\quad\sigma_{\psi}(t)=Q_{\psi}\cdot\sigma_{\phi}(t^{Q_{\psi}}),$

for all $t\in[0,R_{\psi})$.

From (3.4) it follows that

(3.5) $\displaystyle m_{\phi}(\tau^{Q_{\psi}})=1/Q_{\psi}.$

######  Lemma 3.2.

Let $\psi\in\mathcal{K}^{\star}$ with apex $\tau$ and $Q_{\psi}\geq 1$. Fix an
integer $m\in\\{0,1,\dots,Q_{\psi}\leavevmode\nobreak\ -\leavevmode\nobreak\
1\\}$. Let $g$ be the solution of Lagrange’s equation with data $\psi$.

Let $H$ be a nonconstant power series, with nonnegative coefficients and
having radius of convergence $R>\tau$. Assume that

$\displaystyle\textsc{coeff}_{[n]}[H(z)]=0,\quad\text{ if
}n\notin\mathbb{N}_{m,Q_{\psi}},$

then

$\displaystyle\textsc{coeff}_{[n]}\left[H(g(z))\right]\sim
H^{\prime}(\tau)\frac{Q_{\psi}}{\sqrt{2\pi}}\frac{\tau}{\sigma_{\psi}(\tau)}\frac{1}{n^{3/2}}\Big{(}\frac{\psi(\tau)}{\tau}\Big{)}^{n}\,,$

as $n\to\infty$ and $n\in\mathbb{N}_{m,Q_{\psi}}$.

This implies that there exists a constant $C>0$ such that

$\displaystyle\textsc{coeff}_{[n]}\left[H(g(z))\right]\leq
C\,\rho^{-n}n^{-3/2},$

as $n\rightarrow\infty$ and $n\in\mathbb{N}_{m,n}$.

###### Proof.

By hypothesis $H(z)=z^{m}\hat{H}(z^{Q_{\psi}})$. Thus

(3.6) $\displaystyle H^{\prime}(z)=z^{m-1}\tilde{H}(z^{Q_{\psi}}),\quad\text{
for all }m\in\\{1,2,\dots,Q_{\psi}-1\\},$

and $H^{\prime}(z)=z^{Q_{\psi}-1}{H}^{*}(z^{Q_{\psi}})$, for $m=0$. Here
$\hat{H}$, $\tilde{H}$ and $H^{*}$ are all power series with non-negative
coefficients. Besides we may write $\psi(z)=\phi\left(z^{Q_{\psi}}\right)$,
where $\phi$ is a power series in $\mathcal{K}$.

Formula (3.2) tell us that

$\displaystyle\textsc{coeff}_{[n]}\left[H(g(z))\right]=\frac{1}{n}\textsc{coeff}_{[n-1]}\left[H^{\prime}(z)\psi(z)^{n}\right],$

therefore, for integers $n\geq m$, using (3.6), we find that

$\displaystyle\textsc{coeff}_{[n]}\left[H(g(z))\right]=\frac{1}{n}\textsc{coeff}_{[n-m]}\left[\tilde{H}(z^{Q_{\psi}})\phi(z^{Q_{\psi}})^{n}\right],$

for all $m\in\\{1,2,\dots,Q_{\psi}-1\\}$ and also that

$\displaystyle\textsc{coeff}_{[n]}\left[H(g(z))\right]=\frac{1}{n}\textsc{coeff}_{[n-Q_{\psi}]}\left[{H}^{*}(z^{Q_{\psi}})\phi(z^{Q_{\psi}})^{n}\right],$

for $m=0$.

Fix $l\in\\{1,2,\dots,Q_{\psi}-1\\}$. For $n=l+jQ_{\psi}$ we have

(3.7)
$\displaystyle\frac{1}{n}\textsc{coeff}_{[n-l]}\left[\tilde{H}(z^{Q_{\psi}})\phi(z^{Q_{\psi}})^{n}\right]=\frac{1}{n}\textsc{coeff}_{[j]}\left[\tilde{H}(z)\phi(z)^{n}\right].$

For $l=Q_{\psi}$ and $n=l+jQ_{\psi}$ we have

(3.8)
$\displaystyle\frac{1}{n}\textsc{coeff}_{[n-l]}\left[{H}^{*}(z^{Q_{\psi}})\phi(z^{Q_{\psi}})^{n}\right]=\frac{1}{n}\textsc{coeff}_{[j]}\left[{H}^{*}(z)\phi(z)^{n}\right].$

From (3.4) and (3.5) it follows that

$\displaystyle m_{\phi}(\tau^{Q_{\psi}})=1/Q_{\psi}\quad\text{ and
}\quad\sigma_{\psi}(\tau)=Q_{\psi}\cdot\sigma_{\phi}(\tau^{Q_{\psi}}).$

Moreover $\tau^{Q_{\psi}j}=\tau^{n-m}$.

Now we apply a large powers result from Section 8 in [7] (this is the case
$j/n\rightarrow\leavevmode\nobreak\ 1/Q_{\psi},$ as $n\rightarrow\infty$) to
the right-hand side of (3.7) and (3.8). Rearranging terms in the asymptotic
formula (see Section 8 in [7]) we get that

$\displaystyle\textsc{coeff}_{[n]}\left[H(g(z))\right]\sim
H^{\prime}(\tau)\frac{Q_{\psi}}{\sqrt{2\pi}}\frac{\tau}{\sigma_{\psi}(\tau)}\frac{1}{n^{3/2}}\Big{(}\frac{\psi(\tau)}{\tau}\Big{)}^{n}\,,\quad\mbox{as
$n\to\infty$}\text{ and }n\in\mathbb{N}_{m,Q_{\psi}}\,.$

∎

######  Remark 3.3.

With the same hypothesis of Lemma 3.2 we have that

$\displaystyle\textsc{coeff}_{[n]}\left[H(g(z))\right]\sim
H^{\prime}(\tau)\rho^{-(m-1)}A_{n-m+1},\quad\text{ as
}n\rightarrow\infty\text{ and }n\in\mathbb{N}_{m,Q_{\psi}}.$

This follows combining Lemma 3.2 with formula (3.1).

From the previous asymptotic formula we obtain that there exists a constant
$C_{H,\psi}>0$ such that

$\displaystyle\textsc{coeff}_{[n]}\left[H(g(z))\right]\leq
C_{H,\psi}A_{n-m+1},\quad\text{ as }n\rightarrow\infty\text{ and
}n\in\mathbb{N}_{m,Q_{\psi}}.$

The previous relations also give that there exists a constant $C>0$ such that

$\displaystyle\textsc{coeff}_{[n]}\left[H(g(z))\right]\leq
C\rho^{-n}n^{-3/2},\quad\text{ as }n\rightarrow\infty\text{ and
}n\in\mathbb{N}_{m,Q_{\psi}}.$

$\clubsuit$

##  4\. Iteration and Lagrange’s equation

We fix now a power series $\psi(z)=\sum_{n=0}^{\infty}b_{n}z^{n}$ in
$\mathcal{K}^{\star}$ with apex $\tau$. Recall that the radius of convergence
of the solution $g$ of Lagrange’s equation with data $\psi$ is given by
$\rho=\tau/\psi(\tau)$.

For $z$ in the disk $\\{|z|\leq\rho\\}$ consider the sequence of power series
given by the recurrence

(4.1) $\displaystyle g_{n}(z)=z\psi(g_{n{-}1}(z))\,,\quad\mbox{for $n\geq
1$}\,,$

starting off with $g_{0}(z)=b_{0}z$.

This sequence is well defined. Observe that

(4.2) $\displaystyle b_{0}\,\rho=\tau/(\psi(\tau)/b_{0})<\tau<R_{\psi}\,.$

Using inequality (4.2) combined with the fact that
$\psi\in\mathcal{K}^{\star}$ we find that

$\displaystyle|g_{1}(z)|=|z\psi(b_{0}z)|<\rho\,\psi(\tau)=\tau,\quad\text{ for
all }|z|\leq\rho\,.$

By induction on $n\geq 0$ we conclude that for any integer $n\geq 0$ we have

(4.3) $\displaystyle|g_{n}(z)|<\tau,\quad\text{ for all }|z|\leq\rho\,,$

in particular, this implies that the functions in the sequence
$\\{g_{n}\\}_{n\geq 0}$ are continuous on the boundary of the disk of center
$z=0$ and radius $\rho$.

The sequence $(g_{n})_{n\geq 1}$ converges uniformly in the closure of the
disk $\mathbb{D}(0,\rho)$ to the power series $g$. See Remark 2.7 in [14, p.
9] and also [23] for more details about this iteration setting.

The iteration scheme we are interested in this paper is not the above but the
following. Start with $g_{0}(z)=g(z)$ and define recursively

(4.4) $g_{k}(z)=z\big{[}\psi(g_{k{-}1}(z))-b_{0}\big{]},\quad\mbox{for $k\geq
1$}\,.$

Write the expansion $g_{k}(z)=\sum_{n=1}^{\infty}A^{(k)}_{n}z^{n}$. It follows
that $A_{n}^{(k)}=0$ for $1\leq n\leq k$ and that

(4.5) $0\leq A_{n}^{(k)}\leq A_{n}^{(k{-}1)}\leq A_{n},\quad\mbox{for $n\geq
1$ and $k\geq 1$}.$

This means, in particular, that each power series $g_{k}$ has radius of
convergence at least $\rho$, and that the sequence of the $g_{k}$ converges to
$0$ uniformly in the closed disk $\textrm{cl}(\mathbb{D}(0,\rho))$

Define the bivariate analytic function

$\displaystyle G(z,w)=z(\psi(w)-b_{0})\,,\quad\text{ for
}|z|\leq\rho,|w|\leq\tau\,.$

The bound

(4.6) $\displaystyle|G(z,w)|\leq\tau\,,\quad\text{ for
}|z|\leq\rho,|w|\leq\tau\,,$

follows since, for $|z|\leq\rho$ and $|w|\leq\tau$, we have that

$|z||\psi(w)-b_{0}|\leq|z|\sum_{j=1}^{\infty}|b_{j}||w|^{j}\leq|z|\psi(|w|)\leq\rho\psi(\tau)=\tau\,.$

Inequality (4.6) allows us to iterate $G(z,w)$ with respect to the second
variable: for any integer $k\geq 1$ we denote

$\displaystyle G_{k}(z,w)=G(z,G_{k-1}(z,w)),\quad\text{ for all
}|z|\leq\rho\text{ and }|w|\leq\tau\,,$

the $k$-th iterate of $G(z,w)$ in the second variable, starting with
$G_{0}(z,w)=w$.

For any integer $k\geq 0$ we have that

(4.7) $\displaystyle g_{k}(z)=G_{k}(z,g(z)),\quad\text{ for }|z|\leq\rho\,.$

Observe that

(4.8) $z\frac{\partial G}{\partial z}(z,w)=G(z,w)\quad\text{ and
}\quad\frac{\partial G}{\partial w}(z,w)=z\psi^{\prime}(w),\quad\text{ for
}|z|\leq\rho\text{ and }|w|\leq\tau\,.$

The main aim of this section is to obtain the following asymptotic result
about the coefficients $A_{n}^{(k)}$:

######  Theorem 4.1.

For each $k\geq 0$,

$\lim_{\begin{subarray}{c}n\to\infty;\\\
n\in\mathbb{N}_{1,Q_{\psi}}\end{subarray}}\frac{A_{n}^{(k)}}{A_{n}}=\frac{\partial
G_{k}}{\partial w}(\rho,\tau)\,.$

The proof of Theorem 4.1 is contained in Section 4.2 and it is based on a
number of lemmas about $G(z,w)$ which are described in the next section.

######  Remark 4.2.

We can extend Theorem 4.1 in the following way: assume that
$\psi\in\mathcal{K}$ has radius of convergence $R_{\psi}<\infty$ and also that

  1. (1)

$\lim_{t\uparrow R_{\psi}}m_{\psi}(t)\triangleq M_{\psi}=1$,

  2. (2)

$\lim_{t\uparrow R_{\psi}}\psi^{\prime\prime}(t)<\infty$.

Denote $\rho=R_{\psi}/\psi(R_{\psi})$ and $\tau=R_{\psi}$, then we have

$\displaystyle\lim_{\begin{subarray}{c}n\to\infty;\\\
n\in\mathbb{N}_{1,Q_{\psi}}\end{subarray}}\frac{A_{n}^{(k)}}{A_{n}}=\frac{\partial
G_{k}}{\partial w}(\rho,\tau).$

The argument to prove this result is exactly the same than that of Theorem
4.1. The only difference appears in the proof of the auxiliary lemmas of
Subsection 4.1, these proofs now rely on some asymptotic results appearing in
[7]. These results extend the asymptotic formulas in Section 3 to the case
$M_{\psi}=1$ and $\tau=R_{\psi}$.

######  Remark 4.3.

It is possible to generalize the previous iteration scheme in the following
way: consider $\psi(z)=\sum_{n\geq 0}b_{n}z^{n}\in\mathcal{K}^{\star}$ and fix
$\mathcal{I}\subset\\{n\geq 0:b_{n}>0\\}$ a proper subset of indices such that
$0\in\mathcal{I}$. Define

(4.9) $\displaystyle
S_{\mathcal{I}}(z,w)=z(\psi(w)-\psi_{\mathcal{I}}(w))=z\psi_{\mathcal{I}^{c}}(w),\quad\text{
for all }|z|\leq\rho\text{ and }|w|\leq\tau\,,$

where $\psi_{\mathcal{I}}(z)\triangleq\sum_{n\in\mathcal{I}}b_{n}z^{n}$ and
$\mathcal{I}^{c}$ denotes the complement of $\mathcal{I}$ in the set of
indices $\\{n\geq 0:b_{n}>0\\}$.

Observe that

(4.10) $\displaystyle|S_{\mathcal{I}}(z,w)|\leq G(|z|,|w|)\leq\tau,\quad\text{
for all }|z|\leq\rho\text{ and }|w|\leq\tau\,.$

Inequality (4.10) allows us to iterate $S(z,w)$ with respect to the second
variable: for any integer $m\geq 1$ we denote

$\displaystyle
S_{\mathcal{I},m}(z,w)=S_{\mathcal{I}}(z,S_{\mathcal{I},m-1}(z,w)),\quad\text{
for all }|z|\leq\rho\text{ and }|w|\leq\tau\,,$

the $m$-th iterate in the second variable of $S_{\mathcal{I}}(z,w)$, starting
off with $S_{\mathcal{I},0}(z,w)=w$.

Now consider the sequence of analytic functions

(4.11) $\displaystyle
f_{\mathcal{I},m}(z)=S_{\mathcal{I},m}(z,g(z)),\quad\text{ for all
}|z|\leq\rho\,,$

this power series has Taylor expansion

(4.12) $\displaystyle f_{\mathcal{I},m}(z)=\sum_{n\geq
0}B_{n}^{(m)}z^{n},\quad\text{ for all }|z|\leq\rho\,,$

and verifies the recurrence

$\displaystyle
f_{\mathcal{I},m}(z)=z(\psi-\psi_{\mathcal{I}})(f_{\mathcal{I},m-1}(z)),\quad\text{
for all }m\geq 1\,,$

starting with $f_{\mathcal{I},0}(z)=g(z)$.

Taking $\mathcal{I}=\\{0\\}$ in (4.9) we retrieve the iteration scheme (4.4).

###  4.1. Some lemmas concerning $G(z,w)$

The following lemma gives an explicit expression for the partial derivative
with respect to $z$ of the iterate $G_{k}(z,w)$.

######  Lemma 4.4.

For any integer $k\geq 1$ we have

(4.13) $\displaystyle\frac{\partial G_{k}}{\partial z}(z,w)$
$\displaystyle=\sum_{j=1}^{k}\frac{\partial G}{\partial
z}(z,G_{k-j}(z,w))\prod_{i=1}^{j-1}\frac{\partial G}{\partial
w}(z,G_{k-i}(z,w))\,,$

for $|z|\leq\rho$ and $|w|\leq\tau$, with the convention that the empty
product is $1$.

###### Proof.

Formula (4.13) is proved by induction on $k$. For $k=1$, the right-hand side
of (4.13) simplifies and reduces to $({\partial G}/{\partial z})(z,w)$, as it
should.

Assume that identity (4.13) holds for $k\geq 1$, then

$\displaystyle(\star)\quad\frac{\partial G_{k+1}}{\partial
z}(z,w)=\frac{\partial}{\partial z}G(z,G_{k}(z,w))=\frac{\partial G}{\partial
z}(z,G_{k}(z,w))+\frac{\partial G}{\partial w}(z,G_{k}(z,w))\frac{\partial
G_{k}}{\partial z}(z,w)\,.$

Substituting the expression (4.13) for $\partial G_{k}/\partial z$ in
$(\star)$ we find that

$\displaystyle\frac{\partial G_{k+1}}{\partial z}(z,w)$
$\displaystyle=\sum_{j=1}^{k+1}\frac{\partial G}{\partial
z}(z,G_{k+1-j}(z,w))\prod_{i=1}^{j-1}\frac{\partial G}{\partial
w}(z,G_{k+1-i}(z,w))\,.$

∎

The following lemma gives an asymptotic upper bound for the coefficients of
$(\partial G_{k}/\partial z)(z,g(z))$.

######  Lemma 4.5.

For any integer $k\geq 1$ we have

$\displaystyle\textsc{coeff}_{[n]}\left[\frac{\partial G_{k}}{\partial
z}(z,g(z))\right]=O(\rho^{-n}n^{-3/2}),\quad\text{ as
}n\rightarrow\infty\text{ and }n\in\mathbb{N}_{0,Q_{\psi}}\,.$

###### Proof.

Combining formulas (4.7) and (4.8) with Lemma 4.4 we have that

$\displaystyle\textsc{coeff}_{[n]}\left[\frac{\partial G_{k}}{\partial
z}(z,g(z))\right]$
$\displaystyle=\sum_{j=1}^{k}\textsc{coeff}_{[n]}\left[\frac{\partial
G}{\partial z}(z,g_{k-j}(z))\prod_{i=1}^{j-1}\frac{\partial G}{\partial
w}(z,g_{k-i}(z))\right]$
$\displaystyle=\sum_{j=1}^{k}\textsc{coeff}_{[n]}\left[\frac{g_{k+1-j}(z)}{z}\prod_{i=1}^{j-1}\frac{\partial
G}{\partial w}(z,g_{k-i}(z))\right]\,.$

From the inequalities (4.5) we then deduce, for $n\geq 1$, that

$\displaystyle\sum_{j=1}^{k}\textsc{coeff}_{[n]}\left[\frac{g_{k+1-j}(z)}{z}\prod_{i=1}^{j-1}\frac{\partial
G}{\partial w}(z,g_{k-i}(z))\right]$
$\displaystyle\leq\sum_{j=1}^{k}\textsc{coeff}_{[n+1]}\left[g(z)\frac{\partial
G}{\partial w}(z,g(z))^{j-1}\right]\,.$

For $1\leq j\leq k$ we have, using (4.8), that

$\displaystyle\textsc{coeff}_{[n+1]}\left[g(z)\frac{\partial G}{\partial
w}(z,g(z))^{j-1}\right]=\textsc{coeff}_{[n+2-j]}\left[g(z)\psi^{\prime}(g(z))^{j-1}\right]\,.$

Write $H(w)=w\psi^{\prime}(w)^{j{-}1}$. Observe that $H$ is a nonconstant
power series which can be written as
$H(w)=w^{1+(Q_{\psi}-1)(j-1)}\tilde{H}(z^{Q_{\psi}})=w^{Q_{\psi}(j-1)+2-j}\tilde{H}(z^{Q_{\psi}})$,
for certain auxiliary power series $\tilde{H}$ .

Applying Lemma 3.2 with $H(w)=w\psi^{\prime}(w)^{j{-}1}$ and
$m=Q_{\psi}(j-1)+2-j$, we conclude that there exists a constant $E_{j}>0$ such
that

$\displaystyle\textsc{coeff}_{[n+2-j]}\left[g(z)\psi^{\prime}(g(z))^{j-1}\right]\leq
E_{j}\,\rho^{-n}n^{-3/2}\,,\quad\text{ as }n\rightarrow\infty\text{ and
}n\in\mathbb{N}_{0,Q_{\psi}}.\,$

Observe that for integers $n\geq 1$ such that $n\equiv 0,\text{}\mod Q_{\psi}$
we have that $n+2-j\equiv m$,$\mod Q_{\psi}$.

Then we conclude, with $D_{k}=\sum_{j=1}^{k}E_{j}$, that

$\displaystyle\textsc{coeff}_{[n]}\left[\frac{\partial G_{k}}{\partial
z}(z,g(z))\right]\leq D_{k}\,\rho^{-n}n^{-3/2}\,,\quad\text{ as
}n\rightarrow\infty\text{ and }n\in\mathbb{N}_{0,Q_{\psi}}\,.$

∎

For the coefficients of $(\partial G_{k}/\partial w)(z,g(z))$ we have:

######  Lemma 4.6.

For any integer $k\geq 1$ we have

$\displaystyle\textsc{coeff}_{[n]}\left[\frac{\partial G_{k}}{\partial
w}(z,g(z))\right]=O(\rho^{-n}n^{-3/2})\,,\quad\text{ as
}n\rightarrow\infty\text{ and }n\in\mathbb{N}_{0,Q_{\psi}}\,.$

###### Proof.

Applying the chain rule to $G_{k}(z,w)$ and using (4.7) and (4.8), we obtain
that

(4.14) $\displaystyle\frac{\partial G_{k}}{\partial
w}(z,g(z))=\prod_{j=0}^{k-1}\frac{\partial G}{\partial
w}(z,G_{j}(z,g(z)))=z^{k}\prod_{j=0}^{k-1}\psi^{\prime}(G_{j}(z,g(z)))=z^{k}\prod_{j=0}^{k-1}\psi^{\prime}(g_{j}(z))\,,$

for $|z|\leq\rho$ and $|w|\leq\tau$.

Appealing to (4.5) we deduce that

$\textsc{coeff}_{[n]}\left[\frac{\partial G_{k}}{\partial
w}(z,g(z))\right]\leq\textsc{coeff}_{[n-k]}(\psi^{\prime}(g(z))^{k})\,.$

First observe that for integers $j\geq 0$ we have

(4.15)
$\displaystyle\textsc{coeff}_{[j]}\left(\psi^{\prime}(g_{j}(z))\right)=\sum_{n\geq
0}b_{n}\textsc{coeff}_{[j]}\left(g_{j}(z)^{n}\right)\leq\textsc{coeff}_{[j]}\left[\psi^{\prime}(g(z))\right]\,.$

Here we use the formula for the coefficients of a finite product of powers
series and also that $A_{n}^{(l)}\leq A_{n}$, for any pair of nonnegative
integers $l\geq 0$ and $n\geq 1$.

Combining the convolution formula with inequality (4.15) we conclude that

$\displaystyle\textsc{coeff}_{[n]}\left[\frac{\partial G_{k}}{\partial
w}(z,g(z))\right]$
$\displaystyle=\textsc{coeff}_{[n-k]}\left[\prod_{j=0}^{k-1}\psi^{\prime}(G_{j}(z,g(z)))\right]$
$\displaystyle\leq\textsc{coeff}_{[n-k]}\left[\psi^{\prime}(g(z))^{k}\right].$

Denote $H(w)=\psi^{\prime}(w)^{k}$, this function is nonconstant; recall that
$\psi\in\mathcal{K}^{\star}$ cannot be a polynomial of degree $1$. The power
series $H$ can be written as $H(w)=w^{(Q_{\psi}-1)k}\tilde{H}(w^{Q_{\psi}})$,
for certain auxiliary power series $\tilde{H}$ with nonnegative coefficients.

In fact $H(w)=w^{m}(w^{Q_{\psi}(j(Q_{\psi}-1)+l-1)}\tilde{H}(w^{Q_{\psi}}))$
with $m=Q_{\psi}-l$ and $k=jQ_{\psi}+l$, for $j\geq 0$ and
$l\in\\{0,1,\dots,Q_{\psi}-1\\}$. Observe that $m+k\equiv 0$,$\mod Q_{\psi}$.

Applying Lemma 3.2 with $m$ as in the previous paragraph we find that

(4.16) $\displaystyle\textsc{coeff}_{[n-k]}[\psi^{\prime}(g(z))^{k}]\sim
C_{H,\psi}\,\rho^{-n}n^{-3/2}\,,\quad\text{ as }n\rightarrow\infty\text{ and
}n\in\mathbb{N}_{0,Q_{\psi}}\,,$

where $C_{H,\psi}$ is a positive constant. For integers $n\geq k$ such that
$n\equiv 0$,$\mod Q_{\psi}$ we have that $n-k\equiv m$,$\mod Q_{\psi}$.

Using equation (4.16), we conclude that there exists a constant $C>0$ such
that

$\displaystyle\textsc{coeff}_{[n]}\left[\frac{\partial G_{k}}{\partial
w}(z,g(z))\right]\leq C\,\rho^{-n}n^{-3/2}\,,\quad\text{ as
}n\rightarrow\infty\text{ and }n\in\mathbb{N}_{0,Q_{\psi}}\,.$

∎

######  Lemma 4.7.

For any $k\geq 0$ we have

$\displaystyle\frac{\partial G_{k}}{\partial w}(\rho,\tau)\neq 0.$

###### Proof.

Using (4.14) and that $g(\rho)=\tau$, we have that

$\frac{\partial G_{k}}{\partial w}(\rho,\tau)=\frac{\partial G_{k}}{\partial
w}(\rho,g(\rho))=\rho^{k}\prod_{j=0}^{k{-}1}\psi^{\prime}(g_{j}(\rho))\,.$

Now, $\psi^{\prime}(g_{j}(\rho))=0$ could only happen if $\psi^{\prime}(0)=0$
and $g_{j}(\rho)=0$, which means $g_{j}\equiv 0$. The iteration scheme (4.4)
then implies that $g_{j-1}\equiv 0$, and then that $g_{j{-}2}\equiv 0$ and,
finally, that $g\equiv 0$, which is not the case. Thus $(\partial
G_{k}/\partial w)(\rho,\tau)\neq 0$.

∎

###  4.2. Proof of Theorem 4.1.

Fix $k\geq 1$. From (4.7) we have that

$\displaystyle g^{\prime}_{k}(z)=\frac{\partial G_{k}}{\partial
z}(z,g(z))+\frac{\partial G_{k}}{\partial
w}(z,g(z))g^{\prime}(z)\,,\quad\text{ for all }|z|<\rho\,.$

We estimate now the coefficients of $g_{k}^{\prime}(z)$ using the expression
above.

Lemma 4.5 tells us that the first summand of $g_{k}^{\prime}(z)$ satisfies

$\displaystyle\textsc{coeff}_{[n]}\left[\frac{\partial G_{k}}{\partial
z}(z,g(z))\right]=O(\rho^{-n}n^{-3/2})\,,\quad\text{ as
}n\rightarrow\infty\text{ and }n\in\mathbb{N}_{0,Q_{\psi}}\,.$

To estimate the coefficients of the second summand we apply Corollary A with
$(\partial G_{k}/\partial w)(z,g(z))$ in the role of $B(z)$ and
$g^{\prime}(z)$ in the role of $C(z)$ and $r=\rho$.

For $(\partial G_{k}/\partial w)(z,g(z))$, using Lemma 4.6, we have that

$(\star)\quad\textsc{coeff}_{[n]}\left[\frac{\partial G_{k}}{\partial
w}(z,g(z))\right]=O\big{(}\rho^{-n}n^{-3/2}\big{)}\,,\quad\mbox{as
$n\to\infty$}\text{ and }n\in\mathbb{N}_{0,Q_{\psi}}\,.$

On the other hand, for $g^{\prime}(z)$ and because of formula (3.1) we have
that

$(\star\star)\quad\textsc{coeff}_{[n]}\left(g^{\prime}(z)\right)\sim
C\rho^{-n}n^{-1/2}\,,\quad\mbox{as $n\to\infty$}\text{ and
}n\in\mathbb{N}_{0,Q_{\psi}}\,,$

for a positive constant $C$.

The estimates $(\star)$ and $(\star\star)$ combined with Lemma 4.7 allow us to
apply Corollary A, with $\alpha=1/2$ and $\beta=3/2$, and deduce that

$\displaystyle\textsc{coeff}_{[n]}\left[\frac{\partial G_{k}}{\partial
w}(z,g(z))g^{\prime}(z)\right]\sim\frac{\partial G_{k}}{\partial
w}(\rho,\tau)\,(n+1)A_{n{+}1}\,,\quad\text{ as }n\rightarrow\infty\text{ and
}n\in\mathbb{N}_{0,Q_{\psi}}\,.$

Therefore we conclude that

$\displaystyle\textsc{coeff}_{[n]}\left[g_{k}^{\prime}(z)\right]=(n+1)A_{n+1}^{(k)}\sim\frac{\partial
G_{k}}{\partial w}(\rho,\tau)\,(n+1)A_{n+1}\,,\quad\text{ as
}n\rightarrow\infty\text{ and }n\in\mathbb{N}_{0,Q_{\psi}}\,,$

which is equivalent to

$\displaystyle\lim_{\begin{subarray}{c}n\to\infty;\\\
n\in\mathbb{N}_{1,Q_{\psi}}\end{subarray}}\frac{A_{n}^{(k)}}{A_{n}}=\frac{\partial
G_{k}}{\partial w}(\rho,\tau)\,.$

######  Remark 4.8.

Assume that $Q_{\psi}=1$. For any integer $m\geq 0$, we can apply the
asymptotic estimates of this section to the coefficients of the sequence
$f_{\mathcal{I},m}(z)=S_{\mathcal{I},m}(z,g(z))$.

The power series expansions of $S_{\mathcal{I},m}$ and $G_{m}$ are given by:

$\displaystyle S_{\mathcal{I},m}(z,w)=\sum_{l,s \geq
0}S_{l,s}^{(m)}z^{l}w^{m}\quad\text{ and }\quad G_{m}(z,w)=\sum_{l,s \geq
0}G_{l,s}^{(m)}z^{l}w^{m}\,,$

for all $|z|\leq\rho$ and $|w|\leq\tau$ .

By induction on $m\geq 0$ it follows that

(4.17) $\displaystyle S_{l,s}^{(m)}\leq G_{l,s}^{(m)}\,,\quad\text{ for all
}l,s\geq 0\,.$

Combining inequality (4.17) with Lemmas 4.5 and 4.6 we find that

$\displaystyle\textsc{coeff}_{[n]}\left[\frac{\partial
S_{\mathcal{I},m}}{\partial
z}(z,g(z))\right]\leq\textsc{coeff}_{[n]}\left[\frac{\partial G_{m}}{\partial
z}(z,g(z))\right]=O(\rho^{-n}n^{-3/2})\,,\quad\text{ as
}n\rightarrow\infty\,,$

and also that

$\displaystyle\textsc{coeff}_{[n]}\left[\frac{\partial
S_{\mathcal{I},m}}{\partial
w}(z,g(z))\right]\leq\textsc{coeff}_{[n]}\left[\frac{\partial G_{m}}{\partial
w}(z,g(z))\right]=O(\rho^{-n}n^{-3/2})\,,\quad\text{ as
}n\rightarrow\infty\,.$

Applying the same strategy than in the case $\mathcal{I}=\\{0\\}$ we find that

$\displaystyle\lim_{n\rightarrow\infty}\frac{
\,\,B_{n}^{(m)}}{A_{n}}=\frac{\partial S_{\mathcal{I},m}}{\partial
w}(\rho,\tau)\,.$

$\clubsuit$

##  5\. Trees

###  5.1. Rooted trees

A finite rooted tree $a$ is a finite connected graph without cycles with a
distinguished node called root.

The set of leaves (nodes of degree 1, other than the root) of $a$ is denoted
by $\text{leaves}(a)$; we also refer to $\text{leaves}(a)$ as the border of
$a$.

####  5.1.1. Generations and distances on a rooted tree

If $u,v$ are distinct nodes on a rooted tree, its distance $d(u,v)$ is the
length (number of edges) of the unique path (not repeating nodes) that
connects $u$ and $v$. If $u=v$, the distance is $d(u,v)=0$.

For integer $n\geq 0$, the $n$th generation of a rooted tree $a$ is the set of
nodes at exactly distance $n$ from the root. The $0$-th generation consists
simply of the root.

For a node $u$ in the $n$th generation of $a$, the neighboring nodes in
generation $n+1$ are called the descendants of $u$. The outdegree of a node
$u$ of $a$ is the number of its descendants. The leaves are the nodes with no
descendants. The genealogy of a node $v$ of $a$ is the set of nodes in $a$
which lie in the (unique) path connecting the root to $v$.

The distance $\partial(a)$ to the border of the rooted tree $a$ is defined as

$\displaystyle\partial(a)=\min\\{d(\text{root},u):u\in\text{leaves}(a)\\}\,,$

in other terms, the distance to the border of the rooted tree $a$ is the
generation of the leaf with the shortest genealogy. In turn, the height $h(a)$
of a rooted tree is

$h(a)=\max\\{d(\text{root},u):u\in\text{leaves}(a)\\}\,.$

The outdegree profile of a rooted tree $a$ is the list of nonnegative integers

$(k_{0}(a),k_{1}(a),\dots)\,,$

where $k_{j}(a)$ is the number of nodes of $a$ with outdegree $j$. Observe
that if $a$ has $n$ nodes then $k_{j}(a)=0$, for $j\geq n$, and that
$\sum_{j=0}^{n-1}k_{j}(a)=n$ and $\sum_{j=1}^{n-1}jk_{j}(a)=n-1$.

####  5.1.2. Weight of a tree associated to $\psi\in\mathcal{K}$

Fix $\psi(z)=\sum_{n=0}^{\infty}b_{n}z^{n}\in\mathcal{K}$. For any rooted tree
$a$ with $n$ nodes, the $\psi$-weight $w_{\psi}(a)$ of $a$ (associated to
$\psi$) is

(5.1) $\displaystyle w_{\psi}(a)=\prod_{j=0}^{\infty}b_{j}^{k_{j}(a)},$

where $(k_{0}(a),k_{1}(a),\dots)$ is the outdegree profile of $a$. The product
above is actually a finite product, since $k_{j}(a)$ are not 0 only for a
finite number of $j$’s. For details about these weights we refer to [15, p.
999].

####  5.1.3. Plane trees

A rooted plane tree is a finite rooted tree where each descendant of a given
node has an intrinsic label which records its position within the tree, these
labels follow a lexicographical order, see [18] and [11, p. 126] for more
details.

The previous definition is equivalent to specifying an order on the
descendants of each node from left to right, this order allows us to embed our
tree in the plane.

We denote by $\mathcal{G}$ the class of finite rooted plane trees and for any
integer $n\geq 1$ we denote by $\mathcal{G}_{n}$ the subclass of rooted plane
trees with $n$ nodes. Further, for any $k\geq 0$, we denote
$\mathcal{G}^{(k)}\subseteq\mathcal{G}$ the class of rooted plane trees $a$
with $\partial(a)\geq k$ and
$\mathcal{G}_{n}^{(k)}=\mathcal{G}^{(k)}\cap\mathcal{G}_{n}$, the class of
rooted plane trees with $n\geq 1$ nodes and $\partial\geq k$.

We consider also infinite rooted plane trees which have infinitely many nodes,
but each of them has a finite number of descendants. For the precise
definition of this class we refer to [18].

###  5.2. Galton-Watson processes

Let $Y$ be a discrete random variable with expectation
$m\triangleq\mathbf{E}(Y)\leq 1$ and such that

  1. (1)

$\mathbf{P}(Y=0)>0$,

  2. (2)

$\mathbf{P}(Y=0)+\mathbf{P}(Y=1)<1$.

Denote by $\psi$ the probability generating function of $Y$. Conditions (1)
and (2) imply that $\psi(0)>0$ and also that $\psi$ is not a polynomial of
degree $1$.

We use $Y$ as the offspring distribution of a Galton-Watson stochastic process
$(W_{n})_{n\geq 0}$, with $W_{n}$ being the random size of the $n$-generation.

We start with a unique individual in generation zero: $W_{0}\equiv 1$. This
individual has a number of offsprings with probability distribution given by
$Y$. These offsprings comprise the first generation whose size is $W_{1}$
(which has the same distribution as $Y$). Each individual of the first
generation has a random number offsprings with probability distribution $Y$,
independently of each other; these offsprings comprise in turn the second
generation of random size $W_{2}$. And so on.

For i.i.d copies $(Y_{i,j})_{i,j\geq 1}$ of the variable $Y$ and for any
integer $n\geq 1$ we have

$\displaystyle W_{n}=Y_{n,1}+\dots+Y_{n,{W_{n-1}}},\quad\mbox{for $n\geq
1$}\,.$

Besides $W_{0}\equiv 1$.

The discrete process $(W_{n})_{n\geq 0}$ is the Galton-Watson process (from
now on abbreviated GW) with offspring distribution given by $Y$. For each
integer $n\geq 0$, the random variable $W_{n}$ gives the number of individuals
in the $n$th generation of our process.

Since $m=\mathbf{E}(Y)\leq 1$, the GW process with offspring distribution $Y$
extinguishes with probability $1$, that is, $\mathbf{P}(W_{m}=0,\text{ for
some }m)=1$. See, for instance, [24]. The condition $m\leq 1$, which here we
assume from the start, is referred in the literature as the subcritical
($m<1$) and critical ($m=1$) cases. The total progeny of the GW process is
given by the random variable

(5.2) $\displaystyle
W\triangleq\sum_{j=0}^{\infty}W_{j}\stackrel{{\scriptstyle
d}}{{=}}1+\sum_{j=1}^{\infty}W_{j}.$

Since the process extinguishes with probability 1, the total progeny $W$ is
finite almost surely.

We denote the probability generating function of $W$ by $g$. The power series
$g$ verifies Lagrange’s equation with data $\psi$, that is,

$\displaystyle g(z)=z\psi(g(z)),\quad\text{ for all }z\in\mathbb{D}.$

See, for instance, [20] and [24].

For further basic background on classical Galton-Watson processes we refer,
for instance, to [20] and [24].

####  5.2.1. Galton-Watson processes and rooted plane trees

Assume that $Y$ is a discrete random variable with $m=\mathbf{E}(Y)\leq 1$.
Each realization of a GW process with offspring distribution $Y$ can be
identified with a finite rooted plane tree.

Galton-Watson processes are introduced as a model for the evolution of a
population where each individual is distinguishable from the other. In this
model we record the moment of birth and the relation parent/child of each
individual. To take care of this information, we impose an order on the
descendants of each node: we label intrinsically from left to right, as we do
for the rooted plane trees, the position of the descendants of each node.

To generate a Galton-Watson process we use independent copies of a discrete
random variable $Y$. We start with one individual with offspring distribution
$Y$. The descendants of this individual are ordered from left to right. Using
this order we assign copies of $Y$, that we denote
$Y_{1,1},Y_{1,2},\dots,Y_{1,Y}$, to each of the new individuals in the first
generation of our process, then we iterate this construction.

This correspondence between nodes and random variables consider, tacitly, that
the descendants of each node are ordered from left to right, otherwise, we
could not assign a specific random variable to a specific individual and,
therefore, we could not record the number of descendants of a particular
individual. If nodes are not distinguishable, that is, if the descendants of
each individual are not ordered, then, in general, we cannot register if a
given node at the left or a given node at the right has certain number of
descendants: we cannot distinguish left and right and hence we cannot
distinguish different individuals.

We can think about this (subcritical or critical) Galton-Watson process as a
random variable $T$ which takes values in the set $\mathcal{G}$ of finite
rooted plane trees.

For any integer $n\geq 1$ and any rooted plane tree $a\in\mathcal{G}_{n}$ the
$\psi$-weight $w_{\psi}(a)$, here $\psi$ denotes the probability generating
function of $Y$, is the probability of the event $\\{T=a\\}$.

$\displaystyle\mathbf{P}(T=a)=\prod_{j=0}^{\infty}\mathbf{P}(Y=j)^{k_{j}(a)}=w_{\psi}(a),$

where $(k_{0}(a),k_{1}(a),\dots)$ is the outdegree profile of the tree $a$.

Denote by $\\#(T)$ the random variable that gives the total progeny of the GW
process $T$, then we have $\\#(T)\stackrel{{\scriptstyle d}}{{=}}W$. Observe
that $\mathbf{P}(\\#(T)=n)=\mathbf{P}(T\in\mathcal{G}_{n})$, for all $n\geq
1$.

We define the random variable distance to the border of the Galton-Watson
process $T$ as $\partial(T)$. The random variable $\partial(T)$ is given by

$\displaystyle\mathbf{P}(\partial(T)=k)=\mathbf{P}(T\in\mathcal{G}^{(k)}\setminus\mathcal{G}^{(k+1)})\,.$

We aim in this paper to obtain, for any integer $k\geq 0$ and any GW process
$T$, an asymptotic formula for the conditional probability

$\displaystyle\mathbf{P}(\partial(T)\geq
k\,|\,\\#(T)=n)=\mathbf{P}(T\in\mathcal{G}^{(k)}\,|\,\\#(T)=n),\quad\mbox{as
$n\rightarrow\infty$.}$

###  5.3. Parametric families of Galton-Watson processes

Let $\psi(z)=\sum_{n=0}^{\infty}b_{n}z^{n}$ be a power series in
$\mathcal{K}^{\star}$ with radius of convergence $R_{\psi}$ and apex
$\tau\in(0,R_{\psi})$, and denote by $(Y_{t})_{t\in[0,R_{\psi})}$ its Khinchin
family.

We let $g(z)=\sum_{n\geq 1}A_{n}z^{n}$ be the power series solution of
Lagrange’s equation with data $\psi$ which has radius of convergence
$\rho=\tau/\psi(\tau)$, and denote by $(Z_{t})_{t\in[0,\tau/\psi(\tau))}$ its
associated shifted Khinchin family. Observe that $Z_{0}\equiv 1$.

We consider the one-parameter family of GW processes
$(T_{t})_{t\in[0,R_{\psi})}$ where $T_{t}$ is the GW process with offspring
distribution given by $Y_{t}$. For $t=0$, the GW process degenerates, its
total progeny is just one individual (or in terms of trees, just the root).

For each $t\in[0,R_{\psi})$ we denote by $q(t)$, the probability of extinction
for the GW process $T_{t}$. We have $q(t)=1$, for $t\in[0,\tau]$, since for
$t$ in that interval, $m_{\psi}(t)\leq 1$. For $t\in(\tau,R_{\psi})$, we have
that $0<q(t)<1$, see, for instance, [24, p. 4].

For each $t\in(0,R_{\psi})$, we let $\psi_{t}(z)=\psi(tz)/\psi(t)$ be the
probability generating function of the random variable $Y_{t}$; we set
$\psi_{0}\equiv 1$.

We consider, for each $t\in[0,R_{\psi})$, Lagrange’s equation with data
$\psi_{t}$ and the corresponding power series solution $g_{t}(z)$:

(5.3) $\displaystyle g_{t}(z)=z\psi_{t}(g_{t}(z)).$

The case $t=0$ is a degenerate case: $\psi_{0}(z)\equiv 1$ and $g_{0}(z)=z$.

######  Proposition 5.1.

For $t\in[0,R_{\psi})$ we have that

(5.4) $\displaystyle g_{t}(z)=\frac{g(tz/\psi(t))}{t},\quad\mbox{for all
$t\in[0,R_{\psi})$ and $|z|\leq 1$}\,.$

The holomorphic function $g_{t}$ is continuous on $\partial\mathbb{D}$ and
$g_{t}(\mathbb{D})\subset\mathbb{D}$.

Besides, for $t\in[0,\tau]$, the power series $g_{t}(z)$ is the probability
generating function of the random variable $Z_{t/\psi(t)}$.

###### Proof.

We write $h_{t}(z)={g(tz/\psi(t))}/{t}$. Using that $g$ satisfies Lagrange’s
equation with data $\psi$, it is immediate to verify that $h_{t}$ satisfies
Lagrange’s equation with data $\psi_{t}$. Uniqueness of the solution gives
that $g_{t}\equiv h_{t}$.

Equation (5.4) means that

(5.5) $g_{t}(z)=\sum_{n\geq 1}\frac{A_{n}t^{n{-}1}}{\psi(t)^{n}}z^{n}\,.$

The Otter-Meir-Moon formula (3.1) and formula (5.4) give that the radius of
convergence of the power series $g_{t}$ is

$R_{g_{t}}=\frac{\tau/\psi(\tau)}{t/\psi(t)}\,,$

and also the continuity of $g_{t}$ on $\partial\mathbb{D}$. Observe that
$R_{g_{t}}>1$ for $t\neq\tau$, while $R_{g_{\tau}}=1$, see Lemma 3.1.

Equation (5.3) is then satisfied for $|z|\leq 1$, for all $t\in[0,R_{\psi})$.

Now, for $t\in[0,\tau]$, since then $g(t/\psi(t))=t$, we deduce that

$\displaystyle\mathbf{P}(Z_{t/\psi(t)}=n)$
$\displaystyle=\frac{A_{n}(t/\psi(t))^{n}}{g(t/\psi(t))}$
$\displaystyle=\frac{A_{n}(t/\psi(t))^{n}}{t}=\textsc{coeff}_{[n]}(g_{t}(z))\,,\quad\mbox{for
$t\in[0,\tau]$ and $n\geq 1$}\,.$

Therefore, as claimed, $g_{t}$ is the probability generating function of
$Z_{t/\psi(t)}$, for all $t\in[0,\tau]$. ∎

######  Remark 5.2.

The case $t=0$ of this result needs of the convention $0^{0}=1$. $\clubsuit$

Taking $z=1$ in formula (5.3) we find that $g_{t}(1)$ is a fixed point for
$\psi_{t}(z)$, that is,

$\displaystyle\psi_{t}(g_{t}(1))=g_{t}(1),\quad\text{ for all
}t\in[0,R_{\psi}).$

From here we conclude that the probability of extinction $q(t)$ is given by

(5.6) $\displaystyle q(t)=g_{t}(1),\quad\text{ for all }t\in[0,R_{\psi}).$

See [24, p. 4] for more details about this equality.

From formula (5.3) we deduce that the probability of extinction function
$q(t)$ maybe be expressed as

(5.7) $\displaystyle
q(t)=\sum_{n=1}^{\infty}\frac{A_{n}t^{n-1}}{\psi(t)^{n}},\quad\text{ for all
}t\in[0,R_{\psi}),$

with the convention that $0^{0}=1$. Recall that $q(t)=1$, for $t\in[0,\tau)$.

######  Corollary 5.3.

For each $t\in[0,\tau]$, the power series $g_{t}$ is the probability
generating function of $\\#(T_{t})$ and the following equality in distribution
holds

$\displaystyle\\#(T_{t})\stackrel{{\scriptstyle d}}{{=}}Z_{t/\psi(t)}.$

###### Proof.

For all $t\in[0,\tau]$, the power series $g_{t}$ is a probability generating
function. Since $g_{t}$ is the solution of (5.3) and $\psi_{t}$ is the
probability generating function of $Y_{t}$, we have that $g_{t}$ is the
probability generating function of the size of the progeny $\\#(T_{t})$. ∎

######  Remark 5.4.

For each $t\in(\tau,R_{\psi})$, $\\#(T_{t})$ is a proper random variable. In
this case, each $\\#(T_{t})$ takes values in
$\\{1,2,3,\dots\\}\cup\\{\infty\\}$, therefore
$(\\#(T_{t}))_{t\in[0,R_{\psi})}$ is a, proper, one-parameter family of random
variables. $\clubsuit$

###  5.4. The conditional random tree

Let $\mathcal{R}\subset\mathcal{G}$ be a subclass of rooted plane trees. For
integers $n\geq 1$, denote by $\mathcal{R}_{n}$ the subclass of trees of
$\mathcal{R}$ of size $n$.

Fix $\psi(z)=\sum_{n=0}^{\infty}b_{n}z^{n}$ in $\mathcal{K}^{\star}$ with
radius of convergence $R_{\psi}$ and apex $\tau\in(0,R_{\psi})$. For integer
$n\geq 1$, we denote with $U_{n}$ the sum of the $\psi$-weights of the trees
in the class $\mathcal{G}_{n}$ and, similarly, $V_{n}$ the sum of the
$\psi$-weights of the trees in the class $\mathcal{R}_{n}$:

(5.8) $\displaystyle U_{n}=\sum_{a\in\mathcal{G}_{n}}w_{\psi}(a)\,,\quad\text{
and }\quad V_{n}=\sum_{a\in\mathcal{R}_{n}}w_{\psi}(a)\,,$

see equation (5.1) and also [15].

Fix $t\in(0,\tau]$. For the GW process $T_{t}$ and any rooted plane tree
$a\in\mathcal{G}_{n}$, the probability that $T_{t}$ is equal to $a$ is given
by

(5.9)
$\mathbf{P}(T_{t}=a)=\prod_{j=0}^{n-1}\mathbf{P}(Y_{t}=j)^{k_{j}(a)}=\omega_{\psi_{t}}(a)=\prod_{j=0}^{n-1}\frac{b_{j}^{k_{j}}t^{jk_{j}}}{\psi(t)^{k_{j}}}=w_{\psi}(a)\frac{t^{n-1}}{\psi(t)^{n}}\,.$

See, for instance, [18] or [19].

Thus,

(5.10)
$\mathbf{P}(T_{t}\in\mathcal{R}_{n})=V_{n}\frac{t^{n-1}}{\psi(t)^{n}}\,,$

and, in particular,

(5.11)
$\mathbf{P}(T_{t}\in\mathcal{G}_{n})=U_{n}\frac{t^{n-1}}{\psi(t)^{n}}\,,$

The next proposition follows from (5.10) and (5.11).

######  Proposition 5.5.

For $t\in(0,R_{\psi})$, we have

$\displaystyle\mathbf{P}(T_{t}\in\mathcal{R}\,|\,\\#(T_{t})=n)=\frac{V_{n}}{U_{n}}\,,$

for any integer $n\geq 1$ such that $n\equiv 1,\text{}\mod Q_{\psi}$.

###### Proof.

For integers $n\equiv 1,\mod Q_{\psi}$, just observe that

$\mathbf{P}(T_{t}\in\mathcal{R}\,|\,\\#(T_{t})=n)=\frac{\mathbf{P}(T_{t}\in\mathcal{R}_{n})}{\mathbf{P}(T_{t}\in\mathcal{G}_{n})}$

and use (5.10) and (5.11).∎

For $t\in(0,R_{\psi})$ and $n\geq 1$, we have that

$\mathbf{P}(T_{t}\in\mathcal{G}_{n})=\mathbf{P}(\\#(T_{t})=n)=\textsc{coeff}_{[n]}(g_{t}(z))$

and thus from formula (5.5) we see that

$\mathbf{P}(T_{t}\in\mathcal{G}_{n})=\frac{A_{n}t^{n{-}1}}{\psi(t)^{n}}\,.$

Comparing with (5.11) we see that

$A_{n}=U_{n}=\sum_{a\in\mathcal{G}_{n}}\omega_{\psi}(a)\,,\quad\mbox{for
$n\geq 1$}\,.$

##  6\. The distance to the border

Now we introduce a formula for the probability that a Galton-Watson process
$T_{t}$, conditioned to have exactly $n$ nodes, has $\partial(T_{t})\geq k$.

We recall here the notation $\mathcal{G}$ for the class of finite rooted plane
trees and $\mathcal{G}^{(k)}\subseteq\mathcal{G}$ for the subclass of finite
rooted plane trees with $\partial\geq k$.

For any $\psi\in\mathcal{K}$, we denote

(6.1) $\displaystyle A_{n}=\sum_{a\in\mathcal{G}_{n}}w(a),\quad\text{ and
}\quad A_{n}^{(k)}=\sum_{a\in\mathcal{G}_{n}^{(k)}}w(a),$

here $w(a)$ denotes the weight of $a$ with respect to a given
$\psi\in\mathcal{K}$, see equation (5.1).

For any integer $k\geq 1$ and any $t\in[0,\tau]$, the expression
$A_{n}^{(k)}t^{n-1}/\psi(t)^{n}$ does not define a probability distribution.
In particular, this expression does not define a Khinchin family:

$\displaystyle\mathbf{P}(T_{t}\in\mathcal{G}^{(k)})=\sum_{n\geq
1}\,\mathbf{P}(T_{t}\in\mathcal{G}_{n}^{(k)})=\sum_{n\geq
k}\,\frac{A_{n}^{(k)}t^{n-1}}{\psi(t)^{n}}<\sum_{n\geq
1}\,\frac{A_{n}t^{n-1}}{\psi(t)^{n}}=1.$

Here we use that for all $k\geq 1$, the class of rooted trees
$\mathcal{G}_{n}^{(k)}$ is strictly contained in the class $\mathcal{G}_{n}$.

On the other hand for $k=0$, we have the equality $A_{n}^{(0)}=A_{n}$, for all
$n\geq 1$, therefore
$\mathbf{P}(T_{t}\in\mathcal{G}^{(0)})=\mathbf{P}(T_{t}\in\mathcal{G})=1$, for
all $t\in[0,\tau]$.

In the previous reasoning we have used that, for any integer $k\geq 0$, we can
partition the class of rooted plane trees with $\partial\geq k$ by its number
of nodes:

$\displaystyle\mathcal{G}^{(k)}=\bigsqcup_{n=k}^{\infty}\mathcal{G}_{n}^{(k)}\subseteq\mathcal{G},$

where $\mathcal{G}_{n}^{(k)}\cap\mathcal{G}_{m}^{(k)}=\emptyset$, for any pair
of integers $n,m\geq 1$ such that $n\neq m$.

######  Lemma 6.1.

Fix $\psi\in\mathcal{K}$. For any integer $k\geq 0$, and any
$t\in(0,R_{\psi})$, we have

$\displaystyle\mathbf{P}(\partial(T_{t})\geq
k\,|\,\\#(T_{t})=n)=\mathbf{P}(T_{t}\in\mathcal{G}^{(k)}\,|\,\\#(T_{t})=n)=\frac{\,\,\,A_{n}^{(k)}}{A_{n}},$

for all $n\in\mathbb{N}_{1,Q_{\psi}}.$

The proof of this Lemma follows applying Theorem 5.5 with
$\mathcal{R}_{n}=\mathcal{G}^{(k)}_{n}$.

###  6.1. Asymptotic results

Now we give a recurrence relation for the analytic function with coefficients
$A_{n}^{(k)}$. Using this representation we give an asymptotic formula for the
sequence $A_{n}^{(k)}$, as the number of nodes $n\rightarrow\infty$.

For any integer $k\geq 0$, we denote by $g_{k}(z)$ the analytic function with
coefficients $A_{n}^{(k)}$, that is,

$\displaystyle g_{k}(z)=\sum_{n=k}^{\infty}A_{n}^{(k)}z^{n},\quad\text{ for
all }|z|\leq\rho\triangleq\tau/\psi(\tau).$

For all $t\in[0,R_{\psi})$ and $|z|\leq 1$, we have

$\displaystyle\frac{g_{k}(tz/\psi(t))}{t}=\sum_{n=k}^{\infty}\frac{A_{n}^{(k)}t^{n-1}}{\psi(t)^{n}}z^{n}=\sum_{n=k}^{\infty}\mathbf{P}(T_{t}\in\mathcal{G}_{n}^{(k)})z^{n}.$

######  Lemma 6.2.

For any $\psi(z)=\sum_{n=0}^{\infty}b_{n}z^{n}\in\mathcal{K}$ and any integer
$k\geq 1$, the analytic function $g_{k}(z)$ verifies the recurrence relation

(6.2) $\displaystyle g_{k}(z)=z(\psi(g_{k-1}(z))-b_{0}),$

where $g_{0}(z)=g(z)$. Here $g(z)$ denotes the solution of Lagrange’s equation
with data $\psi\in\mathcal{K}$.

###### Proof.

We have that

$\displaystyle\textsc{coeff}_{[n]}\left[z(\psi(g_{k-1}(z))-b_{0})\right]$
$\displaystyle=\textsc{coeff}_{n-1}\left[\psi(g_{k-1}(z))-b_{0}\right]$
$\displaystyle=\sum_{j=1}^{n-1}b_{j}\textsc{coeff}_{n-1}[g_{k-1}(z)^{j}],$

therefore

$\displaystyle\textsc{coeff}_{[n]}\left[z(\psi(g_{k-1}(z))-b_{0})\right]=\sum_{j=1}^{n-1}b_{j}\sum_{l_{1}+l_{2}+\dots+l_{j}=n-1}A_{l_{1}}^{(k-1)}A_{l_{2}}^{(k-1)}\dots
A_{l_{j}}^{(k-1)}.$

For the family of rooted plane trees with $\partial\geq k$, that is,
$\mathcal{G}^{(k)}$, we have:

$\mathcal{G}^{(k)}=\ \ \leavevmode\hbox to26.63pt{\vbox
to41.81pt{\pgfpicture\makeatletter\hbox{\hskip
13.31357pt\lower-36.25243pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{}{{}}{}{{}}{}{{}}{}{{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{0.0pt}{-28.45276pt}\pgfsys@stroke\pgfsys@invoke{
}\hbox{\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-2.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\bullet$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}}\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-9.98056pt}{-32.91942pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{$\mathcal{G}^{(k-1)}$}} }}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{}{ {}{}{}} {{{{{}}{ {}{}}{}{}{{}{}}}}}{}{{{{{}}{
{}{}}{}{}{{}{}}}}}{{}}{}{}{}{}\pgfsys@moveto{0.0pt}{-20.4531pt}\pgfsys@lineto{0.0pt}{-5.75522pt}\pgfsys@stroke\pgfsys@invoke{
} } \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\ \ +\leavevmode\hbox
to66.46pt{\vbox to41.81pt{\pgfpicture\makeatletter\hbox{\hskip
33.23041pt\lower-36.25243pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{}{{}}{}{{}}{}{{}}{}{{}}{}{{}}{}{{}}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{-19.91684pt}{-28.45276pt}\pgfsys@moveto{19.91684pt}{-28.45276pt}\pgfsys@stroke\pgfsys@invoke{
}\hbox{\hbox{\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-2.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\bullet$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}}\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-29.8974pt}{-32.91942pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{$\mathcal{G}^{(k-1)}$}} }}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}}\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{9.93628pt}{-32.91942pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{$\mathcal{G}^{(k-1)}$}} }}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{}{ {}{}{}} {{{{{}}{ {}{}}{}{}{{}{}}}}}{}{{{{{}}{
{}{}}{}{}{{}{}}}}}{{}}{}{}{}{ {}{}{}} {{{{{}}{ {}{}}{}{}{{}{}}}}}{}{{{{{}}{
{}{}}{}{}{{}{}}}}}{{}}{}{}{}{}\pgfsys@moveto{-14.3176pt}{-20.4531pt}\pgfsys@lineto{-4.02802pt}{-5.75522pt}\pgfsys@moveto{4.02853pt}{-5.75522pt}\pgfsys@lineto{14.31796pt}{-20.4531pt}\pgfsys@stroke\pgfsys@invoke{
} } \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}+\text{ \hskip
5.69046pt}\dots$

In this diagram we fix a root and then we paste a tree with $\partial\geq
k-1$, another root and then we paste 2 trees with $\partial \geq k-1$, and so
on. By means of this process we build all the rooted plane trees with
$\partial\geq k$.

If we restrict our attention to the rooted plane trees with $\partial\geq k$
and $n$ nodes, the previous diagram should stop at certain point which depends
on the value of $k$. For the rooted plane trees with $\partial\geq k$ and $n$
nodes, we allocate $n-1$ nodes in the trees which descend from the root: by
means of this process we enumerate the class $\mathcal{G}^{(k)}_{n}$.

If we paste $j$ rooted trees with $\partial\geq k-1$ to a root, then, when
calculating the weights, we should weight the root using the coefficient
$b_{j}$. The previous reasoning tell us that

$\displaystyle\textsc{coeff}_{[n]}\left[z(\psi(g_{k-1}(z))-b_{0})\right]=\sum_{j=1}^{n-1}b_{j}\sum_{l_{1}+l_{2}+\dots+l_{j}=n-1}A_{l_{1}}^{(k-1)}A_{l_{2}}^{(k-1)}\dots
A_{l_{j}}^{(k-1)}=A_{n}^{(k)}.$

See [11] for similar arguments applied to combinatorial classes of rooted
labeled trees or more generally to simple varieties of trees. ∎

Now, we give an asymptotic formula for the probability that a Galton-Watson
process $T_{t}$, conditioned to have total progeny equal to $n$, has distance
to the border $\partial(T_{t})\geq k$, as the number of nodes
$n\rightarrow\infty$.

######  Theorem 6.3.

Fix an integer $k\geq 0$ and a function $\psi\in\mathcal{K}^{\star}$ with
$Q_{\psi}\geq 1$, then, for all $t\in(0,R_{\psi})$, we have

$\displaystyle\lim_{\begin{subarray}{c}n\to\infty;\\\
n\in\mathbb{N}_{1,Q_{\psi}}\end{subarray}}\mathbf{P}(\partial(T_{t})\geq k
\,|\,\\#(T_{t})=n)=\lim_{\begin{subarray}{c}n\to\infty;\\\
n\in\mathbb{N}_{1,Q_{\psi}}\end{subarray}}\frac{A_{n}^{(k)}}{A_{n}}=\frac{\partial
G_{k}}{\partial w}(\rho,\tau).$

The proof of this Theorem follows combining Lemma 6.1 with Theorem 4.1.

######  Remark 6.4.

For values of $t$ in the interval $(\tau,R_{\psi})$, we can also study the
Galton-Watson process $T_{t}$ upon extinction. Take $a\in\mathcal{G}$, this is
a finite rooted plane tree. Suppose that $a$ has exactly $n\geq 1$ nodes, then
we have

(6.3)
$\displaystyle\mathbf{P}(T_{t}=a\,|\,\text{extinction})=\frac{\omega_{\psi}(a)t^{n-1}}{\psi(t)^{n}}\frac{1}{q(t)}.$

Formula (6.3) is valid for all $t\in(0,R_{\psi})$, in particular we have

$\displaystyle\mathbf{P}(T_{t}=a)=\mathbf{P}(T_{t}=a\,|\,\text{extinction})=\frac{\omega_{\psi}(a)t^{n-1}}{\psi(t)^{n}},\quad\text{
for all }t\in(0,\tau].$

Here we use that $q(t)=1$, for all $t\in[0,\tau]$.

For each $t\in(0,R_{\psi})$ we denote $\tilde{T}_{t}$, the Galton-Watson
process $T_{t}$ conditioned upon extinction. If we condition $\tilde{T}_{t}$
to have total progeny $n \geq 1$, then we find that

$\displaystyle\mathbf{P}(\tilde{T}_{t}\in\mathcal{R}\,|\,\\#(\tilde{T}_{t})=n)=\frac{V_{n}}{U_{n}},$

for all $n\in\mathbb{N}_{1,Q_{\psi}}$.

From here, and depending on the restrictions we impose to the class
$\mathcal{R}$, we can find an asymptotic formula for this probability, as the
number of nodes $n\rightarrow\infty$.

##  7\. Applications

In this section we apply Theorem 6.3 to some specific classes of rooted trees.
By means of this result, we give asymptotic formulas for the rooted labeled
Cayley trees (Poisson offspring distribution), rooted plane trees (geometric
offspring distribution) and rooted binary plane trees (Bernoulli $\\{0,2\\}$
offspring distribution), with distance to the border bigger or equal than
$k\geq 0$, as the number of nodes $n$ escapes to infinity.

For the study of the height we refer to [23], [6], and [9] for the Cayley,
plane and binary case respectively.

###  7.1. Rooted labeled Cayley trees

The class of rooted labeled Cayley trees with $n$ nodes $\mathcal{T}_{n}$ is a
family of rooted trees where the descendants of each node are not ordered.
This is a family of labeled trees, that is, for each rooted labeled Cayley
tree with $n$ nodes there is a bijective correspondence between the set of
nodes and the set of labels $\\{1,2,\dots,n\\}$.

The main property of this family of trees is that the trees in this class are
not embedded in the plane. For the specific details about this family of trees
we refer, for instance, to [11, pp. 126-127].

The rooted labeled Cayley trees form a simple variety of trees, see, for
instance [11, pp. 126-127]. A consequence of this fact is that the number of
rooted labeled Cayley trees with $n$ nodes might be counted using Lagrange’s
equation with data $\psi(z)=e^{z}$.

The Cayley tree function $T(z)$, the exponential generating function for the
counting sequence of this family of trees, satisfies Lagrange’s equation

(7.1) $\displaystyle T(z)=ze^{T(z)},\quad\text{ for all }|z|\leq\frac{1}{e}.$

Applying Lagrange’s inversion formula, we find that

(7.2) $\displaystyle
T(z)=\sum_{n=1}^{\infty}\frac{n^{n-1}}{n!}z^{n},\quad\text{ for all
}|z|\leq\frac{1}{e}.$

We want to apply Theorem 6.3 to this particular family of rooted labeled
trees. Each of the elements of the Khinchin family associated to
$\psi(z)=e^{z}$, that we denote $(Y_{t})_{t\in[0,\infty)}$, follows a Poisson
distribution with parameter $t\in[0,\infty)$. See [3], [4] and [7] for more
examples of Khinchin families.

The mean function is given by

$\displaystyle m_{\psi}(t)=\frac{t\psi^{\prime}(t)}{\psi(t)}=t,\quad\text{ for
all }t\in[0,\infty),$

in fact the equation $m_{\psi}(t)=1$ has solution $\tau=1.$

In this case the bivariate function $G(z,w)$ is given by

$\displaystyle G(z,w)=z(e^{w}-1),$

for all $|z|\leq 1/e$ and $|w|\leq 1$.

For any pair of integers $k\geq 0$ and $n\geq 1$, we denote $t_{n}^{(k)}$ the
counting sequence for the rooted labeled Cayley trees with $n$ nodes and
$\partial\geq k$. Besides, we denote $t_{n}$ the counting sequence for the
rooted labeled Cayley trees with $n$ nodes. Formula (7.2) tell us that
$t_{n}=n^{n-1}$, this is Cayley’s formula for the enumeration of the rooted
labeled Cayley trees.

Now, applying Lemma 6.1, we find that for any integer $k\geq 0$, and as
$n\rightarrow\infty$, the proportion that trees in $\mathcal{T}_{n}^{(k)}$ do
occupy in $\mathcal{T}_{n}$ is given by the limit

$\displaystyle\lim_{n\rightarrow\infty}\frac{\,\,\,\,t_{n}^{(k)}}{t_{n}}=\frac{\partial
G_{k}}{\partial w}(1/e,1)\,.$

This asymptotic formula gives the answer to a question posed in [1], for an
alternative proof of this result when $k=2$ and $k=3$, see [1, pp. 309-312].

We denote by $c_{k}\triangleq\lim_{n\rightarrow\infty}t_{n}^{(k)}/t_{n}$.
Applying the chain rule to $G_{k}(z,w)$ we obtain the following recurrence
relation:

(7.3) $\displaystyle c_{k}=\frac{1}{e}e^{G_{k-1}(1/e,1)}c_{k-1},\quad\text{
for all }k\geq 1,$

with $c_{0}=1$.

Let’s study some particular instances of this formula.

  * $\blacksquare$

The case $k=2$. Using the recurrence relation (7.3), we find that

(7.4) $\displaystyle
c_{2}=\frac{1}{e}e^{G(1/e,1)}c_{0}=\frac{1}{e}e^{1-1/e}=e^{-1/e}.$

This result appears in [1, p. 312].

  * $\blacksquare$

The case $k=3$. Using again our recurrence relation, see equation (7.3), we
find that

$\displaystyle c_{3}=\frac{1}{e}e^{G_{2}(1/e,1)}c_{2}.$

We have

$\displaystyle
G_{2}(1/e,1)=G(1/e,G(1/e,1))=G(1/e,1-1/e)=\frac{1}{e}(e^{1-1/e}-1),$

and $c_{2}=e^{-1/e}$, see equation (7.4), therefore

$\displaystyle c_{3}=\frac{1}{e}e^{-1/e}e^{(e^{1-1/e}-1)/e}.$

This is Theorem 3.3, in [1, p. 309].

  * $\blacksquare$

The case $k=4$. In this case we have

$\displaystyle
c_{4}=\frac{1}{e}\exp\left(\frac{1}{e}(e^{(e^{1-1/e}-1)/e}-1)\right)\frac{1}{e}e^{-1/e}e^{(e^{1-1/e}-1)/e}.$

In general, for any $k\geq 4$, we might continue iterating the recurrence
relation (7.3) and therefore find any particular value of $c_{k}$. This means
that, for any $k\geq 1$, the constant $c_{k}$ is computable by iteration.

The recurrence relation (7.3) is the answer to a question posed in [1, p.
312].

###  7.2. Rooted plane trees

The rooted plane trees form a simple variety of trees, that is, we can count
these trees by means of Lagrange’s equation with data $\psi(z)=1/(1-z)$.

The generating function for this family of rooted trees, that we denote
$P(z)$, verifies Lagrange’s equation with data $\psi$:

(7.5) $\displaystyle P(z)=\frac{z}{1-P(z)},\quad\text{ for all
}|z|\leq\frac{1}{4}.$

Applying Lagrange’s inversion formula, we find that

(7.6) $\displaystyle P(z)=\sum_{n=1}^{\infty}C_{n-1}z^{n},\quad\text{ for all
}|z|\leq\frac{1}{4},$

where $C_{n}$ denotes the $n$th Catalan number.

We want to apply Theorem 6.3 to the family of rooted plane trees. Each of the
elements of the Khinchin family associated to $\psi(z)=1/(1-z)$, that we
denote $(Y_{t})_{t\in[0,1)}$, follows a geometric distribution with parameter
$1-t$. See [3], [4] and [7] for examples of Khinchin families and for more
details about this specific family of random variables.

The mean function of this Khinchin family is

$\displaystyle m_{\psi}(t)=\frac{t}{1-t},\quad\text{ for all }t\in[0,1),$

in fact the equation $m_{\psi}(t)=1$ has solution $\tau=1/2$.

For $\psi(z)=1/(1-z)$ we have that

$\displaystyle G(z,w)=z\left(\frac{1}{1-w}-1\right)=\frac{zw}{1-w},$

for all $|z|\leq 1/4$ and $|w| \leq 1/2$.

In this particular case it is possible to find a closed expression for the
$k$-th iterate of $G(z,w)$, this is the content of the following Lemma.

######  Lemma 7.1.

For any $k\geq 1$, the $k$-th iterate of $G(z,w)$ verifies that

(7.7) $\displaystyle
G_{k}(z,w)=\frac{z^{k}w}{1-\frac{1-z^{k}}{1-z}w},\quad\text{ for all }|z|\leq
1/2,|w|\leq 1/4.$

This Lemma follows by induction on $k\geq 1$. Applying this result we will be
able to provide an explicit expression for the asymptotic formula given by
Theorem 6.3. This is a particularity of this example.

We cannot find a closed expression, in the spirit of equation (7.7), for the
family of rooted labeled Cayley trees. See the recurrence relation (7.3).

For any pair of integers $k\geq 0$ and $n\geq 1$ we denote $P_{n}^{(k)}$ the
counting sequence for the rooted plane trees with $n$ nodes and $\partial\geq
k$. Besides, we denote $P_{n}$ the counting sequence for the rooted plane
trees with $n$ nodes. Equation (7.6) gives that $P_{n}=C_{n-1}$. This formula
follows applying Lagrange’s inversion formula to equation (7.5).

Finally, applying Theorem 6.3 to the family of rooted plane trees, we find the
following result

######  Theorem 7.2.

For any integer $k\geq 0$, and as $n\rightarrow\infty$, the proportion that
trees in $\mathcal{G}_{n}^{(k)}$ do occupy in $\mathcal{G}_{n}$ is given by
the limit

$\displaystyle\lim_{n\rightarrow\infty}\frac{\,\,\,\,P_{n}^{(k)}}{P_{n}}=\frac{\partial
G_{k}}{\partial w}(1/4,1/2)=9\frac{4^{k}}{(2+4^{k})^{2}}\,.$

###  7.3. Rooted binary plane trees

Now we study the rooted binary plane trees, these are rooted plane trees where
each node can only have 0 or 2 descendants. We can count these trees using
Lagrange’s equation with data $\psi(z)=1+z^{2}$.

The generating function for the rooted binary plane trees is

$\displaystyle B(z)=\sum_{n=0}^{\infty}C_{n}z^{2n+1},\quad\text{ for all
}|z|\leq 1/2,$

where $C_{n}$ denotes the $n$th Catalan number. The generating function for
the rooted binary trees with $\partial\geq k$ is

$\displaystyle
B_{k}(z)=G_{k}(z,B(z))=\sum_{n=1}^{\infty}B_{n}^{(k)}z^{2n+1},\quad|z|\leq
1/2.$

Now we write

$\displaystyle G(z,w)=zw^{2},\quad\text{ for all }|z|\leq 1/2,|w|\leq 1.$

We can find a closed expression for the iterate $G_{k}(z,w)$. This is the
content of the following lemma.

######  Lemma 7.3.

For any $k\geq 0$, we have

$\displaystyle G_{k}(z,w)=z^{2^{k}-1}w^{2^{k}},\quad\text{ for all }|z|\leq
1/2,|w|\leq 1.$

Using the previous Lemma we conclude that the partial derivatives of
$G_{k}(z,w)$ are given by

(7.8) $\displaystyle\frac{\partial G_{k}}{\partial
z}(z,w)=(2^{k}-1)z^{2^{k}-1}w^{2^{k}},\quad\frac{\partial G_{k}}{\partial
w}(z,w)=2^{k}z^{2^{k}-1}w^{2^{k}-1}.$

In this particular case we also have an explicit formula for the generating
function of the rooted binary plane trees with $\partial_{root}\geq k$.

######  Corollary 7.4.

For $k\geq 0$ we have

(7.9) $\displaystyle
B_{k}(z)=G_{k}(z,B(z))=z^{2^{k}-1}B(z)^{2^{k}},\quad\text{ for all
}\text{\vspace{.1 cm} }|z|\leq 1/2.$

Using this representation, we can give an exact formula for the coefficients
of $B_{k}(z)$. Later on, using this concrete formula, we give an asymptotic
formula for the coefficients $B_{n}^{(k)}$.

For any $n=2m+1$, for $m$ large enough, we have

(7.10)
$\displaystyle\begin{split}\textsc{coeff}_{[2m+1]}\left[B_{k}(z)\right]&=\textsc{coeff}_{[2m-2^{k}+2]}\left[B(z)^{2^{k}}\right]\\\
&=\frac{2^{k}}{2m-2^{k}+2}\textsc{coeff}_{[2m-2^{k+2}+2]}\left[(1+z^{2})^{2m-2^{k}+2}\right]\\\
&=\frac{2^{k}}{2m-2^{k}+2}{2m-2^{k}+2\choose m-2^{k}+1}\sim
2^{k-2^{k}+1}\frac{4^{m}}{\sqrt{\pi}m^{3/2}},\quad\text{ as
}m\rightarrow\infty.\end{split}$

The asymptotic formula (3.1) gives that

(7.11)
$\displaystyle\textsc{coeff}_{[2m+1]}\left[B(z)\right]=C_{m}=\frac{1}{m}{2m\choose
m}\sim\frac{4^{m}}{\sqrt{\pi}m^{3/2}},\quad\text{ as }m\rightarrow \infty.$

The following Theorem follows combining formulas (7.10) and (7.11). This
result is also a direct consequence of Theorem 6.3.

######  Theorem 7.5.

For any integer $k\geq 0$ and $n\geq 1$ odd we have

$\displaystyle\lim_{\begin{subarray}{c}n\to\infty;\\\
n\in\mathbb{N}_{1,2}\end{subarray}}\frac{\,\,\,\,B_{n}^{(k)}}{B_{n}}=\frac{\partial
G_{k}}{\partial w}(1/2,1)=2^{k-2^{k}+1}\,.$

##  8\. Mean number of nodes with $\partial_{v}\geq k$ in a Cayley tree

For the family of unrooted labeled Cayley trees, and following a circle of
ideas appearing in [1], we study the mean number of nodes which are at
distance to the border bigger or equal than $k$, as the number of nodes
$n\rightarrow\infty$.

Recapitulating, for a given tree $T$, and for any integer $k\geq 0$, a node
$v\in\text{nodes}(T)$ is at distance to the border bigger or equal than $k$ if

$\partial_{v}\triangleq\min_{u\in\text{leaves}(T)}d(u,v)\geq k.$

We denote by $\mathcal{U}_{n}$ the class of unrooted labeled Cayley trees. The
nodes of each of the trees in this family can be distinguished by its labels,
therefore, for each tree in $\mathcal{U}_{n}$ there are $n$ rooted labeled
Cayley trees. In particular, the number of unrooted labeled Cayley trees is
given by the sequence $U_{n}=n^{n-2}$.

Let $X_{n,k}$ be the random variable that, for any tree $T\in\mathcal{U}_{n}$,
counts the number of nodes $v$ with distance to the border $\partial_{v}\geq
k$, then we have

$\displaystyle
X_{n,k}(T)=\sum_{u\in\text{nodes}(T)}\textbf{1}_{\\{\partial_{u}\geq k\\}}.$

Following [1], we consider a 0-1 matrix $M$ of size $n\times n^{n-2}$. We
label the columns of this matrix with the collection of trees in
$\mathcal{U}_{n}=\\{t_{1},t_{2},\dots\\}$, and then the rows with the labels
of each node, that is, $\\{1,2,\dots,n\\}$. We write $1$ in the $(j,t_{j})$
entry if the node $j$ is at distance to the border bigger or equal than $k$
and 0 otherwise.

By adding all the entries of $M$ and then dividing by $n^{n-1}$ we obtain the
mean value of the random variable $X_{n,k}$, that is,

$\displaystyle\mathbb{E}_{n}(X_{n,k})=\frac{1}{n^{n-1}}\sum_{T\in\,\mathcal{U}_{n}}X_{n,k}(T).$

For any integer $k\geq 0$, and using the notation

$\displaystyle c_{k}=\lim_{n\rightarrow\infty}t_{n}^{(k)}/t_{n}\,,$

we obtain the following result.

######  Theorem 8.1.

As $n\rightarrow\infty$, the expectation of the proportion of nodes in a
labeled Cayley tree with $n$ nodes that are at distance bigger or equal than
$k$ from any leaf tends to $c_{k}$, that is,

$\displaystyle\lim_{n\rightarrow\infty}\frac{1}{n}\mathbb{E}_{n}(X_{n,k})=c_{k}\,.$

Equivalently,

$\displaystyle\mathbb{E}_{n}(X_{n,k})\sim c_{k}\cdot n,\quad\text{ as
}n\rightarrow\infty\,.$

This same result is true for any subclass of rooted labeled Cayley trees with
exponential generating function given by Lagrange’s equation with data
$\psi(z)=\sum_{j\geq 0}(b_{j}/j!)z^{j}\in\mathcal{K}^{\star}$, where
$b_{j}\in\\{0,1\\}$, for all $j\in\\{0,1,\dots\\}$, and total size
$n\in\mathbb{N}_{1,Q_{\psi}}$.

Finally, for the unrooted labeled unary Cayley trees, that is, the family of
trees given by $\psi(z)=1+z\in\mathcal{K}$, we have

$\displaystyle\mathbb{E}_{n}(X_{n,k})\sim n,\quad\text{ as
}n\rightarrow\infty\,.$

Some particular cases of Theorem 8.1 appear in [1], there the authors prove
the previous result for nodes $v$ with $\partial_{v}\geq 3$, see Theorem 3.7
in [1, p. 314].

## References

  * [1] Aramayona. J, Fernández. J. L., Fernández. P, Martínez-Pérez. C.: Trees, homology, and automorphism groups of RAAGs.  J. Algebr. Comb., 50, 293–315 (2019). https://doi.org/10.1007/s10801-018-0854-y
  * [2] Bóna, M.: $k$-protected vertices in binary search trees. Adv. in App. Math. 53, 1–11 (2014). https://doi.org/10.1016/j.aam.2013.09.003
  * [3] Cantón, A., Fernández, J. L., Fernández, P. and Maciá, V.: Khinchin families and Hayman class, Computational Methods and Function Theory, 21, 851–904 (2021). https://doi.org/10.1007/s40315-021-00420-6
  * [4] Cantón, A., Fernández, J. L., Fernández, P. and Maciá, V.: Khinchin families, set construction and exponentials, preprint.
  * [5] Cheon, G. and Shapiro, L.: Protected points in ordered trees. Appl. Math. Lett., 21, 516-520 (2008). http://dx.doi.org/10.1016/j.aml.2007.07.001
  * [6] de Bruijn, N.G, Knuth, D.E, Rice, S.O.: The average height of planted plane trees. Graph theory and Computing, (pp. 15 - 22). London Academic Press, January 1972. https://doi.org/10.1016/B978-1-4832-3187-7.50007-6
  * [7] Fernández, J. L. and Maciá, V.: Khinchin families and Large Powers,  arXiv:2201.11746.
  * [8] Fernández, J. L. and Maciá, V.: Khinchin families, Lagrangian distributions and Random trees, in preparation.
  * [9] Flajolet. P, Gao. Z, Odlyzco. A, Richmond. B.: The distribution of Heights of Binary Trees and Other Simple Trees Combinatorics, Probability and Computing, 2, 145– 156), (1993). https://doi.org/10.1017/S0963548300000560
  * [10] Flajolet, P, Odlyzko, A.: The Average Height of Binary Trees and Other Simple Trees. Journal of Computer and System Sciences, 25, 171–213 (1982). https://doi.org/10.1016/0022-0000(82)90004-6
  * [11] Flajolet, P. and Sedgewick, R.: Analytic combinatorics. Cambridge University Press, 2009. https://doi.org/10.1017/CBO9780511801655
  * [12] Gittenberger, B. Glebiewski, Z. Larcher, I. and Sulkowska, M.: Protection numbers in simply generated trees and Poĺya trees. Applicable Analysis and Discrete Mathematics (2021). http://dx.doi.org/10.2298/AADM190329010G
  * [13] Heuberger, C. and Prodinger, H.: Protection number in plane trees. Applicable Analysis and Discrete Mathematics (2017). https://doi.org/10.2298/AADM1702314H
  * [14] Sokal, Alan D. A ridiculously simple and explicit implicit function theorem Séminaire Lotharingien de Combinatoire 61A (2009): B61Ad, electronic only. http://eudml.org/doc/222589.
  * [15] Meir, A., Moon, J.W.: On the Altitude of Nodes in Random Trees, Can. J. Math., 30 (1978), 997–1015. https://doi.org/10.4153/CJM-1978-085-0
  * [16] Meir, A., Moon, J.W.: Some asymptotic results useful in enumeration problems. Aeq. Math., 33, 260–268 (1987). https://doi.org/10.1007/BF01836167
  * [17] Meir, A., Moon, J. W.: Packing and Covering Constants for Certain Families of Trees I. Journal of Graph Theory, 1, 157–174 (1977). https://doi.org/10.1002/jgt.3190010211
  * [18] Neveu, J.: Arbres et processus de Galton-Watson. Annales de l’I.H.P. Probabilités et statistiques, 22, 199-207 (1986). http://www.numdam.org/item/?id=AIHPB_1986__22_2_199_0
  * [19] Otter, R.: The Multiplicative Process. The Annals of Mathematical Statistics, 20 no. 2, 206–224 (1949). https://doi.org/10.1214/aoms/1177730031
  * [20] Pitman, J.: Enumerations Of Trees And Forests Related To Branching Processes And Random Walks. Microsurveys in Discrete Probability: DIMACS Workshop (1997). https://statistics.berkeley.edu/tech-reports/482
  * [21] Pitman, J.: Combinatorial stochastic processes. Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour. Springer-Verlag (2006). https://doi.org/10.1007%2fb11601500
  * [22] Polya, G. Szegö, G.: Problems and Theorems in Analysis I, Springer, Berlin, Heidelberg, (1999). https://doi.org/10.1007/978-3-642-61983-0
  * [23] Rényi. A, Szekeres. G.: On the height of trees. Journal of the Australian Mathematical Society, (pp. 497 - 507), November 1967. https://doi.org/10.1017/S1446788700004432
  * [24] Williams, D.: Probability with Martingales. Cambridge University Press. (1991). doi:10.1017/CBO9780511813658