# The # product in combinatorial Hopf algebras

J.-C. Aval¹, J.-C. Novelli² and J.-Y. Thibon²

¹LaBRI, Université de Bordeaux, Talence, France

²Institut Gaspard Monge, Université Paris-Est Marne-la-Vallée, Marne-la-Vallée, France

**Abstract.** We show that the # product of binary trees introduced by Aval and Viennot (2008) is in fact defined at the level of the free associative algebra, and can be extended to most of the classical combinatorial Hopf algebras.

**Résumé.** Nous montrons que le produit # introduit par Aval et Viennot (2008) est défini au niveau de l'algèbre associative libre, et peut être étendu à la plupart des algèbres de Hopf combinatoires classiques.

**Keywords:** combinatorial Hopf algebras, # product, binary trees, permutations, Young tableaux

## 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 $\mathfrak{T}\mathfrak{D}$), segmented compositions (the free cubical algebra $\mathfrak{C}$), 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 $\Sigma(A) = A^+ \cup \{0\}$ with the structure of a semigroup:

$$ua\#bv = \begin{cases} uav & \text{if } b = a, \\ 0 & \text{otherwise.} \end{cases} \qquad (1)$$
For example, $baaca\#adb = baacadb$ and $ab\#cd = 0$. Thus, the # product maps $A^n \times A^m$ to $A^{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 \cdot (v\#w)$ and $(u\#v) \cdot w = u\#(vw)$.

Let $d_k$ be the linear operator on the free associative algebra $K\langle A\rangle$ (over some field $K$) defined by

$$d_k(w) = \begin{cases} uav & \text{if } w = uaav \text{ for some } a, \text{ with } |u| = k-1, \\ 0 & \text{otherwise.} \end{cases} \qquad (2)$$

