# Counting General Phylogenetic networks

Marefatollah Mansouri  Department of Discrete Mathematics and Geometry,
Technische Universität Wien, Wiedner Hauptstraße 8-10/104, A-1040 Wien,
Austria<EMAIL_ADDRESS>
###### Abstract.

We provide precise asymptotic estimates for the number of general phylogenetic
networks by using analytic combinatorial methods. Recently, this approach is
studied by Fuchs, Gittenberger and author himself (Australasian Journal of
Combinatorics 73(2):385-423, 2019), to count networks with few reticulation
vertices for two subclasses: tree-child and normal networks. We follow this
line of research to show how to obtain results on the enumeration of general
phylogenetic networks.

This research has been supported by bilateral Austrian-Taiwanese project FWF-
MOST, grant I 2309-N35.

##  1\. Introduction

A phylogenetic network is a generalization of a phylogenetic tree which can be
used to describe the evolutionary history of a set of species that is non-tree
like. Phylogenetic trees are usually computed from molecular sequences that
are commonly used to show evolutionary history. Phylogenetic trees provide a
useful representation of many evolutionary relationships, and have been well
studied (see, for example [15, 5, 21, 24, 20]). However, these trees are less
suited to model mechanisms of reticulate evolution [25], such as
hybridization, recombination, or reassortment. Phylogenetic networks provide
an alternative to phylogenetic trees when analyzing data sets whose evolution
involves of reticulate events (for more details see, [2, 14, 16]).

In the literature, there are often two kinds of labeling for phylogenetic
networks : leaf-labeled and vertex-labeled. In the latter case, all the
vertices take different labels, and in the former case, leaves are labeled but
non-leaf vertices are unlabeled. The importance of phylogenetic networks is
because of precise representations of reticulation event which is in
particular, the formation of hybrid species. However, there are particular
principles in the procedure of evolution that cause some more restrictions on
phylogenetic networks. Thus, biologists have defined many subclasses of the
class of phylogenetic networks. Recently, studying of enumerative aspects of
phylogenetic networks and related structures have become increasingly
interested. We mentioned already the shape analysis of phylogenetic trees [3,
4, 11, 12] and the bounds for the counting sequences of some classes of
phylogenetic networks [18]. But other counting problems were studied in [1, 8,
9, 17, 19, 22, 24, 13, 27, 6, 26, 7]. Though combinatorial counting problems
are often amenable to the rich tool box of analytic combinatorics [10],
generating functions have been rarely used in phylogenetic networks
enumeration problems.

There are a quite few research studies on general phylogenetic networks. This
paper is concerned with the counting of general phylogenetic networks, a basic
and fundamental question which is of interest in mathematical biology [18]. On
the other hand, the combinatorial view of phylogenetic networks as an
interesting challenge has been addressed only in few papers. The goal of this
study is to develop a more rigorous understanding of counting problem for
general phylogenetic networks with a fixed number of reticulation events. Here
we come back to the open problems of [13] which are left for general networks
and show that sparsened skeleton decomposition is powerful tool for
enumeration problems in general phylogenetic networks. The purpose of the
current study is to show how the present method in [13] for tree-child
networks can be extended for general networks. Before stating our results in
more detail, we recall some definitions and previous works. A phylogenetic
network is defined as a directed acyclic graph (DAG) which is connected and
consists of the following vertices:
$(1)$ leaves which have out-degree 0 and in-degree 1;
$(2)$ tree vertices have out-degree 2 and in-degree 1;
$(3)$ reticulation vertices have out-degree 1 and in-degree 2;
$(4)$ and the root node with out-degree 2 and in-degree 0.
Also, a phylogenetic network is called tree-child network if for every non-
leaf node at least one of its children is a tree node or a leaf. Equivalently,
every tree vertex must have at least one child which is not a reticulation
vertex and every reticulation vertex is not directly followed by another
reticulation vertex.
Note that variations on the definition of rooted binary phylogenetic networks
are around in the literature. In general phylogenetic networks, as defined
before, multiple edges are not explicitly forbidden. Our goal is indeed to
study the most general model of general phylogenetic networks that could be
counted if their number of reticulation vertices is fixed and provide a more
detailed investigation regarding enumeration properties of general networks
with or without multiple edges on their structures.

Figure 1. A phylogenetic network which is not a tree-child network.

Now, denote by $G_{k,n}$ resp. $\tilde{G}_{k,\ell}$ the number of general
networks with $k$ reticulation vertices in the vertex-labeled (leaf-labeled)
case. We focus mainly on proves the following results.

######  Theorem 1.

For the number $G_{k,n}$ of vertex-labeled phylogenetic networks with $k\geq
1$ reticulation vertices, there is a positive constant $d_{k}$ such that

$G_{k,n}\sim
d_{k}\left(1-(-1)^{n}\right)\left(\frac{\sqrt{2}}{e}\right)^{n}n^{n+2k-1},\qquad(n\rightarrow\infty).$

In particular,

$\displaystyle d_{1}=\frac{\sqrt{2}}{4};\qquad
d_{2}=\frac{\sqrt{2}}{32};\qquad d_{3}=\frac{\sqrt{2}}{384}.$

The result reveals that the first and second order asymptotics are the same as
the once for vertex-labeled tree-child networks (see [13]). In other words, we
can show that for the general networks with fixed number of reticulation
vertices, the additional networks that not satisfying the tree-child
conditions are asymptotically negligible as ${n\to\infty}$. Also, this
approach help us to have following result.

######  Theorem 2.

For the numbers $\tilde{G}_{k,\ell}$ of leaf-labeled general networks with
$k\geq 1$ reticulation vertices, we have

$\tilde{G}_{k,\ell}\sim
2^{3k-1}d_{k}\left(\frac{2}{e}\right)^{\ell}\ell^{\ell+2k-1},\qquad(\ell\rightarrow\infty)$

where $d_{k}$ is as in Theorem 1.

######  Remark .

Note that this result only holds for fixed $k$ as $n$ goes to infinity. The
case when $k$ approaches to infinity cannot be done in this way.

The other objective of this paper is to study procedures that can be used to
extract explicit formulas for the number of phylogenetic networks with fixed
reticulation vertices. So points of the presented argumentation can shed some
light on open questions that are left in [27] and [26] about an explicit
formula for the count of phylogenetic networks.

| The explicit formula |
---|---|---
${G}_{1,\ell}^{\nshortparallel}$ | $\ell!\;\Big{(}r_{1}(\ell)\displaystyle 2^{-\ell}\binom{2\ell}{\ell}-2^{\ell}p_{1}(\ell)\Big{)}$ |  $r_{1}(\ell)=\ell,$ and  $p_{1}(\ell)=\frac{1}{2}.$
${G}_{2,\ell}^{\nshortparallel}$ | $\ell!\;\Big{(}r_{2}(\ell)\displaystyle 2^{-\ell}\binom{2\ell+2}{\ell+1}-2^{\ell}p_{2}(\ell)\Big{)}$ |  $r_{2}(\ell)=\frac{(\ell+1)(6\ell^{4}+19\ell^{3}+18\ell^{2}-7\ell)}{2(6\ell-3)(2\ell+1)},$ and  $p_{2}(\ell)=\frac{2\ell^{2}+5\ell+3}{2}.$
|  | $r_{3}(\ell)=\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$
${G}_{3,\ell}^{\nshortparallel}$ | $\ell!\;\Big{(}r_{3}(\ell)\displaystyle 2^{-\ell}\binom{2\ell+4}{\ell+2}-2^{\ell}p_{3}(\ell)\Big{)}$ | $\frac{(\ell+1)(\ell+2)(280\ell^{6}+3072\ell^{5}+12834\ell^{4}+22386\ell^{3}+10949\ell^{2}-5211\ell-3990)}{840(2\ell+3)(2\ell+1)(2\ell-1)}.$
|  | $p_{3}(\ell)=\frac{48\ell^{4}+415\ell^{3}+1326\ell^{2}+1799\ell+816}{768}.\quad\quad\quad\quad\quad\quad\quad\quad\quad$
Table 1. The numbers of leaf-labeled general networks with $\ell$ leaves and
no multiple edges.

##  2\. Generating functions and methods from Analytic combinatorics

This section summarizes some basic concepts on combinatorial classes and their
generating functions that will be used in our work. Our presentation follows
closely [10] (although with much less details), and the reader interested to
know more on the topic is refered to [10, mainly Chapters I.5, II.1, II.5,
VI.3, VII.3, VII.4].

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

Generally speaking, a _combinatorial class_ is a collection $\mathcal{C}$ of
objects of a similar kind (e.g. words, trees, graphs), endowed with a suitable
notion of size or weight (which is a function
$f:\mathcal{C}\longrightarrow\mathbb{N}$) in a way that there are only
finitely many objects of each size. 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, we consider a family of general
phylogenetic networks as a combinatorial class such that the size of a network
is its number of vertices or leave.

The arrangement of $n$ atoms can be considered as objects of size $n$ in
$\mathcal{C}$ such that each atom has size $1$. In our context, these atoms
are the vertices (or leaves) of the networks. In general, combinatorial
objects may or may not be labelled, depending on whether the atoms
constituting an object are distinguishable from one another (_labelled_ case)
or not (_unlabelled_ case). Here, our networks will be labelled combinatorial
objects.

To deal with a labelled combinatorial class $\mathcal{C}$, we introduce
_exponential_ _generating function_ $C(z)=\sum_{n\geq
0}c_{n}\frac{z^{n}}{n!}$, which is a formal power series in $z$ represents the
entire counting sequence of $\mathcal{C}$. The neutral class $\mathcal{E}$ is
made of a single object of size $0$, and its associated generating function is
$E(z)=1$. The atomic class $\mathcal{Z}$ is made of a single object of size
$1$, and its associated generating function is $Z(z)=z$.

We now turn our attention to recursive specifications of a combinatorial
class. For instance, trees are best described recursively. Note that in the
next section we are going to describe decomposition of phylogenetic network
that is based on tree structure which will then be translated into a
functional equation involving their associated exponential generating
functions.

######  Example .

A rooted plane tree is a root to which is attached a (possibly empty) sequence
of trees. In other words, the class $\mathcal{T}$ of rooted plane trees is
definable by the recursive equation:
$\mathcal{T}=\mathcal{Z}+\mathcal{Z}\times\mathcal{T}+\mathcal{Z}\times\mathcal{T}^{2}++\mathcal{Z}\times\mathcal{T}^{3}+\cdots=\mathcal{Z}\times
SEQ(\mathcal{T})$.

Specifications describing a combinatorial class that is iterative can be
represented as a single term built on $\mathcal{E}$, $\mathcal{Z}$ and the
constructions $+,\times,SEQ,CYC,MSET,PSET$. For instance, Cartesian products
(with consistent relabellings in the case of labelled objects) correspond to
products of series, and sequences (_i.e._ , $m$-tuples of objects of a class
$\mathcal{C}$, for any $m\geq 0$) to the quasi-inverse $\frac{1}{1-C(z)}$.
This holds for exponential generating functions of labelled objects. For
labelled classes, the precise statement that we refer to is [10, Theorem
II.1]. Here we get that the corresponding generating function satisfies
$T(z)=\frac{z}{1-T(z)}$. The next step is to have access to the enumeration
sequence $(t_{n})$ of a class $\mathcal{T}$ from an equation satisfied by the
generating function $T(z)$ of $\mathcal{T}$. To state it, we introduce the
notation $n!\cdot[z^{n}]T(z)$ to denote the $n$-th coefficient of the series
$T(z)$; that is to say, writing $T(z)=\sum_{n\geq 0}t_{n}\frac{z^{n}}{n!}$, we
have $t_{n}:=n!\cdot[z^{n}]T(z)$. From this point on, basic algebra does the
rest. First the original equation is equivalent to $T-T^{2}-z=0$. Solving this
quadratic equation gives

$\displaystyle T(z)$ $\displaystyle=\frac{1}{2}(1-\sqrt{(1-4z)})$
$\displaystyle=z+z^{2}+2z^{3}+5z^{4}+14z^{5}+42z^{6}+132z^{7}+429z^{8}+\cdots$
$\displaystyle=\sum_{n\geq 1}\frac{1}{n}\binom{2n-2}{n-1}z^{n},$

and consequently, $t_{n}=\displaystyle n!\cdot\frac{1}{n}\binom{2n-2}{n-1}$.

The other possible way, especially in the case of tree-like objects, is to
appeal to the _transfer theorem_(see [10], VI.1). Before going ahead, first we
illustrate some concepts which help us to clarify the details. A singularity
of an analytic function $f(z)$ is a point $z_{0}$ on the boundary of its
region of analycity for which $f(z)$ is not analytically continuable.
Singularities of a function analytic at $0$, which lie on the boundary of the
disc of convergence, are called dominant singularities. In this case, a
dominant singularity is a singularity with smallest modulus. From Pringsheim’s
theorem ([10], Theorem IV.6) we know that if $f(z)$ is representable at the
origin by a series expansion that has non-negative coefficients and radius of
convergence $\rho$, then the point $z=\rho$ is a singularity of $f(z)$. The
idea behind the transfer theorem is that if $A(z)$ and $B(z)$ are two
generating functions with the same positive real number $\rho$ as dominant
singularity; So when $z{\rightarrow}\rho$, we can write
$A(z){\rightarrow}B(z)$. We obtain the asymptotic expansion of $[z^{n}]A(z)$
by transferring the behaviour of $A(z)$ around its dominant singularity from a
simpler function $B(z)$, from which we know the analytic behaviour.

######  Theorem 3 (Transfer Theorem).

If the generating function $A(z)$ admits an expansion of the form $A(z)\sim
c\cdot(1-\frac{z}{\rho})^{-\alpha}$ as ${{n\to\infty}}$, around its (unique)
dominant singularity $\rho$, then we have

$n!\cdot[z^{n}]A(z)\sim n!\cdot
c\cdot\dfrac{n^{\alpha-1}}{\Gamma(\alpha)}\cdot\rho^{-n},$

as ${{n\to\infty}}$.

######  Remark .

Here $A(z)$ is analytic in the disk of radius $\rho$ centered at the origin.

Recall that $[z^{n}]A(z)$ is the coefficient of $z^{n}$ in $A(z)$, and so it
is $\frac{c_{n}}{n!}$ (resp. $c_{n}$ ), when $A(z)$ is a exponential
(resp.ordinary) generating function. Note that the location of a dominant
singularity will give the exponential growth of the sequence, and the nature
of this singularity the subexponential term. If $A(z)$ has several dominant
singularities coming from pure periodicities (for more details see [10],
IV.6.1 ), then the contributions from each of them must be combined.

These methods are fundamental results from complex analysis that allow to set
up generating function in its disk of convergence, but not always. In
particular, the _transfer theorem_ (Theorem VI.1 of [10]) is one of the
suitable tools, which allows us to derive asymptotic estimates of the
coefficients of generating functions.

###  2.2. Additive parameters and bivariate generating function

It is sometimes interesting to analyze the behaviour of other parameters than
size. For example, interesting parameters for plane trees can be: height,
number of leaves, path length, etc. These parameters are important for
algorithm analysis as they correspond to the performance of algorithms that
compute with or are modeled by plane trees. We now consider _multivariate_
generating functions, where additional variables ($x$, $y$, …) record the
value of other parameters of our objects. One variable is used to track the
size of the structure (e.g. number of nodes in a plane tree) and the other is
used to track the parameter of interest (e.g. height, number of leaves, path
length).

In our cases, we will consider one more such parameter, which are numbers of
certain "unary nodes" occuring in our objects. Namely, denoting $c_{n,\ell}$
the number of objects of size $n$ in the combinatorial class $\mathcal{C}$
such that the parameter has value $\ell$, the multivariate exponential
generating function we consider is
$C(z,y)=\sum_{n,\ell}c_{n,\ell}y^{\ell}\tfrac{z^{n}}{n!}$.

