# Counting Phylogenetic Networks of Level $1$ and $2$

Mathilde Bouvel  Institut für Mathematik, Universität Zürich, Winterthurerstr.
190, CH-8057 Zürich, Switzerland<EMAIL_ADDRESS>,  Philippe
Gambette  Université Paris-Est, LIGM (UMR 8049), UPEM, CNRS, ESIEE, ENPC,
F-77454, Marne-la-Vallée, France<EMAIL_ADDRESS>and  Marefatollah
Mansouri  Technische Universität Wien, Department of Discrete Mathematics and
Geometry, Wiedner Hauptstraße 8-10/104, A-1040 Wien, Austria.
<EMAIL_ADDRESS>
###### Abstract.

Phylogenetic networks generalize phylogenetic trees, and have been introduced
in order to describe evolution in the case of transfer of genetic material
between coexisting species. There are many classes of phylogenetic networks,
which can all be modeled as families of graphs with labeled leaves. In this
paper, we focus on rooted and unrooted level-$k$ networks and provide
enumeration formulas (exact and asymptotic) for rooted and unrooted level-1
and level-2 phylogenetic networks with a given number of leaves. We also prove
that the distribution of some parameters of these networks (such as their
number of cycles) are asymptotically normally distributed. These results are
obtained by first providing a recursive description (also called combinatorial
specification) of our networks, and by next applying classical methods of
enumerative, symbolic and analytic combinatorics.

Keywords: phylogenetic networks, level, galled trees, counting, combinatorial
specification, generating function, asymptotic normal distribution

Mathematics Subject Classification (2010): 05A15, 05A16, 92D15

##  1\. Introduction

Phylogenetic networks generalize phylogenetic trees introducing reticulation
vertices, which have two parents, and represent ancestral species resulting
from the transfer of genetic material between coexisting species, through
biological processes such as lateral gene transfer, hybridization or
recombination. More precisely, binary phylogenetic networks are usually
defined as rooted directed acyclic graphs with exactly one root, tree vertices
having one parent and 2 children, reticulation vertices having 2 parents and
one child and labeled leaves. The leaves are bijectively labeled by a set of
taxa, which correspond to currently living species.

As for trees, phylogenetic networks can be rooted or unrooted. Ideally,
phylogenetic networks should be rooted, the root representing the common
ancestor of all taxa labeling the leaves. But several methods which
reconstruct phylogenetic networks, such as combinatorial [HMSW18, vIM18],
distance-based [BDM12, WTM14] or parsimony-based methods [PC01, LV14], do not
produce inherently rooted networks, but provide unrooted networks where tree
vertices and reticulation vertices cannot be distinguished.

An important parameter that allows to measure the complexity of a phylogenetic
networks is its level. Phylogenetic trees are actually phylogenetic networks
of level $0$, and the level of a network $N$ measures “how far from a tree”
$N$ is.

The problem of enumerating (rooted or unrooted) trees is a very classical one
in enumerative combinatorics. Solving this problem actually led to general
methods for enumerating other tree-like structures, where generating functions
play a key role. We will review some of these methods in Section 3. These
methods have successfully been used by Semple and Steel [SS06] to enumerate
two families of phylogenetic networks, namely unicyclic networks and unrooted
level-$1$ networks (also called _galled trees_). Their results include an
equation defining implicitly the generating function for unrooted level-$1$
networks (refined according to two parameters), which yields a closed formula
for the number of unrooted level-$1$ networks with $n$ (labeled) leaves, $k$
cycles, and a total of $m$ edges (also called arcs) across all the cycles. An
upper bound on the number of unlabeled galled trees is also provided in
[CHT18]. Other counting results have been more recently obtained on other
families of phylogenetic networks, for example on so-called normal and tree-
child networks [MSW15, FGM19] and on galled networks [GRZ18].

In this paper, we extend the results of Semple and Steel in several ways.
First, about unrooted level-$1$ networks, we provide an asymptotic estimate of
the number of such networks with $n$ (labeled) leaves. We also prove that the
two parameters considered by Semple and Steel are asymptotically normally
distributed. Second, we consider rooted level-$1$ networks, whose enumeration
does not seem to have been considered so far in the literature. For these
networks, we provide a closed formula counting them by number of leaves,
together with an asymptotic estimate, and a closed formula for their
enumeration refined by two parameters (the number of cycles and number of
edges across all the cycles). Moreover, we show that these two parameters are
asymptotically normally distributed. Finally, we consider both unrooted and
rooted level-$2$ networks. Similarly, we provide in each case exact and
asymptotic formulas for their enumeration, and prove asymptotic normality for
some parameters of interest, namely: the number of bridgeless components of
strictly positive level, and the number of edges across them. These parameters
are a generalization for level-$k$ ($k>2$) of those considered by Semple and
Steel for level-1, in the sense that they quantify how different from a tree
these phylogenetic networks are.

The results of this paper rely heavily on analytic combinatorics [FS08]. This
framework can also be used to derive uniform random generators (for example
with the recursive method [FZC94] or with a Boltzmann sampler [DFLS04])
directly from the specifications of the classes of phylogenetic networks given
below. This could be useful for applications in bioinformatics, especially to
generate simulated data in order to evaluate the speed or the quality of the
output of algorithms dealing with phylogenetic networks.

Table 1 provides an overview of our results, and of where they can be found in
the paper.

Type of network | Unrooted, | Rooted, | Unrooted, | Rooted,
---|---|---|---|---
| level-$1$ | level-$1$ | level-$2$ | level-$2$
Letter $\mathcal{X}$ denoting the class |  $\mathcal{G}$ (galled) |  $\mathcal{R}$ (rooted) |  $\mathcal{U}$ (unrooted) |  $\mathcal{L}$ (last)
Eq. for the EGF $X(z)$ | Thm. 1 $(*)$ | Thm. 5.1 | Thm. 6.1 | Thm. 7.1
Exact formula for $x_{n}$ | Thm. 1 $(*)$ | Prop. 5.2 | Prop 8.1 | Prop. 8.2
Asymptotic estimate of $x_{n}$ | Prop. 4.2 | Prop. 5.3 | Prop. 6.2 | Prop. 7.2
Eq. for the multivariate EGF | Eq. (3) $(*)$ | Eq. (4) | Eq. (5) | Eq. (6)
Asymptotic normality | Prop. 4.3 | Prop. 5.5 | Prop. 6.3 | Prop. 7.3
Table 1. Overview of our main results. EGF means exponential generating
function. The results marked with $(*)$ also appear in the work of Semple and
Steel [SS06]. In addition, refined enumeration formulas for unrooted and
rooted level-1 networks are provided in [SS06, Thm. 4] and Prop. 5.4
respectively. (Although the proof method applies to obtain such formulas for
level-2 as well, the computations would however be rather intricate, and the
interest _a priori_ of the formulas so obtained questionable, hence our choice
not to do it.)

For the reader’s convenience, we also include in this introduction the
beginnings of the enumeration sequences of the four types of networks we
consider, as well as their asymptotic behavior – see Table 2. We have added
these sequences to the OEIS [OEI19], and we also include in Table 2 their OEIS
reference. We also provide in the supplementary material the code in the DOT
language, as well as a visualization with GraphViz, of the 15 unrooted level-1
networks on 4 leaves, the 3 rooted level-1 networks on 2 leaves, the 6
unrooted level-2 networks on 3 leaves and the 18 rooted level-2 networks on 2
leaves.

$n$ | $g_{n-1}$ | $r_{n}$ | $u_{n-1}$ | $\ell_{n}$
---|---|---|---|---
1 | 0 | 1 | 0 | 1
2 | 1 | 3 | 1 | 18
3 | 2 | 36 | 6 | 1 143
4 | 15 | 723 | 135 | 120 078
5 | 192 | 20 280 | 5 052 | 17 643 570
6 | 3 450 | 730 755 | 264 270 | 3 332 111 850
as $n\to\infty$ | $c_{1}\approx 0.20748$ | $c_{1}\approx 0.1339$ | $c_{1}\approx 0.07695$ | $c_{1}\approx 0.02931$
$x_{n}\sim c_{1}c_{2}^{n}n^{n-1}$ with | $c_{2}\approx 1.89004$ | $c_{2}\approx 2.943$ | $c_{2}\approx 5.4925$ | $c_{2}\approx 15.4333$
OEIS reference | A328121 | A328122 | A333005 | A333006
Table 2. The numbers of rooted and unrooted level-1 or level-2 networks on $n$
leaves.

The remainder of the article is organized as follows. First, Section 2 recalls
definitions and properties of phylogenetic networks that are important for our
purpose. Next, Section 3 reviews some methods of enumerative and analytic
combinatorics which we will apply to solve the enumeration of our networks in
the following sections. Precisely, Sections 4 and 5 deal with level-$1$
networks, unrooted and rooted, while Sections 6 and 7 focus on level-$2$
networks.

##  2\. Some properties of phylogenetic networks

###  2.1. Rooted binary phylogenetic networks

In graph theory, a cut arc or bridge of a directed graph $G$ is an arc whose
deletion disconnects $G$. A bridgeless component of a graph is a maximal
induced subgraph of $G$ without cut arcs.

We define a binary rooted phylogenetic network $N$ on a set $X$ of leaf
labels, for $|X|\geq 2$ as a directed acyclic graph having:

  1. (1)

exactly one root, that is an in-degree-0 out-degree-2 vertex;

  2. (2)

leaves, that is in-degree-1 out-degree-0 vertices which are bijectively
labeled by elements of $X$;

  3. (3)

tree vertices, that is in-degree-1 out-degree-2 vertices;

  4. (4)

reticulation vertices, that is in-degree-2 out-degree-1 vertices;
and such that

  5. (5)

for each bridgeless component $B$ of $N$, there exist at least two cut arcs of
$N$ whose tail111The _tail_ of an arc is by definition its starting point. Its
arrival point is called _head_. belongs to $B$ and whose head does not belong
to $B$.

A binary rooted phylogenetic network $N$ on a singleton ${x}$ is a single
vertex labeled by $x$.

As illustrated in Fig. 1, a binary rooted phylogenetic network $N$ is said to
be level-$k$ (or called a level-$k$ network for short) if the number of
reticulation vertices contained in any bridgeless component of $N$ is less
than or equal to $k$. In a level-1 network $N$, each bridgeless component $B$
having at least two vertices consists of the union of two directed paths,
which start and end at the same vertices, called _source_ and _sink_
respectively. The source is actually either the root of $N$, or the head of a
cut arc of $N$, and the sink is the unique reticulation vertex of $B$. Such
bridgeless components are called _cycles_.

Note that variations on the definition of rooted binary phylogenetic networks
are around in the literature, and a few comments on our choice of definition
are in order. Like in most publications about phylogenetic networks, our
definition of binary rooted phylogenetic networks does not allow multiple
arcs. As our goal is to study a model of binary phylogenetic networks that
could be counted if their number of leaves and level are fixed, condition (5)
is necessary to ensure that there are finitely many phylogenetic networks with
a given number of leaves and level. Note that this restriction has already
appeared in the literature under the name “networks with no redundant
biconnected components” [vIM14] or “with no redundant blobs” [GvIK+16].
Indeed, without it, such networks have an unbounded number of vertices: this
can be seen by replacing any cut arc of the network by a sequence of networks
isomorphic to the one in Fig. 4($2a$), which has only one incoming cut-arc and
one outgoing cut-arc.

Similarly in some algorithmic-oriented papers about phylogenetic networks,
bridgeless components with three vertices and two outgoing arcs are forbidden
because the information needed to distinguish those components from simple
tree vertices also connected with two outgoing arcs is not available in the
input data. In the perspective of counting those objects we do not impose this
restriction. But it could easily be added to our combinatorial descriptions
and formulas below, to be taken into account if needed.

###  2.2. Unrooted binary phylogenetic networks

Now, we extend the latter definition to unrooted phylogenetic networks. A cut-
edge or bridge of an undirected graph $G$ is an edge whose removal disconnects
the graph. A bridgeless component of a graph $G$ is a maximal induced subgraph
of $G$ without cut-edges.

An unrooted binary phylogenetic network $N$ on a set $X$ of at least 2 leaf
labels is a loopless (undirected) graph whose vertices have either degree $3$
(internal vertices) or degree $1$ (leaves), such that its set $L(N)$ of leaves
is bijectively labeled by $X$ and such that for each bridgeless component $B$
of $N$ having strictly more than one vertex, the set of cut-edges incident
with some vertex of $B$ has size at least 3. An unrooted binary phylogenetic
network $N$ on a singleton ${x}$ is a single vertex labeled by $x$. An
unrooted binary phylogenetic tree is an unrooted binary phylogenetic network
with no bridgeless component containing strictly more that one vertex. An
unrooted binary phylogenetic network is said to be level-$k$ (or called an
unrooted level-$k$ network for short) if an unrooted binary phylogenetic tree
can be obtained by first removing at most $k$ edges per bridgeless component,
and then, for each degree-2 vertex, contracting the edge between this vertex
and one of its neighbours. We denote by _cycles_ the bridgeless components of
unrooted level-1 networks having strictly more than one vertex. (Indeed, they
are just cycles – of size at least $3$ – in the graph-theoretical sense.)

