# The # product in combinatorial Hopf algebras.

1 Introduction

There is a well-known Hopf algebra structure, due to Loday and Ronco [8], on the set of planar binary trees. Using a new description of the product of this algebra, (denoted here by PBT) in terms of Catalan alternative tableaux, Aval and Viennot [1] introduced a new product, denoted by #, which is compatible with the original graduation shifted by 1. Since then, Chapoton [2] has given a functorial interpretation of this operation.

Most classical combinatorial Hopf algebras, including PBT, admit a realization in terms of special families of noncommutative polynomials. We shall see that on the realization, the # product has a simple interpretation. It can in fact be defined at the level of words over the auxiliary alphabet. Then, it preserves in particular the algebras based on parking functions (PQSym), packed words (WQSym), permutations (FQSym), planar binary trees (PBT), plane trees (the free tridendriform algebra TD), segmented compositions (the free cubical algebra TC), Young tableaux (FSym), and integer compositions (Sym). All definitions not recalled here can be found, e.g., in [11, 12, 13].

In this extended abstract, most results are presented without proof.

2 A semigroup of paths

Let A be an alphabet. Words over A can be regarded as encoding paths in a complete graph with a loop on each vertex, vertices being labelled by A.

Composition of paths, denoted by #, endows the set [summation](A) = [A.sup.+] [union] {0} with the structure of a semigroup:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1)

For example, baaca#adb = baacadb and ab#cd = 0. Thus, the # product maps [A.sup.n] x [A.sup.m] to [A.sup.m+n-1]. It is graded w.r.t. the path length (i.e., the number of edges in the path).

We have the following obvious compatibilities with the concatenation product: (uv)#w = u x (v#w) and (u#v) x w = u#(vw).

Let [d.sub.k] be the linear operator on the free associative algebra K<A> (over some field K) defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (2)

Then, for u of length k, u#v = [d.sub.k] (uv).

3 Application to combinatorial Hopf algebras

The notion of a combinatorial Hopf algebra is a heuristic one, referring to rich algebraic structures arising naturally on the linear spans of various families of combinatorial objects. These spaces are generally endowed with several products and coproducts, and are in particular graded connected bialgebras, hence Hopf algebras.

The most prominent combinatorial Hopf algebras can be realized in terms of ordinary noncommutative polynomials over an auxiliary alphabet A. This means that their products, which are described by combinatorial algorithms, can be interpreted as describing the ordinary product of certain bases of polynomials in an underlying totally ordered alphabet A = {[a.sub.1] < [a.sub.2] < ...}.

We shall see that all these realizations are stable under the # product. In the case of PBT (planar binary trees), we recover the result of Aval and Viennot [1]. In this case, the #-product has been interpreted by Chapoton [2] in representation theoretical terms.

We shall start with the most natural algebra, FQSym, based on permutations. It contains as subalgebras PBT (planar binary trees or the Loday-Ronco algebra, the free dendriform algebra on one generator), FSym (free symmetric functions, based on standard Young tableaux), and Sym (noncommutative symmetric functions).

It is itself a subalgebra of WQSym, based on packed words (or set compositions), in which the role of PBT is played by the free dendriform trialgebra on one generator TD (based on Schroder trees), the free cubical trialgebra TC (segmented compositions).

Finally, all of these algebras can be embedded in PQSym, based on parking functions.

Note that although all our algebras are actually Hopf algebras, the Hopf structure does not play any role in this paper.

4 Free quasi-symmetric functions: FQSym and its subalgebras

4.1 Free quasi-symmetric functions

4.1.1 The operation [d.sub.k] on FQSym

Recall that the alphabet A is totally ordered. Thus, we can associate to any word over A a permutation [sigma] = std(w), the standardized word std(w) of w, obtained by iteratively scanning w from left to right, and labelling 1, 2,... the occurrences of its smallest letter, then numbering the occurrences of the next one, and so on. For example, std(365182122) = 687193245.

For a permutation [sigma], define

[G.sub.[sigma]] = [summation over (std(w)=[sigma])] w. (3)