For inistanc,on the previous example of rooted plane trees consider one
additional parameter, which is the number of leaves nodes. The coefficient of
$z^{n}y^{\ell}$ in the generating function $T(z,y)$ is then the number of
rooted plane trees with $n$ nodes and exactly $\ell$ leaves, divided by $n!$.

The “dictionnary” translating combinatorial specifications to equations
satisfied by the generating function extends to multivariate series, and our
specification that shows any such tree is leaf or sequences $(\geq 1)$ of
trees that attached to the root nod. This gives
$T(z,y)=zy+\dfrac{zT(z,y)}{1-T(z,y)}$.

##  3\. Decomposing binary phylogenetic networks

In order to count general phylogenetic networks, we will adjust the procedure
of sparsened skeleton decomposition for general networks. This method is well
studied for tree-child networks, with $k$ of reticulation vertices in [13]. We
will use the decomposition to obtain a reduction which can be easily analyzed
by means of generating functions. Consider a general phylogenetic network
having $k$ reticulation vertices. Then each such vertex has two incoming
edges. If one edge is removed for each of the $k$ reticulation vertices, then
the remaining graph is again Motzkin tree (labeled and nonplane). Depending on
our choice for removed edges, this Motzkin tree has at most $2k$ unary nodes.
Recall that for tree-child networks this method gives exactly $2k$ unary
nodes.

Now consider the following procedure: start with a Motzkin tree $T$ with not
more that $2k$ unary nodes and $n$ vertices in total.

  * •

Add directed edges such that each edge connects two unary nodes and any two
edges do not have a vertex in common. Color the started vertices of the added
directed edges green and their end vertices red. Note that if Motzkin tree has
exactly $2k$ unary nodes, the coloring procedure imposes that there will be
equal $k$ colored green and red nodes (see Figure 2, (1)).

  * •

Consider two unary vertices and joint them by using sequence $\mathcal{S}$
($2\leq\mid\mathcal{S}\mid\leq k$) of fixed number of directed edges in the
following way. One of edge in the $\mathcal{S}$ connects the first unary
vertex of the Motzin tree to a leaf which we call $r_{g}$. Then connect
$r_{g}$ to another leaf and continue this process for disjoint leaves until
use all directed edges but one. Now connect the last leaf to a second unary
vertex by the remaining edge. As similar before color first unary vertex green
and consider red color for second ones, then mark (color) all leaves on the
path (leaf) red-green ( Figure 2, (2)). Note that for a general network with
$k$ reticulation vertices, the number of directed edges in the considered
sequence, cannot be exceeded of $k$, because each marked red-green vertex is
reticulation vertex.

  * •

Consider a leaf $g_{g}$ of the Motzkin tree. As similar before connect $g_{g}$
to the two distinct unary vertices by using two sequences
$\mathcal{S}\text{and}\mathcal{S^{\prime}}$ of outgoing directed edges
($2\leq\mid\mathcal{S}\cup\mathcal{S^{\prime}}\mid\leq k$). Mark $g_{g}$ as
double-green vertex and then color targeted unary vertices red. Also, consider
red-green color for all the leaves on the paths of $g_{g}$ to the unary
vertices. ( see Figure 2 (3)).

Note that in the above procedure the resulting graph must be a general
phylogenetic network $\mathcal{G}$. We say then that $T$ (keeping the colors
from the above generation of $\mathcal{G}$, but not the edges) is a colored
Motzkin skeleton (or simply Motzkin skeleton) of $\mathcal{G}$. Now, consider
two sets, but not necessarily disjoint, of colored vertices obtained of above
procedure. The member of first set is all colored vertices with outgoing edges
and then assume all colored vertices with ingoing edges in the second set.
Call them pointer and target sets respectively. In this way, red-green
vertices are considered in both pointer and target sets. It is not hard to see
that the size of target set is correspondent with number of reticulation nodes
on a general phylogenetic network. Note that in this procedure any general
network with no multiple edges and $n$ vertices is generated and each of them
exactly $2^{k}$ times, so in this case every network $\mathcal{G}$ with $k$
reticulation vertices has exactly $2^{k}$ different Motzkin skeletons.
However, note that as opposed to defined subclasses of phylogenetic networks
like tree-child networks, here we assume multiple edges (reticulation vertex
with one parent) are allowed to be in general networks. So for a reticulation
vertex with just one parent, any arbitrary choice and removing of multiple
edges, causes the same Motzkin skeleton. It means the described procedure
generates a network with $k$ reticulation vertices and $r$ multiple edges
exactly $2^{k-r}$ times. In the first step our aim is to set up an exponential
generating functions for general networks with no multiple edges and then get
the correspondent exponential generating function for other networks with at
least one multiple edge.

$r_{1}$$r_{2}$$r_{3}$$g_{1}$$g_{2}$$g_{3}$$(1)$$r_{g_{1}}$$r_{g_{2}}$$g$$(2)$$r$$g$$g_{g}$$r_{g_{1}}$$r_{2}$$r_{1}$$(3)$
Figure 2. Three general phylogenetic networks, where $(1)$ after adding marked
edges there is bijection between green and red (reticulation) vertices in the
Motzkin skeleton. General networks depicted in $(2)$ and $(3)$ which the red-
green and double-green vertices appear after adding the marked edges. Edges
are directed downwards. Figure 3. Corresponding sparsened skeletons of Figure
2 networks.

In order to set up exponential generating functions for the number of general
phylogenetic networks, we will construct them as follows: For a given network
$\mathcal{G}$ fix one of its possible Motzkin tree skeletons, that shows us
how the pointer set vertices are distributed within $\mathcal{G}$ (for
instance consider networks in Figure 2 without marked edges ). Now look for
sparsened skeleton of $\mathcal{G}$ which contains all pointer set vertices
and contract all paths between any two vertices which are either pointer
vertices or an ancestor of them to one edge. Note that this ancestor may be
pointer vertices itself (also see, [13]). In order to construct general
networks with $k$ target vertices (reticulations), we consider a sparsened
skeleton having no more than $k$ pointer vertices. Then we replace all edges
by paths that are made of red vertices or binary vertices with a Motzkin tree
(whose unary vertices are all colored red) as second child and add a path of
the same type on top of the root of the sparsened skeleton. Moreover, we
attach a Motzkin tree (again with all unary vertices colored red) only to
those leaves of the sparsened skeleton such that are just colored green (not
red-green or double-green). Note that red-green and double-green nodes lie on
leaves of sparsened skeleton. Do all of the above in such a way that the new
structure has $k$ target vertices (red and red-green) altogether. What we
obtain so far is a Motzkin skeleton of a phylogenetic network. Finally, add
edges connecting the pointer vertices to the target ones in such a way that
the general phylogenetic networks condition is respected. As an advantage, a
similar procedure can be used to set up generating functions for other kinds
of phylogenetic networks, with fixed number of reticulation vertices, such as
“stack-free” and “galled” networks that are defined in [23, 15].
Let us set up the exponential generating function for the Motzkin trees which
appear in the above construction. After all, the unary vertices in those trees
will be the red nodes of our network.

Denote by $M_{\ell,n}$ the number of all vertex-labeled Motzkin trees $n$
vertices and $\ell$ unary vertices. Furthermore, let $\mathcal{M}$ be the set
of all these Motzkin trees. The exponential generating function associated to
$\mathcal{M}$ is

$M(z,y)=\sum_{n\geq 1}\sum_{\ell\geq 0}M_{\ell,n}y^{\ell}\frac{z^{n}}{n!}.$

Furthermore, let $M(z,y)$ denotes the generating function associated to all
Motzkin trees in $\mathcal{M}$ whose root is a unary node or a binary node, so
we have

$M(z,y)=z+zyM(z,y)+\frac{z}{2}M^{2}(z,y).$

and thus

$\displaystyle M(z,y)=\dfrac{1-zy-\sqrt{1+(y^{2}-2)z^{2}-2zy}}{z}.$ (1)

The first few coefficients can be seen from

$z+yz^{2}+(y^{2}+\frac{1}{2})z^{3}+(y^{3}+\frac{3}{2}y)z^{4}+\cdots.$

##  4\. Counting Vertex And Leaf-Labeled General Phylogenetic Network

In this section, Our main goal is to present a precise asymptotic result for
the number of general phylogenetic networks with a fixed number $k$ of
reticulation vertices. To clear up the methods we start with simple cases,
determine the asymptotic number of general phylogenetic networks with up to
$3$ reticulation nodes. After that, we will show how this approach helps us to
present explicit formulas for the exact number of vetrex and leaf-labeled of
them. Finally, we will focus on the general case and show how previous results
lead us to prove theorems 1 and 2, for general phylogenetic networks with $k$
reticulation vertices. As a warm-up consider general phylogenetic network with
only one reticulation node we use the procedure to obtain (1) and the
(sparsened) skeleton, as described in the previous section: Consider a general
network with no multiple edges, delete one of the two incoming edges of the
reticulation node which then gives a unary-binary tree with exactly two unary
nodes which are colored green and red (we will consider general networks with
multiple edges separately). Conversely, we can start with the general tree or
even the sparsened skeleton and then construct the network from this. For more
explicitly, Let $G^{\nshortparallel}_{i}(z)$ resp. $G^{\shortparallel}_{i}(z)$
denote exponential generating functions for networks with no multiple edges
(with multiple edges) and $i$ reticulation vertices.

######  Proposition 1.

The exponential generating function for vertex-labelled general phylogenetic
networks with one reticulation node is

$\displaystyle
G_{1}(z)=G_{1}^{\nshortparallel}(z)+G_{1}^{\shortparallel}(z)=z\frac{\tilde{a}_{1}(z^{2})-\tilde{b}_{1}(z^{2})\sqrt{1-2z^{2}}\,}{(1-2z^{2})^{\frac{3}{2}}},$
(2)

where,

$\displaystyle\tilde{a}_{1}(z)=\tilde{b}_{1}(z)=1-z.$ (3)

$x$$g$$\ell$(a)$x$$g$$\ell$(b) Figure 4. (a) The structure of Motzkin
skeletons of networks with one reticulation vertex. It originates from a
sparsened skeleton which consists of only one green vertex. It has one green
vertex, denoted by $g$, and one red vertex which is hidden within the forest
made of the triangles in the picture, which are attached to $g$ and all the
vertices on the path of length $\ell$. Note that the position of the red
vertex in this forest is restricted by the general condition. (b) There is
multiple edge when the root of the subtree which is attached to $g$ is the red
node.

###### Proof.

We start with the general Motzkin tree as depicted in Figure 4 $(a)$ and add
an edge starting from $g$ and ending at a red vertex. Note that for all
phylogenetic network, this edge is not allowed point to a node on the path
from $g$ to the root (since the phylogenetic network must be a DAG). Thus,
when starting from the sparsened skeleton, _i.e._ , the single green vertex
$g$, then we must add a sequence of trees on top of $g$ which consist of a
root (these vertices make the path from $g$ to the root of the network) to
which either a leaf or a binary node with two trees is attached. The red
vertex must be contained in the forest made by this sequence or the tree
attached to $g$. Note that the second expression refers to the depicted
structure $(b)$ which is for general networks with a multiple edge. In terms
of generating functions altogether gives

$G_{1}(z)=\frac{1}{2}\frac{\partial}{\partial
y}\frac{z\tilde{M}(z,y)}{1-zM(z,y)}\Big{|}_{y=0}+\frac{z^{2}M(z,0)}{1-zM(z,0)},$

where,

$\displaystyle\tilde{M}(z,y)$ $\displaystyle=M(z,y)-zyM(z,y)=(1-zy)M(z,y).$
(4)

The factor $1/2$ makes up for the fact that each network in case $(a)$ is
counted by the above procedure exactly twice.

∎

From this result we can now easily obtain the asymptotic number of networks.

######  Proposition 2.

Let $G_{1,n}$ denote the number of vertex-labelled general phylogenetic
network with $n$ vertices and one reticulation vertex. If $n$ is even then
$G_{1,n}$ is zero, otherwise

$G_{1,n}=n![z^{n}]G_{1}(z)=\left(\frac{\sqrt{2}}{e}\right)^{n}n^{n+1}\left(\frac{\sqrt{2}}{2}-\frac{\sqrt{\pi}}{2}\cdot\frac{1}{\sqrt{n}}+{\mathcal{O}}\left(\frac{1}{n}\right)\right),$

as ${n\to\infty}$.

###### Proof.

The function (2) has two dominant singularities, namely at $\pm 1/\sqrt{2}$,
with singular expansions

$G_{1}(z)\stackrel{{\scriptstyle z\rightarrow
1/\sqrt{2}}}{{\sim}}\frac{1}{8(1-\sqrt{2}z)^{3/2}},\qquad
G_{1}(z)\stackrel{{\scriptstyle
z\rightarrow-1/\sqrt{2}}}{{\sim}}-\frac{1}{8(1+\sqrt{2}{z})^{3/2}}.$

Applying a transfer lemma for these two singularities completes the proof. ∎

####  4.0.1. Exact value of vertex-labeled general phylogenetic networks with
one reticulation vertex

First, set $n=2m+1$. Then, from (2) we obtain

$[z^{n}]G_{1}(z)=[z^{m}]\bar{G}_{1}(z)$

with

$\bar{G}_{1}(z)=\frac{\tilde{a}_{1}(z)-\tilde{b}_{1}(z)\sqrt{1-2z}}{(1-2z)^{3/2}},$

where $\tilde{a}_{1}(z)$ and $\tilde{b}_{1}(z)$ are as in (3). So we have

$[z^{m}]\bar{G}_{1}(z)=[z^{m}]\dfrac{\tilde{a}_{1}(z)}{(1-2z)^{\frac{3}{2}}}-[z^{m}]\dfrac{\tilde{b}_{1}(z)}{(1-2z)}.$

after some computation we have

$\displaystyle[z^{m}]\bar{G}_{1}(z)=2^{m}\big{(}(m+1)\frac{\displaystyle\binom{2m}{m}}{4^{m}}-\frac{1}{2}\big{)}.$

By replacing $m=(n-1)/2$ this implies

$\displaystyle
G_{1,n}=n!2^{(n-3)/2}\big{(}(n+1)\frac{\displaystyle\binom{n-1}{(n-1)/2}}{2^{n-1}}-1\big{)}.$
(5)

####  4.0.2. Counting Leaf-Labeled General Phylogenetic Network

Let $G_{n,k}$ (resp.$\tilde{G}_{\ell,k}$) denote the number of vertex-labeled
(leaf-labeled) general phylogenetic networks with $n$ vertices ($\ell$ leaves)
and $k$ reticulation nodes. It is well studied in [13], that for all
subclasses of general networks containing only networks in which any two
vertices have different sets of descendant, we have the following equation

$\displaystyle\displaystyle
G_{k,n}=\binom{n}{\ell}(n-\ell)!\;\tilde{G}_{k,\ell}.$ (6)

Figure 5. Two general phylogenetic networks, where in (a) the descendent set
for any two vertices are different, and (b) is a general network which
vertices $v_{1}$ and $v_{2}$ have a set of same descendent.

To see this, first recall from [18] that for any phylogenetic network with
$\ell$ leaves, $k$ reticulation vertices and $n$ vertices, we have
$\displaystyle\ell+k=\frac{n+1}{2}$ (Recall that $n$ is always odd). Now all
vertex-labeled general networks with $n$ vertices and $k$ reticulation
vertices can be constructed as follows: start with a (fixed) leaf-labeled
general network with $\ell$ leaves and $k$ reticulation vertices. Then, choose
$\ell$ labels from the set $n$ labels and re-label the leaves of the fixed
network such that the order is preserved. Finally, label the remaining
$n-\ell$ vertices by any permutation of the set of remaining $n-\ell$ labels.
By the above structure, in this way every vertex-labeled general network is
obtained exactly once.
But for classes of networks where not all networks have the above mentioned
property it is difficult to obtain a simple connection between the vertex-
labeled and leaf-labeled phylogenetic networks. For that we have to cope with
symmetry in some of generated general networks. Here, we will present complete
details to show how to deal with symmetry for general networks with up to $3$
fixed reticulation vertices. However, it will later be shown that as $n$ goes
infinity (resp.$\ell$), the family of general networks that need to deal with
symmetry are asymptotically negligible and thus one again expects
$\displaystyle\tilde{G}_{k,\ell}\sim\frac{\ell!}{n!}G_{k,n}$, be a good
approximation for all leaf-labeled general networks with fixed number of
reticulation vertices when $n$ goes to infinity.

