Olivier Bodini

Antoine Genitrini
email: antoine.genitrini@lip6.fr

AND Écile Mailler
email: c.mailler@bath.ac.uk

Mehdi Naima

STRICT MONOTONIC TREES ARISING FROM EVOLUTIONARY PROCESSES: COMBINATORIAL AND PROBABILISTIC STUDY

Keywords: Evolution process, Increasing trees, Monotonic trees, Analytic Combinatorics, Uniform sampling

In this paper we study two models of labelled random trees that generalise the original unlabelled Schröder tree. Our new models can be seen as models for phylogenetic trees in which nodes represent species and labels encode the order of appearance of these species, and thus the chronology of evolution. One important feature of our trees is that they can be generated efficiently thanks to a dynamical, recursive construction. Our first model is an increasing tree in the classical sense (labels increase along each branch of the tree and each label appears only once). To better model phylogenetic trees, we relax the rules of labelling by allowing repetitions in the second model.

For each of the two models, we provide asymptotic theorems for different characteristics of the tree (e.g. degree of the root, degree distribution, height, etc), thus giving extensive information about the typical shapes of these trees. We also provide efficient algorithms to generate large trees efficiently in the two models. The proofs are based on a combination of analytic combinatorics, probabilistic methods, and bijective methods (we exhibit bijections between our models and well-known models of the literature such as permutations and Stirling numbers of both kinds).

It turns out that even though our models are labelled, they can be specified simply in the world of ordinary generating functions. However, the resulting generating functions will be formal. Then, by applying Borel transforms the models will be amenable to techniques of analytic combinatorics.

Introduction

The aim of this paper is to study combinatorial models for phylogenetic trees: the main idea is to add node labels in order to encode chronology in the classical model introduced by Schröder trees in 1870 in the seminal paper Vier Combinatorische Probleme [START_REF] Schröder | Vier Combinatorische Probleme[END_REF]. In this paper (see the fourth problem), Schröder introduces a simple model of phylogenetic tree model, and enumerates this class of trees by their number of leaves.

In biology, a phylogenetic tree is a classical tool to represent the evolutionary relationship among species. At each branching node of the tree, the descendant species from distinct branches have distinguished themselves in some manner and are no more dependent: the past is shared but the futures are independent.

The main limitation of Schröder's model of phylogenetic trees is that it does not take into account the chronology between the different branching nodes. Since then, probabilistic approaches have been developed to consider this chronology: in particular in the context of binary trees, one can mention, e.g., the stochastic model of Yule [START_REF] Yule | A mathematical theory of evolution, based on the conclusions of Dr[END_REF] and its generalization by Aldous [START_REF] Aldous | Probability distributions on cladograms[END_REF].

However, to the best of our knowledge, there seems to have been no attempt to combinatorially enrich Schröder's original model in order to encode the chronology of evolution (except the short version [START_REF] Bodini | Ranked schröder trees[END_REF] of this paper). Motivated by the fact that models with restricted arities appear in the biology literature under the name of "ranked phylogenetic trees" (see, e.g., [SDH + 04]), we aim at relaxing these restrictions and study models with unrestricted arities. To do so, we consider labelled versions of Schröder's tree, where the labels represent the order at which branchings occur. In Figure 1 we have represented on the left hand-side a classical Schröder trees of size 50 (i.e. with 50 leaves), and, on the right hand-side, a labelled version of the same tree: time is on the vertical axis, from top to bottom, and a node of label x is placed at time x (the horizontal placement is irrelevant).

The two models of trees we study are enumerated by their number of leaves since leaves represent the number of current species. In this paper we do not distinguish between the leaves and therefore they are unlabelled. The justification for this is that we consider species to have the same evolutionary power and are thus undistinguishable. Additionally, the trees are ordered which is not the case in usual phylogenetic tree models. However, this gives a first approach to the study of such trees since the equivalent non-plane models (i.e. where the order of siblings is irrelevant) of these trees require more involved technical tools. We aim in the near future to extend this study to such non-plane models.

Discussion of related models: Increasing trees are classical in the literature: for example, Bergeron, Flajolet and Salvy [START_REF] Bergeron | Varieties of increasing trees[END_REF] study several families of increasinglylabelled trees, and, to do so, they develop some tools that are now classical in analytic combinatorics. As an example, one of these classical tools is the integration of the Greene operators. We refer the reader to [START_REF] Drmota | Random trees[END_REF] where more recent results on various families of increasing trees and the analytic combinatorics methods to quantitatively study them are surveyed.

Beyond their combinatorial description, increasing trees can often be described as the result of a dynamic construction: the nodes are added one by one at successive integer-times in the tree (their labels being the time at which they are added). This description sometimes allows to apply probabilistic method to prove theorems Figure 1. A Schröder tree: without chronological evolution (on the left-hand side), and with chronological evolution (on the righthand side): the label of a node is represented as the distance from this node to the root. about some characteristics such as the height of the tree, and it also often gives a very efficient way to generate large trees from the considered class using simple, iterative and local rules.

We illustrate this dynamical evolution on the simple case of recursive trees. This simple model was originally designed as a simple model for the spread of epidemics [START_REF] Moon | The distance between nodes in recursive trees[END_REF]. Combinatorially, a recursive tree is a rooted non-plane (i.e. the order of siblings is irrelevant) tree whose nodes are labelled from 1 to the number of nodes in such a way that each label appears exactly once, and the labels increase along all branches. We denote by R n the class of all n-node recursive trees. Now, consider a sequence of random trees (t n ) n≥1 built recursively as follows: t 0 has only one node, labelled by 1. Given t n-1 , attach a new child labelled by n to a node picked uniformly at random among the n -1 nodes of t n-1 . Then, it is known that for all n ≥ 1, t n is a tree taken uniformly at random in R n , the set of all n-node recursive trees. Both analytic combinatorics and probabilistic methods, as well as a bijection with permutations, have been used to understand the average typical shape of a large recursive tree: it is known that the degree of the root grows on average as ln n (see [START_REF] Drmota | Random trees[END_REF]Sec. 6.1]), the height as c ln n (for an explicit constant c -see [START_REF] Pittel | Note on the heights of random recursive trees and random m-ary search trees[END_REF]), the proportion of nodes of arity k ≥ 0 converges to 2 -k (see [START_REF] Drmota | Random trees[END_REF]Th. 6.8]). Although our two models of increasing Schröder trees are more involved, our proofs rely on the same three methods used in the recursive tree literature: analytic combinatorics, a dynamical evolution, probabilistic methods, and bijections with classes of permutations.

Our main contributions: Although, as mentioned above, many variations of the recursive tree have been studied, this paper (together with its short version [START_REF] Bodini | Ranked schröder trees[END_REF]) contains the first study of increasing versions of the classical model of Schröder.

Since the classical tools for specifying tree models in analytic combinatorics are not giving here usable generating functions, we aim at defining an evolution process that associates, to each Schröder tree, an evolution represented by an increasing labelling of its internal nodes. Furthermore, in our second model, we relax the labelling constraints by allowing repetitions of labels. In the dynamical construction of the trees, allowing repetition of labels means allowing the addition of several nodes at once in the tree. Our generalisations can be seen as natural discretetime versions of the classical probabilistic model of Yule trees (see, e.g., [START_REF] Steel | Properties of phylogenetic trees generated by yule-type specification models[END_REF]); recall that, in the Yule tree, the time between two branchings are exponentially distributed.

This work is part of a long-term over-arching project, in which we aim at relaxing the classical rules of increasing labelling (described in, e.g., [START_REF] Bergeron | Varieties of increasing trees[END_REF]), by, for example, allowing labels to appear more than once in the tree. The following papers are part of this strand of research: [START_REF] Bodini | On the number of increasing trees with label repetitions[END_REF][START_REF] Bodini | Families of Monotonic Trees: Combinatorial Enumeration and Asymptotics[END_REF] introduce and study models of labelled trees with less-constrained increasing labelling rules; [BDF + 16] focuses on increasingly-labelled "diamonds"; and [START_REF] Genitrini | Asymptotic enumeration of compacted binary trees of bounded right height[END_REF] analyses at a compacted structure that specifies classes of directed acyclic graphs.

In this paper, we introduce two new different models of Schröder trees with chronological evolution: the increasing Schröder trees and the strict monotonic Schröder trees. One important feature of these models is that they can both be simulated efficiently. The models are based on some increasing labelling of Schröder trees, and the repetition of labels is allowed in the second model. For the two models, we prove asymptotic results about important characteristics of a typical large tree of this class (e.g. root distribution, number of nodes of arity 2, 3, etc, height of the tree, etc -see Table 1 where our main results are summarised), and design an algorithm that generates a large tree taken uniformly at random among all trees of a given size in the class. The quantitative analysis of the models and the design of the random samplers rely on a combination of analytic combinatorics methods (see [START_REF] Flajolet | Analytic combinatorics[END_REF] for a survey), probabilistic methods (in particular methods developed by Devroye [START_REF] Devroye | On the height of random m-ary search trees[END_REF] to study the height of split trees), and bijective methods (we exhibit bijections between our classes of trees and classes of permutations, these are then useful for the analysis of different characteristics and for the design of the generation algorithms). In particular, we exhibit interesting relations between Stirling numbers and parameters on trees such as the number of the labellings of nodes, the number of internal nodes, and the depth of a leaf.

Generic approach highlighted in the paper: Similarly to the recursive tree, the two models have a generic constrained evolution process. The specificity of each model is induced by small changes of the evolution process: we give here a generic, non precise description of the evolution process, details specific to each family of trees will be given in each section:

• Start with a single (unlabelled) leaf;

• Iterate the following process: at step (for ≥ 1), select a subset of leaves and replace each selected leaf by an internal node with label attached to an arbitrary sequence of leaves. Note that the increasing labelling corresponds to the chronology of the construction of the tree: internal nodes labelled by an integer were added at time . Our models differ from each other by different constraints on the set of selected leaves: in our first model, this subset is always of size 1, while it can be bigger in the second model. Importantly, our models can be seen as phylogenetic trees of n species (n being the number of leaves): the labels of internal nodes stand for the times at which different branches of the phylogenetic trees split. Plan of the paper: Each of the two main sections (Sections 2 and 3) is dedicated to one of our models of labelled Schröder trees. The organisation inside each section is similar: after defining the model we show theorems about different characteristics of the trees using analytic combinatorics and bijective methods. We then exhibit the associated dynamical evolution that generates the considered class of trees, and use this evolution process to (a) design an efficient random sampler for this class of trees and (b) in the case of our first model, prove some probabilistic results about the height of a typical large tree from this class.

Increasing Schröder trees