We shall need the following easy property of the standardization:

Lemma 4.1 Let = [u.sub.1][u.sub.2] ... [u.sub.n] be a word over A, and [sigma] = [[sigma].sub.1] [[sigma].sub.2] ... [[sigma].sub.n] = std(u). Then, for any factor of u: std([u.sub.i][u.sub.i+1] ... [u.sub.j]) = std([[sigma].sub.i] [[sigma].sub.i+1] ... [[sigma].sub.j].

This implies that FQSym is stable under the [d.sub.k]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (4)

We shall make use of the dual basis of the [G.sub.[sigma]] when dealing with subalgebras of FQSym. In the dual basis [F.sub.[sigma]] defined by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the formula is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (5)

where [??] means that a is removed.

4.1.2 Algebraic structure

The [G.sub.[sigma]] span a subalgebra of the free associative algebra, denoted by FQSym. The product is given by

[G.sub.[alpha]][G.sub.[beta]] = [summation over ([gamma]=uv, std(u)=[alpha], std(v) = [beta])] [G.sub.[gamma]]. (6)

The set of permutations occuring in the r.h.s. is called the convolution of [alpha] and [beta], and denoted by [alpha] * [beta].

Hence,

[G.sub.[sigma]]#[G.sub.[tau]] = [d.sub.k] ([G.sub.[sigma]][G.sub.[tau]]) = [summation over (v[member of][sigma]#[tau])] [G.sub.v], (7)

where [sigma]#[tau] = {v|[absolute value of v] = k + l - 1, std([v.sub.1] ... [v.sub.k]) = [sigma]; std([v.sub.k] ... [v.sub.k+l-1]) = [tau]}.

Indeed, [G.sub.[sigma]]#[G.sub.[tau]] is the sum of all words of the form w = uxv, with std(ux) = [sigma] and std(xv) = [tau]. For example, [G.sub.132]#[G.sub.231] = [G.sub.14352] + [G.sub.15342] + [G.sub.24351] + [G.sub.25341].

4.1.3 Multiplicative bases

The multiplicative bases [S.sup.[sigma]] and [E.sup.[sigma]] of FQSym are defined by (see [4])

[S.sup.[sigma]] = [summation over ([tau][less than or equal to][sigma])] [G.sub.[tau]] and [E.sub.[sigma]] = [summation over ([tau][greater than or equal to][sigma])] [G.sub.[tau]], (8)

where [less than or equal to] denotes the left weak order.

For [alpha] [member of] [G.sub.k] and [beta] [member of] [G.sub.l], define [alpha] [up arrow] [beta] [member of] [G.sub.k+l-1] as the output of the following algorithm:

* scan the letters of [alpha] from left to right and write: [[alpha].sub.i] + [[beta].sub.1] - 1 if [[alpha].sub.i] [less than or equal to] [[alpha].sub.k] or [[alpha].sub.i] + max([beta]) - 1 if [[alpha].sub.i] > [[alpha].sub.k],

* scan the letters of [beta] starting from the second one and write: [[beta].sub.i] if [[beta].sub.i] < [[beta].sub.1] or [[beta].sub.i] + [[alpha].sub.k] - 1 if [[beta].sub.i] [greater than or equal to] [[beta].sub.1].

Similarly, define [alpha] [down arrow] [beta] by:

* scan the letters of [alpha] and write: [[alpha].sub.i] if [[alpha].sub.i] < [[alpha].sub.k] or [[alpha].sub.i] + [[beta].sub.1] - 1 if [[alpha].sub.i] [greater than or equal to] [[alpha].sub.k],

* scan the letters of [beta] starting from the second one and write: [[beta].sub.i] + [[alpha].sub.k] - 1 if [[beta].sub.i] [less than or equal to] [[beta].sub.1] or [[beta].sub.i] + max([alpha]) - 1 if [[beta].sub.i] > [[beta].sub.1].

For example, 3412 [up arrow] 35124 = 78346125 and 3412 [down arrow] 35124 = 56148237.

Theorem 4.2 The permutations appearing in a #-product [G.sub.[alpha]]#[G.sub.[beta]] is an interval of the left weak order:

[G.sub.[alpha]]#[G.sub.[beta]] = [summation over ([gamma][member of][[alpha][down arrow][beta],[alpha][up arrow][beta]] [G.sub.[gamma]]. (9)

Using only either the lower bound or the upper bound, one obtains:

Corollary 4.3 The bases [S.sup.[sigma]] and [E.sup.[sigma]] are multiplicative for the #-product:

[S.sup.[alpha]]#[S.sup.[beta]] = [S.sup.[alpha][up arrow][beta]] and [E.sup.[alpha]]#[E.sup.[beta]] = [E.sup.[alpha][down arrow][beta]]. (10)

For example, [S.sup.3412]#[S.sup.35124] = [S.sup.78346125] and [E.sup.3412]#[E.sup.35124] = [E.sup.56148237].

4.1.4 Freeness

The above description of the # product in the S basis implies the following result:

Theorem 4.4 For the # product, FQSym is free on either [S.sup.[alpha]] or [G.sub.[alpha]] where [alpha] runs over non- secable permutations, that is, permutations of size n [greater than or equal to] 2 such that any prefix [[alpha].sub.1] ... [[alpha].sub.k] of size 2 [less than or equal to] k < n is not, up to order, the union of an interval with maximal value [[sigma].sub.k] and another interval either empty or with maximal value n.

The generating series of the number of non-secable permutations (by shifted degree d'([sigma]) = n - 1 for [sigma] [member of] [G.sub.n]) is Sequence A077607 of [15]

NI(t) := 2t + 2[t.sup.2] + 8[t.sup.3] + 44[t.sup.4] + 296[t.sup.5] + 2312[t.sup.6] + ... (11)

or equivalently 1/(1 - NI(t)) = [[summation].sub.n[greater than or equal to]1] n![t.sup.n-1].

4.2 Young tableaux: FSym

The algebra FSym of free symmetric functions [3] is the subalgebra of FQSym spanned by the coplactic classes

[S.sub.t] = [summation over (Q(w)=t)] w = [summation over (P([sigma])=t)] [F.sub.[sigma]] (12)

where (P, Q) are the P-symbol and Q-symbol defined by the Robinson-Schensted correspondence. This algebra is isomorphic to the algebra of tableaux defined by Poirier and Reutenauer [14]. We shall denote by STab(n) the standard tableaux of size n.

Note that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which does not belong to FSym.

Hence FSym is not stable under the [d.sub.k]. However, we have:

Theorem 4.5 FSym is stable under the #-product.

For example,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (13)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (14)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (16)

Note that those products do not have same number of terms, so that there is no natural definition of what would be the # product on the usual (commutative) symmetric functions.

For T an injective tableau and S a subset of its entries, let us denote by [T.sub.|S] the (sub-)tableau consisting of the restriction of T to its entries in S. For T, T' two skew tableaux, we denote their plactic equivalence (as for words) by T = T', that is we can obtain T' from T by playing Jeu de Taquin. The # product in FSym is given by the following simple combinatorial rule.

Proposition 4.6 Let [T.sub.1] and [T.sub.2] be two standard tableaux of sizes k and l. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (17)

where T runs over standard tableaux of size k + l - 1 such that: [T.sub.|{1,...,k}] = [T.sub.1] and [T.sub.|{k,...,k+l- 1}] = [T.sub.2].

With this description, it is easy to compute by hand

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (18)

4.3 Planar binary trees: PBT

4.3.1 Algebraic structure

Recall that the natural basis of PBT can be defined by

[P.sub.T] = [summation over (T([sigma])=T)] [G.sub.[sigma]] (19)

where T([sigma]) is the shape of the decreasing tree of [sigma].

Proposition 4.7 The image of a tree by [d.sub.k] is either 0 or a single tree:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (20)

according to whether k is the left child of k + 1 in the unique standard binary search tree of shape T (equivalently if the k-th vertex in the infix reading of T has no right child), in which case T' is obtained from T by contracting this edge, the result being 0 otherwise.

By the above result, any product [P.sub.T'] #[P.sub.T"] is in PBT. We just need to select those linear extensions which are not annihilated by [d.sub.k]. Since [d.sub.k] ([F.sub.[sigma]]) is nonzero iff [sigma] has (as a word) a factor k k+1, the image under [d.sub.k] of the surviving linear extensions are precisely those of the poset obtained by identifying the rightmost node of T' with the leftmost node of T". Thus, # is indeed the Aval-Viennot product.

4.3.2 Multiplicative bases

The multiplicative basis of initial intervals [5] (corresponding to the projective elements of [2]) is a subset of the S basis of FQSym:

[H.sub.T] = [S.sup.T] (21)

where [tau] is the maximal element of the sylvester class T [5]. These maximal elements are the 132-avoiding permutations. Hence, they are preserved by the # operation, so that we recover Chapoton's result: the # product of two projective elements is a projective element. One can also apply the argument the other way round: since one easily checks that the # product of two permutations avoiding the pattern 132 also avoids this pattern, it is a simple proof that PBT is stable under #.

As in the case of FQSym, the fact that the S basis is still multiplicative for the # product implies that the product in the P basis is an interval in the Tamari order.

4.4 Noncommutative symmetric functions: Sym

4.4.1 Algebraic structure

Recall that Sym is freely generated by the noncommutative complete functions

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (22)

Here, we have obviously [S.sub.n]#[S.sub.m] = [S.sub.n+m-1]. This implies, for l(1) = r, I = I'[i.sub.[tau]] and J = [j.sub.1]J",

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (23)

where [S.sup.I] is the basis of products of noncommutative complete symmetric functions and [R.sub.I] are noncommutative ribbon Schur functions. For example, [R.sub.1512]#[R.sub.43] = [R.sub.15153].

Clearly, as a #-algebra, [Sym.sup.+] is the free graded associative algebra K<x, y> over the two generators x = [S.sub.2] = [R.sub.2] and y = [[LAMBDA].sub.2] = [R.sub.11] of degree 1, the neutral element being [S.sub.1] = [R.sub.1] = [[LAMBDA].sub.1].

Now, define for any composition I = ([i.sub.0], ..., [i.sub.r]), the binary word: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. On the binary coding of a composition I, one can read an expression of [R.sub.I], [S.sup.I], and [[LAMBDA].sup.1] in terms of #-products of the generators x, y: replace the concatenation product by the #-product, replace 0 by respectively x, x, or y, and 1 by respectively y, x + y, or x + y, so that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (24)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (25)

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (26)

Note that in particular, the maps sending [S.sup.I] either to [R.sub.I] or [[LAMBDA].sup.I] are algebra automorphisms. This property will extend to a Hopf algebra automorphism with the natural coproduct.

4.4.2 Coproduct

In this case, we have a natural coproduct: the one for which x and y are primitive:

[nabla][S.sub.2] = [S.sub.2] [cross product] [S.sub.1] + [S.sub.1] [cross product] [S.sub.2], and [nabla][[LAMBDA].sub.2] = [[LAMBDA].sub.2] [cross product] [[LAMBDA].sub.1] + [[LAMBDA].sub.1] [cross product] [[LAMBDA].sub.2], (27)

and, the neutral element [S.sub.1] is grouplike: [nabla][S.sub.1] = [S.sub.1] [cross product]) [S.sub.1]. Then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (28)

The coproduct of generic [S.sup.I], [[LAMBDA].sup.I], and [R.sub.I] all are the same: since x and y are primitive, x + y is also primitive, so that, e.g.,

[nabla][R.sub.I] = [summation over (w,w'|w[??]w'=b(I))] [C.sup.b(I).sub.w,w'] [R.sub.J] [cross product] [R.sub.K], (29)

where J (resp. K) are the compositions whose binary words are w (resp. w'), and [C.sup.b(I).sub.w,w'] is the coefficient of b(I) in w[??]w'. Another way of presenting this coproduct is as follows: given b(I), choose for each element if it appears on the left or on the right of the coproduct (hence giving [2.sup.[absolute value of I]-1] terms) and compute the corresponding products of x and y.

Hence, the maps sending [S.sup.I] either to [R.sub.I] or [[LAMBDA].sup.I] are Hopf algebra automorphisms.

4.4.3 Duality: quasi-symmetric functions under #

Since Sym is isomorphic to the Hopf algebra K{x, y) on two primitive generators x and y, its dual is the shuffle algebra on two generators whose coproduct is given by deconcatenation.

Since all three bases S, R, and [LAMBDA] behave in the same way for the Hopf structure, the same holds for their dual bases, so that the bases [M.sub.I], [F.sub.I], and the forgotten basis of QSym have the same product and coproduct formulas. In the basis [F.sub.I], this is

[F.sub.I]#[F.sub.J] = [summation over (w[[member of].sup.b(I)[??]b(J) [F.sub.K], (30)

where K is the composition such that b(K) = w.

For example, [F.sub.3]#[F.sub.12] = 3 [F.sub.14] + 2 [F.sub.23] + [F.sub.32], since xx[??]yx = 3yxxx + 2xyxx + xxyx.

Note that since the product is a shuffle on words in x and y, all elements in a product [F.sub.I][F.sub.J] have same length, which is l(I) + l(J) - 1.

5 Word quasi-symmetric functions: WQSym and its subalgebras

5.1 Word quasi-symmetric functions

5.1.1 Algebraic structure

Word quasi-symmetric functions are the invariants of the quasi-symmetrizing action of the symmetric group (in the limit of an infinite alphabet), see, e.g., [12].

The packed word u = pack (w) associated with a word w in the free monoid [A.sup.*] is obtained by the following process. If [b.sub.1] < [b.sub.2] < ... < [b.sub.r] are the letters occuring in w, u is the image of w by the homomorphism [b.sub.i] [??] [a.sub.i]. For example, pack (469818941) = 235414521. A word u is said to be packed if pack (u) = u. Such words can be interpreted as set compositions, or as faces of the permutohedreon, and are sometimes called pseudo-permutations [6].

As in the case of permutations, we have:

Lemma 5.1 Let u = [u.sub.i][u.sub.2] ... [u.sub.n] be a word over A, and v = [v.sub.1][v.sub.2] ... [v.sub.n] = pack(u). Then, for any factor of u, pack ([u.sub.i][u.sub.i+1] ... [u.sub.j]) = pack ([v.sub.i][v.sub.i+1] ... [v.sub.j]).

The natural basis of WQSym, which lifts the quasi monomial basis of QSym, is labelled by packed words. It is defined by

[M.sub.u] = [summation over (pack(w)-u)] w. (31)

Note that WQSym is stable under the operators [d.sub.k]. We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (32)

so that WQSym is also stable under #. Since in this basis the ordinary product is given by

[M.sub.u][M.sub.v] = [summation over (w=u'v'; pack(u')=u, pack(v')=v)] [M.sub.w], (33)

we have

[M.sub.u]#[M.sub.v] = [d.sub.k]([M.sub.u][M.sub.v]) = [summation over (w[member of]u#v)] [M.sub.w], (34)

where u#v = {w| [absolute value of w] = k + l - 1, pack ([w.sub.1] ... [w.sub.k]) = u; pack ([w.sub.k] ... [w.sub.k+l- 1) = v}.

For example, [M.sub.121]#[M.sub.12] = [M.sub.1212] + [M.sub.1213] + [M.sub.1312].

5.1.2 Multiplicative bases

Recall that there exists an order on packed words generalizing the left weak order : it is the pseudo-permutohedron order. This order has a definition in terms of inversions (see [6]) similar to the definition of the left weak order. The generalized inversion set of a given packed word w is the union of the set of pairs (i, j) such that i < j and [w.sub.j] > [w.sub.j] with coefficient one (full inversions), and the set of pairs (i, j) such that i < j and [w.sub.i] = [w.sub.j] with coefficient one half (half-inversions).

One then says that two words u and v satisfy u < v for the pseudo-permutohedron order iff the coefficient of any pair (i, j) in u is smaller than or equal to the same coefficient in v.

Note that the definition of u [up arrow] v and u [down arrow] v (see the section about FQSym) does not require u and v to be permutations. One then has

Theorem 5.2 The words appearing in the product [M.sub.u]#[M.sub.v] is an interval of the pseudo-permutohedron order:

[M.sub.u]#[M.sub.v] = [summation over (w[member of][u[down arrow]v,u[up arrow]v] [M.sub.w]. (35)

The multiplicative bases [S.sup.u] and [E.sup.u] of WQSym are defined in [12] by

[S.sup.u] = [summation over v[less than or equal to]u] [M.sub.v] and [E.sup.u] = [summation over v[greater than or equal to]u] [M.sub.v], (36)

where [less than or equal to] is the pseudo-permutohedron order.

Proposition 5.3 The S and E-bases are multiplicative for the #-product:

[S.sup.u]#[S.sup.v] = [S.sup.u[up arrow]v] and [E.sup.u]#[E.sup.v] = [E.sup.u[down arrow]v]. (37)

5.1.3 Freeness

As in the case of FQSym, we can describe a set of free generators in the S basis for WQSym.

We shall say that a packed word u of size n is secable if there exists a prefix [u.sub.1] ... [u.sub.k] of size 2 [less than or equal to] k < n such that: {[u.sub.1], ..., [u.sub.k]} [intersection] {[u.sub.k], ..., [u.sub.n]} = {[u.sub.k]} and the set {[u.sub.1], ..., [u.sub.k]} is, up to order the union of an interval with maximal value [u.sub.k] and another interval either empty or with maximal value the maximal entry of the whole word u.

Conversely, a packed word of size at least 2 which is not secable will be called non-secable.

Theorem 5.4 For the # product, WQSym is free on the [S.sup.u] or [M.sub.u] where u runs over non-secable packed words.

If a packed word u is weighted by [t.sup.[absolute value of u]-1], the generating series PW(t) of (unrestricted) packed words corresponds to Sequence A000670 of [15]:

PW(t) = 1 + 3t + 13[t.sup.2] + 75[t.sup.3] + 541[t.sup.4] +4683[t.sup.5] + 47293[t.sup.6] + ... (38)

The generating series NSPW of non-secable packed words is related to PW by the relation PW(t) = 1/(1 - NSPW(t)) which enables us to compute NSPW:

NSPW(t) = 3t + 4[t.sup.2] + 24[t.sup.3] + 192t + 1872[t.sup.5] + 21168[t.sup.6] + ... (39)

5.2 The free tridendriform algebra TD

The realization of the free dendriform trialgebra given in [11] involves the following construction. With any word w of length n, associate a plane tree T(w) with n +1 leaves, as follows: if m = max(w) and if w has exactly k - 1 occurences of m, write

w = [v.sub.1] m [v.sub.2] ... [v.sub.k-1] m [v.sub.k], (40)

where the [v.sub.i] may be empty. Then, T(w) is the tree obtained by grafting the subtrees T([v.sub.1]),, ..., T([v.sub.k]) (in this order) on a common root, with the initial condition T([epsilon]) = 0 for the empty word. For example, the tree associated with 243411 is

[ILLUSTRATION OMITTED] (41)

We shall call sectors the zones containing numbers and say that a sector is to the left of another sector if its number is to the left of the other one, so that the reading of all sectors from left to right of any T(w) gives back w.

Now define a polynomial by

[M.sub.t] := [summation over (T(w)=T)] [M.sub.w]. (42)

Then, exactly as in the case of PBT, we have

Theorem 5.5

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (43)

depending on whether the k-th and k + 1-th sectors are grafted on the same vertex or not. In the nonzero case, T' is obtained from T by gluing the k-th and k+1-th sectors.

Corollary 5.6 The operation # is internal on TD.

5.3 The free cubical algebra TC

Define a segmented composition as a finite sequence of integers, separated by vertical bars or commas, e.g., (2, 1 | 2 | 1, 2). We shall associate an ordinary composition with a segmented composition by replacing the vertical bars by commas. Recall that the descents of an ordinary composition are the positions of the ones in the associated binary word. In the same way, there is a natural bijection between segmented compositions of sum n and sequences of length n - 1 over three symbols <, =, >: start with a segmented composition I. If i is not a descent of the underlying composition of I, write < ; otherwise, if i corresponds to a comma, write = ; if i corresponds to a bar, write >.

Now, with each word w of length n, associate a segmented composition S(w), defined as the sequence [s.sub.1], ..., [s.sub.n-1] where [s.sub.i] is the comparison sign between [w.sub.i] and [w.sub.j+1].

For example, given w = 1615116244543, one gets the sequence <><>=<><=<>> and the segmented composition (2|2|1, 2|2, 2|1|1).

Given a segmented composition I, define: [M.sub.I] = [[summation].sub.S(T)=I] [M.sub.T].

It has been shown in [12] that the [M.sub.I] generate a Hopf subalgebra of TD and that their product is given by

[M.sub.I'][M.sub.I"] = [M.sub.I'.I"] + [M.sub.I',I"] + [M.sub.I'|I"]. (44)

where I'.I" is obtained by gluing the last part of I' with the first part of I".

As before, it is easy to see that

Theorem 5.7

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (45)

depending on whether k is not or is a descent of the underlying composition of I. In the nonzero case, I' is obtained from I by decreasing the entry that corresponds to the entry containing the k-th cell in the corresponding composition, that is, if I = ([i.sub.1], ..., [i.sub.l]) where the i are separated by commas or vertical bars, decreasing in where n is the smallest integer such that [i.sub.1] + ... + [i.sub.n] > k.

For the same reason, the following result is also true: [M.sub.I']#[M.sub.I"] = [M.sub.I'.I"], where I'.'I" amounts to glue together the last part of I' with the first part of I" minus one, leaving the other parts unchanged.

6 Parking quasi-symmetric functions: PQSym

A parking function on [n] = {1, 2, ..., n} is a word a = [a.sub.1][a.sub.2] ... an of length n on [n] whose non- decreasing rearrangement a[up arrow] = [a'.sub.1][a'.sub.2] ... an satisfies [a'.sub.i] [less than or equal to] i for all i. We shall denote by PF the set of parking functions.

For a word w over a totally ordered alphabet in which each element has a successor, one can define [13] a notion of parkized word park(w), a parking function which reduces to std(w) when w is a word without repeated letters.

For w = [w.sub.1][w.sub.2] ... [w.sub.n] on {1, 2, ...}, we set

d(w) := min{i|#{[w.sub.j] [less than or equal to] i} < i}. (46)

If d( w) = n + 1 , then w is a parking function and the algorithm terminates, returning w. Otherwise, let w' be the word obtained by decrementing all the elements of w greater than d(w). Then park(w) := park(w'). Since w' is smaller than w in the lexicographic order, the algorithm terminates and always returns a parking function.

For example, let w = (3, 5, 1, 1, 11, 8, 8, 2). Then d(w) = 6 and the word w' = (3, 5, 1, 1, 10, 7, 7, 2). Then d(w') = 6 and w" = (3, 5, 1, 1, 9, 6, 6, 2). Finally, d(w") = 8 and w'" = (3, 5, 1, 1, 8, 6, 6, 2), that is a parking function. Thus, park(w) = (3, 5, 1, 1, 8, 6, 6, 2).

Lemma 6.1 Let u = [u.sub.1][u.sub.2] ... [u.sub.n] be a word over A, and c = [c.sub.1][c.sub.2] ... [c.sub.n] = park(u). Then, for any factor of u: park([u.sub.i][u.sub.i+1] ... [u.sub.j]) = park([c.sub.i][c.sub.i+1] ... [c.sub.j]).

Recall from [13], that with a parking function a, one associates the polynomial

[G.sub.a] = [summation over (park(w)=a)] w. (47)

These polynomials form a basis of a subalgebra (i) PQSym of the free associative algebra over A. In this basis, the product is given by

[G.sub.a][G.sub.b] = [summation over (c=uv; park(u)=a, park(v)=b)] [G.sub.c]. (48)

Thus,

[G.sub.a]#[G.sub.b] = [summation over (c[member of]a#b)] [G.sub.c], (49)

where a#b = {c| [absolute value of c] = k + l - 1, park([c.sub.1] ... [c.sub.k]) = a, park([c.sub.k] ... [c.sub.k+l-1]) = b}. Indeed, [G.sub.a]#[G.sub.b] is the sum of all words of the form w = uxv, with park(ux) = a and park(xv) = b.

Note that PQSym is not stable under the operators [d.sub.k]. For example, [d.sub.1]([G.sub.112]) is not in PQSym. However, let [d'.sub.k] be the linear operator defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (50)

Proposition 6.2 Then, if a is of length k, one has: [G.sub.a]#[G.sub.b] = [d'.sub.k]([G.sub.a][G.sub.b]).

For example, [G.sub.121]#[G.sub.1141] = [G.sub.121161] + [G.sub.121151] + [G.sub.121141].

References

[1] J.-C. AVAL and X. VIENNOT, The product of trees in the Loday-Ronco algebra through Catalan alternative tableaux, Sem. Lothar. Combin. 63, [B63h].

[2] F. CHAPOTON, Some dendriform functors, arXiv:0909.2751.

[3] G. DUCHAMP, F. HIVERT, and J.-Y. THIBON, Noncommutative symmetric functions VI: free quasi-symmetric functions and related algebras, Internat. J. Alg. Comput. 12 (2002), 671-717.

[4] G. DUCHAMP, F. HIVERT, J.-C. NOVELLI, and J.-Y. THIBON, Noncommutative symmetric functions VII: free quasi-symmetric functions revisited, to appear in Ann. Combinat.

[5] F. HIVERT, J.-C. NOVELLI, and J.-Y. THIBON. The algebra of binary search trees, Theoret. Comput. Sci. 339 (2005), 129-165.

[6] D. KROB, M. LATAPY, J.-C. NOVELLI, H. D. PHAN and S. SCHWER, Pseudo-Permutations I: First Combinatorial and Lattice Properties, FPSAC'01, H. Barcelo, ed., 2000.

[7] D. KROB, B. LECLERC, and J.-Y. THIBON, Noncommutative symmetric functions II: Transformations of alphabets, Internat. J. Alg. Comput. 7 (1997), 181-264.

[8] J.-L. LODAY and M.O. RONCO, Hopf algebra of the planar binary trees, Adv. Math. 139 (1998) n. 2, 293-309.

[9] J.-L. LODAY and M. O. RONCO, Trialgebras and families of polytopes, Contemporary Mathematics 346 (2004).

[10] I.G. MACDONALD, Symmetric functions and Hall polynomials, 2nd ed., Oxford University Press, 1995.

[11] J.-C. NOVELLI and J.-Y. THIBON, Construction de trigebres dendriformes, C. R. Acad. Sci, Paris, Ser. I, 342, (2006), 365-369.

[12] J.-C. NOVELLI and J.-Y. THIBON, Polynomial realizations of some trialgebras, FPSAC'06, 2006.

[13] J.-C. NOVELLI and J.-Y. THIBON, Hopf algebras and dendriform structures arising from parking functions, Fund. Math., 193 (2007), 189-241.

[14] S. POIRIER, C. REUTENAUER, Algebres de Hopf de tableaux de Young, Annales des Sciences Mathematiques du Quebec, 19 (1995), 79-90.

[15] N. J. A. SLOANE, The On-Line Encyclopedia of Integer Sequences (electronic), http://www.research.att.com/~njas/sequences/

(i) Strictly speaking, this subalgebra is rather [PQSym.sup.*], the graded dual of the Hopf algebra PQSym, but both are actually isomorphic.

J.-C. Aval (1), J.-C. Novelli (2) and J.-Y. Thibon (2)

(1) LaBRI, University de Bordeaux, Talence, France

(2) Institut Gaspard Monge, University Paris-Est Marne-la-Vallee, Marne-la-Vallee, France