As a warm up, we are going to take exact formula for leaf-labeled general
phylogenetic networks with one reticulation vertex. By the above points we
get,

$\tilde{G}_{1,\ell}=\frac{\ell!}{n!}G_{1,n}.$

After seting $n=2\ell+1$ in (5) we have

$\displaystyle\tilde{G}_{1,l}=\ell!\;2^{\ell}\big{(}(\ell+1)\frac{\displaystyle\binom{2\ell}{\ell}}{4^{\ell}}-\frac{1}{2}\big{)}.$
(7)

####  4.0.3. Relationship to Tree-child networks

In [13], the authors counted tree-child networks which are vertex-labeled or
leaf-labeled. On the other hand, general phylogenetic networks with exactly
one reticulation vertex and no multiple edges are tree-child networks. It
means that $G_{1}^{\nshortparallel}(z)$ is exactly corresponding to generating
function for vertex-labeled tree-child networks with one reticulation vertex.
This translates into

$T_{1}(z)=G_{1}^{\nshortparallel}(z)=\frac{1}{2}\frac{\partial}{\partial
y}\frac{z\tilde{M}(z,y)}{1-zM(z,y)}\Big{|}_{y=0}.$

Solving this equation gives

$T_{1}(z)=G_{1}^{\nshortparallel}(z)=\frac{z^{3}(1-\sqrt{1-2z^{2}})}{2(1-2z^{2})^{3/2}}$

as it must be. In the same way as before the mentioned approaches immediately
implies that

$\displaystyle T_{1,n}=G_{1,n}^{\nshortparallel}=\displaystyle
n!\;2^{(n-3)/2}\big{(}(n-1)\frac{\displaystyle\binom{n-1}{(n-1)/2}}{2^{n-1}}-1\big{)},$
(8)

and for leaf-labeled

$\displaystyle\displaystyle\tilde{T}_{1,\ell}={G}_{1,\ell}^{\nshortparallel}=\ell!\;2^{\ell}\;\big{(}\ell\dfrac{\displaystyle\binom{2\ell}{\ell}}{4^{\ell}}-\frac{1}{2}\big{)}.$
(9)

This approach for leaf labeled case can be saw in [27] with different methods.

###  4.1. General Phylogenetic Network With Two Reticulation Vertices

Now we expand the methods for general phylogenetic networks with $2$
reticulation nodes. For this case, we use some variables
$y_{1},y_{2},y_{r_{g}},y_{g_{g}}$ to express the possible pointing of the
pointer set vertices of the Motzkin skeletons. Furthermore, we have now more
complicated paths (and attached trees) which replace the edges of the
sparsened skeleton and thus we first set up the generating function
corresponding to theses paths. To govern the situation where an edge from one
of the two pointer set vertices must not point to a certain vertices on the
paths in order to avoid multiple edges in the first step, we distinguish three
types of unary vertices, which are the red vertices of our construction. We
will define is a class $\mathcal{P}$ of paths which serve as the essential
building blocks for Motzkin skeletons. In this class the rules for pointing to
particular red vertices differ, depending on whether (i) the red vertex lies
on the path itself,(ii) it is one of the vertices of one of the attached
subtrees (iii) the red vertex is the first vertex of the path. We will mark
the red vertices of type (i) with the variable $y$, those of type (ii) with
$\tilde{y}$ and the vertex of type (iii) with $\hat{y}$ which is introduced in
order to manage structures analysis multiple edges in phylogenetic networks.

${\mathcal{P}}$${\mathcal{P}}$$+$$+$$\\{\varepsilon\\}$$=$${\mathcal{P}}$
Figure 6. The specification of the class $\mathcal{P}$.

To simplify the explanation, let us use the following conventions where the
$\varepsilon$ denotes the empty tree. Each path is a sequence of vertices with
trees attached. Note that each red vertex may belong to different categories
(if it is first vertex of path marked with $\hat{y}$, otherwise with $y$). In
our analysis the variables $y$, $\tilde{y}$ and $\hat{y}$ will be replaced by
a sum of variables $y_{i}$ for $i\in\\{1,2,r_{g},g_{g}\\}$, where the presence
of a particular $y_{i}$ indicates that the corresponding $g_{i}$ is allowed to
point, its absence that pointing is forbidden. In particular, $y$ represent
the permission to point to vertices of the path (except its first vertex) and
$\tilde{y}$ describes the permission to point to vertices of attached trees
and $\hat{y}$ allows pointing to the first vertex of the path. We specify
$\mathcal{P}$ as

$\displaystyle\mathcal{P}=\frac{1-zy}{1-z(y+M(z,\tilde{y}))}+\frac{z\hat{y}}{1-z(y+M(z,\tilde{y}))}.$

This leads to the generating function

$P(z,y,\tilde{y},\hat{y})=\frac{1-zy+z\hat{y}}{1-z(y+M(z,\tilde{y}))},$

after all. Start with this assumption that in the Motzkin skeletons added
directed edges not allowed to make multiple edges., see Figure 7, and then add
the contribution of other all possible Motzkin tree skeletons with multiple
edges as shown in Figure 8. Now we are ready to state the following result.

######  Proposition 3.

The exponential generating function for vertex-labeled general phylogenetic
networks with two reticulation nodes is

${G}_{2}(z)={G}_{2}^{\nshortparallel}(z)+{G}_{2}^{\shortparallel}(z)=z\cdot\frac{\tilde{a}_{2}(z^{2})-\tilde{b}_{2}(z^{2})\sqrt{1-2z^{2}}}{(1-2z^{2})^{7/2}},$

where

$\tilde{a}_{2}(z)=z^{4}-2z^{3}-\frac{1}{2}z^{2}+\frac{5}{2}z\quad\text{ and
}\quad\tilde{b}_{2}(z)=-z^{2}+\frac{5}{2}z.$

Figure 7. The possible structures of the Motzkin skeletons of general
phylogenetic networks with $2$ reticulation nodes such that added edges not
allowed to make multiple edges.

###### Proof.

Consider the general phylogenetic networks arising from the Motzkin skeleton
on the Figure 7 $(a)$ and complete the Motzkin skeleton by adding two egdes
having start vertex $g_{1}$ and $g_{2}$, respectively. Due to this, note that
pointings of the green vertices do not violate the general phylogenetic
network properties by making a directed cyclic component. Also, to avoid
multiple edges, set up the generating function $\tilde{M_{1}}(z,y_{1}+y_{2})$
for the tree attached to the green vertex $g_{1}$. In general
$\tilde{M_{i}}(z,y_{1}+y_{2})=(1-zy_{i})M(z,y_{1}+y_{2})$ is the specification
of unary root Motzkin trees such that pointer vertex which already marked by
variable $y_{i}$, is not allowed to point to the root vertex. So this means
pointing to the root of this tree is forbidden for $g_{1}$ but not for
$g_{2}$. For all the other trees there is no pointing restriction. The
analysis of the vertices on the paths is done path by path.

  * •

Path $\ell$: No green vertex is allowed to point to the vertices of that path.

  * •

Path $k$: Except first node, pointing to all vertices is allowed for $g_{2}$,
but $g_{1}$ may not point to that path at all. So we have

$\displaystyle G_{a}^{\nshortparallel}(z)$
$\displaystyle=\partial_{y_{1}}\partial_{y_{2}}z^{2}\tilde{M}_{1}(z,y_{1}+y_{2})P(z,y_{2},y_{1}+y_{2},0)P(z,0,y_{1}+y_{2},0)\Big{|}_{y_{1}=0,y_{2}=0}.$

Now, consider the Motzkin skeleton $(b)$. For the trees attached to the green
vertices only pointing to the root is forbidden for parent vertices, for all
the other trees there is no pointing restriction. The analysis of the vertices
on the paths is done path by path.

  * •

Path $r$: No green vertex is allowed to point to the vertices of that path.

  * •

Path $k$: Pointing to all vertices is allowed for $g_{2}$, but $g_{1}$ may not
point to that path at all. The situation for path $\ell$ is symmetric.

In this way, Motzkin skeletons which are not respecting the general condition
are generated as well: Indeed, $g_{1}$ may point to the vertex of $\ell$ and
$g_{2}$ to the vertex of $k$, thus violating the generality condition by
making a cycle. The factor $\frac{1}{2}$ in the beginning of expression comes
from the “horizontal symmetry” (This can be briefly shown by H-S) of the
Motzkin skeleton. This yields the generating function

$\displaystyle G_{b}^{\nshortparallel}(z)$
$\displaystyle=\frac{1}{2}\partial_{y_{1}}\partial_{y_{2}}\left(\frac{z^{3}\tilde{M}_{1}(z,y_{1}+y_{2})\tilde{M}_{2}(z,y_{1}+y_{2})}{1-zM(z,y_{1}+y_{2})}P(z,y_{2},y_{1}+y_{2},y_{2})P(z,y_{1},y_{1}+y_{2},y_{1})\right.$
$\displaystyle-\left.\frac{z^{3}M(z,0)^{2}}{1-zM(z,0)}P(z,y_{2},0,y_{2})P(z,y_{1},0,y_{1})\Big{|}_{y_{1}=0,y_{2}=0}\right).$

The other case of general networks has the Motzkin skeleton as shown in Figure
7, $(c)$. The property of red-green leaf entails, first one added directed
edges connects $g_{1}$ to $r_{g}$. After that, there is no restriction for
pointing of $r_{g}$ except the vertices on the paths. This gives

$\displaystyle G_{c}^{\nshortparallel}(z)=$
$\displaystyle\partial_{y_{r}}\frac{z^{3}M(z,y_{r})}{(1-zM(z,y_{r}))^{3}}\Big{|}_{y_{r_{g}}=0}.$

Now, consider the Motzkin skeleton $(d)$ of Figure 7. The double-green vertex
$g_{g}$ can point to all vertices (the pointing order does not matter, so we
divide by $2$) in the attached subtrees.

$\displaystyle G_{d}^{\nshortparallel}(z)$
$\displaystyle=\frac{1}{2}(\partial_{y_{g}})^{2}\frac{z}{1-zM(z,y_{g})}\Big{|}_{y_{g}=0}.$

For the final case, consider the Motzkin skeleton $(e)$. Generality condition
entails that $r_{g}$ be only possible target vertex for pointing of $g_{2}$.
For all the other trees there is no pointing restriction for $r_{g}$. To avoid
of multiple edges, the path $k$ cannot be a simple edge. To do that set the
generating function

$P^{\star}(z,y,\tilde{y},\hat{y})=P(z,y,\tilde{y},\hat{y})-1=\frac{zM(z,\tilde{y})+z\hat{y}}{1-z(y+M(z,\tilde{y}))},$

for a nonempty path. Then we get

$\displaystyle G_{e}^{\nshortparallel}(z)$
$\displaystyle=\partial_{y_{r}}\frac{z}{1-zM(z,y_{r})}P^{\star}(z,0,y_{r},0)\Big{|}_{y_{r}=0}=\partial_{y_{r}}\frac{z^{2}M(z,y_{r})}{(1-zM(z,y_{r}))^{2}}\Big{|}_{y_{r}=0}.$

The exponential generating function for vertex-labeled general networks (with
no multiple edges) is obtained as
$G_{2}^{\nshortparallel}(z)=G_{a}^{\nshortparallel}(z)+G_{b}^{\nshortparallel}(z)+G_{c}^{\nshortparallel}(z)+G_{d}^{\nshortparallel}(z)+G_{e}^{\nshortparallel}(z)/4$
after all. This gives the following result.

$\displaystyle{G}_{2}^{\nshortparallel}(z)=z\cdot\frac{a_{2}^{\nshortparallel}(z^{2})-b_{2}^{\nshortparallel}(z^{2})\sqrt{1-2z^{2}}}{(1-2z^{2})^{7/2}},$
(10)

where

$\displaystyle
a_{2}^{\nshortparallel}(z)=z^{4}+\frac{1}{2}z^{2}+\frac{3}{2}z\quad\text{ and
}\quad b_{2}^{\nshortparallel}(z)=z^{2}+\frac{3}{2}z.$ (11)

Figure 8. The possible structures of the Motzkin skeletons of phylogenetic
networks with $2$ reticulation nodes and all possible considered of fixed
multiple edges contributions.

Next we will set up the exponential generating function for general networks
with at least one multiple edges on their structure (see Figure 8).
Altogether, we obtain

$\displaystyle G_{2}^{\shortparallel}(z)$
$\displaystyle=\frac{1}{2}\left(\partial_{y_{2}}z^{3}M(z,y_{2})\dfrac{P(z,y_{2},y_{2},0)}{1-zM(z,y_{2})}\Big{|}_{y_{2}=0}+\partial_{y_{2}}\dfrac{z^{4}M(z,y_{2})\tilde{M}_{2}(z,y_{2})P(z,y_{2},y_{2},y_{2})}{(1-zM(z,y_{2}))^{2}}\Big{|}_{y_{2}=0}\right.$
$\displaystyle\left.+\partial_{y_{1}}\frac{z^{3}\tilde{M}_{1}(z,y_{1})}{(1-zM(z,y_{1}))^{2}}\Big{|}_{y_{1}=0}+\partial_{y_{r}}\dfrac{z^{2}}{(1-zM(z,y_{r}))}\Big{|}_{y_{r}=0}\right)$
$\displaystyle+\dfrac{z^{4}M(z,0)}{(1-zM(z,0))^{2}}+\frac{1}{2}\dfrac{z^{5}M^{2}(z,0)}{(1-zM(z,0))^{3}},$

where the factor $2$ appears for the expression of $(1)$ to $(4)$, because in
these cases each general phylogenetic network is generated two times. Note
that, there is just a unique general network which arises from the Case $5$.
Also, the factor $2$ appears in last term, because of horizontal symmetry. ∎

So the exponential generating function for vertex-labeled general phylogenetic
networks with two reticulation nodes is then
$G_{2}(z)=G_{2}^{\nshortparallel}(z)+G_{2}^{\shortparallel}(z)$. As an easy
consequence, we obtain the asymptotic number of networks.

######  Corollary .

Let $G_{2,n}$ denote the number of vertex-labeled general phylogenetic
networks with $n$ vertices and exactly two reticulation vertex. If $n$ is even
then $G_{2,n}$ is zero, otherwise

$G_{2,n}=n![z^{n}]G_{2}(z)=\left(\frac{\sqrt{2}}{e}\right)^{n}n^{n+3}\left(\frac{\sqrt{2}}{16}-\frac{\sqrt{\pi}}{8}\cdot\frac{1}{\sqrt{n}}+{\mathcal{O}}\left(\frac{1}{n}\right)\right),$

as ${n\to\infty}$.

###### Proof.

This follows by singularity analysis as before. ∎

####  4.1.1. Explicit formula for vertex-labeled general networks with two
reticulation vertices

We can use generating functions $G_{2}^{\nshortparallel}(z)$ and
$G_{2}^{\shortparallel}(z)$ to extract closed formulas for vertex-labeled
general networks. To see that, consider the contribution of each of them
separately. Start with the exponential generating function
$G_{2}^{\nshortparallel}(z)$ for general networks that do not have double
edges in own structures.

First, set $n=2m+1$. Then, from 10 we obtain

$[z^{n}]{G}_{2}^{\nshortparallel}(z)=[z^{m}]\bar{G}_{2}^{\nshortparallel}(z)$