The first model we are interested in is a generalisation of the Schröder tree, a classical combinatorial structure that was originally introduced in the context of phylogenetics [START_REF] Schröder | Vier Combinatorische Probleme[END_REF]. Our generalisation consists in labelling the internal nodes of a Schröder tree -denote by their number -with the integers {1, . . . , } with the constraints that each label appears exactly once and a node's label is larger than the label of its parent; such a labelling of a tree is called "increasing", we call such a constrained-labelled Schröder tree an increasing Schröder tree. In the tree seen as an evolutionary process, the labels can be interpreted as the order of appearance of the different nodes (which, for example, stand for different species). Several classes of increasingly-labelled trees have already been studied in the literature using analytic combinatorics [START_REF] Flajolet | Analytic combinatorics[END_REF] methods, but these methods applied to the Schröder tree would raise new technical problems. The novelty of our approach is to use a dynamical description of the increasing Schröder tree inspired by its evolutionary interpretation; this allows us to give the first analytical results about this combinatorial structure.

2.1. The model and its context. In this paper, we define rooted trees as genealogical structures: the root is the unique common ancestor of all nodes of the tree, each node except the root has exactly one parent (the root has no parent), nodes that have no children are called leaves, nodes that have at least one child are called internal nodes. The arity of a node is it's number of children. We say that a tree is plane if siblings (nodes that have the same parent) are ordered.

Definition 2.1.1 (see [START_REF] Flajolet | Analytic combinatorics[END_REF]p. 69]). A Schröder tree is a rooted plane tree whose internal nodes all have arity at least 2. The size of a Schröder tree is its number of leaves.

Note that a Schröder tree is an unlabelled combinatorial structure (neither the leaves nor the internal nodes are labelled). In the context of analytic combinatorics the combinatorial class S of Schröder trees is thus specified as

S = Z ∪ Seq ≥2 S.
(1)

Its combinatorial meaning is direct in the context of decomposable objects (see Flajolet and Sedgewick [START_REF] Flajolet | Analytic combinatorics[END_REF] for a detailed introduction for the method of combinatorial specification): An object from S is either a leaf (represented by the single atom Z, of size 1), or it is composed of an internal node, parent of a sequence of at least two elements from S. Note that, in the specification, the internal nodes are omitted (because they are of size 0): the expression Seq ≥2 S is a abbreviation of E × Seq ≥2 S where E stands for an atom of size 0 and Seq ≥2 S is a sequence of at least two elements from S.

Once the combinatorial specification is given, the symbolic method (see [START_REF] Flajolet | Analytic combinatorics[END_REF] for details), translates automatically the equation specifying the objects into a functional equation satisfied by the (ordinary) generating functions associated to the structures. The generating function of S is defined as the formal series S(z) = n≥1 s n z n where s n is the number of Schröder trees of size n (i.e. with n leaves). Using the symbolic method on Equation (1), we get that

S(z) = z + S(z) 2 1 -S(z) . (2)
An elementary iteration allows us to extract the first coefficients of the sequence (s n ) n∈N :

(0, 1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049, 518859, 2646723, 13648869, . . . ) .

Equation (2) implies that the generating function S is algebraic and in fact

S(z) = 1 + z - √ 1 -6z + z 2 4 .
This is sufficient to get the following asymptotic equivalent of s n when n tends to infinity:

s n = 3 √ 2 -4 4 √ π n -3/2 3 -2 √ 2 -n (1 + O( 1 /n)) .
We refer the reader to [FS09, page 69] for a more detailed analysis of this generating function S.

In the rest of the section we are interested in an increasingly-labelled variation of Schröder trees.

Definition 2.1.2. An increasing Schröder tree has a Schröder tree structure and its internal nodes are labelled with the integers between 1 and (where is the number of internal nodes) in such a way that each label appears exactly once and each sequence of labels in the paths from the root to any leaf is (strictly) increasing.

Increasing trees can, to a certain extent, be specified using the Greene operator (see, for example, [FS09, page 139]), and the specification can then be translated into an equation satisfied by the exponential generating function of the increasing tree class. Since in our context the size of a tree is the number of its leaves while only internal nodes are labelled, we need to introduce a second variable u to mark the internal nodes. We let s n, denote the number of increasing Schröder trees with n leaves and internal nodes. Following standard methods in combinatorics we define a generating function that is ordinary for the leaf marks and exponential for the internal node marks: we set S * (z, u) = n, s n, z n u / !. The specification of this combinatorial class is

S * = Z ∪ U Seq ≥2 S * .
Using the symbolic method [START_REF] Flajolet | Analytic combinatorics[END_REF], we obtain the following equation satisfied by S * (z, u):

S * (z, u) = z + u v=0 S * (z, v) 2 1 -S * (z, v) dv.
Although this integral equation could be analysed further in order to get information about increasing Schröder trees, this analysis would be very cumbersome; a better approach is to see the Schröder tree as the result of an evolutionary process. Another advantage of this new approach is that it extends to other families of labelled Schröder trees for which there seems to be no (classical) specification, even using the Greene operator: one such example is the family of strict monotonic Schröder trees studied in Section 3.

In Figure 2 we have represented two increasing Schröder trees: both are generated uniformly at random among all increasing Schröder trees of the same size: size 30 on the left, size 500 on the right. The left-hand-side tree has 27 internal nodes (and 30 leaves). It is the same tree as the one represented in Figure 1, where its chronological evolution is represented on the right-hand side: the internal node labelled by is displayed on level -1 (i.e. at distance -1 from the root on the vertical axis), for all ∈ {1, . . . , 27}. The right-hand-side one is drawn using a circular representation, which is often used for phylogenetic trees: the labels are omitted but as in Figure 1, the length of an edge is proportional to the difference of the labels of the two nodes it connects. This right-hand-side tree has 492 internal nodes (and 500 leaves).

We introduce an evolution process generating increasing Schröder trees:

• Start with a single (unlabelled) leaf;

• Iterate the following process: at step (for ≥ 1), select one leaf and replace it by an internal node with label attached to an arbitrary sequence of new leaves. By taking all trees of the same size together, we obtain the following recurrence, enumerating increasing Schröder trees by size: if, for all n ≥ 1, t n is the number of n-leaf Schröder trees, then t 1 = 1 and, for all n ≥ 2,

t n = n-1 =1 t .
(3)

To make sure that this algorithm generates all increasing Schröder trees and generates each tree exactly "once"; we define this evolution process more rigorously as follows: The process takes as input two sequences of integers (d ) ≥1 and (u ) ≥1 such that u 1 = 1 and for all ≥ 1, d ≥ 2 and 1 ≤ u +1 ≤ i=1 d i -( -1) and gives as an output a sequence (τ ) ≥0 of -internal-node increasing Schröder trees. The process is defined inductively as follows:

• Tree τ 0 is the 1-node tree, without any internal node.

• Given τ , we define τ +1 as follows: we number the leaves of τ in the depth-first order (the choice of the ordering does not matter) from 1 to i=1 d i -( -1), and replace leaf number u +1 by an internal node labelled by + 1 to which d +1 leaves are attached. Note that, by construction, τ is an increasing Schröder tree with internal nodes for all ≥ 0, and the label of a node corresponds to the time in the evolution process when this node became an internal node. In other words, the increasing labelling corresponds to the chronology of the evolution process. Finally, note that the evolution process indeed defines a bijection between the set of increasing Schröder trees having p internal nodes and the set of all sequences (d , u ) 1≤ ≤p such that u 1 = 1, and for all 1 ≤ ≤ p, d ≥ 2 and 1 ≤ u +1 ≤ i=1 d i -( -1).

Recall that we define the size of a Schröder tree to be its number of leaves. It is important to note that, because a Schröder tree with n -1 internal nodes has at least n leaves, the evolution process defines a bijection between the set of all n-leaf Schröder trees and the set of all sequences (d

(n) , u (n) ) 1≤ <n such that for all 1 ≤ < n, u (n) 1 = 1, d (n) ≥ 2, 1 ≤ u (n) +1 ≤ i=1 d (n) i -( -1
), and

i=1 d (n) i -( -1) = n.
2.2. Overview of the main results. We start by solving the enumeration problem in Section 2.3. Then we turn to the analysis of typical parameters in Section 2.4 with the results summarised in Table 2. From the enumeration a relationship with permutations is unveiled. Therefore, in Section 2.5 we will characterise this relationship through a bijection. The bijection will serve as a basis to construct an efficient uniform sampler for this classes that we give in Section 2.6. We conclude with Section 2.7, where we study the average height of these trees; this result is dealt with in an independent subsection because its proof is different from the proofs of all analytical results of Section 2.4 and relies on the uniform sampling method of Section 2.6.

Mean

T = Z ∪ ΘT × Seq ≥1 Z . (4)
In this specification, Z stands for the leaves, and the operator Θ is the classical pointing operator (see [FS09, page 86] for details). The specification is a direct rewriting of the evolution process: a tree is either of size 1 (Z), or it has been built by pointing at a leaf in a smaller tree (ΘT ) and replacing it by a sequence of at least two leaves. Although the latter sequence is of length at least 2, we use the operator Seq ≥1 (Z) instead of Seq ≥2 (Z) because the leaf that was pointed at is reused as the leftmost child of the new internal node.

The symbolic method translates this specification into a functional equation satisfied by the generating function associated to the combinatorial class of increasing Schröder trees. Note that although the increasing Schröder trees are labelled, this labelling does not appear in the specification, i.e. it is possible to work with ordinary generating functions (as opposed to exponential generating functions). This is because the size of an increasing Schröder tree is its number of leaves, and the leaves are not labelled. We define the ordinary generating function associated to T by T (z) = n≥1 t n z n , where t n is the number of increasing Schröder trees of size n. Using the symbolic method (in particular, pointing at a leaf translates into a differential operator), we get

T (z) = z + z 2 1 -z T (z). ( 5
)
From this equation we get that for all n ≥ 3, t n = n t n-1 ; which is also a consequence of Equation (3). Using the fact that t 1 = t 2 = 1, we get that t n = n! /2 for all n ≥ 2 (this sequence (t n ) n appears under the reference OEIS A0017101 ). Note that the radius of convergence of the ordinary generating series T (z) is 0; this series is thus purely formal.

2.4. Analysis of typical parameters. In this section, our aim is to describe the shape of a typical increasing Schröder tree, i.e. a tree taken uniformly at random among all increasing Schröder trees of a fixed size. To get information about this shape, we focus on four characteristics of the tree: the number of internal nodes, the arity of the root, the number of leaves that are children of the root, and the number of binary nodes (node of arity 2). We show asymptotic theorems for these characteristics in a typical increasing Schröder tree when the size goes to infinity.