Note that given a rooted level-$k$ network $N$ on $n$ leaves, we can obtain an
unrooted binary phylogenetic network $N^{\prime}$ on $n+1$ leaves with the
following _unrooting procedure_ : add a vertex adjacent to the root of $N$,
labeled with an extra leaf label (usually denoted $\\#$), and ignore all arc
directions. Theorem 1 of [GBP12] implies in addition that the network
$N^{\prime}$ so obtained is an unrooted level-$k$ network. This unrooting
procedure which consists of building an unrooted level-$k$ network from a
rooted level-$k$ network, illustrated in Fig. 1, can be reversed (see Lemma
4.13 of [JJE+18]), although not in a unique fashion. Indeed, given an unrooted
level-$k$ network $N^{\prime}$ on $n+1$ leaves, it is possible to choose any
leaf and delete it, making its neighbour become the root $\rho$ of a rooted
level-$k$ network $N$ obtained by:

  1. (1)

placing the bridgeless component $B$ containing $\rho$ at the top;

  2. (2)

orienting downwards all the cut-edges incident with vertices of $B$;

  3. (3)

choosing the tail $t$ of one of these cut arcs as the sink of $B$;

  4. (4)

computing an $\rho$-$t$ numbering [LEC67] on the vertices of $B$ if there are
more than one, that is labeling vertices of $B$ with integers from 1 to the
number $n_{B}$ of vertices of $B$, such that the labels of $\rho$ and $t$ are
respectively 1 and $n_{B}$ and such that any vertex of $B$ except $\rho$ and
$t$ is adjacent both to a vertex with a lower label and a vertex with a higher
label;

  5. (5)

orienting each edge of $B$ by choosing its vertex with the lower label as the
tail;
and

  6. (6)

moving downwards into the network, recursively applying this procedure on all
other bridgeless components.

This correspondence is not one-to-one because of the choices of the leaf which
is deleted, and most importantly because of the choices of sinks in step 3
above.

$\rho$$l_{1}$$l_{2}$$l_{3}$$l_{4}$$l_{5}$$l_{6}$ | $\\#$$\rho$$l_{1}$$l_{2}$$l_{3}$$l_{4}$$l_{5}$$l_{6}$
---|---
$N$ | $N^{\prime}$
Figure 1.  A rooted level-2 network $N$ (where all arcs are directed
downwards) and the unrooted level-2 network $N^{\prime}$ obtained by applying
the unrooting procedure on $N$.

###  2.3. Decomposition of rooted and unrooted level-$k$ networks

For any bridgeless component $B$ with $k_{B}\leq k$ reticulation vertices of a
rooted level-$k$ network $N$, the directed multi-graph obtained by removing
all outgoing arcs, and then contracting each arc from an in-degree-1 out-
degree-1 vertex to its child, is called a _level- $k_{B}$ generator_ [vIKK+09,
GBP09]. For each $k>0$, there exists a finite list of _level- $k$ generators_
which can be built from level-($k-1$) generators [GBP09]. Therefore, depending
on the level $k_{\rho}$ of the bridgeless component $B_{\rho}$ of $N$
containing its root $\rho$, $N$ can be decomposed in the following way. It is
either:

  * •

a single leaf if $k_{\rho}=0$ and $\rho$ has out-degree 0;

  * •

a root $\rho$ being the parent of the root $\rho_{1}$ of a rooted level-$k$
network $N_{1}$ and of the root $\rho_{2}$ of a rooted level-$k$ network
$N_{2}$ with disjoint sets of leaf labels, if $k_{\rho}=0$ and $\rho$ has out-
degree $2$;

  * •

a level-$k_{\rho}$ generator $G_{\rho}$ containing the root, with
$0<k_{\rho}\leq k$, whose arcs are subdivided to create new in-degree-1 out-
degree-1 vertices, to which we add a set of cut arcs, whose tails are the out-
degree-0 vertices of $G_{\rho}$ and the newly created in-degree-1 out-degree-1
vertices, and whose heads are roots of rooted level-$k$ networks with disjoint
sets of leaf labels.

Similarly, for any bridgeless component $B$ of an unrooted level-$k$ network
$N$, the multi-graph obtained by first removing all cut-edges incident with
any vertex of $B$, then, for each degree-2 vertex, contracting the edge
between this vertex and one of its neighbours, is called an _unrooted level-
$k_{B}$ generator_ [GBP12, HMW16]. An unrooted level-$k_{B}$ generator can
also be defined as a single vertex for $k_{B}=0$, as two vertices linked by a
multiple edge for $k_{B}=1$, and as a 3-regular bridgeless multi-graph with
$2k_{B}-2$ vertices for $k_{B}>1$ (Lemma 6 of [HMW16]). Therefore, by
considering a leaf $l_{\\#}$ of any unrooted level-$k$ network $N$ and the
bridgeless component $B$ containing the vertex adjacent to this leaf,
depending on the level $k_{B}$ of $B$, $N$ can be decomposed in the following
way.

  * •

If $k_{B}=0$ and $B$ consists of a single vertex of degree $1$ in $N$, then
$N$ is just the leaf $l_{\\#}$ adjacent to another leaf.

  * •

If $k_{B}=0$ and $B$ is not a single vertex of degree $1$ in $N$, then the
leaf $l_{\\#}$ is adjacent to a vertex $v$ of degree $3$ in $N$, such that the
other two edges incident to $v$ are cut-edges. $N$ is described by the edge
between $l_{\\#}$ and $v$, plus the two other edges incident with $v$, which
are in turn identified with edges of two unrooted level-$k$ networks $N_{1}$
and $N_{2}$ with disjoint sets of leaf labels (not containing $\\#$) in such a
way that $v$ is identified with a leaf $l_{\\#1}$ (resp. $l_{\\#2}$) of
$N_{1}$ (resp. $N_{2}$), removing the leaf labels of $l_{\\#1}$ and $l_{\\#2}$
during this identification.

  * •

Otherwise $0<k_{B}\leq k$. In this case, $N$ is described by taking a
level-$k_{B}$ generator whose edges are subdivided to insert vertices, and
then performing identification of these inserted vertices (in a same flavor as
in the previous case). Specifically, one of these inserted vertices is
identified with the neighbour of $l_{\\#}$ in $N$, and all others are
identified with leaves of unrooted level-$k$ networks with disjoint sets of
leaf labels (not containing $\\#$). Again, each leaf that is identified with
another vertex looses its label during this identification.

These decompositions of rooted and unrooted level-$k$ networks will be the key
to our counting results below.

##  3\. Generating functions: some basics tools and techniques

This section summarizes some of the basics on combinatorial classes and their
generating functions that we will use in our work. Our presentation follows
closely [FS08] (although with much less details), and the reader interested to
know more on the topic is referred to [FS08, mainly Chapters I.5, II.1, II.5,
VI.3, VII.3, VII.4]. The reader familiar with the classical tools of analytic
combinatorics may safely skip this section.

###  3.1. (Univariate) generating functions and counting

Generally speaking, a _combinatorial class_ $\mathcal{C}$ is a set of discrete
objects, equipped with a notion of size, such that for every integer $n$ there
is a finite number of objects of size $n$ in $\mathcal{C}$. We denote by
$\mathcal{C}_{n}$ the set of objects of size $n$ in $\mathcal{C}$, and by
$c_{n}$ the cardinality of $\mathcal{C}_{n}$. Specifically in this paper, each
combinatorial class we consider is a family of level-$k$ phylogenetic
networks, and the size of such a network is its number of leaves.

Objects of size $n$ in $\mathcal{C}$ can be seen as an arrangement (following
some rules to be made precise) of $n$ atoms, which are objects of size $1$. In
our context, these atoms are the leaves of the networks, representing the
current species, or _taxa_. When the atoms constituting an object are
distinguishable among themselves, the considered combinatorial objects are
said to be _labeled_ 222Although it is also very classical, the case of
_unlabeled_ objects (with their corresponding _ordinary_ generating functions)
will not be useful in our work, and is therefore omitted from our
presentation.. Because leaves of level-$k$ networks correspond to taxa, our
networks are indeed labeled combinatorial objects. Without loss of generality
(_i.e._ , up to relabeling), atoms in a labeled object of size $n$ are simply
labeled by integers from $1$ to $n$, and we will take this convention in our
work.

To a (labeled) combinatorial class $\mathcal{C}$, we can associate its
_exponential_ _generating function_ $C(z)=\sum_{n\geq
0}c_{n}\frac{z^{n}}{n!}$, which is a formal power series in $z$ encapsulating
the entire enumeration of $\mathcal{C}$.

A _specification_ for a combinatorial class is an unambiguous description of
the objects in the class using simpler classes and possibly the class itself.
For instance, consider labeled rooted ordered binary trees, and define their
size to be the number of their leaves. Such a tree is unambiguously described
as being either a leaf or composed of a root to which a left and a right
subtree are attached, which are themselves labeled rooted ordered binary
trees, with a _consistent relabeling_ of their atoms. By this, we mean the
following: considering two trees whose atoms are labeled by $\\{1,\dots,k\\}$
and $\\{1,\dots,k^{\prime}\\}$, we can build a tree using the first (resp.
second) as left (resp. right) subtree; the atoms of this tree are labeled by
$\\{1,\dots,k+k^{\prime}\\}$, and need to be such that the relative order
between the labels in the left (resp. right) subtree is preserved (and they
may be in any such way). This specification for labeled rooted ordered binary
trees can be formally written as follows: $\mathcal{B}=\bullet$ $\uplus$
$\circ$$\mathcal{B}$$\mathcal{B}$, where $\bullet$ represents a leaf
(contributing $1$ to the size of the object) and $\circ$ represents an
internal node (which contributes $0$ to the size).

Specifications describing (labeled) combinatorial classes can be translated
into equations satisfied by the corresponding (exponential) generating
functions. The precise statement that we refer to is [FS08, Theorem II.1]. The
following proposition summarizes the simplest cases of this translation, which
we will often use later in this paper.

######  Proposition 3.1 (Dictionary).

Let $\mathcal{A}$ and $\mathcal{B}$ be two labeled combinatorial classes.
Denote by $A(z)$ and $B(z)$ their respective exponential generating functions.
Then the generating function of the class which is the disjoint union of
$\mathcal{A}$ and $\mathcal{B}$ (resp. the Cartesian product of $\mathcal{A}$
and $\mathcal{B}$) is $A(z)+B(z)$ (resp. $A(z)\cdot B(z)$). In addition, if
$\mathcal{A}$ contains no object of size $0$, the class which consists of
sequences of objects of $\mathcal{A}$ (_i.e._ , $m$-tuples of objects of
$\mathcal{A}$, for any $m\geq 0$) has generating function $\frac{1}{1-A(z)}$.

On the previous example of binary trees, it follows from the above proposition
that the corresponding generating function satisfies $B(z)=z+B(z)^{2}$.

The next step is to have access to the enumeration sequence $(c_{n})$ of a
class $\mathcal{C}$ from an equation satisfied by the generating function
$C(z)$ of $\mathcal{C}$. A possible way, especially in the case of tree-like
objects, is to appeal to the _Lagrange inversion formula_ ([FS08, Theorem
A.2]). To state it, we introduce the notation $[z^{n}]C(z)$ to denote the
$n$-th coefficient of the series $C(z)$; that is to say, writing
$C(z)=\sum_{n\geq 0}\frac{c_{n}}{n!}z^{n}$, we have
$[z^{n}]C(z)=\frac{c_{n}}{n!}$, or equivalently $c_{n}=n!\cdot[z^{n}]C(z)$.

The Lagrange inversion formula is as follows.

######  Proposition 3.2 (Lagrange inversion formula).

Assume that a generating function $C$ satisfies an equation of the form
$C(z)=z\phi(C(z))$ for $\phi(z)=\sum_{n\geq 0}\phi_{n}z^{n}$ a formal power
series such that $\phi_{0}\neq 0$. Then, we have:

$[z^{n}]C(z)=\frac{1}{n}[z^{n-1}]\phi(z)^{n}\textrm{.}$

Even though defined as formal power series, it is often useful to consider
that generating functions are analytic functions of the complex variable $z$,
in a small disk of convergence around the origin of the complex plane. This
sometimes allows to find a closed form for the generating function in its disk
of convergence, but not always. Even in this least favorable case, it enables
to inherit fundamental results from complex analysis, which can be used for
the purpose of enumerating combinatorial objects. In particular, we have in
this tool box the _Singular Inversion Theorem_ (Theorem VI.6 of [FS08]), which
allows to derive asymptotic estimates of the coefficients of generating
functions.

######  Theorem 3.3 (Singular Inversion Theorem).

Let $C(z)$ be a generating function such that $C(0)=0$, satisfying the
equation $C(z)=z\phi(C(z))$ for $\phi(z)=\sum_{n\geq 0}\phi_{n}z^{n}$ a power
series such that $\phi_{0}\neq 0$, all $\phi_{n}$ are non-negative real
numbers, and $\phi(z)\neq\phi_{0}+\phi_{1}z$. Denote by $R$ the radius of
convergence of $\phi$ at $0$. Assume that $\phi$ is analytic at $0$ (so that
$R>0$), that the _characteristic equation_ $\phi(z)-z\phi^{\prime}(z)=0$ has a
solution $\tau\in(0,R)$ (that is necessarily unique), and that $\phi$ is
aperiodic333Aperiodicity is needed only for the third item below. The
definition of aperiodicity is omitted from this paper, and can be found in
[FS08, Definition IV.5]. A sufficient condition for a power series to be
aperiodic (which applies to all examples considered in this paper), is to have
$\phi_{n}>0$ for all $n$.. Then the followings hold:

  * •

$\rho=\frac{\tau}{\phi(\tau)}$ is the radius of convergence of $C$ at $0$;

  * •

near $\rho$,
$C(z)\sim\tau-\sqrt{\frac{2\phi(\tau)}{\phi^{\prime\prime}(\tau)}}\sqrt{1-\frac{z}{\rho}}$;

  * •

when $n$ grows,
$[z^{n}]C(z)\sim\sqrt{\frac{\phi(\tau)}{2\phi^{\prime\prime}(\tau)}}\frac{\rho^{-n}}{\sqrt{\pi
n^{3}}}$.

###  3.2. Multivariate generating functions and estimating parameters

Until now, our generating functions had only a single variable, $z$, recording
the size of the objects we were counting. We now consider _multivariate_
generating functions, where additional variables ($x$, $y$, …) record the
value of other parameters of our objects. In our cases, we will consider at
most two such parameters, which are numbers of certain “substructures”
occurring in our objects. Namely, denoting $c_{n,k,m}$ the number of objects
of size $n$ in the combinatorial class $\mathcal{C}$ such that the first
parameter has value $k$ and the second has value $m$, the multivariate
exponential generating function we consider is
$C(z,x,y)=\sum_{n,k,m}\tfrac{c_{n,k,m}}{n!}z^{n}x^{k}y^{m}$.

To continue our earlier example of binary trees, we could consider one
additional parameter, which is the number of internal nodes. (Of course,we are
aware that the number of internal nodes is always the number of leaves –
_i.e._ , the size – minus one; but we keep this example just to illustrate
definitions and tools available.) The coefficient of $z^{n}x^{k}$ in the
generating function $B(z,x)$ is then the number of binary trees with $n$
leaves and $k$ internal nodes, divided by $n!$.

The “dictionary” translating combinatorial specifications to equations
satisfied by the generating function extends to multivariate series, and our
earlier specification $\mathcal{B}=\bullet$ $\uplus$
$\circ$$\mathcal{B}$$\mathcal{B}$ gives $B(z,x)=z+xB(z,x)^{2}$.

Here again, the Lagrange inversion formula may be used to derive a closed
formula for the coefficients $c_{n,k,m}$. Indeed, assuming that our
multivariate exponential generating function $C(z,x,y)$ satisfies an equation
of the form $C(z,x,y)=z\phi(C(z),x,y)$ for $\phi(z,x,y)=\sum_{n\geq
0}\phi_{n}(x,y)z^{n}$ a formal power series such that $\phi_{0}\neq 0$, then
we have:

$\tfrac{c_{n,k,m}}{n!}=[z^{n}x^{k}y^{m}]C(z,x,y)=\frac{1}{n}[z^{n-1}x^{k}y^{m}]\phi(z,x,y)^{n}\textrm{.}$

Moreover, under some hypotheses, the following theorem (see [Drm09, Theorem
2.23]) allows to prove that the considered parameters are asymptotically
normally distributed. The notation used in the statement of this theorem is as
follows: if $F$ is a function of several variables, including $v$, $F_{v}$
denotes the partial derivative of $F$ with respect to $v$; as usual,
$\mathbb{E}$ and $\mathbb{V}ar$ respectively denote expectation and variance;
$\mathcal{N}(0,1)$ is the standard normal distribution; and $\xrightarrow{d}$
denotes convergence in distribution.

######  Theorem 3.4.

Assume that $C(z,x)$ is a power series that is the (necessarily unique and
analytic) solution of the functional equation $C=F(C,z,x)$, where $F(C,z,x)$
satisfies the following assumptions: $F(C,z,x)$ is analytic in $C$, $z$ and
$x$ around $0$, $F(C,0,x)=0$, $F(0,z,x)\neq 0$, and all coefficients
$[z^{n}C^{m}]F(C,z,1)$ are real and non-negative.

Assume in addition that the region of convergence of $F(C,z,x)$ is large
enough for having non-negative solutions $z=z_{0}$ and $C=C_{0}$ of the system
of equations

$\displaystyle C$ $\displaystyle=F(C,z,1)$ $\displaystyle 1$
$\displaystyle=F_{C}(C,z,1)$

with $F_{z}(C_{0},z_{0},1)\neq 0$ and $F_{CC}(C_{0},z_{0},1)\neq 0$.

Then, if $X_{n}$ is a sequence of random variables such that

$\mathbb{E}x^{X_{n}}=\dfrac{[z^{n}]C(z,x)}{[z^{n}]C(z,1)},$

then $X_{n}$ is asymptotically normally distributed.

More precisely, setting
$\mu=\dfrac{F_{x}}{z_{0}F_{z}}$

$\displaystyle\sigma^{2}$
$\displaystyle=\mu+\mu^{2}+\dfrac{1}{z_{0}F_{z}^{3}F_{CC}}\Big{(}F_{z}^{2}(F_{CC}F_{xx}-F_{Cx}^{2})-2F_{z}F_{x}(F_{CC}F_{zx}-F_{Cz}F_{Cx})+F_{x}^{2}(F_{CC}F_{zz}-F_{Cz}^{2})\Big{)}$

where all partial derivatives are evaluated at the point $(C_{0},z_{0},1)$, we
have

$\mathbb{E}{X_{n}}=\mu
n+O(1)\;\;\;\;\;\;and\;\;\;\;\;\;\;\;\;\mathbb{V}ar{X_{n}}=\sigma^{2}n+O(1)$

and if $\sigma^{2}>0$ then

$\dfrac{X_{n}-\mathbb{E}{X_{n}}}{\sqrt{\mathbb{V}ar{X_{n}}}}\xrightarrow{d}\mathcal{N}(0,1).$

###  3.3. Implementation and note about computations

Some of the computations used to obtain the results of this paper were
programmed in Maple. A companion Maple document is available from the authors
webpage444at
http://user.math.uzh.ch/bouvel/publications/BouvelGambetteMansouri_Version2_WithoutMultipleEdges.mw.

We also point out to the interested reader that a first version of this
article was considering a variant of the model of level-$k$ phylogenetic
networks, where multiple (_i.e._ parallel) edges are allowed. The counting
results for this alternate model of course differ (starting from level $2$),
and can be found in [BGM19], again with an associated Maple
document555available at
http://user.math.uzh.ch/bouvel/publications/BouvelGambetteMansouri_Version1_WithMultipleEdges.mw.
Similarly, these files can easily be used to adapt the computations in case
other restrictions are imposed on the structure of level-1 or level-2
phylogenetic networks, for example if _tiny cycles_ , defined in [HvIM+17] as
bridgeless components with exactly three vertices, are not allowed.

##  4\. Counting unrooted level-1 networks

###  4.1. Generating function and exact enumeration formula

Unrooted level-1 networks (also called unrooted galled trees) have been
enumerated in [SS06]. The enumeration does not only consider the number of
leaves of the galled trees, but is refined according to two parameters: the
number of cycles (_i.e._ , level-1 generators) and the total number of edges
which are part of a cycle (that we will call _inner edges_). We only reproduce
in Theorem 1 a simplified version of the results of [SS06], taking into
account the number of leaves only.

######  Theorem 4.1.

For any $n\geq 0$, let $g_{n}$ denote the number of unrooted level-1 networks
with $(n+1)$ leaves, and denote by $G(z)=\sum_{n\geq 0}g_{n}\frac{z^{n}}{n!}$
the corresponding generating function. Then $G$ satisfies the following
equation:

$G(z)=z+\frac{1}{2}G(z)^{2}+\frac{1}{2}\frac{G(z)^{2}}{1-G(z)}\textrm{,}$

or equivalently

$G(z)=z\phi(G(z))\textrm{ with
}\phi(z)=\frac{1}{1-\frac{1}{2}z(1+\frac{1}{1-z})}\textrm{.}$

Moreover, for any $n\geq 0$, let $g_{n}$ denote the number of unrooted level-1
networks with $(n+1)$ leaves. We have:

(1) $g_{n}=\frac{(2n-2)!}{2^{n-1}(n-1)!}+\sum_{1\leq i\leq k\leq
n-1}\frac{(n+i-1)!(n+k-i-2)!}{k!(k-1)!(i-k)!(n-i-1)!}2^{-i}\textrm{.}$

Notice that even if the formulas seem different, Eq. (1) can be recovered from
Theorem 4 of [SS06] by summing over $k$ and $m$ and performing the change of
variable $m=n-i+3k-1$. The first values of $g_{n}$ have been included in Table
2.

###### Proof.

We recall the main steps of the proofs of Theorem 1 given in [SS06]. To
prepare the ground for future proofs, we emphasize their embedding in the
context we presented in Section 3.

Since counting rooted objects is far easier that counting unrooted objects, we
establish a bijective correspondence between unrooted level-1 networks, and a
rooted version of these networks, that we call _pointed_ level-1 networks.
Pointed level-1 networks on a set of taxa $X$ are simply unrooted level-1
networks on the set of taxa $X\uplus\\{\\#\\}$, where we declare that the leaf
labeled by $\\{\\#\\}$ is the “root” of the network. This provides a bijection
between unrooted level-1 networks on the set of taxa $X\uplus\\{\\#\\}$ and
pointed level-1 networks on $X$, that have a root labeled by $\\{\\#\\}$.
Therefore, there are as many unrooted level-1 networks on the set of taxa
$X\uplus\\{\\#\\}$ as pointed level-1 networks on $X$ rooted in a leaf labeled
by $\\#\notin X$. Hence $g_{n}$ is the number of pointed level-1 networks with
$n$ leaves in addition to the root.

In a pointed level-1 network $N$ (with at least two leaves), we consider the
other extremity of the edge to which the root belongs. This vertex may belong
to a cycle or not. In the latter case, $N$ is simply described as an unordered
pair of two pointed level-1 networks. In the former case, it is described as a
non-oriented sequence of at least two pointed level-1 networks. Taking into
account the trivial pointed level-1 network with one leaf, a specification for
the pointed level-1 networks is therefore the one shown in Fig. 2, where an
arrow labeled by _sym_ indicates that there is a symmetry w.r.t. the vertical
axis to take into account, and the dashed edge corresponds to an edge or a
path with internal vertices that are incident with cut-edges, themselves
identified with edges of other pointed level-1 networks, the vertex lying on
the cycle being identified with a leaf of corresponding network.

#$\biguplus$$=$${\mathcal{G}}$#${\mathcal{G}}$${\mathcal{G}}$$\tiny{\overleftrightarrow{{sym}}}$ | $\biguplus$ | #$\mathcal{G}$$\mathcal{G}$$\tiny{\overleftrightarrow{{sym}}}$
---|---|---
Figure 2. The combinatorial specification for unrooted level-1 networks
(a.k.a. galled trees).

Thanks to the “dictionary”, the generating function therefore satisfies
$G(z)=z+\frac{1}{2}G(z)^{2}+\frac{1}{2}\frac{G(z)^{2}}{1-G(z)}$ as claimed by
Theorem 1. The second statement about $G(z)$ in Theorem 1 is obtained by
simple algebraic manipulations.

From $G(z)=z\phi(G(z))$, where
$\phi(z)=\frac{1}{1-\frac{1}{2}z(1+\frac{1}{1-z})}$, we can apply Lagrange
inversion to find $g_{n}$. Indeed,
$g_{n}=n![z^{n}]G(z)=(n-1)![z^{n-1}]\phi(z)^{n}$.

Recall the following development of $(1-z)^{-n}$, for any $n\geq 1$, which
will be used here and several times later on:

(2) $\left(\frac{1}{1-z}\right)^{n}=\sum_{i\geq
0}{{n+i-1}\choose{i}}z^{i}\textrm{.}$

Applying this identity twice and the binomial theorem, we get that

$\displaystyle\phi(z)^{n}=$ $\displaystyle\sum_{i\geq
0}{{n+i-1}\choose{i}}\left(\frac{1}{2}z\left(1+\frac{1}{1-z}\right)\right)^{i}$
$\displaystyle=$ $\displaystyle\sum_{i\geq
0}{{n+i-1}\choose{i}}\left(1+\sum_{k=1}^{i}\sum_{p\geq
0}{{i}\choose{k}}{{k+p-1}\choose{p}}z^{p}\right)\frac{1}{2^{i}}z^{i}$
$\displaystyle=$ $\displaystyle\sum_{i\geq
0}{{n+i-1}\choose{i}}\frac{z^{i}}{2^{i}}+\sum_{i\geq
0}\sum_{k=1}^{i}\sum_{p\geq
0}{{n+i-1}\choose{i}}{{i}\choose{k}}{{k+p-1}\choose{p}}\frac{z^{i+p}}{2^{i}}\textrm{.}$

It follows that

$\displaystyle[z^{n-1}]\phi(z)^{n}=$
$\displaystyle{{2n-2}\choose{n-1}}\frac{1}{2^{n-1}}+\sum_{i=0}^{n-1}\sum_{k=1}^{i}\frac{1}{2^{i}}{{n+i-1}\choose{i}}{{i}\choose{k}}{{n+k-i-2}\choose{n-i-1}}$
$\displaystyle\textrm{ and }g_{n}=$
$\displaystyle\frac{(2n-2)!}{2^{n-1}(n-1)!}+\sum_{1\leq k\leq i\leq
n-1}\frac{(n+i-1)!(n+k-i-2)!}{k!(k-1)!(i-k)!(n-i-1)!}2^{-i}\textrm{.}$

∎

###  4.2. Asymptotic evaluation

From Theorem 1, we can furthermore derive an asymptotic evaluation of the
number $g_{n}$ of unrooted level-1 networks on $(n+1)$ leaves, using Theorem
3.3.

######  Proposition 4.2.

The number $g_{n}$ of unrooted level-1 networks on $(n+1)$ leaves is
asymptotically equivalent to $c_{1}\cdot c_{2}^{n}\cdot n^{n-1}$ for constants
$c_{1}$ and $c_{2}$ such that $c_{1}\approx 0.20748$ and $c_{2}\approx
1.89004$.

###### Proof.

Recall that $G(z)$ satisfies $G(z)=z\phi(G(z))$, where
$\phi(z)=\frac{1}{1-\frac{1}{2}z(1+\frac{1}{1-z})}$. Equivalently, this can be
rewritten as $\phi(z)=\frac{2-2z}{z^{2}-4z+2}$. So, $\phi(z)$ is a rational
fraction, whose pole with smallest absolute value is $2-\sqrt{2}\approx
0.5858$. As such, $\phi(z)$ is analytic at $0$, with radius of convergence
$R=2-\sqrt{2}$. Moreover, owing to footnote 3, $\phi(z)$ is aperiodic.
Finally, the characteristic equation $\phi(z)-z\phi^{\prime}(z)=0$ can be
numerically solved (see companion Maple worksheet), showing that it admits a
unique solution in the disk of convergence of $\phi$, namely $\tau\approx
0.34270$. Therefore, the hypotheses of Theorem 3.3 are all satisfied, and
denoting $\rho=\frac{\tau}{\phi(\tau)}\approx 0.19464$, Theorem 3.3 gives:

$[z^{n}]G(z)\sim\sqrt{\frac{\phi(\tau)}{2\phi^{\prime\prime}(\tau)}}\frac{\rho^{-n}}{\sqrt{\pi
n^{3}}}\textrm{.}$

Using the Stirling estimate of the factorial
$n!\sim\left(\frac{n}{e}\right)^{n}\sqrt{2\pi n}$, we get:

$g_{n}\sim\left(\frac{n}{e}\right)^{n}\sqrt{2\pi
n}\sqrt{\frac{\phi(\tau)}{2\phi^{\prime\prime}(\tau)}}\frac{\rho^{-n}}{\sqrt{\pi
n^{3}}}\sim\frac{n^{n-1}}{(e\rho)^{n}}\sqrt{\frac{\phi(\tau)}{\phi^{\prime\prime}(\tau)}}\textrm{.}$

Replacing $\tau$ and $\rho$ by their numerical approximations, we obtain the
announced result. ∎

###  4.3. Refined enumeration and asymptotic distribution of parameters

From the specification of pointed level-$1$ networks seen in the proof of
Theorem 1, it follows easily, as done in [SS06], that the multivariate
generating function
$G(z,x,y)=\sum_{n,k,m}\tfrac{g_{n,k,m}}{n!}z^{n}x^{k}y^{m}$, where $g_{n,k,m}$
is the number of unrooted level-$1$ networks with $n+1$ leaves, $k$ cycles,
and $m$ inner edges, satisfies

(3)
$G(z,x,y)=z+\frac{1}{2}G(z,x,y)^{2}+\frac{1}{2}xy^{3}\frac{G(z,x,y)^{2}}{1-yG(z,x,y)}.$

This equation can be rewritten as $G(z,x,y)=z\phi(G(z,x,y),x,y)$ where $\phi$
is defined by
$\phi(z,x,y)=\tfrac{1}{1-\frac{1}{2}z\left(1+\frac{xy^{3}}{1-yz}\right)}$. As
done in [SS06], we can apply the Lagrange inversion formula to obtain an
explicit expression for $g_{n,k,m}$ – see [SS06, Thm. 4].

Using Theorem 3.4, the above equation may also be used to prove that the
parameters “number of cycles” and “number of inner edges” are both
asymptotically normally distributed.

######  Proposition 4.3.

Let $X_{n}$ (resp. $Y_{n}$) be the random variable counting the number of
cycles (resp. inner edges) in unrooted level-$1$ networks with $n+1$ leaves.
Both $X_{n}$ and $Y_{n}$ are asymptotically normally distributed, and more
precisely, we have

$\mathbb{E}{X_{n}}=\mu_{X}n+O(1),\;\;\;\;\;\;\mathbb{V}ar{X_{n}}=\sigma_{X}^{2}n+O(1)\;\;\;\;and\;\;\;\;\;\dfrac{X_{n}-\mathbb{E}{X_{n}}}{\sqrt{\mathbb{V}ar{X_{n}}}}\xrightarrow{d}\mathcal{N}(0,1),$
$\mathbb{E}{Y_{n}}=\mu_{Y}n+O(1),\;\;\;\;\;\;\mathbb{V}ar{Y_{n}}=\sigma_{Y}^{2}n+O(1)\;\;\;\;and\;\;\;\;\;\dfrac{Y_{n}-\mathbb{E}{Y_{n}}}{\sqrt{\mathbb{V}ar{Y_{n}}}}\xrightarrow{d}\mathcal{N}(0,1),$

where $\mu_{X}\approx 0.46$, $\sigma_{X}^{2}\approx 0.18$, $\mu_{Y}\approx
1.61$ and $\sigma_{Y}^{2}\approx 1.44$.

###### Proof.

Consider first $X_{n}$. Defining $G(z,x):=G(z,x,1)$, it holds that

$\mathbb{E}x^{X_{n}}=\dfrac{[z^{n}]G(z,x)}{[z^{n}]G(z,1)}.$

It follows from the equation for $G(z,x,y)$ that $G(z,x)=F(G(z,x),z,x)$, where
$F$ is defined by
$F(G,z,x)=z\frac{1}{1-\frac{1}{2}G\left(1+\frac{x}{1-G}\right)}$. Being
rational, we see immediately that $F(G,z,x)$ is analytic in $G$, $z$ and $x$
around $0$. Moreover, performing the substitution $z=0$ (resp. $G=0$) gives
$F(G,0,x)=0$ (resp. $F(0,z,x)=z$, which is not identically $0$). Finally, it
is readily checked that $F$ satisfies $[z^{n}G^{m}]F(G,z,1)\geq 0$ for all
$n,m$ (noting for instance that $F$ is obtained using several times the quasi-
inverse operator $A\mapsto\frac{1}{1-A}$, which has a combinatorial
counterpart, as seen in Proposition 3.1). In addition, we can determine
numerically that the system

$\displaystyle G=$ $\displaystyle F(G,z,1)$ $\displaystyle 1=$ $\displaystyle
F_{G}(G,z,1)$

admits a solution $(G_{0},z_{0})$ such that $G_{0}\approx 0.3427$ and
$z_{0}\approx 0.1946$, which satisfies the hypothesis of Theorem 3.4 (see the
companion Maple worksheet to determine the solution and to check it satisfies
the required hypotheses). The result then follows from Theorem 3.4, and the
numerical estimates of $\mu_{X}$ and $\sigma_{X}^{2}$ are obtained plugging
the numerical estimates for $G_{0}$ and $z_{0}$ into the explicit formulas
given by Theorem 3.4 (see again companion Maple worksheet for details). The
proof for $Y_{n}$ follows the exact same steps, considering this time
$G(z,y):=G(z,1,y)$ instead, and adjusting the definition of $F$ accordingly.
As expected, the solution $(G_{0},z_{0})$ of the associated system is the same
as above. ∎

######  Remark 4.4.

In the above proof of Proposition 4.2 (resp. Proposition 4.3), we have
provided some details on how Theorem 3.3 (resp. Theorem 3.4) was used and on
how its hypotheses were checked. This is omitted in later proofs using Theorem
3.3 (see Propositions 5.3, 6.2 and 7.2) or Theorem 3.4 (see Propositions 4.3,
5.5 and 6.3), since they work following the exact same steps. Note also that
all numerical resolutions of equations are done in the companion Maple
worksheet.

##  5\. Counting rooted level-1 networks

###  5.1. Combinatorial specification and generating function

As for unrooted level-1 networks, we start by a combinatorial specification
that describes rooted level-1 networks (also called rooted galled trees).
Because every cycle in a rooted level-1 network not only has a tree vertex
above all other vertices of the cycle, but also a reticulation vertex which is
below all other vertices of the cycle, notice that these objects are different
from the pointed level-1 networks that we considered in the proof of Theorem
1.

Recall that each cycle of a level-1 network has strictly more than one
outgoing arc (otherwise there would be an infinite number of level-1 networks
on $n$ taxa).

Let us denote by $\mathcal{R}$ the set of rooted level-1 networks. The size of
a network of $\mathcal{R}$ is the number of its leaves. Distinguishing on the
level (0 or 1) of the bridgeless component containing its root, a network of
$\mathcal{R}$ is described in exactly one of the following ways. It may be:

  * •

a single leaf (case $0a$);

  * •

a binary root vertex with two children that are roots of networks of
$\mathcal{R}$, whose left-to-right order is irrelevant (case $0b$);

  * •

a cycle containing the root with at least two outgoing cut arcs leading to
networks of $\mathcal{R}$. This last possibility splits into two subcases,
since the reticulation vertex of the cycle may be a child of the root:

    * –

a cycle whose reticulation vertex is attached to a network of $\mathcal{R}$,
is a child of the root and is the lowest vertex of a path coming from the
root, where a sequence of at least one network of $\mathcal{R}$ is attached
(case $1a$);

    * –

a cycle whose reticulation vertex is attached to a network of $\mathcal{R}$,
and such that a sequence of at least one network of $\mathcal{R}$ is attached
to each path of this cycle, the left-to-right order of these two paths being
irrelevant (case $1b$).

The specification for $\mathcal{R}$ is therefore the one given in Fig. 3.

${\mathcal{R}}$${\mathcal{R}}$$\tiny{\overleftrightarrow{{sym}}}$${\mathcal{R}}$${\mathcal{R}}$$\tiny{\overleftrightarrow{{sym}}}$$\biguplus$$\biguplus$$\biguplus$$\bullet$$=$${\mathcal{R}}$Cases:$0a$$0b$$1a$$1b$
Figure 3. The combinatorial specification for rooted level-1 networks. (In
this picture, all arcs are directed downwards, the thick arcs each represent a
directed path which contains at least one internal vertex incident with a cut
arc.)

Denoting $r_{n}$ the number of rooted level-1 networks on $n$ leaves, and
$R(z)=\sum_{n\geq 0}r_{n}\frac{z^{n}}{n!}$ the associated exponential
generating function, we deduce from the specification that

$R=z+\frac{1}{2}R^{2}+\frac{R^{2}}{1-R}+\frac{R}{2}\left(\frac{R}{1-R}\right)^{2}\textrm{.}$

Unlike for the other generating functions considered in this paper, the above
equation for $R$ allows to find a closed formula for $R$. Indeed, the above
equation has four solutions that can be made explicit with the help of a
solver. We can further notice that evaluating the generating function $R(z)$
at $z=0$, we must obtain $R(0)=r_{0}=0$. Among the four candidate solutions
for $R$, we therefore select the only one which has value 0 for $z=0$ and
obtain an explicit form for $R(z)$, given in Theorem 5.1.

######  Theorem 5.1.

The exponential generating function $R(z)$ of rooted level-1 networks is
expressed as

$R(z)=-\frac{\sqrt{2}\sqrt{-4(\sqrt{1-8z}-2)z+9\sqrt{1-8z}-1}}{4(1-8z)^{\frac{1}{4}}}-\frac{1}{4}\sqrt{1-8z}+\frac{5}{4}$

within its disk of convergence of radius $\frac{1}{8}$.

###  5.2. Exact enumeration formula

The first terms of the sequence $(r_{0},r_{1},r_{2},\ldots)$ can be read on
the Taylor expansion of $R(z)$, and have been collected in Table 2:

$R(z)=z+3\frac{z^{2}}{2!}+36\frac{z^{3}}{3!}+723\frac{z^{4}}{4!}+20280\frac{z^{5}}{5!}+o(z^{5})\textrm{.}$

More generally, we have:

######  Proposition 5.2.

For any $n\geq 1$, the number $r_{n}$ of rooted level-1 networks with $n$
leaves is given by

$\frac{(2n-2)!}{2^{n-1}(n-1)!}+\sum_{1\leq k\leq i\leq n-1\atop 0\leq p\leq
k}\frac{(n+i-1)!(n+k-i-2)!\quad
2^{p-i}}{(i-k)!(k-p)!p!(n-1-i-k+p)!(2k-p-1)!}\textrm{.}$

###### Proof.

To obtain a generic formula for $r_{n}$, we apply the Lagrange inversion
formula, rewriting $R(z)$ as $R(z)=z\phi(R(z))\textrm{ where
}\phi(z)=\frac{1}{1-\frac{1}{2}z-\frac{z}{1-z}-\frac{1}{2}\left(\frac{z}{1-z}\right)^{2}}\textrm{.}$

Using twice the usual development of $(1-z)^{-n}$ (for $n\geq 1$) which we
recalled in Eq. (2) and twice the binomial theorem, we obtain that

$\displaystyle\phi(z)^{n}=$ $\displaystyle\sum_{i\geq
0}{{n+i-1}\choose{i}}\frac{z^{i}}{2^{i}}$ $\displaystyle+$
$\displaystyle\sum_{i\geq 0}\sum_{k=1}^{i}\sum_{p=0}^{k}\sum_{j\geq
0}{{n+i-1}\choose{i}}{{i}\choose{k}}{{k}\choose{p}}{{2k-p+j-1}\choose{j}}\frac{z^{i+k-p+j}}{2^{i-p}}\textrm{,}$

and we deduce that

$\displaystyle r_{n}$
$\displaystyle=n![z^{n}]R(z)=n!\frac{1}{n}[z^{n-1}]\phi(z)^{n}=(n-1)![z^{n-1}]\phi(z)^{n}$
$\displaystyle=\frac{(2n-2)!}{2^{n-1}(n-1)!}$ $\displaystyle+\sum_{1\leq k\leq
i\leq n-1\atop 0\leq p\leq
k}\frac{(n+i-1)!(n+k-i-2)!}{(i-k)!(k-p)!p!(n-1-i-k+p)!(2k-p-1)!}2^{p-i}$

as announced. ∎

###  5.3. Asymptotic evaluation

The equation for $R(z)$ also enables us to derive an asymptotic estimate of
$r_{n}$.

######  Proposition 5.3.

The number $r_{n}$ of rooted level-1 networks on $n$ leaves is asymptotically
equivalent to $c_{1}\cdot c_{2}^{n}\cdot n^{n-1}$ for
$c_{1}=\frac{\sqrt{34}(\sqrt{17}-1)}{136}\approx 0.1339$ and
$c_{2}=\frac{8}{e}\approx 2.943$.

###### Proof.

Recall that $R(z)=z\phi(R(z))\textrm{ where
}\phi(z)=\frac{1}{1-\frac{1}{2}z-\frac{z}{1-z}-\frac{1}{2}\left(\frac{z}{1-z}\right)^{2}}$
so that we can apply the Singular Inversion Theorem. Unlike in the case of
unrooted level-1 networks, the solution $\tau$ of the characteristic equation
$\phi(z)-z\phi^{\prime}(z)=0$ to be considered has a nice explicit expression
here, and we have $\tau=\frac{5-\sqrt{17}}{4}$. We obtain
$\rho=\frac{\tau}{\phi(\tau)}=\frac{1}{8}$ and
$\sqrt{\frac{\phi(\tau)}{2\phi^{\prime\prime}(\tau)}}=\frac{\sqrt{17}(\sqrt{17}-1)}{136}$.
Consequently, from Theorem 3.3 we have:

$[z^{n}]R(z)\sim\frac{\sqrt{17}(\sqrt{17}-1)}{136}\frac{8^{n}}{\sqrt{\pi
n^{3}}}\textrm{.}$

Since $r_{n}=n![z^{n}]R(z)$, using the Stirling estimate of the factorial, we
finally get:

$r_{n}\sim\frac{\sqrt{34}(\sqrt{17}-1)}{136}\left(\frac{8}{e}\right)^{n}n^{n-1}\textrm{.}\hfill$

∎

Notice that with the explicit expression of the generating function $R(z)$ in
Theorem 5.1, another way of proving Proposition 5.3 would have been to use the
Transfer Theorem (Corollary VI.1 of [FS08]). We do not enter the details of
this other method here, but we can check that it gives the same result.

###  5.4. Refined enumeration formula

As in the work of Semple and Steel [SS06], we can refine the enumeration of
rooted level-1 networks according to two additional parameters, which are
typical of the “level-1” nature of our networks: their number of cycles and
their total number of arcs among cycles. To do so, let us introduce the
multivariate generating function
$R(z,x,y)=\sum\frac{r(n,k,m)}{n!}z^{n}x^{k}y^{m}$, where $r(n,k,m)$ is the
number of rooted level-1 networks with $n$ leaves, $k$ cycles and $m$ inner
arcs (i.e. the total number of arcs inside those $k$ cycles is $m$). The
specification for $\mathcal{R}$ translates into the following equation for
$R=R(z,x,y)$:

(4)
$R=z+\frac{1}{2}R^{2}+x\frac{R^{2}y^{3}}{1-yR}+xR\frac{1}{2}\left(\frac{Ry^{2}}{1-yR}\right)^{2}\textrm{.}$

The equation can be rewritten as follows:

$R=z\phi(R,x,y)\textrm{ where
}\phi(z,x,y)=\frac{1}{1-\frac{1}{2}z-x\frac{zy^{3}}{1-yz}-\frac{1}{2}xy^{4}\left(\frac{z}{1-yz}\right)^{2}}\textrm{.}$

Applying the Lagrange inversion formula again, we have

$\frac{r(n,k,m)}{n!}=[z^{n}x^{k}y^{m}]R(z,x,y)=\frac{1}{n}[z^{n-1}x^{k}y^{m}]\phi(z,x,y)^{n},$

and by the exact same steps of computation as in the proof of Proposition 5.2,
we get:

######  Proposition 5.4.

The number $r(n,k,m)$ of level-1 networks with $n$ leaves, $k$ cycles and $m$
inner arcs (with $k\geq 1$ and $m\geq 1$) is

$r(n,k,m)=\sum_{p=0}^{k}\frac{(2n+3k-m-2)!(m-2k-1)!2^{p+m+1-n-3k}}{(n+2k-m-1)!p!(k-p)!(m-4k+p)!(2k-p-1)!}\textrm{.}$

Notice that from $r_{n}=r(n,0,0)+\sum_{k=1}^{n-1}\sum_{m=3k}^{n+2k-1}r(n,k,m)$
and the above theorem, we can recover Proposition 5.2 by the change of
variable $m=n+3k-i-1$.

###  5.5. Asymptotic distribution of parameters

As we have seen with Proposition 4.3, the equation for the refined generating
function does not only give access to the explicit formula of Proposition 5.4
above, but also allows to prove that the two parameters of interest are each
asymptotically normally distributed.

######  Proposition 5.5.

Let $X_{n}$ (resp. $Y_{n}$) be the random variable counting the number of
cycles (resp. inner arcs) in rooted level-$1$ networks with $n$ leaves. Both
$X_{n}$ and $Y_{n}$ are asymptotically normally distributed, and more
precisely, we have

$\mathbb{E}{X_{n}}=\mu_{X}n+O(1),\;\;\;\;\;\;\mathbb{V}ar{X_{n}}=\sigma_{X}^{2}n+O(1)\;\;\;\;and\;\;\;\;\;\dfrac{X_{n}-\mathbb{E}{X_{n}}}{\sqrt{\mathbb{V}ar{X_{n}}}}\xrightarrow{d}\mathcal{N}(0,1),$
$\mathbb{E}{Y_{n}}=\mu_{Y}n+O(1),\;\;\;\;\;\;\mathbb{V}ar{Y_{n}}=\sigma_{Y}^{2}n+O(1)\;\;\;\;and\;\;\;\;\;\dfrac{Y_{n}-\mathbb{E}{Y_{n}}}{\sqrt{\mathbb{V}ar{Y_{n}}}}\xrightarrow{d}\mathcal{N}(0,1),$

where $\mu_{X}\approx 0.56$, $\sigma_{X}^{2}\approx 0.18$, $\mu_{Y}\approx
1.93$ and $\sigma_{Y}^{2}\approx 1.24$.

###### Proof.

Recall that, defining
$\phi(z,x,y)=\frac{1}{1-\frac{1}{2}z-x\frac{zy^{3}}{1-yz}-\frac{1}{2}xy^{4}\left(\frac{z}{1-yz}\right)^{2}}$,
$R(z,x,y)$ satisfies $R=z\phi(R,x,y)$. We focus first on $X_{n}$, setting
$y=1$, and we consider $R(z,x):=R(z,x,1)$. It holds that

$\mathbb{E}x^{X_{n}}=\dfrac{[z^{n}]R(z,x)}{[z^{n}]R(z,1)}.$

Defining the function $F$ by $F(R,z,x)=z\phi(R,x,1)$, it also holds that
$R(z,x)=F(R(z,x),z,x)$. It is readily checked that $F$ satisfies all
hypotheses of Theorem 3.4. Moreover, the system

$\displaystyle R=$ $\displaystyle F(R,z,1)$ $\displaystyle 1=$ $\displaystyle
F_{R}(R,z,1)$

admits a solution $(R_{0},z_{0})$ with $z_{0}=1/8$ and $R_{0}\approx 0.2192$,
which satisfies the hypothesis of Theorem 3.4. The result and numerical
estimates of $\mu_{X}$ and $\sigma_{X}^{2}$ then follow from Theorem 3.4.

For $Y_{n}$ instead of $X_{n}$, the proof works in the exact same way,
considering this time $R(z,y):=R(z,1,y)$ instead, and adjusting the definition
of $F$ accordingly. As in the proof of Proposition 4.3, we find the same
solution $(R_{0},z_{0})$ of the associated system, as it should be. ∎

##  6\. Counting unrooted level-2 networks

###  6.1. Combinatorial specification

First of all, let us recall that any bridgeless component in an unrooted
level-2 network contains at least three vertices incident with a cut-edge
(since otherwise there would be an infinite number of such networks with a
given number of leaves).

As in the case of level-1 unrooted networks, we consider _pointed_ level-2
networks, that are unrooted level-2 networks equipped with a fictitious root,
which is a new leaf labeled by the special taxa $\\#$. This provides a
bijection between unrooted level-2 networks on the set of taxa
$X\uplus\\{\\#\\}$ and pointed level-2 networks on $X$. Therefore, there are
as many unrooted level-2 networks of the set of taxa $X\uplus\\{\\#\\}$ as
pointed level-2 networks on $X$ rooted in a leaf labeled by $\\#\notin X$.
Notice that pointed level-2 networks do not correspond to classical rooted
level-2 networks. Indeed, every bridgeless component in a pointed level-2
network has a distinguished vertex which could be considered as the equivalent
of a root, but no reticulation vertices, whereas it has both in the usual
definition of rooted level-2 networks.

Let us denote by $\mathcal{U}$ the set of such pointed level-2 networks, the
size of a network of $\mathcal{U}$ being the number of its leaves different
from the root. Let $u_{n}$ be the number of networks of size $n$ in
$\mathcal{U}$. The above argument shows that $u_{n}$ counts the number of
unrooted level-2 networks on $(n+1)$ leaves. We introduce $U(z)=\sum_{n\geq
0}u_{n}\frac{z^{n}}{n!}$ the associated exponential generating function.

To obtain a combinatorial specification for $\mathcal{U}$, and hence an
equation satisfied by $U(z)$, we describe the possible shapes of a network $N$
of $\mathcal{U}$, depending on the level (0, 1 or 2) of the bridgeless
component that contains the neighbouring vertex of the fictitious root.

Let $v$ be the neighbor of the fictitious root. Then we have the following
cases to consider, depending on the level of the bridgeless component that
contains $v$.

  * •

The first case is that $v$ is a leaf.

  * •

If $v$ does not belong to a cycle nor to a bridgeless component of level 2,
then $N$ is described as an unordered pair of two pointed level-2 networks.

  * •

If $v$ belongs to a cycle but not to a bridgeless component of level 2, then
$N$ is described as an unoriented sequence of at least two pointed level-2
networks.
(These first three cases are the same as in Section 5.)

  * •

The last possibility is that $v$ belongs to a bridgeless component of level 2.
The underlying level-2 generator, $G$, is necessarily of the shape #. In this
case, we distinguish many cases in Section 8.1 of the Appendix, depending on
whether each edge of the level-2 generator contains exactly one vertex
incident with a cut-edge, several or none.

###  6.2. Generating function

The specification is directly translated into the following equation for the
generating function $U$ (see the Appendix for details):

$\displaystyle{U}$
$\displaystyle=z+\frac{{U}^{2}}{2}+\frac{{U}^{2}}{2(1-{U})}+\frac{{U}^{2}}{2(1-{U})}+\frac{3}{2}{U}^{2}+\frac{5{U}^{3}}{2(1-{U})}+\frac{5{U}^{4}}{4(1-{U})^{2}}+{U}^{3}+\frac{3{U}^{4}}{1-{U}}$
$\displaystyle+\frac{3{U}^{5}}{(1-{U})^{2}}+\frac{{U}^{6}}{(1-{U})^{3}}+\frac{{U}^{4}}{4}+\frac{{U}^{5}}{1-{U}}+\frac{3{U}^{6}}{2(1-{U})^{2}}+\frac{{U}^{7}}{(1-{U})^{3}}+\frac{{U}^{8}}{4(1-{U})^{4}}.$

This equation for the generating function allows to derive the first
coefficients of the series expansion of $U(z)$, namely:

${U}(z)=z+3z^{2}+\frac{45}{2}z^{3}+\frac{421}{2}z^{4}+\frac{8809}{4}z^{5}+\cdots.$

The corresponding first values of $u_{n}$ have been included in Table 2.
(Recall indeed that $U(z)=\sum_{n\geq 0}u_{n}\frac{z^{n}}{n!}$ and that
$u_{n}$ is the number of unrooted level-2 networks on $(n+1)$ leaves).

The above equation for $U(z)$ can also be rewritten as follows:

######  Theorem 6.1.

The generating function $U(z)$ satisfies:

$U(z)=z\phi(U(z))\textrm{ where
}\phi(z)=\frac{1}{1-\frac{3z^{5}-16z^{4}+32z^{3}-30z^{2}+12z}{4(1-z)^{4}}}\textrm{.}$

###### Proof.

This is simply obtained from the above equation for $U$ by algebraic
manipulations. ∎

###  6.3. Exact enumeration formula

To obtain a closed form for $u_{n}$, we start from the equation for $U$ given
in Theorem 6.1. By the Lagrange inversion formula we obtain that:

$u_{n}=n![z^{n}]U(z)=\frac{n!}{n}[z^{n-1}]\phi^{n}(z)=(n-1)![z^{n-1}]\phi^{n}(z),$

so, to compute the first values of $u_{n}$, we can compute the Taylor
expansions of $\phi^{n}(z)$ and get the values in Table 2.

As for the case of level-1 networks, we may also deduce with routine algebra
an explicit formula for $u_{n}$. This formula being however rather involved,
we provide it only in Appendix.

###  6.4. Asymptotic evaluation

From Theorem 6.1, we can furthermore derive an asymptotic evaluation of the
number $u_{n}$ of unrooted level-2 networks on $(n+1)$ leaves, using Theorem
3.3.

######  Proposition 6.2.

The number $u_{n}$ of unrooted level-2 networks on $(n+1)$ leaves is
asymptotically equivalent to $c_{1}\cdot c_{2}^{n}\cdot n^{n-1}$ for constants
$c_{1}$ and $c_{2}$ such that $c_{1}\approx 0.07695$ and $c_{2}\approx
5.4925$.

###### Proof.

Denoting by $\tau\approx 0.12117$ the unique solution of the characteristic
equation $\phi(z)-z\phi^{\prime}(z)=0$ in the disk of convergence of $\phi$,
and $\rho=\frac{\tau}{\phi(\tau)}\approx 0.06698$, we have:

$[z^{n}]U(z)\sim\sqrt{\frac{\phi(\tau)}{2\phi^{\prime\prime}(\tau)}}\frac{\rho^{-n}}{\sqrt{\pi
n^{3}}}\textrm{.}$

Using the Stirling estimate of the factorial, we get:

$u_{n}\sim\left(\frac{n}{e}\right)^{n}\sqrt{2\pi
n}\sqrt{\frac{\phi(\tau)}{2\phi^{\prime\prime}(\tau)}}\frac{\rho^{-n}}{\sqrt{\pi
n^{3}}}\sim\frac{n^{n-1}}{(e\rho)^{n}}\sqrt{\frac{\phi(\tau)}{\phi^{\prime\prime}(\tau)}}\textrm{.}$

Replacing $\tau$ and $\rho$ by their numerical approximations, we get the
announced result. ∎

###  6.5. Refined enumeration formula and asymptotic distribution of
parameters

Consider the refined generating function ${U}(z,x,y)$ for unrooted level-2
networks, where the variable $z$ counts the size as before, the variable $x$
counts the number of bridgeless components of level 1 or 2 (or equivalently,
the number of level-1 or level-2 generators in the decomposition of these
networks), and the variable $y$ counts the number of inner edges, defined as
the total number of edges across all level-1 and level-2 bridgeless
components. The specification provided in the Appendix can be refined for
these statistics, yielding the following equation for $U:={U}(z,x,y)$:

$\displaystyle{U}=z$
$\displaystyle+\frac{{U}^{2}}{2}+\frac{xy^{3}{U}^{2}}{2(1-y{U})}+\frac{xy^{6}{U}^{2}}{2(1-y{U})}+\frac{3}{2}xy^{6}{U}^{2}+\frac{5xy^{7}{U}^{3}}{2(1-y{U})}+\frac{5xy^{8}{U}^{4}}{4(1-y{U})^{2}}$
$\displaystyle+xy^{7}{U}^{3}+\frac{3xy^{8}{U}^{4}}{1-y{U}}+\frac{3xy^{9}{U}^{5}}{(1-y{U})^{2}}+\frac{xy^{10}{U}^{6}}{(1-y{U})^{3}}+\frac{xy^{8}{U}^{4}}{4}+\frac{xy^{9}{U}^{5}}{1-y{U}}$
(5)
$\displaystyle+\frac{3xy^{10}{U}^{6}}{2(1-y{U})^{2}}+\frac{xy^{11}{U}^{7}}{(1-y{U})^{3}}+\frac{xy^{12}{U}^{8}}{4(1-y{U})^{4}}.$

From the above equation, and similarly to Proposition 5.4, it would be
possible (although computations and result are not reported in this paper) to
derive an explicit formula for the number of unrooted level-2 networks with
$n$ leaves, $k$ bridgeless components of level 1 or 2, and $m$ edges across
them. Furthermore, some information on the asymptotic behavior of these
parameters can be obtained from Eq. (5).

######  Proposition 6.3.

Let $X_{n}$ (resp. $Y_{n}$) be the random variable counting the number of
level-1 or level-2 bridgeless components (resp. the number of edges across
them) in unrooted level-$2$ networks with $n+1$ leaves. Both $X_{n}$ and
$Y_{n}$ are asymptotically normally distributed, and more precisely, we have

$\mathbb{E}{X_{n}}=\mu_{X}n+O(1),\;\;\;\;\;\;\mathbb{V}ar{X_{n}}=\sigma_{X}^{2}n+O(1)\;\;\;\;and\;\;\;\;\;\dfrac{X_{n}-\mathbb{E}{X_{n}}}{\sqrt{\mathbb{V}ar{X_{n}}}}\xrightarrow{d}\mathcal{N}(0,1),$
$\mathbb{E}{Y_{n}}=\mu_{Y}n+O(1),\;\;\;\;\;\;\mathbb{V}ar{Y_{n}}=\sigma_{Y}^{2}n+O(1)\;\;\;\;and\;\;\;\;\;\dfrac{Y_{n}-\mathbb{E}{Y_{n}}}{\sqrt{\mathbb{V}ar{Y_{n}}}}\xrightarrow{d}\mathcal{N}(0,1),$

where $\mu_{X}\approx 0.69944$, $\sigma_{X}^{2}\approx 0.16919$,
$\mu_{Y}\approx 4.01349$ and $\sigma_{Y}^{2}\approx 4.68675$.

###### Proof.

Consider first $X_{n}$. Defining $U(z,x):=U(z,x,1)$, it holds that

$\mathbb{E}x^{X_{n}}=\dfrac{[z^{n}]U(z,x)}{[z^{n}]U(z,1)}.$

It follows from the equation for $U(z,x,y)$ that
$U(z,x)=F(U(z,x),z,x)=z\frac{1}{1-A(U(z,x),z,x)}$ with

$\displaystyle A(U,z,x)=$
$\displaystyle\frac{{U}}{2}+\frac{x{U}}{2(1-{U})}+\frac{x{U}}{2(1-{U})}+\frac{3x{U}}{2}+\frac{5x{U}^{2}}{2(1-{U})}+\frac{5x{U}^{3}}{4(1-{U})^{2}}+x{U}^{2}$
$\displaystyle+\frac{3x{U}^{3}}{1-{U}}+\frac{3x{U}^{4}}{(1-{U})^{2}}+\frac{x{U}^{5}}{(1-{U})^{3}}+\frac{x{U}^{3}}{4}+\frac{x{U}^{4}}{1-{U}}+\frac{3x{U}^{5}}{2(1-{U})^{2}}$
$\displaystyle+\frac{x{U}^{6}}{(1-{U})^{3}}+\frac{x{U}^{7}}{4(1-{U})^{4}}.$

It is readily checked that $F$ satisfies all hypotheses of Theorem 3.4. The
system

$\displaystyle U=$ $\displaystyle F(U,z,1)$ $\displaystyle 1=$ $\displaystyle
F_{U}(U,z,1)$

admits a solution $(U_{0},z_{0})$ such that $U_{0}\approx 0.1212$ and
$z_{0}\approx 0.06698$, which satisfies the hypothesis of Theorem 3.4. The
result then follows from Theorem 3.4, and the numerical estimates of $\mu_{X}$
and $\sigma_{X}^{2}$ are obtained plugging the numerical estimates for $U_{0}$
and $z_{0}$ into the explicit formulas given by Theorem 3.4. The proof for
$Y_{n}$ follows the exact same steps, considering this time $U(z,y):=U(z,1,y)$
instead, and adjusting the definition of $F$ accordingly. Again, as expected,
the solution $(U_{0},z_{0})$ of the associated system is the same as above. ∎

##  7\. Counting rooted level-2 networks

###  7.1. Combinatorial specification and generating function

To derive a specification for rooted level-2 networks, we distinguish cases
depending on the level ($0$, $1$ or $2$) of the generator to which the root
belongs. The cases corresponding to levels $0$ and $1$ will be the same as in
Section 5. When the root of a rooted level-2 network belongs to a level-$2$
generator, we have to remember that these generators have one vertex which is
above all their other vertices (which is the root of the network) and not just
one but two reticulation vertices. As for rooted level-1 networks, it is
important to keep in mind that any bridgeless component of level $2$ in a
rooted level-2 network has at least two outgoing cut arcs (since otherwise
there would be an infinite number of such networks with a given number of
leaves).

We denote by $\mathcal{L}$ the set of rooted level-2 networks, where the size
corresponds to the number of leaves. And we denote by $L(z)$ the corresponding
exponential generating function. Distinguishing on the level (0, 1 or 2) of
the bridgeless component containing the root, we can see that any network $N$
of $\mathcal{L}$ satisfies exactly one of the following (see Fig. 4).

  * •

$N$ is just a leaf. This contributes $z$ to the generating function (case
$0a$).

  * •

The root of $N$ belongs to a bridgeless component of level 0, that is to say
it is a binary root vertex. Its children are themselves networks of
$\mathcal{L}$ whose left-to-right order is irrelevant. This contributes
$\frac{L^{2}}{2}$ to the generating function (case $0b$).

  * •

The root of $N$ belongs to a bridgeless component of level 1. This case splits
into two subcases, just as in Section 5.

    * –

Either $N$ consists of a cycle whose reticulation vertex is attached to a
network of $\mathcal{L}$, is a child of the root and is the lowest vertex of a
path from the root where a sequence of at least one network of $\mathcal{L}$
is attached. This contributes $\frac{L^{2}}{1-L}$ to the generating function
(case $1a$).

    * –

Or $N$ consists of a cycle whose reticulation vertex is attached to a network
of $\mathcal{L}$, and a sequence of at least one network of $\mathcal{L}$ is
attached to each path of this cycle (case $1b$). This contributes
$\frac{L}{2}\left(\frac{L}{1-L}\right)^{2}$.

  * •

The root of $N$ belongs to a bridgeless component of level 2. The level-2
generators are displayed in Fig. 4, cases $2a$ to $2d$. From these generators,
the networks whose root belong to a bridgeless component of level 2 are
obtained attaching networks of $\mathcal{L}$ to their reticulation vertex or
vertices with out-degree 0, and possibly replacing their arcs with sequences
of at least one network of $\mathcal{L}$. Note that in cases $2b$ and $2d$,
depending on our choices for such arcs, we may have to cope with horizontal
and vertical symmetry. We study these cases in order, and find their
contribution to the generating function $L(z)$.

${\mathcal{L}}$${\mathcal{L}}$$\tiny{\overleftrightarrow{{sym}}}$${\mathcal{L}}$${\mathcal{L}}$$\tiny{\overleftrightarrow{{sym}}}$${\mathcal{L}}$${\mathcal{L}}$$e$$e^{\prime}$$\tiny{\overleftrightarrow{{sym}}}$${\mathcal{L}}$${\mathcal{L}}$${\mathcal{L}}$${\mathcal{L}}$$e_{1}$$e_{1}^{\prime}$$e_{2}$$e_{2}^{\prime}$$e_{3}$$e_{3}^{\prime}$$\tiny{\overleftrightarrow{{sym}}}$$\tiny{sym}$$\biguplus$$\biguplus$$\biguplus$$\biguplus$$\biguplus$$\biguplus$$\biguplus$$\bullet$$=$${\mathcal{L}}$$0a$$0b$$1a$$1b$$2a$$2b$$2c$$2d$
Figure 4. The specification of the class $\mathcal{L}$.

  * –

We first deal with the case where the level-2 generator to which the root
belongs is of type $2a$. This generator has $5$ internal arcs, all
distinguished from each other by the structure of the generator. A network of
$\mathcal{L}$ is attached to its reticulation vertex of out-degree 0.
Moreover, recalling that each bridgeless component must be have at least two
outgoing cut arcs, at least one of the five internal arcs of the generator
must carry a non-empty sequence of networks of $\mathcal{L}$. Therefore, the
contribution of case $2a$ to the generating function of $\mathcal{L}$ is

${L}\cdot\sum_{i=1}^{5}\binom{5}{i}\left(\dfrac{{L}}{1-{L}}\right)^{i}.$

  * –

In the case where the level-2 generator to which the root belongs is of type
$2b$, we similarly have $5$ internal arcs in the generator, at least one of
which must be replaced by a non-empty sequence of networks of $\mathcal{L}$.
However, the two arcs $e$ and $e^{\prime}$ are not distinguishable. The
contribution to the generating function is therefore more subtle to analyze,
and we perform this detailed analysis in the Section 8.2 of the Appendix. The
overall contribution of case $2b$ to the generating function of $\mathcal{L}$
is then shown to be

$\displaystyle{L}\frac{{L}}{1-{L}}+\frac{7}{2}{L}\left(\dfrac{{L}}{1-{L}}\right)^{2}+\frac{9}{2}{L}\left(\dfrac{{L}}{1-{L}}\right)^{3}+\frac{5}{2}{L}\left(\dfrac{{L}}{1-{L}}\right)^{4}+\frac{1}{2}{L}\left(\dfrac{{L}}{1-{L}}\right)^{5}.$

  * –

We now consider the case where the level-2 generator to which the root belongs
is of type $2c$. This generator has $6$ internal arcs, all distinguished from
each other by the structure of the generator. Moreover, two networks of
$\mathcal{L}$ are attached to its reticulation vertices, so that the condition
that each bridgeless component must be have at least two outgoing cut arcs is
already satisfied. Therefore, all $6$ internal arcs of the generator carry
possibly empty sequences of networks of $\mathcal{L}$. As a consequence, the
contribution of case $2c$ to the generating function of $\mathcal{L}$ is

${L}^{2}\left(\dfrac{1}{1-{L}}\right)^{6}.$

  * –

Similarly, when the root belongs to a level-2 generator of type $2d$, the $6$
arcs of the generator carry possibly empty sequences of networks of
$\mathcal{L}$. However, this generator enjoys both a horizontal symmetry
(mapping $e_{i}$ to $e_{i}^{\prime}$ for $i=1,2,3$) and a vertical symmetry
(exchanging the indices $2$ and $3$ and the corresponding pending networks of
$\mathcal{L}$). In case all arcs carry empty sequences, the horizontal
symmetry is actually the identity, so that only the vertical symmetry applies,
yielding a factor $\tfrac{1}{2}$. Otherwise, both the horizontal and the
vertical symmetry need to be taken into account, yielding a factor
$\tfrac{1}{4}$. The total contribution of case $2d$ to the generating function
of $\mathcal{L}$ is therefore

$\frac{1}{2}L^{2}+\dfrac{1}{4}{L}^{2}\cdot\sum_{i=1}^{6}\binom{6}{i}\left(\dfrac{{L}}{1-{L}}\right)^{i}.$

Following this case analysis we obtain an equation characterizing the
generating function of $\mathcal{L}$.

######  Theorem 7.1.

The exponential generating function $L(z)$ of rooted level-2 networks counted
by number of leaves satisfies

$\displaystyle{L}=z$
$\displaystyle+{L}^{2}+\frac{7{L}^{2}}{1-{L}}+\frac{3{L}^{3}}{2(1-{L})}+\frac{14{L}^{3}}{(1-{L})^{2}}+\frac{15{L}^{4}}{4(1-{L})^{2}}+\frac{29{L}^{4}}{2(1-{L})^{3}}+\frac{5{L}^{5}}{(1-{L})^{3}}$
$\displaystyle+\frac{15{L}^{5}}{2(1-{L})^{4}}+\frac{15{L}^{6}}{4(1-{L})^{4}}+\frac{3{L}^{6}}{2(1-{L})^{5}}+\frac{3{L}^{7}}{2(1-{L})^{5}}+\frac{{L}^{2}}{(1-{L})^{6}}+\frac{{L}^{8}}{4(1-{L})^{6}},$

or equivalently

${L}(z)=z\phi({L}(z))\;\;\;where\;\;\;\phi(z)=\dfrac{1}{1-\frac{36z-102z^{2}+159z^{3}-148z^{4}+81z^{5}-24z^{6}+3z^{7}}{4(1-z)^{6}}}.$

We therefore obtain the first terms of the series expansion of $L(z)$,

${L}(z)=z+9z^{2}+\frac{381}{2}z^{3}+\frac{20013}{4}z^{4}+\frac{588119}{4}z^{5}+\frac{37023465}{8}z^{6}+\cdots,$

as reported in Table 2.

###  7.2. Exact enumeration formula

As in the previous sections, Theorem 7.1 allows to derive an explicit formula
for the number $\ell_{n}$ of rooted level-2 phylogenetic networks with $n$
leaves. This complicated formula is given in Appendix.

###  7.3. Asymptotic evaluation

Similarly, from Theorem 7.1, we can also derive the asymptotic behavior of
$\ell_{n}$.

######  Proposition 7.2.

The number $\ell_{n}$ of rooted level-2 phylogenetic networks with $n$ leaves
behaves asymptotically as

$\ell_{n}\sim c_{1}c_{2}^{n}n^{n-1},$

where $c_{1}\approx 0.02931$ and $c_{2}\approx 15.433$.

###### Proof.

Recall that

${L}(z)=z\phi({L}(z))\;\;\;where\;\;\;\phi(z)=\dfrac{1}{1-\frac{36z-102z^{2}+159z^{3}-148z^{4}+81z^{5}-24z^{6}+3z^{7}}{4(1-z)^{6}}}.$

Denoting by $\tau\approx 0.0445$ the unique solution of the characteristic
equation $\phi(z)-z\phi^{\prime}(z)=0$ in the disk of convergence of $\phi$,
and $\rho=\frac{\tau}{\phi(\tau)}\approx 0.0238$, the Singular Inversion
Theorem gives:

$[z^{n}]{L}(z)\sim\sqrt{\frac{\phi(\tau)}{2\phi^{\prime\prime}(\tau)}}\frac{{\rho}^{-n}}{\sqrt{\pi
n^{3}}}\textrm{.}$

Like before, we get the claimed result from $\ell_{n}=n![z^{n}]{L}(z)$ and the
Stirling estimate of the factorial. ∎

###  7.4. Refined enumeration formula and asymptotic distribution of
parameters

Let ${L}(z,x,y)=\sum_{n,k,m}\ell_{n,k,m}\frac{z^{n}}{n!}x^{k}y^{m}$ be the
multivariate generating function counting rooted level-2 networks w.r.t. their
number of leaves (variable $z$), their number of bridgeless components of
level 1 or 2 (variable $x$) and their number of arcs across all these
(variable $y$). From the specification of $\mathcal{L}$ discussed earlier,
${L}(z,x,y)={L}$ is easily seen to satisfy the following equation:

$\displaystyle{L}=z$
$\displaystyle+\frac{{L}^{2}}{2}+x\Big{(}\frac{y^{6}{L}^{2}}{2}+(y^{3}+6y^{6})\frac{{L}^{2}}{1-y{L}}+\frac{3y^{7}{L}^{3}}{2(1-y{L})}+(\tfrac{y^{4}}{2}+\tfrac{27y^{7}}{2})\frac{{L}^{3}}{(1-y{L})^{2}}$
$\displaystyle+\frac{15y^{8}{L}^{4}}{4(1-y{L})^{2}}+\frac{29y^{8}{L}^{4}}{2(1-y{L})^{3}}+\frac{5y^{9}{L}^{5}}{(1-y{L})^{3}}+\frac{15y^{9}{L}^{5}}{2(1-y{L})^{4}}+\frac{15y^{10}{L}^{6}}{4(1-y{L})^{4}}$
(6)
$\displaystyle+\frac{3y^{10}{L}^{6}}{2(1-y{L})^{5}}+\frac{3y^{11}{L}^{7}}{2(1-y{L})^{5}}+\frac{y^{6}{L}^{2}}{(1-y{L})^{6}}+\frac{y^{12}{L}^{8}}{4(1-y{L})^{6}}\Big{)}.$

From the above equation, an explicit formula for $\ell_{n,k,m}$ could
routinely be derived, as in Proposition 5.4, although the computations are
more involved. We decided not to report this formula here. Eq. (6) also allows
to study the asymptotic behavior of the considered parameters.

######  Proposition 7.3.

Let $X_{n}$ (resp. $Y_{n}$) be the random variable counting the number of
bridgeless components of level 1 or 2 (resp. the number of edges across them)
in rooted level-$2$ networks with $n$ leaves. Both $X_{n}$ and $Y_{n}$ are
asymptotically normally distributed, and more precisely, we have

$\mathbb{E}{X_{n}}=\mu_{X}n+O(1),\;\;\;\;\;\;\mathbb{V}ar{X_{n}}=\sigma^{2}_{X}n+O(1)\;\;\;\;$
$\mathbb{E}{Y_{n}}=\mu_{Y}n+O(1),\;\;\;\;\;\;\mathbb{V}ar{Y_{n}}=\sigma^{2}_{Y}n+O(1)\;\;\;\;$

where $\mu_{X}\approx 0.8243$, $\sigma^{2}_{X}\approx 0.1232$, $\mu_{Y}\approx
4.8133$ and $\sigma^{2}_{Y}\approx 3.5523$.

###### Proof.

To prove the result for $X_{n}$ (resp. $Y_{n}$), we specialize Eq. (6) for
$y=1$ (resp. $x=1$) and rewrite it as $L(z,x,1)=F(L(z,x,1),z,x)$ for some
explicit function $F$ (resp. $L(z,1,y)=F(L(z,1,y),z,y)$, for an explicit
different $F$). It is readily checked that $F$ satisfies all hypotheses of
Theorem 3.4, as well as the solutions $(L_{0},z_{0})$ of the system

$\displaystyle L=$ $\displaystyle F(L,z,1)$ $\displaystyle 1=$ $\displaystyle
F_{L}(L,z,1)$

whose approximate values are $L_{0}\approx 0.04447$ and $z_{0}\approx
0.02384$. The result then follows from Theorem 3.4, and the numerical
estimates of $\mu_{X}$ and $\sigma_{X}^{2}$ (resp. $\mu_{Y}$ and
$\sigma_{Y}^{2}$) are obtained plugging the numerical estimates for $L_{0}$
and $z_{0}$ into the explicit formulas given by Theorem 3.4. ∎

## Acknowledgments

This work was supported by a “junior guest” grant by the LABRI and bilateral
Austrian-Taiwanese project FWF-MOST, grants I 2309-N35 (FWF) and
MOST-104-2923- M-009-006-MY3 (MOST). We thank Carine Pivoteau for her insights
about random generation of combinatorial structures as well as two anonymous
reviewers for their useful comments.

## References

  * [BDM12] Alix Boc, Alpha B. Diallo, and Vladimir Makarenkov.  T-rex: a web server for inferring, validating and visualizing phylogenetic trees and networks.  Nucleic Acids Research, 40(W1):W573–W579, 2012.
  * [BGM19] Mathilde Bouvel, Philippe Gambette, and Marefatollah Mansouri.  Counting phylogenetic networks of level $1$ and $2$.  Technical report, Arxiv Preprint, Version 2, 2019.
  * [CHT18] Kuang-Yu Chang, Wing-Kai Hon, and Sharma V. Thankachan.  Compact encoding for galled-trees and its applications.  In 2018 Data Compression Conference, pages 297–306, 2018.
  * [DFLS04] Philippe Duchon, Philippe Flajolet, Guy Louchard, and Gilles Schaeffer.  Boltzmann samplers for the random generation of combinatorial structures.  Combinatorics, Probability and Computing, 13:577–625, 2004.
  * [Drm09] Michael Drmota.  Random Trees.  Springer, 2009.
  * [FGM19] Michael Fuchs, Bernhard Gittenberger, and Marefatollah Mansouri.  Counting phylogenetic networks with few reticulation vertices: Tree-child and normal networks.  Australasian Journal of Combinatorics, 73(2):385–423, 2019.
  * [FS08] Philippe Flajolet and Robert Sedgewick.  Analytic Combinatorics.  Cambridge University Press, 2008.
  * [FZC94] Philippe Flajolet, Paul Zimmermann, and Bernard Van Cutsem.  A calculus for the random generation of labelled combinatorial structures.  Theoretical Computer Science, 132(1-2):1–35, 1994.
  * [GBP09] Philippe Gambette, Vincent Berry, and Christophe Paul.  The structure of level-$k$ phylogenetic networks.  In Twentieth Annual Symposium on Combinatorial Pattern Matching (CPM’09), volume 5577 of Lecture Notes in Computer Science, pages 289–300. Springer, 2009.
  * [GBP12] Philippe Gambette, Vincent Berry, and Christophe Paul.  Quartets and unrooted phylogenetic networks.  Journal of Bioinformatics and Computational Biology, 10(4):1250004.1–1250004.23, 2012.
  * [GRZ18] Andreas DM Gunawan, Jeyaram Rathin, and Louxin Zhang.  Counting and enumerating galled networks, 2018.  arXiv manuscript, https://arxiv.org/abs/1812.08569.
  * [GvIK+16] Philippe Gambette, Leo van Iersel, Steven Kelk, Fabio Pardi, and Celine Scornavacca.  Do branch lengths help to locate a tree in a phylogenetic network?  Bulletin of Mathematical Biology, 78(9):1773–1795, 2016.
  * [HMSW18] Katharina Huber, Vincent Moulton, Charles Semple, and Taoyang Wu.  Quarnet inference rules for level-1 networks.  Bulletin of Mathematical Biology, 80:2137–2153, 2018.
  * [HMW16] Katharina Huber, Vincent Moulton, and Taoyang Wu.  Transforming phylogenetic networks: Moving beyond tree space.  Journal of Theoretical Biology, 404:30–39, 2016.
  * [HvIM+17] Katharina Huber, Leo van Iersel, Vincent Moulton, Celine Scornavacca, and Taoyang Wu.  Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets.  Algorithmica, 77(1):173–200, 2017.
  * [JJE+18] Remie Janssen, Mark Jones, Péter L. Erdös, Leo van Iersel, and Celine Scornavacca.  Exploring the tiers of rooted phylogenetic network space using tail moves.  Bulletin of Mathematical Biology, 80:2177–2208, 2018.
  * [LEC67] Abraham Lempel, Shimon Even, and Israel Cederbaum.  An algorithm for planarity testing of graphs.  In Theory of Graphs: International Symposium, pages 215–232, 1967\.
  * [LV14] Anthony Labarre and Sicco Verwer.  Merging partially labelled trees: hardness and a declarative programming solution.  IEEE/ACM Transactions in Computational Biology and Bioinformatics, 11(2):389–397, 2014.
  * [MSW15] Colin McDiarmid, Charles Semple, and Dominic Welsh.  Counting phylogenetic networks.  Annals of Combinatorics, 19(1):205–224, 2015.
  * [OEI19] OEIS Foundation Inc.  The On-Line Encyclopedia of Integer Sequences.  2019\.  http://oeis.org.
  * [PC01] David Posada and Keith A. Crandall.  Intraspecific gene genealogies: trees grafting into networks.  TEE, 16(1):37–45, 2001.
  * [SS06] Charles Semple and Mike Steel.  Unicyclic networks: compatibility and enumeration.  IEEE/ACM Transactions in Computational Biology and Bioinformatics, 3:398–401, 2006.
  * [vIKK+09] Leo van Iersel, Judith Keijsper, Steven Kelk, Leen Stougie, Ferry Hagen, and Teun Boekhout.  Constructing level-2 phylogenetic networks from triplets.  IEEE/ACM Transactions in Computational Biology and Bioinformatics, 6(4):667–681, 2009.
  * [vIM14] Leo van Iersel and Vincent Moulton.  Trinets encode tree-child and level-2 phylogenetic networks.  Journal of Mathematical Biology, 68(7):1707–1729, 2014.
  * [vIM18] Leo van Iersel and Vincent Moulton.  Leaf-reconstructibility of phylogenetic networks.  SIAM Journal on Discrete Mathematics, 32:2047–2066, 2018.
  * [WTM14] Matthieu Willems, Nadia Tahiri, and Vladimir Makarenkov.  A new efficient algorithm for inferring explicit hybridization networks following the neighbor-joining principle.  Journal of Bioinformatics and Computational Biology, 12(5), 2014\.

##  8\. Appendix

###  8.1. Case analysis for unrooted level-2 generators

In the pictures below, we use thick lines to represent paths containing at
least 2 internal nodes incident with a cut-edge which is incident with another
pointed unrooted level-2 network. We use # to represent the fictitious root in
the pointed network, $v$ to denote its neighbour, and $\mathcal{U}$ to
represent any pointed network.

####  8.1.1. Case 1: One edge with an attached network

One edge of the generator carries a sequence of at least two incident cut-
edges. Because multiple edges are not allowed, it cannot be one of the two
edges incident to $v$. So, it can be only one of the two edges not incident to
$v$ (which are not distinguished). The sequence is unoriented, because of
symmetry, explaining the factor $\tfrac{1}{2}$ below.

$\frac{{U}^{2}}{2(1-{U})}$

#
---

####  8.1.2. Case 2: Two edges with attached networks

Case 2A - Two edges of the generator carry exactly one incident cut-edge.
Since multiple edges are not allowed, it can either be one edge incident to
$v$ and one not, or both edges not incident to $v$. In the latter case, the
two edges should not be distinguished, hence the factor $\tfrac{1}{2}$.

${U}^{2}+\dfrac{{U}^{2}}{2}=\frac{3}{2}{U}^{2}$

#$\mathcal{U}$$\mathcal{U}$ | #$\mathcal{U}$$\mathcal{U}$
---|---

Case 2B - One edge of the generator carries a single incident cut-edge and
another edge carries a sequence of at least two incident cut-edges. Again,
these cannot be the two edges incident to $v$. The only case where symmetries
need to be taken care of is when the two edges are those not incident to $v$:
in this case, the sequence is not oriented, hence the factor $\tfrac{1}{2}$.
In all other cases, the orientation of the sequence is determined by the
presence of the fictitious root or the outgoing arc from the other edge with
and attached network.

$\dfrac{{U}^{3}}{1-{U}}+\dfrac{{U}^{3}}{1-{U}}+\dfrac{{U}^{3}}{2(1-{U})}=\frac{5{U}^{3}}{2(1-{U})}$

#$\mathcal{U}$ | #$\mathcal{U}$ | #$\mathcal{U}$
---|---|---

Case 2C - Two edges of the generator (but not the two incident to $v$, as
before) carry a sequence of at least two incident cut-edges. If one arc is
incident to $v$ and the other not, then both sequences are oriented and there
is no symmetry factor. If the two arcs are those not incident to $v$, then the
two sequences they carry can be seen as an unordered pair of oriented
sequences, seen up to symmetry w.r.t. the vertical axis. This yields a factor
$\tfrac{1}{2}$ since the pair is unordered, and another factor $\tfrac{1}{2}$
to account for the symmetry w.r.t. the vertical axis.

$\dfrac{{U}^{4}}{(1-{U})^{2}}+\dfrac{{U}^{4}}{4(1-{U})^{2}}=\frac{5{U}^{4}}{4(1-{U})^{2}}$

# #
---

####  8.1.3. Case 3: Three edges with attached networks

Case 3A - Three edges of the generator carry exactly one incident cut-edge.
The unused edge can either be incident with $v$ or not. In both cases, we have
a factor $\tfrac{1}{2}$ because of symmetry.

$\dfrac{{U}^{3}}{2}+\dfrac{{U}^{3}}{2}={U}^{3}$

#$\mathcal{U}$$\mathcal{U}$$\mathcal{U}$ | #$\mathcal{U}$$\mathcal{U}$$\mathcal{U}$
---|---

Case 3B - Two edges of the generator carry a single incident cut-edge and one
carries a sequence of at least two incident cut-edges. The only cases where a
symmetry comes into play here are when the edges carrying a single incident
cut-edge are either the two edges incident to $v$ or the two edges not
incident to $v$. This yield the factor $\tfrac{1}{2}$ in these two cases.
Moreover, all sequences are oriented, because of the presence of the
fictitious root or the single incident cut-edges.

$\dfrac{{U}^{4}}{1-{U}}+\dfrac{{U}^{4}}{1-{U}}+\dfrac{{U}^{4}}{2(1-{U})}+\dfrac{{U}^{4}}{2(1-{U})}=\frac{3{U}^{4}}{1-{U}}$

#$\mathcal{U}$$\mathcal{U}$ | #$\mathcal{U}$$\mathcal{U}$ | #$\mathcal{U}$$\mathcal{U}$ | #$\mathcal{U}$$\mathcal{U}$
---|---|---|---

Case 3C - One edge of the generator carries a single incident cut-edge and two
edges carry a sequence of at least two incident cut-edges. Similarly to the
previous case, we obtain a factor $\tfrac{1}{2}$ for symmetry reasons when the
two edges carrying sequences are either the two edges incident to $v$ or the
two edges not incident to $v$. Moreover, all sequences are oriented, because
of the presence of the fictitious root or the single incident cut-edge.

$\dfrac{{U}^{5}}{(1-{U})^{2}}+\dfrac{{U}^{5}}{(1-{U})^{2}}+\dfrac{{U}^{5}}{2(1-{U})^{2}}+\dfrac{{U}^{5}}{2(1-{U})^{2}}=\frac{3{U}^{5}}{(1-{U})^{2}}$

#$\mathcal{U}$ | #$\mathcal{U}$ | #$\mathcal{U}$ #$\mathcal{U}$
---|---|---

Case 3D - Three edges of the generator carry a sequence of at least two
incident cut-edges. In both cases, we have a factor $\tfrac{1}{2}$ for
symmetry reason, but all sequences are oriented by the presence of the
fictitious root, or of the sequence on the edge(s) incident to $v$.

$\dfrac{{U}^{6}}{2(1-{U})^{3}}+\dfrac{{U}^{6}}{2(1-{U})^{3}}=\frac{{U}^{6}}{(1-{U})^{3}}$

# | #
---|---

####  8.1.4. Case 4: Four edges with attached networks

Case 4A - The four edges of the generator each carry exactly one incident cut-
edge. In this case, the two edges incident to $v$ can be exchanged without
modifying the network, and the same holds for the two edges not incident to
$v$. This yields a factor $\tfrac{1}{2}\cdot\tfrac{1}{2}=\tfrac{1}{4}$ due to
symmetries.

$\dfrac{{U}^{4}}{4}$

#$\mathcal{U}$$\mathcal{U}$$\mathcal{U}$$\mathcal{U}$

Case 4B - Three edges of the generator carry a single incident cut-edge and
the fourth one carries a sequence of at least two incident cut-edges. If this
fourth edge is one incident to $v$, then the sequence it carries is oriented
by the presence of the fictitious root, but the two arcs pending on the edges
not incident to $v$ are symmetric, hence a factor $\tfrac{1}{2}$. If on the
contrary the edge carrying the sequence is not incident to $v$, then the
sequence is also oriented, this time because of the arcs attached to the edges
incident to $v$. Moreover, the picture has a symmetry w.r.t. the vertical
axis, hence a factor $\tfrac{1}{2}$.

$\dfrac{{U}^{5}}{2(1-{U})}+\dfrac{{U}^{5}}{2(1-{U})}=\frac{{U}^{5}}{1-{U}}$

#$\mathcal{U}$$\mathcal{U}$$\mathcal{U}$ | #$\mathcal{U}$$\mathcal{U}$$\mathcal{U}$
---|---

Case 4C - Two edges carry a single incident cut-edge and the two others carry
a sequence of at least two incident cut-edges. In all cases, the sequences are
oriented, by the presence of either the fictitious root or of the single arcs
attached to edges. If the edges carrying sequences are one incident to $v$ and
the other not incident to $v$, all edges are in addition distinguished from
each other. In the other two cases, both edges incident to $v$ form an
unordered pair, as well as the two edges not incident to $v$. In each case, we
therefore have a factor $\tfrac{1}{4}$.

$\dfrac{{U}^{6}}{(1-{U})^{2}}+\dfrac{{U}^{6}}{4(1-{U})^{2}}+\dfrac{{U}^{6}}{4(1-{U})^{2}}=\frac{3{U}^{6}}{2(1-{U})^{2}}$

#$\mathcal{U}$$\mathcal{U}$ | #$\mathcal{U}$$\mathcal{U}$ | #$\mathcal{U}$$\mathcal{U}$
---|---|---

Case 4D - One edge of the generator carries a single incident cut-edge and
three edges carry a sequence of at least two incident cut-edges. As in the
previous case, all sequences are oriented. However, if the two edges incident
to $v$ carry a sequence, the picture has a symmetry w.r.t. the vertical axis,
hence a factor $\tfrac{1}{2}$. If on the contrary the two edges not incident
to $v$ carry a sequence, these two edges are indistinguishable, hence a factor
$\tfrac{1}{2}$ also in this case.

$\dfrac{{U}^{7}}{2(1-{U})^{3}}+\dfrac{{U}^{7}}{2(1-{U})^{3}}=\frac{{U}^{7}}{(1-{U})^{3}}$

#$\mathcal{U}$ | #$\mathcal{U}$
---|---

Case 4E - All four edges of the generator carry a sequence of at least two
incident cut-edges. Then all sequences are oriented, but the two edges not
incident to $v$ are indistinguishable. The picture has in addition a symmetry
w.r.t. the vertical axis. This yields a factor $\tfrac{1}{4}$.

$\dfrac{{U}^{8}}{4(1-{U})^{4}}$

#
---

###  8.2. Case analysis for the rooted level-2 generator 2b

In the pictures below, we use thick lines to represent paths containing at
least one internal node incident with a cut arc which is incident with the
root of another rooted level-2 network. All arcs are directed downwards. We
use $\mathcal{L}$ to represented any rooted level-2 network.

####  8.2.1. Case 1:

Only one arc of the generator carries a sequence of at least one outgoing arc.
This arc can only be $e$ or $e^{\prime}$ (and these cases are
indistinguishable), since otherwise the network would contain multiple arcs,
and this is not allowed.

${L}\frac{{L}}{1-{L}}$

${\mathcal{L}}$$e$$e^{\prime}$
---

####  8.2.2. Case 2:

Exactly two arcs of the generator carry a sequence of at least one outgoing
arc. To avoid multiple arcs, either these two arcs are $e$ and $e^{\prime}$
(and those two arcs are symmetric, hence the factor $\frac{1}{2}$), or one of
them is $e$ or $e^{\prime}$ (which are not distinguished) and the other arc is
chosen among the three arcs different from $e$ and $e^{\prime}$.

$\frac{1}{2}{L}\left(\dfrac{{L}}{1-{L}}\right)^{2}+3{L}\left(\dfrac{{L}}{1-{L}}\right)^{2}=\frac{7}{2}{L}\left(\dfrac{{L}}{1-{L}}\right)^{2}$

${\mathcal{L}}$$e$$e^{\prime}$$\tiny{\overleftrightarrow{{sym}}}$ | ${\mathcal{L}}$$e$$e^{\prime}$ | ${\mathcal{L}}$$e$$e^{\prime}$ | ${\mathcal{L}}$$e$$e^{\prime}$ |
---|---|---|---|---

####  8.2.3. Case 3:

Exactly three arcs of the generator carry a sequence of at least one outgoing
arc. Here, there are two possibilities. Either both $e$ and $e^{\prime}$ are
among those three arcs (and those two arcs are symmetric, hence the factor
$\frac{1}{2}$). Or, to avoid multiple arcs, we must choose one of $e$ and
$e^{\prime}$ (which are not distinguished from each other), and two additional
arcs among the three remaining arcs.

$\frac{3}{2}{L}\left(\dfrac{{L}}{1-{L}}\right)^{3}+3{L}\left(\dfrac{{L}}{1-{L}}\right)^{3}=\frac{9}{2}{L}\left(\dfrac{{L}}{1-{L}}\right)^{3}$

${\mathcal{L}}$$e$$e^{\prime}$$\tiny{\overleftrightarrow{{sym}}}$ | ${\mathcal{L}}$$e$$e^{\prime}$$\tiny{\overleftrightarrow{{sym}}}$ | ${\mathcal{L}}$$e$$e^{\prime}$$\tiny{\overleftrightarrow{{sym}}}$ | ${\mathcal{L}}$$e$$e^{\prime}$ | ${\mathcal{L}}$$e$$e^{\prime}$ | ${\mathcal{L}}$$e$$e^{\prime}$
---|---|---|---|---|---

####  8.2.4. Case 4:

Exactly four arcs of the generator carry a sequence of at least one outgoing
arc. Either both $e$ and $e^{\prime}$ are among those four arcs (and those two
arcs are symmetric, hence the factor $\frac{1}{2}$), so the last two are
chosen among the three other arcs of the generator. Or we choose the three
arcs of the generator other than $e$ and $e^{\prime}$, and $e$ (which is
undistinguishable from $e^{\prime}$).

$\frac{\binom{3}{2}}{2}{L}\left(\dfrac{{L}}{1-{L}}\right)^{4}+{L}\left(\dfrac{{L}}{1-{L}}\right)^{4}=\frac{5}{2}{L}\left(\dfrac{{L}}{1-{L}}\right)^{4}$

${\mathcal{L}}$$e$$e^{\prime}$$\tiny{\overleftrightarrow{{sym}}}$ | ${\mathcal{L}}$$e$$e^{\prime}$$\tiny{\overleftrightarrow{{sym}}}$ | ${\mathcal{L}}$$e$$e^{\prime}$$\tiny{\overleftrightarrow{{sym}}}$ | ${\mathcal{L}}$$e$$e^{\prime}$
---|---|---|---

####  8.2.5. Case 5:

All five arcs of the generator carry a sequence of at least one outgoing arc.
The fact that $e$ and $e^{\prime}$ are symmetric explains the factor
$\frac{1}{2}$.

$\frac{1}{2}{L}\left(\dfrac{{L}}{1-{L}}\right)^{5}.$

${\mathcal{L}}$$e$$e^{\prime}$$\tiny{\overleftrightarrow{{sym}}}$

###  8.3. Exact enumeration formulas

####  8.3.1. Unrooted level-2 networks

######  Proposition 8.1.

For any $n\geq 1$, the number $u_{n}$ of unrooted level-2 phylogenetic
networks with $(n+1)$ leaves is given by

$u_{n}=(n-1)!\sum\limits_{{0\leq s\leq q\leq p\leq k\leq i\leq
n-1}\atop{{j=n-1-i-k-p-q-s\geq 0}\atop{i\neq
0}}}{{~{}}\atop{{{{n+i-1}\choose{i}}{{4i+j-1}\choose{j}}{{i}\choose{k}}{{k}\choose{p}}{{p}\choose{q}}{{q}\choose{s}}\qquad\qquad}\atop{\times\left(3\right)^{i}\left(\frac{-15}{6}\right)^{k}\left(-\frac{16}{15}\right)^{p}\left(-\frac{1}{2}\right)^{q}\left(-\frac{3}{16}\right)^{s}.}}}$

###### Sketch.

Recall that $U(z)=z\phi(U(z))$ with
$\phi(z)=\frac{1}{1-\frac{3z^{5}-16z^{4}+32z^{3}-30z^{2}+12z}{4(1-z)^{4}}}$.
Using first the classical development of $(1-z)^{-n}$ in series (see Eq. (2)),
and then the binomial theorem, we have

$\displaystyle\phi(z)^{n}=$ $\displaystyle\sum_{i\geq
0}{{n+i-1}\choose{i}}\left(\frac{12z}{4(1-z)^{4}}+\frac{-30z^{2}+32z^{3}-16z^{4}+3z^{5}}{4(1-z)^{4}}\right)^{i}$
$\displaystyle=$ $\displaystyle\sum_{i\geq
0}\sum_{k=0}^{i}{{n+i-1}\choose{i}}{{i}\choose{k}}\left(\frac{12z}{4(1-z)^{4}}\right)^{i-k}\left(\frac{-30z^{2}+32z^{3}-16z^{4}+3z^{5}}{4(1-z)^{4}}\right)^{k}\textrm{.}$

We continue applying the binomial theorem inside the above formula, isolating
each time the term with the lowest degree in the numerator (that is, first
$\tfrac{-30z^{2}}{4(1-z)^{4}}$, second $\tfrac{32z^{3}}{4(1-z)^{4}}$, …). This
yields

$\displaystyle\phi(z)^{n}=$ $\displaystyle\sum_{i\geq
0}\sum_{k=0}^{i}\sum_{p=0}^{k}\sum_{q=0}^{p}\sum_{s=0}^{q}{{n+i-1}\choose{i}}{{i}\choose{k}}{{k}\choose{p}}{{p}\choose{q}}{{q}\choose{s}}$
$\displaystyle\hskip
28.45274pt\left(\frac{12z}{4(1-z)^{4}}\right)^{i-k}\left(\frac{-30z^{2}}{4(1-z)^{4}}\right)^{k-p}\left(\frac{32z^{3}}{4(1-z)^{4}}\right)^{p-q}\left(\frac{-16z^{4}}{4(1-z)^{4}}\right)^{q-s}\left(\frac{3z^{5}}{4(1-z)^{4}}\right)^{s}$
$\displaystyle=$ $\displaystyle\sum_{i\geq
0}\sum_{k=0}^{i}\sum_{p=0}^{k}\sum_{q=0}^{p}\sum_{s=0}^{q}{{n+i-1}\choose{i}}{{i}\choose{k}}{{k}\choose{p}}{{p}\choose{q}}{{q}\choose{s}}\frac{(3)^{i}(\tfrac{-15}{6})^{k}(\tfrac{-16}{15})^{p}(\tfrac{-1}{2})^{q}(\tfrac{-3}{16})^{s}}{(1-z)^{4i}}z^{i+k+p+q+s}\textrm{.}$

The result then follows from developing of $(1-z)^{-4i}$ in series as
$(1-z)^{-4i}=\sum_{j\geq 0}{{4i+j-1}\choose{j}}z^{j}$ and using the Lagrange
inversion formula. ∎

####  8.3.2. Rooted level-2 networks

######  Proposition 8.2.

For any $n\geq 1$, the number $\ell_{n}$ of rooted level-2 phylogenetic
networks with $n$ leaves is given by

$\ell_{n}=(n-1)!\sum\limits_{{0\leq t\leq m\leq s\leq q\leq p\leq k\leq i\leq
n-1}\atop{{j=n-1-i-k-p-q-s-m-t\geq 0}\atop{i\neq
0}}}{{~{}}\atop{{{{n+i-1}\choose{i}}{{6i+j-1}\choose{j}}{{i}\choose{k}}{{k}\choose{p}}{{p}\choose{q}}{{q}\choose{s}}{{s}\choose{m}}{{m}\choose{t}}\qquad\qquad}\atop{\times\left(9\right)^{i}\left(\frac{-17}{6}\right)^{k}\left(\frac{-53}{34}\right)^{p}\left(\frac{-148}{159}\right)^{q}\left(\frac{-81}{148}\right)^{s}\left(\frac{-8}{27}\right)^{m}\left(\frac{-1}{8}\right)^{t}.}}}$

###### Sketch.

This follows again from the Lagrange inversion formula, using the equation
${L}(z)=z\phi({L}(z))$ for the function $\phi$ given in Theorem 7.1. The
computations involve the usual development of $(1-z)^{-n}$ given by Eq. (2)
and the binomial formula, applied following exactly the same steps as in the
proof of Proposition 8.1. Details of the computations are left to the reader.
∎