with

$\bar{G}_{2}^{\nshortparallel}(z)=\frac{a_{2}^{\nshortparallel}(z)-b_{2}^{\nshortparallel}(z)\sqrt{1-2z}}{(1-2z)^{7/2}},$

where $a_{2}^{\nshortparallel}(z)$ and $b_{2}^{\nshortparallel}(z)$ are as in
11. So we have

$[z^{m}]\bar{G}_{2}^{\nshortparallel}(z)=[z^{m}]\dfrac{a_{2}^{\nshortparallel}(z)}{(1-2z)^{\frac{7}{2}}}-[z^{m}]\dfrac{b_{2}^{\nshortparallel}(z)}{(1-2z)^{3}}.$

After some computation we have

$[z^{m}]\bar{G}_{2}^{\nshortparallel}(z)=2^{m-2}\Big{(}P_{1}(m)\frac{\displaystyle
2m\binom{2m}{m}}{15(2m-1)4^{m}}-P_{2}(m)\Big{)},$

where

$\displaystyle P_{1}(m)=30m^{3}+20m^{2}+15m-20\quad\text{ and }\quad
P_{2}(m)=2m^{2}+m.$ (12)

By replacing $m=(n-1)/2$ this implies

$\displaystyle
G_{2,n}^{\nshortparallel}=n!2^{(n-5)/2}\Big{(}P_{1}((n-1)/2)\frac{\displaystyle(n-1)\binom{n-1}{(n-1)/2}}{15(n-2)2^{n-1}}-P_{2}((n-1)/2)\Big{)}.$
(13)

Note that correspondent generating function for general networks with multiple
edges is

$\displaystyle{G}_{2}^{\shortparallel}(z)=z\cdot\frac{a_{2}^{\shortparallel}(z^{2})-b_{2}^{\shortparallel}(z^{2})\sqrt{1-2z^{2}}}{(1-2z^{2})^{1/2}},$

such that

$\displaystyle a_{2}^{\shortparallel}(z)=z^{2}+z\quad\text{ and }\quad
b_{2}^{\shortparallel}(z)=z.$

In the same way, it can be used to get exact formula for vertex-labeled
general networks that are belong to this subclass. We refrain from giving
details and just list the obtained expressions. The reader is invited to
derive them herself.

$\displaystyle
G_{2,n}^{\shortparallel}=n!2^{(n-3)/2}(n-1)\Big{(}\frac{\displaystyle(n-1)\binom{n-1}{(n-1)/2}}{2^{n}}-\frac{1}{2})\Big{)}.$
(14)

After all by summing up 13 and 14 we have

$\displaystyle
G_{2,n}=G_{2,n}^{\nshortparallel}+G_{2,n}^{\shortparallel}=n!2^{(n-3)/2}\Big{(}A((n-1)/2)\frac{\displaystyle(n-1)\binom{n-1}{(n-1)/2}}{15(n-2)2^{n-1}}-B((n-1)/2)\Big{)},$
(15)

where

$\displaystyle A(m)=30m^{3}+80m^{2}-15m-20\quad\text{ and }\quad
B(m)=m^{2}+\frac{3}{2}m.$ (16)

####  4.1.2. Explicit formula for leaf-labeled general networks with two
reticulation vertices

Note that, the Equation (6) which comes from the described procedure in
Section 4.0.2 for construction all vertex-labeled networks from fixed leaf-
labeled ones does not work anymore. It is because by applying the method there
are some leaf-labeled networks which generate some vertex-labeled networks
more than one (here twice). Thus for normalization, and deal with symmetry the
correspondent generating functions of such networks can be considered
separately (see Figure 9).

Figure 9. (Top) The structure of general network with two reticulation
vertices such that two vertices have the same set of descendant which can be
generate from (a) by pointing green vertices to the root of each other
attached trees or (b) a double-green vertex points to unary vertices with same
parent.

So we have

${G}_{2}^{\nshortparallel}(z)={\dot{G}}_{2}^{\nshortparallel}(z)+{\ddot{G}}_{2}^{\nshortparallel}(z),$

where ${\dot{G}}_{2}^{\nshortparallel}(z)$ correspondent generating function
for general networks such that the procedure set out in Section 4.0.2 can be
applied directly for them.

$\displaystyle{\dot{G}}_{2}^{\nshortparallel}(z)=z\cdot\frac{\dot{a}_{2}^{\nshortparallel}(z^{2})-\dot{b}_{2}^{\nshortparallel}(z^{2})\sqrt{1-2z^{2}}}{(1-2z^{2})^{7/2}},$

where,

$\displaystyle\dot{a}_{2}^{\nshortparallel}(z)=-4z^{5}+11z^{4}-9z^{3}+4z^{2}+z\quad\text{
and }\quad\dot{b}_{2}^{\nshortparallel}(z)=4z^{4}-6z^{3}+4z^{2}+z.$

For this set of general networks we can directly use Equation (6). Thus, same
procedure as like before gives us

$\displaystyle\dot{G}_{2,\ell}^{\nshortparallel}=\ell!2^{\ell-1}\Big{(}(6\ell^{4}+19\ell^{3}+18\ell^{2}-7\ell-3)\frac{\displaystyle(\ell+1)\binom{2\ell+2}{\ell+1}}{(6\ell-3)(2\ell+1)4^{\ell}}-(2\ell^{2}+5\ell+3)\Big{)}.$
(17)

Now we set up generating function for family of networks which are shown in
the top of Figure 9. It is not hard to see that, by using the previous methods
each related (fixed) leaf-labeled general network can construct a vertex-
labeled general network exactly twice (because of symmetry). For this case
Equation (6) can modify as
${\ddot{G}}^{\nshortparallel}_{2,\ell}=2\frac{\ell!}{n!}{\ddot{G}}^{\nshortparallel}_{2,n}.$
The generating function for this subfamily of general networks is

$\displaystyle{\ddot{G}}_{2}^{\nshortparallel}(z)=z\cdot\frac{\ddot{a}_{2}^{\nshortparallel}(z^{2})-\ddot{b}_{2}^{\nshortparallel}(z^{2})\sqrt{1-2z^{2}}}{(1-2z^{2})^{1/2}},$

where

$\displaystyle\ddot{a}_{2}^{\nshortparallel}(z)=-\frac{1}{2}z^{2}+\frac{1}{2}z\quad\text{
and }\quad\ddot{b}_{2}^{\nshortparallel}(z)=\frac{1}{2}z.$

After some manipulation we get

$\displaystyle\ddot{G}_{2,\ell}^{\nshortparallel}=\ell!2^{\ell-1}\Big{(}\frac{\displaystyle(\ell+1)\binom{2\ell+2}{\ell+1}}{(2\ell-1)(2\ell+1)4^{\ell}}\Big{)}.$

The explicit formula for leaf-labeled general networks with no multiple edges
and two reticulation vertices is

$\displaystyle\begin{aligned}
G_{2,\ell}^{\nshortparallel}&=\dot{G}_{2,\ell}^{\nshortparallel}+\ddot{G}_{2,\ell}^{\nshortparallel}\\\
&=\ell!2^{\ell-1}\Big{(}(6\ell^{4}+19\ell^{3}+18\ell^{2}-7\ell)\frac{\displaystyle(\ell+1)\binom{2\ell+2}{\ell+1}}{(6\ell-3)(2\ell+1)4^{\ell}}-(2\ell^{2}+5\ell+3)\Big{)}.\end{aligned}$
(18)

To complete the details, we can get explicit formula for the number of leaf-
labeled networks that are generated by sparsened skeletons which as depicted
in Figure 8. Note that for this case, all generated networks belong to the
first subclass of general networks which the Equation 6 can be used directly.
So we have

$\displaystyle
G_{2,\ell}^{\shortparallel}=\ell!2^{\ell+1}(\ell+1)\Big{(}\frac{\displaystyle(\ell+1)\binom{2\ell+2}{\ell+1}}{4^{\ell+1}}-\frac{1}{2}\Big{)}.$

After all, we get

$\displaystyle\displaystyle\tilde{G}_{2,\ell}=G_{2,\ell}^{\nshortparallel}+G_{2,\ell}^{\shortparallel}=\ell!2^{\ell-1}\Big{(}A(\ell)\frac{\displaystyle(\ell+1)\binom{2\ell+2}{\ell+1}}{(6\ell-3)(2\ell+1)4^{\ell}}-B(\ell)\Big{)}\Big{)},$
(19)

where

$\displaystyle A(\ell)=6\ell^{4}+31\ell^{3}+30\ell^{2}-10\ell-3\quad\text{ and
}\quad B(\ell)=2\ell^{2}+\frac{41}{8}\ell+\frac{25}{8}.$ (20)

In the same way, the methods can be used to study of specifications for
general phylogenetic networks with $k\geq 3$ reticulation nodes. Its obvious
by increasing number of rediculation nodes we have to consider various number
of the Motzkin skeletons to cover all possible cases. For more understanding,
we invite the reader to look at Appendix section to see all the Motzkin
skeletons and related specifications for $k=3$. As similar as $k=2$, first we
focus on structures with no multiple edges and then for each Motzkin skeleton
consider possible contributions of double edges on the structures and add them
to the results. After all this gives
$G_{3}(z)=G_{3}^{\nshortparallel}(z)+G_{3}^{\shortparallel}(z)$ ( See Appendix
A for more details) such that causes following results for vertex-labeled
general networks with fixed $3$ reticulation vertices.

######  Proposition 4.

The exponential generating function for vertex-labeled general phylogenetic
networks with three reticulation nodes is

${G}_{3}(z)=G_{3}^{\nshortparallel}(z)+G_{3}^{\shortparallel}(z)=z\cdot\frac{a_{3}(z^{2})-b_{3}(z^{2})\sqrt{1-2z^{2}}}{(1-2z^{2})^{11/2}},$

where

$a_{3}(z)=z^{6}+5z^{5}-10z^{4}-\frac{23}{2}z^{3}+\frac{109}{4}z^{2},$

and,

$b_{3}(z)=z^{5}-\frac{7}{2}z^{4}-5z^{3}+\frac{109}{4}z^{2}.\;\;\;\;\;$

######  Corollary .

Let $G_{3,n}$ denote the number of vertex-labelled general phylogenetic
networks with $n$ vertices and exactly three reticulation vertex. If $n$ is
even then $G_{3,n}$ is zero, otherwise

$G_{3,n}=n![z^{n}]G_{3}(z)=\left(\frac{\sqrt{2}}{e}\right)^{n}n^{n+5}\left(\frac{\sqrt{2}}{192}-\frac{\sqrt{\pi}}{64}\cdot\frac{1}{\sqrt{n}}+{\mathcal{O}}\left(\frac{1}{n}\right)\right),$

as ${n\to\infty}$.

Also, consequently as similar as before we can take the explicit formulas for
vertex and leaf-labeled general networks with $3$ reticulation vertices. For
vertex labelled case, as like before we set $n=2m+1$, so we have

$[z^{n}]{G}_{3}(z)=[z^{m}]\bar{G}_{3}(z),$

such that,

$[z^{m}]\bar{G}_{3}(z)=[z^{m}]\dfrac{a_{3}(z)}{(1-2z)^{\frac{11}{2}}}-[z^{m}]\dfrac{b_{3}(z)}{(1-2z)^{5}}.$

It gives

$\mathcal{F}(m):=[z^{m}]\bar{G}_{3}(z)=\frac{2^{m-6}}{3}\Big{(}A_{1}(m)\frac{\displaystyle
m(m-1)\binom{2m}{m}}{35(2m-1)4^{m-2}}-B_{1}(m)\Big{)},$

where

$A_{1}(m)=104m^{4}+836m^{3}+876m^{2}-454m-79\quad\text{and,}\quad
B_{1}(m)=48m^{4}+127m^{3}-60m^{2}-121m+6.$ (21)

By replacing $m=(n-1)/2$, we have,

$G_{3,n}=n!\cdot\mathcal{F}((n-1)/2).$

we need some more arguments to extract explicit formula for the leaf-labeled
case. It is because of symmetry that we can see in some of the generated
networks. For someone who is interest, complete details of steps can be found
in the Appendix section.
Now, the defined structure for paths of sparsened skeletons with well defined
generating function (1) for attached trees, capable us to prove the theorem 1.
Proof of Theorem 1. In particular note that function $G(z,y)$ is the form $zM$
(1), which $z$ refers to vertices lie on the pathes of sparsened skeleton.

$\displaystyle G(z,y)=a(z,y)-b(z,y)\sqrt{1+(y^{2}-2)z^{2}-2zy},$ (22)

where $a(z,y),b(z,y)$ are polynomials in $z$ and $y$ with $a(z,0)=b(z,0)=1$.
In summary, we have exponential generating function $G_{k}$ for phylogenetic
network in sum of terms of the form

$\displaystyle\partial_{y_{1}}\cdots\partial_{y_{k}}\frac{G_{1}(z,y)\cdots
G_{s}(z,y)}{(1-G_{s+1}(z,y))\cdots(1-G_{s+t}(z,y))}\Big{|}_{y_{1}=0,\ldots,y_{k}=0},$
(23)

Note that in this expression, numerator refers to generating function of
subtrees which rooted at green vertices. The denominator refers to sequences
of subtrees which rooted the vertices on the paths of sparsened skeleton. Also
where the number of functions $G_{s+i}(z,y)$ is bounded by the number of edges
of the sparsened skeleton increased by one (for the sequence of trees added
above the root when constructing the Motzkin skeletons). Now, recall lemma
$3.1$ from [13] which can be used for any similar structures as $G(z,y)$. We
can apply this lemma after expanding (23) and obtain that

$\displaystyle
G_{k}(z)=\frac{a_{k}(z)-b_{k}(z)\sqrt{1-2z^{2}}}{(1-2z^{2})^{p}}.$ (24)

We proceed to show that $p=2k-1/2$. For that, observe (23) without the
derivatives is of the general form given in (24) with the exponent of the
denominator equals $t/2$ which reaches its maximum for the sparsened skeleton
with the maximal number of edges and is thus at most $k-1/2$. Also, from the
above lemma, we see that each differentiation increases the exponent by $1$.
Thus, the exponent of (23) when written as (24) is at most $2k-1/2$. Adding up
this terms gives

$G_{k}(z)=\frac{{a}_{k}(z)-{b}_{k}(z)\sqrt{1-2z^{2}}}{(1-2z^{2})^{2k-1/2}},$

where $a_{k}(z)$ and $b_{k}(z)$ are suitable polynomials. Let $G_{k,n}$ denote
the number of vertex-labeled general phylogenetic networks with $n$ vertices
and $k$ reticulation vertices. If $n$ is even then $G_{k,n}$ is zero,
otherwise there is a positive constant ${d}_{k}$ such that as
$n\rightarrow\infty$,

$G_{k,n}=n![z^{n}]G_{k}(z)\sim{d}_{k}\left(\frac{\sqrt{2}}{e}\right)^{n}n^{n+2k-1},$

Where by singularity analysis and Stirling’s formula we get

${d}_{k}=\frac{2\sqrt{2\pi}{a}_{k}(1/\sqrt{2})}{4^{k}\Gamma(2k-1/2)}.$

$\square$

######  Remark .

For the positivity claim, we already see in [13] that corresponding constant
$\tilde{d}_{k}$ for normal and tree-child networks is positive which is lower
bound of $d_{k}$ for general networks.

######  Proposition 5.

For the numbers of vertex-labeled general phylogenetic networks $G_{k,n}$ and
vertex-labeled tree-child networks $T_{k,n}$,

$\displaystyle G_{k,n}=T_{k,n}\left({1+\mathcal{O}}(\frac{1}{n})\right),$ (25)

as ${n\to\infty}$.

###### Proof.

