Christian Capelle
email: capelle@lirmm.fr

Michel Habib
email: habib@lirmm.fr

Fabien De Montgolfier
email: montgolfier@lirmm.fr

Graph Decompositions and Factorizing Permutations

Keywords: Graph algorithms, graph decompositions, modular decomposition. 1 General decomposition framework

. Such a concept appears to play a central role in recent papers dealing with graph decomposition. It is applied here for modular decomposition of directed graphs, and we propose a simple linear algorithm that computes the whole decomposition tree when a factorizing permutation is provided.

. It also suggests many new decomposition algorithms for various notions of graph decompositions.

Definition 1 A permutation σ of the vertex set X is called a factorizing permutation for a given decomposition if every decomposition set is a factor of σ (i.e. its vertices appear consecutively in σ).

Such a permutation always exists as soon as the decomposition tree is provided, since it can be obtained by a simple preorder traversal of the tree. In this paper we consider the inverse problem.

Central Problem:

Data: a graph G = (X, E) and a factorizing permutation σ. Find: the decomposition tree (or the decomposition sets).

For a leading example of such a graph decomposition, one can take the modular decomposition, also called substitution decomposition, of graphs (an overview of this theory and its applications can be found in [START_REF] Möhring | Substitution decomposition for discrete structures and connections with combinatorial optimization[END_REF]). We present the basic concepts of this decomposition in the following section. In this article we deal with the general case of decomposition of directed graphs. Other examples are modules or blocks for inheritance acyclic directed graphs leading also to decomposition trees [START_REF] Huchard | Sur quelques questions algorithmiques de l'héritage multiple[END_REF][START_REF] Habib | A linear algorithm to decompose inheritance graphs into modules[END_REF][START_REF] Capelle | Décompositions de Graphes et Permutations Factorisantes[END_REF][START_REF] Capelle | Block decomposition of inheritance hierarchies[END_REF].

Clearly it could be hard to find a factorizing permutation, but in some cases a factorizing permutation is given for free. As for example as noticed by Hsu and Ma [START_REF] Hsu | Substitution decomposition on chordal graphs and applications[END_REF][START_REF] Hsu | A Simple Test for Interval Graphs[END_REF] in the case of chordal graphs, the cardinality lexicographic breadth first search of the graph yields a factorizing permutation for modular decomposition. Similarly, as noticed by Ducournau and Habib [START_REF] Ducournau | La multiplicité de l'héritage dans les langages à objets[END_REF], any depth-first greedy linear extension of an inheritance graph yields a factorizing permutation for the module decomposition of inheritance graphs.

Moreover Habib and Paul [START_REF] Habib | A simple linear time algorithm for cograph recognition[END_REF] have proposed a very simple O(n + m) algorithm to compute a factorizing permutation of a cograph. This work has been generalized to modular decomposition [START_REF] Habib | Partition Refinement techniques: an interesting toolkit[END_REF] with an O(n + m log n) algorithm for undirected graphs. These algorithms are easy to understand. As in the previous examples, they show the usefulness of dividing the calculation of the decomposition tree in two steps : calculation of the factorizing permutation, and calculation of the tree from this permutation.

Our algorithm deals with the modular decomposition of graphs (directed or not), but it can easily be adapted for the other decompositions mentioned above for inheritance graphs. It runs in O(n + m), and therefore is a common generalization of Hsu and Ma [START_REF] Hsu | Substitution decomposition on chordal graphs and applications[END_REF] and Habib et al. [START_REF] Habib | A linear algorithm to decompose inheritance graphs into modules[END_REF] which were relatively sophisticated ad hoc algorithms. Here we propose a simpler algorithm.

As a consequence, such an algorithm and the notion of factorizing permutation introduce some new perspectives for graph decomposition algorithms. Indeed, the decomposition process can be divided into two steps. First, find a way to produce a factorizing permutation, and then use the general algorithm defined here to compute the decomposition tree. Therefore one can focus on the search of such factorizing permutations.

Our central problem is connected to the search of the tree structure involved in factorizing permutation, and therefore a problem of interest by its own. One of the main results of this work is to propose a linear algorithm that applies both for directed or undirected graphs. Furthermore, other graph decompositions (for example those associated with edge-partitioning) can also be considered using this approach [START_REF] Capelle | Décompositions de Graphes et Permutations Factorisantes[END_REF].

Another example of this paradigm could be found in Hopcroft and Tarjan's pioneering work. Namely their algorithm [START_REF] Hopcroft | Dividing a Graph into Triconnected Components[END_REF] for triconnected graph recognition uses two depth-first searches and collect triconnected components by "factors". This paper is organized as follows. The next section presents main results about Modular Decomposition. In Section 3 we introduce a new object, the fracture tree, and present its properties. In Section 4 we propose a simple algorithm leading from the fracture tree to the modular decomposition tree, and its linearity is proven in Section 5. In Section 6 (Conclusion) several directions for further research and a conjecture are presented.

Modular decomposition

The modular decomposition (also called substitution decomposition) is very important since its study plays a central role in the area of partial orders, comparability graphs, and transitive orientations [START_REF] Golumbic | Algorithmic graph theory and perfect graphs[END_REF]. Here we focus on decomposition sets that are called strong modules, which are defined as follows:

Definition 2 Two set E and F overlap if E ∩ F = / 0, E \ F = / 0, and F \ E = / 0. Let G = (X, E) be a graph
with n vertices and m arcs. The outer neighborhood of v is written Γ + (v) and its inner neighborhood is

Γ -(v). A subset M of X is a module if ∀v ∈ X \ M, M does not overlap neither Γ + (v) nor Γ -(v).
Every set with 1 or n vertices is a trivial module. A graph with no non-trivial module is prime. A strong module is a module that does not overlap any other module. They are the decomposition sets of the modular decomposition. In the following a factorizing permutation is considered with respect to the strong modules. Notice that a given graph may have many factorizing permutations, up to n! for prime graphs.

The Modular decomposition tree of a graph G is the transitive reduction of the inclusion order of the strong modules of G.

Each node N (N ⊂ X is the strong module represented by this node) of the decomposition tree is labeled by the quotient graph of G N according to its children. Such a quotient graph is called the representative graph of the node N.

Four mutually exclusive cases can be distinguished :

• A node is labeled series if its representative graph is a clique.

• A node is labeled parallel if its representative graph is a stable set.

• A node is labeled order if its representative graph is a total ordering.

• If no one of the previous cases apply, a node N is labelled prime. The representative graph of N is a prime graph.

Let us recall the well-known decomposition theorem (for example see [START_REF] Möhring | Substitution decomposition for discrete structures and connections with combinatorial optimization[END_REF])

Theorem 1 (Modular Decomposition) Let G = (X, E) be a digraph such that |X| 2. One of the four following claims is true:

1. G is not connected and it can be decomposed according to its connected components. The corresponding node in T G will be a parallel node.

2. G is not connected and G can be decomposed according to the connected components of G. The corresponding node in T G will be a series node.

3. G can be decomposed in strong modules such that the quotient graph is a non-trivial total ordering. The corresponding node in T G will be an order node.

4. Else, the maximal non-trivial strong modules of G do not overlap. The quotient graph is prime and the corresponding node in T G will be a prime node.

Even though a given graph could have exponentially many modules, it has O(n) strong modules. Therefore an algorithm has to deal only with the good ones, the strong modules.

Let us denote by LCA(x, y) the Least Common Ancestor of the vertices x and y in the modular decomposition tree. The following property trivially holds: [START_REF] Cournier | A new linear algorithm for Modular Decomposition[END_REF][START_REF] Mcconnell | Modular decomposition and transitive orientation[END_REF][START_REF] Dahlhaus | Efficient and Practical Modular Decomposition[END_REF], they remain rather hard to implement, and it is still worthwhile to search for simplifications. The result presented here can be understood as a step forward in this direction. Moreover, existing algorithms deal only with undirected graphs, while ours deals with both directed and undirected graphs. The next section presents an interesting decomposition tool; namely the fracture tree.

