Philippe Andary
email: andary@dir.univ-rouen.fr

Finely homogeneous computations in free Lie algebras

Keywords:

, which gives a way to go from every Lyndon word of length n to its successor (with respect to lexicographic order by length), in space and worst case time complexity On. Finally, we give a simple algorithm which uses Duval's method (the one above) to compute the next standard bracketing of a Lyndon word for lexicographic order by length. We can find an interesting application of this algorithm in control theory, where one wants to compute within the command Lie algebra of a dynamical system (letters are actually vector fields).

Introduction

Let A = fa 1 ;a 2 ;:::;a k gbe a set with k elements, and QhAi the associative (non-commutative) algebra on A. Defining a Lie bracket ([x; y]=xy yx)onthisQ-module turns it into a Lie algebra, and we will denote by L(A) its Lie subalgebra generated by A (i.e. L(A) is the free Lie algebra on A and QhAi its enveloping algebra). A will now be called an alphabet, whose elements are the letters,andA is the free monoid (the set of all words) over A.

We know that L(A) is a graded Q-module

L(A)= M n1 L n ( A) (1)
where L n (A) is the submodule of L(A) generated by homogeneous components with degree n.Furthermore, L n (A) is the direct sum of finely homogeneous submodules L (A) with multidegree 2 N k such that jj = n. Hence we have All the classical monomial basis of L(A) are finely homogeneous (see Reutenauer [START_REF] Reutenauer | Free Lie Algebras[END_REF], for example, or

L(A)= M 2N k L ( A) (2
Viennot [START_REF] Viennot | Algèbres de Lie libres et monoïdes libres[END_REF]), i.e. their components are finely homogeneous Lie monomials, thus every computation on Lie polynomials (the elements of L(A)) is nothing but a computation in some fine homogeneity class. We want to emphasize the use of a particular basis of L(A), the Lyndon basis, introduced by Chen et al. in the late 1950s [START_REF] Chen | Free differential calculus, IV. The quotient groups of the lower central series[END_REF] (the interested reader can find all the details of its construction in Lothaire [START_REF] Lothaire | Combinatorics on words[END_REF]).

For this purpose, we choose a total order a 1 <a 2 <:::<a k on A, which induces a lexicographic order on A .Aw ord`is a Lyndon word if it is primitive and minimal in its conjuguacy class. This means that cannot be written as u n for given u in A and n 2,a nd` vu whenever `= uv.WedenotebyLy(A) the set of Lyndon words over A.

For every Lyndon word `we define its (right) standard factorization (`0;`0 0 ) as the unique couple of Lyndon words such that `= `0`0 0 and `00 is of maximal length. Moreover, the recursive Lie bracketing of the standard factorization will be called the (right) standard bracketing of `, denoted by [`].

It would be convenient to define the left standard factorization (u; v) of `as the unique couple of Lyndon words such that `= uv and u is of maximal length. Then the recursive Lie bracketing of the left standard factorization will be called the left standard bracketing of `, denoted by (`).

Note that A is included in Ly(A) and that [a]=a=( a )for every letter a.A s a ne x e m p l e ,l e t A = fa; bg and `= aaabab,then`is Lyndon because it is primitive and `<sfor each of its proper suffix s. The standard bracketings of `are

[`] = [a; [[a; [a; b]]; [a; b]]] (`) = [[a; [a; [a; b]]];[a;b]] It is well known that Ly(A) is a factorization of A and that [Ly(A)] is a basis of L(A) (called the Lyndon basis of L(A)).
The paper is organized as follows. First, we give a fast algorithm to compute the maximal Lyndon word (with respect to lexicographic order) of Ly (A) for every given multidegree in N k . We will see that the letters of a Lyndon word which is maximal in its fine homogeneity class are as much 'regularly distributed' as possible.

In the second part, we give an algorithm to compute all the words living in Ly (A) for any given in N k . The best known method for generating Lyndon words is that of Duval [START_REF] Duval | Génération d'une section des classes de conjuguaison et arbre des mots de Lyndon de longueur bornée[END_REF], which gives a way to go from every Lyndon word of length n to its successor (with respect to lexicographic order by length), in space and worst case time complexity O(n). It is easy to see that in the special case where A = fa; bg and `= a k+3 ba k 1 b (k>0 ), there are 2 k 1 1 Lyndon words of length 2k +4between `and its successor in the same fine homogeneity class (namely a k+2 ba k b). Hence, this method has an exponential worst case time complexity for our purpose.

Finally, we give a simple algorithm which uses Duval's method (the one above) to compute the next standard bracketing of a Lyndon word for lexicographic order by length. We can find an interesting application of this algorithm in control theory, where one wants to compute within the command Lie algebra of a dynamical system (letters actually are vector fields). Standard bracketing are very expansive to compute in this context, and that is why we want to generate them as quickly as possible in the lexicographic order by length.

2 Maximal Finely Homogeneous Lyndon Words

Introduction

Given in (N ) k , the question is to find a description of the maximal finely homogeneous Lyndon word with respect to lexicographic order (A) = maxfLy (A)g

(3)

We will merely denote it by when no confusion is possible.

Before answering our question, let us give a short description of the problem's background. Let `be a Lyndon word with fine homogeneity 2 (N ) k ;itiswellknown [START_REF] Lothaire | Combinatorics on words[END_REF]that

[`]=`+ X `<w w (4)
Of course, if `= the only Lyndon word appearing in [`] is `itself, but the reciprocal may, or may not, be true. Anyhow, this led us to an algorithmic answer to our former question, when A = fa; bg in a first time, then for any finite alphabet. Just for fun now, we know that the reciprocal is not true and we were able to find a lot of counter examples (with the help of computers) for which

supp([`]) \ Ly (A)=f`g (5)
For example, each of the following words aabbabaabbabababaabbabab, aabbabababaabbababababab and aabbabababababababababab are in Ly (12;12) (fa; bg) and verify equation ( 5).

The Binary Case

Let us consider the case k =2, thus A = fa; bg.

if (n =1)o r( m =1) then Return(a n b m ) else if n m then q := n div m r := n mod m if r =0
then Return(a q+1 ba q 1 b(a q b) m 2 ) else Return(MFHLynd((r;m), fa; a q bg))

else q := m div n r := m mod n if r =0 then Return(ab q 1 ab q+1 (ab q ) n 2 )

else Return(MFHLynd((n r;r), fab q ;ab q+1 g))

end

Proof. Let (n; m) be any couple of positive integers. We will denote by the result of the MFHLynd function. As this algorithm is recursive, we denote by n i , m i and A i the instances of formal parameters during the i-th function call (n 1 = n, m 1 = m and A 1 = fa; bg). Note that the algorithm will terminate in a finite number of steps, say p, since through each step i the sum n i + m i will strictly decrease. Furthermore, let us denote by i the word (ni;mi ) at each stage i.

If p =1then n is a multiple of m,orm is a multiple of n, and we obviously have = 1 = (n;m) (fa; bg).

So let us consider the case p>1 , i.e. either n = q 1 m + r 1 with q 1 1 and 0 <r 1 <m ,o r m = q 1 n + r 1 with q 1 1 and 0 <r 1 <n.T h e n(n 2 ;m 2 )is (r 1 ;m) or (n r 1 ;r 1 ), depending on the value of n and m,andA 2 is fa; a q1 bg or fab q1 ;ab q1+1 g accordingly. Of course, 2 1 because Ly(A 2 ) Ly(A 1 ), and if we prove that

1 2 A 2 (6)
the previous inequality turns to an equality. Now the end of the proof is trivial: we have = p ,b u t relation ( 6) implies

1 = 2 = :::= p (7)
Finally, for the proof to be complete, we have to justify relation [START_REF] Knuth | The Art of Computer Programming[END_REF]. For this purpose, we will first suppose that n = q 1 m + r 1 (thus A 2 = fa; a q1 bg). We can write 1 = a q1+"1 b:::a q1+"m b [START_REF] Nijenhuis | Combinatorial Algorithms[END_REF] and one can easily see that " 1 =1 , " 2 2f 0 ;1 gand q 1 " i 1 for 3 i m (since 1 2

Ly (n;m) (fa; bg)). Next, the existence of h = minfi : " i < 0g would imply the existence of a Lyndon word `in Ly (n;m) (fa; bg) which would be greater than 1 . Indeed, let us write 1 = wv 1 v 2 :::v t ,where w = a q1+1 b:::a q1+"h 1 ba q1 x b (x = j" h j)andthev i 's are defined by the left standard bracketing of 1

Furthermore, we will consider w 0 = a q1+1 b:::a q1+"h 1 1 b (10)

w 00 = a q1 x+1 b (11)
Some v i 's are greater than w 0 , some are not, but they are all greater than w. So we can split those v i between w and w 0 in two words, and apply the same transformation as in w ! (w 0 ;w 00 ). Now construct a sequence of Lyndon words, with those v i that are greater than w 0 on the one hand, and the splitted ones (v 0 i ;v 00 i )on the other. Then concatenating this reordered sequence will give us a new Lyndon word which is greater than 1 (because the former begins with w 0 , and the latter with w). But this fact contradicts the maximality of 1 ,soh doesn't exist. Now, the second case m>n, mnot a multiple of n, is not substantially different from the previous one. Let us denote by A 0 the alphabet A equipped with the reverse order b<a.T h e n' : A A 0 such that '(a)=band '(b)=aextends to an isomorphism from A onto (A 0 ) . Moreover, ' is order preserving, and we have clearly

(n;m) (fa; bg)= '( ( m;n) (fa; bg)) e (12)
where (u 1 :::u k )e=u k :::u 1 is the mirror image of the word u. 2

The analysis of this algorithm is trivial, since its recurrence tree is structurally equivalent to that of Euclide's algorithm for computing the greatest common divisor of n and m.Sowehave Theorem 2 For given positive integers (n; m), the worst case time complexity for MFHLynd function is O(log(max(n; m))).

Proof. See Knuth [START_REF] Knuth | The Art of Computer Programming[END_REF] for instance, Theorem 4.5.3-F and Corollary 4.5.3-L, p. 343. else if n m

then q := n div m r := n mod m if r =0 then if k =2 then Return(a q+1 1 a 2 a q 1 1 a 2 (a q 1 a 2 ) m 2 )
else Return(MFHLynd(( 2 ;:::; k ), fa q 1 a 2 ;:::;a q 1 a k g)) else Return(MFHLynd((r; 2 ;:::; k ), fa 1 ;a q 1 a 2 ;:::;a q 1 a k g))

else h := n for i decreasing from k downto 2 do q i := i div h r i := i mod h h := h r i if (8i; r i =0) then Return(a 1 a qk k :::a q2 1 2 a 1 a qk k :::a q2+1 2 (a 1 a qk k :::a q2 2 ) n 2 ) else t := 0 for i increasing from 2 to k do if r i > 0 then t := t +1 i t := i

Return(MFHLynd((n P t j=1 r ij ;r i1 ;:::;r it ), fa 1 a qk k :::a q2 2 ;a 1 a qk k :::a qi 1 1 i1 1 a qi 1 +1 i1 ;:::;a 1 a qk k :::a qi t 1 it 1 a qi t +1 it g))

end

We can reasonably expect the complexity of such an algorithm to be a function in the size of the alphabet and in the maximum of the components i , but unfortunately, we were not able to analyse the behaviour of MFHLynd function in this case deeply enough.

3 Fine Homogeneous Generation of Lyndon Words

Introduction

Now the problem is to find all words in Ly (A),forevery in (N ) k . We will need the following well known reducing property (see, for example, Duchamp and Krob [START_REF] Duchamp | Combinatorics in trace monoids II[END_REF] for a partially commutative version of this proposition):

Proposition 1 Let k>1, A=fa 1 <:::<a k gand A 0 =(A a k )a k .T he nLy(A)=Ly(A 0 ) [fa k g. Let us see, with an example, how we will dissect Lyndon words to solve our problem. Suppose = (3; 3) and A = fa; bg (k =2). By proposition 1, if A 0 = ab then Ly(A)=Ly(A 0 ) [ b. Denoting by B the minimal subset of A 0 such that Ly (A) B , we mean the code B = fa; ab; abb; abbbg

We want to find out all Lyndon words on B that are in Ly (A) ; we know their fine homogeneity, but we don't know how they look like: there can be either two a and one abbb, or one a, one ab and one abb.

(Note that we cannot take three times ab, since Lyndon words are primitive.)

Hence, our initial problem breaks down into two 'smaller' subproblems -find all of the words in Ly (2;1) (fa; abbbg) and Ly (1;1;1) (fa; ab; abbg). These subproblems are smaller insofar as the length of the involved Lyndon words are smaller over the new alphabets than over the previous one (here, we have to compare fa; abbbg and fa; ab; abbg with fa; bg). It is still necessary to detail the way we compute Ly (1;1;1) (fa; ab; abbg).Herewehave =(1;1;1

Clearly, iterating this process will give, in a finite number of steps, every Lyndon word on fa; bg with fine homogeneity (3; 3). In fact, our algorithm will ultimately construct all alphabets with only one letter which is a word in Ly 3;3 (fa; bg). For example, the subproblems' decomposition tree in this case is and finally, Ly 3;3 (fa; bg)=faaabbb; aababb; aabbabg.

Translation in Terms of Partition

Looking closely at our process gives the feeling that breaking down our problem into smaller ones is exactly the same as finding a set of partitions under some constraints. For example, in the first stage of our previous computation we have searched for the set of elements x in N 4 such that x 1 + x 2 + x 3 + x 4 =3 , verifying the constraint x 1 +2x 2 +3x 3 +4x 4 =6 . We have accepted (2; 0; 0; 1) and (1; 1; 1; 0), refused (0; 3; 0; 0) (since Lyndon words are primitive), and thereby found all the solutions in x. Next, during the decomposition of Ly 1;1;1 (fa; ab; abbg), we have searched for the set of elements (x; x 0 ) in N 2 2 verifying

x 1 + x 2 = 1 x 0 1 + x 0 2 = 1 x 1 +2 x 2 +x 0 1 +2 x 0 2 = 3
Here, again, we have found all the solutions in (x; x 0 ), namely ((1; 0); (0; 1)) and ((0; 1); (1; 0)).

For a good formulation of the problem in terms of composition and partition, we will need some notations and definitions. For every x in N p ,wedefine jxj = x 1 + x 2 + :::+x p (16) and jjxjj = x 1 +2 x 2 +:::+px p (17)

A composition of the positive integer n into p partsisap-tuple x in N p such that jxj = n.Furthermore, when jjxjj = n + we say that x is constrained by . We will denote by (n; p) (resp. (n; p))theset of all compositions of n into p parts (resp. the set of all compositions constrained by ).

A partition of the positive integer into p p a r tsisap-tuple y in (N ) p such that jyj = n and y 1 :::y p 1. We will denote by (n; p) the set of all partitions of n into p parts, and by (n; p) the set of all partitions of n into p parts whose value does not exceed (thus y 1 ).

For consistency with our previous notations, we will call x =(x i1 ;:::;x it )the composition without any 0's (thus, for all 1 j t, x ij > 0 and every other x i are zero), and we will denote by B x the subset of elements of B at the i j -th place for lexicographic order (1 j t).

Here is a trivial property which will be helpful for computing the compositions, since we know a constant worst case time complexity algorithm to derive the successor of a partition (see Nijenhuis and Wilf [8]).

Proposition 2 For given n, p and , every partition in p (n+; n) is equivalent to a unique composition in (n; p). Proof. proof is immediate if we see that, given a partition in p (n + ; n), the corresponding composition x in (n; p) is such that x i is nothing but the number of parts (in y) equal to i (for all i in [1;p]).

2

As an example, all the compositions constrained by 3, of 3 into no more than 4 parts are (2; 0; 0; 1), (1; 1; 1; 0) and (0; 3; 0; 0). Proposition 2 says that they are equivalent to the partitions of 6 into 3 parts not greater than 4, namely (4; 1; 1), (3; 2; 1) and (2; 2; 2); which will become evident with the notation 1 2 4, 123 and 2 3 . For every partition y this last form, which is equivalent to a composition x, we will write y the sequence of non zero exponents (for example, if y = 123 then y =(1;1;1)); so that x = y.

The Algorithm

Now we can state Theorem 3 Let k>1, A=fa 1 < :::< a k gand =( 1 ;:::; k )2 (N ) k .S e tB := fa i a k j :1 ik 1;0j k g, :=( k ;k)and for each in :

X := 1 ( 1 ; k +1)::: k 1 ( k 1 ; k +1):

Then we have

Ly (A)= [ 2 [ x2X Ly x (B) (18)
Proof. On the one hand, we will study the case k =2 , so we consider A = fa; bg, =( n; m) and B = fab j :0jm g.T h e r ei sm +1elements in B, and to each composition x 2 N m+1 ,w e associate the fine homogeneous class of words in B F x = fw 2 B : jwj ab j = x j ; 0 j mg:

Since F x is never empty, there is at least one Lyndon word in F x (note that, by Proposition 1, Ly(B)

Ly(A)) we want to determine those x such that F x contains a Lyndon word in Ly (A) -thus every Lyndon word in F x will belong to Ly (A). Of course, Ly (A) will be the union set of Ly x (B) over all these x. But it is clear that the only criteria for x 2 N m+1 to be choosen are jxj = n and jjxjj = n + m.

So must be a composition of n into no more than m +1parts, constrained by m, and the theorem is proved when k =2(with =f(m)gand X (m) = m (n; m +1)).

On the other hand, we will now consider the case k>2 .T h e nw eh a v eB = fa i a k j :1i k 1 ;0j k gand jBj = k( k +1). Here, the problem is to find all x =(x (1) ;:::;x (k 1) ) in N k+1 k 1 such that jx (i) j i (1 i k 1) P k 1 i=1 jjx (i) jj = jj (20) Thus we must have, for all i, the inequalities i jjx ( i)

jj i + k (21)
and it is clear now that the set of solutions for (20) is exactly the union set over 2 ( k ;k)of the jBj-tuple x of (non-negative) integers verifying jx (i) j = i jjx (i)

jj = i + i (22)
for all 1 i k 1.

2

From Theorem 3 and Proposition 2, we can deduce the function FHGLynd, which takes as input an alphabet A and a multidegree , and outputs the set of elements in Ly (A)

Tests on the Execution Time

Except for the FHGLynd function, the only algorithm at hand for computing the homogeneity class of Lyndon words could be one derived from Duval's method. As we will see in the next section, this method allows us to go from one Lyndon word to the (lexicographically) next one with the same length. Thus, a new function, say FHGL, is born: given an alphabet A with k letters and a homogeneity vector (with n = jj), construct the set Ly (A) by iterative application of Duval's method, picking up those words whose homogeneity is . However, we have to bear in mind that this is an exponential algorithm, since the number of Lyndon words whose length is n is O( k n n ). We wanted to get a feeling on the complexities of both methods. For this purpose, both algorithms have been implemented in Maple V.3 on an SS10 workstation under Solaris 2.3 operating system.

The first time we found out that, for the generation of a given homogeneity class of Lyndon words, the FHGLynd function is more efficient than FHGL.

The second time, we decided, given a finite alphabet A of size k and an integer n, to generate all the words in Ly n (A), first in lexicographic order by Duval's method (algorithm D), and then by homogeneity classes with our function (algorithm A). Although the average running time of A per homogeneity class becomes gradually smaller than the running time of D while k and/or n grow, algorithm A does not seem to be linear in n, since algorithm does, and their execution time ratio increases.

Hence, it is obvious that these two algorithms are devoted to different problems: FHGL is well suited for lexicographic enumeration of Lyndon words of given length, while FHGLynd is just right for homogeneity generation of Lyndon words.

Generating the Lyndon Basis 4.1 Introduction

We want here to generate the standard bracketing of Lyndon words for lexicographic order by length. We know an efficient algorithm, due to Duval [START_REF] Duval | Génération d'une section des classes de conjuguaison et arbre des mots de Lyndon de longueur bornée[END_REF], which gives the next Lyndon word for lexicographic order by length with a constant average time complexity [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF]. The idea is quite simple: adapt Duval's method to obtain the index of the standard factorization in addition to the Lyndon word, of course, preserving time complexity; then a convenient tree data structure could be used to recursively store all the standard factorizations.

Duval's Theorem

We will write ''and'' for lexicographic order and lexicographic order by length, respectively. These total orders on A are defined as follows:

u v iff 8 < : v 2 uA ; or (9r;s;t2 A )(9a; b 2 A)(u = ras; v = rbt; a < b) u v iff 8 < : juj < jvj;
or juj = jvj;uv For all Lyndon word `, we will denote by S(`), when it makes sense, its successor, for lexicographic order, which is not in `A . It is computed as follows: remove all terminal maximal letters of `,then where grayed zones means the suppression of maximal letters. Now we can carry through the proof. If w = S(`) this is because jS(`)j = n,tha ti sS(`)= 1:::`n 1 succ(`n) with `n <z. In this case i(w) is obviously i(`).

Otherwise, there are two cases left. On the one hand, when w = u 1 q1 u 2 we must have i(w)= d 1 because of the preliminary remark. On the other hand, in the general case (t>2 ,o rt =2and q 2 > 1), the longest prefix of w which is Lyndon, is at least as long as u 1 q1 :::u t 1 qt 1 u t qt 1 ,s i n c e u 1 <u 2 <:::<u t . But according to the preliminary remark, it cannot be longer than this word. Hence i(w)= P t 1 i =1 q i d i +( q t 1)d t = n d t .

2

As an example, let us consider A = fa; bg and n =5 . Then we have the following table:

(`; i(`)) w = u 1 q1 :::u t qt i(w) for the four first lines i(w) is d 1 ,sincet =2and q 2 =1 , but for the fifth it is n d 2 =4since q 2 > 1.

Now, for the sake of completeness, let us give the slight improvement of Duval's algorithm function NextLynd(`,i(`))

# Input : `is a Lyndon word which is not maximal in its fine # homogeneous class. # i(`) is the index of the standard factorization of `. # Output : w, the successor of `with same length, for lexicogra-# phic order by length ; or the empty word if `is maximal # in its fine homogeneous class. # i(w), the index of the standard factorization of w ; #o r 0 if `is maximal in its fine homogeneous class.

  begin

( 1 )

 1 =[[:::[[(w); (v 1 )]; (v 2 )];:::];(v t )]

2 2. 3

 23 The General CaseIn a second time, we were able to generalize the function MFHLynd to any finite alphabet A in the following manner: function MFHLynd(,A) # Input : =( 1 ;:::; k ) is a k-tuple of positive integers. # A = fa 1 ;:::;a k g is the (ordered) alphabet. # Output : maxfLy (A)g.

  begin let z be the maximal letter of A for lexicographic order n := j`j w:= k := n while w[k]=z do k := k 1 w[k]:=succ(w[k]) if w[1] = zthen Return(",0) else t := 1

  Every word in Ly (A) is a Lyndon word over B, with either one aabb and one ab, or one a and one ababb.

	Thus
	Ly 1;1;1 (fa; ab; abbg)=Ly 1;1 (faabb; abg) [ Ly 1;1 (fa; ababbg)
	), A = fa; ab; abbg (k =3)andB is the code
	B = fa; aabb; ab; ababbg	(14)

replace the last non-maximal letter by its successor in A. Notice that S(`) has always a smaller size than `. For example, on A = fa; b; cg, S(aaacc) is aab (not aabab !), and S(aaabb) is aaabc. Duval proves that Theorem 4 If `is a Lyndon word with length n, which is not maximal in its fine homogeneous class ; if w is the following Lyndon word of `for '', then we have:

where the u i are Lyndon words derived from prefixes of `. More precisely, the u i are defined as follows (where u[1::j] is the prefix of u, whose length is j): u 1 = S(`); d 1 = ju 1 j; q 1 =( n 1) div d 1 ; r 1 =1+(n 1) mod d 1 ; u 2 = S(u 1 [1::r 1 ]); d 2 = ju 2 j; q 2 = r 1 div d 2 ;

r 2 = r 1 mod d 2 > 0; ::: u t = S(u 1 [1::r t 1 ]); d t = ju t j; q t = r t 1 div d t ; r t = r t 1 mod d t =0 : Let us have a feeling on the behaviour of the underlying algorithm on the Lyndon word `= a 3 bab 10 (over A = fa; bg). The first prefix we compute is (a 3 b 2 ) 2 ,s i n c eS(`)=a 3 b 2 , and because r 1 must be positive. Then we get (a 3 b 2 ) 2 a 2 b since S(a 3 b 2 )=a 2 b, and finally, we compute S(a 2 )=ab giving w =( a 3 b 2 ) 2 a 2 bab.

This algorithm is O(j`j) in worst case time complexity, and Berstel and Pocchiola [START_REF] Berstel | Average cost of Duval's algorithm for generating Lyndon words[END_REF] have proved it to be optimal in average time complexity (actually, they give the asymptotic bound (k +1 ) =k,wherek is the cardinal of A).

Adapted Duval's Algorithm

We have seen that Duval constructs the next Lyndon word by computing successive prefixes, thus we had the natural idea to use the left standard factorization instead of the right one, as usual. So, if we denote by i(u) the index of the left standard factorization of a Lyndon word u, and with the notations of Theorem 4, we have Theorem 5 If w = S(`),theni(w)=i ( ); otherwise if w = u 1 q1 u 2 ,t h e ni(w)=d 1 ,e l s ew = u 1 q1 :::u t qt and i(w)=n d t . Proof. First, we have to notice that, for all <it , the relation u i = S(u 1 [1::r i 1 ]) implies the existence of the integer d i in [[1 ;r i 1 ] ]and the letter i = succ(u i 1

then Return(w,i(`)) else if t =2 and q 2 =1 then Return(w,d 1 ) else Return(w,n d t ) end where u[j] means the j th letter of u,andsucc() is the following letter of in A.

It is clear that the complexity is the same as for the original algorithm, since we have added only two tests in the function's body (and also the use of four new integer variables).


H Caprasse
email: caprasse@vm1.ulg.ac.be

BRST Charge and Poisson Algebras

Keywords:

An elementary introduction to the classical version of gauge theories is made. The shortcomings of the usual gauge fixing process are pointed out. They justify the need to replace it by a global symmetry: the BRST symmetry and its associated BRST charge. The main mathematical steps required to construct it are described. The algebra of constraints is, in general, a nonlinear Poisson algebra. In the nonlinear case the computation of the BRST charge by hand is hard. It is explained how this computation can be made algorithmic. The main features of a recently created BRST computer algebra program are described. It can handle quadratic algebras very easily. Its capability to compute the BRST charge as a formal power series in the generic case of a cubic algebra is illustrated.

Introduction

Gauge invariance plays a key role in the formulation of all basic physical theories: this is true both at the classical and quantum levels. General relativity as well as all field theoretic models which describe the electromagnetic, the weak and the strong interactions are based on it. One feature of gauge invariant theories is that they contain what physicists call 'non-observable' quantities. These are objects which are not in one-to-one correspondance with physical measurements. This means that there are several ways to express them as functions of the phase space variables. A way to eliminate this arbitrariness is to introduce constraints among the phase space variables themselves. One says that one fixes the gauge. However, it turns out that this procedure almost always destroys both locality and covariance of the theory. On the other hand, this choice of gauge is a local operation, and one would like, of course, such a fixing of gauge to be global. Therefore, one needs to find something else to express the gauge arbitrariness and to single out physical quantities. In Becchi et al. [1] and Tyutin [2] and many subsequent works (see, for instance, Henneaux and Teitelboim [START_REF] Henneaux | Quantization of Gauge Systems[END_REF] and the references therein), it has been shown that, if one works in a properly defined extended phase space, all gauge theories possess a nice symmetry called the BRST symmetry. Its generator is the BRST charge. This symmetry is global, and its use is sufficient to express gauge invariance in a proper way. It allows us to properly identify the space of physical states. BRST symmetry turns out to be essential in the quantization of Yang-Mills theory and in the theory of strings.

The work presented here is relevant to the classical formulation of the BRST symmetry. Considering classical gauge theories for which the (first class) constraints obey a linear as well as a nonlinear Poisson algebra, it is shown that the computation of the BRST charge can be made algorithmic. Its implementation in Reduce is discussed, and its capabilities illustrated. This work has been done in collaboration with Burnel and Dresse, and is described in Burnel et al. [START_REF] Burnel | [END_REF].

In Sect. 2, an elementary (and grossly oversimplified) introduction to gauge theories is made. The need to introduce the BRST symmetry is explained. In Sect. 3, the main mathematical steps which lead to BRST symmetry are reviewed. These use homological algebra extensively. In Sect. 4, the algorithm to compute the BRST charge is described. Finally, in Sect. 5, a few caracteristics of its implementation in Reduce are considered. Its capabilities are illustrated through the consideration of the case where the constraints are characterized by a cubic Poisson algebra.

Introduction to Gauge Theories

Lagrangian Formulation

In classical mechanics, one describes a physical system from the action principle:

S = Z t2 t1 L(q i ; _ q i ) d (1)
S = 0 (2)
S is the action, t 1 ;t 2 are the initial and final times, L is the Lagrangian, q i (i =1:::n) are the coordinates and _ q i are their time derivatives. The corresponding dynamical equations are:

d dt @L @ _ q i @L @q i (3)
Once the initial conditions q i (0); _ q i (0) are given, they allow to determine q i (t); _ q i (t) for any t so that the physical state of the system is uniquely determined. However, the converse is not true, in general.

A given physical state may be described by several (generalized) coordinate variables. For instance let:

LL(q 1 q 2 ;_ q 1 _ q 2 ) (

All functions q i (t);i=1 ;2

q i ( t)=q i 0 ( t)+(t) (5)
where (t) is an arbitrary function of t such that ( 0 )=0describe the same physical state. So, an intuitive way to see gauge theories is to think of them as models which describe a physical system through a set of generalized coordinate variables which are not uniquely determined by the dynamical equations and the initial conditions.

Hamiltonian Formulation

Momenta are defined by

p i = @L @ _ q i = f(q i ; _ q i ) (6)
Together with the coordinates they form the phase space of the system. If we express the total time derivative in (3) in terms of the partial derivatives, one sees that the accelerations q i are uniquely defined only if dtm @ 2 L @ _ q i @ _ q j 6 =0

Here one is interested to the case where this determinant is equal to zero. In that case, the functions given by ( 6) cannot be inverted. The momenta are not all independent, i.e. there exists K relations among the q i 0 s; p i 0 s. Let them be C m (q i ;p i )=0 ;m=1;:::K

These relations mean that the motion of the system develops inside a subspace of the phase space. One can give a hamiltonian formulation of the action principle. When such relations exist, the hamiltonian (H) is not uniquely determined. Indeed, one can always replace it by

H H 0 = H + u m (p; q)C m (9)
The eqations of motion can be rewritten

_ q i = @H @p i + u m @C m @p i (10)
_ p i = @H @q i u m @C m @q i (11) C m (q; p)=0

The constraints should be conserved in time. This means

_ C m = fC m ;Hg+u m 0 fC m ;C m 0g =0 (13)
where, by definition, the Poisson brackets are fA; Bg = @A @q i @B @p i @A @p i @B @q i (14

)
New constraints are generated by (13). Some of them depend on the u's. They are such that some of their Poisson brackets with the C m 's are different from zero. When this is encountered, one can eliminate some of the Lagrange parameters in [START_REF] Caprasse | ASSIST.RED REDUCE library[END_REF]. They are called second class constraints. They can be treated properly by replacing the Poisson brackets by the Dirac brackets [START_REF] Dirac | Lectures on Quantum Mechanics[END_REF]. So as not to obscure the discussion, one makes the simplifying assumption that all new constraints are independent of the u's. If there are J new constraints, they must be added to the previous one. They are called first class constraints. All these new constraints are first class functions. This means that they satisfy fF;C i g = j i (p; q)C j (15)

One groups them together with the primary constraints in M = K + J constraints. They form a Poisson algebra, i.e. they satisfy the equation

fC a ;C b g=f c ab (q i ;p i )C c (16)
Each first class constraint is also the generator of a gauge transformation which acts on any function F of the phase space variables in the following way:

F = a fF;C a g (17)
These transformations determine the gauge orbits.

The Algebraic Structures on Phase Space

Let C 1 (P ) be the set of regular functions on phase space such that (i) multiplication is associative;

(ii) Poisson brackets of any two functions exists and have the derivation property.

The geometry of phase space is sympletic.

Let be the surface in phase space defined by all first class functions. One defines:

N(P )=fFjF= a (q; p)C a g (18)
This set is invariant under the gauge transformations (17). Moreover, it is an ideal of C 1 (P). One is led to define the set of regular functions on , which is named C 1 (), as the quotient C 1 () = C 1 (P)=N(P)

Two functions F and F 0 are said equivalent, i.e.

F F 0 iff F 0 F = a (q; p) C a A quantity is physical iff it belongs to C 1 ();
it is invariant under all transformations (17).

Gauge Fixing

The gauge freedom indicates that there are several sets of canonical variables that correspond to a given physical state. Each physical state is characterized by an equivalence class in C 1 (). One would like to recover the one-to-one correspondance between it and its expression in terms of the canonical variables. This is only possible if one fixes the gauge. This can be done if one imposes additional relations ff b (q; p) 0 b =1;:::;Ng (ii) dtm(ff b ;C a g)6 =0.

The surface generated by (20) (with N = M) should intersect gauge orbits at one point only. If this is always possible locally, it turns out that it is a requirement impossible to satisfy globally. In particular, this is always so for non-abelian gauge theories. There are also other problems with this procedure: locality and (or) covariance of the theory are lost. A celebrated example of this is the Coulomb gauge (div à =0)

in electrodynamics. All this justifies the need to replace gauge fixing by something else: this is BRST symmetry. Its nice properties are:

it is a global symmetry, it avoids the construction of the reduced phase space, and it preserves locality and covariance.

The price one has to pay is the necessity to enlarge the original phase space. Let us mention that a very good account of the history of its discovery can be found in Hooft [START_REF] Hooft | Gauge Theory and Renormalization[END_REF].

Construction of the BRST Charge

The most direct way to introduce BRST symmetry is to use homological algebra. A detailed covering of its deduction can be found in Henneaux and Teitelboim [START_REF] Henneaux | Quantization of Gauge Systems[END_REF]. In this short introduction, one can only review the main mathematical steps.

Phase Space Extension

To each first class constraint C a one associates additional 'fermionic variables' a and P a . They are odd parity Grassmann variables. a has ghost number 1 while P a has ghost number 1 (these last variables are called antighosts). Poisson brackets are generalized to these variables adding to (14) the new contribution fA; Bg gh = A @ @ a @B @P a + A @ @P a @B @ a :

In particular, one gets:

f a ; b g=fP a ; P b g =0 ; f a ;P b g= a b :

Phase space is therefore enlarged:

(q i ;p j ) ! (q i ;p j ; a ;P a )

Once this is done, one can extend the hamiltonian formulation to systems involving Grassmann variables and constraints involving them.

Mathematical Ingredients

One has to use several aspects of graded differential algebras. One introduces the graded algebra A

A = k A k (23) A i A j A i+j (24)
which contains all polynomials one can build on the enlarged phase space. k is the grading -it is not necessarily positive. There are several ways to define it, as we shall see. If x 2 A i then the degree of x is

deg x = i (25)
In this frame, one introduces the notion of differential. D is a differential if

D(xy)=xD(y)+( 1) D y (D(x))y; 8x; y 2 A , D=deg D(x) deg x = 1 , D 2 =0 , (
Then for all elements of A of degree k one can define the cohomology (homology):

H k (D) = (KerD) k (ImD) k if d =1 (28)
H k (D) = (KerD) k (ImD) k if d = 1 ( 29
)
since ImD is an ideal of KerD.

Finally, one uses the concept of contracting homotopy . Suppose that for a certain grading of A an operator exists, such that

A = A (30) x = x (31) D + D =(we suppose D =1) (32)
then H 0 (D) 6 = 0

(33)

H (D) = 0 8 6 =0 (34)
The reason why H (D) is 0 comes from the fact that for 6 =0one gets, successively,

x = 1 x = 1 (D + D)x = D 1 x (35)
which shows that any element which belongs to the kernel of D also belongs to its image (here y = 1 x ).

BRST Symmetry

First, taking for the grading the degree in the P a 's of the phase space polynomials, one defines the Koszul-Tate derivative by q i =0= p i =0= a

(36)

P a = C a (37) deg = 1 (38)
then

H 0 () = C 1 () (39)
H k () = 0 8k 6 =0

It selects all phase space functions regular on the constraint surface.

Second, taking for the grading the degree in the a 's of the phase space polynomials, one defines the longitudinal derivative d by dF = fF;C a g a (41)

d a = 1 2 b c f a cb (42) deg d = +1 (43) then H 0 (d)=ffunctions invariant on g (44)
The last step is to show that there exists a differential s defined by s = + d + :::

(45)
when the grading equals the difference between the ghost number and the antighost number. Here the ::: mean contributions from operators of higher degrees. This differential acts on an arbitrary phase space function in the following way:

sF = fF; g E (46)
The index E stresses the fact that the Poisson bracket is the one generalized to the extended phase space.

H 0 (s) contains all gauge invariant functions. is the BRST charge. It is the generator of the BRST symmetry. Since s 2 =0, one gets f; g =0

It is a nilpotent operator. This property allows us to compute it.

Computation of the BRST Charge

In this section, it is shown that the computation of the BRST charge can be made fully algorithmic. Again, for a more detailed explanation the reader is referred elsewhere [START_REF] Burnel | [END_REF][START_REF] Dresse | [END_REF].

The Generalized Poisson Algebra

To be able to build the algorithm, a restriction must be made on the algebra of first class constraints: it is that the 'structure constants' may only depend on phase space through the constraints themselves,i.e. where the f i 's are constants and q is an integer.

The Algorithm

The BRST charge can be developed as a sequence over the degrees in P a 's:

= N 1 X n=0 (n) = N 1 X n=0
A j1:::jn i1:::in+1 i1 ::: i n +1 P j1 :::P j n (49)

with A A(C;f). has parity equal to 1, as it must be. On the left-hand side, the integer N is not explicitly written as an index since it is not known apriori, whether the right-hand side is a polynomial or not. In case it is a polynomial, the expression (49) furnishes a closed form expression of . It is easily seen, then, that

(0) = a C a (50)
This is a gauge transformation in which the parameters a have been replaced by a .IfO is any operator in the graded differential algebra, the differential is such that (O)=fO; (0) g (51)

From this and the nilpotent property of (47), one can deduce

(n+1) = D (n) (52)
where

D (n) = 1 2 n X k=0 f (k) ; (n k) g C + n 1 X k=0 f (k+1) ; (n k) g gh (53)
The index C means that the Poisson bracket is the ordinary bracket taken with respect to the (q i ;p j )

while the index means that the bracket is given by ( 22). From (52) one sees that at each stage of the recursive calculation (n) is determined only up to a exact expression, since 2 =0. Therefore, there is a large degree of indeterminency on the expression of . This is a problem for the algorithmization of the calculation. Therefore, one is to introduce some additional input in order to select a given solution. Two types of restrictions have been tried. The first requires that the number of terms in the expressions (n) for each n be minimized. Apart from its practical interest for the calculation itself, it has no other motivation.

How to do that in an algorithmic way is explained in Burnel et al. [START_REF] Burnel | [END_REF]. The second is more theoretically grounded. Suppose there exists a grading such that a contracting homotopy exists. It verifies

( + )A k = N k A k (54)
With respect to that grading, one can write (52)

(n+1) k = D (n) k (55)
for all k. This equation can be rewritten as

(n) = X k 1 N k D ( n 1) k (56)
if we one takes (54) into account. The particular solution is obtained if one drops on both sides. One can show that such a exists for all Poisson algebras obeying the restrictions defined in the previous subsection. It is given by Dresse [START_REF] Dresse | [END_REF] = @ @C a P a

The corresponding solution is called the 'covariant' solution because it remains invariant under any regular transformation

C a M b a C b (58) P a M b a P b (59) a (M 1 ) a b b
(60)

Applications

The computation of the BRST charge is trivial if the Poisson algebra is a Lie algebra. This is the case in all usual gauge theories closely linked to present phenomenology. The algorithm of Sect. 4 may be applied in many cases which go beyond the usual gauge theories. However, in this extended context, the calculations are much more complex and very often untractable by hand calculations. One is not even sure that there exists a closed form of . The recursive procedure must be pursued toward very big values of N , eventually, to be able to see that. This justifies the use of computer algebra in this context.

Implementation

Implementation has been done in Reduce, and it uses two complementary packages DUUMY [START_REF] Dresse | RED REDUCE library[END_REF] and ASSIST [START_REF] Caprasse | ASSIST.RED REDUCE library[END_REF]. It is written in the symbolic language. A few important remarks are in order:

(a) Since the number of constraints may be anything (and may be large), it is absolutely necessary to avoid an explicit representation of indices. The package DUMMY offers precisely the possibility to work with dummy indices and, therefore, to free oneself from the number of constraints. This package also allows us (i) to find a canonical form to any expression involving dummy indices, (ii) to include anticommutative as well as commutative operators, and

(iii) to take into account full and mixed symmetries.

The many reordering operations necessary to achieve these properties made it necessary to base the internal representation on the vector data structure for efficiency reasons. It is one of the functions of ASSIST to allow us to manipulate them in a list-like way.

The restriction on the kind of mixed symmetries which can be considered is that they may be expressed as a tree-like configuration.

(b) The package contains three files. The first contains the part of the algorithm which is application independent. The second contains the basic Poisson brackets; the third contains the Jacobi identities. The inclusion of Jacobi identities is crucial to obtain a compact meaningful result. Of course, when they are involved, we can only get a normal form. When there are several of them, the search for the normal form may be time consuming. It is done by a function which is not automatically called by the main algorithm, but which can be used at each step of the recursive calculation.

Results

The program has been applied to the usual linear algebra, to several quadratic algebras and to cubic algebras. A full discussion can be found elsewhere [START_REF] Burnel | [END_REF][START_REF] Dresse | [END_REF]. Here, one considers only the simplest example of the linear algebra, and the most spectacular of the generic cubic algebra which is a generalization of the spin 4 algebra.

Usual Linear Lie Algebras

The constraint algebra is given by fC a ;C b g=f c ab C c :

Using the program, one easily recovers the well known result

(1) = 1 2 f c ab ab P c (61)
Computing D (1) and checking that D (1) =0leads to the Jacobi identity

f c [ab f e d]c =0
One gets D (1) =0. This stops the construction because all the higher order contributions vanish.

The Generic Cubic Algebra

Of course, here there is no reason to find a closed form for . It is for this (rather academic) example that the power of the package can be best appreciated.

The generic Poisson algebra is

fC d1 ;C d2 g=f d3 d1d2 C d3 +D d3d4 d1d2 C d3 C d4 +E d3d4d5 d1d2 C d3 C d4 C d5 (62)
It is seen that the constants f; D and E must satisfy the five Jacobi identities: (64)

2D fd1d2 d7[d4 D d3gd7 d5d6] + E fd1d2d3g d7[d4 f d7 d5d6] +3f fd1 d7[d4 E d2d3gd7 d5d6] =0; (65) 3D fd3d4 d1[d2 E d5d6gd1 d7d8] +2E fd3d4d5 d1[d2 D d6gd1 d7d8] =0; (66) E d8fd1d2 [d6d7 E d3d4d5g d9]d8 =0: (67)
The calculation order by order can be done. The result is explosive if one does not enforce the simplification induced by the above identities. The one and six order results are What are the conditions required on the structure constants to guarantee the existence of a closed form solution for ? What are their meanings?

Among the many solutions, the most concise (i.e. the one which is of lowest order in P a ) is not, in general, the covariant one. So the minimal rank of the algebra is difficult to determine. Some considerations on the above questions have already been made [START_REF] Burnel | [END_REF][START_REF] Dresse | [END_REF][START_REF] Dresse | [END_REF]. To properly answer these questions, however, a deeper study of nonlinear Poisson algebras should be made. No doubt the computation of the BRST charge can play a role in that study. The package BRST turns out to be potentially very useful in that context.

  in such a way that a ff b ;C a g0) a =0 (21) This obviously implies that (i) N = M.

  D)=1. in the last equation means the parity of D. It is 0 or 1 for any object. This is the deg of D with respect to a Z 2 grading applied on A. In concrete terms, on can say that it distinguises between quantities of 'Bose' and 'Fermi' types. The kernel and the image of D are defined by KerD = fxjDx =0 g (26) ImD = fxj9y 2 A : Dy = xg

  fC a ;C b g=f c ab (C) For practical reasons, the f c ab are required to be polynomials in the C's so that the previous equation may be rewritten

=211680

  Some mathematical questions can be raised at this point:

Acknowledgements

This work has been supported by the Fonds National de la Recherche Scientifique (FNRS) and by INTAS contract 93-0030.


Alois Panholzer

Helmut Prodinger
email: helmut.prodinger@tuwien.ac.at

Descendants and ascendants in binary trees

Keywords: binary tree, tree traversal, generating function, Zeilberger's algorithm

There are three classical algorithms to visit all the nodes of a binary tree -preorder, inorder and postorder traversal. From this one gets a natural labelling of the n internal nodes of a binary tree by the numbers 1; 2;:::;n, indicating the sequence in which the nodes are visited. For given n (size of the tree) and j (a number between 1 and n), we consider the statistics number of ascendants of node j and number of descendants of node j. By appropriate trivariate generating functions, we are able to find explicit formulae for the expectation and the variance in all instances. The heavy computations that are necessary are facilitated by MAPLE and Zeilberger's algorithm. A similar problem comes from labelling the leaves from left to right by 0; 1;:::;n and considering the statistic number of ascendants (=height) of leaf j. For this, Kirschenhofer [1] has computed the average. With our approach, we are also able to get the variance. In the last section, a table with asymptotic equivalents is provided for the reader's convenience.

Introduction

Binary trees are not only interesting for combinatorialists, but also for computer scientists, since they constitute a basic data structure. As such, naturally, one needs traversal algorithms, which visit every node of the tree. Basically, there are three traversal algorithms: inorder, preorder,andpostorder traversal. They are all recursive, the left subtree being treated before the right subtree, and they differ with respect to the visit of the root: first (preorder), middle (inorder), and last (postorder). As general references, we cite Knuth [START_REF] Knuth | The Art of Computer Programming[END_REF], Sedgewick [START_REF] Sedgewick | Algorithms[END_REF], and Sedgewick and Flajolet [START_REF] Sedgewick | An Introduction to the Analysis of Algorithms[END_REF].

The performance of such algorithms is directly related to the following parameters, which are discussed in this paper: the number of ascendants of a node j, which is the number of nodes between the root and the node j; and the number of descendants of a node j, which is the number of nodes of the subtree rooted at node j. (The sum of the numbers of ascendants, over all j, is the so-called path length, a quantity that is traditionally used to measure the complexity of tree algorithms. Clearly, it is independent of the labelling.)

The three traversal algorithms induce different labellings of the nodes with the natural numbers 1; 2;:::; the first node visited gets number 1, and so on. Thus, if we have a binary tree with n internal nodes, it makes sense to speak about node j,f or1 j n (see Figures 123).

From a probabilistic point of view, there are different models, e.g. the binary search trees (e.g. see Martínez and Prodinger [START_REF] Martínez | On the number of descendants and ascendants in random search trees[END_REF]). In this paper, we concentrate on Catalan statistics, i.e. we assume that each binary tree with n internal nodes is equally likely. We denote by B the family of binary trees, sometimes called extended binary trees, which is defined by the formal identity

h + B B B = (1)
where is the symbol for an internal node and 2 is the symbol for a leaf or external node.

The family of objects from B with exactly n internal nodes is denoted by B n . Further, we write B n for the number of elements from B n . Finally, we denote with B(z)= P n 0 B n z n the ordinary generating function of the B n 's.

We are considering exact formulae for the expectation and variance of the number of ascendants (resp. descendants) of node j in a random binary tree with n internal nodes ('of size n'), for all three traversal algorithms.

A similar problem, namely the number of ascendants of the leaves (labelled from left to right by 0; 1;:::;n), was considered by Kirschenhofer [START_REF] Kirschenhofer | On the height of leaves in binary trees[END_REF][START_REF] Kirschenhofer | Some new results on the average height of binary trees[END_REF]. He obtained an explicit formula for the expected value of leaf j. (Kirschenhofer's definition of 'height' differs by 1 from our quantity.) We rederive this and compute the variance additionally.

Apart from Kirschenhofer's formula, all results seem to be new to the best of our knowledge. The reason that people were not considering such problems earlier might be related to the fact that we used the g g g g computer algebra system MAPLE quite heavily in this paper, and also the powerful algorithm of Zeilberger [7,[START_REF] Graham | Concrete Mathematics[END_REF], tools that were not generally available in the eighties. This approach might be less elegant than some clever ad hoc arguments, but it is definitely more flexible.

Except for two instances, we always get closed formulae, although sometimes of a quite complicated nature. Therefore we give asymptotic equivalents in the last section. In these two cases, the answer is given in terms of a sum, which cannot be evaluated in closed form, which might be seen for instance from the asymptotic equivalent or also with Petkovšek's algorithm [7].

The labelling by inorder traversal is equivalent to the sequence of MIN-turns; the jth MIN-turn is defined to be the root of the smallest subtree containing the leaves labelled j 1 and j. Some results about MINturns in the context of planted plane (=ordered) trees can be found elsewhere [START_REF] Kemp | On the average oscillation of a stack[END_REF][START_REF] Kirschenhofer | On the average hyperoscillations of planted plane trees[END_REF][START_REF] Kirschenhofer | On the average oscillation of the contour of monotonically labelled ordered trees[END_REF].

We would like to emphasize, however, that the spirit of this paper is on exact enumeration, not on asymptotics. Questions about limiting distributions, as treated in Gutjahr and Pflug [START_REF] Gutjahr | The asymptotic contour process of a binary tree is a Brownian excursion[END_REF] (related to Kirschenhofer's analysis) are not considered here, and referred to further research. Now we sketch the methodology that we use. We always translate the symbolic equation (1) directly into an algebraic equation for the (ordinary) trivariate generating functions

F (z; u; v)= X j 10 X nj X l0 f n;j;l z n u j v l ; (2)
where the coefficients f n;j;l are defined as the number of objects from B n , where the node with label j has exactly l ascendants (or descendants, respectively). In short, we do not need to set up recurrences, but we use the symbolic method [START_REF] Sedgewick | An Introduction to the Analysis of Algorithms[END_REF] to get the functions F (z; u; v) immediately. In general, when we are interested in a certain node j, we distinguish three cases, namely whether the root is this node or whether it lies in the left or right subtree. Consequently, the functional equations of later sections have three terms on the right-hand side. In the instance of the next section, where we consider leaves, things are similar but slightly different.

To obtain the expectation E n;j , the second factorial moment M 2 n;j and the variance V n;j of the number of ascendants (or descendants, respectively) of the node with label j in a tree with n internal nodes ('of size n') we use the relations

E n;j = 1 B n [z n u j ] @ @v F (z; u; v) v=1 ; M (2) n;j = 1 B n [z n u j ] @ 2 @v 2 F (z; u; v) v=1 ; V n;j = M (2) n;j + E n;j E 2 n;j : (3)
Using the symbolic method, the formal equation ( 1) translates into an equation of the generating function B(z):

B(z)=1+zB 2 (z) : (4)
From the solution

B(z)= 1 p 1 4 z 2 z (5)
we get the coefficients of B(z), the so called Catalan numbers

B n = 1 n +1 2 n n : (6)
To shorten the presentation, we will use the following abbreviations throughout the whole paper:

X = p 1 4z; Y = p 1 4zu ; G 1 (z; u)= @ @v F (z; u; v) v=1 ; G 2 (z; u)= @ 2 @v 2 F (z; u; v) v=1 :
2

The Height of Leaves

We begin by reviewing and extending the results given by Kirschenhofer, but with the method mentioned above. We will translate the formal identity (1) into a functional equation for the trivariate generating function of the desired parameter.

In this section, f n;j;l denotes the number of binary trees of size n, where the leaf labelled with j has height l. Then we get for the trivariate generating function F (z; u; v) of the f n;j;l , defined as in equation ( 2), the functional equation F (z; u; v)=v+zvF (z; u; v)B(z)+zuvF (z; u; v)B(zu) : (7) This leads immediately to the solution

F (z; u; v)= v 1 zvB(z) zuvB(zu) : (8)
By differentiating [START_REF] Graham | Concrete Mathematics[END_REF] we get with the use of the abbreviations from above

G 1 (z; u)= 4 ( p 1 4 z+ p 1 4 zu ) 2 = 4 (X + Y ) 2 : (9)
To find the coefficients in the expansion of 1 (X+Y ) 2 , we can expand this expression about u =1 .T h i s leads to

1 (X + Y ) 2 = X k0 1 4(k +2) 2(k +1) k+1 z k (1 4z) k+1 (u 1) k :
The coefficients are then given by the following sum:

[z n u j ] 1 (X + Y ) 2 = n X k=j 1 4(k +2 ) 2(k +1 ) k+1 n k k j ( 1)
k j 4 n k : [START_REF] Kirschenhofer | On the average hyperoscillations of planted plane trees[END_REF] We find a closed form of this sum by using Zeilberger's algorithm y [7,[START_REF] Graham | Concrete Mathematics[END_REF]: We write

F (n; j; k)= 1 4(k +2 ) 2(k +1 ) k+1 n k k j ( 1)
k j 4 n k ; then Zeilberger's algorithm finds the relation

To find an expression for the coefficients

[z n u j ] 1 (X + Y ) 2 = f (n; j)= X k2Z F( n; j; k) ; (12)
we sum the above equation over all k 2 Z.

The right side of the equation telescopes and we get the linear recurrence (for n j)

(n + 3)(n j +1 ) f( n+1 ;j)=2 ( n+ 1)(2n 2j +3)f(n; j); [START_REF] Feller | An Introduction to Probability Theory and its Applications[END_REF] and the initial condition

f (j; j)= 1 4(j +2) 2(j +1 ) j+1 :
This gives the desired result (for

0 j n) [z n u j ] 1 (X + Y ) 2 = f (n; j)= (2j + 1)(2n 2j +1 ) 2(n + 1)(n +2) 2j j 2(n j) n j : (14)
Combining equations ( 3), ( 6) and ( 14), we find again Kirschenhofer's result [START_REF] Kirschenhofer | On the height of leaves in binary trees[END_REF].

y We note that every summation done with Zeilberger's algorithm could of course also be done with hypergeometric summations.

Theorem 1. The expectation E n;j of the height of the leaf with label j in a binary tree of size n, is given by (16)

E n;j = 2(2j + 1)(2n 2j
For this, we also need the coefficients of 1 (X+Y ) 3 . To get them we make the following rearrangements:

1 (X + Y ) 3 = (X Y ) 3 (X 2 Y 2 ) 3 = X 3 3X 2 Y +3XY 2 Y 3 64z 3 (1 u) 3 = p 1 4z (1 u) 3 1 16z 3 + 1 16z 2 + 3u 16z 2 + p 1 4zu (1 u) 3 1 16z 3 3 16z 2 u 16z 2 : ( 17
)
From this we see that

[z n u j ] 1 (X + Y ) 3 =[ z n u j ] p 1 4 z (1 u) 3 1 16z 3 + 1 16z 2 + 3u 16z 2
for 0 j n; (18) which finally leads to

[z n u j ] 1 (X + Y ) 3 = 3 4 (2n + 1)(j + 1)(n j +1 ) ( n+ 1)(n + 2)(n +3) 2n n for 0 j n: (19)
With the relations (3), ( 6), ( 14) and ( 19) we get

Observing equation (3), we get as a consequence Theorem 2. The variance V n;j of the height of the leaf with label j in a binary tree of size n, is given by Now we label the nodes of the tree by 1; 2;:::;nas we visit them by inorder traversal. Then f n;j;l denotes the number of binary trees of size n, where the node with label j has exactly l descendants. The trivariate generating function F (z; u; v) (cf. ( 2)) fulfills the algebraic equation

V n;j = 12(j + 1)(2n + 1)(n j +1) (n+ 2)(n +3) 2(2j + 1)(2n 2j
F (z; u; v)=zuvB(zuv)B(zv)+zF (z; u; v)B(z)+zuB(zu)F (z; u; v) ; (22)
which can be found by translating the formal equation ( 1) appropriately. Therefore, we have the following explicit formula:

F (z; u; v)= zuvB(zv)B(zuv) 1 zB(z) zuB(zu) : (23)
From this we get by differentiating

G 1 (z; u)= 1 4 z 1 XY 1 X 1 Y +1 : (24)
The expansion of the coefficients is easy and we get

[z n u j ]G 1 (z; u)=[ z n u j ] 1 4 zXY = 1 4 2j j 2(n +1 j) n+1 j
for 1 j n:

(25)

This gives, with the relations (3), ( 6) and ( 25), Theorem 3. The expectation E n;j of the number of descendants of the node with label j, where the nodes are labelled by inorder traversal, in a binary tree of size n, is given by

E n;j = n +1
Further, we get from (23) the equation

G 2 (z; u)= (1 X )( 4X 2 Y 2 +3 X 2 Y 3 +X 2 XY 3 +2 XY 2 XY + Y 2 Y 3 ) 8zX 3 Y 3 = 1 8z 3+ 4 X 1 X 3 + 1 8 zY 4 6 X + 1 X 2 + 1 X 3 + 1 8zY 2 1 X 1 X 2 + 1 8zY 3 1+ 1 X : (27)
With the relations

[z n u j ] 1 X p Y q =[ z j u j ] 1 Y q [ z n j ] 1 X p =[ z j ] 1 X q [ z n j ] 1 X p for p; q 2 N (28) and [z n ] 1 X = 2n n ; [z n ] 1 X 2 =4 n ; [ z n ] 1 X 3 =( 2 n+1 ) 2n n ; (29)
the expansion of ( 27) is also easy to do (preferably with the use of a computer algebra system like MAPLE), and we get for (32)

The Number of Ascendants of Nodes Labelled by Inorder Traversal

Here we denote by f n;j;l the number of binary trees of size n, where the node labelled j by inorder traversal has exactly l ascendants.

For the usual trivariate generating function F (z; u; v) we get from equation ( 1) the functional equation

F (z; u; v)=zuvB(zu)B(z)+zvF (z; u; v)B(z)+zuvB(zu)F (z; u; v) ; (33)
and thus

F (z; u; v)= zuvB(z)B(zu) 1 zvB(z) zuvB(zu) : (34)
Hence, it follows by differentiation from equation (34) that

G 1 (z; u)= (1 X )(1 Y ) z(X + Y ) 2 = 1 z(X + Y ) 2 1 z(X + Y ) + XY z(X + Y ) 2 :
(35) Therefore, we need the coefficients of

[z n u j ] 1 X + Y =[ z n u j ] X Y X 2 Y 2 =[ z n u j ] p 1 4 z p 1 4 zu 4z(1 u) =[ z n u j ] p 1 4 z 4 z (1 u) = 1 2(n +1 ) 2 n n for 1 j n; (36)
and of

[z n u j ] XY (X + Y ) 2 =2 [ z n 1 u j ] 1 ( X+Y) 2 +2[z n 1 u j 1 ] 1 (X +Y) 2 [z n u j ] 1 (X+Y) 2 = (n 1)(n 8j)+8 j ( j 1) 2n(n + 1)(n +2 ) 2 j j 2 n 2 j n j
for 1 j n:

(37)

Combining equations ( 14), ( 36) and (37), we get for

1 j n [z n u j ]G 1 (z; u)= 4 jn + n 4j 2 +4 j+1 2(n + 1)(n +2) 2j j 2n +2 2 j n+1 j 2 n+1 (n+ 1)(n +2) 2n n :
This leads to Theorem 5. The expectation E n;j of the number of ascendants of the node with label j, where the nodes are labelled by inorder traversal, in a binary tree of size n, is given by

E n;j = 4jn + n 4j 2 +4j+1 2(n +2 ) 2j j 2n+2 2j n+1 j 2n n 2n +1 n+2 for 1 j n: (38)
For G 2 (z; u) we get from equation (34) by differentiating twice and evaluating

at v =1 G 2 ( z; u)= 2 (1 X )(1 Y )(X + Y 2) z(X + Y ) 3 = 4XY z(X + Y ) 3 + 4 z(X + Y ) 3 6 z(X + Y ) 2 2XY z(X + Y ) 2 + 2 z(X + Y ) : (39)
To expand this expression we need additionally

[z n u j ] XY (X + Y ) 3 = 1 2 [z n u j ] 1 X + Y [z n u j ] 1 (X + Y ) 3 +2[z n 1 u j ] 1 (X+Y) 3 +2 [ z n 1 u j 1 ] 1 ( X+Y) 3 = 2 n 2 15jn 5n +1 5 j 2 3 4(n + 1)(n + 2)(n +3 ) 2 n n for 1 j n: (40)
With the relations (39), ( 19), ( 36), ( 37) and (40) we get (for

1 j n) [z n u j ]G 2 (z; u)= 2(2n + 1)(6jn +5 n 6 j 2 +6j+9) (n+ 1)(n + 2)(n +3) 2n n 12jn 2 +5n 2 12j 2 n +3 2 jn +14n 20j 2 +2 0 j+9 ( n+ 1)(n + 2)(n +3) 2j j 2n +2 2 j n+1 j : (41)
From that we obtain Lemma 3. The second factorial moment M

n;j of the number of ascendants of the node with label j,

where the nodes are labelled by inorder traversal, in a binary tree of size n, is for all 1 j n given by M

n;j = 2(2n + 1)(6jn +5n 6j 2 +6j+9)

(n+ 2)(n +3) 12jn 2 +5 n 2 12j 2 n +32jn +1 4 n 20j 2 +20j+9 ( n+ 2)(n +3) 2 j j 2n+2 2j n+1 j 2n n : (42)
Thus, we have Theorem 6. The variance V n;j of the number of ascendants of the node with label j, where the nodes are labelled by inorder traversal, in a binary tree of size n, is for all 1 j n given by

V n;j = (2n + 1)(12jn 2 +7n 2 12j 2 n +3 6 jn +26n 24j 2 +2 4 j+ 27) (n +2 ) 2 ( n+3 ) 4 jn 3 +5n 3 4j 2 n 2 +16jn 2 +24n 2 12j 2 n+44jn+43n 32j 2 +32j+24 2(n +2) 2 (n+3 ) 2 j j 2n+2 2j n+1 j 2n n (4jn + n 4j 2 +4j+1) 2 4(n +2) 2 2 j j 2 2 n +2 2j n+1 j 2 2n n 2 :
(43)

The Number of Descendants of Nodes Labelled by Preorder Traversal

The following results are obtained by the same methods that we used in the instance of inorder traversal. So we can omit the details and only sketch the main steps to get analogous results in the case of preorder (and postorder traversal, in later sections). The trivariate generating function F (z; u; v) of the numbers f n;j;l , counting the trees of size n,w here the node with label j (labelled by preorder traversal) has exactly l descendants, is given by the functional equation

F (z; u; v)=zuvB 2 (zv)+zuF (z; u; v)B(z)+zuB(zu)F (z; u; v) ; (44)
and explicitly by

F (z; u; v)= zuvB 2 (zv) 1 zuB(z) zuB(zu) : (45)
We note that the full sum can be easily evaluated; (56)

This relation might be useful if j is rather small; the sum can always be rewritten so that it has not more than roughly n=2 terms.

To expand the quantity

G 1 (z; u)= 4(1 Y ) (1 + Y )(X + Y ) 2 = 2 zu(X + Y ) 2 4 (X + Y ) 2 2Y zu(X + Y ) 2 (59)
we still need the following expansion:

[z n u j ] Y (X + Y ) 2 =[ z n u j ] XY (X + Y ) 3 +[z n u j ] 1 (X+Y) 3 4[z n 1 u j 1 ] 1 (X + Y ) 3 = 2n +1 3j 2(n + 1)(n +2 ) 2 n n : (60)
Hencewehave

[z n u j ]G 1 (z; u)= ( jn +2n j)(2n 2j
To get the coefficients in the expansion of

G 2 (z; u)=8 (1 Y ) 2 (X + Y +2 ) ( X +Y) 3 (1 + Y ) 2 = 8(1 4uz +2 u 2 z 2 ) u 2 z 2 1 ( X +Y) 3 8(1 2uz) u 2 z 2 Y (X + Y ) 3 + 4(1 4uz +2 u 2 z 2 ) u 2 z 2 1 ( X +Y) 2 4(1 2uz) u 2 z 2 Y (X + Y ) 2 (62)
we still have to compute the coefficients [z n u j ] Y (X +Y ) 3 . As a first step, we get them as a sum:

[z n u j ] Y (X + Y ) 3 = j X k=0 [z k u k ]Y [z n k u j k ] 1 (X + Y ) 3 = 3 2 j X k=0 (2k 2)! k!(k 1)! (2(n k) + 1)(j k + 1)(n j +1 ) ( n k+ 1)(n k + 2)(n k +3 ) 2(n k) n k ; (63)
that is valid by observing the limiting relation ( 2)!

( 1)! = 1 2 . Zeilberger's algorithm evaluates this sum as before, and we obtain

[z n u j ] Y (X + Y ) 3 = (2j + 1)(2n +1 2 j )(3n 4j +3 ) 4(n + 1)(n + 2)(n +3 ) 2 j j 2 n 2 j n j : (64)
Henceweget

[z n u j ]G 2 (z; u)= 4(2n+1)(3jn
n;j of the number of ascendants of the node with label j, where the nodes are labelled by preorder traversal, in a binary tree of size n is given by

M (2) n;j = 4(2n+1)(3jn 3 +23n 3 3j 2 n 2 51jn 2 +18n 2 +33j 2 n 42jn+19n+30j 2 30j ) (n + 2)(n + 3)(n + 4)(n +5 ) ( n j +1)(11j 2 n 3 +47jn 3 +46n 3 16j 3 n 2 68j 2 n 2 44jn 2 +36n 2 35j 2 n 35jn+38n+16j 3 +20j 2 16j ) (j + 2)(n + 2)(n + 3)(n + 4)(n +5 ) 2 j +2 j+1 2n+2 2j n+1 j 2n n : (66)
This leads to the following: Theorem 10. The variance V n;j of the number of ascendants of the node with label j, where the nodes are labelled by preorder traversal, in a binary tree of size n, is given by V n;j = 2n(2n+1)(6n 4 j+28n 4 6n 3 j 2 21n 3 j +86n 3 60jn 2 40n 2 +12j 2 n+297jn 62n 186j 2 +138j 12) (n +2) 2 (n+3) 2 (n+ 4)(n +5) (j+ 1)(j + 2)(n +2) 2 (n+3) 2 (n+ 4)(n +5) (67) with = 2(2j + 1)(2n 2j + 1)(5j 2 n +26jn 5 +24n 5 8j 3 n 4 79j 2 n 4 152jn 4 132n 4 +44j 3 n 3 51j 2 n 3 554jn 3 864n 3 + 200j 3 n 2 + 919j 2 n 2 + 1112jn 2 444n 2 188j 3 n 242j 2 n + 528jn 24n 48j 3 120j 2 +48j) . (72)

Fig. 1 :Fig. 2 :

 12 Fig. 1: A binary tree with 11 internal nodes, that are labelled by inorder traversal. Node 4 has seven descendants and two ascendants, leaf 6 has a height of 5.

Fig. 3 :

 3 Fig. 3: A binary tree with 11 internal nodes, that are labelled by postorder traversal. Node 5 has one descendant and four ascendants.

Lemma 1 .

 1 The second factorial moment M (2) n;j of the height of the leaf with label j in a binary tree of size n is given for all 0 j n by

3

  The Number of Descendants of Nodes Labelled by Inorder Traversal

7Theorem 11 .

 11 The Number of Descendants of Nodes Labelled by Postorder TraversalNow f n;j;l counts the number of binary trees of size n, where the node with label j (labelled by postorder traversal) has exactly l descendants.For the trivariate generating function we get the relationF (z; u; v)=zuvB2 (zuv)+zF(z; u; v)B(z)+zB(zu)F (z; u; v) ; The expectation E n;j of the number of descendants of the node with label j,w h e r et h e nodes are labelled by postorder traversal, in a binary tree of size n, is given by

  ;j of the number of descendants of the node with label j, where the nodes are labelled by inorder traversal, in a binary tree of size n, is given by

					1 j n
	[z	n u j ]G 2 (z; u)=	n	4	1	2 j j			2 n+2 n+1	2j j		1 2	4 n +	1 8	4 j	2n+2 n+1	2j j	+	1 8	4 n +1 j	j 2j	:
																				(30)
	This leads to
	Lemma 2. The second factorial moment M	(2)
		M	(2) n;j =	(n	1)(n +1) 4	2 j j	2n+2 2j n+1 j 2n n			(31)
			+	n +1 2 n n		1 2	4	n +	1 8	4	j	2 n+2 n+1	2j j	+	1 8	4 n +1 j	j 2j	for 1 j n:
	So we get with equation (3)
		V n;j =	n(n +1 ) 4	2 j j	2n+2 2j n+1 j 2n n	(n +1) 2 16	2j j	2 2n+2 2j n+1 j n 2n 2	2
			+	n +1 2 n n		1 2	4	n +	1 8	4	j	2n+2 n+1	2 j j	+	1 8	4	n +1 j	j 2j	for 1 j n:

nTheorem 4. The variance V n;j of the number of descendants of the node with label j, where the nodes are labelled by inorder traversal, in a binary tree of size n, is given by

6

  The Number of Ascendants of Nodes Labelled by Preorder TraversalNow f n;j;l counts the number of binary trees of size n, where node with label j has exactly l ascendants.For the usual trivariate generating function, we get the relation

	F (z; u; v)=zuvB 2 (z)+zuvF (z; u; v)B(z)+zuvB(zu)F (z; u; v) ;	(57)
	from which we obtain
	F (z; u; v)=	1	zuvB 2 (z) zuvB(z) zuvB(zu)	:

  The expectation E n;j of the number of ascendants of the node with label j, where the nodes are labelled by preorder traversal, in a binary tree of size n, is given for all 1 j n by

		+1 )	2j+2	2n	2j	2n	3j	2 n+2
		( n+ 1)(n + 2)(n +3)	j+1	n	j	(n + 2)(n +3 )	n+1	;
	which proves
	Theorem 9. E n;j =	(jn +2 n (n+ 2)(n +3) j )(2n 2j +1)	2j+2 j +1	2n 2j n j 2n n	2(2n + 1)(2n (n + 2)(n +3) 3j)

:

From (45) we get

For 1 j n only the first summand contributes a nonzero coefficient. At first we get the sum

which we evaluate as before with Zeilberger's algorithm and obtain (49) and furthermore, Theorem 7. The expectation E n;j of the number of descendants of the node with label j, where the nodes are labelled by preorder traversal, in a binary tree of size n, is given by

For G 2 (z; u) we get the following expression:

To read off the coefficients in this expression, we still need to expand X 2 (X+Y ) and

we get the coefficients from

For the coefficients from 1 X 3 (X+Y ) we first get the following sum:

which can be simplified using equations ( 47) and (48), yielding

It can be shown that the remaining sum cannot be brought into a closed form; see the general comment from the introduction.

Combining these results, we get

n;j of the number of descendants of the node with label j, where the nodes are labelled by preorder traversal, in a binary tree of size n is given by M [START_REF] Knuth | The Art of Computer Programming[END_REF] n;j = n(2n 2j +1) (55)

This leads immediately to Theorem 8. The variance V n;j of the number of descendants of the node with label j, where the nodes are labelled by preorder traversal, in a binary tree of size n, is given by

Combining the earlier results we get for the coefficients

n;j of the number of descendants of the node with label j, where the nodes are labelled by postorder traversal, in a binary tree of size n is given by

This leads immediately to Theorem 12. The variance V n;j of the number of descendants of the node with label j, where the nodes are labelled by postorder traversal, in a binary tree of size n, is given by (76)

The Number of Ascendants of Nodes Labelled by Postorder Traversal

Here we denote by f n;j;l the number of binary trees of size n, where the node labelled j by postorder traversal has exactly l ascendants.

For the trivariate generating function F (z; u; v) we get the relation

and explicitly

From this equation we derive

(79)

To get the coefficients in the expansion of the above expression we need

With this we get

and Theorem 13. The expectation E n;j of the number of ascendants of the node with label j, where the nodes are labelled by postorder traversal, in a binary tree of size n, is given for all 1 j n by

Furthermore, we consider the coefficients of

(X+Y) 2 :

(83)

To do this we need

Then we get

where is given in Lemma 7, whence we have Lemma 7. The second factorial moment M (2) n;j of the number of ascendants of the node with label j, where the nodes are labelled by postorder traversal, in a binary tree of size n is given by M (2) n;j = 4(2n+1)(3jn 3 +2n 3 3j 2 n 2 9jn 2 +18n 2 +33j 2 n 84jn+40n+30j 2 30j) (n + 2)(n + 3)(n + 4)(n +5)

with =j(5n 5 26jn 4 +47n 4 +37j 2 n 3 163jn 3 +143n 3 16j 3 n 2 +116j 2 n 2 250jn 2 +129n 2 13j 2 n +31jn 40n +16j 3 68j 2 +72j 20) .

Also, we get

Theorem 14. The variance V n;j of the number of ascendants of the node with label j, where the nodes are labelled by postorder traversal, in a binary tree of size n, is given by V n;j = 2n(2n+1)(6jn 4 +n 4 +11n 3 +33jn 3 6j 2 n 3 +36jn 2 +35n 2 +12j 2 n+51jn+13n 186j 2 +234j 60) (n +2) 2 (n+3) 2 (n+ 4)(n +5)

with =j(3n 7 14jn 6 +23n 6 +19j 2 n 5 38jn 5 2n 5 8j 3 n 4 29j 2 n 4 + 428jn 4 436n 4 + 44j 3 n 3 681j 2 n 3 +1950jn 3 1271n 3 +200j 3 n 2 955j 2 n 2 +1794jn 2 1003n 2 188j 3 n+950j 2 n 1048jn+ 262n 48j 3 + 264j 2 336j + 120) .

Asymptotics

In this section we evaluate our findings asymptotically, under the assumptions j fixed; j n, with 0 <<1; n jfixed.

The asymptotics of the closed form formulae are easy. We only need to apply Stirling's formula for the factorial:

:

To evaluate the two formulae containing sums asymptotically for a fixed ration = j=n, we need additionally the arcsine-law (cf. Feller [START_REF] Feller | An Introduction to Probability Theory and its Applications[END_REF]):

arcsin p :

All the computations to get the asymptotic formulae are then standard, thus we only collect the results in a table.