First, observe that $G_{k,n}-T_{k,n}$ is bounded by the number of networks
which arise from all types of Motzkin skeletons where for each green vertex,
the considered all possibilities of adding an edge violates the tree-child
condition. Note that, the largest number will come from the sparsened
skeletons where all pointer vertices are the leaves. Now, fix such a type of
Motzkin skeletons and one of its green vertices. Then, for this vertex, we
will have the following options.

  * •

The green vertex points to the root of the subtree which is attached to the
one of green vertices in the Motzkin skeletons. Note that if it points to the
root of its subtree, tree-child condition violates by making multiple edge.
For the exponential generating function this gives

$\partial_{y_{2}}\cdots\partial_{y_{k}}\frac{G_{1}(z,y)\cdots
G_{s}(z,y)}{(1-G_{s+1}(z,y))\cdots(1-G_{s+2k-1}(z,y))}\Big{|}_{y_{2}=0,\ldots,y_{k}=0},$

Here, and below $y$ is the sum of $y_{i}$’s with $2\leq i\leq k$ and not all
of the $y_{i}$’s must be present; also which are present can differ from one
occurrence to the next.

  * •

There is a red-green vertex on the Motzkin skeleton. Note that the red-green
property entails that one another pointer vertex joints to this leaf by adding
directed edge which reduces the number of the derivative by one. Then we get

$\partial_{y_{2}}\cdots\partial_{y_{k}}\frac{G_{1}(z,y)\cdots
G_{s-1}(z,y)}{(1-G_{s+1}(z,y))\cdots(1-G_{s+2k-1}(z,y))}\Big{|}_{y_{2}=0,\ldots,y_{k}=0}.$

  * •

There is double-green vertex in the Motzkin skeleton that points to the
branches of sparsened skeleton. Then, we have

$\partial_{y_{3}}\cdots\partial_{y_{k}}\frac{G_{1}(z,y)\cdots
G_{s-2}(z,y)}{2\cdot(1-G_{s+1}(z,y))\cdots(1-G_{s+2k-1}(z,y))}\Big{|}_{y_{2}=0,\ldots,y_{k}=0}.$

The existence of double green node in considered skeleton is like that two
green vertices are merged to each others. Consequently, the number of edges
reduce by two, which also leads to a contribution of smaller order.

The exponential generating function of all networks arising from these Motzkin
skeletons and the pointer vertices are a sum of generating functions of the
above three types. Thus, we obtain that this generating function has the form

$\frac{c(z)-d(z)\sqrt{1-2z^{2}}}{(1-2z^{2})^{p}},$

where $c(z)$ and $d(z)$ are suitable polynomials and the maximum of $p$ is as
follows: note that without the derivatives in the above expressions, $p$ would
be at most $k-1/2$. Also, because of above lemma, each derivative increases
this bound by one. Thus, $p$ is at most $2k-\frac{3}{2}$.

Now, we obtain that the exponential generating function of the above number
has the form

$\frac{{c}(z)-{d}(z)\sqrt{1-2z^{2}}}{(1-2z^{2})^{2k-\frac{3}{2}}},$

where ${c}(z)$ and ${d}(z)$ are suitable polynomials. Singularity analysis
gives then the bound

${\mathcal{O}}\left(\left(\frac{\sqrt{2}}{e}\right)^{n}n^{n+2k-2}\right).$

Summing over all possible type of Motzkin skeletons and all green vertices, we
obtain the claimed result. ∎

Vertex Labeled |  k=1 |  k=2 |  k=3
---|---|---|---
Phylogenetic |  |  |
Networks |  $c_{1}$ $c_{1}^{\prime}$ |  $c_{2}$ $c_{2}^{\prime}$ |  $c_{3}$ $c_{3}^{\prime}$
$N_{k,n}$ |  $\frac{\sqrt{2}}{2}$ $-\frac{3\sqrt{\pi}}{2}$ |  $\frac{\sqrt{2}}{16}$ $-\frac{3\sqrt{\pi}}{8}$ |  $\frac{\sqrt{2}}{192}$ $-\frac{3\sqrt{\pi}}{64}$
|  |  |
$T_{k,n}$ |  $\frac{\sqrt{2}}{2}$ $-\frac{\sqrt{\pi}}{2}$ |  $\frac{\sqrt{2}}{16}$ $-\frac{\sqrt{\pi}}{8}$ |  $\frac{\sqrt{2}}{192}$ $-\frac{\sqrt{\pi}}{64}$
|  |  |
$G_{k,n}$ |  $\frac{\sqrt{2}}{2}$ $-\frac{\sqrt{\pi}}{2}$ |  $\frac{\sqrt{2}}{16}$ $-\frac{\sqrt{\pi}}{8}$ |  $\frac{\sqrt{2}}{192}$ $-\frac{\sqrt{\pi}}{64}$
Table 2.  The first two asymptotic orders of normal, tree-child and general
phylogenetic networks with at most $3$ reticulation vertices. For all of them
the first coefficient is same.

###  4.2. Asymptotic counting of leaf-labeled general phylogenetic Networks

In this part we want to prove Theorem 2 and argue that for the number of leaf-
labeled general phylogenetic networks with $k\geq 1$ reticulation vertices (as
like leaf-labeled tree-child ($\tilde{T}_{k,\ell}$) and normal networks, see
[13]) we can use,

$\displaystyle\tilde{G}_{k,\ell}\sim
2^{3k-1}d_{k}\left(\frac{2}{e}\right)^{\ell}\ell^{\ell+2k-1},\qquad(\ell\rightarrow\infty)$
(26)

as a relative precise estimate of leaf-labeled general phylogenetic network,
where $d_{k}$ is as in Theorem 1.

It is enough to show that the number of a subfamily $\mathcal{G}$ of general
networks such that some of their vertices have the same set of descendant are
rare. Indeed, $\mathcal{G}$ consists of general networks that equation $(6)$
can not be used directly for them. It’s because of that in the described
method (see 4.0.2 ) some of the fix leaf-labeled networks generate vertex-
labeled networks more than one. In other words, having a pair of vertices with
a set of the same descendant is necessary condition but not sufficient to
generate vertex-labeled networks twice or more. For instance, consider a leaf
which is attached edge $(u,g_{i})$ in Figure 10 (a). Though, $g_{1}$ and
$g_{2}$ have a set of the same descendant but applying the procedure (4.0.2),
generates each vertex-labeled uniquely.

Figure 10. The structures of general phylogenetic networks where pair of
vertices have a same descendant set after adding the directed edges in Motzkin
skeletons.

Proof of Theorem2. Consider a subfamily $\mathcal{G}$ as similar before. It is
sufficient for our purposes to show that when $\ell\rightarrow\infty$, the
number of these networks are asymptotically negligible. Assume, without loss
of generality, these networks are without multiple edges because each of them
reduces the number of differentiations in the expression for the exponential
generating function by one, that causes the contribution of lower-order.
Note that, $\mathcal{G}$ is bounded by the number of networks which arise from
two types of Motzkin skeletons that are depicted in Figure 10. First, when two
green vertices point to the child vertices of each others (Figure 10, (a)) and
second, a double-green vertex points unary vertices with the same parent (b).
In the former case, two green vertices and in the later case double-green
vertex with vertex $v$ have set of the same descendant. Note that in each of
described cases, the number of derivatives and consequently, the power of
denominator in exponential generating function will be reduce by two. So The
first two asymptotic orders are as in theorem 1. That implies

$\displaystyle
G_{k,2\ell+2k-1}\sim\binom{2\ell+2k-1}{\ell}(\ell+2k-1)!\tilde{G}_{k,\ell}.$
(27)

Now we have
$\tilde{G}_{k,\ell}\sim\frac{\ell!}{(2\ell+2k-1)!}G_{k,2\ell+2k-1}$, which an
asymptotic result (26) follows by Theorem 1 and Stirling’s formula.

$\square$

## Acknowledgment

I would like to thank the Bernhard Gittenberger and Michael Fuchs for
critically reading the manuscript and making suggestions that led to
significant improvements to the content and clarity of the paper.

## References

  * [1] Nikita Alexeev and Max A. Alekseyev.  Combinatorial scoring of phylogenetic networks.  In Computing and combinatorics, volume 9797 of Lecture Notes in Comput. Sci., pages 560–572. Springer, [Cham], 2016.
  * [2] photo Hans-Jurgen Bandelt.  Phylogenetic networks.  In Verhandlungen des Naturwissenschaftlichen Vereins Hamburg, volume 34, pages 51–71, 1994.
  * [3] Miklós Bóna.  On the number of vertices of each rank in $k$-phylogenetic trees.  Discrete Math. Theor. Comput. Sci., 18(3):Paper No. 7, 7, 2016.
  * [4] Miklós Bóna and Philippe Flajolet.  Isomorphism and symmetries in random phylogenetic trees.  J. Appl. Probab., 46(4):1005–1019, 2009.
  * [5] Magnus Bordewich and Charles Semple.  Determining phylogenetic networks from inter-taxa distances.  J. Math. Biol., 73(2):283–303, 2016.
  * [6] Mathilde Bouvel, Philippe Gambette, and Marefatollah Mansouri.  Counting phylogenetic networks of level 1 and 2. arxiv:1909.10460v2.  2019\.
  * [7] Gabriel Cardona, Joan Carles Pons, and Celine Scornavacca.  Correction: Generation of binary tree-child phylogenetic networks.  PLOS Computational Biology, 15(10):1–1, 10 2019.
  * [8] Éva Czabarka, Péter L. Erdős, Virginia Johnson, and Vincent Moulton.  Generating functions for multi-labeled trees.  Discrete Appl. Math., 161(1-2):107–117, 2013.
  * [9] Filippo Disanto and Noah A. Rosenberg.  Enumeration of ancestral configurations for matching gene trees and species trees.  J. Comput. Biol., 24(9):831–850, 2017.
  * [10] Philippe Flajolet and Robert Sedgewick.  Analytic combinatorics.  Cambridge University Press, Cambridge, 2009.
  * [11] Leslie R. Foulds and Robert W. Robinson.  Determining the asymptotic number of phylogenetic trees.  In Combinatorial mathematics, VII (Proc. Seventh Australian Conf., Univ. Newcastle, Newcastle, 1979), volume 829 of Lecture Notes in Math., pages 110–126. Springer, Berlin, 1980.
  * [12] Leslie R. Foulds and Robert W. Robinson.  Enumerating phylogenetic trees with multiple labels.  In Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986), volume 72, pages 129–139, 1988\.
  * [13] 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.
  * [14] Dan Gusfield, Satish Eddhu, and Charles Langley.  Efficient reconstruction of phylogenetic networks with constrained recombination.  In CSB03, pages 363–374, 2003.  http://wwwcsif.cs.ucdavis.edu/ gusfield/ieeefinal.pdf.
  * [15] D.H. Huson, R. Rupp, and C. Scornavacca.  Phylogenetic Networks: Concepts, Algorithms and Applications.  Cambridge University Press, 2010.
  * [16] C. Randal Linder and Loren H. Rieseberg.  Reconstructing patterns of reticulate evolution in plants.  American Journal of Botany, 91(10):1700–1708, 2004.  http://www.amjbot.org/cgi/reprint/91/10/1700.pdf.
  * [17] Simone Linz, Katherine St. John, and Charles Semple.  Counting trees in a phylogenetic network is #P-complete.  SIAM J. Comput., 42(4):1768–1776, 2013.
  * [18] Colin McDiarmid, Charles Semple, and Dominic Welsh.  Counting phylogenetic networks.  Ann. Comb., 19(1):205–224, 2015.
  * [19] Noah A. Rosenberg.  Counting coalescent histories.  J. Comput. Biol., 14(3):360–377, 2007.
  * [20] Ernst Schröder.  Vier kombinatorische Probleme.  Z. Math. Phys., 15:361–376, 1870.
  * [21] Charles Semple.  Phylogenetic networks with every embedded phylogenetic tree a base tree.  Bull. Math. Biol., 78(1):132–137, 2016.
  * [22] Charles Semple.  Size of a phylogenetic network.  Discrete Appl. Math., 217(part 2):362–367, 2017.
  * [23] Charles Semple and Jack Simpson.  When is a phylogenetic network simply an amalgamation of two trees?  Bulletin of Mathematical Biology, 80(9):2338–2348, Sep 2018.
  * [24] Charles Semple and Mike Steel.  IEEE/ACM Trans. Comput. Biology Bioinform., 3:84–91, 2006.
  * [25] P. H. A. Sneath.  Cladistic representation of reticulate evolution.  Systematic Zoology, 24(3):360–368, 1975.
  * [26] Louxin Zhang.  Counting tree-child networks and their subclasses. arxiv:1908.01917v2.  2019\.
  * [27] Louxin Zhang.  Generating normal networks via leaf insertion and nearest neighbor interchange.  BMC Bioinformatics, 20(20):642, Dec 2019.

##  Appendix A General Phylogenetic Network With Three Reticulation Nodes

This section presents a theoretical extension of the studied procedure for
general phylogenetic network with three reticulation vertices. As like before,
we decompose the network according to how the reticulation vertices are
distributed in the networks. For more explicitly, first consider the Motzkin
skeletons with just green vertices ( Figure 11). We can use them to figure out
the rest of Motzkin skeletons with red-green and double-green vertices as
well. In the end, we add the contribution of the Motzkin skeletons with
multiple edges. For $i,\ j\in\\{1,2,3,r,g\\}$, use $Y_{i,...,j}$ denotes the
operator differentiating with respect to $y_{i},...,\ y_{j}$ and setting
$y_{i}=...=y_{j}=0$ afterwards, _i.e._ , $\
Y_{i,...,j}f(z,y_{i},...,y_{j})=\left(\partial_{y_{i}}...\partial_{y_{j}}f\right)(z,0,...,0)$.
Now we investigate the details of extracting exponential generating function
for cases in the Figure 11. We follow the same procedure that used for general
phylogenetic networks with two reticulation vertices. Start with simple case
which that the three green vertices lie on one path, _i.e._ , one green vertex
is ancestor of another, which itself is ancestor of the third one. All
possibilities for the pointings of the edges starting at $g_{1},g_{2}$ and
$g_{3}$ may target any vertex in all the other trees. Concerning the vertices
on the spine, we have some restrictions. The edge from $g_{1}$ may not end at
any vertex from $\ell_{1}$ , $\ell_{2}$ and the root of its attached subtree.
The edges from $g_{2}$ may not point to first vertex of $\ell_{1}$ (to avoid
of multiple edges) and any vertex of $\ell_{2}$. Finally, no green vertex may
point to the vertex of $\ell_{3}$. Note that the contribution of multiple
edges will be considered in later cases. Overall, this yields the generating
function

$\displaystyle G_{A}(z)$
$\displaystyle=Y_{1,2,3}\left(\frac{z^{3}\tilde{M}_{1}(z,y_{1}+y_{2}+y_{3})}{1-zM(z,y_{1}+y_{2}+y_{3})}P(z,y_{3},y_{1}+y_{2}+y_{3},0)P(z,y_{2}+y_{3},y_{1}+y_{2}+y_{3},y_{3})\right).$

Figure 11. The structure of Motzkin skeletons of networks with $3$
reticulation vertices. All of them, originate from a sparsened skeleton which
consists of only green vertices.

Next we will determine the generating function of all general networks
belonging to case that one green vertex is a common ancestor of the other two,
but none of those two is ancestor of the other one. As in the previous section
we analyse the substructures. There are four vertices in the sparsened
skeleton, yielding a factor $z^{4}$ . Any non-root red vertices in the subtree
attached to $g_{1}$ may be targets of the edge coming from any green nodes and
for root one, pointing is allowed for $g_{2}$ and $g_{3}$ (but not $g_{1}$, to
avoid multiple edges). for the subtree attached to $g_{2}$ vice versa.

  * •

Paths $\ell_{3}$ and $\ell_{4}$: These paths are sequences of vertices, each
with a subtree attached to it. For $\ell_{4}$ each green vertex is allowed to
point at the red vertices in these subtrees. Pointing to the vertices of the
path is not allowed. Likewise, just the corresponding vertices on the path of
$\ell_{3}$ are forbidden for $g_{1}$ and $g_{2}$ by the generality condition
but $g_{3}$ may points non-first vertex of that as well.

  * •

