# Protection numbers in simply generated trees and Pólya trees

Bernhard Gittenberger, Zbigniew Gołębiewski,
Isabella Larcher, and Małgorzata Sulkowska  Department of Discrete Mathematics
and Geometry, Technische Universität Wien, Wiedner Hauptstraße 8-10/104,
A-1040 Wien, Austria<EMAIL_ADDRESS>Department of Computer
Science, Wrocław University of Science and Technology, ul. Wybrzeze
Wyspianskiego 27, 50-370, Wrocław, Poland<EMAIL_ADDRESS>Department of Discrete Mathematics and Geometry, Technische Universität Wien,
Wiedner Hauptstraße 8-10/104, A-1040 Wien, Austria.
<EMAIL_ADDRESS>Department of Computer Science, Wrocław
University of Science and Technology, ul. Wybrzeze Wyspianskiego 27, 50-370,
Wrocław, Poland<EMAIL_ADDRESS>
###### Abstract.

We determine the limit of the expected value and the variance of the
protection number of the root in simply generated trees, in Pólya trees, and
in unlabelled non-plane binary trees, when the number of vertices tends to
infinity. Moreover, we compute expectation and variance of the protection
number of a randomly chosen vertex in all those tree classes. We obtain exact
formulas as sum representations, where the obtained sums are rapidly
converging and therefore allowing an efficient numerical computation of high
accuracy. Most proofs are based on a singularity analysis of generating
functions.

This research has been supported by the ÖAD, grant PL04-2018, and Wroclaw
Univeristy of Science and Technology grant 0401/0052/18. The first and third
author have also been supported by the Austrian Science Fund (FWF), grant SFB
F50-03.

##  1\. Introduction

The protection number of a tree is the length of the shortest path from the
root to a leaf. It is interchangeably called the protection number of a root.
We define the protection number of a vertex $v$ in tree $T$ as the protection
number of a maximal subtree of $T$ having $v$ as a root. We say that a vertex
is $k$-protected if $k$ does not exceed its protection number.

10210100100 Figure 1. Tree with vertices holding their protection numbers.

Previous research concerning protection numbers has been conducted in two
closely related directions: (i) a number of $k$-protected vertices in a tree
of size $n$, and (ii) the protection number of a root or a random vertex.

Cheon and Shapiro [4] were the first ones to investigate the number of
$2$-protected nodes in trees. They stated the results for unlabelled ordered
trees and Motzkin trees. Later on Mansour [23] complemented their work by
solving $k$-ary tree case. Over the next several years these results were
followed by a series of papers examining the number of $k$-protected nodes
(usually for small values of $k$) in various models of random trees. To
mention just a few, Du and Prodinger [12] analysed the average number of
$2$-protected nodes in random digital search trees, Mahmoud and Ward [21]
presented a central limit theorem as well as exact moments of all orders for
the number of $2$-protected nodes in binary search trees and three years later
they found the number of $2$-protected nodes in recursive trees (consult
[22]). The family of binary search trees was investigated also by Bóna and
Pittel [3] who showed that the number of its $k$-protected nodes decays
exponentially in $k$.

In 2015 Holmgren and Janson [19] went for more general results. Using
probabilistic methods, they derived a normal limit law for the number of
$k$-protected nodes in a binary search tree and a random recursive tree.

Soon after, two particular parameters attracted attention of the algorithmic
community. These were (as already mentioned earlier) the protection number of
the root and the protection number of a random vertex. In 2017 Copenhaver [5]
found that in a random unlabelled plane tree the expected value of the
protection number of the root and the expected value of the protection number
of a random vertex approach $1.62297$ and $0.727649$, respectively, as the
size of the tree tends to infinity. These results were extended by Heuberger
and Prodinger [18]. They showed the exact formulas for the first terms of the
expectation, the variance and the probability of the respective protection
numbers.

The protection number of a root is closely related to parameters called
minimal fill-up level and saturation level. These were studied previously by,
among others, Devroye [7] and Drmota [9, 10].

The aim of this paper is to generalize the protection number results to a
larger class of rooted trees. We study both the root protection number as well
as a random vertex protection number for the family of simply generated trees
(introduced by Meir and Moon [24]) and their non-plane counterparts:
unlabelled non-plane rooted trees, also called Pólya trees due to their first
extensive treatment by Pólya [27], examined further by Otter [25] including
numerical results and the binary case. The present paper broadens the results
from [18], but maintaining the emphasis on as concrete formulas as possible.

For simply generated trees a general theory of asymptotics of certain
functional was developed recently in [6], but this theory does not cover local
functionals as the number of protected nodes. Devroye and Janson [8] presented
a unified approach to obtaining the number of $k$-protected nodes in various
classes or random trees by putting them in the general context of fringe
subtrees introduced by Aldous in [2]. We have obtained analogous results for
simply generated trees, but employing a different methodology. This allows an
efficient numerical treatment and may serve as a basis for random generation
in the framework of Boltzmann sampling [13]. Parts of our investigations fall
into the general framework of additive functionals treated in [28], but our
focus on concrete expressions allows an easy access to numerical evaluation of
the considered parameters.

### Plan of the paper

In Sections 2, 3, and 4 we consider simply generated trees, Pólya trees and
non-plane binary trees, respectively. In each section the expected value and
the variance of the protection number of the root and the protection number of
a random vertex are computed. All these quantities tend to constants when the
tree size tends to infinity. The emphasis is on deriving exact expressions for
these constants in terms of characteristic parameters of the considered tree
class. We obtain them in terms of sums that converge at an exponential rate
and therefore enable us to compute efficiently accurate numerical values. We
provide numerical values for the several well-known simply generated tree
classes as well as for the two non-plane classes studied in Sections 3 and 4.

##  2\. Simply generated trees

###  2.1. Protection number of the root

The class $\mathcal{T}$ of simply generated trees was introduced in [24] and
can be described as the class of plane rooted trees whose generating function
satisfies a function equation of particular type: If $t_{n}$ denotes the sum
of the weights of all trees with $n$ vertices, then the generating function
$T(z)=\sum_{n\geq 0}t_{n}z^{n}$ satisfies

$\displaystyle T(z)=z\phi(T(z)),$

where the power series $\phi(t)=\sum_{j\geq 0}\phi_{j}t^{j}$ has only non-
negative coefficients, $\phi_{0}>0$, and there is a $j\geq 2$ such that
$\phi_{j}>0$. Moreover, it is required that the equation
$\tau\phi^{\prime}(\tau)=\phi(\tau)$ has a unique positive solution.

We are interested in the asymptotic protection number of a random simply
generated tree, sampled according to the weights from all simply generated
trees with $n$ vertices, where $n$ tends to infinity.

######  Remark .