Property 1 LCA(x,
3 The Fracture Tree

Notations and definitions

Notations In the following, G = (X, E) is a graph (directed or not) with n vertices and m arcs, and σ(G) (or σ if unambiguous) a factorizing permutation of G. The successor of x in σ is x ′ and its predecessor is ′ x. If σ -1 (x) < σ -1 (y) then x is to the left of y. If G is undirected, it is treated as a directed symmetric graph, so the same notations are used for both cases.

Definition 3 Given a set S ⊂ X of vertices, a vertex x is a cutter of S if S is not a module of the induced graph G(S ∪ {x}). This means that x / ∈ S and that at least two vertices of S have different adjacency relations with x. The set of cutters of S is denoted by Cut(S).

Of course M is a module if and only if Cut(M) = / 0. Furthermore we have Property 2 let M be a module and S a subset of M, then Cut(S) ⊂ M.

Since σ is supposed to be a factorizing permutation, the strong modules are factors of it, so the cutters "gather together" in the vicinity of any factor S, in a manner shown below. In order to reach linear time for our algorithm, the only subsets we deal with are the pairs, made up with two consecutive vertices of σ. Fortunately there is no need of computing the set of all cutters of a given pair: it is enough to consider the furthest ones. Definition 4 Let P = {x, x ′ } be a pair of vertices. The first cutter of P, denoted by f c(P), is the leftmost vertex of Cut(P) (if any) appearing in the factor σ(1) . . . x. If such a vertex exists, the left fracture of P, denoted by L f (P), is the factor f c(P) . . . x. The last cutter of P, lc(P), is the rightmost vertex of Cut(P) appearing in x ′ . . . σ(n) and the right fracture, R f (P), is the factor x ′ . . . lc(P).

Parenthesizing

Since a fracture is a factor of σ, it can be enclosed into parentheses. The parenthesized factorizing permutation σ is the word where such parentheses have been inserted: an opening parenthesis to the left of f c({x, x ′ }) and a closing one to the right of x mark the left fracture, and likewise for the right fracture. If many opening and closing parentheses have to be written between two consecutive vertices, all the closing ones must be inserted before the first opening one. Finally the permutation itself is enclosed with two extra parentheses. σ = ( We claim that σ is a well-formed word of parentheses, also called a Dyck word, because an equal number of opening and closing parentheses are inserted, and furthermore the opening parenthesis of a fracture appears always before its closing one.

Fractures have the following property:

Property 3 A module and a fracture can not overlap.

Proof: Let M be a strong module, F a fracture (left or right) and P = {x, x ′ } the pair of vertices that create F. By Property 2, if P ⊂ M then Cut(P) ⊂ M, so any fracture of P is a factor of M. If x ∈ M and x ′ / ∈ M, then the right fracture of P does not intersect M, and its left one has the same right boundary as M and thus can not overlap it. If x / ∈ M and x ′ ∈ M, the case is symmetric. At least if neither x nor x ′ belongs to M, since M is a module either all or none of its vertices cuts P, and since M is a factor of σ it can not overlap a fracture of P. ✷

Lemma 1 Let M be a strong module of G and σ a parenthesized factorizing permutation of G. σ[M] is a

Dyck subword of σ.

Proof: Let us color in red the fracture parentheses of the inner pairs of M. Property 2 claims those fractures to be factors of M. Furthermore the right fracture of the pair formed with the first vertex of M and its predecessor, and the left fracture of the pair formed with the last vertex of M and its successor, are also colored in red only if those fractures are factors of M. All the remaining parentheses are left in black. The corresponding fractures have at least one vertex out of M, and Property 3 ensures that they do not overlap M, so the black parentheses are out of M. We can swap red and black parentheses on the boundaries of M so that red parentheses are a factor of σ. It made up with pairs of fracture parentheses, so it is a Dyck word. ✷

The fracture tree

Given a word of parentheses, a natural idea is to construct the associated tree, using a simple pushdown automaton. Let us call fracture tree FT (σ) the tree of the parenthesized factorizing permutation σ. Its leaves are the vertices of G, which are the letters of σ enclosed in the parenthesizing.

The two extra parentheses correspond to the root of the decomposition tree, and the relationship between σ and the fracture tree is then straightforward. The tree can be build from left to right using the following automaton that scans the Dyck word from left to right, start from a special vertex CurrentNode = Root and applying the following rules when a symbol (, ) or a letter x is read :

( : add a new vertex child N to the current node, CurrentNode = N;
) : backtrack to the father of CurrentNode, CurrentNode = Father(CurrentNode);

x : add a leaf to CurrentNode labeled with x.

Clearly the Dyck word σ corresponds to a depth-first search of the fracture tree FT (σ(G)). Our goal is to cast this fracture tree (depending on G and on σ) into the modular decomposition tree (depending only on G). It will be shown, by the following properties, that indeed the fracture tree is a good approximation of the modular decomposition tree.

A leaf of the fracture tree of G is identified with the corresponding vertex of x, and a node of the fracture tree is identified with the subset of X rooted by this node, like in a modular decomposition tree.

By definition, the nodes of the decomposition tree represent exactly the strong modules of the graph. For the fracture tree only weaker properties hold, as explained now :

Lemma 2 Let M be a strong module of G, and G ′ the graph obtained from G by contracting the module M into a new vertex x. For any factorizing permutation σ of G, FT (σ(G)) can be obtained from FT (σ[G ′ ]) by replacing the leaf x by a forest (each connected component of that forest being connected to the father of x in FT (σ[G ′ ])).

Proof: Using Lemma 1, vertices of M appear consecutively in σ and therefore σ[G ′ ] is well-defined, when replacing the vertices of M by a single vertex x.

Let us apply on σ[G ′ ] the automaton previously introduced. It produces FT (σ[G ′ ]) in which x is a leaf. Applying the same automaton on σ gives FT (σ(G)). When the automaton deals with the Dyck word that ) it suffices to replace x by F. ✷ Therefore we reach here the main technical point of this approach: a strong module does not always correspond to a proper subtree of the fracture tree. It has to be studied in full details, and next theorem describes some good situations. Definition 5 Given a Dyck word, the parentheses height at some letter v is the number of opening parentheses before v minus the number of closing parentheses before v.

Theorem 2 Let G be a graph, σ a factorizing permutation of G, and N ′ a node of the modular decomposition tree of G, representing a strong module M. If N ′ is a prime node, or if the father of N ′ is a series, parallel or order node, then there is a node N in the fracture tree of σ that represents M.

Proof: Since the fracture tree is built using the automaton, the vertices of G represented by a node N of the fracture tree are exactly a Dyck subword of σ enclosed by a pair of parentheses (including the parentheses associated with the link from N to Father(N)). Using Lemma 2, it just remains to prove that there is a pair of parentheses enclosing the module, so that its vertices are children of only one node and form a tree. The proof is in two parts: the first deals with series, parallel or order nodes children of series, parallel or order nodes, and the second deals with prime nodes.

Let us start with the easy case. Let N be a parallel, series or order node of the modular decomposition tree and F its parallel, series or order father. First, due to Theorem 1, a series node generates no series children. Similarly a parallel (resp. order) node can not be child of a parallel (resp. order) node. So F and N have different types. Let α be the left end of N in σ and β its right end. Since F has at least two children, the predecessor ′ α of α or the successor β ′ of β (or both) exists and descends from F. Suppose ′ α does. We have LCA(α, β) = N and LCA( ′ α, α) = F. Let us denote by |(x, y)| the number of arcs between x and y, which can be 0, 1 or 2. By Property 1, |( ′ α,β)| = |(α, β)|, so β cuts the pair { ′ α, α}. No child z of F to the right of β can cut this pair because its least common ancestor with both ′ α and α is F so

|(z, ′ α)| = |(z, α)|.
A vertex out of F can not cut the pair either, because F is a module. β is thus the last cutter of { ′ α, α} and the right fracture of this pair is α . . . β. Since N is well parenthesized by itself (by the Lemma 1), this fracture corresponds to a node in the fracture tree. Notice that if ′ α does not exist or is not a child of F, then β ′ does, and then N is the left fracture of {β, β ′ }. This demonstrates the theorem in the case of series, parallel or order nodes.

α ' α F N β
If N is a prime node of the modular decomposition tree, the case is a little more complex. We will prove that whatever the type of his father F, N is a node of the fracture tree. To prove that, we just have to demonstrate that given a prime graph and a parenthesized factorizing permutation of its vertices, the automaton produces a tree and not a forest. The proof uses an induction on the number k of nodes (non leaves) which are children of N.

For k = 0 (i.e. all children of N are leaves of the modular decomposition tree), let us suppose that in σ[N] the parentheses height is null between two consecutive vertices x and x ′ . σ can be split into two subwords σ(1) . . . x and x ′ . . . σ(h). Clearly, xx ′ can not be a factor of any fracture, because in σ(1) . . . x there is as many opening parentheses as closing ones. Consider the link between x and x ′ . It can be formed with no arc, one right arc (from x to x ′ ), one left arc or two arcs. Let T be its type. Let us now consider the other links between the two factors. The link between ′ x (if ′ x exists) and x ′ is also T , or else x ′ would cut the pair { ′ x, x} and xx ′ would be factor of its right fracture, bringing the parentheses height at more than one: contradiction. By iterating this until the first vertex σ(1), all links between a vertex of σ(1) . . . x and x ′ are also T . For the same reason, all links between x and a vertex of x ′ . . . σ(h) are T . Now, consider all links between ′ x (if it exists) and x ′ . . . σ(h). They are T , because if there exists y to the right of x ′ such that ( ′ x, y) = T , we know that (x, y) = T so y cuts { ′ x, x} and so xx ′ ⊂ L f ({ ′ x, x}). A similar argument applies with ′′ x and x ′′ and so on, hence all links between vertices from σ(1) . . . x and from x ′ . . . σ(h) are T . So σ(1) . . . x and x ′ . . . σ(h) are two modules. At least one of them is not trivial, because N has at least three vertices, so N can not be a prime graph. In conclusion, the parentheses height can not be null inside the permutation, and therefore σ[N] is enclosed by two parentheses and N is a node of the fracture tree.

Suppose now that N has k ≥ 1 nodes for children. Let N ′ be one of these nodes, and consider the graph G ′ in which N ′ is contracted to a single vertex. In the modular decomposition tree of G ′ the node N has k -1 children which are nodes, and therefore we may apply the induction on G ′ . Therefore N is a node of the fracture tree of G ′ . Using Lemma 2, we obtain that N is also a node of the fracture tree of G, which demonstrates the theorem for prime nodes. ✷ Theorem 2 does not cover all cases, in particular: children of a prime node which are series, parallel or order (in the modular decomposition tree) may be not present in the fracture tree. We know by the Lemma 2 that they necessarily appear as consecutive children of one node of the fracture tree. We call merging such a case. For instance, in our example Figure 4, the order module {6, 7, 8} is merged with the prime module {6, . . . 14}. And there is no node of the fracture tree representing it.

At this point, we know that there are nodes in the fracture tree representing (almost all) strong modules. Fortunately any vertex of G appears exactly once as a leaf of the fracture tree, and the only leaves of the fracture tree are the vertices of G. So, a node represents the same set of vertices as another if and only if they form a chain of nodes having only one child, excepted the last.

We consider that the true representative of a module is the last node of such a chain, and we say it is a genuine node. The other nodes (those with only one child, or representing a set of vertices other than a module) are said to be dummies.

Furthermore, it is important to notice that the inclusion of modules (as in the modular decomposition) is preserved in the fracture tree: this is given by Lemma 2. This is why we can claim that the fracture tree is a good approximation of the modular decomposition tree.

So, given the fracture tree, in order to get the modular decomposition tree we have to :

1. identify the genuine nodes and their type, 2. suppress the remaining (dummy) nodes, 3. detect merged strong modules and fix them, 4. suppress the weak modules.

Efficient solutions for all of these four steps are detailed in the next section.

Getting the modular decomposition tree

For sake of simplicity let us divide the main algorithm into six successive linear scans. The first one writes the fracture parenthesizing, using the automaton, and the second one reads this parenthesizing and builds the fracture tree. Let us now focus here on the remaining successive scans that transform the fracture tree into the modular decomposition tree.

Third scan: Module recognition

Obviously M is a module if and only if Cut(M) = / 0. If S is a factor of σ then we have

x ∈ Cut(S) ⇒ ∃{y, y ′ } ⊂ S such that x ∈ Cut({y, y ′ })
The proof is trivial: if x ∈ Cut(S) then x cuts some pair {u, v} ∈ M. yy ′ is thus a factor of u . . . v. We use the converse: if x does not cut any pair of consecutive vertices of S, then x does not cut S. This leads us to the following property:

Property 4 Let N be a node of the fracture tree. If all cutters of all consecutive pairs of N belong to N then, N represents a module.

Let N be the scanned node and C 1 . . .C k its k children (ordered with respect to σ). Let us call f v(C i ) the first vertex of C i and lv(C i ) its last vertex, so that C i is the factor f v(C i ) . . . lv(C i ) of σ. Its cutters can be computed using Fig. 6: The fracture tree after the third scan. Genuine nodes are circled, while known dummies are crossed. Inside a node is written its first and last cutters.

f c(N) = min f v(N), min {x,x ′ }⊂N f c({x, x ′ }) 1
lc(N) = max lv(N), max {x,x ′ }⊂N lc({x, x ′ })
where min (resp. max) finds the leftmost (resp. rightmost) vertex in σ.

Notice that the pairs included in a C i have already been scanned, and in fact there is no need to scan them again. The "new" pairs are only those for which N is the least common ancestor, i.e.

{lv(C

i ), f v(C i+1 )} i∈[1,k-1] .
Now we have the following efficient recurrences:

f c(N) = min f v(N), k-1 min i=1 f c {lv(C i ), f v(C i+1 )} , k min i=1 f c C i (1) lc(N) = max lv(N), k-1 max i=1 lc {lv(C i ), f v(C i+1 )} , k max i=1 lc C i (2)
Property 5 All the genuine nodes of the fracture tree can be detected in O(n).

Proof: Suppose we get in O(1) the first and last cutter of a pair (this is realistic, because they are calculated during the parenthesizing scan, and can be stored in an array). With the formulae (1) and ( 2), a pair may be checked only if the current node is its least common ancestor, and a node only if the current node is its father. So a bottom-up parsing of the fracture tree establishes for any node its first and last cutters and vertices, and then if it is a module, in O(n) for the whole tree. This is the third scan of our algorithm. ✷

Fourth scan: dummy nodes deletion

Since we know which nodes represent a module and which do not, we can now delete all the dummy nodes (either the nodes with only one child or the nodes that do not represent a module). Notice that by deletion we do not mean that we prune the tree, but that the children of the erased node become children of their former grandfather. The whole process takes O(n), and the new fracture tree produced contains only genuine nodes. It should be noticed also that this step can be very easily merged with the previous one. In fact, up to now among the genuine nodes found in the previous scan, we could have some weak modules, that must be removed from the tree. That is the purpose of the last scan.

Fifth scan: recovering the merged modules

Given a module M and its children C 1 . . .C k in the fracture tree, all supposed to be modules at this point, we can focus on its representative graph G M . Notice that the representative graphs of all the nodes of the tree can be computed in O(n + m). In the following, σ[G M ] denotes the factorizing permutation of G M compatible with σ(G), i.e. the vertices x 1 . . . x k of G M appear in the same order as C 1 . . .C k in σ(G).

If M is an series, order or parallel node, by the Theorem 2 we know that all its children in the modular decomposition tree are represented in the fracture tree, and thus are exactly C 1 . . .C k . If M is a series (resp. order, parallel) node then G M is a clique (resp. total ordering, stable set). This can be checked in O(k): we make an array A M with the outer degree of each node. If A M = [0, . . . 0] then M is parallel, and if

A M = [k -1, . . . k -1]
then M is series. Obviously in those cases, it is not worthwhile to store G M and A M .

If A M is a permutation of {0, . . . k -1} and if all vertices of G M have the same degree (inter plus outer) then M is an order node. The permutation A M -1 gives us the total ordering represented by N: for instance A M -1 (0) is its smallest element. G M can be deleted, but A M -1 has to be computed and kept. If none of those cases apply, then M is a prime node. A M can be deleted, but G M must be kept, else information about the graph structure will be lost. We must be careful, because the C i 's are not necessary the children of M in the modular decomposition tree: indeed merging of series, parallel or order nodes can happen. Fortunately, since all the children of those merged node are represented, we know that the C i 's are either children (in the modular decomposition tree) of M or of a merged non-prime node. The nodes are ordered according to σ, so that all the children of a merged node appear consecutively. We can detect all merging by searching blocks of consecutive twins. Of course the relation "be a true (resp. false) twin of" is symmetric and transitive. We shall consider the transitive closure of the "be an half twin of" relation, thus we have three equivalences relations.

Theorem 3

The merged series (resp. parallel, order) nodes are exactly the non-trivial equivalence classes of the twin relations, corresponding to blocks of consecutive true (resp. false,half) twins of maximal length.

Proof: Let P be a prime node of the modular decomposition tree and M a child of P in this tree, that merged with P in the fracture tree. Since M is a strong module, it is a factor x l . . . x r (l < r) of the factorizing permutation σ[G P ]. If M is series or parallel, it is obvious that ∀i, j ∈ [l, r], x i and x j are twins (true or f alse)

In fact (3) holds also if M is an order module. Let us prove it. Suppose there are two vertices x i and x j of x l . . . x r which are not twins. Necessarily there exist two consecutive non-twins vertices x k and x ′ k between x i and x j . Since M is a module, the cutters of {x k , x ′ k } belong to M. So there is a fracture containing some (at least two, but not all) consecutive vertices of x l . . . x r . The automaton that has produced the fracture tree would have created one node for this fracture, a contradiction. Thus all consecutive vertices of a merged node are twins in the representative graph G P . A vertex x of a merged module M can not be a twin of y / ∈ M, so merged modules are indeed equivalence classes of the transitive closure of the twin relation. Since those classes are by construction factors of σ(G P ), this demonstrates the theorem. ✷ It should be noticed that in the merged order case, the ordering of the vertices in σ is exactly the ordering induced by the order node, otherwise there would exist some cutter.

We know without further calculation the cutters of a pair:

if f c({lv(C i ), f v(C i+1 )}) ∈ C j , j < i in G, then f c({x i , x ′ i }) = x j in G M , and if f c({lv(C i ), f v(C i+1 )}) ∈ C i in G then {x i , x ′ i } has no first cutter in G M .
No other case is possible. Let us now consider how twins can be detected: x i and x ′ i are twins if and only if the first (resp. last) cutter of {lv(C i ), f v(C i+1 )} does not exist or is to the right (resp. left) of f v(C i ) (resp. lv(C i+1 ) ). Thus a pair {x, x ′ } of σ(G) is used only once in the search of twins, in the node LCA(x, x ′ ), making this search O(n) for the whole tree.

Last scan: weak module deletion

At this point we know that all the strong modules are represented in our tree (which is now very near to the modular decomposition tree), and that all its nodes are modules. It only remains to determine the genuine nodes which do not correspond to strong modules of the original graph. Since a node of the fracture tree always represents a factor of σ, the weak modules factor of σ(G) can only be factors of series, parallel or order nodes. And we know that those kind of nodes can not have children with the same type as them. Thus we detect a weak module node because we see a series node being a child of a series node (it is the same for parallel or order nodes). They were the last dummies, and they are deleted from the tree: the tree we have now is the modular decomposition tree. In our example, the order module {4, 5} is weak and must be merged with the (strong) module {3, 4, 5}.

In fact, the only weak module nodes are the orders. In a series or parallel module, all the vertices are twin in the representative graph, so its parenthesized factorizing permutation has in fact no parentheses.

Complexity

Now we can state our main result: Theorem 4 Our algorithm computes the modular decomposition tree of any directed graph, if a factorizing permutation is provided, in O(n + m) time and space complexity.

Proof:

1. The first scan, which establishes the parenthesizing of a given factorizing permutation, takes O(n + m) time, because for the n -1 pairs of vertices we search the first and last cutter in the adjacency of their two vertices, so the adjacency of a vertex is examined at most twice. The output of this scan is a permutation with n vertices and at most 4n -4 parentheses, Thus the whole complexity of the proposed algorithm is in O(n + m). ✷

Conclusions

A consequence of our main result is that the modular decomposition of graphs and the computation of a factorizing permutation with respect to the strong modules are really equivalent problems. It was know that these two problems have the same theoretical time complexity. But here we have proposed an algorithm which is not only theoretically interesting but really efficient.

This allows some new perspectives about using a systematic search of factorizing permutations in many graph decomposition contexts. See for example the decomposition of inheritance graphs as used in Object Oriented Programming and Knowledge Representation Systems. The block decomposition of these graphs is computed using a two phases algorithm: the first one computes a factorizing permutation, and the second one extracts the strong blocks from it [START_REF] Capelle | Décompositions de Graphes et Permutations Factorisantes[END_REF].

We have pointed out that the factorizing permutations play a central role in the decomposition theory. Another direction worthwhile investigating is the question of which invariants can be directly computed out of factorizing permutations. It remains also to consider new classes of graphs for which a factorizing permutation is easy to compute. Generalizations of chordal graphs (HHD-free graphs for example) are natural candidates.

And we may end with a nice problem, which is a enlightened by this work and some recent linear modular decomposition algorithms [START_REF] Cournier | A new linear algorithm for Modular Decomposition[END_REF][START_REF] Mcconnell | Modular decomposition and transitive orientation[END_REF][START_REF] Dahlhaus | Efficient and Practical Modular Decomposition[END_REF], which consists in proving the following conjecture.

Conjecture:

There exists a simple way to compute a factorizing permutation for the modular decomposition of any undirected graph.

Up to now only an O(n + m log n) direct algorithm is known to compute a factorizing permutation for any undirected graphs [START_REF] Habib | Partition Refinement techniques: an interesting toolkit[END_REF]. For cographs it has been recently improved down to linear-time [START_REF] Habib | A simple linear time algorithm for cograph recognition[END_REF].

Another direction of research could be to generalize the notion of factorization permutation to other decompositions such as the split decomposition of graphs [START_REF] Cunningham | Decomposition of directed graphs[END_REF][START_REF] Ma | An O(n 2 ) algorithm for undirected split decomposition[END_REF]. This would be very interesting because in such a decomposition the decomposition tree is quite different.

Fig. 1 :Fig. 2 :

 12 Fig. 1: A directed graph

Fig. 3 :

 3 Fig.3: Parenthesized factorizing permutation of the graph Figure1, with σ = 1, . . . , 14. The exponent written upon a parenthesis just denotes the first vertex of the pair for which this parenthesis marks the fracture.

Fig. 4 :

 4 Fig. 4: Fracture tree of our example

Fig. 5 :

 5 Fig. 5: Substitution in a graph and in a parenthesized factorizing permutation corresponds to M it produces a forest F. And to obtain FT (σ(G)) from FT (σ[G ′ ]) it suffices to replace x by F.✷ Therefore we reach here the main technical point of this approach: a strong module does not always correspond to a proper subtree of the fracture tree. It has to be studied in full details, and next theorem describes some good situations.

Fig. 7 :

 7 Fig. 7:The fracture tree during the fifth scan. Only genuine nodes remain. Inside a node is written its representative graph, with the twins in black.

2 . 6 .

 26 The second scan, which reads the O(n)-sized parenthesizing and builds the fracture tree with at most 2n -2 nodes, takes O(n) space and time since it uses a simple automaton, 3. The third scan (modules recognition) takes O(n) time complexity (Property 5), 4. The fourth scan (dummy nodes deletion) takes O(n) time, since it uses a breadth-first search, and suppress in O(1) (by an easy merging of the lists of children) the dummy nodes, 5. The fifth scan takes O(n + m) time and space complexity for quotienting all subgraphs. Then, the module typing and the search of twins (knowing the cutters) is O(n), The sixth and last scan takes O(n) for deleting weak modules.

Definition 6

 6 Two vertices are twins if no vertex cuts them. x and y are true twins if (x, y) ∈ E and (y, x) ∈ E, false twins if (x, y) / ∈ E and (y, x) / ∈ E and half twins if either (x, y) ∈ E or (y, x) ∈ E.

Acknowledgements

The authors wish to thank the referees for their valuables remarks and suggestions.


Guy Louchard
email: louchard@ulb.ac.be

Helmut Prodinger

Probabilistic Analysis of Carlitz Compositions

Keywords: Carlitz compositions, Smirnov words, polyominoes, central limit theorems, local limit theorems, large deviation theorems, Markov chains, Brownian motion

Using generating functions and limit theorems, we obtain a stochastic description of Carlitz compositions of large integer n (i.e. compositions two successive parts of which are different). We analyze: the number M of parts, the number of compositions T (m, n) with m parts, the distribution of the last part size, the correlation between two successive parts, leading to a Markov chain. We describe also the associated processes and the limiting trajectories, the width and thickness of a composition. We finally present a typical simulation. The limiting processes are characterized by Brownian Motion and some discrete distributions.

Introduction

A Carlitz composition of n is a composition two successive parts of which are different (see Carlitz [START_REF] Carlitz | Restricted compositions[END_REF]). T (m, n) will denote the number of Carlitz compositions of n with m parts. All T (•, n) compositions will be considered as equiprobable. We call M the random variable (R.V.): number of parts. In [START_REF] Knopfmacher | On Carlitz compositions[END_REF], Knopfmacher and Prodinger found asymptotic values for: T (•, n), the mean number of parts E[M], the number of general compositions with exactly m equal adjacent parts, the mean of equal adjacent parts number, the mean of the largest part. They also analyze Carlitz composition with zeros and with some restrictions. Carlitz compositions can also be studied using Smirnov words; see [START_REF] Goulden | Combinatorial enumeration[END_REF] and [START_REF] Knopfmacher | On Carlitz compositions[END_REF].

In [START_REF] Louchard | Probabilistic analysis of some (un)directed animals[END_REF], [START_REF] Louchard | Probabilistic analysis of column-convex and directed diagonally-convex animals[END_REF], and [START_REF] Louchard | Probabilistic analysis of column-convex and directed diagonally-convex animals. II: Trajectories and shapes[END_REF], Louchard analyzes some polyominoes (or animals) such as: directed columnconvex animals, column-convex animals and directed diagonally convex animals. He obtained asymptotic distributions for M and for the size of columns. He also derived limiting processes for typical trajectories and shapes. Related material can be found in [START_REF] Bender | Convex n-ominoes[END_REF].

In the present paper, we consider Carlitz compositions as particular polyominoes and obtain a stochastic description of their behaviour for large n. We analyze the number M of parts, the number of composition T (m, n) with m parts, the distribution of the last part size, the correlation between two successive parts, leading to a Markov chain. We consider also the associated processes and the limiting trajectories and shapes (which show a "filament silhouette"), the width and the thickness (part size) of a composition. We present an algorithm for efficient large Carlitz composition simulation.

We use such tools as asymptotic analysis of generating functions (based on their singularities) leading to central limit, local limit and large deviation theorems. The limiting processes are characterized by Brownian Motion, the extreme value-distribution and some discrete distributions.

Our results can be summarized as follows: the number M of parts and T (m, n) are analyzed in Theorems 2.1, 2.2, 2.3. The distribution of the last part size is given in Theorem 2.4. The distribution of intermediate part size and the correlation between two successive parts are considered in Theorems 2.5, 2.6 (including the Markov chain description). The associated processes are discussed in Theorems 2.7, 2.8, 2.9. The simulation algorithm is given in Sec. 3.1 and the thickness is considered in Theorem 3.1, 3.2, and 3.3.

The paper is organized as follows: Section 2 gives the probabilistic analysis of Carlitz compositions, Section 3 analyzes the simulation algorithm and the composition thickness, Section 4 concludes the paper. An Appendix provides some identities we need in the paper. Several notations will appear in the sequel. Let us summarize some of them:

• " D ∼" means "convergence in distribution."

• N (µ,V ) is the Normal (or Gaussian) random variable with mean µ and variance V .

• "∼" means "asymptotic to" (n or m → ∞).

• T (m, n) is the number of Carlitz compositions of n with m parts.

• "Vertical distribution" means "Expression for T (m, n) for given number of parts m."

• "Horizontal distribution" means "distribution of the number of parts M for given n."

• ⇒ n→∞ : weak convergence of random functions in the space of all right continuous functions having left limits with values in R 2 and endowed with the Skorohod metric d 0 (see Billingsley [4] Chap. III).

• VAR(T ) := Variance(T ).

• B(t) := the classical Brownian Motion.

Probabilistic analysis of Carlitz Compositions

In this section, we first analyze the number M of parts. Then we obtain the distribution of the last part size (LP). Next we compute the correlation between two successive intermediate parts, leading to a Markov chain. Finally, we consider the associated processes and limiting trajectories.

Number of parts

Let T (m, n) be the number of Carlitz Compositions (CC) of n with m parts and let f m (i, n) be the number of CC with the same characteristics and last part of size i. We shall mark n by z, m by w and i by θ. The corresponding generating functions (GF) satisfy

f j (θ, z) = f j-1 (1, z) zθ 1-zθ -f j-1 (zθ, z), j ≥ 2 and f 1 = zθ 1-zθ .
(The first part can be of any size.) Hence φ(w, θ, z) Iterating, this leads to

:= ∑ ∞ 1 w j f j (θ, z) satisfies φ(w, θ, z) = wzθ 1 -zθ + wzθ 1 -zθ φ(w, 1, z) -wφ(w, zθ, z).
φ = A 1 (w, θ, z)[1 + D 1 ], (1)
where

D 1 := φ(w, 1, z) = A 1 (w, 1, z)/[1 -A 1 (w, 1, z)], A 1 (w, θ, z) = ∞ ∑ j=1 (-1) j+1 z j θw j 1 -z j θ . (2)
Notice that 1

+ D 1 = 1/h, (3)
where h(w, z) := 1 -A 1 (w, 1, z). This generating function was already known to Carlitz [START_REF] Carlitz | Restricted compositions[END_REF].

First set θ = 1. When w = 1 we get the GF of the total number

T (•, n) of CC (n) (CC of n):
this is given by D 1 (1, z). The dominant singularity of D 1 is given by the root z * (with smallest module) of h(1, z), i.e. z * = •571349793158088 . . . h(1, z) is analytic for |z| < 1. To be sure that z * is the dominant singularity, we use the principle of the argument of Henrici [START_REF] Henrici | Applied and Computational Complex Analysis[END_REF]: the number of solutions of the equation f (z) = 0 that lie inside a simple closed curve Γ, with f (z) analytic inside and on Γ, is equal to the variation of the argument of f (z) along Γ, a quantity also equal to the winding number of the transformed curve f (Γ) around the origin. The argument was used in Flajolet and Prodinger [START_REF] Flajolet | Level number sequences for trees[END_REF] in a similar situation. Figure 1 represents [ℜ(h), ℑ(h)] for z = .60 exp(it), t = 0..2π, where h is converted into a series up to O(z 60 ). The winding number is 1, so that h has only one root z * for |z| < .60.

By singularity analysis, T (•, n) is asymptotically given by

T (•, n) ∼ - 1 z * h z (1, z * ) 1 z * n = C 1 /z * n , n → ∞, (4)
with

C 1 = 1 z * A 1,z (1,1,z * ) = •4563634741 • • • (F z
means differentiation w.r.t. z and similarly for w). Indeed A 1 (1, 1, z * ) ≡ 1. For w ∈ [0, 1], h is analytic for |z| < 1 and for w ∈ [1, ∞], h is analytic for |z| < 1/w. Let us remark that the numerical computation of h is delicate: this is an alternating series. So it is better to use (A1). This leads to

h(w, z) = 1 -∑ k≥1 wz k 1 + wz k .
The same technique has been used for A 1 (w, θ, z) and h w , h z . Let us return to our asymptotic analysis. By Bender's Theorems 1,3 and (3.2) in [START_REF] Bender | Central and local limit theorems applied to asymptotics enumeration[END_REF] we can get more: we obtain the asymptotic distribution of the number of parts M in CC(n), where we consider all possible T (•, n) as equiprobable. Let

r 1 := -h w /h z , r 2 := -(r 2 1 h zz + 2r 1 h zw + h w + h ww )/h z .
Setting w = 1, z = z * , we derive

µ 1 := -r 1 /z * = •3506012746 • • • , σ 2 1 := µ 2 1 -r 2 /z * = •1339166786 • • •
Then Bender's results lead to the following theorem.

Theorem 2.1 (Horizontal Distribution in CC(n)). The number M of parts in a CC(n) of large given n is asymptotically Gaussian

: M -nµ 1 √ nσ 1 D ∼ N (0, 1), n → ∞.
Also a local limit theorem holds:

T (m, n) ∼ C 1 z * n e -(m-nµ 1 ) 2 /(2nσ 2 1 ) √ 2πn σ 1 , n → ∞, m -nµ 1 = O( √ n ).
Remark. C 1 and µ 1 are already given in Knopfmacher and Prodinger [START_REF] Knopfmacher | On Carlitz compositions[END_REF].

For n = 30, Figure 2 gives the observed normalized distribution of M (observed = circle, asymptotic = line), extracted from [z 30 ]D 1 . There is an obvious bias: this will be explained later in Section 2.2. Now if we fix m and consider n as variable (there are, of course, an infinite number of CC for given m), we can obtain another asymptotic form for T (m, n): the conditioned distribution is given by

[w m z n ]D 1 (w, z) = 1 z * n [w m z n ]D 1 (w,
C 2 = -1 h w (1, z * ) = 1 • 3016594836 • • • , µ 2 := 1/µ 1 = 2 • 852242911 • • • , (5) σ 2 2 = σ 2 1 /µ 3 1 = 3 • 1073787943 • • • ,
we obtain the following theorem.

Theorem 2.2 (Vertical Distribution in CC(n)). For large given number of parts m, T (m, n) is asymptotically given by

T (m, n) ∼ C 2 z * n e -(n-mµ 2 ) 2 /(2mσ 2 2 ) √ 2πmσ 2 , m → ∞, n -mµ 2 = O( √ m ). Note that C 1 /C 2 = µ 1 .
For further use, we have also computed C 2 ( j) based on a first part of fixed size j. We first derive (conditioning on j):

φ(w, θ, z| j) = A 2 (w, θ, z| j) + A 1 (w, θ, z)D 2 , (6)
where

D 2 := φ(w, 1, z| j) = A 2 (w, 1, z| j)/h, A 2 (w, θ, z| j) = θ j wz j /(1 + wz j ),
and A 1 is given by [START_REF] Bender | Central and local limit theorems applied to asymptotics enumeration[END_REF].

This leads to

C 2 ( j) = - A 2 (1, 1, z * | j) h w (1, z * ) = -z * j 1 + z * j 1 h w (1, z * ) . (7)
Note that, by (A1), ∑ j C 2 ( j) = C 2 , as it should. Theorem 2.3 is still valid.

Bender's theorems are based on the analysis of ϕ(w) = [ r(1) r(w) ] n where r(w) is the root of (3), seen as a z-equation, and r(1) = z * . But r(1)/r(w) is usually not a Probability GF (PGF). Indeed, we obtain 1

r(w) = 1+w-1 2 w 2 + 7 12 w 3 +• • • which of course doesn't correspond to a PGF.
Similarly, we could consider t(z), the root of (3) (seen as a w-equation), with t(z * ) = 1, and analyze 1 t(z * z) . But we can't even construct a series in z.

It is possible to derive a large deviation result for the number of parts, using r(w).

Following Bender [START_REF] Bender | Central and local limit theorems applied to asymptotics enumeration[END_REF] Theorem 3, we first set w = e s . We have

r ′ (s) = -h w e s /h z , r ′′ (s) = -(r ′2 h zz + 2r ′ e s h zw + e s h w + e 2s h ww )/h z .
where, here, h w = h w (w, r(w)), etc. Bender leads to the following large deviation result:

Theorem 2.3 For m outside the range [nµ 1 -O( √ n ), nµ 1 + O( √ n )], choose s * such that µ = m/n = -r ′ (s * )/r(s * ).
The following asymptotic relation holds:

T (m, n) ∼ e -ms * A 1 [e s * , 1, r(s * )] [r(s * )] n σ(s * ) √ 2πn[-h z (e s * , r(s * ))]r(s * ) , n → ∞, with σ 2 (s * ) = (m/n) 2 -r ′′ (s * )/r(s * ).
The range of validity of Theorem 2.3 can be established as follows. First, we must consider the contour of h(w, z) = 0. After detailed analysis, it appears that this contour h(w, z) = 0 is made of 2 parts: see Figure 3.

Part I, for w ∈ (0, 1], z ∈ [z * , 1), with r(w) -→ w→0 1.

Part II, for w ∈ [1, w 1 ), z ∈ (1/w 1 , z * ] and w 1 is the limit of the solution of h[w, 1 w -ε] = 0, ε → 0. The computation of w 1 offers no special numerical problem and leads to

w 1 = 2 • 584243690 • • • , z 1 = 1/w 1 = •3869604109 • • •
(we must only be careful with the precision: 20 digits are enough in the range we use). µ(w 1 ) and σ 2 (w 1 ) are given by µ(w

1 ) = •4657044011 • • • , σ 2 (w 1 ) = •1056119001 • • • .
The function µ(w) is increasing from 0 to µ(w 1 ), σ 2 (w) goes from 0 (for w = 0) to some maximum and then decreases to σ 2 (w 1 ). So finally, the range for µ is given by (0, µ(w 1 )), z = r(w) following the contour defined above.

The verification of condition (V) of Bender's Theorem 3 (which allows to go from a central limit theorem to a local limit theorem) amounts to prove that h(e s , z) is analytic and bounded for for some ε > 0, δ > 0, where r(s) is the suitable solution of h(e s , r(s)) = 0 (i.e. with r(0) = z * ): this follows from the analyticity analysis of h in the beginning of this section.

Distribution of the last part size in CC

We want to analyze the asymptotic distribution of the size LP of the last part of a CC(n). Setting w = 1 in (1), we derive

[z n ]φ(1, θ, z) ∼ A 1 (1, θ, z * ) -z * n z * h z (1, z * )
, n → ∞, uniformly for θ in some complex neighbourhood of the origin. This may be checked by the method of singularity analysis of Flajolet and Odlyzko, as used in Flajolet and Soria [START_REF] Flajolet | General combinatorial schemes: Gaussian limit distribution and exponential tails[END_REF] or Hwang [START_REF] Hwang | Théorèmes limites pour les structures aléatoires et les fonctions arithmétiques[END_REF]. Normalizing by the total number of CC(n) (4) this leads to the following asymptotic (n → ∞) PGF for the last part size LP:

G(θ) = A 1 (1, θ, z * ).
Expanding, this leads to

π 1 (i) := [θ i ]G(θ) = z * i 1 + z * i , with typical geometric behaviour. Of course G(1) = 1 by (A1) and E(LP) = ∑ iπ(i) = 2 • 5833049669 • • •.
For n = 12, we have computed the observed normalized distribution of LP corresponding to This gives the following Figure 4 (observed = circle, asymptotic = line). The agreement is quite good.

[z 12 ]φ(θ, 1, z).
We can now obtain more information from [START_REF] Aldous | Probability Approximations via the Poisson Clumping Heuristic[END_REF]. The asymptotic distribution of the last part size in CC(n) of m parts is related to [w m z n ]φ(w, θ, z) and Bender's Theorems 1 and 3 lead to the GF:

T (θ, m, n) ∼ C 1 z * n e -(m-nµ 1 ) 2 /(2nσ 2 1 ) √ 2πnσ 1 G(θ), for m -nµ 1 = O( √ n )
, uniformly for θ in some complex neighbourhood of the origin. Again the uniformity can be checked by following Bender's analysis. Normalizing by T (m, n) (see Theorem 2.1), this gives again G(θ). So we have proved the following result:

Theorem 2.4 For m -nµ 1 = O( √ n )
, the asymptotic distribution of the size LP of the last part in CC(n) with m parts is given by π 1 ( j) = z * j /(1 + z * j ) for n → ∞ uniformly for all j.

For instance, for n = 30, m = 9, 11, 13, (⌊nµ 1 ⌋ = 10, ⌊ √ nσ 1 ⌋ = 2) we have computed the observed normalized distribution of LP.

Figure 5 shows that the fit is quite good near the mean, but there is a bias for the two other values of m: n is not yet large enough to yield a distribution of LP that is nearly independent of m Returning to the proof of Bender's theorem, we must compute from (1) i.e.

[θ k w m ]ϕ 1 ϕ 2 [ z * r(w) ] n with ϕ 1 (θ, w) = A 1 (w, θ, r(w)), ϕ 2 (w) = - 1 r(w)h z (w, r(w)) , 0
v ′ (0) = ϕ 1,w (1, 1) ϕ 1 (1, 1) + ϕ 2,w (1) ϕ 2 (1) = β say.
But it is easy to check that ϕ 1,w (1, 1) = 0 and

ϕ 2,w (1) = [r w h z + z * h z,z r w + z * h z,w ]/[z * h z ] 2 , ϕ 2 (1) = -1/(z * h z ), r w = -h w /h z .
From now on, we set 1 (n = 30). This gives Figure 6, where the fit is now nearly perfect. We have, conditioning on j,

h z = h z (1, z * ), etc. Numerical computation gives β = •5365417012 • • • This bias β is now reintroduced in Figure

Correlation between two successive intermediate parts

#(m, n, m 1 , k) = ∑ n 1 ∑ j =k T (m 1 , n 1 , k)T (m 2 , n -n 1 , •)| j.
With Theorem 2.4 (vertical form) and Theorem 2.2 [Eq. 7], this leads, after normalization by T (m, n), to the following distribution:

#(m, n, m 1 , k) T (m, n) ∼ ∑ n 1 ∑ j =k e -(n 1 -m 1 µ 2 ) 2 /2m 1 σ 2 2 √ 2πm 1 σ 2 π 1 (k) × ×C 2 ( j) e -(n-n 1 -m 2 µ 2 ) 2 /2m 2 σ 2 2 √ 2πm 2 σ 2 e -(n-mµ 2 )/2mσ 2 2 √ 2πmσ 2 , (8)
and with (A1) we readily obtain the following distribution π 2 (k) for k:

π 2 (k) = ∑ j =k π 1 (k)C 2 ( j) = -z * k (1 + z * k ) 2 h w .
For further use, we compute, for ℓ ≥ k

π 2 (ℓ) = π (1) 2 (ℓ)z * k + π (2) 2 (ℓ)z * 2k + O(z * 3k ), k → ∞, with π (1) 2 (ℓ) = - z * (l-k) h w , π (2)
2 (ℓ) = 2z * 2(l-k) h w . (9)
By (A2), we obtain ∑ ∞ 1 π 2 (k) = 1 and by (A3), ∑ kπ 2 (k) = µ 2 as it should. So we obtain the following theorem.

Theorem 2. [START_REF] Campbell | Generalized Inverse of Linear Transformations[END_REF] The asymptotic (n → ∞) distribution of intermediate part size is given by π 2 (k), with mean µ 2 .

But we can get more from [START_REF] Flajolet | Level number sequences for trees[END_REF], which shows that the asymptotic joint distribution (in stationary distribution) of two successive intermediate part sizes k and j is given by

π 1 (k)C 2 ( j), j = k.
Normalizing by π 2 (k), this leads to the following Markov chain related to two successive intermediate parts:

Π(k, j) = z * j (1 + z * k ) 1 + z * j , j = k. ( 10
)
The chain is irreducible, recurrent positive and reversible. Of course the stationary distribution of Π is given by π 2 (k). Therefore, we obtain the following theorem.

Theorem 2.6 The asymptotic, n → ∞, distribution of two successive intermediate parts in a CC (n) is

given by a Markov chain Π(i, j), with stationary distribution π 2 (k), and with mean µ 2 .

Let us now analyze the asymptotic behaviour of Π(i, j). This will be used in Sec. 3.2. For fixed ℓ, we obtain

Π + (ℓ, k) := ∞ ∑ j=k Π(ℓ, j) = (1 + z * ℓ ) z * k 1 -z * (1 + O(z * k )), k → ∞.
For further use, we set

ϕ 3 (ℓ) := 1 + z * ℓ 1 -z * . ( 11
)

Associated processes and limiting trajectories

Let us now turn to trajectories. Let x i be the size of part i and set X( j) := ∑ j 1 x i . We have E[X(m)] ∼ mµ 2 and we must check that VAR[X(m)] ∼ mσ 2 2 as given by [START_REF] Campbell | Generalized Inverse of Linear Transformations[END_REF]. We first derive mσ 2

X := VAR[X(m)] ∼ m[S 2 - µ 2 2 ] + 2m ∑ ∞ 1 C x k where S 2 := ∑ π 2 ( j) j 2 = 12 • 208296194 • • • , C x k := ∑ i ∑ j (i -µ 2 )π 2 (i)Π k (i, j)( j -µ 2 ).
But it is easily checked that S 3 := ∑ ∞ 1 C x k can be written as

S 3 = lim w→1 - 1 h w ∑ i ∑ j i 1 + z * i [θ j ]φ(w, θ, z * |i) j 1 + z * j -w ∑ i z * i i 2 (1 + z * i ) 2 -µ 2 2 w 2 1 -w .
With [START_REF] Carlitz | Restricted compositions[END_REF], this can be simplified as

S 3 = lim w→1 ∑ i ∑ j - 1 h w i 1 + z * i j 1 + z * j [θ j ] A 2 (w, θ, z * |i) -wz * i θ i w + A 1 (w, θ, z * )A 2 (w, 1, z * |i) wh(w, z * ) - µ 2 2 w 1 -w .
This leads to (we set w = 1 -ε)

S 3 = lim ε→0 - µ 2 2 ε + µ 2 2 + φ6 - 1 h w - φ5 (1) h w ε + φ5,w (1) h w - φ5 (1)h ww 2h 2 w , (12)
where φ6 := 1

h w ∑ i i 2 (1 + z * i ) 2 z * 2i (1 + z * i ) = -• 95938032262 • • • , ϕ 5 (w, θ, i) = A 1 (w, θ, z * )A 2 (w, 1, z * |i)/w. But A 1 (1, θ, z * ) ≡ G(θ), so we derive - 1 h w • -φ5 (1) h w = - 1 h w ∑ i ∑ j i 1 + z * i • -z * i (1 + z * i )h w . • z * j 1 + z * j • j 1 + z * j ≡ µ 2 2 .
So the singularity in ( 12) is removed. Similarly, we obtain

φ5,w (1) = ∑ i ∑ j i 1 + z * i • j 1 + z * j [θ j ]ϕ 5,w (1, θ, i) ,
and finally

mσ 2 X ∼ m S 2 + µ 2 2 + 2 φ6 - φ5,w (1) h 2 w + µ 2 2 h ww 2h w = mσ 2 2 , (13)
by (A4) as expected.

We can now apply the Functional Central Limit Theorem (for dependent R.V.) (see for instance Billingsley [4, p. 168 ff.]) and we obtain the following result, where B(t) is the standard Brownian Motion (BM).

Theorem 2.7 X([Nt]) -µ 2 Nt σ 2 √ N ⇒ B(t), N → ∞, t ∈ [0, 1],
where N := number of parts of CC(n).

Let us now condition on X(m) = n. A realization of X for fixed n is given by Theorem 2.7, where we stop at a random time m such that X(m) = n. Proceeding as in [START_REF] Louchard | Probabilistic analysis of some (un)directed animals[END_REF] it is easy to check that this amounts to fix N = n/µ 2 in Theorem 2.7 (denominator) and we obtain the following result.

Theorem 2.8 Conditioned on X

(m) = n, X([mt]) -µ 2 mt σ 2 n/µ 2 ⇒ B(t).
Let us now consider the oscillations of X(•) around its mean. Let us define the lower oscillation bound W - n and the range W n :

W - n := -inf i ∈ [0, m] [X(i) -µ 2 i], W n := sup - inf [0, m] [0, m] [X(i) -µ 2 i],
where m is the number of parts in CC(n).

But now the lower bound W - n , normalized by n/µ 2 σ 2 , is asymptotically given by inf

B(t) [0, 1] and the range W n corresponds to the range sup -inf [0, 1] [0, 1]
B(t). The densities of these R.V. are well known: the first one is given by

f 1 (x) = 2e -x 2 /2 √ 2π ,
the second one is given by

f 2 (x) = 8 √ 2π ∞ ∑ k=1 k 2 (-1) k-1 exp[-k 2 x 2 /2], or f 2 (x) = ( 2 π ) 1/2 1 x L ′ ( x 2 ),
where

L(z) = 1 -2 ∞ ∑ k=1 (-1) k-1 exp[-2k 2 z 2 ] = (2π) 1/2 1 z ∞ ∑ k=1 exp[-2(k -1) 2 π 2 /8z 2 ],
by Jacobi θ-relations (see e.g. Whittaker and Watson [START_REF] Whittaker | A Course of Modern Analysis[END_REF]. This immediately leads to the following result Theorem 2.9 For large n, and with

N = n/µ 2 , W - n /(σ 2 √ N ) has the asymptotic density f 1 , W n /(σ 2 √ N ) has the asymptotic density f 2 .
In summary, we can see the CC as a B.M. with some thickness (part size). The distribution of the thickness is characterized by Theorem 2.6.

Simulations and thickness

In this section, we present an algorithm for CC(n) simulation, then we analyze the CC thickness maximum.

Realizations

A simulated realization of a CC(n) proceeds as follows. ✷ Start with a part of size j at time i = 1 given by π 1 ( j). Proceed from a part of size k at time i -1 to a part of size j at time i by using a Markov chain defined by the probability matrix Π(k, j) given by [START_REF] Goulden | Combinatorial enumeration[END_REF]. Stop the chain as soon as S := ∑ m i=1 j i > n. For n = 10.000, a typical unnormalized trajectory for X(i) is given in Figure 7, which shows a "filament silhouette." A typical normalized trajectory for

X(i)-µ 2 i σ 2 √ N and X(i-1)-µ 2 i σ 2 √
N , showing the thickness (here the thickness is defined by the size of the parts) is given in Figure 8. Of course, both trajectories are asymptotically equivalent for n → ∞. A zoom on i = [1030..1050] is given in Figure 9.

Hitting times and maximum for CC thickness

Let us call thickness the part size. In this section, we derive the thickness hitting times (to high level) asymptotic distribution. This leads to a maximum asymptotic density. We consider the set x i of R.V. describing the thickness of CC. Let us define the set D := [k..∞), k >> 1. By [START_REF] Henrici | Applied and Computational Complex Analysis[END_REF], we see that the probability transition to D is O(ε),ε = z * k and by standard properties (see Keilson [16], Aldous [START_REF] Aldous | Probability Approximations via the Poisson Clumping Heuristic[END_REF]) we know that the hitting time to D is such that (we drop k for ease of notation): •

• E ℓ [T D ] = C 3 ε + ψ(ℓ) + O(ε) (
Pr ℓ [T D ≥ x] ∼ e -x/E ℓ [T D ] , x → ∞.
We should write C 3 (ℓ) but we will soon check that C 3 is independent of ℓ. To compute C 3 and ψ(ℓ), we use the classical relation:

E ℓ [T D ] = 1 + ∑ j∈D C Π[ℓ, j]E j [T D ] (14)
i.e.

C 3 + ψ(ℓ)ε = ε + ∑ j∈D C Π[ℓ, j][C 3 + ψ( j)ε] + O(ε 2 ) = ε + ΠC 3 -εϕ 3 (ℓ)C 3 + ∑ j Π(ℓ, j)ψ( j)ε + O(ε 2 ), (15)
and ϕ 3 is given by [START_REF] Henrici | Applied and Computational Complex Analysis[END_REF]. Eq. ( 14) leads to

1 = ∑ D π 2 (ℓ)E ℓ (T D ).
(This is equivalent to a formula of Kac, see [START_REF] Kac | On the notion of recurrence in discrete stochastic processes[END_REF]). Therefore, we obtain

1 = C 3 ∑ D π (1)
2 (ℓ), (16) 0
= ∑ D π (1)
2 (ℓ)ψ(ℓ) +C 3 ∑ D π (2) 2 (ℓ)
2 and π

2 are given by ( 9)). Comparison of powers of ε in [START_REF] Kac | On the notion of recurrence in discrete stochastic processes[END_REF] leads to [I -Π]C 3 = 0, which confirms that C 3 is independent of ℓ. We derive

ψ(ℓ) = 1 -ϕ 3 (ℓ)C 3 + ∑ j Π(ℓ, j)ψ( j), or [I -Π]ψ = δ, with δ(ℓ) := 1 -ϕ 3 (ℓ)C 3 . (18)
We must have π 2 δ = 0, therefore

1 = ∑ π 2 (ℓ)ϕ 3 (ℓ)C 3 , C 3 = 1/ ∑ ℓ π 2 (ℓ)ϕ 3 (ℓ), which fixes C 3 = -h w (1 -z * ).
(This is of course equivalent to [START_REF] Keilson | Markov Chain Models-Rarity and Exponentiality[END_REF].)

We denote by M 1 the Drazin inverse of I -Π. We refer to Campbell and Meyer [START_REF] Campbell | Generalized Inverse of Linear Transformations[END_REF] for a detailed definition and analysis of the Drazin inverse. We have

M 1 = ∑ n≥0 (Π n -1 × π 2 ) = M 2 -1 × π 2 , ( 19
)
where

M 2 := [I -Π + 1 × π 2 ] -1 = ∑ n≥0 [Π -1 × π 2 ]
n is the potential used in Kemeny, Snell and Knapp [START_REF] Kemeny | Denumerable Markov Chains[END_REF]. The solution of ( 18) is given by ψ = M 1 δ + π 2 ψ.

To fix C 6 := π 2 ψ, we first derive

∑ D π (1)
2 ψ = ∑ D π (1) 2 M 1 δ +C 6 ∑ D π (1) 2 ,
and with [START_REF] Kemeny | Denumerable Markov Chains[END_REF],

C 6 = [h w (1 -z * ) 2 h w (1 -z * 2 ) -∑ D π (1) 2 M 1 δ][-h w (1 -z * )].
We can summarize our results in the following form.

Theorem 3.1 The thickness hitting time E

ℓ [T D ] to D := [k..∞], k >> 1 is given by E ℓ [T D ] ∼ C 3 z * k + ψ(ℓ) + O(z * k ), with C 3 = -h w (1 -z * ), ψ(ℓ) = M 1 [1 -C 3 ϕ 3 (ℓ)] +C 6 (M 1 is the potential kernel given in (19)). Pr ℓ [T D ≥ x] ∼ e -xz * k /C 3 , x → ∞.
Now let M (t) := sup i∈ [1..t] x i (maximum thickness with t parts). We know that

Pr[M (t) < k] = Pr[T D ≥ t + 1].
So, by standard asymptotic analysis,

Pr[M (t) < k] ∼ exp[-exp[logt -k log(z * -1 ) -logC 3 ]], t → ∞.
Set now k := j + 1 and

C 4 = z * /C 3 .
By Theorem 2.1, we know that t = nµ 1 + O( √ n ) and µ 1 = h w /(h z z * ).

Hence, we derive the following theorem (we use now the notation M (n)). Then, with integer j and η = O(1),

Pr[M (n) ≤ j] ∼ G 1 (η), n → ∞, where G 1 (η) := exp[-exp[-η log(z * -1 )]]. Let ψ 1 (n) := log(C 4 nµ 1 )/ log(z * -1 ) = [log n -log(-h z ) -log(1 -z * )]/ log(z * -1 )
,

and η = j -⌊ψ 1 (n)⌋ -{ψ 1 (n)}.
Asymptotically, the distribution is a periodic function of ψ 1 (n) (with period 1), which can be written as

log Pr [M (n) ≤ (⌊ψ 1 (n)⌋ + k) e -{ψ 1 (n)} log(z * -1 ) -→ n→∞ -e -k log(z * -1 )
.

We also have

Pr[M (n) = j] ∼ f 1 (η),
where f 1 (η) := G 1 (η) -G 1 (η -1). The asymptotic moments of M (n) are also periodic functions of ψ 1 (n). They can be written as Harmonic sums which are usually analyzed with Mellin transforms: see Flajolet et al [START_REF] Flajolet | Mellin transforms and asymptotics: Harmonic sums[END_REF]. The asymptotic non-periodic term in the moments of M (n) is given by the following result.

Theorem 3.3

The constant term Ē in the Fourier expansion (in ψ 1 (n)) of the moments of M (n) is asymptotically given by

Ē[M (n) -ψ 1 (n)] i ∼ +∞ -∞ η i [G 1 (η) -G 1 (η -1)]dη.
It is well known that the extreme-value distribution function e -e -x has mean γ and variance π 2 /6. From this, we can for instance derive

Ē[M (n)] ∼ ψ 1 (n) + 1 2 + γ log(z * -1 ) . (20)
The other periodic terms have very small amplitude (see Flajolet et al [START_REF] Flajolet | Mellin transforms and asymptotics: Harmonic sums[END_REF]).

For n = 10.000, we have simulated 2.000 trajectories. The observed distribution for maximum thickness is given in Figure 10.

The observed and limiting distribution function (DF) are given in Figure 11 (observed = circle, asymptotic = line). The limiting DF is given by G 1 [ j -ψ 1 (n)] and, due to the sensitivity of G 1 to the mean, we have taken ψ 1 (n) = M0 (n) -

Conclusion

Using some generating functions and limit convergence theorems, we have obtained a complete stochastic description of Carlitz compositions. The same techniques could be used for some generalizations such as Carlitz compositions with zeros and with some restrictions. In a recent paper by Hitczenko and Louchard [START_REF] Hitczenko | Distinctness of compositions of an integer: a probabilistic analysis[END_REF], the distinctness of classical and Carlitz compositions has been fully analyzed.

= ∑ j,k≥1 (-1) j+1 jkz jk = -∑ j,k≥1 k j(-z k ) j = T (1, 1, 2). ✷ σ 2 2 ≡ σ 2 X . (A4) Proof S 2 = T (2, 1, 2) T (0, 1, 2) , µ 2 2 = zh z h w 2 = T (1, 1, 2) T (0, 1, 2) 2 , φ6 = - T (2, 2, 3) T (0, 1, 2) , σ 2 X = S 2 -µ 2 2 + 2Σ, or, by (13), T (2, 1, 2) T (0, 1, 2) + T (1, 1, 2) T (0, 1, 2) 2 -2 T (2, 2, 3) T (0, 1, 2) -2 φ5,w T (0, 1, 2) 2 - φ5 h ww (T (0, 1, 2)) 3 . h ww = ∑ j≥1 (-1) j+1 j( j -1)z j 1 -z j = ∑ j,k≥1 (-1) j+1 j( j -1)z jk = -∑ j,k≥1 j( j -1)(-z k ) j = 2T (0, 2, 3). φ5 = h 2 w µ 2 2 = (zh z ) 2 = T (1, 1, 2) 2 . ϕ 5 (w, θ, i) = ∑ k≥1 (-1) k+1 z k θw k 1 -θz k • z i 1 + wz i . [θ j ]ϕ 5 (w, θ, i) = ∑ k≥1 (-1) k+1 z k w k z k( j-1) z i 1 + wz i = ∑ k≥1 (-1) k+1 z k j w k z i ∑ ℓ≥0 (-1) ℓ (wz i ) ℓ .
[

Fig. 1 :

 1 Fig. 1: Winding number of h

Fig. 2 :

 2 Fig. 2: Observed normalized distribution of M(n = 30) But, for z = 1, the dominant singularity of D 1 (w, zz * ) is w * = 1. So with

Fig. 3 :

 3 Fig. 3: Contour of h = 0 and domain of convergence

Fig. 4 :

 4 Fig. 4: Observed normalized distribution of the last part size LP(n = 12).

Fig. 5 :

 5 Fig. 5: Observed normalized LP distribution (cross: m = 9, circle: m = 11, box: m = 13, n = 30)and r(w) is again the root of (3) with r(1) = z * . But according to Hwang[START_REF] Hwang | Théorèmes limites pour les structures aléatoires et les fonctions arithmétiques[END_REF], [14, Theorem 2], we know that the mean value of M for large n is given by E(M) ∼ nµ 1 + v ′ (0), where v(s) := log[ϕ 1 (1, e s )ϕ 2 (e s )/(ϕ 1 (1, 1)ϕ 2 (1))],

Fig. 6 :

 6 Fig. 6: Observed normalized distribution of M with bias (observed = circle, asymptotic = line, n = 30) j, let #(m, n, m 1 , k) be the total number of CC(n) with m parts, part m 1 of size k, and set m 2 := mm 1 .We have, conditioning on j,

Fig. 7 :

 7 Fig. 7: Unnormalized X(•).

Fig. 8 :Fig. 9 :

 89 Fig. 8: Normalized X(•), with thickness.

Theorem 3. 2

 2 Let η := j -[log n + logC 4 + log µ 1 ]/ log(z * -1 ).

Fig. 10 :

 10 Fig. 10: Distribution of maximum thickness.

Fig. 11 :

 11 Fig. 11: Observed and limiting DF.

k≥1 (- 1 ) 1 +

 k≥111 θ j ]ϕ 5,w (1, θ, i) = ∑ ℓ≥0 ∑ k+1 z k j z i z iℓ (k + ℓ)(-1) ℓ . z j (-1) k+1 z k j z i z iℓ (k + ℓ)(-1) ℓ = -∑ i≥1 iz 2i (1 + z i ) 3 ∑ j≥1 jz j (1 + z j ) 2 + ∑ i≥1 iz i (1 + z i ) 2 ∑ j≥1 jz j (1 + z j ) 3 . This gives φ5,w (1) = T (1, 1, 2)[T (1, 1, 3)-T (1, a boring but simple computation we findh zz = 1 z 2 T (2, 2, 3) + T (1, 2, 3) -T (2, 1, 3) + T (1, 1, 3) ,

= T ( 1 , 1 , 1 - 1 , 1 2 T 3 - 3 = T ( 1 , 1

 1111123311 1, 2) T (0, 1, 2) -T (2, 2, 3) + T (1, 2, 3) -T (2, 1, 3) + T (1, 1, 3) 1 T (0, 1, 2) -2r 1 h zw + h w + h ww T (2r 1 h zw + h w + h ww T ((0, 1, 2) T (1, 1, 2) T (1, 2, 3) -T (1, 1, 3) T (1, 1, 2) 2 T (0, 1, 2) h w + h ww T (1, 1, 2) 2 T (0, 1, 2)

  zz * ).

	0.2
	0.15
	0.1
	0.05
	0	6	8	10	12	14	16	18	20	22
						x

  T (1, 1, 2) 2 T (2, 2, 3) + T (1, 2, 3) -T (2, 1, 3) + T (1, 1, 3) T (1, 1, 2) 2 T (0, 1, 2) 3 -2r 1 h zw + h w + h ww T (1, 1, 2) 2 T (0, 1, 2) 3

	=	T (1, 1, 2) T (0, 1, 2)	+	r 2 1 h zz + 2r 1 h zw + h w + h ww zh z	T (1, 1, 2) 3 T (0, 1, 2) 3
	=	T (1, 1, 2) T (0, 1, 2)	-	r 2 1 h zz + 2r 1 h zw + h w + h ww T (1, 1, 2)	T (1, 1, 2) 3 T (0, 1, 2) 3
	=	T (1, 1, 2) T (0, 1, 2)	-r 2 1 h zz + 2r 1 h zw + h w + h ww	T (1, 1, 2) 2 T (0, 1, 2) 3
	=	T (1, 1, 2) T (0, 1, 2)	-	T (0, 1, 2) 2

1365-8050 c 2002 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

Acknowledgements

The pertinent comments of the referee led to improvements in the presentation.

A Appendix : Some combinatorial identities

Let us first set T (a, b, c)

Since for the special choice z * of z the left side equals 1, the right side also does. Note that this is the only identity where we need the value z * . All next identities are on arbitrary z.

Hence

But now, we easily check that Identification of σ 2 2 and σ 2 X is now immediate. ✷


Michael Drmota
email: michael.drmota@tuwien.ac.at

Helmut Prodinger

The Height of q-Binary Search Trees

Keywords: Binary search tree, q-analog, height

q-binary search trees are obtained from words, equipped with the geometric distribution instead of permutations. The average and variance of the height are computed, based on random words of length n, as well as a Gaussian limit law.

Introduction

The paper [START_REF] Prodinger | A q-analogue of the path length of binary search trees[END_REF] introduces for the first time a meaningful q-model of binary search trees: instead of binary search trees, one considers tournament trees, which differ only marginally from binary search trees; if one starts from a permutation 1 2 ••• n π 1 π 2 ••• π n , then one inserts the number i instead of the number π i . Thus, traversing the tree in inorder, we might think of the associated permutation as ρ1σ, where 1 goes into the root, and ρ resp. σ form (recursively) the left resp. right subtree. We could have called this paper "The Height of q-Tournament Trees;" however we decided not to do so since binary search trees are by far better known, both, in the community of theoretical computer scientists, and combinatorialists. A nice reference for tournament trees and increasing trees in general is [START_REF] Bergeron | Varieties of increasing trees[END_REF]. Now instead of considering permutations π 1 π 2 • • • π n , we consider words over the alphabet {1, 2, 3, . . . }, and (geometric) probabilities attached to the letters, i. e., the probability of letter i is pq i-1 , with p + q = 1. The binary search tree is then constructed by writing a nonempty word w as w = xay, where a is the smallest letter occurring, and x ∈ {a + 1, a + 2, . . . } * and y ∈ {a, a + 1, . . . } * . The letter a goes into the root and x resp. y form the left resp. right subtree.

The paper [START_REF] Prodinger | A q-analogue of the path length of binary search trees[END_REF] dealt with the path length; here we consider the height. The height of a binary search tree (and thus of the trees in our model) is defined to be the largest number of nodes in a path from the root to a leaf; the empty tree (related to the empty word) has height 0.

We will prove that the expected height, when considering random words of length n, is asymptotic to pn; the variance will also be computed as well as a Gaussian limit law. (The letter p will always denote 1q in this paper.) Recall that the result for traditional binary search trees is ∼ c log n with c = 4.31107, see [START_REF] Devroye | On the variance of the height of random binary search trees[END_REF]; unfortunately we do not get that result as the limit q → 1 as it so happened for the path length. However, nothing 1365-8050 c 2002 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France is wrong here, since the limit q → 1 in pn simply tells us that the average height should be less than linear. Although this original hope of getting the classical result as a corollary did not work out, we nevertheless think that the results presented here are of independent interest. Note also that pn is the expected number of letters 1 in a (random) string of length n. In our asymmetric model, they must all lie on one path.

In more detail, we will obtain the following results: Let H n denote the height of q-binary search trees with n (internal) nodes (this is a random variable, defined on words of length n).

Theorem 1 For every positive q < 1 the height H n of q-binary search trees with n (internal) nodes satifies a central limit theorem of the form

sup x∈R Pr{H n ≤ x} -Φ x -pn √ npq = O(n -1/2 ), (1)
where Φ(x) denotes the normal distribution function

Φ(x) = 1 √ 2π x -∞ e -t 2 /2 dt.
The expected value is given by

E H n = pn + O 1 p , (2)
in which the O-constant is uniform for 0 < q < 1. The variance can be estimated by

V H n = pqn + O q n 1/2 log 2 n . (3)
The O-constant in the error term of the variance is not uniform for 0 < q < 1. The dependency on q has not been worked out since the order of magnitude of the error term is surely not optimal. However, although the error term for the expected value is uniform, this theorem cannot be used to cover the case q → 1 where it is known that the expected value is given by [START_REF] Devroye | On the variance of the height of random binary search trees[END_REF]) and the variance is bounded:

E H n = c log n + O (log log n) (with c = 4.31107 • • • , see
V H n = O (1)
(see [START_REF] Drmota | The variance of the height of binary search trees[END_REF][START_REF] Reed | The height of a random binary search tree[END_REF]).

Intuitively, this result (and its proof) says that the height is dominated by the number of 1's in the sequence. This seems to be due to the fact that most 1's appear consecutively in the sequence, producing rather skew subtrees. The contribution from 2's is asymptotically negligible since there are much fewer of them, etc.

Studying the combinatorics (of words) of geometrically distributed random variables has been a long term project of one of us (H. P.), and further papers can be found on this author's webpage. We do not want to give more details here, but in all previous cases the correspondence between the model of words and its limit (permutations) led to very satisfactory results.

We would like to cite the paper [START_REF] Barlow | Diffusion limited aggregation on a homogeneous tree[END_REF] which is of general interest in this context.

Weak Convergence

Lemma 1 Let y k (x) denote the generating function

y k (x) = ∑ n≥0 Pr{H n ≤ k}x n .
Then we have y 0 (x) ≡ 0, y k (0) = 1 and

y k+1 (x) = pxy k (x)y k (qx) + y k+1 (qx) (4)
for k ≥ 0.

Proof. The proof is a straightforward translation of the basic decomposition w = xay: If a = 1 (described by px), then the left subtree consists only of letters in {2, 3, . . . }, described by y k (qx), but the right subtree can have any letters, which is described by y k (x). However, if a > 1, we get the term y k+1 (qx) (we might then think of all letters being reduced by 1). ✷

If we write this in the form

y k+1 (x) -y k+1 (qx) (1 -q)x = y k (qx)y k (x),
then the limit q → 1 gives y ′ k+1 (x) = y 2 k (x), the usual recursion in the instance of binary search trees. (Recall that f (x)-f (qx)

(1-q)x =: (D q f )(x), and D q is called the q-difference operator.) Also, if we write

y k (x) = ∑ 0≤ j<2 k a k, j x j ,
then we get, by comparing coefficients,

a k+1, j = p 1 -q j ∑ 0≤i< j a k,i a k, j-1-i q i for j ≥ 1,
and a k,0 = 1 for all k ≥ 0. Thus, Theorem 1 may be reformulated in terms of a k, j . However, in this paper we will not make use of this notion.

Lemma 2

The generating functions y k (x) (k ≥ 0, 0 ≤ x < 1) are bounded above by

y k (x) ≤ 1 1 -x - x 1 -x px 1 -qx k . ( 5
)
Furthermore, this inequality is also true on the level of coefficients, i. e. for n ≥ 1 and k ≥ 1

Pr{H n ≤ k} = [x n ]y k (x) ≤ 1 -[x n ] x 1 -x px 1 -qx k = k-1 ∑ l=0 n -1 l p l q n-1-l . (6)
Note that this upper bound is an exact binomial distribution function which is asymptotically normal with mean p(n -1) + 1 = pn + q and variance pq(n -1).

Proof. Since y k (x) ≤ 1/(1x) we get from (4) that

y k+1 (x) ≤ px 1 -qx y k (x) + 1 1 -qx .
Thus, (5) follows by induction. Note that any step in these calculations is also true on the level of coefficients. Thus,

Pr{H n ≤ k} ≤ 1 -[x n ] x 1 -x px 1 -qx k . Set Y k (x) = 1 1 -x - x 1 -x px 1 -qx k and ∆ k (x) = Y k (x) -Y k-1 (x) = 1 p px 1 -qx k . Since [x n ]∆ k (x) = n -1 k -1 p k-1 q n-k , (6)
follows immediately. ✷

Lemma 3

The generating functions y k (x) (k ≥ 0, 0 ≤ x < 1) are bounded below by

y k (x) ≥ 1 1 -x - x 1 -x px 1 -qx k - (qx) 2 1 -qx px 1-qx k -(qx) k px 1-qx -qx - qx 1 -x px 1 -qx px 1-qx k -(qx) k px 1-qx -qx + qx 2 1 -x px 1 -qx k 1 -(qx) k 1 -qx . (7)
Furthermore, this inequality is also true on the level of coefficients.

Proof. First we use the trivial lower bound

y k (x) ≥ 1 -x k+1 1 -x
and the upper bound (5) to obtain the inequality

y k+1 (x) = pxy k (x)y k (qx) + y k+1 (qx) ≥ x(1 -q)y k (x) 1 1 -qx - (qx) k+1 1 -qx + 1 1 -qx - (qx) k+2 1 -qx ≥ px 1 -qx y k (x) + 1 1 -qx -px (qx) k+1 1 -qx 1 1 -x - x 1 -x px 1 -qx k - (qx) k+2 1 -qx .
Now [START_REF] Feller | An Introduction to Probability Theory and Its Applications[END_REF] follows by induction. As in the proof of Lemma 2 it can be observed that ( 7) is also true on the level of coefficients. ✷

In order to obtain proper error terms for the lower bound for Pr{H n ≤ k} which may derived from Lemma 3 we make use of the following lemma. Lemma 4 Let 0 < q < 1 be given and let F(x) be a function which is analytic for |x| < 1 + ε for some ε > 0. Then there exist c > 0 and η > 0 (depending on q) such that

[x n ]F(x) px 1 -qx k = O n -1/2 exp - c n k -pn 2 (8)
and

[x n ]F(x) px 1-qx k -(qx) k px 1-qx -qx = O n -1/2 exp - c n k -pn 2 + O(q k ) (9)
uniformly for |k -pn| ≤ ηn as n → ∞.

Proof. By using standard saddle point asymptotics (compare with [START_REF] Drmota | A bivariate asymptotic expansion of coefficients of powers of generating functions[END_REF]) it follows that

[x n ]F(x) px 1 -qx k = 1 2πi |z|=x 0 F(z) pz 1 -qz k dz z n+1 = O n -1/2 x -n 0 px 0 1 -qx 0 k ,
where the saddle point x = x 0 = 1 -k n /q is determined by the equation

x d dx px 1-qx px 1-qx = n k .
In particular we have x 0 = 1 if k/n = p. Finally a local expansion of

x -n 0 px 0 1 -qx 0 k = q n-k p k 1 -k n n-k k n k
completes the proof of ( 8). The proof of (9) runs along similar lines. However, we have to be a little bit more careful. The reason is that the denominator pz 1qz qz is singular for z 1 = 0 and for z 2 = (-1 + 2q)/q 2 . Nevertheless the whole part

pz 1-qz k -(qz) k pz 1-qz -qz is regular for |z| < 1/q. Note that |z 2 | > 1 for 0 < q < √ 2 -1 and that |z 2 | < 1 for √ 2 -1 < q < 1. Thus, if q = √
2 -1 we get similarly to the above

[x n ]F(x) px 1-qx k -(qx) k px 1-qx -qx = 1 2πi |z|=x 0 F(z) pz 1-qz k -(qz) k pz 1-qz -qz dz z n+1 = 1 2πi |z|=x 0 F(z) pz 1-qz k pz 1-qz -qz dz z n+1 - 1 2πi |z|=x 0 F(z) (qz) k pz 1-qz -qz dz z n+1 = 1 2πi |z|=x 0 F(z) pz 1-qz k pz 1-qz -qz dz z n+1 - 1 2πi |z|=1 F(z) (qz) k pz 1-qz -qz dz z n+1 = O n -1/2 x -n 0 px 0 1 -qx 0 k + O(q k ).
Note that we just shifted the paths of integration in regions of analyticity if η is chosen sufficiently small such that |x 0 -1| < |1z 2 |.

If q = √ 2 -1 then there are polar singularities at z 2 = -1 after splitting the integral. However, the residues of the functions involved (at z = -1) are both of order

O ( √ 2 -1) k = O(q k ),
which implies that we get the same error term as in the case q = √ 2 -1. ✷ Note further that (with a little bit more effort) we could have been much more precise. However, the bound given by Lemma 4 is sufficient for our purposes.

Lemma 5 For every 0 < q < 1 there exist c > 0 and η > 0 (depending on q) such that

Pr{H n ≤ k} - k ∑ l=0 n -1 l p l q n-1-l = O n -1/2 exp - c n k -pn 2 ( 10
)
uniformly for |k -pn| ≤ ηn and

Pr{|H n -pn| ≥ m} = O exp -c m 2 n ( 11
)
uniformly for |m| ≤ ηn as n → ∞.

Proof. First we note that (9) of Lemma 4 applies to the function

(qx) 2 1 -qx px 1-qx k -(qx) k px 1-qx -qx .
Thus we obtain

[x n ] (qx) 2 1 -qx px 1-qx k -(qx) k px 1-qx -qx = O n -1/2 exp - c n k -pn 2 + O(q k )
uniformly for |k -pn| ≤ ηn as n → ∞.

The remaining terms will now be treated in the same way as in the proof of Lemma 4:

[x n ] qx 1 -x px 1 -qx px) 1-qx k -(qx) k px 1-qx -qx + qx 2 1 -x px 1 -qx k 1 -(qx) k 1 -qx = 1 2πi |z|=1-ε qz 1 -z pz 1 -qz pz 1-qz k -(qz) k pz 1-qz -qz - qz 2 1 -z pz 1 -qz k 1 -(qz) k 1 -qz dz z n+1 = 1 2πi |z|=x 0 qz 1 -z pz 1 -qz 1 pz 1-qz -qz - qz 2 1 -z 1 1 -qz pz 1 -qz k dz z n+1 - 1 2πi |z|=1-k -1 qz 1 -z pz 1 -qz (qz) k pz 1-qz -qz dz z n+1 + 1 2πi |z|=1-k -1 qz 2 1 -z pz 1 -qz k (qz) k 1 -qz dz z n+1 = O n -1/2 x -n 0 px 0 1 -qx 0 k + O(kq k ).
For the first integral we use the fact that the function

F(z) = qz 1 -z pz 1 -qz 1 pz 1-qz -qz - qz 2 1 -z 1 1 -qz
is regular at z = 1 und thus bounded in a vicinity of z = 1 (compare with the proof of Lemma 4). The second and third integrals are easy to estimate. We only have to apply the trivial bounds max

|z|=1-k -1 1 1 -z = k, max |z|=1-k -1 z k = O(1)
and max

|z|=1-k -1 pz 1 -qz k = 1 + O(k -1 ) k = O(1)
.

Finally observe that in the range |k -pn| ≤ ηn we surely have

kq k = O n -1/2 exp - c n k -pn 2
which completes the proof of (10). The proof of ( 11) is now easy. We just have to combine a proper tail estimate for the binomial distribution, i. e.

∑ |l-pn|≥m n -1 l p l q n-1-l = O exp -c m 2 n , with (10)
. ✷

We are now able to complete the first part of Theorem 1. It is well known that the distribution function of the binomial distribution can be estimated by the distribution function of the normal distribution up to a uniform error of order O(n -1/2 ), i. e., as n → ∞,

sup x∈R ∑ l≤x n -1 l p l q n-1-l -Φ x -pn √ pqn = O(n -1/2 ), (12)
compare with [7, p. 542]. Furthermore, by (10) we get a similar result for the distribution of H n :

sup x∈R Pr{H n ≤ x} -∑ l≤x n -1 l p l q n-1-l = O(n -1/2 ). (13)
Note that (10) provides (13) just for x with |x -pn| ≤ ηn. However, by (11) we know that

Pr{|H n -pn| ≥ ηn} = O exp -cη 2 n .
By the monotonicity of the distribution function this implies that for x with |x -pn| ≥ ηn we also have

Pr{|H n -pn| ≥ x} = O exp -cη 2 n .
Thus (13) follows.

The first part of Theorem 1, i. e. [START_REF] Barlow | Diffusion limited aggregation on a homogeneous tree[END_REF], is now a trivial consequence of (12) and (13).

Convergence of Moments

Lemmata 2 and 3 can be easily used to get quite tight bounds for the expected value. Note that

∑ n≥0 E H n x n = ∑ k≥0 1 1 -x -y k (x) . (14)
Lemma 6 The expected value of H n can be bounded by

pn + q ≤ E H n ≤ pn + O 1 p . ( 15
) Proof. Set E(x) = ∑ k≥0 1 1 -x -y k (x) .
Then by ( 5) we obtain

E(x) ≥ x 1 -x ∑ k≥0 px 1 -qx k = x(1 -qx) (1 -x) 2 ,
which is also true on the level of coefficients. Thus, we have

E H n ≥ pn + q.
Similarly we get the upper bound. From

E(x) ≤ x(1 -qx) (1 -x) 2 + (qx) 2 1 -qx 1 px 1-qx -qx 1 1 -px 1-qx - 1 1 -qx + qx 1 -x px 1 -qx 1 px 1-qx -qx 1 1 -px 1-qx - 1 1 -qx - qx 2 1 -x 1 1 -qx   1 1 -px 1-qx - 1 1 -qx 2 (1-q) 1-qx   = x(1 -qx) (1 -x) 2 + (qx) 2 (1 -x)(1 -qx) + pqx 2 (1 -x) 2 (1 -qx) - qx 2 (1 -x) 2 + qx 2 (1 -x) 1 -pqx 2 1-qx = x(1 -qx) (1 -x) 2 + qx 2 (1 -qx) (1 -x) (1 -qx -pqx 2 )
we directly obtain

E H n ≤ pn + O 1 p .
This completes the proof of Lemma 6. ✷

Unfortunately it seems that we cannot prove similarly tight estimates for the variance. However, we can obtain a non-trivial result:

Lemma 7

The variance of H n can be bounded by V H n = pqn + O q n 1/2 log 2 n . We apply this formula for the height H n where we have very precise estimates for EH n and its distribution function F n (x) = Pr{H n ≤ x}, compare with Lemma 5 and Lemma 6.

Let u ≤ η √ n be a parameter to be defined later. By applying Lemma 5 and Lemma 6 we get 2 Choosing u = log 2 n gives the result. ✷

It should be further mentioned that it is quite easy to get asymptotic relations for all central moments of the form

E(H n -E H n ) k ∼ c k (pqn) k/2 (n → ∞)
by the method as described in Lemma 7, where c 2k = (2k)!/(2 k k!) and c 2k+1 = 0. Thus we have not only a weak convergence result for H n (properly normalized) but convergence of moments, too.

  Proof. If F(x) = Pr{X ≤ x} denotes the distribution function of a random variable X (of compact support) then the variance of X can be represented byV X = 2 EX -∞ (EXy)F(y) dy + 2 ∞ EX (y -EX)(1 -F(y)) dy.

EH n -u √ n 0 (( 2 + O u 2 √ n , 2 EH 2 + O u 2 √ n , and 2 n

 02222 EH n -y)F n (y) dy = O ne -cu 2 , EH ny)F n (y) dy = pqn EH n )(1 -F n (y)) dy = pqn EH n -u √ n (y -EH n )(1 -F n (y)) dy = O ne -cu 2 .