Paths $\ell_{1}$ and $\ell_{2}$: They are symmetric, so we discuss $\ell_{1}$.
The vertices of the subtrees are allowed targets for the edge from all green
vertices. The edge from $g_{2}$ and $g_{3}$ may end at each vertex of the
path.

Note that the generality condition will be violated by making cyclic
component, if $g_{2}$ points a red vetex on the path $\ell_{1}$ and $g_{1}$
vice versa. We subtract this cases from the result. Overall, this gives, again
using the operator $Y_{i,...,j}$ defined above, the generating function

$\displaystyle G_{B}(z)=$
$\displaystyle\frac{1}{2}Y_{1,2,3}\left(\frac{z^{4}\tilde{M}_{1}(z,y_{1}+y_{2}+y_{3})\tilde{M}_{2}(z,y_{1}+y_{2}+y_{3})}{1-zM(z,y_{1}+y_{2}+y_{3})}P(z,y_{1}+y_{3},y_{1}+y_{2}+y_{3},y_{1}+y_{3})\right.\quad$
$\displaystyle\times$ $\displaystyle
P(z,y_{3},y_{1}+y_{2}+y_{3},0)P(z,y_{3}+y_{2},y_{1}+y_{2}+y_{3},y_{3}+y_{2})$
$\displaystyle-$
$\displaystyle\left.\frac{z^{4}M(z,y_{3})^{2}}{(1-zM(z,y_{3}))}P(z,y_{1}+y_{3},y_{3},y_{1}+y_{3})P(z,y_{2}+y_{3},y_{3},y_{2}+y_{3})P(z,y_{3},y_{3},0)\right)$

Next we pay attention to the case that one green vertex is ancestor of another
one, but not of both of them, and the third one is not ancestor of any other
green vertex. The sparsened skeleton has $4$ vertices and the subtrees
attached to $g_{1}$ and $g_{3}$. The red vertices of the subtree of $g_{1}$
and $g_{3}$ may be targeted by any edges starting from green vertices. Note
that if $g_{1}$ and $g_{3}$ have the red root attached subtrees, they are not
allowed to point at own attached red root vertex respectively to avoid
multiple edges. Next we inspect the paths:

  * •

Path $\ell_{4}$: All green vertices may point to the vertices of the subtrees.
Pointing to the path itself is not allowed.

  * •

Path $\ell_{3}$: The edge starting at $g_{3}$ may point to vertices of the
subtrees, but not to the vertices of the path itself. All but the first vertex
for $g_{2}$ of the path as well as all tree vertices can be the end point of
the edge starting at $g_{1}$ and $g_{2}$.

  * •

Path $\ell_{1}$: Similar to $\ell_{3}$. The edges from $g_{2}$ and $g_{3}$ may
point anywhere of the path. The vertices of the subtrees may be targeted by
$g_{1}$ as well.

  * •

Path $\ell_{2}$: All green vertices may point to the vertices of the subtrees.
To point at the vertices on the path is only allowed for $g_{1}$.

Altogether, we obtain the generating function $G_{C}(z)$ with the expression

$\displaystyle G_{C}(z)$
$\displaystyle=Y_{1,2,3}\left(\frac{z^{4}\tilde{M}_{3}(z,y_{1}+y_{2}+y_{3})\tilde{M}_{1}(z,y_{1}+y_{2}+y_{3})}{1-zM(z,y_{1}+y_{2}+y_{3})}P(z,y_{2}+y_{3},y_{1}+y_{2}+y_{3},y_{2}+y_{3})\right.\quad$
$\displaystyle\quad
P(z,y_{1},y_{1}+y_{2}+y_{3},y_{1})P(z,y_{1}+y_{2},y_{1}+y_{2}+y_{3},y_{1})$
$\displaystyle-\frac{z^{4}M(z,0)^{2}}{1-zM(z,0)}P(z,y_{1},0,y_{1})^{2}P(z,y_{2}+y_{3},0,y_{2}+y_{3})$
$\displaystyle-\frac{z^{4}\tilde{M}_{3}(z,y_{3})M_{3}(z,y_{3})}{(1-zM(z,y_{3}))^{2}}P(z,y_{1},y_{3},y_{1})P(z,y_{2},y_{3},y_{2})$
$\displaystyle-\frac{z^{4}M_{2}(z,y_{2})^{2}}{1-zM(z,y_{2})}P(z,y_{1},y_{2},y_{1})P(z,y_{1}+y_{2},y_{2},y_{1})P(z,y_{3},y_{2},y_{3})\Bigg{)}.$

In this way, Motzkin skeletons which are not respecting the generality
condition are generated as well: Indeed, $g_{1}$ may point to the vertex on
the paths $\ell_{2}$ or $\ell_{3}$ when both or one of $g_{2}$ and $g_{3}$
point to vertex of $\ell_{1}$, such that makes directed cyclic component.

The last case of general networks has Motzkin skeletons as shown in Figure 11.
The restriction for the target vertex of the edges to be added at $g_{1}$,
$g_{2}$ and $g_{3}$ follow the analogous rules in order to meet the generality
constraint. Setting up the generating function follows the same pattern as
before. We omit now the details and get from path analysis after all

$\displaystyle G_{D}(z)$ $\displaystyle=\frac{1}{2}Y_{1,2,3}$
$\displaystyle\left(\frac{z^{5}\tilde{M}_{3}(z,y_{1}+y_{2}+y_{3})\tilde{M}_{2}(z,y_{1}+y_{2}+y_{3})\tilde{M}_{1}(z,y_{1}+y_{2}+y_{3})}{1-zM(z,y_{1}+y_{2}+y_{3})}P(z,y_{1}+y_{2},y_{1}+y_{2}+y_{3},y_{1}+y_{2})\right.$
$\displaystyle\times
P(z,y_{1}+y_{3},y_{1}+y_{2}+y_{3},y_{1}+y_{3})P(z,y_{2}+y_{3},y_{1}+y_{2}+y_{3},y_{2}+y_{3})P(z,y_{3},y_{1}+y_{2}+y_{3},y_{3})$
$\displaystyle-\frac{z^{5}\tilde{M}_{3}(z,y_{3})M(z,y_{3})^{2}}{(1-zM(z,y_{3}))^{2}}P(z,y_{1}+y_{3},y_{3},y_{1}+y_{3})P(z,y_{2}+y_{3},y_{3},y_{2}+y_{3})P(z,y_{3},y_{3},y_{3})\Bigg{)}$
$\displaystyle-
Y_{1,2,3}\left(\frac{z^{5}\tilde{M}_{1}(z,y_{3})M(z,y_{1})^{2}}{(1-zM(z,y_{1}))^{2}}P(z,y_{1}+y_{3},y_{1},y_{1}+y_{3})P(z,y_{2}+y_{1},y_{1},y_{2}+y_{1})P(z,y_{3},y_{1},y_{3})\right.$
$\displaystyle-\frac{z^{5}M(z,0)^{3}}{(1-zM(z,0))^{2}}P(z,y_{1},0,y_{1})P(z,y_{2},0,y_{2})P(z,y_{3},0,y_{3})\Bigg{)}.$

So far we just have considered the Motzkin skeletons in Figure 11 with three
reticulation vertices such that only green vertices are considered as pointer
set vertices. Now we consider the structure of the Motzkin skeletons with red-
green and double-green vertices and set up exponential generating functions
for them separately. Note that, the crucial point is that distribution of
pointer nodes on the Motzkin skeleton must be such a way that, after adding
directed edges, we get a general phylogenetic network with $3$ reticulation
vertices. Recall that, for any red-green leaf first we consider another
pointer vertex such that connects to this nodes by adding a directed edge.
Let’s start with the Motzkin skeletons that contain at least one red-green
vertex. Consider a case with three pointer vertices lie on a path (two green
colored vertices with a red-green leaf), such a way that a red-green once lies
on the bottom of the path (left of Figure 12). Note that, we get two different
expressions depends on our choice that which green vertex ($g_{2}$ or $g_{3}$)
is considered first to point red-green leaf.

Figure 12. The structure of Motzkin skeletons with red-green leaves that can
be generated from the Motzkin skeletons $G_{A}(z)$ and $G_{B}(z)$. In the left
and right figures, $g_{1}$ is replaced with a red-green leaf, and in the right
one two red-green leaves are considered as a pointer vertex at the end of
cherry.

$\displaystyle G_{A}^{r_{g}}(z)$
$\displaystyle=Y_{r,3}\frac{z^{3}P^{\star}(z,y_{3},y_{r}+y_{3},y_{3})P(z,y_{3},y_{r}+y_{3},0)}{1-zM(z,y_{r}+y_{3})}+Y_{r,2}\dfrac{z^{3}P(z,y_{2},y_{r}+y_{2},0)}{(1-zM(z,y_{r}+y_{2}))^{2}}.$

Note that to avoid of multiple edges, the path between $g_{2}$ and red-green
vertex cannot be empty edge, in the case of added directed edge connects
$g_{2}$ to the red-green leaf.
As similar before, there are two possible cases for the general networks
arising from the Motzkin skeletons depicted on the middle of Figure 12. In the
first case, if we fix an added directed edge from $g_{2}$ to red-green leaf,
the only restriction for pointing of $g_{3}$ will be the vertices on the path
that connects it to the root and its first child vertex (to avoid multiple
edge). The red-green vertex may point to any non-path vertex. The second term
is regards the situation that a shortcut connects $g_{3}$ to the red-green
vertex. After subtracting Motzkin skeletons which are not respecting general
network condition, we obtain

$\displaystyle G_{B_{1}}^{r_{g}}(z)=$ $\displaystyle
Y_{r,3}\left(\frac{z^{4}M(z,y_{r}+y_{3})}{1-zM(z,y_{r}+y_{3})}P(z,y_{3},y_{r}+y_{3},0)P(z,y_{3},y_{r}+y_{3},y_{3})^{2}\right)$
$\displaystyle+$ $\displaystyle
Y_{r,2}\left(\frac{z^{4}\tilde{M}_{2}(z,y_{2}+y_{r})}{(1-zM(z,y_{r}+y_{2}))^{2}}P(z,y_{2},y_{r}+y_{2},y_{2})P(z,y_{r},y_{r}+y_{2},y_{r})\right)$
$\displaystyle-$ $\displaystyle
Y_{r,2}\left(\frac{z^{4}M(z,0)}{(1-zM(z,0))^{2}}P(z,y_{2},0,y_{2})P(z,y_{r},0,y_{r})\right).$

Another case such that one green vertex is a common ancestor of the other two
red-green vertices, is depicted in right of Figure 12. First, $g_{3}$ points
to the one of red-green leaf then another directed edge connects this leaf to
second red-green leaf in the Motzkin skeleton. The edge starting at latter
red-green leaf may point to any vertex except on the paths ones. This yields
the generating function

$\displaystyle G_{B_{2}}^{r_{g}}(z)=$ $\displaystyle
Y_{r}\left(\frac{z^{4}}{(1-zM(z,y_{r}))^{4}}\right).$

Figure 13. The structures of Motzkin skeletons that are correspondent with the
Motzkin skeleton $G_{C}(z)$ by replacing respectively $g_{1}$, $g_{3}$ or both
of them with red-green leaves.

Consider the Motzkin skeletons depicted in Figure 13. For the first one, the
generating function is given by

$\displaystyle G_{C_{1}}^{r_{g}}(z)$
$\displaystyle=Y_{r,3}\left(\frac{z^{4}\tilde{M}_{3}(z,y_{r}+y_{3})}{(1-zM(z,y_{r}+y_{3}))^{2}}P(z,y_{r},y_{r}+y_{3},y_{r})P(z,y_{3},y_{r}+y_{3},y_{3})\right.$
$\displaystyle-\left.\frac{z^{4}M(z,0)}{(1-zM(z,0))^{2}}P(z,y_{r},0,y_{r})P(z,y_{3},0,y_{3})\right)$
$\displaystyle+Y_{r,2}\left(\frac{z^{4}M(z,y_{2}+y_{r})}{(1-zM(z,y_{r}+y_{2}))}P(z,y_{2},y_{r}+y_{2},y_{2})P(z,y_{2},y_{r}+y_{2},0)\right).$

For the Motzkin skeletons on the middle of Figure 13, we obtain

$\displaystyle G_{C_{2}}^{r_{g}}(z)$
$\displaystyle=Y_{r,2}\left(\frac{z^{4}M(z,y_{r}+y_{2})}{(1-zM(z,y_{r}+y_{2}))^{2}}P(z,y_{2},y_{r}+y_{2},y_{2})P(z,y_{2},y_{r}+y_{2},0)\right)$
$\displaystyle+Y_{r,1}\left(\frac{z^{4}\tilde{M}_{1}(z,y_{1}+y_{r})}{1-zM(z,y_{r}+y_{1})}P(z,y_{1},y_{r}+y_{1},y_{1})P^{\star}(z,y_{1},y_{r}+y_{1},y_{1})P(z,y_{r},y_{r}+y_{1},y_{r})\right.$
$\displaystyle-\left.\frac{z^{4}M(z,0)}{1-zM(z,0)}P(z,y_{r},0,y_{r})P(z,y_{1},0,y_{1})P^{\star}(z,y_{1},0,y_{1})\right).$

For the right one, we will take two terms for exponential generating function
depending on which red-green leaf is pointed by $g_{2}$ first. After all, we
get from path analysis

$\displaystyle G_{C_{3}}^{r_{g}}(z)$
$\displaystyle=Y_{r}\left(\frac{z^{4}}{(1-zM(z,y_{r}))^{3}}P^{\star}(z,0,y_{r},0)+\frac{z^{4}}{(1-zM(z,y_{r}))^{4}}\right).$

Figure 14.  The Motzkin skeletons which arise from the $G_{D}(z)$ by
considering distribution of all possible red-green leaves.

The last case of general networks with at least one red-green vertex have
Motzkin skeletons as shown in Figure 14. The restriction for the target vertex
of the edges to be added at pointer set vertices follow the analogous rules in
order to meet the generality constraint. Setting up the generating function
follows the same pattern as before. We omit now the details and get from path
analysis after all

$\displaystyle G_{D_{1}}^{r_{g}}(z)$
$\displaystyle=Y_{r,3}\left(\frac{z^{5}\tilde{M}_{3}(z,y_{r}+y_{3})M(z,y_{r}+y_{3})}{1-zM(z,y_{r}+y_{3})}P(z,y_{r},y_{r}+y_{3},y_{r})P(z,y_{3},y_{r}+y_{3},y_{3})^{3}\right.$
$\displaystyle-\left.\frac{z^{5}M(z,0)^{2}}{(1-zM(z,0))}P(z,y_{r},0,y_{r})P(z,y_{3},0,y_{3})^{3}\right)$
$\displaystyle+Y_{r,2}\left(\frac{z^{5}\tilde{M}_{2}(z,y_{2}+y_{r})M(z,y_{2}+y_{r})}{(1-zM(z,y_{r}+y_{2}))^{2}}P(z,y_{2},y_{r}+y_{2},y_{2})^{2}P(z,y_{r},y_{r}+y_{2},y_{r})\right.$
$\displaystyle-\left.\frac{z^{5}M(z,0)^{2}}{(1-zM(z,0))^{2}}P(z,y_{2},0,y_{2})^{2}P(z,y_{r},0,y_{r})\right).$
$\displaystyle G_{D_{2}}^{r_{g}}(z)$
$\displaystyle=Y_{r,1}\left(\frac{z^{5}\tilde{M}_{1}(z,y_{r}+y_{1})M(z,y_{r}+y_{1})}{(1-zM(z,y_{r}+y_{1}))^{2}}P(z,y_{r},y_{r}+y_{1},y_{r})P(z,y_{1},y_{r}+y_{1},y_{1})^{2}\right.$
$\displaystyle-\left.\frac{z^{5}M(z,0)^{2}}{(1-zM(z,0))^{2}}P(z,y_{r},0,y_{r})P(z,y_{1},0,y_{1})^{2}\right).$
$\displaystyle G_{D_{3}}^{r_{g}}(z)$
$\displaystyle=Y_{r}\left(\frac{z^{5}M(z,y_{r})}{(1-zM(z,y_{r}))^{5}}\right).$
$\displaystyle G_{D_{4}}^{r_{g}}(z)$
$\displaystyle=Y_{r}\left(\frac{z^{5}M(z,y_{r})}{(1-zM(z,y_{r}))^{5}}+\frac{z^{5}M(z,y_{r})}{(1-zM(z,y_{r}))^{5}}\right).$