For the sake of simplicity we assume that $\phi$ is non-periodic, meaning that
there are integers $i,j,k$ such that $\phi_{i},\phi_{j},\phi_{k}$ are all
positive and satisfy $\gcd(\phi_{j}-\phi_{i},\phi_{k}-\phi_{i})=1$. The
periodic case can be dealt with in the very same way, but the calculations
leading to the desired number have to be done repeatedly (for analogous
situations) in order collect several contributions to the final value.

Within this paper the primary tool that is used will be singularity analysis
(see [15, 16]), which provides a direct connection between the singularities
of a generating function and the asymptotic behaviour of its coefficients. By
Pringsheim’s theorem [16, p. 240] we know that a generating function must have
a singularity at $z=R$, if $R$ denotes the radius of convergence. Our
assumption that $\phi$ is non-periodic guarantees furthermore that this is the
only singularity on the circle of convergence. Throughout this paper we will
call $z=R$ the _dominant singularity_ of the generating function. In
particular, we denote the dominant singularity of $T(z)$ by $\rho$.
Furthermore, we say that a function $f$ has an algebraic singularity of type
$\alpha$ at $s$, if there is a constant $C$ such that $f(z)\sim
f(s)+C\cdot(1-\frac{z}{s})^{\alpha}$ as $z$ tends to $s$ in such a way that
$z-s\notin\mathbb{R}^{+}$. In this case $f$ admits a Puiseux expansion in
terms of powers $(1-\frac{z}{s})^{\alpha/k}$ for some positive integer $k$.
For instance, it is well known that the generating function $T(z)$ associated
to some class of simply generated trees has an algebraic singularity $\rho$ of
type 1/2 (for obvious reasons also called square root singularity) the
location of which is determined by the system $T(\rho)=\rho\phi(T(\rho))$,
$1=\rho\phi^{\prime}(T(\rho))$, _cf._ [10]. For further information on this
theory we refer the reader to [16] and [15].

Let $T_{k}(z)$ denote the generating function of the class of simply generated
trees that have protection number at least $k$, where $z$ marks the total
number of nodes. Furthermore, let $\phi(T)$ be non-periodic. Then, $T_{k}(z)$
can be defined by

$\displaystyle T_{k}(z)=z\left(\phi(T_{k-1}(z))-\phi_{0}\right).$ (1)

Note that $T_{0}(z)=T(z)$.

######  Lemma 1.

All generating functions $T_{k}(z)$ have the same dominant singularity as
$T(z)$, and it is a square root singularity.

###### Proof.

First let us consider that the generating function $T_{k}(z)$ reads as

$\displaystyle T_{k}(z)=\Omega^{k}(T(z))$

where $\Omega(t)=z\phi(t)-z\phi_{0}$ and $\Omega^{k}(\cdot)$ denotes the
$k$-fold composition. Since $\Omega(t)$ is analytic at $T(\rho)$, inserting a
function admitting a Puiseux expansion
$t(z)=\alpha_{0}+\alpha_{1}\sqrt{1-\frac{z}{\rho}}+\dots$ results in

$\Omega(t(z))=\Omega(\alpha_{0})+\Omega^{\prime}(\alpha_{0})\alpha_{1}\sqrt{1-\frac{z}{\rho}}+\dots,$

again being a Puiseux expansion at $z=\rho$. It is well known that $T(z)$
admits a Puiseux expansion $\tau_{0}+\tau_{1}\sqrt{1-\frac{z}{\rho}}+\dots$
with nonzero numbers $\tau_{0}$ and $\tau_{1}$. Moreover, we always insert one
of the functions $T_{k}(z)$, thus $\alpha_{0}$ attains the positive values
$T_{k}(\rho)$, $k=0,1,2,\dots$, implying that $\Omega^{\prime}(\alpha_{0})$ is
always positive, as $\Omega(t)$ is a power series with only non-negative
coefficients. By induction it is guaranteed that $\alpha_{1}$ is always
negative and thus all the function $T_{k}(z)$ have a unique dominant
singularity of square root type at $z=\rho$. ∎

In order to derive the expected value of the protection number $X_{n}$ of a
random simply generated tree of size $n$ (i.e. with $n$ nodes) asymptotically,
we use the well known formula

$\displaystyle\mathbb{E}X_{n}=\sum_{k\geq 1}\mathbb{P}(X_{n}\geq k).$ (2)

Thus, we need to calculate the probability $\mathbb{P}(X_{n}\geq k)$, which is
given by

$\displaystyle\mathbb{P}(X_{n}\geq k)=\frac{[z^{n}]T_{k}(z)}{[z^{n}]T(z)}.$

######  Theorem 1.

Let $X_{n}$ be the protection number of a random simply generated tree of size
$n$. Then the expected value $\mathbb{E}X_{n}$ and the variance
$\mathbb{V}X_{n}$ satisfy

$\displaystyle\lim_{n\to\infty}\mathbb{E}X_{n}=\sum_{k\geq
1}\rho^{k-1}\prod_{i=1}^{k-1}\phi^{\prime}(T_{i}(\rho)),$

and

$\displaystyle\lim_{n\to\infty}\mathbb{V}X_{n}=\sum_{k\geq
1}(2k-1)\rho^{k-1}\prod_{i=1}^{k-1}\phi^{\prime}(T_{i}(\rho))-\left(\lim_{n\to\infty}\mathbb{E}X_{n}\right)^{2}.$

with $\rho$ denoting the dominant singularity of the generating function
$T(z)=z\phi(T(z))$ of the class of simply generated trees.

###### Proof.

We know that the asymptotic behaviour of the generating function, namely
$T(z)=\tau_{0}+\tau_{1}\sqrt{1-\frac{z}{\rho}}+\tau_{2}(1-\frac{z}{\rho})+\ldots$,
implies

$\displaystyle[z^{n}]T(z)\sim-\tau_{1}\frac{n^{-3/2}}{\Gamma(-1/2)}\rho^{-n},$
(3)

as $n$ tends to infinity. In order to derive the asymptotics of the $n$-th
coefficient of $T_{k}(z)$, observe that we know from Lemma 1 that all
generating functions $T_{i}(z)$ have the same dominant singularity $\rho$ of
type $\frac{1}{2}$. Setting $\eta=\sqrt{1-\frac{z}{\rho}}$, the Puiseux
expansions of $T_{k}(z)$ and $T_{k-1}(z)$ read as

$\displaystyle T_{k}(z)=\tau_{0,k}+\tau_{1,k}\eta+\tau_{2,k}\eta^{2}+\ldots.$

and

$\displaystyle
T_{k-1}(z)=\tau_{0,k-1}+\tau_{1,k-1}\eta+\tau_{2,k-1}\eta^{2}+\ldots.$

Plugging these expansions into (1) and using $z=\rho(1-\eta^{2})$ we get

