Alois Panholzer
email: alois.panholzer@tuwien.ac.at

Analysis of some parameters for random nodes in priority trees

Keywords: priority trees, node depth, descendants, limiting distribution

Priority trees are a certain data structure used for priority queue administration. Under the model that all permutations of the numbers 1, . . . , n are equally likely to construct a priority tree of size n we study the following parameters in size-n trees: depth of a random node, number of right edges to a random node, and number of descendants of a random node. For all parameters studied we give limiting distribution results.

Introduction

The data structure of priority trees (also called p-trees) is used to implement priority queues. Priority queues are important for many scheduling problems (e.g., for jobs, events, etc.). Typical applications are given in operation systems (scheduling the execution of different jobs, resource management, etc.) and in discrete event simulation models (scheduling events according to their time of occurrence). To each element in a priority queue there is associated a fixed key, whose value determines its priority. We will here assume that low key values correspond to high priority. Two basic operations are fundamental for priority queue administration: inserting an element with arbitrary priority (INSERT), and removing the element with the highest priority (DELETE).

Priority trees can be considered as a special implementation of binary trees that make them suitable for usage as a priority queue. Formally they are defined as follows: a priority tree either is empty or consists of a sequence of nodes with non-increasing keys, the so called left path, such that to each node on the left path except the last one, there is associated a possibly empty priority tree, the so called right subtree. All nodes of the right subtree that are associated with a node z on the left path are ranked between z and the left successor of z. More precisely, if x with key k denotes the left successor of z with key l, then all nodes in the right subtree of z have key values s: k ≤ s < l. k = s can occur as is seen by considering the insertion algorithm defined in the sequel.

Of course it follows from this definition that not every binary tree of size n, where the size of a tree is given as usual by the number of internal nodes, can appear as a priority tree. The number P n of different size-n priority trees is given by the number of size-n Motzkin-trees (also called unary-binary trees). Although this is not mentioned explicitly in [START_REF] Jonassen | Analysis of an algorithm for priority queue administration[END_REF] it is a direct consequence of the formula for P n presented in that work. Priority trees are generated from the empty tree by successively inserting new elements via the recursive algorithm INSERT. Inserting a new element p into a priority tree T works as follows:

• If T is empty or the key associated to the root of T is not larger than p, then let p be the new root and T its left subtree.

• Otherwise follow the left path of T and look for the first node x that has a key not larger than the key of p.

-If no such node exists, then append p to the left path as a new left leaf.

-Otherwise let us denote by z the predecessor of x; thus the key of p is ranked between the keys of x and z. In this case algorithm INSERT will be applied recursively to the right subtree of z to insert node p.

We give in Figure 1 an example of constructing a priority tree with the algorithm INSERT.

ǫ ⇒ 3 ⇒ Fig. 1: Construction of a priority tree of size 6 from the keys 3, 1, 6, 4, 5, 2 starting with the empty tree (denoted by ǫ). The node with key 3 has in the resulting tree exactly 2 ascendants (i.e., there are exactly 2 nodes lying on the path from the root to the node 3; therefore the depth of this node is 2) and 3 descendants (i.e., the size of the subtree with node 3 as root-node is 3). The number of right edges on the path from the root to node 3 is 0.

Priority trees were investigated in the early 1960's as a data structure for maintaining priority queues in the implementation of the programming language SIMULA, which was developed at the Norwegian Computer Center in Oslo by Dahl and Nygaard. A first average-case analysis of the behaviour of priority trees was given by Jonassen and Dahl in [START_REF] Jonassen | Analysis of an algorithm for priority queue administration[END_REF]. They are also mentioned in handbooks of algorithms and data structure, e.g., in [START_REF] Gonnet | Handbook of algorithms and data structures[END_REF], where some of the results obtained in [START_REF] Jonassen | Analysis of an algorithm for priority queue administration[END_REF] are cited. In the average-case analysis it has been used always the so called random permutation model as the underlying probability model. This means that all n! permutations of {1, 2, . . . , n} are assumed to be chosen equally likely as data arrays to construct a priority tree of size n starting with the empty tree using algorithm INSERT repeatedly. As main results in their analysis we cite the expected number of key comparisons I n and the expected recursion depth R n when inserting a random element into a random size-n priority tree, and the expected size of the left path L n in a random size-n priority tree (this gives the depth of the node with the smallest key value, the so called left leaf, and thus the depth of the data with the highest priority, where the depth of a node x in the tree is here always measured by the number of nodes lying on the direct path from the root to x):

E(I n ) = H 2 n+1 3 + 10H n+1 9 - H (2) n+1 3 - 28 27 , for n ≥ 2, E(R n ) = 2 3 H n+1 + 1 9 , for n ≥ 2, E(L n ) = 2H n -1.
Here H n := n k=1

1 k and H

(2)

n := n k=1
1 k 2 denote the first and second order harmonic numbers. Since E(I n ) ∼ 1 3 log 2 n, it follows that the operation INSERT is for priority trees asymptotically more expensive than for other priority queue structures (like heaps or leftist trees, see, e.g., [START_REF] Gonnet | Handbook of algorithms and data structures[END_REF]). We further remark that the dynamic behaviour of priority trees was considered in [START_REF] Jonassen | The stationary p-tree forest[END_REF].

The average case analysis of this data structure under the random permutation model has been extended in [START_REF] Panholzer | Average-case analysis of priority trees: a structure for priority queue administration[END_REF], see also [START_REF] Panholzer | Untersuchungen zur durchschnittlichen Gestalt gewisser Baumfamilien. Mit besonderer Berücksichtigung von Anwendungen in der Informatik[END_REF]. The focus has been given there in computing exact formulae for the mean of several tree statistics for nodes in size-n trees with a fixed key j (and not for random nodes). In particular we obtained for size-n priority trees among others exact and asymptotic results for the expected depth of node j (= number of ancestors of j and also called height of j), the expected number of right edges (and left edges) to the node j, the expected number of descendants of node j, and the number of key comparisons when inserting a node with key j + 1 2 . Moreover, we have shown that the length of the left path L n is asymptotically Gaussian distributed with mean E(L n ) ∼ 2 log n and variance V(L n ) ∼ 2 log n. We remark that the latter result can be obtained directly by applying the theory of records (see, e.g., [START_REF] Devroye | Applications of the theory of records in the study of random trees[END_REF]).

In the present work we will reconsider some of these parameters, where we will focus here on establishing limiting distribution results for randomly chosen nodes in size-n priority trees: in particular we will analyse the depth A n of a random node. We remark that we use throughout this paper the convention that a node is considered as its own ancestor (and is thus counted for the depth) and descendant. The results obtained for these tree statistics are given in Section 2.

The motivation of the author for a detailed study of this tree family is three-fold.

• Up to now there exist only few results, which describe the average-case behaviour of the operations in priority trees that are of interest when using them as a data structure for priority queue administration. In particular the behaviour of the algorithm INSERT when inserting a random node into a randomly grown priority tree of size n is little analyzed: everything known was obtained more than 30 years ago in [START_REF] Jonassen | Analysis of an algorithm for priority queue administration[END_REF] leading to the exact and asymptotic formulae for the expectation of the number of key comparisons I n and the expectation of the recursion depth R n given above. Although we will not carry out the distributional analysis of I n and R n in the present paper state that these parameters are closely related to

A [H] n and A [R]
n studied here: one obtains that, asymptotically,

I n behaves like A [H] n and R n behaves like A [R]
n , or to be more precise, Theorem 1 also holds for I n and Theorem 2 also holds for R n . We state these results as Corollary 4. We remark that Corollary 4 is not a consequence of Theorem 1-2 (e.g., it does not seem that there is a simple relation between

I n and A [H]
n ), but a consequence of the proof of these theorems, which is fully analogous. A very raw sketch of the proof of these results appeared in [START_REF] Kuba | Analysis of insertion costs in priority trees[END_REF] as an extended abstract of a conference.

• This tree model seems to be also of some purely mathematical interest, since the algorithm INSERT gives a quite simple construction rule, which generates a tree family with an unusual behaviour.

Most random tree models are either a member of the class of log n-trees (a randomly chosen node has expected depth Θ(log n), like, e. g., the data structures binary search trees, digital search trees, and Quad-trees) or of the class of √ n-trees (a randomly chosen node has expected depth Θ( √ n), like, e. g., binary trees or unordered labelled trees, so called Cayley trees). As a consequence of Theorem 1 it is shown in this paper that priority trees are neither log n-trees nor √ n-trees, but the depth of a randomly chosen node has expectation ∼ 1 3 log 2 n and variance ∼ 10 81 log 3 n and is, after normalization, asymptotically standard normally distributed.

• The proof of the asymptotic normality of the centered and scaled version of the parameter A

[H] n as stated in Theorem 1 could be of some methodological interest, since it was shown by using the method of moments without shifting by the exact or asymptotic mean. This requires of course a very detailed description of the asymptotic behaviour of the ordinary or factorial moments of A

[H]

n to take care of the huge cancellations when considering the centered random variable. The motivation comes from the fact that there are several parameters in the study of discrete structures, where one has a simple description of the random variable of interest by means of generating functions leading to functional equations, differential equations, etc., but when applying the method of moments, after shifting by the asymptotic mean, one often (apart from the instance E(X n ) ∼ cn) cannot directly continue the computations at the level of generating functions, but one is rather forced to go back and do it at the level of coefficients. In general certainly shifting the mean, i.e., to study directly the recurrences for the centered moments, is advantageous; see, e.g., [START_REF] Chen | Analysis in distribution of two randomized algorithms for finding the maximum in a broadcast communication model[END_REF] for an impressive example. However, there might be some intrinsic interest in the question what is necessary to know (and how to obtain this knowledge) about the behaviour of the generating functions of the ordinary (or factorial) moments of a random variable X n to show asymptotic normality of the normalized version of X n , in particular for instances, where the so called quasi-power theorem is not applicable.

Results and mathematical preliminaries

Results

As already mentioned in the introduction we use as mathematical model for our analysis of priority trees the random permutation model, i.e., all n! permutations of the numbers 1, . . . , n are equally likely for constructing a priority tree of size n. For this model we give here in Theorems 1-3 limiting distribution results for the following three parameters:

• A [H]
n is the random variable that counts the depth (= height) of a randomly chosen node in a random priority tree of size n, i.e., the number of nodes (= ancestors) lying on the unique path from the root to a randomly chosen node.

• A [R]
n is the random variable that counts the number of right edges on the path from the root to a randomly chosen node in a random priority tree of size n

• A [D]
n is the random variable that counts the number of descendants of a randomly chosen node in a random priority tree of size n. The number of descendants of a node x is here defined as the size of the subtree rooted at node x, i.e., a chosen node is always counted as a descendant of itself.

We formulate now the main results of this paper, where we denote as usual by

(d)
--→ convergence in distribution and where Φ(x) denotes the distribution function of the standard normal distribution N (0, 1).

Theorem 1 The depth A [H]

n of a random node in a random size-n priority tree is asymptotically Gaussian distributed:

sup x∈R P    A [H] n -1 3 log 2 n 10 81 log 3 n ≤ x    -Φ(x) = o(1).
The expectation E(A

[H] n ) and the variance V(A [H] n ) satisfy E(A [H] n ) = 1 3 log 2 n + O(log n), V(A [H] n ) = 10 81 log 3 n + O(log 2 n). Theorem 2 The number A [R]
n of right edges on the path from the root to a random node in a random sizen priority tree is asymptotically Gaussian distributed, where the convergence rate is of order O 1 √ log n :

sup x∈R P    A [R] n -2 3 log n 10 27 log n ≤ x    -Φ(x) = O 1 √ log n .
The expectation

E(A [R] n ) and the variance V(A [R] n ) satisfy E(A [R] n ) = 2 3 log n + O(1), V(A [R] n ) = 10 27 log n + O(1)
.

Theorem 3 The number A [D]

n of descendants of a random node in a random size-n priority tree converges in distribution to a discrete random variable A [D] (with non-existing r-th moments E A [D] r , for

r ≥ 1), A [D] n (d)
--→ A [D] , which has the distribution

P A [D] = m = 2 3m(m + 1) H m - m -1 3m(m + 1) 2 , for m ≥ 1.

The r-th moments of A [D]

n are given asymptotically by

E A [D] n r = r(r+1) (r-1)(r+2) n r-1 log n + O n r-1 , for r ≥ 2, 1 3 log 2 n + O log n , for r = 1.
We further present here limiting distribution results for the following two parameters, which describe the insertion costs when inserting a random element into randomly grown priority trees.

• I n : the number of key comparisons that are made when inserting a random element into a random priority tree of size n with the algorithm INSERT. For the model of randomness we assume further that all values of the set { 1 2 , 3 2 , . . . , n + 1 2 } can occur with equal probability 1 n+1 as the key of the inserted element.

• R n : the recursion depth, i. e., the number of calls of the algorithm INSERT, when inserting a random element into a random priority tree of size n.

By applying the methods used for the proof of Theorem 1-2 we obtained the following results (see [START_REF] Kuba | Analysis of insertion costs in priority trees[END_REF]).

Corollary 4

The number of key comparisons I n when inserting a random element into a random size-n priority tree with the algorithm INSERT is asymptotically Gaussian distributed:

sup x∈R P    I n -1 3 log 2 n 10 81 log 3 n ≤ x    -Φ(x) = o(1).
The expectation E(I n ) and the variance V(I n ) satisfy

E(I n ) = 1 3 log 2 n + O(log n), V(I n ) = 10 81 log 3 n + O(log 2 n).
The recursion depth R n when inserting a random element into a random size-n priority tree with the algorithm INSERT is asymptotically Gaussian distributed, where the convergence rate is of order O 1 √ log n :

sup x∈R P    R n -2 3 log n 10 27 log n ≤ x    -Φ(x) = O 1 √ log n .
The expectation E(R n ) and the variance V(R n ) satisfy

E(R n ) = 2 3 log n + O(1), V(R n ) = 10 27 log n + O(1).

Mathematical preliminaries and outline of the proofs

In our analysis we use the approach introduced in [13]: we work with three families of combinatorial objects denoted by A, B and C. The family A contains ordinary priority trees generated from random permutations (applying algorithm INSERT repeatedly) starting with the empty tree, the auxiliary family B contains priority trees generated from random permutations starting with the additional element "+∞", the auxiliary family C contains priority trees generated from random permutations starting with the additional element "-∞". We always assume that these additional elements are not counted for the size of an object, which means that the size of an object is given by the number of nodes without elements -∞ and +∞.