In the end, we consider the Motzkin skeletons with the contribution double-
green vertices as depicted in Figure 15. Note that, The extra factor
$\frac{1}{2}$ appears in the expression of $G_{E}^{2}(z)$ and $G_{E}^{3}(z)$,
because the order of pointing for double-green vertex is not matter. After
normalization we obtain

Figure 15. Possible structures of Motzkin skeletons with three reticulation
vertices and contribution of double-green vertices.

$\displaystyle G_{E}^{1}(z)$
$\displaystyle=Y_{g,r}\frac{z^{3}P(z,y_{g},y_{r}+y_{g},y_{g})}{(1-zM(z,y_{g}+y_{r}))^{2}}.$
$\displaystyle G_{E}^{2}(z)$
$\displaystyle=\frac{1}{2}(Y_{g})^{2}Y_{1}\frac{z^{3}\tilde{M}_{1}(z,y_{1}+y_{g})}{1-zM(z,y_{1}+y_{g})}P(z,y_{g},y_{1}+y_{g},y_{g})P(z,y_{1},y_{g}+y_{r},y_{1})$
$\displaystyle-\frac{1}{2}(Y_{g})^{2}Y_{1}\dfrac{z^{3}M(z,0)}{1-zM(z,0)}P(z,y_{1},0,y_{1})P(z,y_{g},0,y_{g})$
$\displaystyle-Y_{g}\dfrac{z^{5}M(z,y_{g})}{(1-zM(z,y_{g}))^{5}}.$
$\displaystyle G_{E}^{3}(z)$
$\displaystyle=\frac{1}{2}(Y_{g})^{2}Y_{1}\frac{z^{2}P(z,y_{1},y_{1}+y_{g},0)}{1-zM(z,y_{1}+y_{g})}.$

Now, we sum up all obtained generating functions so far. For normalization,
the result must be divided by $8$, Since the procedure will generate each
general network eight times. Overall, by collecting everything, the
exponential generating function for vertex-labelled general phylogenetic
networks with three reticulation nodes is

${G}_{3}^{\nshortparallel}(z)=z\cdot\frac{a_{3}^{\nshortparallel}(z^{2})-b_{3}^{\nshortparallel}(z^{2})\sqrt{1-2z^{2}}}{(1-2z^{2})^{11/2}},$

where

$a^{\nshortparallel}_{3}(z)=3z^{6}+2z^{5}+4z^{4}+2z^{3}+\frac{69}{4}z^{2},$

and,

$b^{\nshortparallel}_{3}(z)=z^{5}+\frac{9}{2}z^{4}+11z^{3}+\frac{69}{4}z^{2}.\;\;\;\;\;$

Also, consequently as similar as before we can take the explicit formulas for
vertex and leaf-labeled general networks with $3$ reticulation vertices. To
see them set $n=2m+1$, so we have

$[z^{n}]{G}_{3}^{\nshortparallel}(z)=[z^{m}]\bar{G}_{3}^{\nshortparallel}(z),$

such that,

$[z^{m}]\bar{G}_{3}^{\nshortparallel}(z)=[z^{m}]\dfrac{a^{\nshortparallel}_{3}(z)}{(1-2z)^{\frac{11}{2}}}-[z^{m}]\dfrac{b^{\nshortparallel}_{3}(z)}{(1-2z)^{5}}.$

It gives

$\mathcal{F^{\nshortparallel}}(m):=[z^{m}]\bar{G^{\nshortparallel}}_{3}(z)=\frac{2^{m-6}}{3}\Big{(}A^{\nshortparallel}_{3}(m)\frac{\displaystyle
m(m-1)\binom{2m}{m}}{35(2m-1)4^{m-2}}-B^{\nshortparallel}_{3}(m)\Big{)}.$

where

$\displaystyle A^{\nshortparallel}_{3}(m)$
$\displaystyle=104m^{4}+416m^{3}+596m^{2}-384m+61,$ $\displaystyle\quad
B^{\nshortparallel}_{3}(m)$ $\displaystyle=48m^{4}+31m^{3}-12m^{2}-73m+6.$

By replacing $m=(n-1)/2$ we have,
$G_{3,n}^{\nshortparallel}=n!\cdot\mathcal{F^{\nshortparallel}}((n-1)/2).$
With some more steps but similar as before we can present explicit formula for
the number of leaf-labeled general network with three reticulation vertices.
Let ${\dot{G}^{\nshortparallel}}_{3}(z)$ denotes corresponding generating
function for general networks that holds the situation of equation (6) and
${\ddot{G}^{\nshortparallel}}_{3}(z)$ be generating function for general
networks which arise from the Motzkin skeletons figure 16. We have
${G}_{3}^{\nshortparallel}(z)={\dot{G}^{\nshortparallel}}_{3}(z)+{\ddot{G}^{\nshortparallel}}_{3}(z)$.
So for the first subfamily (for $m>3$) we get

$\displaystyle\mathcal{\dot{F}^{\nshortparallel}}(m)=\frac{2^{m-5}}{3}\Big{(}\dot{A}^{\nshortparallel}_{3}(m)\frac{\displaystyle
m(m-1)\binom{2m}{m}}{35(2n-5)(2n-3)(2m-1)4^{m-2}}-\dot{B}^{\nshortparallel}_{3}(m)\Big{)},$
(28)

where,

$\displaystyle\dot{A}^{\nshortparallel}_{3}(m)=280m^{6}-288m^{5}-1086m^{4}-2626m^{3}+9239m^{2}-7463m+4290,\quad$

and

$\displaystyle\quad\dot{B}^{\nshortparallel}_{3}(m)=24m^{4}-\frac{31}{2}m^{3}+6m^{2}+\frac{85}{2}m-21.$

Also for $m=3$ ($\ell=1$), we have $\mathcal{\dot{F}^{\nshortparallel}}(3)=8$.

Figure 16. The family of general networks with generating function
${\ddot{G}^{\nshortparallel}}_{3}(z)$ such that each fixed leaf-labeled
general network of (a) can construct corresponding vertex-labeled general
network four times. For general network arose from second row shapes it will
be exactly two times. Note that, for $b_{1}$, $b_{2}$ and $b_{3}$ first we
complete the structure by adding one more directed edge from green vertex to
unary red vertex.

Now we consider the family of general networks with $3$ reticulation vertices
such that there is a pair of vertices that have the set of same descendent and
applying the procedure (4.0.2) needs to cope with symmetry for them ; see
Figure 16. First, we set up generating function, let’s show it
$G_{s_{1}}^{\nshortparallel}(z)$, for case (a) as shown at the top of Figure
16. Each fixed leaf-labeled general network which is arisen from this
structure can generate corresponding vertex-labeled networks four times. So
for this case we normalize equation $6$ by considering
${G^{\nshortparallel}}_{s_{1},\ell}=4\frac{\ell!}{n!}G_{s_{1},n}^{\nshortparallel}.$
Let’s $G_{s_{2}}^{\nshortparallel}(z)$ denotes the corresponding generating
function for second row structures of Figure 16. Note that each fixed leaf-
labeled network belongs to these family can construct vertex-labeled network
two times, so we get
${G^{\nshortparallel}}_{s_{2},\ell}=2\frac{\ell!}{n!}G_{s_{2},n}^{\nshortparallel}.$
Overall, we obtain the
${\ddot{G}^{\nshortparallel}}_{3}(z)=G_{s_{1}}^{\nshortparallel}(z)+G_{s_{2}}^{\nshortparallel}(z)$,
where

$\displaystyle G_{s_{1}}^{\nshortparallel}(z)$
$\displaystyle=\frac{1}{4}\frac{z^{6}M(z,0)}{1-zM(z,0)},$

and then we get

$\displaystyle\mathcal{\ddot{F}^{\nshortparallel}}_{s_{1}}(m):=[z^{m}]{\bar{G}^{\nshortparallel}}_{s_{1}}(z)=2^{m-2}\Big{(}\frac{\displaystyle
m(m-1)\binom{2m}{m}}{(2n-3)(2m-1)4^{m}}\Big{)}.$ (29)

Also we have

$\displaystyle G_{s_{2}}^{\nshortparallel}(z)$
$\displaystyle=\frac{1}{2}\partial
y\frac{z^{7}\tilde{M}(z,y)M(z,y)^{2}}{4(1-zM(z,y))^{2}}P(z,y,y,y)$
$\displaystyle+\frac{1}{2}\partial
y\frac{z^{6}M(z,y)^{2}}{4(1-zM(z,y))}P(z,y,y,0)$
$\displaystyle+\frac{1}{2}\partial
y\frac{z^{6}\tilde{M}(z,y)M(z,y)}{2(1-zM(z,y))^{2}}$
$\displaystyle+\frac{1}{4}\frac{z^{8}M(z,0)^{3}}{1-zM(z,0)}.$

such that for or $m>3$ ( $\ell>1$) we have

$\displaystyle\mathcal{\ddot{F}^{\nshortparallel}}_{s_{2}}(m):=[z^{m}]{\bar{G}^{\nshortparallel}}_{s_{2}}(z)=2^{m-3}\Big{(}(2m^{3}-15m^{2}+38m-34)\frac{\displaystyle
m(m-1)\binom{2m}{m}}{(2m-5)(2n-3)(2m-1)4^{m-1}}-\frac{1}{2}(m-3)\Big{)},$ (30)

and $\mathcal{\ddot{F}^{\nshortparallel}}_{s_{2}}(3)=0$. Obviously, this means
there is no any general network with one leaf which can be generated by second
row structures of Figure 16. Overall, by collecting everything, we have
$G_{3,1}^{\nshortparallel}=51$ and for $\ell>1$ we use

$\displaystyle\begin{aligned}
G_{3,\ell}^{\nshortparallel}&=\ell!\cdot\Big{(}\mathcal{\dot{F}^{\nshortparallel}}(\ell+2)+4\ddot{F}^{\nshortparallel}_{s_{1}}(\ell+2)+2\ddot{F}^{\nshortparallel}_{s_{2}}(\ell+2)\Big{)}\\\
&=\ell!\;\Big{(}r_{3}(\ell)\displaystyle
2^{-\ell}\binom{2\ell+4}{\ell+2}-2^{\ell}p_{3}(\ell)\Big{)},\end{aligned}$
(31)

where after manipulation we get $r_{3}(\ell)$ and $p_{3}(\ell)$ as show in
table (1) for the number of leaf-labeled general networks with three
reticulation vertices and no multiple edges. In the following, we want to set
up exponential generating functions for general networks with three
reticulation vertices and at least one multiple edges. It can be done by a
case by case analysis of each sparsened skeletons which are depicted in
Figures 17 to the 22. Note that, each factor of expression represents the
number of generated times, so we use them to normalize final results.

Figure 17. The structures of the Motzkin skeletons of general phylogenetic
networks with at least one multiple edges which are arised from $G_{A}(z)$.

$\displaystyle G_{A}^{1}(z)$
$\displaystyle=\frac{1}{4}Y_{2,3}\frac{z^{4}M(z,y_{2}+y_{3})}{1-zM(z,y_{2}+y_{3})}P(z,y_{2}+y_{3},y_{2}+y_{3},y_{3})P(z,y_{3},y_{2}+y_{3},0).$
$\displaystyle G_{A}^{2}(z)$
$\displaystyle=\frac{1}{4}Y_{1,3}\frac{z^{4}\tilde{M}_{1}(z,y_{1}+y_{3})}{1-zM(z,y_{1}+y_{3})}P(z,y_{3},y_{1}+y_{3},y_{3})P(z,y_{3},y_{1}+y_{3},0).$
$\displaystyle G_{A}^{3}(z)$
$\displaystyle=\frac{1}{4}Y_{1,2}\frac{z^{4}\tilde{M}_{1}(z,y_{1}+y_{2})}{(1-zM(z,y_{1}+y_{2}))^{2}}P(z,y_{2},y_{1}+y_{2},0).$
$\displaystyle G_{A}^{4}(z)$
$\displaystyle=\frac{1}{2}Y_{3}\frac{z^{5}M(z,y_{3})}{1-zM(z,y_{3})}P(z,y_{3},y_{3},y_{3})P(z,y_{3},y_{3},0).$
$\displaystyle G_{A}^{5}(z)$
$\displaystyle=\frac{1}{2}Y_{2}\frac{z^{5}M(z,y_{2})}{(1-zM(z,y_{2}))^{2}}P(z,y_{2},y_{2},0).$
$\displaystyle G_{A}^{6}(z)$
$\displaystyle=\frac{1}{2}Y_{1}\frac{z^{5}\tilde{M}(z,y_{1})}{(1-zM(z,y_{1}))^{3}}.$
$\displaystyle G_{A}^{7}(z)$
$\displaystyle=\frac{z^{6}M(z,0)}{(1-zM(z,0))^{3}}.$ $\displaystyle
G_{A}^{8}(z)$
$\displaystyle=\frac{1}{4}Y_{r}\frac{z^{4}P^{\star}(z,0,y_{r},0)}{(1-zM(z,y_{r}))^{2}}.$
$\displaystyle G_{A}^{9}(z)$
$\displaystyle=\frac{1}{4}Y_{r}\frac{z^{4}}{(1-zM(z,y_{r}))^{3}}.$
$\displaystyle G_{A}^{10}(z)$
$\displaystyle=\frac{1}{4}Y_{r,3}\frac{z^{3}P(z,y_{3},y_{r}+y_{3},0)}{1-zM(z,y_{3}+y_{r})}.$
$\displaystyle G_{A}^{11}(z)$
$\displaystyle=\frac{1}{2}Y_{r}\frac{z^{4}}{(1-zM(z,y_{r}))^{2}}.$

Figure 18.  The structures of the Motzkin skeletons of general phylogenetic
networks with at least one multiple edges which are arised from $G_{B}(z)$.

$\displaystyle G_{B}^{1}(z)=$
$\displaystyle\frac{1}{8}Y_{1,2}\Bigg{(}\frac{z^{5}\tilde{M}_{1}(z,y_{1}+y_{2})\tilde{M}_{2}(z,y_{1}+y_{2})}{(1-zM(z,y_{1}+y_{2}))^{2}}P(z,y_{1},y_{1}+y_{2},y_{1})P(z,y_{2},y_{1}+y_{2},y_{2})$
$\displaystyle-$
$\displaystyle\frac{z^{5}M(z,0)^{2}}{(1-zM(z,0))^{2}}P(z,y_{1},0,y_{1})P(z,y_{2},0,y_{2})\Bigg{)}.$
$\displaystyle G_{B}^{2}(z)=$
$\displaystyle\frac{1}{4}Y_{2,3}\Bigg{(}\frac{z^{5}M(z,y_{2}+y_{3})\tilde{M}_{2}(z,y_{2}+y_{3})}{1-zM(z,y_{2}+y_{3})}P(z,y_{2}+y_{3},y_{2}+y_{3},y_{2}+y_{3})$
$\displaystyle\times$ $\displaystyle
P(z,y_{3},y_{2}+y_{3},0)P(z,y_{3},y_{2}+y_{3},y_{3})\Bigg{)}.$ $\displaystyle
G_{B}^{3}(z)=$
$\displaystyle\frac{1}{4}Y_{3}\frac{z^{6}M(z,y_{3})^{2}}{1-zM(z,y_{3})}P(z,y_{3},y_{3},y_{3})^{2}P(z,y_{3},y_{3},0).$
$\displaystyle G_{B}^{4}(z)=$
$\displaystyle\frac{1}{2}Y_{2}\frac{z^{6}\tilde{M}_{2}(z,y_{2})M(z,y_{2})}{(1-zM(z,y_{2}))^{3}}P(z,y_{2},y_{2},y_{2}).$
$\displaystyle G_{B}^{5}(z)=$
$\displaystyle\frac{1}{2}\frac{z^{7}M(z,0)^{2}}{(1-zM(z,0))^{4}}.$
$\displaystyle G_{B}^{6}(z)=$
$\displaystyle\frac{1}{4}Y_{r}\frac{z^{5}M(z,y_{r})}{(1-zM(z,y_{r}))^{3}}P(z,y_{r},y_{r},y_{r}).$
$\displaystyle G_{B}^{7}(z)=$
$\displaystyle\frac{1}{4}Y_{r}\frac{z^{5}M(z,y_{r})}{(1-zM(z,y_{r}))^{4}}.$