2.4.1. Quantitative analysis of the number of iteration steps. In this section, we show that although an increasing Schröder tree of size n can have between 1 and n -1 internal nodes, it typically has of order n -ln n internal nodes. This result is particularly interesting to analyse the complexity of the evolutionary process: this means that, on average, this evolutionary process takes of order n -ln n iteration steps to generate a typical increasing Schröder tree of size n. In fact, our result is stronger than just finding an equivalent for the average number of iterations since we prove a central limit theorem for this quantity. To complete the picture we also quantify the average number of nodes of a fixed degree. We will show that the average number of binary nodes in a typical tree is n -2 ln n, the number of ternary nodes is ln n and higher arity nodes have a constant mean.

Theorem 2.4.1. For all n ≥ 1, we denote by X n the number of internal nodes in a tree taken uniformly at random among all increasing Schröder trees of size n.

Then, asymptotically when n tends to infinity,

E Tn [X n ] ∼ n -ln n, V Tn [X n ] ∼ ln n, and X n -(n -ln n) √ ln n d --→ N (0, 1) in distribution.
To prove this theorem, we enrich the specification (4) with an additional parameter U marking the internal nodes:

T = Z ∪ U × Θ Z T × Seq ≥1 Z ,
where the operator Θ Z consists in pointing at an element marked by Z. Note that here we do not use the Greene operator: the increasing labelling is a consequence of the iterative process. Using the symbolic method, this implies that, if t n,k is the number of increasing Schröder trees with n leaves and k internal nodes,

t n (u) = n-1 k=0 t n,k u k , and T (z, u) = n≥1 t n (u) z n , then T (z, u) = z + uz 2 1 -z ∂ z T (z, u), (6)
where ∂ z denotes the partial differentiation according to z. Once again, we write

(1 -z)T (z, u) = z(1 -z) + uz 2 ∂ z T (z, u)
, and extract the coefficient of z n on both sides, we thus get that t 1 (u) = 1, t 2 (u) = u and, for all n > 2,

t n (u) = (1 + (n -1)u) t n-1 (u). ( 7
)
Extracting the coefficient of u k on both sides of this last equation gives: t 1,0 = 1, t n,1 = 1 and for all n > 1,

t n,k = t n-1,k + (n -1) t n-1,k-1 for all 0 < k < n,
and t n,k = 0 otherwise. The first values of t n,k are listed in Table 3. Note that, for all n ≥ 1, t n,n-1 is the number of increasing binary trees (see [FS09, page 143] for details). 1 0 , 1 0 , 1, 2 0 , 1, 5, 6 0 , 1, 9, 26, 24 0 , 1, 14, 71, 154, 120 0 , 1, 20, 155, 580, 1044, 720 From Equation (7), we easily deduce a closed form for t n (u): for all n ≥ 2, we have

t n (u) = u n-1 =2 (1 + u). (8)
This is a shifted version of the sequence OEIS A145324, which is related to Stirling cycle numbers. Our proof of Theorem 2.4.1 relies on the following lemma, which is a straightforward consequence of Equation ( 8). From now on t n (u) will always refer to the generating function of t n,k with respect to k, that is

t n (u) = n-1 k=0 t n,k u k . Lemma 2.4.2. Let SC n (u) =
n-1 i=0 (u + i) be the generating functions of the respective rows of the Stirling Cycle numbers (see [FS09, page 735]), which enumerate all permutations of a set of size n that decompose into k cycles (i.e. Stirling numbers of the first kind). If we set tn (u) = n-1 k=0 t n,k u n-k , which is the row-reversed generating function, then

tn (u) = SC n (u) 1 + u = u n-1 =2 (u + ).
Proof of Theorem 2.4.1. One could apply Hwang's quasi-powers theorem [START_REF] Hwang | On Convergence Rates in the Central Limit Theorems for Combinatorial Structures[END_REF], but since we have an explicit formula for t n (u), we decided instead to apply Lévy's continuity theorem directly. By Lemma 2.4.2, we have that

, if Xn = n -X n , for all ξ ∈ R, E e iξ• Xn -ln n √ ln n = 1 t n e -iξ √ ln n tn e iξ √ ln n = 2 n! e -iξ √ ln n+ iξ √ ln n • Γ n + e iξ √ ln n Γ 2 + e iξ √ ln n = 2 + o(1) Γ(3 + o(1)) n -1 + e iξ √ ln n n+e iξ √ ln n -1 2 e n e -iξ √ ln n e n-1+e
E e iξ• Xn -ln n √ ln n = (1 + o(1)) n -1 + e iξ √ ln n n+e iξ √ ln n -1 2 e -iξ √ ln n n n+ 1 /2 = (1 + o(1)) n e iξ √ ln n e -iξ √ ln n n .
Since

n e iξ √ ln n = exp (ln n) 1 + iξ √ ln n - ξ 2 2 ln n + O (ln n) -3 /2 ∼ n →∞ ne iξ √ ln n-ξ 2 /2 ,
we get

E e iξ• Xn -ln n √ ln n = (1 + o(1)) e -ξ 2 /2 ,
which, by Lévy's continuity theorem concludes the proof; recall that Xn = n -X n .

2.4.2. Quantitative analysis of the root node. In this section, we show that the distribution of the degree of the root of a tree taken uniformly at random among all increasing Schröder trees of size n is in fact independent of n:

Theorem 2.4.3. The degree A T n of the root of a tree taken uniformly at random among all increasing Schröder trees of size n satisfies, for all n ≥ 1,

E[A T

n ] = 2 e -3, and V[A T n ] = 14 e -4 e 2 -8. In fact, for all 2 ≤ k ≤ n, we have

P(A T n = k) = 2k (k + 1)! . ( 9
)
The proof of Theorem 2.4.3 relies on the following lemma.

Lemma 2.4.4. If t n,k is the number of increasing Schröder trees whose root has arity k, then t 1,0 = 1, for all n ≥ 0, t n,1 = 0 and for all n ≥ 2, 2 ≤ k ≤ n -1,

t n,k = k n! (k + 1)! , and t n,n = 1.
Indeed, this lemma together with the fact that t n = n! /2, implies Equation (9). The mean and variance of this probability distribution are then straightforward to calculate, which concludes the proof of Theorem 2.4.3: it only remains to prove Lemma 2.4.4.

We refer the reader to Table 4 where the first values of t n,k are listed. The sequences (t n (u)) n≥1 and (t n,k ) 2≤k<n are related to the sequences OEIS A094112 and OEIS A092582, which enumerate some families of permutations (the former enumerates a family of permutations avoiding some pattern, the second permutations with initial cycle of a given size). Since the number of increasing Schröder trees of size n ≥ 2 is equal to n! /2, it is natural to expect some links between this family of trees and permutations: in Section 2.5 we exhibit a bijection between the two families. 1, 0 0, 0, 1 0, 0, 2, 1 0, 0, 8, 3, 1 0, 0, 40, 15, 4, 1 0, 0, 240, 90, 24, 5, 1 0, 0, 1680, 630, 168, 35, 6, 1 Table 4. Values of t n,k , the number of size-n increasing Schröder trees of root-arity k, and 0 ≤ k ≤ n ∈ {1, . . . , 7}.

Proof of Lemma 2.4.4. In this proof, the variable U marks the arity of the root (we re-use the same notation as in the previous section, but with a different meaning; this is done to avoid having too many different notations). Using the evolution process, we get that

T = Z ∪ U × Z × Seq ≥1 (U × Z) ∪ Θ Z (T \ Z) × Seq ≥1 Z .
Indeed, the root is either a leaf (Z), or it is an internal node to which is attached a sequence of at least 2 leaves (U × Z × Θ Z (Z) × Seq ≥1 (U × Z)), or the tree is larger, i.e. the last step in the evolution process was replacing another leaf by an internal node to which is attached a sequence of non-marked leaves (Θ Z (T \ Z) × Seq ≥1 Z). Using the symbolic method, we thus get that

T (z, u) = z + u 2 z 2 1 -uz + z 2 1 -z ∂ z (T (z, u) -z) .
In the same way as before, through a direct extraction [z n ](1 -zu)(1 -z)T (z, u), we prove that t 1 (u) = 1, t 2 (u) = u 2 , and for all n > 2,

t n (u) = (u -1) u n-1 + n t n-1 (u).
This implies t 1,0 = 1, t n,n = 1 for all n ≥ 1, t n,k = n t n-1,k for all 1 ≤ k ≤ n -1, and t n,k = 0 for all k > n, which concludes the proof.

2.4.3. Quantitative analysis of the number of nodes of a given arity. In this section, we prove asymptotic results for the number of nodes of a given arity in a typical increasing Schröder tree, starting with binary nodes:

Theorem 2.4.5. Let B n be the number of binary nodes (nodes of arity 2) in a tree taken uniformly at random among all increasing Schröder trees of size n. Asymptotically when n tends to infinity, we have

E[B n ] = n-2 ln n+2γ- 7 3 +O 1 n , and V[B n ] = 4 ln n+4 γ- 2 3 π 2 - 17 6 +O 1 n ,
where γ is the Euler-Mascheroni constant. Moreover, in distribution when n tends to infinity,

B n -(n -2 ln n) 2 √ ln n → N (0, 1).
In other words, on average, almost all internal nodes are binary, and only a proportion of order 2 ln n/n of internal nodes are at least ternary. In the following theorem, we show that, on average, half of all non-binary nodes are ternary.

Theorem 2.4.6. Let C ( ) n be the number of nodes of arity ≥ 3 in a tree taken uniformly at random among all increasing Schröder trees of size n. Asymptotically when n tends to infinity, we have EC (3) n = ln n + O(1), and EC ( ) n ∼ c , for some positive constants (c ) ≥4 ; and, for = 4, we have c 4 = 23 /90. Proof of Theorem 2.4.5. Here the specification is easy to exhibit, and its translation via the symbolic method is direct (in this proof, U marks the binary nodes):

T = Z ∪ Θ Z T × U × Z ∪ Seq ≥2 Z ; T (z, u) = z + u z 2 + z 3 1 -z ∂ z T (z, u).
The method we use to analyse this differential equation is similar to [START_REF] Chern | Distribution of the number of consecutive records[END_REF]. For all n ≥ 3,

t n (u) = (1 + u(n -1))t n-1 (u) + (1 -u)(n -2)t n-2 (u), (10)
with t 1 (u) = 1 and t 2 (u) = u. Once again (see also Lemma 2.4.2) we take the normalised row-reversed generating function tn

(u) = 2 n! n-1 k=0 t n,k u n-k = 2 n! u n t n ( 1 /u).
From Equation (10), we get that, for all n ≥ 3,

tn (u) = n + u -1 n tn-1 (u) + u(u -1)(n -2) n(n -1) tn-2 (u), (11)
with t1 (u) = 2u and t2 (u) = u. We now define F (z, u) = n≥1 n tn (u)z n ; this generating function satisfies the following differential equation:

z (1 -z) ∂ z F (z, u) = 1 + uz -u(1 -u)z 2 F (z, u) + 2u 2 z 2 , with initial condition ∂ z F (z, u)| z=0 = 2 u. This last equation gives F (z, u) = 2uz (1 -z) u 2 +1 e u(1-u)z • 1 - z 0 u(1 -t) u 2 e -u(1-u)t dt .
We remark that F (z, u) is singular at z = 1 with a pole of order u 2 + 1, thus

F (z, u) ∼ z=1 g(u) (1 -z) u 2 +1 , with g(u) = 2ue u(1-u) 1 - 1 0 u(1 -t) u 2 e -u(1-u)t dt .
Therefore, asymptotically when n → +∞,

n tn (u) = g(u) Γ (u 2 + 1) n u 2 1 + O 1 n ,
uniformly for all u such that |u-1| ≤ δ for some δ > 0. This thus falls into the scope of the quasi-powers framework and Theorem IX.8 [FS09, p. 645] is applicable with B(u) = exp (2u) and β n = ln n, which concludes the proof (the mean and variance expansions can be calculated automatically using, e.g., a computer software such as Maple).

Proof of Theorem 2.4.6. We first look at ternary nodes: the specification (with U marking ternary nodes) is given by

T = Z ∪ Θ Z T × Z ∪ U × Z 2 ∪ Seq ≥3 Z which implies T (z, u) = z + z 2 + u z 3 + z 4 1 -z ∂ z T (z, u),
and thus, for all n ≥ 4:

t n (u) = nt n-1 (u) + (u -1)(n -2)t n-2 (u) + (n -3)(1 -u)t n-3 (u),
with t 0 (u) = 0, t 1 (u) = 1 and t 2 (u) = 1. Differentiating this equation, we get that, for all n ≥ 5,

t n (u)| u=1 = nt n-1 (u)| u=1 + (n -2)(n -2)! 2 - (n -3)(n -3)! 2 .
This thus implies that, for all n ≥ 5,

E[C (3) n ] = E[C (3) n-1 ] + (n -2) n(n -1) - (n -3) n(n -1)(n -2) = 5 12 + n =5 (k -2) k(k -1) - (k -3) k(k -1)(k -2)
. We reason similarly for = 4 (U now marks nodes of arity 4):

T = Z ∪ Θ Z T × Z ∪ Z 2 ∪ U × Z 3 ∪ Seq ≥4 Z ; T (z, u) = z + z 2 + z 3 + u z 4 + z 5 1 -z ∂ z T (z, u).
Thus, for all n ≥ 4, we have

t n (u) = nt n-1 (u) + (u -1)(n -3)t n-3 (u) + (n -4)(1 -u)t n-4 (u),
with t 0 = 0, t 1 (u) = 1, t 2 (u) = 1 and t 3 (u) = 3, which, after differentiating at u = 1 and dividing by t n gives, for n ≥ 6,

E[C (4) n ] = E[C (4) n-1 ] + (n -3) n(n -1)(n -2) - (n -4) n(n -1)(n -2)(n -3)
,

with E[C (4) 5 ] = 6 /60. The recurrence can be solved explicitly and we obtain,

E[C (4) n ] = 23 90 - 13 6n - 1 6 (n -2) + 4 3 (n -1)
, which proves the statement for = 4. We now treat the general ≥ 5 case (U now marks nodes of arity ):

T = Z ∪ Θ Z T × ∪ -2 i=1 Z ∪ U × Z -1 ∪ Seq ≥ Z ; T (z, u) = z + -1 i=2 z i + u z + z +1 1 -z ∂ z T (z, u).
This implies that, for all n ≥ :

t n (u) = nt n-1 (u) + (u -1)(n -+ 1)t n-+1 (u) + (n -)(1 -u)t n-(u),
with t n (u) = t n for all n < . Therefore, we get, for n ≥ + 2,

E[C ( ) n ] = E[C ( ) n-1 ] + n -+ 1 n(n -1) • • • (n -+ 2) - n - n(n -1) • • • (n -+ 1) = E[C ( ) +1 ] + n k= +1 (k -+ 1) k(k -1) • • • (k -+ 2) - (k -) k(k -1) • • • (k -+ 1) . Since k -+ 1 k(k -1) • • • (k -+ 2) - k - k(k -1) • • • (k -+ 1) ∼ k→∞ 1 k -2 , which implies that, for all ≥ 4, lim n→∞ E[C ( ) n ] = E[C ( ) +1 ] + ∞ k= +1 k -+ 1 k(k -1) • • • (k -+ 2) - k - k(k -1) • • • (k -+ 1) < +∞.
All these sequences converge to constants that get smaller and smaller when increases.

Table 3 gives a summary of the typical number of nodes for the smallest arities: the first three values appear explicitly in the latter proofs and an obvious adaptation of Theorem 2.4.6 gives the constants c for larger . Figure 3. The asymptotic number of -ary nodes 2.5. Bijection with permutations. Since the number of increasing Schröder trees of size n is equal to t n = n! /2, it hints at the existence of a relationship between our model of increasing trees and a subclass of permutations. In this section, we aim at exhibiting this relationship.

We denote by σ = (σ 1 , . . . , σ n ) the size-n permutation that sends i to σ i ∈ {1, . . . , n} for all i ∈ {1, . . . , n}. For all k ∈ {1, . . . , n}, we denote by σ -1 (k) the pre-image of k by σ, and sometimes call σ -1 (k) the "position" of k in the permutation σ.

We now define recursively a map M between HP, the class of permutations such that 1 appears before 2, and the class T of increasing Schröder trees.

The only element of HP of size 2 is the permutation (1, 2); we set its image to be the tree whose root is labelled by 1 and has two (unlabelled) leaf-children. Now assume that we have defined M(σ) for all permutations σ ∈ HP of size at most n -1 for some n ≥ 2 and let σ be a size-n permutation in HP. We distinguish two cases according to the pre-image of n by σ; we denote by σi = σ i if σ i < σ n and σi = σ i -1 otherwise. For example, if σ = (4, 1, 5, 2, 3), then σ = (3, 1, 4, 2); σ can be seen as the permutation induced by σ on {1, . . . , n -1}.

• If σ -1 (n) = n then, we set M(σ) to be the tree M(σ) in which we add a new rightmost leaf to the internal node with the largest label. In Figure 4 we present the mapping on an example, where we have ordered the steps reversely to understand the process in a constructive way.

• If σ -1 (n) = k < n,
Theorem 2.5.1. The map M is a one-to-one map between HP and T .

Proof. First note that the image by M of a permutation of size n is a Schröder tree of size n: indeed, at each iteration we remove exactly one element from the permutation and add exactly one leaf to the tree by either adding a leaf to the node with largest label or by removing one leaf and adding two new ones. Since the number of permutations of size n in HP is equal to the number of Schröder trees of size n, it is enough to prove that M is injective to conclude the proof. The mapping is injective since by induction at each iteration we remove the greatest element of the permutation and the following actions are performed on the resulting tree in a non-ambiguous manner. This concludes the proof.

2.6. Uniform random sampling. In this section, we present an algorithm that samples a Schröder tree uniformly at random among all Schröder trees of a given size. Our aim is to use this algorithm to generate trees of large size (typically several thousands of leaves): we thus provide a detailed analysis of the complexity of our sampler.

Note that the uniform sampling of structures with increasing labelling constraints is not so classical in the context of analytic combinatorics. Martínez and Molinero [START_REF] Martínez | Generic algorithms for the generation of combinatorial objects[END_REF][START_REF] Molinero | Ordered Generation of Classes of Combinatorial Structures[END_REF] focus on the recursive method: using and generalising recursive and unranking generation methods, they give a method that, given a combinatorial specification, automatically outputs a uniform generation algorithm and its complexity analysis. Using a different approach based on Boltzmann generation, Bodini, Roussel and Soria [START_REF] Bodini | Boltzmann samplers for first-order differential specifications[END_REF] give an algorithmic framework to develop Boltzmann samplers in the context of specifications that lead to differential equations of the first order. The paper [BDF + 16] shows that this framework can be extended to the context of differential equations of higher order; in particular, they apply this method to the generation of diamonds satisfying differential equations of order 2.

The bijection presented in Section 2.5 immediately gives an algorithm that samples a tree uniformly among all Schröder trees of size n: first sample a permutation uniformly at random among all permutations of size n in HP, and then build its image by M. While there exists fast algorithms to sample permutations (see for example [START_REF] Bacher | Generating random permutations by coin tossing: Classical algorithms, new analysis, and modern implementation[END_REF]), it is not clear how to make the application of M efficient.

Instead, we use the bijection M as a basis for a direct probabilistic construction. Indeed, one can sample a permutation uniformly at random in HP by doing the following recursive procedure: if n = 2, then return σ (2) = (1, 2). If n ≥ 3, assume we have sampled σ (n-1) uniformly among all permutations of size n -1. Draw an integer k n uniformly at random in {1, . . . , n}, and set σ (n) n = k n , and

σ (n) i = σ (n-1) i if σ (n-1) i < k n σ (n-1) i + 1 otherwise.
One can indeed check that σ (n) is uniformly distributed among all permutations of size n in HP. Executing this random sampling of σ (n) simultaneously with M (note that, for all n ≥ 3, σ (n-1) = σ(n) , where the notation σ is defined in the definition of M) is the idea of our sampler:

Algorithm 1 Increasing Schröder Tree Builder

1: function TreeBuilder(n) 2:
if n = 1 then 3:

return the single leaf 4:

T = the root labelled by 1 and attached to two leaves 5: = 2 6:

for i from 3 to n do 7:

k = rand int(1, i) 8: if k = i then 9:
Add a new leaf to the last added internal node in T 10: else 11:

Create a new binary node at position k in T 12:

with label and attached to two leaves 13:

= + 1 14:

return T

The function rand int(a, b) returns uniformly at random an integer in {a, a + 1, . . . , b}.

Using adequate data structures, as for example by keeping an array of pointers to all leaves and another one to the last inserted internal node, each insertion in the tree under construction is done in constant time. We thus get Theorem 2.6.1. The function TreeBuilder(n) in Algorithm 1 is a uniform sampling algorithm for size-n trees. Asymptotically, it operates in O(n) operations on trees and necessitates O(n ln n) random bits. 2.7. Analysis of the height of a typical increasing Schröder tree. The probabilistic construction used in our uniform sampler allows us to prove the following result.

Theorem 2.7.1. For all n ≥ 2, let H n be the height of a tree taken uniformly at random among all increasing Schröder trees of size n. Asymptotically when n tends to infinity,