$\displaystyle\tau_{0,k}+\tau_{1,k}\eta+\tau_{2,k}\eta^{2}+\ldots=\rho(1-\eta^{2})\left(\sum_{j\geq
0}\phi_{j}\left(\tau_{0,k-1}+\tau_{1,k-1}\eta+\tau_{2,k-1}\eta^{2}+\ldots\right)^{j}-\phi_{0}\right).$

Expanding and comparing coefficients of $\eta^{0}$ and $\eta^{1}$ yields

$\displaystyle[\eta^{0}]$
$\displaystyle:\tau_{0,k}=\rho\phi(\tau_{0.k-1})-\rho\phi_{0},$
$\displaystyle[\eta^{1}]$ $\displaystyle:\tau_{1,k}=\rho\sum_{j\geq
0}\phi_{j}j\tau_{1,k-1}\tau_{0,k-1}^{j-1}.$

Obviously, the $\tau_{0,i}$’s match exactly the $T_{i}(\rho)$, $i\geq 0$, as
they are the constant terms in the Puiseux expansions of the functions
$T_{i}(z)$, with $0\leq i\leq k$. Thus, the equation for $\tau_{1,k}$ can be
rewritten as $\tau_{1,k}=\rho\tau_{1,k-1}\phi^{\prime}(T_{k-1}(\rho))$.

As $\tau_{1,0}=\tau_{1}$, we get

$\displaystyle\tau_{1,k}=\tau_{1}\rho^{k-1}\prod_{i=1}^{k-1}\phi^{\prime}(T_{i}(\rho)).$

Applying a transfer lemma [15] directly gives the asymptotics of the
coefficients of $T_{k}(z)$ and plugging them in conjunction with (3) into
Equation (2) yields the asymptotic value for the mean. In order to derive the
formula for the asymptotic variance we use the equation

$\displaystyle\mathbb{V}X_{n}=\mathbb{E}(X_{n}^{2})-(\mathbb{E}X_{n})^{2}\quad\text{
and }\quad\mathbb{E}(X_{n}^{2})=\sum_{k\geq 1}(2k-1)\mathbb{P}(Y_{n}\geq k)$

and immediately get the asserted result. ∎

It is easy to see that the sequence $(T_{i}(\rho))_{i\geq 0}$ is monotonically
decreasing, since the number of trees with protection number at least $i$ is
always greater than the number of trees that have an $(i+1)$-protected root,
i.e. protection number at least $i+1$. Since $\phi^{\prime}$ is monotonically
increasing on the positive real axis, this implies that
$\rho\phi^{\prime}(T_{i}(\rho))\leq\rho\phi^{\prime}(T_{1}(\rho))<\rho\phi^{\prime}(T(\rho))=1.$
Thus, we can estimate the sum for the expected value by

$\displaystyle\lim_{n\to\infty}\mathbb{E}X_{n}=\sum_{k\geq
1}\prod_{i=1}^{k-1}\left(\rho\phi^{\prime}(T_{i}(\rho))\right)<\sum_{k\geq
1}(\rho\phi^{\prime}(T_{1}(\rho)))^{k-1},$

which converges, since $\rho\phi^{\prime}(T_{1}(\rho))<1$. As the last sum is
a convergent geometric series and the inequality even holds term-wise, we can
calculate efficiently the asymptotic mean and variance for all classes of
simply generated trees with arbitrary accuracy. We will now exemplify this by
calculating the limits of mean and variance of the protection number of some
prominent classes of simply generated trees.

######  Example  (Plane trees).

The generating function $C(z)$ of plane trees is the unique power series
solution of

$\displaystyle C(z)=z\frac{1}{1-C(z)},$

which yields

$\displaystyle C(z)=\frac{1}{2}-\sqrt{\frac{1}{4}-z}.$ (4)

Thus, its dominant singularity is $\rho=\frac{1}{4}$, and
$C(\rho)=\frac{1}{2}$.

The recursion for the $T_{i}(\rho)$’s reads as

$\displaystyle T_{1}(\rho)=\frac{1}{4},\qquad
T_{i}(\rho)=\frac{1}{4-4T_{i-1}(\rho)}-\frac{1}{4}.$

In case of plane trees the recursion can be solved explicitly, leading to

$\displaystyle T_{i}(\rho)=\frac{3}{2(4^{i}+2)}.$

The limits of expected value and variance are therefore given by

$\displaystyle\lim_{n\to\infty}\mathbb{E}X_{n}=\sum_{k\geq
1}\frac{1}{4^{k-1}}\prod_{i=1}^{k-1}\frac{1}{\left(1-\frac{3}{2(4^{i}+2)}\right)^{2}}\approx
1.622971384715353,$

and

$\displaystyle\lim_{n\to\infty}\mathbb{V}X_{n}=\sum_{k\geq
1}(2k-1)\frac{1}{4^{k-1}}\prod_{i=1}^{k-1}\frac{1}{\left(1-\frac{3}{2(4^{i}+2)}\right)^{2}}-\left(\lim_{n\to\infty}\mathbb{E}X_{n}\right)^{2}\approx
0.7156950717833327,$

which has already been calculated by Heuberger and Prodinger in [18].

######  Example  (Motzkin trees).

The generating function $M(z)$ of Motzkin trees is defined by

$\displaystyle M(z)=z\left(1+M(z)+M(z)^{2}\right),$

which can be solved to result in

$\displaystyle M(z)=\frac{1-z-\sqrt{1-2z-3z^{2}}}{2z}.$

Thus, its dominant singularity is $\rho=\frac{1}{3}$ and $M(\rho)=1$.

The recursion for the $T_{i}(\rho)$’s reads as

$\displaystyle T_{1}(\rho)=\frac{2}{3},\qquad
T_{i}(\rho)=\frac{1}{3}\left(T_{i-1}(\rho)^{2}+T_{i-1}(\rho)\right)$

This recursion can be transformed into another one for the numerators of the
rational numbers $T_{i}(\rho)$: Indeed, if we write $T_{i}(\rho)=A_{i}\cdot
3^{-2^{i}+1}$, then $A_{1}=2$ and $A_{i}=A_{i-1}^{2}+3^{2^{i-1}-1}\cdot
A_{i-1}$, for $i\geq 2$. The recurrence for the $A_{i}$’s does not fall into
the scheme of Aho and Sloane [1] and we are not aware of any method to solve
it explicitly. But as stated before, the sequence $(T_{i}(\rho))_{i\geq 1}$ is
exponentially decreasing and estimates are easily obtained. Thus we can
calculate the limits of mean and variance for the protection number
numerically with arbitrary accuracy:

$\displaystyle\lim_{n\to\infty}\mathbb{E}X_{n}\approx
2.546378248338912,\qquad\lim_{n\to\infty}\mathbb{V}X_{n}\approx
1.679348871220563.$

######  Example  (Incomplete binary trees).

The generating function $I(z)$ of incomplete binary trees is defined by

$\displaystyle I(z)=z\left(1+2I(z)+I(z)^{2}\right),$

which gives

$\displaystyle I(z)=\frac{1-2z-\sqrt{1-4z}}{2z}.$

The dominant singularity is therefore at $\rho=\frac{1}{4}$ and $I(\rho)=1$.

The recursion for the $T_{i}(\rho)$’s reads as

$\displaystyle T_{1}(\rho)=\frac{3}{4},\qquad
T_{i}(\rho)=\frac{1}{4}(T_{i-1}(\rho)^{2}+2T_{i-1}(\rho)).$

This recursion cannot be solved explicitly, but the numerical values can be
easily computed: They are

$\displaystyle\lim_{n\to\infty}\mathbb{E}X_{n}\approx
3.536472483525321,\qquad\lim_{n\to\infty}\mathbb{V}X_{n}\approx
3.763883442795153.$

######  Example  (Cayley trees).

Though, in a strict sense, Cayley trees do not belong to the class of simply
generated trees (_cf._ the discussions in [20] and [17]), they are usually
listed as an example for that class. In fact, they are closely related (see
[26] for a thorough analysis and [17] for an analysis of the differences) and
in many contexts (like the one considered here), quotients of coefficients are
computed which makes the fact that in this case the generating functions are
exponential ones irrelevant.

The (exponential) generating function $C(z)$ of Cayley trees is defined by

$\displaystyle C(z)=ze^{C(z)},$

which has its dominant singularity at $\rho=\frac{1}{e}$. Moreover, we have
$C(\rho)=1$.

The recursion for the $T_{i}(\rho)$’s reads as

$\displaystyle T_{1}(\rho)=1-\frac{1}{e},\qquad
T_{i}(\rho)=\frac{1}{e}(e^{T_{i-1}(\rho)}-1).$

As in the two previous examples the recursion for the $T_{i}(\rho)$’s cannot
be solved explicitly, but the numerical values are

$\displaystyle\lim_{n\to\infty}\mathbb{E}X_{n}\approx
2.286198316708012,\qquad\lim_{n\to\infty}\mathbb{V}X_{n}\approx
1.598472890455086.$

######  Example  (Binary trees).

This is the class of complete binary trees with only internal vertices
contributing to the size. The generating function is then defined by the
functional equation $B(z)=1+zB(z)^{2}$ with $B(z)=C(z)/z$ where $C(z)$ is the
function displayed in (4). Though this class does not strictly fall into the
simply generated framework, the functional equation is of the form
$B(z)-1=z\phi(B(z)-1)$, which reflects the fact that incomplete binary trees
with all nodes counted are in bijection to complete binary trees with only
internal vertices counted. For the protection number this causes some shifts
within the tree. But the methodology presented above works here as well. We
get $T_{0}(z)=B(z)$ and $T_{k}(z)=zT_{k-1}(z)^{2}.$ Since $\rho=1/4$ we have
$T_{k}(\rho)=2^{2-2^{k}}$, for all $k\geq 0$, and then finally
$\mathbb{P}(X_{n}\geq k)\to 2^{k+1-2^{k}}$, as $n$ tends to infinity. Thus we
obtain

$\displaystyle\lim_{n\to\infty}\mathbb{E}X_{n}\approx
1.562988296151161,\qquad\lim_{n\to\infty}\mathbb{V}X_{n}\approx
0.372985688954940.$

###  2.2. Protection number of a random vertex

In the first part of this section we studied the average protection number of
a simply generated tree, that is the protection number of the root of the
simply generated tree. Now we are interested in the average protection number
of a randomly chosen vertex in a simply generated tree of size $n$. We denote
this sequence of random variables by $Y_{n}$.

As in the previous section we calculate the mean via
$\mathbb{E}Y_{n}=\sum_{k\geq 1}\mathbb{P}(Y_{n}\geq k).$ In order to do so we
proceed analogously to Heuberger and Prodinger in [18] and define $S_{k}(z)$
to be the generating function of the sequence $(s_{n,k})_{n\geq 0}$ of
$k$-protected vertices summed over all trees of size $n$. As in [18] this
generating function can be calculated by

$\displaystyle S_{k}(z)=z^{-1}T_{k}(z)\frac{\partial}{\partial u}T(z,1),$ (5)

by means of the bivariate generating function $T(z,u)$ of simply generated
trees, where $z$ marks the size and $u$ the number of leaves, and the
generating function $T_{k}(z)$ of simply generated trees with protection
number at least $k$. The formula for $S_{k}(z)$ arises from considering a
$k$-protected vertex in the following way: First point at a leaf in a simply
generated tree (which yields the factor $\frac{\partial}{\partial u}T(z,1)$),
then remove this leaf (which explains the $z^{-1}$) and finally attach a tree
with protection number at least $k$ (giving the factor $T_{k}(z)$).

######  Remark .

The procedure works also for complete binary trees, where only internal
vertices contribute to the tree size. The only difference is that for complete
binary trees the factor $z^{-1}$ in (5) must be removed, because removing a
leaf does not change the size.

Using the generating function $S_{k}(z)$ we can express the probability
$\mathbb{P}(Y_{n}\geq k)$ by

$\displaystyle\mathbb{P}(Y_{n}\geq k)=\frac{[z^{n}]S_{k}(z)}{n[z^{n}]T(z)}.$
(6)

######  Theorem 2.

Let $Y_{n}$ be the protection number of a randomly chosen vertex in a random
simply generated tree of size $n$. Then,

$\displaystyle\lim_{n\to\infty}\mathbb{E}Y_{n}=\frac{\phi_{0}}{T(\rho)}\sum_{k\geq
1}T_{k}(\rho),$

and

$\displaystyle\lim_{n\to\infty}\mathbb{V}Y_{n}=\frac{\phi_{0}}{T(\rho)}\sum_{k\geq
1}(2k-1)T_{k}(\rho)-\left(\lim_{n\to\infty}\mathbb{E}Y_{n}\right)^{2}.$

###### Proof.

First we need to determine the $n$-th coefficient of $S_{k}(z)$. We have

$\displaystyle\frac{\partial}{\partial
u}T(z,1)=\frac{z\phi_{0}}{1-z\phi^{\prime}(T(z))}.$ (7)

Using $T^{\prime}(z)=z\phi^{\prime}(T(z))T^{\prime}(z)+\phi(T(z))$ and
$\phi(T(z))=\frac{T(z)}{z}$ we get

$\displaystyle
z\phi^{\prime}(T(z))=\frac{T^{\prime}(z)-\frac{T(z)}{z}}{T^{\prime}(z)}.$

Therefore (7) transforms to

$\displaystyle\frac{\partial}{\partial
u}T(z,1)=\frac{T^{\prime}(z)z^{2}\phi_{0}}{T(z)}.$

Thus, altogether we have