The analysis of the tree statistics introduced above relies heavily on the decomposition of the families A, B and C according to the first element k of a random permutation of the numbers 1, 2, . . . , n. These fundamental combinatorial decompositions are given in Figure 2.

They will lead to systems of recurrences for the probabilities P{A n = m}, P{B n = m} and P{C n = m} of the random variables A n , B n and C n , where A n is either A random variables A n,j , B n,j and C n,j , which count the corresponding tree parameters in objects of size n in the families A, B and C for a fixed node j (instead of a random node). Of course we have then

[H] n , A [R] n or A [D] n ,
A n = n j=1 J n,j A n,j ,
where J n,j is the indicator variable of the event U n = j, where U n is uniformly (and independently of the A n,j ) distributed on {1, 2, . . . , n}. Corresponding equations hold for the B n and C n , too. It holds then that

P{A n = m} = 1 n n j=1 P{A n,j = m}, etc.
This approach was used in [START_REF] Panholzer | Average-case analysis of priority trees: a structure for priority queue administration[END_REF] and one can translate the decompositions of Figure 2 easily into systems of recurrences for the probabilities P{A n,j = m}, etc. By introducing trivariate generating functions

A(z, u, v) := n≥1 n j=1 m≥0 P{A n,j = m}z n u j v m , etc.
we obtain then systems of linear differential equations for A(z, u, v), B(z, u, v) and C(z, u, v), which lead after specializing u = 1 to systems of linear differential equations for

A(z, v) := A(z, 1, v) = n≥1 m≥0 n P{A n = m}z n v m
and the corresponding functions B(z, v) and C(z, v). All systems of differential equations can be transformed into single higher order linear differential equations for A(z, v).

Before we outline how to proceed from these differential equations we introduce some notation used throughout this paper. We denote by x m := x(x -1) • • • (xm + 1) the falling factorials and by ⌊x⌋ the floor function (see, e.g., [START_REF] Graham | Concrete mathematics[END_REF]). In order to avoid clumsy notations we use the abbreviation Pol x (d) for any polynomial in x of degree at most d, which can vary in every occurrence of Pol

x (d). If d < 0 then we use the convention that Pol x (d) = 0. With [x n ]f (x) we denote the n-th coefficient f n of a power series f (x) = k≥0 f k x k or polynomial f (x) = d k=0 f k x k . Furthermore we use the abbreviation L(z) := log 1 1-z and the Iverson-notation [[Statement]],
which gives 1 if Statement is true and 0 otherwise.

In the instance of A

[H] n we will use the method of moments to show the stated central limit theorem. First we can reduce the order of the third order differential equation for A(z, v) to a second order linear differential equation for a function H(z, v). The functions H r (z) := ∂ r ∂v r H(z, v) v=1 satisfy for all integers r ≥ 0 second order Cauchy-Euler differential equations and one can easily pump out the structure of the solutions for H r (z) as linear combinations of functions

1 (1-z) 2 L(z) 2r-m , with 0 ≤ m ≤ 2r and (1 -z)L(z) 2r-2-m , with 0 ≤ m ≤ 2r -2.
This is shown in Lemma 5. This structure will follow also directly from the general study of Cauchy-Euler differential equations given in [START_REF] Chern | An asymptotic theory for Cauchy-Euler differential equations with applications to the analysis of algorithms[END_REF]. But it is essential in our analysis to obtain a full recursive description for the coefficients α (m) r of the functions 1

(1-z) 2 L(z) m in these linear combinations, which is also established in Lemma 5.

Next, these recurrences for the coefficients α (m) r are studied for fixed m as a function of r. In Lemma 6 we show the representation α

(m) r = 1 3 r r ⌊ m+1 2 ⌋ Pol r (2m -⌊ m+1 2
⌋), which holds for fixed m and r ≥ 0. Moreover, the leading coefficients η (m) in the polynomials are given.

Lemma 8 translates these results to the generating functions A r (z) of the r-th factorial moments of

A [H] n , A r (z) := ∂ r ∂v r A(z, v) v=1 = n≥1 n E A [H] n r z n .
In particular we obtain the asymptotic

expansion A r (z) ∼ 2r m=0 a (m) r 1
(1-z) 2 L(z) 2r-m around the dominant singularity z = 1, where the coefficients a (m) r are for fixed m and r ≥ 0 again given by a is now used together with a description of the appearing sums via higher order differences to treat the massive cancellations and to determine the leading terms of the r-th

(m) r = 1 3 r r ⌊ m+1 2 ⌋ Pol r (2m -⌊ m+1 2
centered moments E A [H] n -1 3 log 2 n r .
It follows that after normalization these centered moments converge to the moments of the standard normal distribution N (0, 1). This is established in Lemma 9.

Together with the Theorem of Fréchet and Shohat (see, e.g., [START_REF] Fisz | Probability theory and mathematical statistics[END_REF]) Theorem 1 is shown.

In the instance of

A [R]
n the second order differential equation for A(z, v) is of Cauchy-Euler type, which has an explicit solution. Extracting coefficients [z n ]A(z, v) uniformly in a neighbourhood of v = 1 only requires singularity analysis of generating functions [START_REF] Flajolet | Singularity analysis of generating functions[END_REF]. Theorem 2 follows from this expansion immediately by an application of the quasi-power theorem due to Hwang [START_REF] Hwang | On convergence rates in the central limit theorems for combinatorial structures[END_REF].

In the instance of A [D]

n the second order differential equation for A(z, v) is again of Cauchy-Euler type. Although the solution is not given in closed form, it is here not hard to extract coefficients [z n v m ]A(z, v) and thus to give explicit results for the probabilities P{A

Singularity analysis leads then to asymptotic results for

E A [D] n r .
The complete proofs of Theorems 1-3 are given in Sections 3-5.

3 Depth of a random node

A system of recurrences

Using the combinatorial decomposition given in Figure 2, i.e., the decomposition with respect to the first element k of a random permutation of {1, . . . , n}, we obtain the following system of recurrences for the probabilities P{A

[H] n,j = m}, P{B [H] n,j = m} and P{C [H]
n,j = m}, which give the probabilities that node j has depth m in a random generated object of size n of the families A, B and C for 1 ≤ j ≤ n (see [START_REF] Panholzer | Average-case analysis of priority trees: a structure for priority queue administration[END_REF]). We recall the convention used in this paper that the depth of a node x is always measured by the number of nodes lying on the direct path from the root to x.

P{A [H] n,j = m} = 1 n 0 @ j-1 X k=1 P{C [H] n-k,j-k = m} + pn-j,m-1 + n X k=j+1 m X i=0 p n-k,i P{B [H] k-1,j = m -i} 1 A , (1a) P{B [H] n,j = m} = 1 n 0 @ j-1 X k=1 P{A [H] n-k,j-k = m -1} + [[m = 2]] + n X k=j+1 P{B [H] k-1,j = m -1} 1 A , (1b)
P{C [H] n,j = m} = 1 n 0 @ j-1 X k=1 P{C [H] n-k,j-k = m} + pn-j,m-1 + n X k=j+1 m-1 X i=0 p n-k,i P{A [H] k-1,j = m -1 -i} 1 A . (1c)
The appearing functions p n,m give the probabilities that the size of the left path, i.e., the number of nodes from the root to the left leaf, in a random object of size n of the family C is m. We will here make the convention to count the element +∞ but not the element -∞ for the depth of a node and the size of the left path. It has been shown already in [START_REF] Panholzer | Average-case analysis of priority trees: a structure for priority queue administration[END_REF] that these probabilities and their generating function p(z, v) := n≥0 m≥0 p n,m z n v m are given by:

p n,m = n m n! and p(z, v) = 1 (1 -z) v ,
where n m denote the signless Stirling numbers of first kind. This can be seen easily by the observation that when starting with the element -∞ and inserting n distinct elements, an element x will be inserted into the left path if and only if x is larger than all elements already inserted. Thus p n,m is nothing else than the probability that the number of left-to-right maxima of a random permutation of {1, . . . , n} is exactly m, and it is well-known that these probabilities are given by the formula stated above.

The generating functions approach

Introducing the generating function A(z, u, v) :=

n≥1 1≤j≤n m≥0 P{A [H]
n,j = m}z n u j v m , and the corresponding functions B(z, u, v) and C(z, u, v), this system of recurrences (1) gives the following system of linear differential equations:

∂ ∂z A(z, u, v) = u 1 -uz C(z, u, v) + uv 1 -uz p(z, v) + p(z, v)B(z, u, v), ∂ ∂z B(z, u, v) = uv 1 -uz A(z, u, v) + uv 2 (1 -z)(1 -uz) + v 1 -z B(z, u, v), ∂ ∂z C(z, u, v) = u 1 -uz C(z, u, v) + uv 1 -uz p(z, v) + vp(z, v)A(z, u, v), with initial conditions A(0, u, v) = B(0, u, v) = C(0, u, v) = 0. The generating function of interest A(z, v) := A(z, 1, v) = n≥1 m≥0 n P{A [H] n = m}z n v m
, and the corresponding auxiliary functions B(z, v) and C(z, v), are thus satisfying the following system of differential equations with initial conditions

A(0, v) = B(0, v) = C(0, v) = 0: ∂ ∂z A(z, v) = 1 1 -z C(z, v) + 1 (1 -z) v B(z, v) + v (1 -z) v+1 , (2a)
∂ ∂z B(z, v) = v 1 -z A(z, v) + v 1 -z B(z, v) + v 2 (1 -z) 2 , (2b)
∂ ∂z C(z, v) = 1 1 -z C(z, v) + v (1 -z) v A(z, v) + v (1 -z) v+1 . (2c)
Using the substitutions C(z, v) := (1z)C(z, v) and B(z, v) := (1z) v B(z, v) we can simplify system (2) and get

∂ ∂z A(z, v) = 1 (1 -z) 2 C(z, v) + 1 (1 -z) 2v B(z, v) + v (1 -z) v+1 , (3a)
∂ ∂z B(z, v) = v(1 -z) v-1 A(z, v) + v 2 (1 -z) v-2 , (3b)
∂ ∂z C(z, v) = v (1 -z) v-1 A(z, v) + v (1 -z) v . ( 3c
)
Now one can successively eliminate B(z, v) and C(z, v) from (3a) by comparing with (3b) and (3c) and get eventually the following homogeneous third order linear differential equation for A(z, v):

∂ 3 ∂z 3 A(z, v) - 3 + 2v 1 -z ∂ 2 ∂z 2 A(z, v) + 2v 2 (1 -z) 2 - 1 (1 -z) v+1 ∂ ∂z A(z, v) + 2v (1 -z) v+2 A(z, v) = 0, (4) with initial conditions A(0, v) = 0, ∂ ∂z A(z, v) z=0 = v, ∂ 2 ∂z 2 A(z, v) z=0 = 2v(v + 1) resulting from P{A [H] 1 = 1} = 1, P{A [H] 2 = 1} = P{A [H] 2 = 2} = 1 2 .
Since one solution of ( 4) is given by 1 1-z , which is checked easily, we can reduce the order of this differential equation when substituting

H(z, v) := ∂ ∂z (1 -z)A(z, v) . (5)
This leads to the following homogeneous second order linear differential equation, which is the starting point of our studies (i) :

∂ 2 ∂z 2 H(z, v) - 2v 1 -z ∂ ∂z H(z, v) - 2v (1 -z) v+1 H(z, v) = 0, (6)
with initial values H(0, v) = v and ∂ ∂z H(z, v) z=0 = 2v 2 . In order to apply the method of moments we define for integers r ≥ 0 the functions H r (z) via

H r (z) := ∂ r ∂v r H(z, v) v=1 .
Differentiating equation ( 6) r times with respect to v and evaluating at v = 1 leads then to the following differential equations for H r (z) of Cauchy-Euler type:

H ′′ r (z) - 2 1 -z H ′ r (z) - 2 (1 -z) 2 H r (z) = S r (z), (7)
where the inhomogeneous parts are given by S 0 (z) = 0 and for r ≥ 1:

S r (z) = 2r 1 -z H ′ r-1 (z) + 2 r-1 k=0 r k H k (z) 1 (1 -z) 2 L(z) r-k + r -k (1 -z) 2 L(z) r-1-k . ( 8
)
The corresponding homogeneous differential equation has the general solution (with arbitrary constants C 1 , C 2 ):

H [hom] r (z) = C 1 1 (1 -z) 2 + C 2 (1 -z).
The variation of parameters method (see, e.g., [START_REF] Pontryagin | Ordinary differential equations[END_REF]) gives then immediately the general solution of the required H r (z): [START_REF] Jonassen | The stationary p-tree forest[END_REF] where the constants C r,1 and C r,2 are specified by the initial conditions: adapting to the initial values leads to the linear system of equations i) It should be remarked that the general solution of this differential equation can be expressed via hypergeometric functions or alternatively via Bessel functions. Maple is capable of finding a required solution basis. However it seems quite involved to show the given central limit theorem directly from the solution obtained after adapting to the initial values.

H r (z) = 1 3(1 -z) 2 z t=0 (1 -t) 3 S r (t)dt - 1 -z 3 z t=0 S r (t)dt + C r,1 (1 -z) 2 + C r,2 (1 -z),
1 1 2 -1 C r,1 C r,2 = ∂ r ∂v r v v=1 ∂ r ∂v r 2v 2 v=1 , (
and thus to the solutions

C 0,1 = 1, C 0,2 = 0, C 1,1 = 5 3 , C 1,2 = - 2 3 , C 2,1 = 4 3 , C 2,2 = - 4 3 , C r,1 = 0, C r,2 = 0, for r ≥ 3. (10)
We get immediately that H 0 (z) = 1 (1-z) 2 , which, of course, follows also from the definition.

The exact solution of H r (z)

We will give now the exact solutions of the functions H r (z) satisfying ( 9), where we make throughout this paper the convention that

b k=a f (k) = 0 if b < a.
We also recall the abbreviation L(z) := log 1 1-z . Lemma 5 The solution H r (z) of the differential equation ( 9) is given by

H r (z) = 2r m=0 α (m) r 1 (1 -z) 2 L(z) 2r-m + 2r-2 m=0 β (m) r (1 -z)L(z) 2r-2-m , ( 11
)
with certain constants α that are defined recursively via (ii)

α (0) r = 1 3 α (0) r-1 , for r ≥ 1, (12a)
α (m) r = 1 3(2r -m) » 4rα (m-1) r-1 + 2r(2r -m)α (m-2) r-1 + m X k=0 2 `r r-1-k ´α(m-k) r-1-k + m-1 X k=0 2(k + 1) `r r-1-k ´α(m-1-k) r-1-k - (12b) + m-1 X l=0 (-1) m-l (2r -1 -l) m-l-1 3 m-l+1
» 4rα

(l-1) ii) It must be noticed that in the further proof only the recurrences for α will not be used in the sequel, but they are stated here to keep the paper self-contained.

r-1 + 2r(2r -l)α (l-2) r-1 + l X k=0 2 `r r-1-k ´α(l-k) r-1-k + l-1 X k=0 2(k + 1) `r r-1-k ´α(l-1-k) r-1-k - , for 1 ≤ m ≤ 2r -1, α (2r) r = 2r-1 X l=0 (-1) l (2r -1 -l)! 3 2r-l+1 » 4rα (l-1) r-1 + 2r(2r -l)α (l-2) r-1 + l X k=0 2 `r r-1-k ´α(l-k) r-1-k + l-1 X k=0 2(k + 1) `r r-1-k ´α(l-1-k) r-1-k - (12c) + 2r-3 X l=0 (2r -3 -l)! 3 2r-1-l » -2rβ (l-1) r-1 + 2r(2r -2 -l)β (l-2) r-1 + l X k=0 2 `r r-1-k ´β(l-k) r-1-k + l-1 X k=0 2(k + 1) `r r-1-k ´β(l-1-k) r-1-k - + Cr,1, (
β (0) r = - r 3(r -1) β (0) r-1 , for r ≥ 2, β (m) r = - 1 3(2r -2 -m) » -2rβ (m-1) r-1 + 2r(2r -2 -m)β (m-2) r-1 + m X k=0 2 `r r-1-k ´β(m-k) r-1-k + m-1 X k=0 2(k + 1) `r r-1-k ´β(m-1-k) r-1-k - (12d) + m-1 X l=0 - (2r -3 -l) m-l-1 3 m-l+1 » -2rβ (l-1) r-1 + 2r(2r -2 -l)β (l-2) r-1 + l X k=0 2 `r r-1-k ´β(l-k) r-1-k + l-1 X k=0 2(k + 1) `r r-1-k ´β(l-1-k) r-1-k - , for 1 ≤ m ≤ 2r -3,
β (2r-2) r = -α (2r) r + Cr,1 + Cr,2. ( 12e
)
The constants C r,1 and C r,2 are given by [START_REF] Jonassen | Analysis of an algorithm for priority queue administration[END_REF]. Furthermore we make the convention that α where we show in parallel the following formulae for the inhomogeneous parts S r (z) of ( 7):

S r (z) = 2r-1 l=0 γ (l) r 1 (1 -z) 4 L(z) 2r-1-l + 2r-3 l=0 δ (l) r 1 1 -z L(z) 2r-3-l , (13)
where the γ

(l)
r and δ

(l)
r are for r ≥ 0 given recursively by

γ (l) r = 4rα (l-1) r-1 + 2r(2r -l)α (l-2) r-1 + l X k=0 2 `r r-1-k ´α(l-k) r-1-k + l-1 X k=0 2(k + 1) `r r-1-k ´α(l-1-k) r-1-k , (14a)
δ (l) r = -2rβ (l-1) r-1 + 2r(2r -2 -l)β (l-2) r-1 + l X k=0 2 `r r-1-k ´β(l-k) r-1-k + l-1 X k=0 2(k + 1) `r r-1-k ´β(l-1-k) r-1-k . ( 14b
)
For r = 0 we obtain from the recurrences α

(0) 0 = C 0,1 = 1, β (0) 0 = 0, γ (0) 0
= 0 and δ (0) 0 = 0, which corresponds with S 0 (z) = 0 and H 0 (z) = 1

(1-z) 2 ; thus formulae [START_REF] Kuba | Analysis of insertion costs in priority trees[END_REF] and [START_REF] Panholzer | Average-case analysis of priority trees: a structure for priority queue administration[END_REF], and also the recurrences ( 12) and ( 14), hold for r = 0. Now we assume that formulae [START_REF] Kuba | Analysis of insertion costs in priority trees[END_REF] and ( 13) together with the recurrences of the appearing coefficients are proven for all 0 ≤ k < r with a given r ≥ 1. To show them also for r we use at first the recursive definition of S r (z) via ( 8) and compute by using the induction hypothesis:

1 1 -z H ′ r-1 (z) = 1 (1 -z) 4 2r-2 X l=0 α (l) r-1 " 2L(z) 2r-2-l + (2r -2 -l)L(z) 2r-3-l " + 1 1 -z 2r-4 X l=0 β (l) r-1 " -L(z) 2r-4-l + (2r -4 -l)L(z) 2r-5-l " , H k (z) L(z) r-k (1 -z) 2 = 2k X l=0 α (l) k 1 (1 -z) 4 L(z) r+k-l + 2k-2 X l=0 β (l) k 1 1 -z L(z) r+k-l-2 , for 0 ≤ k ≤ r -1.
Plugging in equation ( 8) these representations we get after collecting terms:

S r (z) = 1 (1 -z) 4 2r-1 l=0 L(z) 2r-1-l 4rα (l-1) r-1 + 2r(2r -l)α (l-2) r-1 + l k=0 2 r r-1-k α (l-k) r-1-k + l-1 k=0 2(k + 1) r r-1-k α (l-1-k) r-1-k (15) + 1 1 -z 2r-3 l=0 L(z) 2r-3-l -2rβ (l-1) r-1 + 2r(2r -2 -l)β (l-2) r-1 + l k=0 2 r r-1-k β (l-k) r-1-k + l-1 k=0 2(k + 1) r r-1-k β (l-1-k) r-1-k .
Extracting in equation ( 15) the coefficients from the powers of L(z) shows then the validity of the given formulae [START_REF] Pontryagin | Ordinary differential equations[END_REF] for γ (l) r and δ (l) r also for r ≥ 1.

To compute H r (z) using ( 9) we require the following antiderivative formulas (for integers m ≥ 0), which are obtained easily via integration by parts:

z t=0 1 1 -t L(t) m dt = 1 m + 1 L(z) m+1 , 1 (1 -z) 2 z t=0 (1 -t) 2 L(t) m dt = -(1 -z) m k=0 m k 3 k+1 L(z) m-k + 1 (1 -z) 2 m! 3 m+1 , (1 -z) z t=0 1 (1 -t) 4 L(t) m dt = 1 (1 -z) 2 m k=0 (-1) k m k 3 k+1 L(z) m-k + (1 -z) (-1) m+1 m! 3 m+1 .
Plugging in the representation (15) of S r (z) into the solution (9) for H r (z) gives then after a few manipulations and collecting terms:

H r (z) = γ (0) r 6r 1 (1 -z) 2 L(z) 2r - δ (0) r 3(2r -2) (1 -z)L(z) 2r-2 + 1 (1 -z) 2 2r-1 m=1 L(z) 2r-m γ (m) r 3(2r -m) + m-1 l=0 γ (l) r (-1) m-l (2r -1 -l) m-l-1 3 m-l+1 + 1 (1 -z) 2 2r-1 l=0 γ (l) r (-1) l (2r -1 -l)! 3 2r-l+1 + 2r-3 l=0 δ (l) r (2r -3 -l)! 3 2r-1-l + C r,1 (16)
+ (1 -z) 2r-3 m=1 L(z) 2r-2-m - δ (m) r 3(2r -2 -m) + m-1 l=0 - δ (l) r (2r -3 -l) m-l-1 3 m-l+1 + (1 -z) - 2r-1 l=0 γ (l) r (-1) l (2r -1 -l)! 3 2r-l+1 - 2r-3 l=0 δ (l) r (2r -3 -l)! 3 2r-1-l + C r,2 .
Extracting in equation ( 16) the coefficients from the powers of L(z) gives then the relations:

α (0) r = γ (0) r 6r , for r ≥ 1, α (m) r = γ (m) r 3(2r -m) + m-1 l=0 γ (l) r (-1) m-l (2r -1 -l) m-l-1 3 m-l+1 , for 1 ≤ m ≤ 2r -1, α (2r) r = 2r-1 l=0 γ (l) r (-1) l (2r -1 -l)! 3 2r-l+1 + 2r-3 l=0 δ (l) r (2r -3 -l)! 3 2r-1-l + C r,1 , β (0) r = - δ (0) r 6(r -1)
, for r ≥ 2,

β (m) r = - δ (m) r 3(2r -2 -m) + m-1 l=0 -δ (l) r (2r -3 -l) m-l-1 3 m-l+1 , for 1 ≤ m ≤ 2r -3, β (2r-2) r = - 2r-1 l=0 γ (l) r (-1) l (2r -1 -l)! 3 2r-l+1 - 2r-3 l=0 δ (l) r (2r -3 -l)! 3 2r-1-l + C r,2 .
Plugging in the already proved equations ( 14) for γ n involving higher order harmonic numbers (see [START_REF] Zave | A series expansion involving the harmonic numbers[END_REF]). The expectation E(A

[H]

n ) has been computed already in [START_REF] Panholzer | Average-case analysis of priority trees: a structure for priority queue administration[END_REF]:

E(A [H] n ) = n + 1 3n H 2 n + 2(2n + 5) 9n H n - n + 1 3n H (2) n - 13n + 1 27n , for n ≥ 2, E(A [H] 1 ) = 1.

This immediately gives E(A [H]

n ) ∼ 1 3 log 2 n as asymptotic equivalent of the expectation. A (somewhat lengthy) exact formula for the variance V(A [12, p. 47], which gives the asymptotic equivalent V(A

[H] n ) appears in
[H] n ) ∼ 10
81 log 3 n.

Description of the coefficients α (m) r

Of great importance in our proof of Theorem 1 is a quite detailed description of the structure of the coefficients α

α (m) r = 1 3 r r ⌊ m+1 2 ⌋ Pol r (2m -⌊ m+1 2 ⌋). (17a)
Moreover, the leading coefficients η (m) := [r 2m ]3 r α (m) r are given by

η (m) = 5 9 m m! . ( 17b
)
Remark: Equation (17a) is obviously equivalent to the formulation that for every m there exist constants c m,i , 0 ≤ i ≤ 2m -⌊ m+1 2 ⌋, such that for all r ≥ 0:

α (m) r = 1 3 r r ⌊ m+1 2 ⌋ 2m-⌊ m+1 2 ⌋ i=0 c m,i r 2m-⌊ m+1 2 ⌋-i .
Thus, for all i ≥ 0, one can define functions c i (m), with m ∈ N, via:

c i (m) := c m,i , for 2m -⌊ m+1 2 ⌋ ≥ i, 0, otherwise,
and obtains the following lemma equivalent to Lemma 6.

Lemma 7 There exist functions c 0 (m), c 1 (m), c 2 (m), . . . , such that for all m ≥ 0, r ≥ 0 the coefficients α (m) r are given as follows: is given by

α (m) r = 1 3 r r ⌊ m+1 2 ⌋ 2m-⌊ m+1 2 ⌋ i=0 c i (m) r 2m-⌊ m+1 2 ⌋-i . (18a
η (m) = 5 9 m m! . ( 18b
)
The formulation used in Lemma 7 has the advantage that we have indeed a description of the coefficients α (m) r valid for all m ≥ 0, r ≥ 0. However, the formulation used in Lemma 6 is the direct outcome of the proof by induction carried out in the following.

Proof: We use induction on m.

Step 0: The initial step. For m = 0 we have due to (12a) the recurrence for m fixed as a function of r. First we write recurrence (12b), which holds for m ≤ 2r -1, as

α (0) r = 1 3 α (0) r-1 , for r ≥ 1, α (0)
α (m) r = 2r 3(2r -m) α (m) r-1 + 1 3(2r -m) 4rα (m-1) r-1 + 2r(2r -m)α (m-2) r-1 + m k=1 2 r r-1-k α (m-k) r-1-k + m-1 k=0 2(k + 1) r r-1-k α (m-1-k) r-1-k (19) + m-1 l=0 (-1) m-l (2r -1 -l) m-l-1 3 m-l+1 4rα (l-1) r-1 + 2r(2r -l)α (l-2) r-1 + l k=0 2 r r-1-k α (l-k) r-1-k + l-1 k=0 2(k + 1) r r-1-k α (l-1-k) r-1-k .
Step 2: Simplifying the recurrence. In the following we will examine every term of the inhomogeneous part of this first order linear recurrence for α (m) r using the induction hypothesis, where we consider m as fixed as mentioned before. We start with

4rα (m-1) r-1 = 1 3 r r(r -1) ⌊ m 2 ⌋ Pol r (2m -2 -⌊ m 2 ⌋) = 1 3 r r 1+⌊ m 2 ⌋ Pol r (2m -2 -⌊ m 2 ⌋), (20)
2r(2r -m)α (m-2) r-1 = 1 3 r r(r -m 2 )(r -1) ⌊ m-1 2 ⌋ Pol r (2m -4 -⌊ m-1 2 ⌋) = 1 3 r (r -m 2 )r 1+⌊ m-1 2 ⌋ Pol r (2m -4 -⌊ m-1 2 ⌋) = 1 3 r r 1+⌊ m 2 ⌋ Pol r (2m -3 -⌊ m 2 ⌋), (21)
where we combined in the last equation the cases m even and m odd.

Next we consider

2 r r -1 -k α (m-k) r-1-k = 1 3 r r 1+k (r -1 -k) ⌊ m-k+1 2 ⌋ Pol r (2m -2k -⌊ m-k+1 2 ⌋) = 1 3 r r k+1+⌊ m-k+1 2 ⌋ Pol r (2m -2k -⌊ m-k+1 2 ⌋) = 1 3 r r 2+⌊ m 2 ⌋ Pol r (k + 1 + ⌊ m-k+1 2 ⌋ -2 -⌊ m 2 ⌋ + 2m -2k -⌊ m-k+1 2 ⌋) = 1 3 r r 2+⌊ m 2 ⌋ Pol r (2m -1 -k -⌊ m 2 ⌋), for 1 ≤ k ≤ m.
Thus we get

m k=1 2 r r-1-k α (m-k) r-1-k = 1 3 r r 2+⌊ m 2 ⌋ Pol r (2m -2 -⌊ m 2 ⌋).
For computing the leading coefficient η (m) it is necessary to determine the leading coefficient of the appearing polynomial. It is seen easily that only the case k = 1 gives a contribution and we obtain: 1) .

[r 2m ]3 r m k=1 2 r r-1-k α (m-k) r-1-k = 2[r 2m ]3 r r r-2 α (m-1) r-2 = [r 2m ]3 r r 2 1 3 r-2 (r -2) ⌊ m 2 ⌋ η (m-1) r 2m-2-⌊ m 2 ⌋ + Pol r (2m -3 -⌊ m 2 ⌋) = 9[r 2m ]r 2+⌊ m 2 ⌋ η (m-1) r 2m-2-⌊ m 2 ⌋ + Pol r (2m -3 -⌊ m 2 ⌋) = 9η (m-
Combining these computations we get

m k=1 2 r r-1-k α (m-k) r-1-k = 1 3 r r 2+⌊ m 2 ⌋ 9η (m-1) r 2m-2-⌊ m 2 ⌋ + Pol r (2m -3 -⌊ m 2 ⌋) .
One shows similarly that

2(k + 1) r r-1-k α (m-1-k) r-1-k = 1 3 r r 1+⌊ m 2 ⌋ Pol r (2m -2 -k -⌊ m 2 ⌋), for 0 ≤ k ≤ m -1,
and thus

m-1 k=0 2(k + 1) r r-1-k α (m-1-k) r-1-k = 1 3 r r 1+⌊ m 2 ⌋ Pol r (2m -2 -⌊ m 2 ⌋). ( 22
)
Next we consider for 0 ≤ l ≤ m -1:

4rα (l-1) r-1 = 1 3 r r(r -1) ⌊ l 2 ⌋ Pol r (2l -2 -⌊ l 2 ⌋) = 1 3 r r 1+⌊ l 2 ⌋ Pol r (2l -2 -⌊ l 2 ⌋),
and thus

(-1) m-l (2r -1 -l) m-l-1 3 m-l+1 4rα (l-1) r-1 = 1 3 r (2r -1 -l) m-l-1 r 1+⌊ l 2 ⌋ Pol r (2l -2 -⌊ l 2 ⌋).
We distinguish the cases l even and l odd. Fist we consider the case l even, where we use

⌊ l 2 ⌋+⌊ m-l-1 2 ⌋ = ⌊ m-1
2 ⌋ (for arbitrary integers m):

1 3 r (2r -1 -l) m-l-1 r 1+⌊ l 2 ⌋ Pol r (2l -2 -⌊ l 2 ⌋) = 1 3 r 2 m-l-1 (r -l+2 2 ) ⌊ m-l-1 2 ⌋ (r -l+1 2 ) m-l-1-⌊ m-l-1 2 ⌋ r 1+⌊ l 2 ⌋ Pol r (2l -2 -⌊ l 2 ⌋) = 1 3 r (r -1 -⌊ l 2 ⌋) ⌊ m-l-1 2 ⌋ r 1+⌊ l 2 ⌋ Pol r (m -l -1 -⌊ m-l-1 2 ⌋)Pol r (2l -2 -⌊ l 2 ⌋) = 1 3 r r 1+⌊ l 2 ⌋+⌊ m-l-1 2 ⌋ Pol r (m + l -3 -⌊ l 2 ⌋ -⌊ m-l-1 2 ⌋) = 1 3 r r ⌊ m+1 2 ⌋ Pol r (m + l -2 -⌊ m+1 2 ⌋).
Next we consider the case l odd, where we use

⌊ l 2 ⌋ + ⌊ m-l 2 ⌋ = ⌊ m-1
2 ⌋ (for arbitrary integers m):

1 3 r (2r -1 -l) m-l-1 r 1+⌊ l 2 ⌋ Pol r (2l -2 -⌊ l 2 ⌋) = 1 3 r 2 m-l-1 (r -l+1 2 ) ⌊ m-l 2 ⌋ (r -l+2 2 ) m-l-1-⌊ m-l 2 ⌋ r 1+⌊ l 2 ⌋ Pol r (2l -2 -⌊ l 2 ⌋) = 1 3 r (r -1 -⌊ l 2 ⌋) ⌊ m-l 2 ⌋ r 1+⌊ l 2 ⌋ Pol r (m -l -1 -⌊ m-l 2 ⌋)Pol r (2l -2 -⌊ l 2 ⌋)
and thus

m-1 l=0 (-1) m-l (2r -1 -l) m-l-1 3 m-l+1 l k=0 2 r r-1-k α (l-k) r-1-k = 1 3 r r ⌊ m+1 2 ⌋ Pol r (2m -1 -⌊ m+1 2 ⌋).
Here we are also interested in the leading coefficient of the polynomial, where it is seen easily that only the summand with k = 0 and l = m -1 gives a contribution. We compute

[r 2m-1 ]3 r m-1 l=0 (-1) m-l (2r -1 -l) m-l-1 3 m-l+1 l k=0 2 r r-1-k α (l-k) r-1-k = -[r 2m-1 ]3 r 2 9 r r-1 α (m-1) r-1 = -[r 2m-1 ] 2 3 r 1+⌊ m 2 ⌋ η (m-1) r 2m-2-⌊ m 2 ⌋ + Pol r (2m -3 -⌊ m 2 ⌋) = - 2 3 η (m-1) ,
and get thus the more detailed description

m-1 l=0 (-1) m-l (2r -1 -l) m-l-1 3 m-l+1 l k=0 2 r r-1-k α (l-k) r-1-k = 1 3 r r ⌊ m+1 2 ⌋ - 2 3 η (m-1) r 2m-1-⌊ m+1 2 ⌋ + Pol r (2m -2 -⌊ m+1 2 ⌋) . ( 25
)
The last term in ( 19) can be treated analogous to the previous cases and we get for 0 ≤ l ≤ m -1:

l-1 k=0 2(k + 1) r r -1 -k α (l-1-k) r-1-k = 1 3 r r 1+⌊ l 2 ⌋ Pol r (2l -2 -⌊ l 2 ⌋),
and further

m-1 l=0 (-1) m-l (2r -1 -l) m-l-1 3 m-l+1 l-1 k=0 2(k + 1) r r -1 -k α (l-1-k) r-1-k = 1 3 r r ⌊ m+1 2 ⌋ Pol r (2m -3 -⌊ m+1 2 ⌋). ( 26
)
Now we collect all terms using (20)-( 26) and obtain then from (19) the recurrence:

α (m) r = 2r 3(2r -m) α (m) r-1 + 1 3(2r -m) 1 3 r r 1+⌊ m 2 ⌋ 9η (m-1) r 2m-1-⌊ m 2 ⌋ + Pol r (2m -2 -⌊ m 2 ⌋) + 1 3 r r ⌊ m+1 2 ⌋ - 2 3 η (m-1) r 2m-1-⌊ m+1 2 ⌋ + Pol r (2m -2 -⌊ m+1 2 ⌋) . ( 27
)
With the substitution α(m)

r := 3 r α (m) r
we obtain after multiplying by 3 r the following recurrence which holds for 1 ≤ m ≤ 2r -1:

α(m) r = r r -m 2 α(m) r-1 + 1 r -m 2 r 1+⌊ m 2 ⌋ 3 2 η (m-1) r 2m-1-⌊ m 2 ⌋ + Pol r (2m -2 -⌊ m 2 ⌋) + r ⌊ m+1 2 ⌋ - 2 3 η (m-1) r 2m-1-⌊ m+1 2 ⌋ + Pol r (2m -2 -⌊ m+1 2 ⌋) (28)
We will now study this recurrence, where we have to distinguish the cases m even and m odd.

Step 3: Solving the recurrence for m even. We start with m even (and m > 0) and set m = 2q, where the recurrence (28) holds for all r > q. We get

α(2q) r = r r -q α(2q) r-1 + 1 r -q r 1+q 3 2 η (2q-1) r 3q-1 + Pol r (3q -2) + r q - 2 3 η (2q-1) r 3q-1 + Pol r (3q -2) = r r -q α(2q) r-1 + r q 5 6 η (2q-1) r 3q-1 + Pol r (3q -2) . ( 29
)
Dividing equation ( 29) by r q leads then for r > q to α(2q)

r r q = α(2q) r-1 (r -1) q + 5 6 η (2q-1) r 3q-1 + Pol r (3q -2) = α(2q) r-1 (r -1) q + 5 6 η (2q-1) r 3q-1 + Pol r (3q -2).
Now we write the appearing polynomial of degree 3q-2 in the basis of the falling factorials as 3q-2 l=0 c l r l with certain constants c l . After solving this recurrence by summation we get

α(2q) r r q = α(2q) q q q + r k=q+1 5 6 η (2q-1) k 3q-1 + r k=q+1 3q-2 l=0 c l k l = α (2q)
q q q + 5 6 η (2q-1) (r + 1) 3q -(q + 1) 3q 3q +

Pol r (3q-1) 3q-2 l=0 c l (r + 1) l+1 -(q + 1) l+1 l + 1 .

Since the polynomial in r of degree 3q -1 is zero at r = q we can write α(2q) r r q = α(2q) q q q + 5 6 η (2q-1) (r + 1) 3q -(q + 1) 3q 3q + (rq)Pol r (3q -2), and further

α(2q) r = r q α(2q) q q q + 5 18q η (2q-1) (r + 1) 3q -(q + 1) 3q + (r -q)Pol r (3q -2) . (30)
From the validity of the recurrence we get that this formula is valid for r > q. But when plugging in r = q, the second and third term of (30) vanish and only α(2q) q remains, thus the formula is also valid for r = q. Moreover, when plugging in values 0 ≤ r < q, the formula gives α(2q) r = 0 or equivalently α (2q) r = 0, which matches with the definition of the α (2q) r

. Thus the formula is actually true for all r ≥ 0, if m = 2q. After back substitution we can write (30) for even m > 0 as

α (m) r = 1 3 r r ⌊ m+1 2 ⌋ 5 9m η (m-1) r 2m-⌊ m+1 2 ⌋ + Pol r (2m -1 -⌊ m+1 2 ⌋) , (31a)
and get in this case the following recurrence for the leading coefficients η (m) :

η (m) = 5 9m η (m-1) . (31b)
Step 4: Solving the recurrence for m odd. The case m odd in recurrence (28) is studied next. We assume that m = 2q + 1, then we have for r > q:

α(2q+1) r = r r -q -1 2 α(2q+1) r-1 + 1 r -q -1 2 r 1+q 3 2 η (2q) r 3q+1 + Pol r (3q) + r 1+q - 2 3 η (2q) r 3q + Pol r (3q -1) = r r -q -1 2 α(2q+1) r-1 + r 1+q r -q -1 2 5 6 η (2q) r 3q+1 + Pol r (3q) . (32)
Multiplying (32) by the factor (r-q-1 2 ) r-q r r-q gives for r > q the recurrence α(2q+1)

r (r -q -1 2 ) r-q r r-q = α(2q+1) r-1 (r -1 -q -1 2 ) r-1-q (r -1) r-1-q + (r -1 -q -1 2 ) r-1-q r q+1 r r-q 5 6 η (2q) r 3q+1 + Pol r (3q) .
We write the polynomial of degree 3q as 3q l=0 c l r l with certain constants c l and obtain after solving this recurrence by summation the following formula which holds for r > q:

α(2q+1) r (r -q -1 2 ) r-q r r-q = α(2q+1) q (-1 2 ) 0 q 0 + r k=q+1 5 6 η (2q) (k -1 -q -1 2 ) k-1-q k q+1 k 3q+1 k k-q + r k=q+1 (k -1 -q -1 2 ) k-1-q k q+1 k k-q 3q l=0 c l k l . Since α(2q+1) q = 0 or equivalently α (2q+1) q
= 0 per definition, we obtain for r > q the formula α(2q+1)

r = r r-q (r -q -1 2 ) r-q r k=q+1 5 6 η (2q) (k -1 -q -1 2 ) k-1-q k q+1 k 3q+1 k k-q + r r-q (r -q -1 2 ) r-q r k=q+1 (k -1 -q -1 2 ) k-1-q k q+1 k k-q 3q l=0 c l k l = r k=q+1 5η (2q) r r+q+1-k k 3q+1 6(r -q -1 2 ) r+1-k + r k=q+1 r r+q+1-k (r -q -1 2 ) r+1-k 3q l=0 c l k l ,
where we use here and in the following computations the identity x m+n = x m (xm) n repeatedly. After shifting k by -q -1 and making a base change to the falling factorials we get the following expression with certain constants d l :

α(2q+1) r = 5 6 η (2q) r-q-1 k=0 r r-k k 3q+1 (r -q -1 2 ) r-q-k + 3q l=0 d l r-q-1 k=0 r r-k k l (r -q -1 2 ) r-q-k = 5 6 η (2q) r-q-1 k=0 r r+3q+1-k (r -q -1 2 ) r-q-k + 3q l=0 d l r-q-1 k=0 r r+l-k (r -q -1 2 ) r-q-k = 5η (2q) r! 6(r -q -1 2 ) r-q r-q-1 k=0 (k -1 2 ) k k 3q+1 k! + 3q l=0 d l r! (r -q -1 2 ) r-q r-q-1 k=0 (k -1 2 ) k k l k! . (33)
To evaluate the sums in (33) we use the identity (for s a non-negative integer, where D z denotes the differential operator with respect to z):

n k=0 (k -1 2 ) k k s k! = [z n ] z s 1 -z D s z 1 √ 1 -z = [z n ](s -1 2 ) s z s (1 -z) s+ 3 2 = (s -1 2 ) s (n + 1 2 ) n-s n s n! .
We get then from equation (33):

α(2q+1) r = 5η (2q) r!(3q + 1 2 ) 3q+1 (r -q -1 2 ) r-4q-2 (r -q -1) 3q+1 6(r -q -1 2 ) r-q (r -q -1)! + 3q l=0 d l r!(l -1 2 ) l (r -q -1 2 ) r-q-1-l (r -q -1) l (r -q -1
2 ) r-q (rq -1)! , and due to obvious simplifications the following result, which holds for r > q:

α(2q+1) r = 5η (2q) 6 (3q + 1 2 ) 3q+1 (3q + 3 2 ) 3q+2 r q+1 (r -q -1) 3q+1 + 3q l=0 d l (l -1 2 ) l (l + 1 2 ) l+1 r q+1 (r -q -1) l = 5η (2q) 6(3q + 3 2 ) r q+1 (r -q -1) 3q+1 + 3q l=0 d l l + 1 2 r q+1 (r -q -1) l = r q+1 5η (2q) 9(2q + 1) (r -q -1) 3q+1 + Pol r (3q) = r q+1 5η (2q) 9(2q + 1) r 3q+1 + Pol r (3q) . (34)
But this formula (34) gives α(2q+1) r = 0 or equivalently α

= 0 for all r ≤ q, and this matches with the definition of α (2q+1) r . Thus (34) holds for all r ≥ 0. Back substitution leads thus for odd m to

α (m) r = 1 3 r r ⌊ m+1 2 ⌋ 5η (m-1) 9m r 2m-⌊ m+1 2 ⌋ + Pol r (2m -1 -⌊ m+1 2 ⌋) , (35a)
and we get in this case the following recurrence for the leading coefficient η (m) :

η (m) = 5η (m-1) 9m . (35b)
Step 5: The leading coefficients. Therefore the only thing remaining in the proof of Lemma 6 is to show formula (17b) for η (m) , but due to formulae (31b) and (35b) together with the initial value η (0) = 1 we obtain finally

η (m) = 5 9 m m! . (36)
A r (z) = 2r m=0 a (m) r 1 (1 -z) 2 L(z) 2r-m + O 1 1 -z .
The coefficients a

a (m) r = 1 3 r r ⌊ m+1 2 ⌋ η (m) r 2m-⌊ m+1 2 ⌋ + Pol r (2m -1 -⌊ m+1 2 ⌋) . (37)
Remark: Again one could also use the following description of the coefficients a

(m)
r , which is equivalent to the formulation given above: there exist functions c0 (m), c1 (m), c2 (m), . . . , such that for all m ≥ 0, r ≥ 0 the coefficients a (m) r are given as follows: appearing there we obtain further the following local expansion in a complex neighbourhood of z = 1:

a (m) r = 1 3 r r ⌊ m+1 2 ⌋ 2m-⌊ m+1 2 ⌋ i=0 ci (m) r 2m-⌊ m+1 2 ⌋-i ,
A r (z) = 2r m=0 α (m) r 1 1 -z z t=0 1 (1 -t) 2 L(t) 2r-m dt + O 1 1 -z . ( 38
)
Since integration by parts gives

1 1 -z z t=0 1 (1 -t) 2 L(t) 2r-m dt = 1 (1 -z) 2 2r-m k=0 (-1) k (2r -m) k L(z) 2r-m-k - 1 1 -z (-1) 2r-m (2r -m)!,
we get from (38) after easy manipulations

A r (z) = 2r m=0 α (m) r 1 (1 -z) 2 2r-m k=0 (-1) k (2r -m) k L(z) 2r-m-k + O 1 1 -z = 1 (1 -z) 2 2r m=0 L(z) 2r-m m k=0 (-1) m-k (2r -k) m-k α (k) r + O 1 1 -z .
This leads to the stated asymptotic expansion of A r (z) in Lemma 8 with coefficients

a (m) r = m k=0 (-1) m-k (2r -k) m-k α (k) r . (39)
Using the representation α

(k) r = 1 3 r r ⌊ k+1 2 ⌋ Pol r (2k -⌊ k+1 2
⌋) obtained in Lemma 6 one gets after distinguishing the cases k even and k odd for 0 ≤ k ≤ m:

(-1) m-k (2r -k) m-k α (k) r = 1 3 r r ⌊ m+1 2 ⌋ Pol r (m + k -⌊ m+1 2 ⌋),
and equation (39) leads to

a (m) r = m k=0 (-1) m-k (2r -k) m-k α (k) r = 1 3 r r ⌊ m+1 2 ⌋ Pol r (2m -⌊ m+1 2 ⌋). (40)
It remains to examine the leading coefficient, where it turns out that only the summand k = m gives a contribution, and by using equation (17b) we get

[r 2m ]3 r a (m) r = [r 2m ] m k=0 (-1) m-k (2r -k) m-k 3 r α (m) r = [r 2m ]3 r α (m) r = η (m) = 5 9 m m! .
This completes the proof of Lemma 8. ✷

The r-th centered moments of A [H] n

The last step is to compute the asymptotic growth of the r-th centered moments E A

[H] n -1 3 log 2 n r .
Lemma 9 The r-th centered and normalized moments of A

[H] n satisfy, for r fixed:

E   A [H] n -1 3 log 2 n 10 81 log 3 n r   = (2m)! 2 m m! + O 1 log n , if r = 2m even, O 1 √ log n , if r odd.
Proof: The basic thing to compute these moments is of course extracting coefficients from the generating functions A r (z) asymptotically via singularity analysis, which leads to asymptotic expansions for the factorial moments:

E A [H] n r = 1 n [z n ]A r (z).
We will require here the full expansion given in [5, p. 227] as Theorem 3A to get (ǫ denotes an arbitrarily small constant > 0):

1 n [z n ] 1 (1 -z) 2 L(z) m = m k=0 m k κ k (log n) m-k + O 1 n 1-ǫ , (41)
where the constants κ k are given as follows (it is here important that they are not depending on m):

κ k = (-1) k d k ds k 1 Γ(-s) s=-2 .
In particular it holds that κ 0 = 1. This expansion is necessary since every term of A k (z), 0 ≤ k ≤ r, in the asymptotic expansion in Lemma 8 gives a contribution to the r-th centered moment E A

E A [H] n l = 2l j=0 a (j) l 1 n [z n ] 1 (1 -z) 2 L(z) 2l-j + O 1 n = 2l j=0 a (j) l 2l-j i=0 κ i 2l -j i (log n) 2l-j-i + O 1 n 1-ǫ = 2l m=0 (log n) 2l-m m j=0 a (j) l 2l -j m -j κ m-j + O 1 n 1-ǫ . (42)
The ordinary moments of A

[H]

n are of course related to the corresponding factorial moments via

E A [H] n k = k l=0 k l E A [H] n l = k l=0 k l 2l m=0 (log n) 2l-m m j=0 a (j) l 2l -j m -j κ m-j + O 1 n 1-ǫ , (43)
where n m denote the Stirling numbers of second kind.

Using (43) gives then the following expansion of the centered moments:

E A [H] n - 1 3 log 2 n r = r k=0 r k (-1) r-k 1 3 log 2 n r-k E A [H] n k (44) = r k=0 r k (-1) r-k 1 3 log 2 n r-k k l=0 k l 2l m=0 (log n) 2l-m m j=0 a (j) l 2l -j m -j κ m-j + O 1 n 1-ǫ .
The crucial step now is to control the massive cancellations appearing in (44). This is managed with the detailed description of the a (m) r given in Lemma 8. First we obtain after routine manipulations

E " `A[H] n - 1 3 log 2 n ´r" = r X k=0 `r k ´(-1) r-k (log n) 2r-2k 3 r-k k X l=0 ( k k -l ) 2k X m=2l (log n) 2k-m m-2l X j=0 a (j) k-l `2k-2l-j m-2l-j ´κm-2l-j + O `1 n 1-ǫ = r X k=0 `r k ´(-1) r-k 1 3 r 2k X m=0 (log n) 2r-m ⌊ m 2 ⌋ X l=0 ( k k -l ) m-2l X j=0 3 k a (j) k-l `2k-2l-j m-2l-j ´κm-2l-j + O `1 n 1-ǫ = 2r X m=0 (log n) 2r-m 1 3 r r X k=⌊ m+1 2 ⌋ `r k ´(-1) r-k ⌊ m 2 ⌋ X l=0 ( k k -l ) m-2l X j=0 3 k a (j) k-l `2k-2l-j m-2l-j ´κm-2l-j | {z } =: Sm(k) +O `1 n 1-ǫ ´. (45)
Now we have a closer look at the sum S m (k) in (45) for fixed m as a function of k. First we obtain for m, l, j fixed, with 0 ≤ j ≤ m -2l, after distinguishing the cases j even and j odd and using Lemma 8:

3 k a (j) k-l 2k -2l -j m -2l -j κ m-2l-j = (k -l) ⌊ j+1 2 ⌋ (2k -2l -j) m-2l-j Pol k (2j -⌊ j+1 2 ⌋) = (k -l) ⌊ m+1 2 ⌋-l Pol k (m + j -l -⌊ m+1 2
⌋), and thus for m, l fixed:

m-2l j=0 3 k a (j) k-l 2k -2l -j m -2l -j κ m-2l-j = (k -l) ⌊ m+1 2 ⌋-l Pol k (2m -3l -⌊ m+1 2 ⌋). (46)
Next we require the following property of the Stirling numbers of second kind k k-l for fixed l as a function of k: these functions are for every integer l ≥ 0 a polynomial in k of degree 2l with zeros 0, 1, . . . , l -1 (see [7, p. 271]), thus

k k -l = k l Pol k (l). (47)
Combining equations ( 46) and ( 47) gives for all m, l fixed, with 0 ≤ l ≤ ⌊ m 2 ⌋:

k k -l m-2l j=0 3 k a (j) k-l 2k -2l -j m -2l -j κ m-2l-j = k ⌊ m+1
and further that, for m fixed, S m (k) is a polynomial in k of degree (at most) 2m with the following factorization:

S m (k) = k ⌊ m+1 2 ⌋ Pol k (2m -⌊ m+1 2 ⌋). (48)
Of course there is again the equivalent formulation that there exist functions f 0 (m), f 1 (m), f 2 (m), . . . , such that we have for all m ≥ 0, k ≥ 0 the representation

S m (k) = k ⌊ m+1 2 ⌋ 2m-⌊ m+1 2 ⌋ i=0 f i (m) k 2m-⌊ m+1 2 ⌋-i .
Later on we will require also the leading coefficient [k 2m ]S m (k) of S m (k), i.e., the function f 0 (m). It is seen easily from the computations above that the only summand that gives a contribution to the main term of order k 2m is obtained for the values l = 0 and j = m in the sum defining S m (k). We get thus for all m ≥ 0:

[k 2m ]S m (k) = [k 2m ] ⌊ m 2 ⌋ l=0 k k -l m-2l j=0 3 k a (j) k-l 2k-2l-j m-2l-j κ m-2l-j = [k 2m ] k k 3 k a (m) k 2k-m 0 κ 0 = [k 2m ]3 k a (m) k = η (m) = 5 9 m m! . (49)
Now we evaluate the following sum F (r, m) in equation ( 45) for arbitrary pairs (r, m) with r ≥ 0, m ≥ 0:

F (r, m) := r k=⌊ m+1 2 ⌋ r k (-1) r-k S m (k).
First we use that S m (k) has the factor k ⌊ m+1

2 ⌋ and it holds thus S m (k) = 0 for 0 ≤ k < ⌊ m+1 2 ⌋, which means that we can sum over the whole range (iii) from 0 to r:

F (r, m) = r k=0 r k (-1) r-k S m (k). (50)
Next we use the calculus of higher order differences (see, e.g., [START_REF] Graham | Concrete mathematics[END_REF]); that means we can interpret this sum as

F (r, m) = r k=0 r k (-1) r-k S m (k) = ∆ r S m (x) x=0 ,
where ∆ denotes the forward difference operator (∆f

(x) := f (x + 1) -f (x) for functions f (x)). If f (x) is a polynomial in x of degree at most r, i.e., f (x) = r l=0 f l x l , it holds then that r k=0 r k (-1) r-k f (k) = ∆ r f (x) x=0 = r!f r . (51)
(iii) Now it becomes apparent, why we had to give attention to the factor r But due to equation (48), for arbitrary m ≥ 0, S m (x) is a polynomial in x of degree 2m, which implies that the r-th power of the difference operator annihilates S m (x) for all pairs (r, m), which satisfy r > 2m, i.e.,

r k=0 r k (-1) r-k S m (k) = 0, (52)
whenever r > 2m or equivalently m ≤ ⌊ r-1 2 ⌋. Thus the first non-vanishing term in the expansion of E A

[H] n -1 3 log 2 n r as given in (45) can occur for m = ⌊ r+1 2 ⌋, which gives after distinguishing the cases r even and r odd:

E A [H] n - 1 3 log 2 n r = O (log n) 3r 2 , for r even, O (log n) 3r-1 2
, for r odd.

To obtain the leading coefficient in this expansion for r even we use again formula (51) together with (49) and get for r = 2m:

1 3 2m 2m k=0 2m k (-1) 2m-k S m (k) = 1 3 2m (2m)![k 2m ]S m (k) = 1 9 m (2m)! η (m) = (2m)!( 10 81 ) m 2 m m! .
Expansion (45) gives then:

E A [H] n - 1 3 log 2 n r = (2m)! 2 m m! 10 81 m (log n) 3r 2 + O (log n) 3r 2 -1 , for r = 2m even, O (log n) 3r-1 2 , for r odd. (53)
Therefore normalization with the main term 10 81 log 3 n of the variance of A

Number of right edges to a random node

Due to the decomposition of the families A, B and C we obtain the following system of recurrences for the probabilities P{A

[R] n,j = m}, P{B [R] n,j = m} and P{C [R]
n,j = m}, which give the probabilities that the number of right edges on the path from the root to node j in a random generated object of size n are m (for 1 ≤ j ≤ n):

P{A [R] n,j = m} = 1 n 0 @ j-1 X k=1 P{C [R] n-k,j-k = m} + [[m = 0]] + n X k=j+1 P{B [R] k-1,j = m} 1 A ,
The corresponding homogeneous differential equation has the general solution

A [hom] (z, v) = C 1 (1 -z) -1 2 - √ 1+8v 2 + C 2 (1 -z) -1 2 + √ 1+8v 2
, with arbitrary constants C 1 , C 2 . Variation of the parameters method gives after adapting to the initial conditions the solution

A(z, v) = 1 + 2v + √ 1 + 8v 2v √ 1 + 8v (1-z) -1 2 - √ 1+8v 2 - 1 + 2v - √ 1 + 8v 2v √ 1 + 8v (1-z) -1 2 + √ 1+8v 2 - 1 v(1 -z) . (56)
Singularity analysis applied to equation (56) gives then immediately the following asymptotic expansion of the coefficients uniformly in a complex neighbourhood of v = 1 (ǫ denotes an arbitrary small constant > 0):

[z n ]A(z, v) = 1 + 2v + √ 1 + 8v 2v √ 1 + 8v Γ 1+ √ 1+8v 2 n √ 1+8v-1 2 1 + O 1 n 1-ǫ .
Thus we get the following asymptotic expansion of the moment generating function E e A [R] n s = 1 n [z n ]A(z, e s ), which holds uniformly in a neighbourhood of s = 0: .

E e A [R] n s = e U (s) log n+V (s) 1 + O 1 n 1-ǫ , (57a) with

(57b)

An application of the quasi-power theorem (see [START_REF] Hwang | On convergence rates in the central limit theorems for combinatorial structures[END_REF]) gives then with U ′ (0) = 2 3 and U ′′ (0) = 10 27 the stated central limit theorem for A 5 Number of descendants of a random node

A system of recurrences

Here we want to obtain a system of recurrences for the probabilities P{A n,j = m}, which give the probabilities that node j has exactly m descendants in a random generated object of size n of the families A, B and C for 1 ≤ j ≤ n. To obtain such equations from the combinatorial decomposition described in Figure 2 we will condition upon the event that the node with key j of object C is lying on the left path, i.e., node j is lying on the path from the root to the left leaf; we write j ∈ LP, or not, j ∈ LP. Furthermore we denote by q n,j the probability that node j in a random object of size n in family C is positioned on the left path, i.e., P{j ∈ LP(T ) : T a random object of size n in family C}. As already pointed out in [START_REF] Panholzer | Average-case analysis of priority trees: a structure for priority queue administration[END_REF] this is equivalent to the condition that node j is a left-to-right maximum in a random permutation of size n, thus q n,j = 1 nj + 1 . = m}z n v m , etc. with initial conditions A(0, v) = B(0, v) = C(0, v) = 0:

∂ ∂z A(z, v) = 1 1 -z C(z, v) + 1 1 -z B(z, v) + R(z, v), (59a)
∂ ∂z B(z, v) = 1 1 -z A(z, v) + 1 1 -z B(z, v) + v (1 -z)(1 -vz) , (59b)
∂ ∂z C(z, v) = 1 1 -z C(z, v) + 1 1 -z A(z, v) + R(z, v), (59c)
where R(z, v) is given as

R(z, v) = v (1 -z)(1 -vz) + v z(1 -vz) 2 L(z) + v 2 z(1 -v)(1 -vz) L(z) - v z(1 -v)(1 -z) L(z).
With the substitutions C(z, v) = (1z)C(z, v) and B(z, v) = (1z)B(z, v) we obtain after adding equations (59b) and (59c):

∂ ∂z A(z, v) = 1 (1 -z) 2 B(z, v) + C(z, v) + R(z, v), ∂ ∂z B(z, v) + C(z, v) = 2A(z, v) + (1 -z) v (1 -z)(1 -vz) + R(z, v) ,
and a simple elimination leads to the following second order linear differential equation of Cauchy-Euler type for A(z, v): The general solution of the corresponding homogeneous differential equation is given by

∂ 2 ∂z 2 A(z, v) - 2 1 -z ∂ ∂z A(z, v) - 2 (1 -z) 2 A(z, v) = 2v 2 (1 -z)(1 -vz) 2 - 2v 2 (1 -v) (1 -z)(1 -vz)
A [h] (z, v) = C 1 (v) 1 (1 -z) 2 + C 2 (v)(1 -z),
with arbitrary functions C 1 (v) and C 2 (v). Variation of the parameters method gives then after adapting to the initial conditions the solution of differential equation (60):

A(z, v) = 1 3(1 -z) 2 z t=0 2v 2 (1 -t) 2 (1 -vt) 2 - 2v 2 (1 -v)(1 -t) 2 (1 -vt) 3 L(t) dt (61) - 1 -z 3 z t=0 2v 2 (1 -t)(1 -vt) 2 - 2v 2 (1 -v) (1 -t)(1 -vt) 3 L(t) dt + v 3(1 -z) 2 - v(1 -z) 3 .

The limiting distribution

To characterize the limiting distribution of A

[D] n we will first compute an explicit formula for the probabilities P{A

[D] n = m}. To do this we will extract coefficients from (61), where we require the following formulae, which are obtained by routine (but somehow lengthy) computations. It holds then for m ≥ 2:

[z n v m ] 1 (1 -z) 2 Z z t=0 2v 2 (1 -t) 2 (1 -vt) 2 dt = 4n m(m + 1) + 4 m(m + 1)
,

[z n v m ](1 -z) Z z t=0 2v 2 (1 -t)(1 -vt) 2 dt = - 2(m -1) n(n -1)
,

[z n v m ] 1 (1 -z) 2 Z z t=0 2v 2 (1 -v)(1 -t) 2
(1vt) 3 L(t)dt Using these equations we obtain from (61) the following explicit formula for the probabilities P{A H n -H m (62)

n

  of a random node, the number of right edges A [R] n to a random node and the number of descendants A [D]

Fig. 2 :

 2 Fig. 2: Decomposition of the families A, B and C according to the first element.

  ⌋), with the same leading coefficients η (m) of the polynomials occurring in a

n

  = m}. From this explicit formula we obtain immediately the first part of Theorem 3. To obtain the asymptotic formulae for the r-th moments of A [D] n as given in the second part of Theorem 3 we expand the solution of A(z, v) in terms of w := v -1 and determine for fixed r the asymptotic expansion of [w r ]A(z, v) around the dominant singularity z = 1.

,

  for 0 ≤ m ≤ 2r -1, are required. Thus in particular the recurrences for β (m) r

  m < 0 or r < 0 or m > 2r, and that β (m) r = 0 if m < 0 or r ≤ 0 or m > 2r -2. Remark: Due to the convention b k=a f (k) = 0 if b < a used throughout this paper Lemma 5 gives in particular the values α (0) 0 = C 0,1 = 1 and β (0) 0 = 0. Proof: To show this result we use induction on r,

r

  also for r ≥ 1. ✷ Lemma 5 (together with equation (5)) allows now to compute at least in principle closed formulae for the moments of A[H]

Lemma 6

 6 m fixed as a function of r. This is done in the following lemma, where we recall the abbreviation Pol x (d) for a certain polynomial in x of degree at most d, which can vary in every occurrence of Pol x (d). If d < 0 then we use the convention that Pol x (d) = 0. The coefficients α (m) r are for m fixed and r ≥ 0 given by

)

  Moreover, the function η (m) := c 0 (m) = [r 2m ]3 r α (m) r

0 = 1 , 3 r 1 :

 131 for r ≥ 0. Thus the given representation (17) is true for m = 0.Step The recurrence. Now we assume that for 0 ≤ k < m and given m ≥ 1 the representation (17) holds. We will now study the coefficients α (m) r

✷ 3 . 5 Lemma 8

 358 Asymptotic expansion of A r (z) Lemma 6 leads easily to a description of the generating functions of the factorial moments of A The generating functions A r (z) := ∂ r ∂v r A(z, v) v=1 = n≥1 n E A [H] n r z n have the following local expansion around the dominant singularity z = 1:

9 m

 9 for m fixed and r ≥ 0 given by the following formula, where the same leading coefficients η (m) = 5 m! as in (17b) appear:

9 m

 9 where the function c0 (m) is given by c0(m) = η (m) = 5 m! . Proof: Since A(z, v) = 1 1-z z t=0 H(t, v)dt due to (5), we obtain A r (z) = 1 1z

1 3

 1 log 2 n r , and only a very detailed knowledge about the structure of the coefficients of A k (z) can explain the huge cancellations. Using equation (41), Lemma 8 leads to

8 . 3 r

 83 It is considerably less effort in Lemma 6 and Lemma 8 to show only the representation a (m) r = 1 Pol r (2m) for m ≤ 2r -1, but this is not sufficient for the proof.

n 1 3 log 2 n √ 10 81 log 3 n

 1103 proves this lemma. ✷ Thus we have shown in Lemma 9 that the r-th moments of A[H] nconverge to the r-th moments of a standard normally distributed random variable X withE X r = (2m)!2 m m! , for r = 2m even, 0 for r odd.Together with the Theorem of Fréchet and Shohat this shows the limiting distribution result for A[H] n stated as Theorem 1.

  = m}, P{B [D]n,j = m} and P{C[D]

  initial conditions A(0, u, v) = B(0, u, v) = C(0, u, v) = 0: , u, v) + R(z, u, v), with R(z, u, v) = uv (1z)(1uvz) + uv z(1uvz) 2 L(z) + uv 2 z(1v)(1uvz) L(z) -uv z(1v)(1uz) L(z).This leads to the following system of differential equations for the generating functions A(z, v):= A(z, 1, v) = n≥1 m≥0 n P{A [D] n

  3 L(z), (60) with initial conditions A(0, v) = 0 and ∂ ∂z A(z, v) z=0 = v resulting from P{A

1 `

 1 Hn -Hm-1 ´i + h nm + 1 m Hn-m -n + 1 m `Hn -Hm ´i« , [z n v m ](1z) Z z t=0 2v 2 (1v) (1t)(1vt) 3 L(t)dt

1 n

 1 [z n v m ]A(z, v): P{A [D] n = m} = 2(nm)(n 2 + mn + m 2 -1) 3n 2 (n -1)m(m + 1) H n-m -2(n + 1) 3nm(m + 1)

  and B n and C n are defined as the corresponding random variables for objects in B and C. To obtain them we introduce

	object of C with nodes k+1, . . . , n	✍✌ ✎☞ +∞
	✍✌ ✎☞ k	✍✌ ✎☞ k	object of A with nodes k+1, . . . , n
	object of B with nodes 1, . . . , k-1	object of B with nodes 1, . . . , k-1
	Decomposition of family A	Decomposition of family B
		object of C
		with nodes k+1, . . . , n
	✍✌ ✎☞ k
	object of A with nodes 1, . . . , k-1 Decomposition of family C ✎☞ -∞ ✍✌

⌋ Pol k (2m -2l -⌊ m+1 2 ⌋),

Acknowledgement

The author thanks the anonymous referees for their comments made on an earlier version of that manuscript helping to improve the presentation of the contents.

This work was supported by the Austrian Science Foundation FWF, grant S9608-N13, and by the ÖAD funded Austrian-French exchange program "Amadée".

1365-8050

Thus we get for all 0 ≤ l ≤ m -1 the equation (-1) m-l (2r -1l) m-l-1 3 m-l+1 4rα

(l-1)

which gives m-1 l=0

(-1) m-l (2r -1l) m-l-1 3 m-l+1 4rα

(l-1)

We further have for 0 ≤ l ≤ m -1:

r-1 = 1 3 r r(r -l 2 )(r -1)

where the last equation is obtained when distinguishing the cases l even and l odd. Similar to the last computation we obtain for 0 ≤ l ≤ m -1 when considering the cases l even and l odd separately:

and further

Next we get for 0 ≤ l ≤ m -1 due to considerations as above:

We are now interested in

Again when distinguishing the cases l even and l odd we obtain for 0 ≤ l ≤ m -1:

Introducing the generating function A(z, u, v) := n≥1 1≤j≤n m≥0 P{A

[R]

n,j = m}z n u j v m , and the corresponding functions B(z, u, v) and C(z, u, v), we can convert this system of recurrences into the following system of linear differential equations:

We obtain thus the following system of differential equations for the generating function

and the corresponding auxiliary functions B(z, v) and

With the substitutions C(z, v) := (1z)C(z, v) and B(z, v) := (1z)B(z, v) we obtain after adding equations (54b) and (54c):

Now a simple elimination leads to the following second order linear differential equation of Cauchy-Euler type for A(z, v):

We get then directly from Figure 2 the recursive equations

If node j is lying on the left path in an object of C it has exactly j descendants, namely the nodes {1, 2, . . . , j}. We get therefore

Together with

n,j = m | j ∈ LP}, we get the following system of recurrences:

The generating functions approach

Introducing the generating functions A(z, u, v) := n≥1 1≤j≤n m≥0 P{A

[D]

n,j = m}z n u j v m , etc. we get from the system of recurrences (58) the following system of linear differential equations with

, for m ≥ 1.

With the asymptotic expansion H n = log n + γ + O 1 n of the harmonic numbers we get from (62) the discrete limiting distribution of A

n given in Theorem 3.

The r-th moments

To compute the r-th moments of A

[D]

n we define w := v -1 and use

Thus we want to extract the coefficients [z n w r ]A(z, v) asymptotically for fixed r and n → ∞. To do this we use the following formulae:

Using the asymptotic expansions (63) we get from (61): , the second part of Theorem 3 is also proven.

Conclusion

Priority trees are an easy-to-describe binary tree model, where the behaviour of basic random nodeparameters is fundamentally different from the binary search tree model and the Catalan tree model.


Dariusz Dereniowski

Adam Nadolski
email: nadolski@eti.pg.gda.pl

A note on compact and compact circular edge-colorings of graphs †

Keywords: edge-weighted graph, compact edge-coloring, interval edge-coloring, compact circular edge-coloring, NP-completeness, approximation algorithm

We study two variants of edge-coloring of edge-weighted graphs, namely compact edge-coloring and circular compact edge-coloring. First, we discuss relations between these two coloring models. We prove that every outerplanar bipartite graph admits a compact edge-coloring and that the decision problem of the existence of compact circular edge-coloring is NP-complete in general. Then we provide a polynomial time 1.5-approximation algorithm and pseudo-polynomial exact algorithm for compact circular coloring of odd cycles and prove that it is NP-hard to optimally color these graphs. Finally, we prove that if a path P2 is joined by an edge to an odd cycle then the problem of the existence of a compact circular coloring becomes NP-complete.

Introduction

In the paper we consider two variants of edge-coloring of weighted graphs. Let (G, w) be a weighted graph, where G = (V (G), E(G)) and w : E(G) → N. For a given positive real r denote by I r the interval [0, r] and by C r a circle of circumference r. Moreover, let J (I r ) and A(C r ) denote the set of all open subintervals of I r and the set of all open arcs of C r , respectively. Then, an edge r-coloring of G is an assignment c : E(G) → J (I r ) such that |c(e)| = w(e) for every edge e and c(e 1 ) ∩ c(e 2 ) = ∅ for every pair of adjacent edges e 1 , e 2 . For a vertex v ∈ V (G) let B v denote the set of the edges that are incident to v. An edge r-coloring is said to be compact at v, if e∈Bv c(e), namely the closure of the union of the intervals assigned to the edges incident to v, forms an interval. An edge r-coloring that is compact at every vertex v ∈ V (G) is said to be compact.

Notice that a circle C r can be considered as an interval I r with identified endpoints. In this way J (I r ) is transformed into a subset of A(C r ). Therefore, these arcs can be denoted as (a, b), where a < b. The arcs of A(C r ) that are not inherited from J (I r ) are the open arcs containing point 0, therefore they can be (2, 0.5)

Fig. 1: An optimal circular edge-coloring of C5.

denoted as (a, b), where b < a. These notions motivate us to transform the definition of edge-coloring in such a way that arcs of a circle, instead of intervals, are assigned to the edges. A circular edge r-coloring of (G, w) is a mapping c : E(G) → A(C r ) such that |c(e)| = w(e) for every edge e and c(e 1 )∩c(e 2 ) = ∅ for every pair of adjacent edges e 1 , e 2 . In the same way as above we provide the definition of compactness for this coloring model. Namely, a circular edge r-coloring is said to be compact at vertex v ∈ V (G) if e∈Bv c(e) forms an arc of C r or is equal to C r . Finally, a circular edge r-coloring is compact if it is compact at every vertex v ∈ V (G).

In the paper we consider edge-colorings only, therefore we often write circular r-coloring and rcoloring instead of circular edge r-coloring and edge r-coloring, respectively. Moreover, in the case r-coloring could be misled with circular r-coloring , we write standard r-coloring instead of r-coloring.

At this point we would like to notice that the restriction of the edge weights to positive integers is for convenience merely. Suppose the weights were rational and c was a standard or circular r-coloring. Then, we could multiply all the weights by M , the least common multiple of the denominators of the weights, making all of the weights positive integers. If we also multiplied by M the endpoints of all the colors assigned by c, we would obtain a standard or circular (M • r)-coloring. Moreover, this transformation would preserve the compactness property in both coloring models.

In both cases our objective is to minimize the parameter r, namely the length of an interval or the length of a circle. In the following, we name the parameter r as the number of colors. Clearly, every r-coloring can be transformed into a circular r-coloring. However, the opposite transformation is not always possible. Fig. 1 depicts an optimal circular edge-coloring of C 5 with all weights equal to 1 [START_REF] Hackmann | The circular chromatic index[END_REF]. This coloring uses 2.5 colors, while a standard coloring would require at least 3 colors. Notice that the transformation of an r-coloring into a circular r-coloring preserves the property of compactness.

Both coloring variants can be applied in scheduling theory to represent schedules with no-idles in models such as biprocessor tasks system or open shop. Consider an automated production system in which there is a set of tasks, each requiring the simultaneous use of two preassigned machines (processors, tools, etc.). This situation can be modeled by a graph, whose vertices correspond to the machines and the edges correspond to the tasks. Then, each schedule of makespan r can be represented by an r-coloring of such a graph. Moreover, if the production process proceeds in a periodic way, i.e. whenever one set of tasks is completed, the following one is started immediately, the schedule is modeled by a circular edge-coloring. In some industrial applications, like chemistry or metallurgy, the processors have to work without idle times due to technological or economical constraints. It occurs that a schedule with no idles on all processors corresponds to a compact coloring in both standard and periodic setting. This motivates our considerations of compact coloring models. The reader interested further in relations between compact colorings and schedules fulfilling the no-idle constraint is referred to [START_REF] Giaro | Task Scheduling Without 2-Sided Waiting Periods on Dedicated Processors[END_REF][START_REF] Nadolski | Chromatic Scheduling in Cyclic Manufacturing Systems[END_REF][START_REF] Kubale | Chromatic scheduling in a cyclic open shop[END_REF][START_REF] Solot | Some graph-theoretical models for scheduling in automated production systems[END_REF] There are numerous papers on the problem of compact edge-coloring, often referred to as interval or consecutive edge-coloring. Surveys on this topic can be found in several books that deal with various problems in graph coloring [START_REF] Asratian | Bipartite Graphs and Their Applications[END_REF][START_REF] Giaro | Interval edge-coloring of graphs[END_REF][START_REF] Jensen | Graph Coloring Problems[END_REF]. It is known that not every graph admits a compact coloring even if all weights are equal to 1 and the problem of determining whether a given graph can be colored in a compact manner is NP-hard, even for bipartite graphs [START_REF] Sevastyanov | Interval colorability of the edges of a bipartite graph (in Russian)[END_REF]. In the case of arbitrary weights the same problem is NP-hard even for odd cycles [START_REF] Giaro | Task Scheduling Without 2-Sided Waiting Periods on Dedicated Processors[END_REF]. On the other hand, paths and even cycles admit compact edge-colorings. However, for these graphs an optimal compact coloring cannot be determined in polynomial time, unless P=NP [START_REF] Giaro | NP-hardness of compact scheduling in simplified open and flow shops European[END_REF].

The compact circular coloring variant has attained less attention in the literature. The paper [START_REF] Nadolski | Compact cyclic edge-coloring of graphs[END_REF] studies properties of this coloring model in the case of unit weights. The author constructed graphs, for which optimal compact circular colorings are determined and graphs, for which it is proved that there are no compact circular colorings. In the papers [START_REF] Solot | Compact cylindrical scheduling[END_REF][START_REF] Solot | Some graph-theoretical models for scheduling in automated production systems[END_REF] the authors consider compact circular coloring of bipartite graphs in the context of application of this coloring model in scheduling, in the cyclic version of open shop.

Clearly, no compact or compact circular r-coloring exists for r < ∆(G, w), where ∆(G, w) = max v∈V (G) { e∈Bv w(e)} denotes the weighted degree of (G, w). Below, we cite an interesting result used in the following sections, which classifies graphs for which there exists a compact circular r-coloring for every weight function w and every r ≥ ∆(G, w).

Theorem 1 ( [START_REF] Solot | Compact cylindrical scheduling[END_REF]) For every graph G the following two statements are equivalent:

(i) for every weight function w and every r ≥ ∆(G, w) there exists a compact circular r-coloring of (G, w);

(ii) G is bipartite and outerplanar.

This paper is organized as follows. In the next section (Sec. 2) we discuss the relations between compact and circular compact colorings. These considerations yield a characterization of the graphs which admit a standard compact coloring with arbitrary weights on the edges. Moreover, we prove that the decision problem of existence of a circular compact coloring is NP-complete. Then, we study the problem of compact circular coloring of odd cycles in Section 3. We prove that a compact circular coloring exists for every weighted odd cycle and provide an approximation algorithm. Moreover, we prove that an optimal coloring cannot be determined in polynomial time, unless P=NP and construct a pseudo-polynomial exact algorithm. Finally, we show that joining a path P 2 to a vertex of a cycle makes the problem of colorability NP-hard.

Relations between Standard and Circular Compact Colorings

As it was noticed in the introduction, a compact r-coloring can be transformed into compact circular rcoloring. The following proposition strengthens this statement. Its proof is based on the ideas presented in [START_REF] Nadolski | Compact cyclic edge-coloring of graphs[END_REF] for non-weighted colorings.

Proposition 2 Suppose that a graph G with a weight function w admits a compact standard edge rcoloring for some r ≥ ∆(G, w). Then there exists a compact circular s-coloring of (G, w) for every s ≥ ∆(G, w).

Proof: Let c be a compact r-coloring and let s ≥ ∆(G, w). For a given edge e let c 1 (e) and c 2 (e) denote the left and right endpoint of the interval c(e), respectively. Moreover, for x ≥ 0 we denote by [x] s the unique y ∈ [0, s), such that x = y + i • s for some integer i. We construct an assignment c : E(G) → A(C s ) given by the following formula

c(e) = ([c 1 (e)] s , [c 2 (e)] s ).
We claim that c is a compact circular s-coloring.

Clearly, |c(e)| = w(e) for every edge e. Let e 1 and e 2 be two adjacent edges. Without loss of generality suppose that c 1 (e 1 ) < c 2 (e 1 ) ≤ c 1 (e 2 ) < c 2 (e 2 ). Then, c 2 (e 2 ) ≤ c 1 (e 1 ) + ∆(G, w), since c is compact. This together with s ≥ ∆(G, w) yields c(e 1 ) ∩ c(e 2 ) = ∅, which proves that c is a circular s-coloring. The proof that c is compact is straightforward. ✷ Suppose that for a given weighted graph (G, w) we have a compact circular r-coloring for some r > e∈E(G) w(e). Then, there exists a point x ∈ C r such that x ∈ c(e) for any edge e. Without loss of generality we may assume that x = 0. Therefore, every arc c(e) can be transformed to an appropriate interval from J (I r ). In this way we construct an r-coloring of (G, w), which is compact. This gives us the following proposition.

Proposition 3 If for a given graph G and a weight function w there exists a compact circular r-coloring, where r > e∈E(G) w(e), then there exists a compact r-coloring of (G, w).

Propositions 2 and 3 together with Theorem 1 yield the following theorem.

Theorem 4 For every graph G the following two conditions are equivalent:

(i) for every weight function w there exists a compact r-coloring of (G, w) for some r ≥ ∆(G, w);

(ii) G is bipartite and outerplanar.

Proof: (i) ⇒ (ii): Let w be a given weight function. From (i) we obtain that (G, w) has a compact r-coloring for some r ≥ ∆(G, w), which together with Proposition 2 yields that (G, w) admits a compact circular s-coloring for every s ≥ ∆(G, w). Since w is arbitrary, Theorem 1 implies that G is both bipartite and outerplanar.

(ii) ⇒ (i): Let w be any weight function. Put r = e∈E(G) w(e) + 1. From Theorem 1 it follows that there exists a compact circular r-coloring. Proposition 3 implies that there exists an r-coloring of (G, w) that is compact. ✷

Note that the proof of Theorem 1 from [START_REF] Solot | Compact cylindrical scheduling[END_REF] together with the proof of Proposition 3 leads to a polynomialtime algorithm for compact coloring of weighted outerplanar bipartite graphs. On the other hand, the problem of determining the optimal compact coloring for these graphs is NP-hard, since it is already NP-hard for paths and even cycles [START_REF] Giaro | NP-hardness of compact scheduling in simplified open and flow shops European[END_REF].

In the following proposition we prove that one cannot determine in polynomial time whether a given weighted graph admits any compact circular r-coloring, unless P=NP.

Proposition 5

The following problem is NP-complete: "Given a weighted graph (G, w). Does there exist a real r such that (G, w) has a compact circular r-coloring?".

Proof: First we prove that the problem belongs to NP. Note that it is not straightforward, since r and colors are from continuous domain. It suffices to argue that the answer is positive if and only if there exists a rational r = p/q, p, q ∈ N, gcd(p, q) = 1, q ≤ p ≤ e∈E(G) w(e) and a compact circular r-coloring c such that c(e) = (φ(e)/q, (φ(e) + q • w(e))/q) for every edge e, where φ(e) ∈ {0, . . . , p -1} and addition is taken modulo q.

For convenience we assume that G is connected. Let c be a compact circular r-coloring. If r is irrational we claim that there exists a standard compact coloring which leads to the existence of circular compact ∆(G, w)-coloring by Proposition 2. We can assume that there is an edge e 0 for which c(e 0 ) = (0, w(e)), shifting the colors if needed. Denote by ℓ(e) the left endpoint of c(e) for each edge e. We have ℓ(e 0 ) = 0, which together with connectivity of G and compactness of c implies that for each edge e there exists an integer k e such that ℓ(e) ≡ k e (mod r). Since r is irrational, k e is unique. It is easy to observe that assigning (k e , k e + w(e)) to each edge e gives a standard compact coloring.

Suppose c is a compact circular r-coloring, where r = p/q is rational, gcd(p, q) = 1. We can assume 0 is the left endpoint of a color of some edge, shifting the colors if needed. Then, the compactness property implies that c satisfies the condition c(e) = (φ(e)/q, (φ(e) + q • w(e))/q) for each edge. Now we argue that if p > e∈E(G) w(e) then one could construct a compact circular ∆(G, w)coloring. Suppose that c is a compact circular (p/q)-coloring, where p > e∈E(G) w(e). We assume that c(e) = (φ(e)/q, (φ(e) + qw(e))/q) for each edge e, where φ(e) ∈ {0, . . . , p -1}. Then, there exists some x ∈ {0, . . . , p -1} that φ(e) = x for any edge e. Without loss of generality we assume that x = 0. Since p and q are coprime, for each y ∈ {1, . . . , p -1} there exists a unique z(y) ∈ {1, . . . , p -1} such that q • z(y) ≡ y (mod p). Using the same argument as that in the proof of Theorem 5 in [START_REF] Nadolski | Compact cyclic edge-coloring of graphs[END_REF], one can observe that assigning (z(φ(e)), z(φ(e)) + w(e)) to each edge e yields a compact standard edge-coloring. Thus, we can construct a compact circular ∆(G, w)-coloring by Proposition 2.

To complete the proof we construct a reduction from a problem which is NP-complete to the considered one. Consider a weighted graph (G, w). Let S = e∈E(G) w(e). We construct a weighted graph ( Ḡ, w) by adding to (G, w) two new vertices connected by an edge of weight S + 1. We claim that (G, w) admits a compact standard r-coloring for some r if and only if ( Ḡ, w) admits a circular compact q-coloring for some q.

Suppose there exists a compact standard r-coloring of (G, w). Then, by Proposition 2 there exists a compact circular q-coloring of ( Ḡ, w), where q = max{r, S + 1} ≥ ∆( Ḡ, w). Now let c be a compact circular q-coloring of ( Ḡ, w). Such a coloring restricted to (G, w) would be a compact circular q-coloring of (G, w). Moreover, q ≥ S + 1, which together with Proposition 3 yields that (G, w) admits a compact standard q-coloring.

Therefore, we have reduced the problem of the existence of a compact r-coloring for some r to the problem of the existence of a compact circular q-coloring for some q. Since the former is NP-complete [START_REF] Sevastyanov | Interval colorability of the edges of a bipartite graph (in Russian)[END_REF], this completes the proof. ✷

Compact Circular Coloring of Odd Cycles

The results of the previous section imply that no efficient algorithm can construct a compact circular coloring of an arbitrary graph, while the results of [START_REF] Solot | Some graph-theoretical models for scheduling in automated production systems[END_REF] provide an algorithm that constructs an optimal compact circular coloring of any outerplanar bipartite graph in polynomial time. In the first part of this section we provide an algorithm for compact circular coloring of odd cycles. Note that determining whether there exists a standard compact coloring of an odd cycle is NP-hard [START_REF] Giaro | Task Scheduling Without 2-Sided Waiting Periods on Dedicated Processors[END_REF].

Theorem 6 For every weight function w : E(C 2k+1 ) → N of an odd cycle there exists a compact circular r-coloring for some r ≤ 1.5 • ∆(C 2k+1 , w).

Proof: Denote the consecutive vertices of the cycle as v 0 , . . . , v 2k and assume that w({v

0 , v 1 }) + w({v 1 , v 2 }) = ∆(G, w) and w({v 0 , v 1 }) ≥ w({v 1 , v 2 }). Let r = w({v 2k , v 0 }) + w({v 0 , v 1 }) + w({v 1 , v 2 }).
The following inequalities hold

w({v 2k , v 0 }) ≤ w({v 1 , v 2 }) ≤ 0.5 • ∆(C 2k+1 , w),
which implies that r ≤ 1.5 • ∆(G, w). We construct an assignment c :

E(C 2k+1 ) → A(C r ) as follows c({v 0 , v 1 }) = (w({v 1 , v 2 }), r -w({v 2k , v 0 })), c({v i , v i+1 }) = (0, w({v i , v i+1 })) for i = 1, 3, . . . , 2k -1, c({v i , v i+1 }) = (r -w({v 2k , v 0 }, r) for i = 2, 4, . . . , 2k,
where v 2k+1 = v 0 . We claim that c is a compact circular r-coloring.

First, consider a fixed vertex v i , where i ∈ {2, 3, . . . , 2k}. Observe that the colors assigned to the edges incident to v i are (0, a) and (rb, 0), where a and b are the weights of these edges. This yields that c is a proper circular r-coloring at v i and that the compactness constraint is fulfilled at v i . In the same way we check that the restrictions of compact circular coloring are satisfied by c at vertices v 0 and v 1 .

✷

Note that if we follow the steps of the proof of Theorem 6, then we obtain an algorithm for compact circular coloring of odd cycles which runs in linear time. Moreover, since no circular r-coloring exists for any r < ∆(G, w), such an algorithm is 1.5-approximate.

Corollary 7 There exists a 1.5-approximation algorithm running in O(n) time for compact circular coloring of weighted odd cycles. Now we prove that the problem of determining an optimal compact circular coloring of an odd cycle is NP-hard.

Theorem 8

The problem of determining if for a given weighted odd cycle (C 2k+1 , w) there exists a compact circular ∆(C 2k+1 , w)-coloring is NP-complete.

Proof: The proof that the considered problem belongs to NP is straightforward. We construct a reduction from the problem of determining whether a given weighted odd cycle admits a standard compact coloring, which is known to be NP-hard [START_REF] Giaro | Task Scheduling Without 2-Sided Waiting Periods on Dedicated Processors[END_REF]. Consider a weighted cycle (C, w) -an instance of this problem. Let e 1 , . . . , e 2k+1 be the consecutive edges of the cycle and let a i be the weight of e i , i = 1, . . . , 2k + 1. We construct an odd cycle C with 2k + 3 edges f 1 , . . . , f 2k+3 and weights w(f i ) = a i for i = 1, . . . , 2k + 1 and w(f 2k+2 ) = w(f 2k+3 ) = S, where S = a 1 + . . . + a 2k+1 . Clearly, ∆( C, w) = 2S. We claim that (C, w) admits any compact standard r-coloring if and only if ( C, w) admits a compact circular 2Scoloring.

(⇐): Suppose that c is a compact circular 2S-coloring of ( C, w). We can assume, rotating the colors if needed, that c(f 2k+2 ) = (0, S) and c(f 2k+3 ) = (S, 2S). Then, edge f 1 must obtain one of the colors (0, a 1 ) or (Sa 1 , S) and edge f 2k+1 must obtain one of the colors (2Sa 2k+1 , 2S) or (S, S + a 2k+1 ). The compactness of c gives us that

(c(f 1 ) ∪ . . . ∪ c(f 2k+1 )) ⊂ C 2S
is an arc of length at most S. This yields that either c(f 1 ) = (0, a 1 ) and c(f 2k+1 ) = (2Sa 2k+1 , 2S) or c(f 1 ) = (Sa 1 , S) and c(f 2k+1 ) = (S, S + a 2k+1 ). Observe that the former case can be transformed to the latter by reversing and rotating the coloring, therefore we assume that c(f 1 ) = (Sa 1 , S) and c(f 2k+1 ) = (S, S + a 2k+1 ). Using the compactness of c again we obtain that c(f i ) is a subinterval of (a 2k+1 , 2Sa 1 ) for every i = 1, . . . , 2k + 1. Therefore, we can assign color c(f i ) to e i for i = 1, . . . , 2k + 1 obtaining a compact standard 2S-coloring of (C, w).

(⇒): Notice that if there exists any compact r-coloring of (C, w), then there exists a compact Scoloring. Moreover, such a coloring can be transformed by shifting and if necessary reversing the colors to a compact 2S-coloring c, such that c(e 1 ) = (Sa 1 , S) and c(e 2k+1 ) = (S, S + a 2k+1 ). We define an assignment c : E( C) → A(C 2S ) as follows: c(f i ) = c(e i ) for i = 1, . . . , 2k + 1 and c(e 2k+2 ) = (0, S), c(e 2k+3 ) = (S, 2S). This gives us a compact circular 2S-coloring of ( C, w). ✷

We have proved that an optimal compact circular edge-coloring cannot be constructed in polynomial time, unless P=NP. However, we can construct a pseudo-polynomial algorithm that solves this problem.

Consider an odd cycle (C, w) and denote its edges as e 1 , . . . , e n . Let (P, w) be a path of length n, with edges f 1 , . . . , f n and weights w(f i ) = w(e i ). To construct an optimal compact circular edge-coloring of (C, w) we first find for each f i the set of colors that can be assigned to that edge by some standard compact coloring c of (P, w) such that c(f 1 ) = (0, w(f 1 )) and c(f j ) is an interval of R for all j = 1, . . . , n. For each i = 1, . . . , n we construct a set L[i] of the values that can be attained by the left endpoint of c(f i ) in such a coloring. The sets L[i] can be determined using the following dynamic programming formulas

L[1] = {0}, (1)
L[i + 1] = {ℓ -w(f i+1 ) : ℓ ∈ L[i]} ∪ {ℓ + w(f i ) : ℓ ∈ L[i]}, i = 1, . . . , n -1. (2)
The following proposition provides a relation between standard compact colorings of (P, w) and compact circular colorings of (C, w).

Proposition 9 Let r ≥ ∆(C, w). A compact circular r-coloring of (C, w) exists if and only if there exists a compact standard coloring c of (P, w) such that c(f 1 ) = (0, w(f 1 )) and c(f n ) = (arw(f n ), ar) for some integer a.

Proof: (⇒) Consider a compact circular r-coloring c of (C, w). Without loss of generality we can assume that c(e 1 ) = (0, w(e 1 )) and c(e n ) = (rw(e n ), r). We construct a compact coloring c of (P, w). First we put c(f 1 ) = (0, w(f 1 )) and then we define c(f i+1 ) using c(f i ) for every i = 1, . . . , n -1. For every i the left endpoint of c(e i+1 ) is equal to the right endpoint of c(e i ), or the right endpoint of c(e i+1 ) is equal to the left endpoint of c(e i ). In the first case we put c(f i+1 ) = (r i , r i + w(e i+1 )) and in the second case we put c(f i+1 ) = (l iw(e i+1 ), l i ), where (l i , r i ) = c(f i ). It is easy to observe that c defined in this way is a standard compact coloring of (P, w) and that

c(e i ) = ([l i ] r , [r i ] r ).
Therefore, since c(e n ) = (rw(e n ), r), we have r n ≡ 0 (mod r), which implies c(f n ) = (arw(f n ), ar) for some integer a.

(⇐) Consider a compact coloring c of (P, w) such that

c(f 1 ) = (0, w(e 1 )), c(f n ) = (ar -w(f n ), ar), (3)
where a ∈ Z and r ≥ ∆(C, w). Denote c(f i ) = (l i , r i ) and put c(e i ) = ([l i ] r , [r i ] r ). We claim that c is a compact circular r-coloring of (C, w). Using (3) we obtain c(e 1 ) = (0, w(e 1 )) and c(e n ) = (rw(e n ), r). Therefore, the colors of e 1 and e n are not conflicting and the compactness criterion is satisfied in the common vertex of e 1 and e n . Moreover, since c is a compact coloring of path P and r ≥ ∆(C, w) coloring c must be proper and compact at every other vertex of the cycle (C, w). ✷ Proposition 9 implies that once we have computed L[n] we can find an optimal compact circular coloring by finding the minimum r ≥ ∆(C, w) such that arw(e n ) ∈ L[n] for some integer a.

Theorem 10 An optimal compact circular coloring of an odd cycle (C, w) can be constructed in O(nW ) time, where W = n i=1 w(e i ).

Proof: First, we derive the sets L[i] for i = 1, . . . , n using formulas (1) and ( 2). This can be completed in O(nW ) time, since L[i] contains at most 2W integers for every i = 1, . . . , n.

Then, we must find the minimum r, such that r ≥ ∆(G, w) and arw(e n ) ∈ L[n] for some integer a. It is easy to observe that r(ℓ) is the minimum real not less than ∆(G, w) such that a • r(ℓ) = ℓ + w(e n ) for some a ∈ Z. Therefore, the optimal value r is equal to

r = min{r(ℓ) : ℓ ∈ L(n)}. (4)
Notice that n-1 i=0 w(e i ) ∈ L(n) and n i=0 w(e i ) ≥ ∆(G, w), which implies that r defined by (4) satisfies r < +∞. After we have computed r we can find a compact circular r-coloring of (C, w). First, backtracking the algorithm for computing L[i], we find a standard coloring c of (P, w) such that c(f 1 ) = (0, w(f 1 )) and c(f n ) = (ar-w(f n ), ar) for some integer a. Finally, putting c(e i ) = ([l i ] r , [r i ] r ), where (l i , r i ) = c(f i ) for i = 1, . . . , n, we obtain a compact circular r-coloring c, in the same way as in the proof of Proposition 9.

✷

The results we have proved so far provide that odd cycles can be colored in a compact circular way in polynomial time, while the problem of determining whether for an input graph there exists any compact circular coloring is NP-complete in general. One may ask, how the structure of the cycle must be made more complicated to make this problem hard. The following theorem proves that it is NP-hard for an odd cycle with a path P 2 connected to a vertex of the cycle.

f 3 2S 1 f 4 6S + 1 e 1 2a 1 2a 2 e 2 . . . e 2k+1 f 2 f 1 2S 2a 2k+1
Fig. 2: A graph (G, w) constructed in the proof of Theorem 11.

Theorem 11

The following problem is NP-complete: "Given weighted graph (G, w), where G has a structure of an odd cycle with a path P 2 connected to one of its vertices. Does there exist a real r > 0 such that (G, w) admits a compact circular r-coloring?".

Proof: In the same way as in the proof of Theorem 8 we reduce the problem of determining if there exists a compact r-coloring of (C 2k+1 , w) for some r to the considered problem. Let a 1 , . . . , a 2k+1 be the weights of consecutive edges of (C 2k+1 , w) and let S = a 1 + . . . + a 2k+1 . Consider a weighted graph (G, w) depicted in Fig. 2. We claim that (G, w) admits a compact circular r-coloring for some r if and only if (C 2k+1 , w) is standard compact q-colorable for some q.

(⇒): Suppose c is a compact circular r-coloring of (G, w). Clearly, r ≥ ∆(G, w) = 6S + 2. Without loss of generality, rotating the coloring if needed, we may assume that either c(f 1 ) = (0, 2S) and c(f 2 ) = (2S, 4S) or c(f 1 ) = (0, 2S) and c(f 2 ) = (2S + 1, 4S + 1).

Consider the first case. The color of edge e 1 is equal to either (r -2a 1 , r) or (2S, 2S + 2a 1 ) and the color of e 2k+1 is either (2S -2a 2k+1 , 2S) or (4S, 4S + 2a 2k+1 ). However, (c(e 1 ) ∪ . . . ∪ c(e 2k+1 )) is an arc of length at most 2S, since c is compact, therefore we get that c(e 1 ) = (2S, 2S + 2a 1 ) and c(e 2k+1 ) = (2S -2a 2k+1 , 2S). Moreover, c(e i ) ⊂ (0, 4S) for i = 1, . . . , 2k + 1, which yields that c can be transformed to a compact 4S-coloring of (C 2k+1 , w).

We claim that the second case cannot occur. If we suppose that c(f 1 ) = (0, 2S) and c(f 2 ) = (2S + 1, 4S +1), in the same way we obtain that c(e 1 ) = (2S, 2S +2a 1 ), c(e 2k+1 ) = (2S -2a 2k+1 +1, 2S +1). However, compactness of c yields that c(e i ) ⊂ (0, 4S + 1), i = 1, . . . , 2k + 1 implying that the arcs c(e i ), i = 1, . . . , 2k + 1 either all begin in even points or all begin in odd points -a contradiction.

(⇐): Suppose that there exists a compact standard r-coloring of (C 2k+1 , w). Then we can transform it, in the same way as in the proof of Theorem 8, to a compact circular (6S + 2)-coloring. ✷

Concluding Remarks

We have studied the complexity of the problem of circular edge-coloring of weighted graphs. The former results of [START_REF] Solot | Compact cylindrical scheduling[END_REF] give a polynomial-time algorithm for circular coloring of outerplanar bipartite graphs, while coloring general bipartite graphs was proven to be NP-hard [START_REF] Kubale | Chromatic scheduling in a cyclic open shop[END_REF][START_REF] Solot | Some graph-theoretical models for scheduling in automated production systems[END_REF]. The theorems of the last section extend these results and yield a nearly complete classification of the complexity of the problem of coloring nonbipartite graphs. We have proved that it is NP-hard to optimally color weighted odd cycles. Moreover, Theorem 11 implies that it is not possible to provide a polynomial-time algorithm that constructs any compact circular coloring of non-bipartite graphs from any significantly wider class than odd cycles. This also justifies, why in Theorem 6 and Corollary 7 we have considered such simple graphs as odd cycles.

  If (-w(e n )) ∈ L[n] then obviously r = ∆(C, w). Otherwise, for each ℓ ∈ L[n] we derive r(ℓ) = |ℓ + w(e n )|/⌊|ℓ + w(e n )|/∆(G, w)⌋, where r(ℓ) = +∞ if |ℓ + w(e n )| < ∆(G, w).

† Both authors are supported in parts by Foundation for Polish Science and Ministry of Science grant N516 029 31/2941. 1365-8050