P H n ln n ∈ [1 -ε, γ + ε] → 1,
where γ = inf{c ≥ 2 : c -1 + c ln(2/c) < 0} ≈ 4.311. This implies in particular that E[H n ] = Θ(ln n) when n tends to infinity.

Note that, equivalently, γ can be defined as the smallest solution of c -

1 + c ln(2/c) = 0 on [2, ∞).
We remark all other results in this section on increasing Schröder trees are more precise than a Θ order. However, since the height involves a maximum (maximum height of a leaf in the tree), it is not a surprise that the height is more intricate to study than other parameters. In the literature, precise results on the height are known for two classes of random trees: the trees for which a scaling limit result can be proved (e.g. Catalan trees' scaling limit is Aldous' continuous random tree), or the split trees of Devroye (see, e.g., [START_REF] Devroye | On the height of random m-ary search trees[END_REF]). Increasing Schröder trees fall in neither of these two classes; however, we are able to adapt Devroye's techniques to get the upper bound in Theorem 2.7.1.

We split the proof of Theorem 2.7.1 in two parts: we prove the upper bound in Section 2.7.1, and the lower bound in Section 2.7.2 2.7.1. Upper bound in Theorem 2.7.1. Definition 2.7.2. Given a sequence of integers d = (d i ) i≥1 , we define the random d-ary tree (τ (d) n ) n≥0 recursively as follows: τ (d) 0 is reduced to its root, given τ (d) -1 , we build τ (d) as the tree obtained by picking a leaf uniformly at random in τ (d) -1 and replacing it by a node to which d leaves are attached.

Lemma 2.7.3. Let D = (D ) ≥1 be the sequence of integer-valued random variables defined for all k ≥ 2 by: (i) P(D 1 = k) = 2k/(k + 1)!, and (ii) if, for all ≥ 1, we denote by D = i=1 D i , then,

P(D +1 = k|D 1 , . . . , D ) = ( D + 1)!(k -1 + D ) (k + D )! .
Then, for all ≥ 1, the tree τ (D) is equal in distribution to an increasing Schröder tree taken uniformly at random among all trees of its size.

Proof. To prove this claim, it is enough to show that if, for all i ≥ 1, D i is the degree of node i in an increasing Schröder tree taken uniformly at random among all trees of its size, then the distribution of (D i ) i≥1 satisfies (i) and (ii). We show how this follows from Theorem 2.6.1: Indeed, note that the degree of the last inserted internal node increases as long as the random integer k = k i (see line 7

of Algorithm 1) drawn in the i-th loop is equal to i. Note that this happens with probability 1 /i. For example, the degree of the root starts at 2, we draw the first integer k 3 ∈ {1, 2, 3} and if k 3 = 3, then we can conclude that D 1 = 2, otherwise, we know that D 1 ≥ 3 and we need to look at k 4 . Therefore, P(D 1 = 2) = 2 /3, as claimed, and P(D 1 ≥ 3) = 1 /3. Iterating this argument, we get that

P(D 1 ≥ k) = k i=3 P(k i = i) = k i=3 1 i = 2 k! ,
and thus

P(D 1 = k) = P(D 1 ≥ k) -P(D 1 ≥ k + 1) = 2 k! - 2 (k + 1)! = 2k (k + 1)! , as claimed.
By definition of our sampling algorithm, we know that the ( +1)-st internal node is inserted into the tree during the loop number i = D 1 + • • • + D + 1 = D + 1. Therefore, we get

P(D +1 = 2|D 1 , . . . , D ) = P(k i+1 = i + 1) = 1 - 1 D + 2 ,
as claimed, and

P(D +1 ≥ 3|D 1 , . . . , D ) = 1 D + 2 .
Iterating this argument, we get that, for all k ≥ 3,

P(D +1 ≥ k|D 1 , . . . , D ) = D +k-1 j= D +2 P(k j = j) = D +k-1 j= D +2 1 j = ( D + 1)! ( D + k -1)! .
This concludes the proof because

P(D +1 = k|D 1 , . . . , D ) = P(D +1 ≥ k|D 1 , . . . , D ) -P(D +1 ≥ k + 1|D 1 , . . . , D ) = ( D + 1)! ( D + k -1)! - ( D + 1)! ( D + k)! = ( D + 1)!( D + k -1) (k + D )! .
This lemma allows us to prove the upper-bound in Theorem 2.7.1: This proof is an adaptation of Devroye [START_REF] Devroye | On the height of random m-ary search trees[END_REF] in which the case of regular trees is treated (in regular trees, nodes have all the same degree; they are also known as random k-ary trees). We denote by N 1 (n), . . . , N D1 (n) the sizes of the subtrees of the root of τ (D) n ; a straightforward adaptation of [Dev90, Lemma 2] gives that, conditionally on D 1 ,

P((n -m + 2)S 1 ≥ x) ≤ P(N 1 (n) ≥ x) ≤ P(nS 1 ≥ x), (12)
where S 1 is the minimum of D 1 -1 i.i.d. random variables uniform on [0, 1]. We reason conditionally on the sequence D of random degrees, and denote by P D the law under this conditioning. We denote by S 1 , . . . , S D1 the spacings induced on [0, 1] by a sample of D 1 -1 i.i.d. random variables uniform on [0, 1]. Using the fact that the sizes of the subtrees of the root, N 1 (n), . . . , N D1 (n) all have the same distribution, we get

P D (H n ≥ k) ≤ D1 i=1 P D (H Ni(n) ≥ k -1) = D 1 P D (H N1(n) ≥ k -1) ≤ D 1 P D (H nS1 ≥ k -1),
where we have used Equation ( 12) in the last inequality. We now iterate this identity: we denote by

I(n) = n k i=1 S(D i ),
where, for all d ≥ 2, S(d) is the minimum of d -1 i.i.d. random variables uniform on [0, 1]. We get

P D (H n ≥ k) ≤ k i=1 D i P D H I(n) ≥ 0 = k i=1 D i P D n k i=1 S(D i ) ≥ 1 ,
because a tree has height at least 1 as soon as it has at least one internal node. We now use Chebychev's inequality, which implies that, for all α ≥ 1,

P D (H n ≥ k) ≤ k i=1 D i n α E D k i=1 S(D i ) α = n α k i=1 Γ(D i + 1) Di-1 i=1 (α + i) .
See [Dev90, Equation (1)] for the last equality. For all α ≥ 1, and for all d ≥ 2, we have

ln Γ(d + 2) - d i=1 ln(α + i) = ln Γ(d + 1) - d-1 i=1 ln(α + i) + ln(d + 1) -ln(α + d) ≤ ln Γ(d + 1) - d-1 i=1 ln(α + i).
Therefore, since D i ≥ 2 almost surely for all i ≥ 1, we get

P D (H n ≥ k) ≤ n α k i=1 Γ(3) α + 1 = n α 2 α + 1 k .
This expression is minimised for α = k/ ln n -1; taking k = c ln n and α = c -1, we get that, for all c ≥ 2 (because α ≥ 1),

P D (H n ≥ c ln n) ≤ n c-1+c ln(2/c) .
If we take c > γ where γ = inf{c ≥ 2 : c -1 + c ln(2/c) < 0}, then

P D (H n ≥ c ln n) → n→∞ 0,
which concludes the proof for the upper bound in Theorem 2.7.1. 2.7.2. Lower bound in Theorem 2.7.1. For this proof, we use the fact that the height of a tree is larger or equal to the depth of the leftmost leaf; the following lemma gives information on the behaviour of this quantity: Lemma 2.7.4. Let Y n be the depth of the leftmost leaf in a tree taken uniformly at random among all increasing Schröder trees of size n.

For n ≥ 1, Y n d = n -X n ,
where X n is the number of internal nodes in a typical increasing Schröder tree of size n (see Theorem 2.4.1), and thus, we have convergence in distribution when n tends to infinity:

Y n -ln n √ ln n d --→ N (0, 1).
Note that the choice of the leftmost leaf is arbitrary, although it has the advantage that the specification is straightforward.

Proof. We directly look at the differential equation satisfied by T (z, u), where u marks the internal nodes that belong to the leftmost path (between the root and the leftmost leaf).

T (z, u) = z + ∂ z T (z, u) z z 3 1 -z + T (z, u) uz 1 -z .
Indeed, the tree is either a unique leaf (which is thus also the leftmost leaf) at height zero (z), or at the last step of the evolution process, we have selected a leaf that is not the leftmost one and replaced it by a sequence of at least two leaves (∂ z (T (z, u)/z) z 3 1-z ), or we have replaced the leftmost leaf by an internal node and a sequence of at least two leaves (T (z, u) uz 1-z ). We rewrite this equation as

(1 -uz)T (z, u) = z(1 -z) + z 2 ∂ z T (z, u),
and thus, identifying the coefficient of z n on both sides gives that

t n (u) = (u + n -1)t n-1 (u),
t 1 (u) = 1, and t 2 (u) = u. This implies that, for all n ≥ 3,

t n (u) = u n-1 i=2 (u + i) = 1 1 + u SC n (u),
where SC n (u), defined in Lemma 2.4.2, is the generating function of all size n permutations with k cycles. Therefore, using Lemma 2.4.2, we get that Y n d = n-X n in distribution, where X n is the number of internal nodes in a typical increasing Schröder tree, which concludes the proof, by Theorem 2.4.1.

The lower bound of Theorem 2.7.1 follows from Lemma 2.7.4 since, almost surely for all ≥ 1, H ≥ Y D +1 , where we recall that Y n is the depth of the leftmost leaf in an n-leaf uniform increasing Schröder tree and D = i=1 D i . Indeed, by Lemma 2.7.4, we have that, for all ε > 0,

P(H n ≤ (1 -ε) ln n) ≤ P(Y n ≤ (1 -ε) ln n) ≤ P Y n -ln n √ ln n ≤ -ε √ ln n → 0,
when n tends to infinity, which concludes the proof of the lower bound of Theorem 2.7.1.

Strict monotonic Schröder trees

3.1. The model and its context. In this section we introduce and study a generalisation of the increasing Schröder trees, which we call strict monotonic Schröder trees. The main difference between the two models is that in strict monotonic Schröder trees, several internal nodes can be labelled by the same integer as long as they are not on the same ancestral line:

Definition 3.1.1. A strict monotonic Schröder tree is a classical Schröder tree structure whose internal nodes are labelled by the integers between 1 and (for some ≥ 1), in such a way that each integer in {1, . . . , } appears at least once in the tree and the sequence of labels in the path from the root to any leaf is (strictly) increasing.

We remark that the trees are qualified by "strict" in the sense that the sequence of labels along the paths from the root to any leaf is strictly increasing. In Figure 5 we show two strict monotonic trees: the left-hand-side one is of size 30 with 16 distinct labels, the right-hand-side one is of size 500 (sampled uniformly at random among all trees of size 500), with 495 internal nodes labelled with 372 distinct labels.