$\displaystyle[z^{n}]S_{k}(z)=[z^{n}]z^{-1}T_{k}(z)\frac{T^{\prime}(z)z^{2}\phi_{0}}{T(z)},$

which gives

$\displaystyle[z^{n}]S_{k}(z)\sim\frac{-\tau_{0,k}\tau_{1}\phi_{0}}{2\tau_{0}}\frac{n^{-1/2}}{\Gamma(1/2)}\rho^{-n}.$

Finally, we get

$\displaystyle\mathbb{E}Y_{n}$ $\displaystyle=\sum_{k\geq
1}\mathbb{P}(Y_{n}\geq k)=\sum_{k\geq
1}\frac{[z^{n}]S_{k}(z)}{n[z^{n}]T(z)}\overset{n\to\infty}{\to}\sum_{k\geq
1}\frac{T_{k}(\rho)\phi_{0}}{T(\rho)}.$

For the variance we use again the formula $\mathbb{V}Y_{n}=\sum_{k\geq
1}(2k-1)\mathbb{P}(Y_{n}\geq k)-\mathbb{E}(Y_{n})^{2}$ and (6). ∎

| $\lim_{n\to\infty}\mathbb{E}Y_{n}$ | $\lim_{n\to\infty}\mathbb{V}Y_{n}$
---|---|---
Plane trees | 0.7276492769137261 | 0.8168993794836289
Motzkin trees | 1.307604625963334 | 1.730614214799486
Incomplete binary trees | 1.991819588602741 | 3.638259051495130
Cayley trees | 1.186522661652180 | 1.632206223956926
Complete binary trees | 1.265686036087572 | 0.226591112528581
Table 1. The approximate values for the limits of mean and variance of the
protection number of a random vertex in different classes of simply generated
trees.

##  3\. Pólya trees

###  3.1. Protection number of the root

Let $T(z)$ be the generating function of Pólya trees, which reads as

$\displaystyle T(z)=ze^{T(z)}\exp\left(\sum_{i\geq
2}\frac{T(z^{i})}{i}\right),$

and in correspondence to the previous section let us denote by $T_{k}(z)$ the
generating function of the class of Pólya trees that have protection number at
least $k$. This generating function can be specified by

$\displaystyle T_{k}(z)=ze^{T_{k-1}(z)}\exp\left(\sum_{i\geq
2}\frac{T_{k-1}(z^{i})}{i}\right)-z,$ (8)

with $T_{0}(z)=T(z)$. From the classical results of Pólya [27] we know that
$T(z)$ has a unique dominant singularity $\rho$ of type 1/2 and admits Puiseux
series expansion there, which starts as

$T(z)\sim
1-b\sqrt{1-\frac{z}{\rho}}+\frac{b^{2}}{3}\left(1-\frac{z}{\rho}\right)+d\left(1-\frac{z}{\rho}\right)^{3/2}+\cdots.$
(9)

Numerical approximations for the constants have been first computed by Otter
[25]. This was also topic in Finch [14, Section 5.6] and [16, p. 477] where we
find approximations up to 25 digits: $\rho\approx 0.3383218568992076951961126$
and $b\approx 1.55949002037464088554226$.

######  Lemma 2.

All the generating functions $T_{k}(z)$ have their (unique) dominant
singularity at $\rho$, and the singularity is a square root singularity.

###### Proof.

First let us recall that $T_{0}(z)=T(z)$. Thus, for $k=0$ the lemma is
trivial. For $k\geq 1$ we proceed by induction. Therefore let us assume that
$T_{k-1}(z)$ has the dominant singularity $\rho$ which is of type
$\frac{1}{2}$. Then the dominant singularity of $T_{k}(z)$, satifying the
recurrence relation (8), comes from $e^{T_{k-1}(z)}$, since
$\exp\left(\sum_{i\geq 2}\frac{T_{k-1}(z^{i})}{i}\right)$ is analytic in
$|z|<\rho+\epsilon$ with $\epsilon>0$ sufficiently small. Applying the
exponential function to a function having an algebraic singularity does
neither change the location nor the type of the singularity, which proves the
assertion after all. ∎

The goal of this section is to derive an asymptotic value for the average
protection number of Pólya trees. We use again the formula
$\mathbb{E}X_{n}=\sum_{k\geq 1}\mathbb{P}(X_{n}\geq k)$, but rewrite this
equation as

$\displaystyle\mathbb{E}X_{n}=\sum_{k\geq
1}\prod_{i=1}^{k}\mathbb{P}(X_{n}\geq k|X_{n}\geq k-1),$

where the conditional probabilities can be obtained by

$\displaystyle\mathbb{P}(X_{n}\geq k|X_{n}\geq
k-1)=\frac{[z^{n}]T_{k}(z)}{[z^{n}]T_{k-1}(z)}.$ (10)

######  Lemma 3.

The asymptotic expansions of the $n$-th coefficients of $T_{k}(z)$ and
$T_{k-1}(z)$ read as

$\displaystyle[z^{n}]T_{k-1}(z)$
$\displaystyle=\frac{\gamma_{k}\rho^{-n}n^{-\frac{3}{2}}}{\Gamma(-1/2)}\left(1+\mathcal{O}\left(\frac{1}{n}\right)\right),$
$\displaystyle[z^{n}]T_{k}(z)$
$\displaystyle=\frac{(T_{k}(\rho)+\rho)\gamma_{k}\rho^{-n}n^{-\frac{3}{2}}}{\Gamma(-1/2)}\left(1+\mathcal{O}\left(\frac{1}{n}\right)\right),$

as $n\to\infty$, with a constant $\gamma_{k}>0$.

###### Proof.

Let the Puiseux expansion of $T_{k-1}(z)$ be given by
$T_{k-1}(z)=T_{k-1}(\rho)-\gamma_{k}\sqrt{1-\frac{z}{\rho}}+\ldots$.

Then $T_{k}(z)$ behaves asymptotically as $T_{k}(z)\sim\rho
e^{T_{k-1}(\rho)}Q_{k-1}(\rho)e^{-\gamma_{k}\sqrt{1-\frac{z}{\rho}}},$ where
$Q_{k-1}(\rho)=\exp\left(\sum_{i\geq 2}\frac{T_{k-1}(\rho^{i})}{i}\right)$.
Applying the asymptotic relation $e^{-\gamma_{k}\sqrt{1-\frac{z}{\rho}}}\sim
1-\gamma_{k}\sqrt{1-\frac{z}{\rho}}$ and using the equation $\rho
e^{T_{k-1}(\rho)}Q_{k-1}(\rho)=T_{k}(\rho)+\rho$ completes the proof. ∎

Plugging the expansions obtained in Lemma 3 into Equation (10) gives

$\displaystyle\mathbb{P}(X_{n}\geq k|X_{n}\geq k-1)=T_{k}(\rho)+\rho,$

which directly yields the following theorem.

######  Theorem 3.

Let $X_{n}$ be the protection number of a random Pólya tree of size $n$. Then

$\displaystyle\lim_{n\to\infty}\mathbb{E}X_{n}=\sum_{k\geq
1}\prod_{i=1}^{k}(T_{k}(\rho)+\rho)\approx 2.154889671973873,$ (11)

and $\lim_{n\to\infty}\mathbb{V}X_{n}\approx 1.369993017502652.$

###### Proof.

The proof for the asymptotic mean follows directly by Lemma 3. In order to
determine the variance we use the representation
$\lim_{n\to\infty}\mathbb{V}X_{n}=\sum_{k\geq
1}(2k-1)\prod_{i=1}^{k}(T_{k}(\rho)+\rho)-\mathbb{E}(X_{n})^{2}$. ∎

######  Remark .

Note that in order to get accurate numerical values, we must not compute
$T_{k}(\rho)$ by insertion into a (truncated) series expansion for $T_{k}(z)$
The reason is that $\rho$ lies on the circle of convergence and thus the
convergence is very slow at $z=\rho$. Instead, $T_{k}(\rho)$ can be directly
computed using the recurrence relation (8). The values $T_{k}(\rho^{i})$ for
$i\geq 2$, which appear in that recurrence relation, can be computed with the
help of the series expansion of $T_{k}(z)$, because $\rho^{i}$ then lies in
the interior of region of convergence where the series converges at an
exponential rate.

######  Remark .

We could also have used the same approach as for simply generated trees in
order to get the asymptotic mean. Then the resulting formula looks like

$\displaystyle\lim_{n\to\infty}\mathbb{E}X_{n}=\sum_{k\geq
1}\rho^{k-1}\prod_{i=1}^{k-1}C_{i}e^{T_{i}(\rho)},$ (12)

where $C_{j}=\exp\left(\sum_{i\geq 2}\frac{T_{j}(\rho^{i})}{i}\right)$. One
can show that $C_{i}$ tends to 1 and and $T_{i}(\rho)$ tends to 0
exponentially fast and get the constant given in Theorem 3. However, since
this approach requires more technical calculations, we decided to switch to
the more direct strategy using the conditional probabilities. Moreover note
that the equivalence of (11) and (12) is immediate from (8).

###  3.2. Protection number of a random vertex

The method of marking a leaf and replacing it by a tree with protection number
$k$ does not work here. Due to possible symmetries in non-plane trees, this
would result in wrong counting: Indeed, if there are $k$-protected vertices
$x_{1},\dots,x_{\ell}$ which can be mapped to each other by some automorphisms
of the tree (_i.e._ , they lie in the same vertex class), then only one of
them is counted. Though this is counterbalanced by trees having $\ell$ leaves
in the same vertex class one of which is replaced by a tree with protection
number $k$ (the root of this tree is then counted $\ell$ times), there are
further overcounts: As all leaves are marked, trees having several leaves in
the same vertex class are counted several times, and so are their
$k$-protected vertices.

Thus we appeal to the proof of [28, Theorem 3.1] here: For a tree $T$ let

$f(T)=\begin{cases}1&\text{ if $T$ has protection number at least $k$},\\\
0&\text{ otherwise.}\end{cases}$

Moreover, we define $F(T)$ to be the number of $k$-protected nodes in $T$.
Then the generating function $R_{k}(z,u)=\sum_{T}z^{|T|}u^{F(T)}$ satisfies
(_cf._ [28, Equ. (3.1)])

$z\exp\left(\sum_{i\geq 1}\frac{R_{k}(z^{i},u^{i})}{i}\right)=\sum_{n\geq
1}z^{n}\sum_{T:|T|=n}u^{F(T)-f(T)}$ (13)

As in Section 2.2 we utilize the formula $\mathbb{E}Y_{n}=\sum_{k\geq
1}\mathbb{P}(Y_{n}\geq k)$ and express the occurring probabilities as
$\mathbb{P}(Y_{n}\geq k)=[z^{n}]S_{k}(z)/(n[z^{n}]T(z))$ with $S_{k}(z)$ being
the generating function whose $n$th coefficient is the cumulative number of
$k$-protected nodes in all trees of size $n$. Obviously, $((\partial/\partial
u)R_{k})(z,1)=S_{k}(z)$ and thus by differentiating (13) with respect to $u$
and inserting $u=1$ we obtain

$T(z)\sum_{i\geq 1}S_{k}(z^{i})=S_{k}(z)-T_{k}(z).$ (14)

This implies

$S_{k}(z)=\frac{T(z)\sum_{i\geq
2}S_{k}(z^{i})+T_{k}(z)}{1-T(z)}\sim\frac{\sum_{i\geq
2}S_{k}(\rho^{i})+T_{k}(\rho)}{b\sqrt{1-\frac{z}{\rho}}}$ (15)

where $b$ is the constant appearing in (9). Standard transfer theorems applied
to (9) give

$[z^{n}]T(z)\sim\frac{-bn^{-3/2}\rho^{-n}}{\Gamma(-1/2)}=\frac{bn^{-3/2}\rho^{-n}}{2\sqrt{\pi}},$

and from (15) we get

$[z^{n}]S_{k}(z)\sim\frac{\left(\sum_{i\geq
2}S_{k}(\rho^{i})+T_{k}(\rho)\right)n^{-1/2}\rho^{-n}}{b\sqrt{\pi}}$

and thus

$\mathbb{P}(Y_{n}\geq k)\sim\frac{2}{b^{2}}\left(\sum_{i\geq
2}S_{k}(\rho^{i})+T_{k}(\rho)\right).$ (16)

Since $T_{k}(\rho)$ decreases exponentially (_cf._ remark after Theorem 3),
and so does $\sum_{i\geq 2}S_{k}(\rho^{i})$, these probabilities decrease
exponentially and thus the series for $\mathbb{E}Y_{n}$, namely

$\mathbb{E}Y_{n}=\sum_{k\geq 1}\mathbb{P}(Y_{n}\geq k),$

converges rapidly. But (16) still bears a secret, because we do not have an
explicit expression for $S_{k}(z)$ and we cannot solve the functional equation
(14).

For numerical purposes, however, it is not necessary to have an explicit
expression for $S_{k}(z)$. If we write $S_{k}(z)=\Psi(S_{k}(z))$ with $\Psi$
being the operator on the ring of formal power series defined by

$\Psi(f(z))=\frac{T(z)\sum_{i\geq 2}f(z^{i})+T_{k}(z)}{1-T(z)},$

then $\Psi$ is a contraction on the metric space $\mathbb{R}[[z]]$ equipped
with the formal topology (_cf._ [16, Appendix A.5]). Indeed, if $f(z)$ and
$g(z)$ coincide up to their $\ell$th coefficient, then the first $2\ell+2$
coefficients of $\Psi(f(z))$ and$\Psi(g(z))$ coincide.