Then, for $u$ of length $k$, $u\#v = d_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_1 < a_2 < \dots\}$.

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 $\mathfrak{T}\mathfrak{D}$ (based on Schröder trees), the free cubical trialgebra $\mathfrak{T}\mathfrak{C}$ (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_k$ on FQSym

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

$$ G_{\sigma} = \sum_{\text{std}(w)=\sigma} w. \qquad (3) $$

We shall need the following easy property of the standardization:

**Lemma 4.1** Let $u_1u_2\cdots u_n$ be a word over $A$, and $\sigma = \sigma_1\sigma_2\cdots\sigma_n = \text{std}(u)$. Then, for any factor of $u$: $\text{std}(u_iu_{i+1}\cdots u_j) = \text{std}(\sigma_i\sigma_{i+1}\cdots\sigma_j)$.

This implies that $\mathbf{FQSym}$ is stable under the $d_k$:

$$ d_k(\mathbf{G}_{\sigma}) = \begin{cases} \mathbf{G}_{\text{std}(\sigma_1\cdots\sigma_{k-1}\sigma_{k+1}\cdots\sigma_n)} & \text{if } \sigma_{k+1} = \sigma_k + 1, \\ 0 & \text{otherwise.} \end{cases} \qquad (4) $$

We shall make use of the dual basis of the $G_{\sigma}$ when dealing with subalgebras of $\mathbf{FQSym}$. In the dual basis $\mathbf{F}_{\sigma}$ defined by $\mathbf{F}_{\sigma} := G_{\sigma-1}$, the formula is

$$ d_k(\mathbf{F}_{\sigma}) = \begin{cases} \mathbf{F}_{\text{std}(\sigma_1\cdots\widehat{kk+1}\cdots\sigma_n)} & \text{if } \sigma \text{ has a factor } k k+1, \\ 0 & \text{otherwise,} \end{cases} \qquad (5) $$

where $\hat{a}$ means that $a$ is removed.

### 4.1.2 Algebraic structure

The $G_{\sigma}$ span a subalgebra of the free associative algebra, denoted by $\mathbf{FQSym}$. The product is given by

$$ G_{\alpha}G_{\beta} = \sum_{\gamma=uv, \text{std}(u)=\alpha, \text{std}(v)=\beta} G_{\gamma}. \qquad (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_{\sigma} \# G_{\tau} = d_k(G_{\sigma} G_{\tau}) = \sum_{\nu \in \sigma \# \tau} G_{\nu}, \qquad (7) $$

where $\sigma \# \tau = \{\nu | |\nu| = k+l-1, \text{std}(\nu_1 \dots \nu_k) = \sigma; \text{std}(\nu_k \dots \nu_{k+l-1}) = \tau\}$.

Indeed, $G_{\sigma} \# G_{\tau}$ is the sum of all words of the form $w = uxv$, with $\text{std}(ux) = \sigma$ and $\text{std}(xv) = \tau$. For example, $G_{132} \# G_{231} = G_{14352} + G_{15342} + G_{24351} + G_{25341}$.

### 4.1.3 Multiplicative bases

The multiplicative bases $S^{\sigma}$ and $E^{\sigma}$ of $\mathbf{FQSym}$ are defined by (see [4])

$$ S^{\sigma} = \sum_{\tau \le \sigma} G_{\tau} \quad \text{and} \quad E^{\sigma} = \sum_{\tau \ge \sigma} G_{\tau}, \qquad (8) $$

where $\le$ denotes the left weak order.

For $\alpha \in \mathfrak{S}_k$ and $\beta \in \mathfrak{S}_l$, define $\alpha \uparrow \beta \in \mathfrak{S}_{k+l-1}$ as the output of the following algorithm:

* scan the letters of $\alpha$ from left to right and write: $\alpha_i + \beta_1 - 1$ if $\alpha_i \le \alpha_k$ or $\alpha_i + \max(\beta) - 1$ if $\alpha_i > \alpha_k$,
* scan the letters of $\beta$ starting from the second one and write: $\beta_i$ if $\beta_i < \beta_1$ or $\beta_i + \alpha_k - 1$ if $\beta_i \ge \beta_1$.

Similarly, define $\alpha \downarrow \beta$ by:

* scan the letters of $\alpha$ and write: $\alpha_i$ if $\alpha_i < \alpha_k$ or $\alpha_i + \beta_1 - 1$ if $\alpha_i \ge \alpha_k$,

* scan the letters of $\beta$ starting from the second one and write: $\beta_i + \alpha_k - 1$ if $\beta_i \le \beta_1$ or $\beta_i + \max(\alpha) - 1$ if $\beta_i > \beta_1$.

For example, $3412 \uparrow 35124 = 78346125$ and $3412 \downarrow 35124 = 56148237$.

**Theorem 4.2** The permutations appearing in a \#-product $G_\alpha \# G_\beta$ is an interval of the left weak order:

$$G_{\alpha} \# G_{\beta} = \sum_{\gamma \in [\alpha \downarrow \beta, \alpha \uparrow \beta]} G_{\gamma}. \qquad (9)$$

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

**Corollary 4.3** The bases $S^\sigma$ and $E^\sigma$ are multiplicative for the \#-product:

$$S^{\alpha} \# S^{\beta} = S^{\alpha \uparrow \beta} \quad \text{and} \quad E^{\alpha} \# E^{\beta} = E^{\alpha \downarrow \beta}. \qquad (10)$$

For example, $S^{3412} \# S^{35124} = S^{78346125}$ and $E^{3412} \# E^{35124} = E^{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^\alpha$ or $G_\alpha$ where $\alpha$ runs over non-secable permutations, that is, permutations of size $n \ge 2$ such that any prefix $\alpha_1 \dots \alpha_k$ of size $2 \le k < n$ is not, up to order, the union of an interval with maximal value $\sigma_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 \in \mathfrak{S}_n$) is Sequence A077607 of [15]

$$\mathrm{NI}(t) := 2t + 2t^2 + 8t^3 + 44t^4 + 296t^5 + 2312t^6 + \dots \qquad (11)$$

or equivalently $1/(1 - \mathrm{NI}(t)) = \sum_{n \ge 1} n! t^{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_t = \sum_{Q(w)=t} w = \sum_{P(\sigma)=t} F_{\sigma} \qquad (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 $\mathrm{STab}(n)$ the standard tableaux of size $n$.

Note that $S_{\begin{bmatrix} 3 & 4 \\ 1 & 2 \end{bmatrix}} = G_{2413} + G_{3412}$, so that $d_1(S_{\begin{bmatrix} 3 & 4 \\ 1 & 2 \end{bmatrix}}) = G_{312}$, which does not belong to $FSym$.

Hence $FSym$ is not stable under the $d_k$. However, we have:
**Theorem 4.5** FSym is stable under the #-product.

For example,

$$ \mathbf{S}_{\begin{smallmatrix} 2 \\ 1 & 3 \end{smallmatrix}} \# \mathbf{S}_{\begin{smallmatrix} 3 \\ 1 \end{smallmatrix}} = \mathbf{S}_{\begin{smallmatrix} 5 \\ 2 \\ 1 & 3 \end{smallmatrix}} + \mathbf{S}_{\begin{smallmatrix} 5 \\ 2 & 4 \\ 1 & 3 \end{smallmatrix}} \quad (13) $$

$$ \mathbf{S}_{\begin{smallmatrix} 3 \\ 1 & 2 \end{smallmatrix}} \# \mathbf{S}_{\begin{smallmatrix} 3 \\ 2 \\ 1 \end{smallmatrix}} = \mathbf{S}_{\begin{smallmatrix} 5 \\ 4 \\ 3 \\ 1 & 2 \end{smallmatrix}} \quad (14) $$

$$ \mathbf{S}_{\begin{smallmatrix} 3 \\ 2 \\ 1 \end{smallmatrix}} \# \mathbf{S}_{\begin{smallmatrix} 2 \\ 1 & 3 \end{smallmatrix}} = \mathbf{S}_{\begin{smallmatrix} 4 \\ 3 \\ 2 \\ 1 & 5 \end{smallmatrix}} \quad (15) $$

$$ \mathbf{S}_{\begin{smallmatrix} 3 \\ 2 \\ 1 \end{smallmatrix}} \# \mathbf{S}_{\begin{smallmatrix} 3 \\ 1 & 2 \end{smallmatrix}} = \mathbf{S}_{\begin{smallmatrix} 3 \\ 2 & 5 \\ 1 & 4 \end{smallmatrix}} + \mathbf{S}_{\begin{smallmatrix} 5 \\ 3 \\ 2 \\ 1 & 4 \end{smallmatrix}} \quad (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|_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 \equiv 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_1$ and $T_2$ be two standard tableaux of sizes $k$ and $l$. Then

$$ \mathbf{S}_{T_1} \# \mathbf{S}_{T_2} = \sum \mathbf{S}_T \quad (17) $$

where $T$ runs over standard tableaux of size $k+l-1$ such that: $T|_{\{1,...,k\}} = T_1$ and $T|_{\{k,...,k+l-1\}} = T_2$.

With this description, it is easy to compute by hand

$$ \mathbf{S}_{\begin{smallmatrix} 4 \\ 1 & 2 & 3 \end{smallmatrix}} \# \mathbf{S}_{\begin{smallmatrix} 3 \\ 1 & 2 \end{smallmatrix}} = \mathbf{S}_{\begin{smallmatrix} 6 \\ 4 & 5 \\ 1 & 2 & 3 \end{smallmatrix}} + \mathbf{S}_{\begin{smallmatrix} 6 \\ 4 \\ 1 & 2 & 3 & 5 \end{smallmatrix}} + \mathbf{S}_{\begin{smallmatrix} 4 & 6 \\ 1 & 2 & 3 & 5 \end{smallmatrix}}. \quad (18) $$

## 4.3 Planar binary trees: PBT

### 4.3.1 Algebraic structure

Recall that the natural basis of PBT can be defined by

$$ \mathbf{P}_T = \sum_{\mathcal{T}(\sigma)=T} \mathbf{G}_{\sigma} \quad (19) $$

where $\mathcal{T}(\sigma)$ is the shape of the decreasing tree of $\sigma$.
**Proposition 4.7** The image of a tree by $d_k$ is either 0 or a single tree:

$$d_k(\mathbf{P}_T) = \begin{cases} \mathbf{P}_{T'}, & \sigma \text{ is nonzero iff } \sigma \text{ has (as a word) a factor } k \sigma \text{, the image of } d_k \text{ of the surviving linear extensions is precisely those of the poset obtained by identifying the rightmost node of } T' \text{ with the leftmost node of } T''}. \\ 0, & \text{otherwise.} \end{cases} \tag{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 $\mathbf{P}_{T'} \# \mathbf{P}_{T''}$ is in PBT. We just need to select those linear extensions which are not annihilated by $d_k$. Since $d_k(\mathbf{F}_\sigma)$ is nonzero iff $\sigma$ has (as a word) a factor $k \sigma + 1$, the image under $d_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_T = S^\tau \tag{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

$$S_n(A) = \sum_{i_1 \le i_2 \le \dots \le i_n} a_{i_1} a_{i_2} \cdots a_{i_n} = G_{12 \cdots n} \tag{22}$$

Here, we have obviously $S_n \# S_m = S_{n+m-1}$. This implies, for $l(I) = r$, $I = I'_{i_r}$ and $J = j_1 J''$,

$$S^I \# S^J = S^{I' \cdot (i_r + j_1 - 1) \cdot J''} \quad \text{and similarly} \quad R_I \# R_J = R_{I' \cdot (i_r + j_1 - 1) \cdot J''} \tag{23}$$

where $S^I$ is the basis of products of noncommutative complete symmetric functions and $R_I$ are noncommutative ribbon Schur functions. For example, $R_{1512} \# R_{43} = R_{15153}$.

Clearly, as a #-algebra, $\mathbf{Sym}^+$ is the free graded associative algebra $\mathbb{K}\langle x, y \rangle$ over the two generators $x = S_2 = R_2$ and $y = \Lambda_2 = R_{11}$ of degree 1, the neutral element being $S_1 = R_1 = \Lambda_1$.

Now, define for any composition $I = (i_0, \dots, i_r)$, the binary word: $b(I) = 0^{i_0-1}1(0^{i_1-1})1 \dots (0^{i_r-1})$. On the binary coding of a composition $I$, one can read an expression of $R_I$, $S^I$, and $\Lambda^I$ 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

$$R_I := (x^{i_0-1})^{\#y} (x^{i_1-1})^{\#y} \cdots (x^{i_r-1})^{\#y}, \qquad (24)$$

$$S^I := (x^{i_0-1})^{\#(x+y)} (x^{i_1-1})^{\#(x+y)} \cdots (x^{i_r-1})^{\#(x+y)}, \qquad (25)$$

and

$$\Lambda^I := (y^{i_0-1})^{\#(y+x)} (y^{i_1-1})^{\#(y+x)} \cdots (y^{i_r-1})^{\#(y+x)}, \qquad (26)$$

Note that in particular, the maps sending $S^I$ either to $R_I$ or $\Lambda^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_2 = S_2 \otimes S_1 + S_1 \otimes S_2, \quad \text{and} \quad \nabla \Lambda_2 = \Lambda_2 \otimes \Lambda_1 + \Lambda_1 \otimes \Lambda_2, \qquad (27)$$

and, the neutral element $S_1$ is grouplike: $\nabla S_1 = S_1 \otimes S_1$. Then,

$$\nabla S_n = \sum_{i=1}^{n} \binom{n-1}{i-1} S_i \otimes S_{n+1-i}. \qquad (28)$$

The coproduct of generic $S^I$, $\Lambda^I$, and $R_I$ all are the same: since $x$ and $y$ are primitive, $x + y$ is also primitive, so that, e.g.,

$$\nabla R_I = \sum_{w, w'|w \perp w' = b(I)} C_{w, w'}^{b(I)} R_J \otimes R_K, \qquad (29)$$

where $J$ (resp. $K$) are the compositions whose binary words are $w$ (resp. $w'$), and $C_{w,w'}^{b(I)}$ is the coefficient of $b(I)$ in $w \perp 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^{|I|-1}$ terms) and compute the corresponding products of $x$ and $y$.

Hence, the maps sending $S^I$ either to $R_I$ or $\Lambda^I$ are Hopf algebra automorphisms.

### 4.4.3 Duality: quasi-symmetric functions under #

Since $\mathbf{Sym}$ is isomorphic to the Hopf algebra $\mathbb{K}\langle x, y \rangle$ 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_I$, $F_I$, and the forgotten basis of $\mathbf{QSym}$ have the same product and coproduct formulas. In the basis $F_I$, this is

$$F_I \# F_J = \sum_{w \in b(I) \perp b(J)} F_K, \qquad (30)$$

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

For example, $F_3 \# F_{12} = 3F_{14} + 2F_{23} + F_{32}$, since $xx \perp yx = 3yxx + 2xyxx + xxyx$.

Note that since the product is a shuffle on words in $x$ and $y$, all elements in a product $F_I F_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 = \text{pack}(w)$ associated with a word $w$ in the free monoid $A^*$ is obtained by the following process. If $b_1 < b_2 < \dots < b_r$ are the letters occuring in $w$, $u$ is the image of $w$ by the homomorphism $b_i \mapsto a_i$. For example, $\text{pack}(469818941) = 235414521$. A word $u$ is said to be packed if $\text{pack}(u) = u$. Such words can be interpreted as set compositions, or as faces of the permutohedron, and are sometimes called pseudo-permutations [6].

As in the case of permutations, we have:

**Lemma 5.1** Let $u = u_1u_2\cdots u_n$ be a word over $A$, and $v = v_1v_2\cdots v_n = \text{pack}(u)$. Then, for any factor of $u$, $\text{pack}(u_iu_{i+1}\cdots u_j) = \text{pack}(v_iv_{i+1}\cdots v_j)$.

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

$$ M_u = \sum_{\text{pack}(w)=u} w. \qquad (31) $$

Note that WQSym is stable under the operators $d_k$. We have

$$ d_k(\mathbf{M}_w) = \begin{cases} \mathbf{M}_{w_1 \cdots w_{k-1} w_{k+1} \cdots w_n} & \text{if } w_k = w_{k+1}, \\ 0 & \text{otherwise,} \end{cases} \qquad (32) $$

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

$$ \mathbf{M}_u \mathbf{M}_v = \sum_{w=u'v'; \text{pack}(u')=u, \text{pack}(v')=v} \mathbf{M}_w, \qquad (33) $$

we have

$$ \mathbf{M}_u \# \mathbf{M}_v = d_k(\mathbf{M}_u \mathbf{M}_v) = \sum_{w \in u \# v} \mathbf{M}_w, \qquad (34) $$

where $u \# v = \{w | |w| = k+l-1, \text{pack}(w_1 \dots w_k) = u; \text{pack}(w_k \dots w_{k+l-1}) = v\}$.

For example, $\mathbf{M}_{121} \# \mathbf{M}_{12} = \mathbf{M}_{1212} + \mathbf{M}_{1213} + \mathbf{M}_{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_i > w_j$ with coefficient one (full inversions), and the set of pairs $(i, j)$ such that $i < j$ and $w_i = w_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 \uparrow v$ and $u \downarrow 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_u \# M_v$ is an interval of the pseudo-permutohedron order:

$$ M_u \# M_v = \sum_{w \in [u \downarrow v, u \uparrow v]} M_w. \qquad (35) $$

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

$$ S^u = \sum_{v \le u} M_v \quad \text{and} \quad E^u = \sum_{v \ge u} M_v, \qquad (36) $$

where $\le$ is the pseudo-permutohedron order.

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

$$ S^u \# S^v = S^{u \uparrow v} \quad \text{and} \quad E^u \# E^v = E^{u \downarrow v}. \qquad (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_1 \dots u_k$ of size $2 \le k < n$ such that: $\{u_1, \dots, u_k\} \cap \{u_k, \dots, u_n\} = \{u_k\}$ and the set $\{u_1, \dots, u_k\}$ is, up to order the union of an interval with maximal value $u_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^u$ or $M_u$ where $u$ runs over non-secable packed words.

If a packed word $u$ is weighted by $t^{|u|-1}$, the generating series $PW(t)$ of (unrestricted) packed words corresponds to Sequence A000670 of [15]:

$$ PW(t) = 1 + 3t + 13t^2 + 75t^3 + 541t^4 + 4683t^5 + 47293t^6 + \dots \qquad (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 + 4t^2 + 24t^3 + 192t + 1872t^5 + 21168t^6 + \dots \qquad (39) $$

## 5.2 The free tridendriform algebra $\mathcal{T}\mathcal{D}$

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 $\mathcal{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_1 m v_2 \cdots v_{k-1} m v_k, \qquad (40) $$

where the $v_i$ may be empty. Then, $\mathcal{T}(w)$ is the tree obtained by grafting the subtrees $\mathcal{T}(v_1), \dots, \mathcal{T}(v_k)$ (in this order) on a common root, with the initial condition $\mathcal{T}(\epsilon) = \emptyset$ for the empty word. For example, the tree associated with 243411 is

<figure><img src="image_1.png" /></figure>
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 $\mathcal{T}(w)$ gives back $w$.

Now define a polynomial by

$$ \mathcal{M}_T := \sum_{\mathcal{T}(w)=T} \mathcal{M}_w. \qquad (42) $$

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

**Theorem 5.5**

$$ d_k(\mathcal{M}_T) = \begin{cases} \mathcal{M}_{T'}, & \mathcal{T}(w)=T \\ 0, & \mathcal{T}(w) \neq T \end{cases} \qquad (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 $\mathfrak{SD}$.

## 5.3 The free cubical algebra $\mathfrak{SC}$

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_1, \dots, s_{n-1}$ where $s_i$ is the comparison sign between $w_i$ and $w_{i+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: $\mathcal{M}_I = \sum_{S(T)=I} \mathcal{M}_T$.

It has been shown in [12] that the $\mathcal{M}_I$ generate a Hopf subalgebra of $\mathfrak{SD}$ and that their product is given by

$$ \mathcal{M}_{I'} \mathcal{M}_{I''} = \mathcal{M}_{I',I''} + \mathcal{M}_{I',I''} + \mathcal{M}_{I'|I''}. \qquad (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**

$$ d_k(\mathcal{M}_I) = \begin{cases} \mathcal{M}_{I'}, & \mathcal{T}(w)=T \\ 0, & \mathcal{T}(w) \neq T \end{cases} \qquad (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 $\mathbf{I} = (i_1, \dots, i_\ell)$ where the $i$ are separated by commas or vertical bars, decreasing $i_n$ where $n$ is the smallest integer such that $i_1 + \dots + i_n > k$.

For the same reason, the following result is also true: $\mathcal{M}_{I'} \# \mathcal{M}_{I''} = \mathcal{M}_{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, \dots, n\}$ is a word $\mathbf{a} = a_1 a_2 \cdots a_n$ of length $n$ on $[n]$ whose non-decreasing rearrangement $\mathbf{a}^\uparrow = a'_1 a'_2 \cdots a'_n$ satisfies $a'_i \le 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_1 w_2 \cdots w_n$ on $\{1, 2, \dots\}$, we set

$$d(w) := \min\{i | \#\{w_j \le i\} < i\}. \qquad (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_1 u_2 \cdots u_n$ be a word over $A$, and $\mathbf{c} = c_1 c_2 \cdots c_n = \text{park}(u)$. Then, for any factor of $u$: $\text{park}(u_i u_{i+1} \cdots u_j) = \text{park}(c_i c_{i+1} \cdots c_j)$.

Recall from [13], that with a parking function $\mathbf{a}$, one associates the polynomial

$$\mathbf{G}_{\mathbf{a}} = \sum_{\text{park}(w)=\mathbf{a}} w. \qquad (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

$$\mathbf{G}_{\mathbf{a}}\mathbf{G}_{\mathbf{b}} = \sum_{\mathbf{c}=uv; \text{park}(u)=\mathbf{a}, \text{park}(v)=\mathbf{b}} \mathbf{G}_{\mathbf{c}}. \qquad (48)$$

Thus,

$$\mathbf{G}_{\mathbf{a}}\#\mathbf{G}_{\mathbf{b}} = \sum_{\mathbf{c} \in \mathbf{a}\#\mathbf{b}} \mathbf{G}_{\mathbf{c}}, \qquad (49)$$

where $\mathbf{a}\#\mathbf{b} = \{\mathbf{c} | |\mathbf{c}| = k + l - 1, \text{park}(\mathbf{c}_1 \cdots \mathbf{c}_k) = \mathbf{a}, \text{park}(\mathbf{c}_k \cdots \mathbf{c}_{k+l-1}) = \mathbf{b}\}$. Indeed, $\mathbf{G}_{\mathbf{a}}\#\mathbf{G}_{\mathbf{b}}$ is the sum of all words of the form $w = uxv$, with $\text{park}(ux) = \mathbf{a}$ and $\text{park}(xv) = \mathbf{b}$.

Note that PQSym is not stable under the operators $d_k$. For example, $d_1(\mathbf{G}_{112})$ is not in PQSym. However, let $d'_k$ be the linear operator defined by

$$d'_{k}(\mathbf{G}_{\mathbf{c}}) = \begin{cases} \mathbf{G}_{\mathbf{c}_1 \cdots \mathbf{c}_{k-1} \mathbf{c}_{k+1} \cdots \mathbf{c}_n} & \text{if } \mathbf{c}_k = \mathbf{c}_{k+1} \text{ and } \mathbf{c}_1 \cdots \mathbf{c}_{k-1} \mathbf{c}_{k+1} \cdots \mathbf{c}_n \in \text{PF}, \\ 0 & \text{otherwise.} \end{cases} \qquad (50)$$

<footnote>(i) Strictly speaking, this subalgebra is rather PQSym*, the graded dual of the Hopf algebra PQSym, but both are actually isomorphic.</footnote>
**Proposition 6.2** Then, if a is of length k, one has: $G_a\#G_b = d'_k(G_aG_b)$.

For example, $G_{121}\#G_{1141} = G_{121161} + G_{121151} + G_{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 trigèbres dendriformes*, C. R. Acad. Sci, Paris, Sér. 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, *Algèbres de Hopf de tableaux de Young*, Annales des Sciences Mathématiques du Québec, **19** (1995), 79–90.

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