Because of the possible repetition of labels, this class of labelled trees cannot be directly specified using the classical analytic combinatorics operators for labelled structures. However, the following recursive construction allows us to specify the class of strict monotonic Schröder trees using operators for unlabelled structures. Every strict monotonic Schröder tree can be built as follows:

• Start with a single (unlabelled) leaf.

• At step (for ≥ 1), select a non-empty subset of leaves and replace each of them by an internal node with label attached to a sequence of at least two leaves.

Overview of the main results.

As in Section 2, we first solve the counting problem and its asymptotic equivalent for this family of trees (see Section 3.3).

We then notice that the enumeration problem corresponds to the one of ordered set partitions which are counted by ordered Bell numbers, and, in Section 3.4, we exhibit a bijection between weakly increasing Schröder trees and ordered set partitions. Solving the counting problem and exhibiting this bijection allows us to study some typical parameters of these trees (see Section 3.5; the results of this section are summarised in

G = Z ∪ G[Z → (Z ∪ Seq ≥2 Z)] \ G.
Note that again the labelling does not appear directly in the specification. The combinatorial meaning of this specification is the following: A tree of G is either a single leaf, or it is obtained by taking an already constructed tree in G, and replace each leaf by either a leaf (i.e. no change) or an internal node attached to a sequence of at least two leaves. Furthermore we omit the case where no leaf is changing (this is why we subtract the set G). Note that subtracting G is important, otherwise some integer values could be absent in the final tree. For example, if there is no change at step 2 but then the evolution continues, then 2 would not appear in the final tree but larger integers would appear as labels.

Using the symbolic method, we can translate this specification into a functional equation (with substitution) for the ordinary generating series:

G(z) = z + G z + z 2 1 -z -G(z) = z + G z 1 -z -G(z). (13)
From this equation we extract the recurrence for the number g n of strict monotonic Schröder trees with n leaves: we get

g n = [z n ] z + G z + z 2 1 -z -G(z) = δ n,1 -g n + ≥1 g [z n-] 1 1 -z .
We use Kronecker's notation: δ n,1 = 1 if n = 1 and 0 otherwise. The last coefficient follows from the binomial theorem. This implies

g n =    1 if n = 1, n-1 =1 n-1 -1 g otherwise. ( 14
)
The first terms are equal to a shift of the sequence of ordered Bell numbers (also called Fubini numbers or surjection numbers) referenced as OEIS A000670:

(g n ) n∈N = (0, 1, 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563, . . . ) .

We recall that the n-th ordered Bell number counts the number of ordered partitions of a set of size n, where an ordered partition of a set S is an ordered sequence of disjoint subsets of S whose union is equal to S. Ordered Bell numbers are specified by

B = Seq (Set ≥1 Z) . (15)
Motivated by this remark, we define in Section 3.4 a bijection between the set of strict monotonic Schröder trees and the set of ordered partitions. Following the approach developed by Pippenger in [START_REF] Pippenger | The hypercube of resistors, asymptotic expansions, and preferential arrangements[END_REF] for ordered Bell numbers, we compute the exponential generating function of G, i.e. we apply the Borel transform on G(z). But first we recall some basic properties of the latter transform. The Borel transform, denoted by B, takes as an argument an ordinary generating function and gives as its image the corresponding exponential generating series. More precisely, for all real-valued sequence (a n ) n≥0 , we set

B   n≥0 a n z n   = n≥0 a n z n n! .
Note that if t n ≤ ρ n n! for n sufficiently large then B[T (z)] is analytic around 0. It is easy to check that:

Fact 3.3.1. For all ordinary generating functions f = f (z), we have

(i) B [zf (z)] = z 0 B[f (t)]dt and (ii) B [f (z)] = (B[f (z)]) + z(B[f (z)]) .
Proposition 3.3.2. The exponential generating function enumerating strict monotonic Schröder trees is

B[G(z)] = 1 2 (z -ln (2 -e z )) .
Proof. From Equation ( 14) we obtain

2g n = δ n,1 + n =1 n -1 -1 g .
This recurrence can be directly used to derive an equation for the exponential generating function of G:

2B[G(z)] = z + n≥1 n =1 n -1 -1 g z n n! ,
which is the classical equation satisfied by the ordered Bell numbers. Following the approach of [START_REF] Pippenger | The hypercube of resistors, asymptotic expansions, and preferential arrangements[END_REF], we differentiate the equation with respect to z and get

2(B[G(z)]) = 1 + n≥1 n =1 n -1 -1 g z n-1 (n -1)! .
Since the sum is the convolution of (B[G(z)]) with exp(z), we get

(B[G(z)]) = 1 2 -e z , which implies B[G(z)] = (z -ln (2 -e z )) /2 as claimed.
Recall that ordered Bell numbers are specified by B = Seq(Set ≥1 Z) and thus have exponential generating function B(z) = 1/(2 -e z ). This directly implies that our sequence (g n ) n≥0 is equal to the sequence of ordered Bell numbers shifted by one, since B(z) is the derivative of B[G(z)]. This link between strict monotonic trees and ordered Bell numbers has the interesting following consequence: we have shown that the (shifted) ordinary generating function of the ordered Bell numbers satisfies Equation (13). As far as we can tell, this was not known before.

The asymptotic behaviour of ordered Bell numbers is known (see, e.g., [FS09, p. 109]): if we denote by b n the n-th ordered Bell number, then

b n = n =0 ! n ∼ n→∞ n! 2 (ln 2) n+1 ,
where the n 's are the Stirling partition numbers (also called Stirling numbers of the second kind, see [FS09, Appendix A.8]). They count the number of ways to partition a set of n objects into k non-empty subsets.

The number b n is equal to the number g n+1 of strict monotonic Schröder trees of size n + 1, which implies that, for all n ≥ 1,

g n = n-1 =0 ! n -1 ∼ n→∞ (n -1)! 2 (ln 2) n .
3.4. Bijection with ordered Bell numbers. Since the number of strict monotonic Schröder trees of size n + 1 is equal to the number of ordered partitions of a set of size n, it is natural to try to find an explicit bijection between the two classes.

In this section, we exhibit such a bijection.

To describe precisely the bijection we need the following definitions and notations. Recall that the subsets of an ordered partitions are ordered but the elements inside each subset are not. In the following, we denote by p = (p 1 , p 2 , . . . , p ) the ordered partition of subsets p 1 , . . . , p ; for example, we have ({3, 4}, {1, 5, 7}, {2, 6}) = ({2, 6}, {3, 4}, {1, 5, 7}). We denote by |p i | the size of the i-th subset of p, and by |p| = i=1 p i its total size (i.e. the number of elements of ∪ i=1 p i ). Let a = {α 1 , α 2 , . . . , α r } (with r ≥ 1) be a subset of N; without loss of generality, we can assume that α 1 < α 2 < . . . < α r . A run of a is a maximal sequence (α i , α i+1 , . . . , α j ) (1 ≤ i ≤ j ≤ r) of consecutive integers, i.e. (α i , α i+1 , . . . , α j ) = (α i , α i +1, . . . , α i +j-i), α i-1 < α i -1 and α j+1 > α j +1, unless α i = α 1 or α j = α r . We define the function runs as the function that lists all the runs of a subset: for example, runs({3, 4}) = ({3, 4}) and runs({1, 3, 6, 7}) = ({1}, {3}, {6, 7}).

An ordered partition p = (p 1 , . . . , p ) is called incomplete if and only if ∪ i=1 p i = {1, 2, . . . , |p|}: e.g. the partition ({3, 4}, {1, 5, 7}) is incomplete due to the fact that ∪ i=1 p i = {1, 3, 4, 5, 7} = {1, 2, 3, 4, 5}. We define the normalisation of a partition p (either incomplete or not), denoted by norm(p), as the ordered partition of {1, . . . , |p|} that keeps the relative order between the elements. For example, if p = ({3, 4}, {1, 5, 7}), then norm(p) = [{2, 3}, {1, 4, 5}].

We are now ready to describe our bijection: we first define the mapping M', which associates a strict monotonic Schröder tree to each (possibly incomplete) ordered partition p = (p 1 , . . . , p ). Before starting we fix an arbitrary order for the leaves in the tree once and for all (for example, the one given by the postorder traversal of the tree). Then tree M'(p) is the result of the following recursive procedure:

• At time 1, consider a tree with one internal node labelled by 1 to which are attached |p 1 | + 1 leaves. • At each time 2 ≤ i ≤ , we denote by p 1 , . . . , p i the ordered subsets of the renormalization of (p 1 , . . . , p i ), i.e. norm((p 1 , . . . , p i )) = (p 1 , . . . , p i ).

We denote by r 1 , . . . , r j the runs of p i , i.e. runs(p i ) = (r 1 , . . . , r j ); recall that each of r 1 , . . . , r j is a set of successive integers, possibly reduced to a singleton. Now, we iterate the following process: for k from 1 to j, take the leaf whose index is the first element of In Figure 6 we show how to construct M (p) when p = ({3, 4}, {1, 5, 7}, {2, 6}). The resulting strict monotonic Schröder tree is of size 8. It is straightforward to check that M' is indeed a bijection.

3.5. Analysis of typical parameters. In this section, we give information about the shape of a typical strict monotonic Schröder tree: more precisely, we prove limit theorems for the number of distinct labels and the arity of the root as well as the average number of internal nodes in a tree picked uniformly at random among all strict monotonic Schröder trees of size n (i.e. with n leaves).

3.5.1. Quantitative analysis of the number of iteration steps. The main novelty of strict monotonic Schröder trees compared to increasing Schröder trees is that repetitions of labels are allowed: it is thus natural to ask how many repetitions there are in a typical strict monotonic Schröder tree. To answer this question, one can mark iterations by adding a new variable u in Equation (13):

G(z, u) = z + u G z 1 -z , u -u G(z, u), which implies g n,k =    1 if n = 1 and k = 0, n-1 =1 n-1 -1 g ,k-1 otherwise, (16)
with n being the size and k the number of iteration steps (i.e. the number of distinct labels). In Figure 7, we show the first values of (g n,k ) that are stored in OEIS A019538.

1, 0, 1, 0, 1, 2, 0, 1, 6, 6, 0, 1, 14, 36, 24, 0, 1, 30, 150, 240, 120, 0, 1, 62, 540, 1560, 1800, 720 Theorem 3.5.1. The number of strict monotonic Schröder trees of size n with exactly k distinct labels is given by

g n,k = k! n -1 k .
We denote by X G n the number of distinct labels in a tree picked uniformly at random among all strict monotonic Schröder trees of size n + 1: for all n ≥ 1, X G n is a random variable such that P(X G n = k) = g n,k / n k=1 g n,k . Then, asymptotically when n tends to infinity,

X G n -n 2 ln 2 (1-ln 2)n (2 ln 2) 2 d --→ N (0, 1).
The analysis of the limiting distribution is classical in the quasi-powers framework established by Hwang [START_REF] Hwang | On Convergence Rates in the Central Limit Theorems for Combinatorial Structures[END_REF]; see [START_REF] Flajolet | Analytic combinatorics[END_REF]p. 645,653] for details and applications.