As there is exactly one tree with $k+1$ vertices which possesses $k$-protected
vertices at all (namely the path of length $k$ has a $k$-protected root)
whereas all smaller trees do not possess any $k$-protected vertices, we know
that the (one-term) series $z^{k+1}$ coincides with $S_{k}(z)=z^{k+1}+\cdots$
in its first $k+2$ coefficients. Applying $\Psi$ to $z^{k+1}$ a few times,
with each application more than doubling the number of known coefficients of
$S_{k}(z)$, gives quickly a fairly accurate expression for $S_{k}(z)$. We
obtain the following theorem:

######  Theorem 4.

Let $Y_{n}$ be the protection number of a random vertex in a random Pólya tree
of size $n$. Then

$\displaystyle\lim_{n\to\infty}\mathbb{E}Y_{n}=\sum_{k\geq
1}\frac{2}{b^{2}}\left(\sum_{i\geq 2}S_{k}(\rho^{i})+T_{k}(\rho)\right)\approx
0.9953254987$

and $\lim_{n\to\infty}\mathbb{V}Y_{n}\approx 1.3818769746.$

##  4\. Non-plane binary trees

###  4.1. Protection number of the root

We denote by $T(z)$ the generating function of non-plane binary trees, where
$z$ marks the number of internal nodes. Then $T(z)$ satisfies

$\displaystyle T(z)=1+z\left(\frac{1}{2}T(z)^{2}+\frac{1}{2}T(z^{2})\right).$

The generating function $T_{k}(z)$ of non-plane binary trees with protection
number at least $k$ fulfills

$\displaystyle
T_{k}(z)=z\left(\frac{1}{2}T_{k-1}(z)^{2}+\frac{1}{2}T_{k-1}(z^{2})\right),$

and $T_{0}(z)=T(z)$.

In order to obtain the asymptotic mean and variance for the protection number
of a random non-plane binary tree of size $n$ we proceed analogously as in the
previous section for Pólya trees. Thus, we use

$\displaystyle\mathbb{E}X_{n}=\sum_{k\geq
1}\prod_{i=1}^{k}\mathbb{P}(X_{n}\geq k|X_{n}\geq k-1)=\sum_{k\geq
1}\prod_{i=1}^{k}\frac{[z^{n}]T_{k}(z)}{[z^{n}]T_{k-1}(z)}.$

######  Theorem 5.

Let $X_{n}$ be the protection number of a random non-plane binary tree of size
$n$. Then

$\displaystyle\lim_{n\to\infty}\mathbb{E}X_{n}=\sum_{k\geq
1}\prod_{i=1}^{k-1}(\rho T_{i}(\rho))\approx 1.707603060723366$

and $\lim_{n\to\infty}\mathbb{V}X_{n}\approx 0.431102549825064.$

###### Proof.

Let the Puiseux expansion of $T_{k}(z)$ and $T_{k+1}(z)$ read as

$\displaystyle
T_{k-1}(z)=T_{k-1}(\rho)-\gamma_{k}\sqrt{1-\frac{z}{\rho}}+\mathcal{O}\left(1-\frac{z}{\rho}\right),$

and

$\displaystyle
T_{k}(z)=\rho\left(\frac{1}{2}T_{k-1}(\rho)^{2}+\frac{1}{2}T_{k-1}(\rho^{2})\right)+\rho
T_{k-1}(\rho)\gamma_{k}\sqrt{1-\frac{z}{\rho}}+\mathcal{O}\left(1-\frac{z}{\rho}\right)$

Using singularity analysis yields the desired result for the mean. For the
variance we use again the formula $\mathbb{V}X_{n}=\sum_{k\geq
1}(2k-1)\mathbb{P}(X_{n}\geq k)-\mathbb{E}(X_{n})^{2}$. ∎

###  4.2. Protection number of a random internal vertex

The asymptotic mean and variance for the protection number of a randomly
chosen internal vertex in a random non-plane binary tree can be obtained in
the same way as in the previous section for Pólya trees.

Thus, we again set up an equation for the generating function $R_{k}(z,u)$
where the coefficients $[z^{n}u^{l}]R_{k}(z,u)$ count the number of non-plane
binary trees of size $n$ with $l$ $k$-protected vertices:

$\displaystyle\frac{z}{2}\left(R_{k}(z,u)^{2}+R_{k}(z^{2},u^{2})\right)=\sum_{n\geq
1}z^{n}\sum_{T:|T|=n}u^{F(T)-f(T)}$

Differentiating this equation with respect to $u$ and setting $u=1$ yields

$\displaystyle zT(z)S_{k}(z)+zS_{k}(z^{2})=S_{k}(z)-T_{k}(z).$

Therefore we get

$\displaystyle S_{k}(z)=\frac{zS_{k}(z^{2})+T_{k}(z)}{1-zT(z)}.$

The asymptotic expansion of $T(z)$ is given by

$\displaystyle T(z)\sim\frac{1}{\rho}-a\sqrt{1-\frac{z}{\rho}}.$

In [16, p. 477] we find the numerical values of the constants $\rho$ and $a$.
(_Caveat_ : The scaling is different, so [16, p. 477] in fact lists
$a\cdot\rho$, not $a$.) We have $\rho\approx 0.4026975036714412909690453$ and
$a\approx 2.8061602222420538943722824$. Using this expansion we get

$\displaystyle\mathbb{P}(Y_{n}\geq
k)=\frac{[z^{n}]S_{k}(z)}{n[z^{n}]T(z)}\sim\frac{2}{a^{2}\rho}\left(\rho
S_{k}(\rho^{2})+T_{k}(\rho)\right).$

By denoting $\Psi(f(z))=\frac{zf(z^{2})+T_{k}(z)}{1-zT(z)}$ we can use the
same arguments as in the Pólya case to efficiently obtain numerical values for
the probabilities $\mathbb{P}(Y_{n}\geq k)$. Finally, we are able to calculate
the asymptotic mean and variance for the protection number of a random node in
non-plane binary trees.

######  Theorem 6.

Let $Y_{n}$ be the protection number of a random internal vertex in a random
non-plane binary tree of size $n$. Then

$\displaystyle\lim_{n\to\infty}\mathbb{E}Y_{n}$
$\displaystyle=\frac{2}{a^{2}\rho}\sum_{k\geq 1}\left(\rho
S_{k}(\rho^{2})+T_{k}(\rho)\right)\approx 1.3124128299,$

and $\lim_{n\to\infty}\mathbb{V}Y_{n}\approx 0.2676338724.$

##  5\. Conclusion

In this paper we generalized the work of Heuberger and Prodinger, who derived
the average protection number of plane trees, to a more general framework. We
obtained the average protection number for all simply generated trees, as well
as for Pólya trees and non-plane binary trees. We did not include Pólya trees
with general degree restrictions, since the general expressions will look
clumsy and only numerical results for specific classes may be of interest. But
it is immediate that the asymptotic mean and variance of the protection number
for Pólya-trees with any kind of degree restriction can be calculated in the
very same way. As we saw in some of the examples, there are classes of trees,
for which the obtained formulas involve a recurrence that might not be
solvable explicitly. However, using these equations it is possible to
calculate the asymptotic mean and variance in an arbitrarily accurate way with
a fairly low computational effort. In Table 2 we summarize the obtained
results for some specific tree classes.

Tree model | $\lim_{n\to\infty}\mathbb{E}X_{n}$ | $\lim_{n\to\infty}\mathbb{E}Y_{n}$
---|---|---
Simply generated trees |  |
Plane trees | 1.62297 | 0.72765
Motzkin trees | 2.54638 | 1.30760
Incomplete binary trees | 3.53647 | 1.99182
Cayley trees | 2.28620 | 1.18652
Complete binary trees | 1.56298 | 1.26568
Non-plane trees |  |
Pólya trees | 2.15489 | 0.99532
Non-plane binary trees | 1.70760 | 1.31241
Table 2. Summary of the obtained mean values for the protection numbers.

It is well known that Cayley trees and Pólya trees are very similar, but the
latter are not simply generated, as the simple proof presented in [11] shows.
A detailed analysis of the structural differences was done in [17, 26]:
Roughly speaking, Pólya trees are Cayley tree (more precisely, the simply
generated class whose ordinary generating function is the exponential
generating function of Cayley trees) with small forests attached to each
vertex. Comparing the resulting values (from Table 2) for Cayley trees and
Pólya trees shows the quantitative effect of those forests, which have on
average less than one vertex. As expected, these additional forests decrease
the protection numbers.

For complete binary trees the correspondence between plane and non-plane is a
bit different due to the strict degree constraint. The small forests are not
attached anywhere, but they always consist of two identical trees and
attachment is done by replacing a leaf. The effect of the presence or absence
of symmetries seems stronger than the possible increase of the protection
number by adding forests, because the larger number of plane structures gives
some bias to lower protection numbers.

## References

  * [1] A. V. Aho and N. J. A. Sloane.  Some doubly exponential sequences.  Fibonacci Quart., 11(4):429–437, 1973.
  * [2] David Aldous.  Asymptotic fringe distributions for general families of random trees.  The Annals of Applied Probability, 1(2):228–266, 1991.
  * [3] Miklós Bóna and Boris Pittel.  On a random search tree: asymptotic enumeration of vertices by distance from leaves.  Advances in Applied Probability, 49(3):850–876, 2017.
  * [4] Gi-Sang Cheon and Louis W. Shapiro.  Protected points in ordered trees.  Appl. Math. Lett., 21(5):516–520, 2008.
  * [5] Keith Copenhaver.  k-protected vertices in unlabeled rooted plane trees.  Graph. Comb., 33(2):347–355, 2017.
  * [6] Jean-François Delmas, Jean-Stéphane Dhersin, and Marion Sciauveau.  Cost functionals for large (uniform and simply generated) random trees.  Electron. J. Probab., 23:Paper No. 87, 36, 2018.
  * [7] Luc Devroye.  A note on the probabilistic analysis of Patricia trees.  Random Struct. Algorithms, 3(2):203–214, 1992.
  * [8] Luc Devroye and Svante Janson.  Protected nodes and fringe subtrees in some random trees.  Electron. Commun. Probab., 19:10 pp., 2014.
  * [9] Michael Drmota.  The saturation level in binary search tree.  In Danièle Gardy and Abdelkader Mokkadem, editors, Mathematics and Computer Science, pages 41–51, Basel, 2000. Birkhäuser Basel.
  * [10] Michael Drmota.  Random trees.  Springer, Wien, NewYork, 2009.  An interplay between combinatorics and probability.
  * [11] Michael Drmota and Bernhard Gittenberger.  The shape of unlabeled rooted trees.  European J. Combinat., 31:2028–2063, 2010.
  * [12] Rosena R. X. Du and Helmut Prodinger.  Notes on protected nodes in digital search trees.  Appl. Math. Lett., 25(6):1025–1028, 2012.
  * [13] Philippe Duchon, Philippe Flajolet, Guy Louchard, and Gilles Schaeffer.  Boltzmann samplers for the random generation of combinatorial structures.  Combin. Probab. Comput., 13(4-5):577–625, 2004.
  * [14] Steven R. Finch.  Mathematical constants, volume 94 of Encyclopedia of Mathematics and its Applications.  Cambridge University Press, Cambridge, 2003.
  * [15] Philippe Flajolet and Andrew Odlyzko.  Singularity analysis of generating functions.  SIAM Journal on Discrete Mathematics, 3(2):216–240, 1990.
  * [16] Philippe Flajolet and Robert Sedgewick.  Analytic Combinatorics.  Cambridge University press, 2009.
  * [17] Bernhard Gittenberger, Emma Yu Jin, and Michael Wallner.  On the shape of random Pólya structures.  Discrete Math., 341(4):896–911, 2018.
  * [18] Clemens Heuberger and Helmut Prodinger.  Protection number in plane trees.  Applicable Analysis and Discrete Mathematics, 11(2):314–326, 2017\.
  * [19] Cecilia Holmgren and Svante Janson.  Limit laws for functions of fringe trees for binary search trees and random recursive trees.  Electron. J. Probab., 20:51 pp., 2015.
  * [20] Svante Janson.  Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation.  Probab. Surv., 9:103–252, 2012.
  * [21] Hosam M. Mahmoud and Mark Daniel Ward.  Asymptotic distribution of two-protected nodes in random binary search trees.  Appl. Math. Lett., 25(12):2218–2222, 2012.
  * [22] Hosam M. Mahmoud and Mark Daniel Ward.  Asymptotic properties of protected nodes in random recursive trees.  J. Applied Probability, 52(1):290–297, 2015.
  * [23] Toufik Mansour.  Protected points in k-ary trees.  Appl. Math. Lett., 24(4):478–480, 2011.
  * [24] Amram Meir and John W. Moon.  On the altitude of nodes in random trees.  Canadian Journal of Mathematics, 30:997–1015, 1978.
  * [25] Richard Otter.  The number of trees.  Annals of Mathematics, 49(3):583–599, 1948.
  * [26] Konstantinos Panagiotou and Benedikt Stufler.  Scaling limits of random Pólya trees.  Probab. Theory Related Fields, 170(3-4):801–820, 2018.
  * [27] George Pólya.  Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen.  Acta Mathematica, 68(1):145–254, Dec 1937.
  * [28] Stephan Wagner.  Central limit theorems for additive tree parameters with small toll functions.  Combin. Probab. Comput., 24(1):329–353, 2015.