Figure 19.  The structures of the Motzkin skeletons of general phylogenetic
networks with at least one multiple edges which are arised from $G_{C}(z)$.

$\displaystyle G_{C}^{1}(z)$
$\displaystyle=\frac{1}{4}Y_{2,3}\frac{z^{5}M(z,y_{2}+y_{3})\tilde{M}_{3}(z,y_{2}+y_{3})}{(1-zM(z,y_{2}+y_{3}))^{2}}P(z,y_{2}+y_{3},y_{2}+y_{3},y_{2}+y_{3})P(z,y_{2},y_{2}+y_{3},0).$
$\displaystyle G_{C}^{2}(z)$
$\displaystyle=\frac{1}{4}Y_{1,3}\left(\frac{z^{5}\tilde{M}_{1}(z,y_{3}+y_{1})\tilde{M}_{3}(z,y_{3}+y_{1})}{1-zM(z,y_{3}+y_{1})}P(z,y_{1},y_{3}+y_{1},y_{1})^{2}P(z,y_{3},y_{3}+y_{1},y_{3})\right.$
$\displaystyle-\left.\frac{z^{5}M(z,0)^{2}}{1-zM(z,0)}P(z,y_{1},0,y_{1})^{2}P(z,y_{3},0,y_{3})\right).$
$\displaystyle G_{C}^{3}(z)$
$\displaystyle=\frac{1}{4}Y_{1,2}\left(\frac{z^{5}\tilde{M}_{1}(z,y_{2}+y_{1})M(z,y_{2}+y_{1})}{1-zM(z,y_{2}+y_{1})}P(z,y_{1},y_{2}+y_{1},y_{1})\right.$
$\displaystyle\left.\times
P(z,y_{1}+y_{2},y_{1}+y_{2},y_{1})P(z,y_{2},y_{2}+y_{1},y_{2})\right.$
$\displaystyle-\left.\frac{z^{5}M(z,0)^{2}}{(1-zM(z,0))^{2}}P(z,y_{1},0,y_{1})P(z,y_{2},0,y_{2})\right).$
$\displaystyle G_{C}^{4}(z)$
$\displaystyle=\frac{1}{2}Y_{3}\frac{z^{6}\tilde{M}_{3}(z,y_{3})M(z,y_{3})}{(1-zM(z,y_{3}))^{3}}P(z,y_{3},y_{3},y_{3}).$
$\displaystyle G_{C}^{5}(z)$
$\displaystyle=\frac{1}{2}Y_{2}\frac{z^{6}M(z,y_{2})^{2}}{(1-zM(z,y_{2}))^{2}}P(z,y_{2},y_{2},y_{2})P(z,y_{2},y_{2},0).$
$\displaystyle G_{C}^{6}(z)$
$\displaystyle=\frac{1}{2}Y_{1}\frac{z^{6}\tilde{M}_{1}(z,y_{1})M(z,y_{1})}{(1-zM(z,y_{1}))^{2}}P(z,y_{1},y_{1},y_{1})^{2}.$
$\displaystyle G_{C}^{7}(z)$
$\displaystyle=\frac{z^{7}M(z,0)^{2}}{(1-zM(z,0))^{4}}.$

Figure 20.  The structures of the Motzkin skeletons of general phylogenetic
networks with at least one multiple edges which are arised from $G_{C}(z)$.

$\displaystyle G_{C}^{9}(z)$
$\displaystyle=\frac{1}{4}Y_{r}\frac{z^{5}M(z,y_{r})}{(1-zM(z,y_{r}))^{3}}P(z,y_{r},y_{r},y_{r}).$
$\displaystyle G_{C}^{10}(z)$
$\displaystyle=\frac{1}{4}Y_{r}\frac{z^{5}M(z,y_{r})}{(1-zM(z,y_{r}))^{4}}.$
$\displaystyle G_{C}^{11}(z)$
$\displaystyle=\frac{1}{4}Y_{r}\frac{z^{5}M(z,y_{r})}{(1-zM(z,y_{r}))^{2}}P(z,y_{r},y_{r},y_{r})P^{\star}(z,0,y_{r},0).$
$\displaystyle G_{C}^{12}(z)$
$\displaystyle=\frac{1}{4}Y_{r}\frac{z^{5}M(z,y_{r})}{(1-zM(z,y_{r}))^{4}}.$
$\displaystyle G_{C}^{13}(z)$
$\displaystyle=\frac{1}{4}Y_{r,1}\left(\frac{z^{4}\tilde{M}_{1}(z,y_{1}+y_{r})}{1-zM(z,y_{1}+y_{r})}P(z,y_{1},y_{1}+y_{r},y_{1})P(z,y_{r},y_{1}+y_{r},y_{r})\right.$
$\displaystyle-\left.\dfrac{M(z,0)}{1-zM(z,0)}P(z,y_{1},0,y_{1})P(z,y_{r},0,y_{r})\right).$
$\displaystyle G_{C}^{14}(z)$
$\displaystyle=\frac{1}{2}Y_{r}\left(\frac{z^{5}M(z,y_{r})}{(1-zM(z,y_{r}))^{2}}P(z,y_{r},y_{r},y_{r})\right).$
$\displaystyle G_{C}^{15}(z)$
$\displaystyle=\frac{1}{4}Y_{r}\frac{z^{4}}{(1-zM(z,y_{r}))^{3}}.$

Figure 21.  The structures of the Motzkin skeletons of general phylogenetic
networks with at least one multiple edges which are arised from $G_{D}(z)$.

$\displaystyle G_{D}^{1}(z)$
$\displaystyle=\frac{1}{4}Y_{2,3}\left(\frac{z^{6}M(z,y_{2}+y_{3})\tilde{M}_{2}(z,y_{2}+y_{3})\tilde{M}_{3}(z,y_{2}+y_{3})}{1-zM(z,y_{2}+y_{3})}P(z,y_{2}+y_{3},y_{2}+y_{3},y_{2}+y_{3})\right.$
$\displaystyle\times
P(z,y_{2},y_{2}+y_{3},y_{2})P(z,y_{3},y_{2}+y_{3},y_{3})^{2}-\frac{z^{6}M(z,0)^{3}}{(1-zM(z,0))^{2}}P(z,y_{2},0,y_{2})P(z,y_{3},0,y_{3})^{2}\Bigg{)}.$
$\displaystyle G_{D}^{2}(z)$
$\displaystyle=\frac{1}{8}Y_{1,2}\left(\frac{z^{6}M(z,y_{1}+y_{2})\tilde{M}_{1}(z,y_{1}+y_{2})\tilde{M}_{2}(z,y_{1}+y_{2})}{(1-zM(z,y_{1}+y_{2}))^{2}}P(z,y_{1}+y_{2},y_{1}+y_{2},y_{1}+y_{2})\right.$
$\displaystyle\times
P(z,y_{1},y_{1}+y_{2},y_{1})P(z,y_{2},y_{1}+y_{2},y_{2})-\frac{z^{6}M(z,0)^{3}}{(1-zM(z,0))^{3}}P(z,y_{1},0,y_{1})P(z,y_{2},0,y_{2})\Bigg{)}.$
$\displaystyle G_{D}^{3}(z)$
$\displaystyle=\frac{1}{4}Y_{3}\frac{z^{7}M(z,y_{3})^{2}\tilde{M}_{3}(z,y_{3})}{(1-zM(z,y_{3}))^{2}}P(z,y_{3},y_{3},y_{3})^{3}.$
$\displaystyle G_{D}^{4}(z)$
$\displaystyle=\frac{1}{2}Y_{2}\frac{z^{7}M(z,y_{2})^{2}\tilde{M}_{2}(z,y_{2})}{(1-zM(z,y_{2}))^{3}}P(z,y_{2},y_{2},y_{2})^{2}.$
$\displaystyle G_{D}^{5}(z)$
$\displaystyle=\frac{1}{2}\frac{z^{8}M(z,0)^{3}}{(1-zM(z,0))^{5}}.$
$\displaystyle G_{D}^{6}(z)$
$\displaystyle=\frac{1}{4}\left(Y_{r}\frac{z^{6}M(z,y_{r})^{2}}{(1-zM(z,y_{r}))^{4}}P(z,y_{r},y_{r},y_{r})\right).$
$\displaystyle G_{D}^{7}(z)$
$\displaystyle=\frac{1}{4}\left(Y_{r}\frac{z^{6}M(z,y_{r})^{2}}{(1-zM(z,y_{r}))^{4}}P(z,y_{r},y_{r},y_{r})\right).$
$\displaystyle G_{D}^{8}(z)$
$\displaystyle=\frac{1}{4}Y_{r}\left(\frac{z^{6}M(z,y_{r})^{2}}{(1-zM(z,y_{r}))^{4}}P(z,y_{r},y_{r},y_{r})\right).$

Figure 22.  The structures of the Motzkin skeletons of general phylogenetic
networks with at least one multiple edges which are arised from $G_{E}^{2}(z)$
and $G_{E}^{3}(z)$.

$\displaystyle G_{E}^{\prime}(z)$
$\displaystyle=\frac{1}{8}(Y_{g})^{2}\frac{z^{4}M(z,y_{g})}{(1-zM(z,y_{g}))^{2}}P(z,y_{g},y_{g},y_{g}).$
$\displaystyle G_{E}^{{}^{\prime\prime}}(z)$
$\displaystyle=\frac{1}{8}(Y_{g})^{2}\frac{z^{3}}{(1-zM(z,y_{g}))^{2}}.$

Figure 23. General networks with multiple edges and corresponding generating
function ${\ddot{G}^{\shortparallel}}_{3}(z)$ such that any fixed leaf-labeled
of them can generate all-vertex labeled exactly twice.

Overall, by collecting everything, we obtain the following result.

${G}_{3}^{\shortparallel}(z)=z\cdot\frac{a_{3}^{\shortparallel}(z^{2})-b_{3}^{\shortparallel}(z^{2})\sqrt{1-2z^{2}}}{(1-2z^{2})^{11/2}},$

where

$a^{\shortparallel}_{3}(z)=z^{5}-z^{4}+\frac{13}{2}z^{3}+10z^{2}\quad\text{and},\quad
b^{\shortparallel}_{3}(z)=4z^{3}+10z^{2}.\;\;\;\;\;$

After some computation, it gives

$\displaystyle\mathcal{F^{\shortparallel}}(m):=[z^{m}]\bar{G^{\shortparallel}}_{3}(z)=2^{m-1}\Big{(}A^{\shortparallel}_{3}(m)\frac{\displaystyle
m(m-1)\binom{2m}{m}}{3(2m-1)4^{m}}-B^{\shortparallel}_{3}(m)\Big{)}.$ (32)

where

$A^{\shortparallel}_{3}(m)=6m^{3}+4m^{2}-m-2\quad\text{and,}\quad
B^{\shortparallel}_{3}(m)=m^{3}-\frac{1}{2}m^{2}-\frac{1}{2}.$

By replacing $m=(n-1)/2$ we have,
$G_{3,n}^{\shortparallel}=n!\cdot\mathcal{F^{\shortparallel}}((n-1)/2)$ for
the number of vertex-labeled general phylogenetics with $3$ reticulation
vertices and at least one multiple edge in their structures.

Now we set up generating function for leaf-labeled. we Consider
${G^{\shortparallel}}_{3}(z)={\dot{G}^{\shortparallel}}_{3}(z)+{\ddot{G}^{\shortparallel}}_{3}(z)$
which respectively right side of equation denote generating functions for two
subfamilies of this class (general networks with multiple edges) that we can
use the equation directly or not (needs to cope with symmetry); see Figure 23.
For the first subfamily we get

$\mathcal{\dot{F}^{\shortparallel}}(m):=[z^{m}]\dot{\bar{G}}^{\nshortparallel}_{3}(z)=2^{m-2}\Big{(}\dot{A}^{\nshortparallel}_{3}(m)\frac{\displaystyle
m(m-1)\binom{2m}{m}}{3(2n-3)(2m-1)4^{m-1}}-\dot{B}^{\nshortparallel}_{3}(m)\Big{)}.$

where,

$\displaystyle\dot{A}^{\shortparallel}_{3}(m)=6m^{4}-5m^{3}-7m^{2}-2m+6\quad\text{and,}\quad\dot{B}^{\shortparallel}_{3}(m)=2m^{3}-m^{2}-m.$
(33)

Also the generating function corresponding to the general networks in Figure
23 is

$\displaystyle\ddot{G}^{\shortparallel}_{3}(z)$
$\displaystyle=\frac{1}{2}\frac{z^{6}M(z,0)}{1-zM(z,0)}+\frac{1}{4}\frac{z^{8}M(z,0)^{3}}{(1-zM(z,0))^{3}}+\frac{1}{4}\frac{z^{7}M(z,0)^{2}}{(1-zM(z,0))^{2}}+\frac{1}{2}\frac{z^{7}M(z,0)^{2}}{(1-zM(z,0))^{2}}$
$\displaystyle=\frac{1}{2}\frac{z^{3}}{(1-2z^{2})^{\frac{3}{2}}},$

such that

$\displaystyle\mathcal{\ddot{F}^{\shortparallel}}(m):=[z^{m}]\ddot{\bar{G}}^{\nshortparallel}_{3}(z)=2^{m-1}m(m-1)(m-2)\displaystyle\Big{(}\frac{\displaystyle\binom{2m}{m}}{(2n-3)(2m-1)4^{m}}\Big{)}.$
(34)

Note that, every member of leaf-labeled general networks arising from Figure
23 construct corresponding vertex-labeled networks twice. Overall, by
replacing $m=\ell+2$ we have

$\displaystyle\begin{aligned}
G_{3,\ell}^{\shortparallel}&=\displaystyle\ell!\cdot\Big{(}\mathcal{\dot{F}^{\shortparallel}}(\ell+2)+2\mathcal{\ddot{F}^{\shortparallel}}(\ell+2)\Big{)}\\\
&=\ell!\cdot
2^{\ell}\cdot\displaystyle\Big{(}\dfrac{(\ell+1)(\ell+2)^{2}(6\ell^{3}+31\ell^{2}+45\ell+15)\displaystyle\binom{2\ell+4}{\ell+2}}{3(2\ell+1)(2\ell+3)4^{\ell+1}}-(2\ell^{3}+11\ell^{2}+19\ell+10)\Big{)},\end{aligned}$
(35)

for the number of leaf-labeled general networks with three reticulation
vertices and at least one multiple edge. Finally, we have
$\tilde{G}_{3,\ell}=G_{3,\ell}^{\nshortparallel}+G_{3,\ell}^{\shortparallel}$,
for the number of all general phylogenetic networks with three reticulation
vertices.