Proof. Recall that g n,k = k! n-1 k is the number of ordered partitions of a set of size n having k non-empty parts. It is known (see, e.g. [Ben73, Example 3.4]) that, if K n is the number of parts in an ordered set partition of size n, then

K n -n 2 ln 2 (1-ln 2)n (2 ln 2) 2 d --→ N (0, 1),
in distribution. This concludes the proof since K n has the same distribution as X G n for all n ≥ 1.

3.5.2. Quantitative analysis of the number of internal nodes. In this model the number of internal nodes is different from the number of distinct labels that appear in the tree: this is because one integer can label several internal nodes. It is thus natural to ask how many internal nodes a typical strict monotonic Schröder trees of size n (i.e. with n leaves) has. The specification marking both leaves (with variable z) and internal nodes (with variable u) is

G(z, u) = z + G z + uz 2 1 -z , u -G(z, u). ( 17
)
We recall that the substitution z → z + uz 2 1-z means that at each iteration each leaf can be left as it is (z → z) or expanded into an internal node attached to an arbitrary number of leaves (z → z 2 1-z ). A new internal, marked with the variable u, is created only in the second case. 1, 0, 1, 0, 1, 2, 0, 1, 5, 7, 0, 1, 9, 31, 34, 0, 1, 14, 86, 226, 214 0, 1, 20,190,874,1946,1652 Figure 8. Distribution of (g n,k ) k for n ∈ {1, . . . , 7} For all 1 ≤ n and 1 ≤ k ≤ n -1, we denote by g n,k the number strict monotonic Schröder trees with n leaves and k internal nodes: Figure 8 shows the values of (g n,k ) 1≤k≤n-1 for n ∈ {1, 2, . . . , 7}. This triangle of integers is not yet stored in OEIS. However, its diagonal is equal to OEIS A171792. In fact in the diagonal the numbers corresponds to the number of strict monotonic trees with n leaves and n -1 internal nodes, i.e. binary strict monotonic trees: this class of trees is studied in [START_REF] Bodini | On the number of increasing trees with label repetitions[END_REF].

Theorem 3.5.2. If we denote by I G n the (random) number of internal nodes in a tree picked uniformly at random among all strict monotonic Schröder trees of size n, then, asymptotically when n tends to infinity,

E[I G n ] = n→∞ n -(ln 2)(ln n) + π 2 12 -1 + (ln 2) -γ + ln 2 2 + ln ln 2 + o(1),
where γ is the Euler-Mascheroni constant.

Proof. For all n ≥ 1, we denote by h n = n-1 k=1 kg n,k , and let H be the ordinary generating function of (h n ) n≥1 ; we have

H(z) = ∂G(z, u) ∂u |u=1 .
The ratio h n /g n is equal to the expected number of internal nodes in a tree taken uniformly at random among all strict monotonic Schröder trees of size n; we are Theorem 3.5.3. Asymptotically when n tends to infinity, A G n converges in distribution to a (shifted) zero-truncated Poisson law with parameter ln 2, i.e. for all u ≥ 0, p n (u) → n→∞ ue u ln 2 -u.

This implies that E[A G n ] → 2 ln 2 + 1 when n tends to infinity. Proof. Thanks to the bijection of Section 3.4, we know that A G n is equal to the size of the first subset +1 in an ordered partition picked uniformly at random among all ordered partitions of {1, . . . , n -1}. We denote by P the class of ordered partitions, 1 is the empty partition, Z is a singleton, and U marks the elements in the first subset. Here the specification is defined in the context of labelled object, thus the associated generating functions are exponential (see [START_REF] Flajolet | Analytic combinatorics[END_REF] for notation details):

P = 1 + Set ≥1 (UZ) Seq(Set ≥1 Z).
Using the symbolic method for exponential generating function, we get

P (z, u) = 1 + e uz -1 2 -e z . Thus, if we set pn (u) = [z n ]P (z, u) [z n ]P (z, 1) , for all n ≥ 0, then [z n ]P (z, u) → n→∞ 1 2 (2 u -1) (ln 2) -n-1 .
This implies that, for all u ≥ 0,

pn (u) → n→∞ 2 u -1.
Note that, by definition, pn (u) is the probability generating function of the size S n of the first subset in an ordered partition picked uniformly at random among all ordered partitions of {1, . . . , n-1}. Because of the bijection of Section 3.4, we know that A G n and S n-1 + 1 have the same distribution, implying that p n (u) = up n (u). This concludes the proof.

3.6. Uniform random sampling. To sample uniformly at random a strict monotonic Schröder tree of size n, we could choose a two-step algorithm. First we sample uniformly an ordered partition of the set {1, . . . , n -1} and then with the use of the bijection of Section 3.4 we transform it into a strict monotonic Schröder tree. But here, in this section, we prefer to present a direct algorithm that generates uniformly a strict monotonic Schröder tree, i.e. without the intermediate step of generating another combinatorial object like an ordered partition.

The global approach for our algorithmic framework deals with the recursive generation method adapted to the analytic combinatorics point of view in [START_REF] Flajolet | A calculus for the random generation of labelled combinatorial structures[END_REF]. But in our context we note that we can obtain for free (from a complexity view) an unranking algorithm. This fact is sufficiently rare to mention it: usually unranking algorithm are less efficient than recursive generation ones. Unranking algorithmic has been developed in the 70's by Nijenhuis and Wilf [START_REF] Nijenhuis | Combinatorial algorithms[END_REF] and then has been introduced to the context of analytic combinatorics by Martínez and Molinero [START_REF] Martínez | Generic algorithms for the generation of combinatorial objects[END_REF]. Here the idea is not to draw uniformly an object, but first to define a total order over the objects under consideration (in our context, strict monotonic Schröder trees) and then an integer (named the rank) is chosen to build deterministically the associated object. Obviously if the rank is uniformly chosen among all possible ranks, then the unranking algorithm is nothing else than a uniformly random sampler. But the unranking approach gives also a way for obtaining an exhaustive sampler, just by iterating the sampling over all possible ranks (the reader can refer to the paper [START_REF] Bodini | Beyond series-parallel concurrent systems: the case of arch processes[END_REF] for an example of both methods: recursive generation and unranking).

For both types of algorithms (unranking or recursive generation) some precomputations are done (only once before the sampling of many objects). We compute (and store) the numbers of trees of sizes from 1 to n. This calculation is done with a quadratic complexity (in the number of arithmetic operations) using the recursive formula for (g n ) n≥1 (see Equation ( 14)). This complexity is only achieved if we first compute and memorise all values of (i!) 1≤i≤n .

Then it only remains to build the tree of rank r recursively. If r is sampled uniformly at random in {0, 1, . . . , g n -1} the algorithm is a uniform sampler and if r is deterministically chosen, then the algorithm is a classical unranking algorithm. To do this, we recall that (see Equation ( 14)), for all n ≥ 1,

g n = n -1 n -2 g n-1 + n -1 n -3 g n-2 + • • • + n -1 0 g 1 , (19)
and interpret this equation combinatorially: to build a tree of size n, we take a size ∈ {1, . . . , n -1} tree T constructed with exactly one less iteration. To grow it into a size-n tree, we interpret the binomial coefficient n-1 -1 as the number of composition of n in parts: some of the leaves of T are replaced by internal nodes to which leaves are attached, some leaves remain leaves. To do that we traverse the tree T and each time we see a leaf, we do the following action: if the next part (in the composition) is of value 1, we keep the leaf unchanged otherwise for a value s > 1, we replace the leaf by an internal node (labelled with the currently step number) and attached s leaves to it. We then take the next part of the composition into consideration and continue the tree traversal.

Focusing on Equation (19) and the equation above we see that a function allowing the unranking of compositions is necessary. Recall that the composition of the integer n into parts is in bijection with the number of sets of combinations of ( -1) elements chosen in (n -1) ones. A way to prove this consists in laying ( -1) barriers in the sequence of n bullets in order to define parts. There are classical algorithms to unrank combinations in the lexicographical order. An algorithm has been described by Buckles and Lybanon [START_REF] Buckles | Algorithm 515: Generation of a vector from the lexicographical index [g6[END_REF]. Furthermore a survey about such an approach has recently been published [START_REF] Genitrini | Lexicographic Unranking of Combinations Revisited[END_REF]. For these algorithms we can easily prove that their average complexity (when ranges over all possibilities) is Θ(n) in the number of arithmetic operations by having first memoized all factorial values of the numbers from 0 to n. In the following we develop a simpler approach based on the classical recursive generation without any lexicographic constraint. The algorithm is an unranking method for the composition of integers. It is based on the reverse lexicographic order (cf e.g. [START_REF] Ruskey | Combinatorial generation[END_REF]) so that we get an easier implementation 2 . For simplification, we suppose having memoized all values of r s for r ∈ {1, n} and s ∈ {1, r}. Using the classical Pascal's rule for binomial coefficients, we obtain the following recurrence for the number of composition of n into parts:

C n, = n -1 -1 = C n-1, + C n-1, -1 . (20)
We thus deduce Algorithm 2 for the unranking method where the union symbol '∪' used in the algorithm represents list concatenation.

Algorithm 2 Reverse Lexicographic Composition Unranking 1: function UnrankComposition(n, , r) 2:

if n = and r = 0 then 3:

return (1, 1, . . . , 1)

4: if r < n-2 -1 then 5: C :=UnrankComposition(n -1, , r) 6: C[0] := C[0] + 1 7: return C 8: else 9: s := r -n-2 -1 10: C := (1) ∪ UnrankComposition(n -1, -1, s) 11: return C
Theorem 3.6.1. The function UnrankComposition is an unranking algorithm (based on the reverse lexicographic order) and calling it with the parameters ≤ n and a uniformly-sampled integer r in {0, . . . , n-1 -1 -1}, gives as output a uniform composition of n into parts.

Using the memorisation of binomial coefficients, the algorithm needs at most ( -1) arithmetic operations on big integers.

The function UnrankComposition manipulates numbers upper bounded by

n-1 -1 ≤ 2 n . Thus the memory size of the big integers, that are used during the calculations, is O(n) bits.

Proof. We prove that the algorithm is correct by induction on n. The result is true when n = and r = 0 since the algorithm returns (1). Fix an integer n and assume that the algorithm is correct for all ≤ n -1, and that the total order over compositions is the reverse lexicographic one (see, e.g., [START_REF] Ruskey | Combinatorial generation[END_REF] for the definition of the reverse lexicographic order). Let be an integer between 0 and n, and r be an integer chosen uniformly at random in {0, . . . , C n, -1}. Equation (20) implies that a composition of n in parts is either a composition of (n -1) in parts whose first part has been increased by one, or it is a composition of (n -1) in ( -1) parts, and a new part equal to 1 is added at the beginning of the composition. In both cases, the first elements are all greater than the second elements according to the lexicographic order. The recurrence hypothesis ends the proof since the rank value r (or s in the second case) is adapted to each of the latter cases.

The number of arithmetic operations is immediate when all binomial coefficients are first memorised.

In Equation (19) the first term is much bigger than the second one, which is much bigger than the third one and so on. This approach, focusing first on the dominant terms is an adaptation to the idea underlying the Boustrophedonic order presented in [START_REF] Flajolet | A calculus for the random generation of labelled combinatorial structures[END_REF]. It allows to improve essentially the average complexity of the random sampling algorithm. In our case of strict monotonic Schröder trees since they do not follow a standard specification (cf. [START_REF] Flajolet | A calculus for the random generation of labelled combinatorial structures[END_REF] for details), the complexity gain is even better. The loop starting in line 6 aims at determining the interesting term Algorithm 3 Strict monotonic Schröder Tree Unranking 1: function UnrankTree(n, s) 2:

if n = 1 then 3:

return the tree reduced to a single leaf 4: := 1 5: r := s 6:

while r >= 0 do 7:

r := r -n-1 • g n- 8: := + 1 9: := -1 10: r := r + n-1 • g n- 11:

T :=UnrankTree(n -, r mod g n-) 12:

if n -≤ n/2 then 13:

C :=UnrankComposition(n, n -, r//g n-) 14: else 15:

C :=UnrankComposition(n, + 1, ( n-1 -1 -r)//g n-) 16:

C :=ComplementComposition(C) 17:

Substitute in T , using traversal T , some leaves according to C 18:

return the tree T

The sequences (g ) ≤n and ( !) ∈{1,...,n} have been pre-computed and stored. Line 13: The operation // is the Euclidean division. Recall a composition of (n, ) can be seen as a choice of -1 barriers inside a sequence of n bullets. The function ComplementComposition(n, , r) returns the complement of the barriers chosen in the r-th composition of (n, ).

in the sum (19), thus the size of the tree in the evolution process letting to build the tree of rank s and size n.

The traversal T used to substitute some leaves in line 13 determines partly the total order over the strict monotonic trees. Let α be an strict monotonic tree, and T a given traversal of all trees. We remark that there is a single evolution process building α (the construction is unambiguous). If α is built at the step , then we denote by α the single tree (built with -1 steps) and α the single composition such that at step replacing the leaves from α according to the composition α, using the traversal T , we obtain α.

Here we remark that the whole tree α is strongly dependent on the traversal of the leaves of α (while some leaves are substituted by an internal nodes attached to new leaves according to α). We define now how to compare strict monotonic trees (we use the analogous notations also for the latter for all trees). Definition 3.6.2. Let α and β be two trees. We define α < β if

• the size of α is smaller than the one of β, or • if both sizes are equal to n and if the size of α is strictly greater than the one of β or if both sizes of α and β are equal and the composition α is smaller than β, using the reverse lexicographic order over compositions.

Proposition 3.6.3. The order defined over strict monotonic trees is a total order.

The result is immediate since all possible cases according to the trees α and β for comparing them are explored. Theorem 3.6.4. The function UnrankTree is an unranking algorithm and calling it with the parameters n and a uniformly-sampled integer s in {0, . . . , g n -1} gives as output a uniform strict monotonic Schröder tree of size n .

The correctness of the algorithm follows directly from the total order over the trees and Equation (19).

Theorem 3.6.5. Once the pre-computations have been done, the function Un-rankTree needs O(n) arithmetic operations on big integers to construct a tree of size n.

Here the algorithm works with number of order g n , thus the big integers that are taken into account are encoded with O(n log n) bits.

Proof. We assume that all binomial coefficients (C n, ) 0≤ ≤n have been memorised and prove that, with this information stored, the complexity in terms of arithmetic operations (on big integers) is of order O(n). Note that if we only memorise the factorial numbers (i!) 0≤i≤n-1 the complexity is at most three times the complexity obtained when memorising the binomial coefficient and thus still of order O(n).

For all n ≥ 1, we denote by a n the number of arithmetic operations that come from the loop in line 7 and the calls in lines 11 and 12, when building all trees of size n (i.e. we sum the number needed for each r ∈ {0, . . . , C n, -1}). The exact value of arithmetic operations is a n + O(ng n ), because at each recursive call there is at most a constant number of operations that are not counted in a n . We first analyse a n : we have

a n = n-1 =1
n -1 (min( , n -1 -) -1 + 2 ) g n-+ a n-.

In fact, for the terms with index , we are interested in the trees α of size n such that their corresponding tree α is of size n -. Thus such trees α are counted by n-1 g n-. And for each of them the factor min( , n -1 -) -1 is the number of operations needed for the unranking of the composition (we use the symmetry in the binomial coefficients), the factor 2 is the number of multiplication and subtractions in the loop in line 7. Furthermore we have a 1 = 0. By taking an upper bound for the min function, we get that if ā1 = 0, and, for all n ≥ 2, We thus deduce ān ∼ 3ng n , which concludes the proof.

We now give some final remarks about this algorithm: In order to obtain a better time complexity for the implementation, we must use an array of pointers to the leaves of the tree under construction so that the tree traversal is efficient. At each step , a leaf stored in the array is replaced by n -+ 1 leaves that must be stored in the array. An efficient way consists in reusing the cell from the replaced leaf, and to append all other leaves at the end on the array. Thus, the most efficient traversal T of the leaves consists to the left right traversal of the array. But obviously this is not really a natural traversal for the tree. Nevertheless, in practice we use this efficient traversal T .

Figure 2 .

 2 Figure 2. Two increasing Schröder trees

iξ √ ln n n n+ 1 2 ,

 2 where we have used Stirling's formula. Note that lim n→∞ e 1-e iξ √ ln n = 1, and Γ(3) = 2, which implies that

  when n tends to infinity, we get E[C(3) n ] = ln n + O(1), as claimed.

Figure 4 .

 4 Figure 4. A size-8 example of the mapping M

Figure 5 .

 5 Figure 5. Two strict monotonic Schröder trees

Figure 6 .

 6 Figure 6. The constructive bijection between an ordered partition and a strict monotonic Schröder tree

Figure 7 .

 7 Figure 7. Distribution of (g n,k ) k for n ∈ {1, . . . , 7}

n

  -1 (3 g n-+ ān-) , then a n ≤ ān for all n ≥ 1. Using similar calculations as in the proof of Proposition 3.3.2, we obtain an equation satisfied by the Borel transform of the series associated to (ā n ): 2 B[ Ā(z)] = e z B[ Ā(z)] + 3ze z (B[G(z)]) .

Table 1 .

 1 Main analytic results of the paper: behaviour of the characteristics of a large typical tree of each of the two classes of labelled Schröder trees. The parameter n stands for the size of the trees (i.e. their number of leaves) and the results represent the average values of the parameters when n → +∞.

		Number of trees	Distinct labels Internal nodes Height
	Increasing Schröder trees	n!/2		n -ln n	n -ln n	Θ(ln n)
	Strict monotonic Schröder trees (n -1)!/(2 (ln 2)	n )	1 2 ln 2 n	n -ln 2 ln n

Table 2 .

 2 Summary of the main results on parameters of Increas-

			Variance	Limit law
	Internal nodes	n -ln n	ln n	Normal
	Degree of the root	2 e -3	0.4997	modified Poisson
	Number of binary nodes n -2 ln 2	4 ln n	Normal
	Number of ternary nodes	ln n
	Height of the tree	Θ (ln n)

ing Schröder trees 2.3. Exact enumeration and relationship with permutations. Let T denote the class of increasing Schröder trees. Using the evolution process, we get the following specification for T :

Table 3 .

 3 Values of t n,k (the number of increasing Schröder trees with n leaves and k internal nodes) for n ∈ {1, 2, . . . , 7}, and k ∈ {0, 1, . . . , n -1}.

Table 5 .

 5 Table 5 below). Finally, in Section 3.6, we conclude this part on weakly increasing Schröder trees by designing a uniform random sampler, which also gives an unranking algorithm. Summary of the main results on parameters of Strict monotonic Schröder trees 3.3. Enumeration and relationship with ordered Bell numbers. Using the iterative construction described above, we deduce the following specification for the class G of all strict monotonic Schröder trees:

		Mean	Var.	Limit law
	Internal nodes	n -ln 2 ln n
	Distinct labels	1 2 ln 2 n	(1-ln 2) (2 ln 2) 2 n	Normal
	Degree of the root	2 ln 2 + 1	2 ln 2 (1 -ln 2) (shifted) zero-truncated Poisson

Throughout this paper, a reference OEIS A• • • points to Sloane's Online Encyclopedia of Integer Sequences www.oeis.org.

For the composition unranking, note that it would suffice to look for the rank n -1 -r (instead of r) in order to get the lexicographic order.

Acknowledgement. The authors Hsien-Kuei Hwang for his help with the proof of Theorem 2.4.5 and for telling us about the links of this proof with [CHY00]. The authors thank the anonymous referees for their comments and suggested improvements. All these remarks have increased the quality of the paper.

This research is partially supported by the ANR project MetACOnc, ANR-15-CE40-0014. C. Mailler aknowledges EPSRC for support through the fellowship EP/R022186/1.

thus interested in the asymptotic behaviour of this ratio. Differentiating according to u and then substituting u by 1 in Equation ( 17) gives

because ∂G(z, u) ∂z

Since Equation ( 18) is similar to Equation (13), we apply the same method as in the proof of Proposition 3.3.2. We first derive

Then using Equation (13) we deduce

Furthermore since for any function

Then, since

where Li 2 is the dilogarithm function, defined in [FS09, section VI.8.]. Using its asymptotic development at 1, we get

By using classical transfer theorems we obtain the result by extracting the (n-1)-st coefficient of (B[H(z)]) and dividing it by the n-th coefficient of B[G(z)].

3.5.3. Quantitative characteristics of the root node. In this section, we look at the arity of the root in a typical strict monotonic Schröder tree. We denote by A G n the arity of the root in a tree picked uniformly at random among all strict monotonic Schröder trees of size n, and by p n its probability generating function: