Emily Burgunder
email: burgunder@math.univ-toulouse.fr

Bérénice Delcroix-Oger

STRUCTURE THEOREMS FOR DENDRIFORM AND TRIDENDRIFORM ALGEBRAS

We state new Cartier-Milnor-Moore Poincaré-Birkhoff-Witt theorems for dendriform and tridendriform structures. We introduce the terplicial coalgebra structure as an analogue in the tridendriform algebras of the duplicial co-structure for the dendriform case, and prove a rigidity theorem.

Combinatorial objects gain in comprehension when seen as constructible from a few elements, for instance, when seen as a free algebra over a vector space. For a combinatorial object endowed with an associative algebraic operation with respect to an order, one may consider the dendriform and tridendriform algebra associated to it. Considering these finer structures reduced the dimension (rankwise) of the vector space when seen as a free dendriform or tridendriform algebra. But, proving that an object is free over one of these structure is not always easy. Some tools exist, mostly generalised Poincaré-Birkhoff-Witt Cartier-Milnor-Moore theorems or generalised Borel (called rigidity theorems). Namely, in the dendriform case with Foissy's work [START_REF] Foissy | Bidendriform bialgebras, trees and free quasi-symmetric functions[END_REF] where he considers two different dendriform structures one as an algebra and one as a coalgebra which are not dual from each other; or the work of Loday and Ronco considering an associative coalgebra and a dendriform algebra [START_REF] Loday | On the structure of cofree Hopf algebras[END_REF]. One can also consider a different approach and find a duplicial structure (closely related to the dendriform structure) and consider a duplicial-duplicial rigidity theorem due to [START_REF] Loday | Generalized bialgebras and triples of operads[END_REF]. But such an analogue would not exist in the tridendriform case. In the tridendriform case, one structure theorem is due to Maria Ronco and the first author when considering an associative structure and a tridendriform algebra.

We investigate different rigidity theorems, namely those arising from the dualisation of the dendriform or tridendriform operations. We provide explicit combinatorial expressions of the intertwining relations which permit rapidly to conclude to the non-freeness of an object and provide a deeper knowledge of it.

We introduce the terplicial algebra, and prove some rigidity theorems with a terplicial coalgebra structure, which plays an analogous role to the duplicial algebra in the dendriform case. The intertwining relations are Date: July 29, 2018. The work of the first author was supported by ANR CATHRE. The work of the second author was supported by LabEx CIMI.

short. Moreover, the free terplicial and the free tridendriform algebra are spanned by trees and the terplicial operation can be seen as a set operation related to the tridendriform one via an order, as defined in [START_REF] Vong | On (non-) freeness of some tridendriform algebras[END_REF].

The paper has two parts one dedicated to the dendriform case and the second on the tridendriform case.

It is organised as follows: we recall definitions of the dendriform and duplicial algebra and coalgebras. We introduce the duplicial dendriform bialgebra with their explicit intertwinning relations and state their associated rigidity theorem. We then apply it to reprove the freeness of the Solomon-Tits algebra and the Parking function [START_REF] Burgunder | Tridendriform structure on combinatorial Hopf algebras[END_REF][START_REF] Vong | On (non-) freeness of some tridendriform algebras[END_REF] algebra in a more concise way. To prove the intertwining relations, we give a precise description of the product and coproduct in the free algebra using paths. It introduces a whole new set of operations indexed by paths with their intertwining relations combinatorially explicited. The computation of the relations gives, as a byproduct, the number of elements of some intervals of the Tamari posets considered with Chatel and Pons [START_REF] Châtel | Counting smaller elements in the Tamari and m-Tamari lattices[END_REF].

The terplicial operad introduced later on is not exactly an analogous of the duplicial operad with regards to dendriform but merely of a skew-symmetric version. We investigate this operad and rigidity theorems associated to it.

The second part of the paper is dedicated to the tridendriform case. After recalling the definition of the tridendriform algebra and coalgebra, we introduce the terplicial algebra and coalgebra. We then state the rigidity theorem for terplicial bialgebras, co-terplicial tridendriform bialgebras, and dual tridendriform bialgebras.

The next section is devoted to a precise description of the tridendriform and the terplicial operations in the free algebra and cofree coalgebra through paths in order to prove the intertwining relations as in the dendriform case. It gives a new insight with their dual path indexed coproducts.

We then apply it to reprove Vong's theorem of the non-freeness of the Parking functions algebra with the Novelli-Thibon structure.

1 Dual dendriform bialgebras and duplicial-dendriform bialgebras.

This section is devoted to the dendriform algebra structure. We prove a new rigidity theorem for duplicial-dendriform bialgebras: a vector space with a duplicial coalgebra structure and a dendriform algebra structure which are moreover linked through intertwining relations.This is used to reprove the freeness of the Solomon-Tits algebra and the Parking algebra in a shorter and new way. We also consider a dendriform bialgebras where the operations and the cooperations are obtained by dualisation. We investigate very precisely the relations between the product and coproduct to have a deeper knowledge of free dendriform algebra as dualising an operation is the most natural thing one can do on a given combinatorial object. This investigation leads us to give the number of elements of some intervals in the Tamari posets that is considered by Chatel and Pons [START_REF] Châtel | Counting smaller elements in the Tamari and m-Tamari lattices[END_REF].

Confluence law et rigidity theorem

We recall from [START_REF] Burgunder | Rigidity theorem, freeness of algebras and applications[END_REF] the definition of a confluence law and a rigidity theorem and refer the reader to this reference for further information. Note that we are considering nonsymmetric quadratic operads here, which implies a simplification of definitions.

Definition 1.1.1. Given a vector space H which has an algebra structure given by binary products µ 1 , . . . , µ p and a coalgebra structure given by binary coproducts δ 1 , . . . , δ p , a confluence law λ is a rewriting system of (co)-algebraic expressions in H which contains:

• rules from the products µ i (x ⊗ y) → µ i (x, y) ∈ H, for any x, y ∈ H • rules from the coproducts δ i (x) → x 1 ⊗ x 2 ∈ H ⊗ H, for any x ∈ H, with x 1 ⊗ x 2 = δ i (x) using Sweedler's notation. • mixed distributive rules δ i (µ j (x ⊗ y)) → µ 1 ⊗ µ 2 (δ 1 (x) ⊗ δ 2 (y)), which is convergent, where δ 1 and δ 2 are (not necessary binary) coproducts and µ 1 and µ 2 are (not necessary binary) products. Such a confluence law enables to define a structure of bialgebra on H. Theorem 1.1.2 ([1], Rigidity theorem). Any conilpotent bialgebra satisfying a confluence law is free and cofree over its primitive elements.

1.2 Definitions: dendriform and duplicial (co)algebras. We recall the definitions of dendriform algebras, dendriform coalgebras and describe the free dendriform algebra on the vector space spanned by the planar binary rooted trees P BT, and the conilpotent cofree codendriform coalgebra. Then we recall the definitions of duplicial algebras, coalgebras and describes their free algebra and cofree conilpotent coalgebra on P BT . Definition 1.2.1. A dendriform algebra (see [START_REF] Loday | Dialgebras and related operads[END_REF]) structure on a vector space A is a pair of binary products ≺: A ⊗ A → A and : A ⊗ A → A, satisfying that:

(a ≺ b) ≺ c = a ≺ (b ≺ c + b c), (a b) ≺ c = a (b ≺ c), (a ≺ b + a b) c = a (b c).
Example 1.2.2. The free dendriform structure has been defined in [START_REF] Loday | On the structure of cofree Hopf algebras[END_REF] on the vector space spanned by labelled planar binary trees, which will be denoted P BT (V ) := P BT n ⊗ V ⊗n with V being the vector space of labellings, and P BT n the vector space generated by planar binary trees with n leaves.

For the sake of clarity, we recall that a planar rooted tree is an oriented connected acyclic graph embedded in the plane with a set of edges E(T ) and a set of vertices V (E), with a distinguished vertex ρ called the root such that there is only one non-oriented path connecting a vertex to the root. A tree will be drawn with the root at the bottom, and the orientation of the edges will be from the root to the leaves. The chosen orientation is contrary to the usual orientation on planar trees. Here, the orientation choice is for proof purposes only. For an oriented edge from a vertex a to a vertex b, the vertex a will be called a source and b a target. The vertex a is then the parent of b and b a child of a. An edge is said to be inner if its target is not a leaf. As the trees we consider are reduced the inner edges will have arity at least three (at least two out going and exactly one in-going) and the root arity at least two (at least two out-going). We present these trees with the children of a given node horizontally aligned which gives a natural description of left and right children. As considering binary planar rooted trees, one needs to add that the set of vertices is partitioned into a set of leaves with arity 1 (one in-going edge), a set of inner vertices with arity are 3 (two out-going edges and one in-going) and the root which is of arity 2 (two out-going edges).

Consider a tree T and denote T as the grafting of its left hand-side tree t l and right hand-side tree t r on the root of T and denoted T = ∨(t l ; t r ). The operations ≺, are defined on two trees T and S as

T ∅ = ∅ ≺ T = T , ∅ T = T ≺ ∅ = ∅ , T ≺ S = ∨(t l ; t r ≺ S + t r S) , (1)
T S = ∨(T ≺ s l + T s l ; s r ) . ( 2
)
We recall that Definition 1.2.3. Any codendriform coalgebra is a vector space C with two cooperations ∆ ≺ and ∆ satisfying: In other words, when considering for every T ∈ T * the elements T * defined as T * (S) = δ T S where δ is the Kroenecker symbol, this endows P BT * with a linear basis given by the T * . Then, the expressions for the cooperations reads: ∆(T ) = a,b∈P BT δ T * (a≺b) =0 1 T * (a≺b) a ⊗ b. The definition of the operations gives a constructive way to define the cooperations:

(∆ ≺ ⊗ id) • ∆ ≺ = (id ⊗ ∆ * ) • ∆ ≺ (∆ ⊗ id) • ∆ ≺ = (id ⊗ ∆ ≺ ) • ∆ (∆ * ⊗ id) • ∆ = (id ⊗ ∆ ) • ∆ , where ∆ * = ∆ ≺ + ∆ . A co-augmented conilpotent codendriform coalgebra C is a coalgebra ver- ifying that: C = ∪ n≥0 F n C where F 0 C = K, F 1 C = {x ∈ C | ∆ ≺ (x) = ∆ (x) = 0}, F n C = {x ∈ C | ∆ ≺ (x) ∈ F n-1 C ⊗2 , ∆ (x) ∈ F n-1 C ⊗2 }.
∆ (∨(t l ; t r )) = t l ⊗ ∨(∅; t r ) + ∆ * (t l ) 1 ⊗ ∨(∆ * (t l ) 2 ; t r ) (3) ∆ ≺ (∨(t l ; t r )) = ∨(t l ; ∅) ⊗ t r + ∨(t l ; ∆ * (t r ) 1 ) ⊗ ∆ * (t r ) 2 (4)
where ∆ * = ∆ ≺ + ∆ , and ∆ (∨(∅, t r )) = ∆ ≺ (∨(t l , ∅)) = 0. This can be proven by direct inspection. The above coalgebra structure on the planar binary trees is the free conilpotent codendriform coalgebra. The proof is straightforward by dualisation. Definition 1.2.5. A duplicial algebra structure on A is a pair of binary products : A ⊗ A → A and : A ⊗ A → A, satisfying that: and are associative, (x y) z = x (y z), for any x,y,z in A.

Example 1.2.6. The free duplicial structure on the planar binary rooted trees is given, for any trees T and S, by:

T ∅ = ∅ T = T , ∅ T = T ∅ = ∅ T S = ∨(T s l ; s r ) and T S = ∨(t l ; t r S)
This algebraic structure can be dualised to give the coduplicial coalgebra notion: Definition 1.2.7. A coduplicial coalgebra C is a vector space endowed with the coproducts ∆ , ∆ :

C → C ⊗ C such that: ∆ and ∆ are associative, (∆ ⊗ id) • ∆ = (id ⊗ ∆ ) • ∆ . A co-augmented conilpotent coduplicial coalgebra C is a coalgebra verifying that: C = ∪ n≥0 F n C where F 0 C = K, F 1 C = {x ∈ C | ∆ (x) = ∆ (x) = 0}, F n C = {x ∈ C | ∆ (x) ∈ F n-1 C ⊗2 , ∆ (x) ∈ F n-1 C ⊗2 }.
Example 1.2.8. The free conilpotent coduplicial coalgebra is isomorphic to the vector space generated by planar binary rooted trees, endowed with the coproducts:

∆ (T ) = t l ⊗ ∨(∅, t r ) + ∆ (t l ) 1 ⊗ ∨(∆ (t l ) 2 , t r ) ∆ (T ) = ∨(t l , ∅) ⊗ t r + ∨(t l , ∆ (t r ) 1 ) ⊗ ∆ (t r ) 2 , with ∆ (∨(t l , ∅)) = ∆ (∨(∅, t r )) = 0.

Duplicial-dendriform bialgebras.

Let H be a vector space with a dendriform algebra structure (H, ≺, ) and a codendriform coalgebra structure (H, ∆ , ∆ ). We define the confluence law linking the products and the coproducts, and state the rigidty theorem: every conilpotent coduplicial dendriform bialgebra is free and cofree on its primitive. Note that these relations are different from the one presented in [START_REF] Mansuy | Algèbres de greffes[END_REF]. Definition 1.3.1. Let H be a vector space with a dendriform algebra structure (H, ≺, ) and a codendriform coalgebra structure (H, ∆ , ∆ ). If it satisfies moreover ∀x, y ∈ H that:

∆ (x y) = x ⊗ y + x * (∆ (y)) 1 ⊗ (∆ (y)) 2 + (∆ (x)) 1 ⊗ (∆ (x)) 2 y, ∆ (x ≺ y) = (∆ (x)) 1 ⊗ (∆ (x)) 2 ≺ y, ∆ (x y) = x (∆ (y)) 1 ⊗ (∆ (y)) 2 , ∆ (x ≺ y) = x ⊗ y + x ≺ (∆ (y)) 1 ⊗ (∆ (y)) 2 + (∆ (x)) 1 ⊗ (∆ (x)) 2 * y,
where * = + ≺, then H is said to be a coduplicial-dendriform bialgebra.

Example 1.3.2. P BT endowed with the dendriform algebra structure and the coduplicial coalgebra structure is a coduplicial-dendriform bialgebra.

The proof is postponed to the section 3.4.2 using the combinatorial description of the dendriform product and the coduplicial coproduct, described in section 3.

Theorem 1.3.3. Any conilpotent coduplicial-dendriform bialgebra is free and cofree over its primitive elements.

Proof. We apply the result of [START_REF] Burgunder | Rigidity theorem, freeness of algebras and applications[END_REF]: the confluence laws are associated to the dual morphism on planar binary trees and the associated operad is non symmetric.

Indeed, P BT is free and cofree over its primitives K • ∨(∅, ∅).

Conilpotent dual dendriform bialgebras are free and cofree.

In [START_REF] Foissy | Bidendriform bialgebras, trees and free quasi-symmetric functions[END_REF], Foissy considers dendriform bialgebras: bialgebras with a dendriform structure for the algebraic and the coalgebraic structure with a confluence law linking them both. But, the confluence law between both structures is coming from a ϕ-isomorphism which is not obtained when considering dendriform products and their dual coproducts but by considering dendriform products and the dualisations of other dendriform products (see [START_REF] Burgunder | Rigidity theorem, freeness of algebras and applications[END_REF]). It seems natural to consider the case where the ϕ-isomorphism linking both structures is the case where the coalgebraic structure is the dual structure of the algebraic structure. In this section we focus on constructing the confluence law that links both structures and we show that the coproduct we define is compatible in the sense of [START_REF] Burgunder | Rigidity theorem, freeness of algebras and applications[END_REF].

Let H be a vector space with a dendriform algebra structure (H, ≺, ) and a codendriform coalgebra structure (H, ∆ ≺ , ∆ ).

We will introduce some notations:

∆ k+1 = (id ⊗k ⊗ ∆ ) • • • • • (id ⊗ ∆ ) • ∆ k+1 = •(id⊗ ) • • • • • (id ⊗k ⊗ ) α = ∆ + k=1 (-1) k (id⊗ k ) • ∆ k+1 α ≺ = ∆ ≺ + k=1 (-1) k (≺ k ⊗id) • ∆ k+1 ≺
where α , α ≺ are the alternating convolution operations, from which we deduce the idempotents ≺ •α ≺ and •α which satisfy good properties (cf. [13, proposition 2.3.5]). Note that for any tree T = ∨(t l ; t r ) the tensor product t l ⊗ ∨(∅; t r ) can be expressed as α (T ). This is proven by induction while using the definitions (3), [START_REF] Brouder | QED Hopf algebras on planar binary trees[END_REF]. Analogously, ∨(t l ; ∅) ⊗ t r can be expressed as α ≺ (T ) . Definition 1.4.1. Let H be a vector space with a dendriform algebra structure (H, ≺, ) and a codendriform coalgebra structure (H, ∆ ≺ , ∆ ). If it satisfies moreover that for all x, y ∈ H:

∆ (x y) = α (x y) + ∆ * (x * α (y) 1 ) 1 ⊗ ∆ * (x * α (y) 1 ) 2 α (y) 2 , ∆ (x ≺ y) = ∆ (x) 1 ⊗ ∆ (x) 2 ≺ y , ∆ ≺ (x y) = x ∆ ≺ (y) 1 ⊗ ∆ ≺ (y) 2 , ∆ ≺ (x ≺ y) = α ≺ (x ≺ y) + α ≺ (x) 1 ≺ ∆ * (α ≺ (x) 2 * y) 1 ⊗ ∆ * (α ≺ (x) 2 * y) 2 .
then H is said to be a dual dendriform bialgebra.

Note that this confluence law is not a finite sum of composition of tensors of operations and cooperations, but applied on an element x it is polynomial.

Example 1.4.2. P BT (V ) endowed with the above codendriform and dendriform structure is a dual dendriform bialgebra.

Proof. The definition of coproducts of trees (3), (4) applied on the operations and ≺ of two trees T = ∨(t l , t r ), S = ∨(s l , s r ) give the confluence laws when using the above remark:

∆ (T S) = T * s l ⊗ ∨(∅; s r ) + ∆ * (T * s l ) 1 ⊗ ∨(∆ * (T * s l ) 2 ; s r ) , (5) ∆ ≺ (T ≺ S) = ∨(t l ; ∅) ⊗ t r * S + ∨(t l ; ∆ * (t r * S) 1 ) ⊗ ∆ * (t r * S) 2 . ( 6
)
The proof of the relations ∆ (T ≺ S) = T ∆ ≺ (S) 1 ⊗ ∆ ≺ (S) 2 , and ∆ ≺ (T S) = ∆ (T ) 1 ⊗ ∆ (T ) 2 ≺ S are done combinatorially in section 3.4.

Theorem 1.4.3. Any conilpotent dual dendriform bialgebra is free and cofree over its primitive.

Proof. We apply the result of [START_REF] Burgunder | Rigidity theorem, freeness of algebras and applications[END_REF]: the confluence laws are associated to the dual morphism on planar binary trees and the associated operad is non symmetric.

Indeed, P BT endowed with its dual dendriform bialgebra is free and cofree on its primitives K • ∨(∅, ∅). Remark 1.4.4. Let (H, ≺, , ∆ ≺ , ∆ ) be a conilpotent dual dendriform bialgebra whose primitive elements are explicitely known. We denote by proj 1 : H ⊗ H → H the canonical projection of the first component and proj 2 the canonical projection on the second component, we denote by 1 F ≺ 1 the application which is the identity on F ≺ 1 H and null elsewhere, analogously for 1 F 1 , and by p ≺ i (resp. p i ) the composition p

≺ i := proj i •(id ⊗ 1 F ≺ 1 ) • ∆ ≺ , (p i := proj i •(1 F 1 ⊗ id) • ∆ ). We then have α ≺ = (1 F ≺ 1 ⊗ id) • ∆ ≺ and α = (id ⊗ 1 F 1 ) • ∆ on P BT (V ).
2 Application: freeness of algebras as dendriform algebras

We then apply the above rigidity theorem to some combinatorial algebras to prove their freeness as a dendriform algebra, namely the algebra of surjections and of Parking functions.

2.1 Application: freeness of the Solomon Tits algebra as a dendriform algebra. Let us consider Solomon-Tits algebra the space of surjection.

Consider the set ST r n := {x :

[n] → [r],
x surjective } and the vector space

ST = ⊕ n≥r≥1 K[ST r n ]
. For x ∈ ST r n , we write x = (x(1), . . . , x(n)), listing its images, and r = max{x(i), 1 ≤ i ≤ n}. For x ∈ ST r n , y ∈ ST s m denote the shifted concatenation by x × y = (x(1), . . . , x(n), y(1) + r, . . . , y(m) + r).

This vector space can be endowed with a dendriform structure (≺, ), see for example [START_REF] Novelli | Hopf algebras and dendriform structures arising from parking functions[END_REF][START_REF] Foissy | Bidendriform bialgebras, trees and free quasi-symmetric functions[END_REF][START_REF] Burgunder | Tridendriform structure on combinatorial Hopf algebras[END_REF], as follows:

let x ∈ ST r n , y ∈ ST s m define (1) x y := f ∈Sh (r,s) f • (x × y), (2) x ≺ y := f ∈Sh ≺ (r,s) f • (x × y),
where, f ∈ Sh ≺ is a (r, s)-shuffle such that f (r) > f (r + s) and f ∈ Sh is a (r, s)-shuffle such that f (r) < f (r + s).

Fix that x 1 K := 0 =: 1 K ≺ x and x ≺ 1 K := x =: 1 K x, for all x ∈ ST. Note that ST + := ST ⊕ K1 is not a dendriform algebra, because there does not exist a coherent way to define 1 K 1 K and 1 K ≺ 1 K .

For x ∈ ST r n , and suppose that x -1 (r) = {j 1 < • • • < j λ(x) }. We will denote by x j 1 = (x(1), . . . , x(j 1 -1)). Recursively define the list of left-to-right maxima as LR(x) = {LR(x j 1 ), j 1 } the concatenation of LR(x j 1 ) with j 1 , with LR(∅) = ∅. Similarly define the list of right-to-left maxima RL(x) := {j λ(x) , RL(x j λ(x) )}, with RL(∅) = ∅ and x j λ(x) = (x(j λ(x) + 1), . . . , x(n)). Given a map x : [n] -→ [r] there exists a unique surjective map std(x) ∈ ST r n such that x(i) < x(j) if, and only if, std(x)(i) < std(x)(j), for 1 ≤ i, j ≤ n. The map std(x) is called the standardisation of x.

We can now define a coduplicial structure on ST. For x ∈ ST r n , denote LR(x) = (l 1 , . . . , l x ):

∆ (x) = (x(1), . . . , x(l k -1)) ⊗ std(x(l k ), . . . , x(n))
with l k is the maximum element in LR(x) satisfying that x(l k ) = x(l k+1 ) + 1 and that the left hand-side of the above tensor product belongs to ST.

For x ∈ ST r n , denote RL(x) = (r 1 , . . . , r x ):

∆ (x) = std(x(1), . . . , x(r k )) ⊗ (x(r k + 1), . . . , x(n))
where r k is the minimum element in RL(x), such that the right hand-side of the above tensor product is in ST and that x(r k ) = x(r k+1 ) -1.

Proposition 2.1.2. ST endowed with the coproducts ∆ , ∆ and the dendriform structure (≺, ) is a Dup c -Dend bialgebra.

Proof. First we prove that ∆ , ∆ are coduplicial. The coassociativity of both coproducts is due to the fact that the standardisation preserves the left to right (or right to left) maxima. The confluence laws is verified as ∆ cuts after the first (from left to right) maximum of the word and that ∆ cuts after the last maximum of the word. The confluence law is verified between the coproduct and the products by direct inspection. Indeed, consider

x ∈ ST r n , y ∈ ST s m , denote ∆ (x) = x 1 ⊗ x 2 , x 1 ∈ ST r 1 n 1 , x 2 ∈ ST r 2 n 2 , ∆ (x ≺ y) = ∆ ( f ∈Sh ≺ (r,s) f • (x × y)) = f ∈Sh ≺ (r,s) x 1 ⊗ f | n+1,...,n+m • (x 2 × y) = g∈Sh ≺ (r-r 1 ,s) x 1 ⊗ g • (x 2 × y)
where given a map f :

[n] -→ [r] and a subset K of [r], the co-restriction of f to K is the map f | K := (f (j 1 ), . . . , f (j l )), where {j 1 < • • • < j l } := {i ∈ [n]/f (i) ∈ K}.
The other relations are obtained analogously.

We can reprove the known result (see [START_REF] Foissy | Bidendriform bialgebras, trees and free quasi-symmetric functions[END_REF][START_REF] Burgunder | Free algebraic structures on the permutohedra[END_REF][START_REF] Novelli | Hopf algebras and dendriform structures arising from parking functions[END_REF][START_REF] Vong | On (non-) freeness of some tridendriform algebras[END_REF]) using the coduplicialdendriform structure on ST: Proposition 2.1.3. ST is free as a dendriform algebra on its primitives.

The property is straightforward since ST is endowed with a connected Dup c -Dend bialgebra structure. Remark 2.1.4. The primitives are not the same as in [START_REF] Burgunder | Free algebraic structures on the permutohedra[END_REF] as in dimension 3 the primitives are (1, 3, 2), (2, 3, 1) whereas in [START_REF] Burgunder | Free algebraic structures on the permutohedra[END_REF] it is (1, 2, 1), [START_REF] Burgunder | Tridendriform structure on combinatorial Hopf algebras[END_REF][START_REF] Burgunder | Free algebraic structures on the permutohedra[END_REF][START_REF] Burgunder | Rigidity theorem, freeness of algebras and applications[END_REF]. The number of elements of ST for each dimension is given by the Fubini numbers [20, A00670].

Application: freeness of the Parking function algebra.

The set of Parking functions can be endowed with a dendriform structure given by the work of Novelli-Thibon [START_REF] Novelli | Hopf algebras and dendriform structures arising from parking functions[END_REF]. We follow [START_REF] Burgunder | Tridendriform structure on combinatorial Hopf algebras[END_REF].

Definition 2.2.1. A map f : [n] → [n] is called a n-non-decreasing parking function if f (i) ≤ i for 1 ≤ i ≤ n. The set of n-non-decreasing parking functions is denoted by NDPF n . The composition f := f ↑ • σ of a non-decreasing parking function f ↑ ∈ N DP F n and a permutation σ ∈ S n is called a n-parking function. The set of n-parking functions is denoted by PF n . The subset of those such that max{f (i), 1 ≤ i ≤ n} = r is denoted PF r n .
Let PQSym * denote the vector space spanned by the set n≥1 PF n of parking functions. The binary operations ≺ and on PQSym * are defined in a similar way that in the case of ST:

f ≺ g := max(h)>max(k) hk, f g := max(h)≤max(k) hk,
where the sums are taken over all pairs of maps (h, k) verifying that hk is parking, Park(h) = f and Park(k) = g, for f, g ∈ n≥1 PF n and the map Park :

n≥1 F n -→ n≥1
PF n is the Parking counterpart of the standardisation.

We will now define on the Parking function a structure of coduplicial coalgebra similarly to ST.

For x ∈ P F r n and suppose that x -1 (r) = {j 1 < • • • < j λ(x) }. We will denote by x j 1 = (x(1), . . . , x(j 1 -1)).

Define LR(x) as the concatenation of LR(x j 1 ) and j 1 , with LR(∅) = ∅.

Similarly define RL(x) as the concatenation of j λ(x) and RL(x j λ(x) ), with

RL(∅) = ∅, x j λ(x) = (x(j λ(x) + 1), . . . , x(n)). For x ∈ PF r n , denote LR(x) = (l 1 , . . . , l x ): ∆ (x) = (x(1), . . . , x(l k -1)) ⊗ std(x(l k ), . . . , x(n)) with l k ∈ LR(x) the maximum element such that x(l k ) = x(l k+1 ) + 1 and that x 1 belong to PF. For x ∈ PF r n , denote RX(x) = (r 1 , . . . , r x ): ∆ (x) = std(x(1), . . . , x(r k )) ⊗ (x(r k + 1), . . . , x(n)) where r k ∈ RL(x) the minimum element such that x 2 ∈ PF and that x(r k ) = x(r k+1 ) -1.
Proposition 2.2.2. PQSym * endowed with the coproducts ∆ , ∆ and the dendriform structure (≺, ) is a Dup c -Dend bialgebra.

Proof. The coduplicial structure is satisfied as the Parkisation of words preserve the maxima.

The confluence law is verified as in ST by direct inspection.

As a corollary:

Corollary 2.2.3. [START_REF] Burgunder | Free algebraic structures on the permutohedra[END_REF] The dendriform algebra of Parking function is free as a dendriform algebra over the vector space of its primitive elements.

3 Combinatorial description of the products and coproducts and the confluence law on P BT .

In the following section, we introduce combinatorial descriptions of the shuffle of trees from which we can then deduce the dendriform operations, and the combinatorial description of the codendriform coproduct on the vector space spanned by the planar binary rooted trees. The description are based on some shuffle paths and cutting paths in trees. These descriptions will be useful to give an explicit confluence law in terms of trees and coefficients only. This gives an efficient tool to guess the codendriform structures on examples or show that some algebras are not free for the given dendriform structure.

Cutting paths and shuffle paths.

Cutting paths:

Consider T = ∨(t l , t r ) a tree and q a path in the tree from the root to a leaf, denote e i q its edges. Note that this path only depends on the choice of a leaf. The orientation of the tree defines for every vertex the notion of a right edge and a left edge. This path is referred to as a cutting path. We now construct a coproduct indexed by this cutting path as follows.

If the path q is the leftmost path of T , denoted by l T , we will define

∆ l T (T ) = ∅ ⊗ T
and the path is the rightmost path of T , denoted by r T , we will define

∆ r T (T ) = T ⊗ ∅ .
For any other path, denoted (e 1 , . . . , e m ), define inductively the coproduct as follows:

∆ (e 1 ,...,em) T = ∨(t l , ∆ (e 2 ,...,em) (T e 1 ) 1 ) ⊗ ∆ (e 2 ,...,em) (T e 1 ) 2 e 1 is a right edge, ∆ (e 2 ,...,em) (T e 1 ) 1 ⊗ ∨(∆ (e 2 ...,em) (T e 1 ) 2 , t r ) e 1 is a left edge, (7)
using Sweedler's notation for the coproduct and where m is the total number of edges of q and T e 1 is the right (resp. left) subtree of T if e 1 is a right edge (resp. left).

Shuffle paths:

Consider a tree T = ∨(t l , t r ) with its description as a planar graph T = (V (T ); E(T )), where E(T ) ∈ V (T ) × V (T ) and e = (s(e), t(e)) for any edge e ∈ E(T ), with s(e) the source of the edge e and t(e), its target. Consider another tree S = ∨(s l , s r ) = (V (S); E(S)). Consider the path of the tree T from the root ρ T to the rightmost leaf, noted r T = (V (r T ); E(r T )), and the leftmost path of S, l S = (V (l S ); E(l S )). Note that as r T is a path in a tree one can consider E(r T ) as an ordered sequence of edges such that for two adjacent edges e 1 , e 2 ∈ E(r T ) satisfy t(e 1 ) = s(e 2 ). The same goes for E(l S ). The edges E(r T ) will be denoted e i r T , the edges of l S will be denoted e i l S for i integer. Consider the sequence of edges of p, noted (e i p ) i , result of a shuffle of the ordered edges r T with those of l S . The sequence p starts with e 1 r T or e 1 l S and will be referred to as a shuffle path of T and S. The cardinal of ordered set of vertices of p is

T = S = T * p S =
| V (p) |=| V (r T ) | + | V (l S ) | -1,
)) if e 1 p = e 1 l S ( 8
)
where m is the sum of the number of edges of r T and l S .

Therefore

T * p S = (((V (T ) ∪ V (S)) \ (V (r T ) ∪ V (l S ))) ∪ V (p), (E(T ) ∪ E(S)) \ (E(r T ) ∪ E(l S )) ∪ E(p)).
Example 3.1.1. Figure 1 gives an example of a shuffle product of two trees T and S associated to the path p = (l S 1 , r T 1 , r T 2 ) where the edges of the rightmost path of T are denoted r T 1 , r T 2 and the edge of the leftmost path of S is denoted l S 1 .

Combinatorial description of the dendriform (co)products

defined on P BT through paths.

Codendriform coproducts and cutting paths.

For a tree T we will denote Q(T ) the set of all paths from root to a non-extremal leaf of T , by Q l (resp. Q r ) the subset of paths with their first edge being a left (resp. right) edge.

T = , Q(T ) = { , , , , } ∆ * (T ) = ⊗ + ⊗ + ⊗ + ⊗ + ⊗ .
∆ * (T ) = q∈Q(T ) ∆ q (T ) ∆ (T ) = q∈Q l (T ) ∆ q (T ) ∆ ≺ (T ) = q∈Qr(T ) ∆ q (T )
Proof. It is immediate when considering the construction of the coproduct (4) and ( 3).

An example is illustrated in figure 2.

Dendriform products and shuffle paths.

For two trees T, S, we will denote P (T, S) the set of shuffle of the edges of r T with those of l S ; the subset of sequences such that the first edge is in r T (resp. in l S ) is denoted P < (T, S) (resp. P > (T, S)).

Proposition 3.2.2. Let T, S be two binary trees, then we have:

T * S = p∈P (T,S) T * p S T S = p∈P>(T,S) T * p S T ≺ S = p∈P<(T,S) T * p S
Proof. The proof is immediate when considering the constructive definition of the product (1) and (2).

∆ (T ) = 1≤k<|r T | ∆ (r T 1 ,...,r T k ,l T r k 1 ,...,l T r k |l l T r k | ) T ∆ (T ) = 1≤k<|l T | ∆ (l T 1 ,...,l T k ,r T l k 1 ,...,r T l k |r T l k | ) T
Proof. It follows from the construction of the coproducts. ,l 1 ,...,l |l S | ) S 3.4 Confluence law with non-constant coefficients on P BT . Understanding on P BT the confluence laws in a more combinatorial manner, with confluence laws with non-constant coefficients but depending on the cofiltration of the coalgebra is an efficient tool to determine either the structure "should" have a free structure on a given combinatorial object or to show rapidly that it is not free.

For example consider the free cofree conilpotent dual dendriform bialgebra on P BT with combinatorially defined products and coproducts. Understanding in a more combinatorial way the confluence law asks to compute the coefficients arising in front of the different elements appearing in it.

Example 3.4.1. In the example 3.2.3, one gets that the number of elements of T ⊗S in the coproduct of ∆ (T S) is 6 which correspond to the cutting paths drawn with dots: Note that the cutting paths and the shuffle paths coincide.

From the above example, it becomes clear that elements in the coproduct ∆ (T S) will appear multiple times: it depends on the intersection of the cutting path and the shuffle path.

Therefore, the first step is to understand the confluence law between the product associated to shuffle path and the coproduct associated to a cutting path.

Confluence laws between shuffle paths and cutting paths

Lemma 3.4.2. Let T , S be two trees, p a shuffle path of P (T, S), and q cutting path of Q(T * p S). Let p ∩ q be the possibly empty path in T * p S with edges E(p) ∩ E(q). Consider also the path in T * p S denoted q c composed of the edges E(q) \ (E(p) ∩ E(q)). This path is empty or a path with edges strictly in T or in S (denoted q T respectively q S ), according to the reached leaf.

Proof. It is proven by induction on the number of leaves using the combinatorial definitions of the product (8) and coproduct [START_REF] Châtel | Counting smaller elements in the Tamari and m-Tamari lattices[END_REF]. Indeed, in low dimensions it is clear. Suppose the property true for trees with the sum of their number of leaves inferior or equal to n. Consider two trees T = ∨(t l , t r ) and S = ∨(s l , s r ) such that the total number of their leaves is n + 1, with a shuffle path p denoted as a sequence of edges (p i ) 1≤i≤n and a cutting path q denoted as a sequence of edges (q i ) 1≤i≤m .

The following cases can occur: if q 1 = p 1 then consider the paths (p 2 , . . . , p n ) and (q 2 , . . . , q m ) in the trees T 1 = t r , S 1 = S if p 1 is the first edge of r T or T 1 = T , S 1 = s l if p 1 is the first edge of l S and conclude by induction.

If q 1 = p 1 , suppose moreover that p 1 is an edge of r T (the symmetric being p 1 is an edge of l S ). Then by construction q 1 is the left edge of the root of T . Moreover E(q) ⊂ E(T ) \ E(r T ) as ∆ q (T * p S) = ∆ (q 2 ,...,q m ) (t l ) 1 ⊗ ∨(∆ (q 2 ,...,q m ) (t l ) 2 , t r * (p 2 ,...,p n ) S).

With the notation of the above lemma, denote p c (resp. q c ) the path in T * p S defined by the sequence of edges of E(p) \ (E(p) ∩ E(q)) (resp. E(q) \ (E(p) ∩ E(q))), denote by p S (respectively p T ) the path in T * p S defined by the sequence of edges (E(p

) ∩ E(q) ∩ E(S)) ∪ E(p c ) (resp. (E(p) ∩ E(q) ∩ E(T )) ∪ E(p c )). When E(q) ⊂ E(T ) ∪ E(p ∩ q) then denote by [q] T
the path in T defined by the sequence of edges E(q) ∩ E(T ), and if E(q) ⊂ E(S) ∪ E(p ∩ q) denote by [q] S the path in S defined by the sequence of edges E(q) ∩ E(S). Lemma 3.4.3.

∆ q (T * p S) =    T ⊗ S if p = q ∆ [q] T (T ) 1 ⊗ ∆ [q] T (T ) 2 * p S S else if E(q c ) ⊂ E(T ) T * p T ∆ [q] S (S) 1 ⊗ ∆ [q] S (S) 2 else if E(q c ) ⊂ E(S)
Proof. A cutting path is determined by the leaf to which it leads, and by definition of T * p S, this leaf is a former leaf of T or of S. Therefore, all the cases are considered.

Mixed distibutive laws on co-duplicial dendriform bialgebras:

In section 1.3 the confluence laws of coduplicial-dendriform bialgebra were defined. We prove here that P BT endowed with the dendriform algebra structure and the coduplicial coalgebra structure verifies the confluence laws.

Proof. The proof is deduced from lemma 3.4.3 as the confluence laws can be rewritten in terms of product indexed by shuffle paths and coproduct indexed by cutting paths. For example ∆ (T S) rewrites in terms of paths:

∆ (T S) = p∈P<(T,S) 1≤k<|r T * pS | ∆ (r T 1 ,r T * pS 2 ,...,r T * pS k ,l T * pS r k 1 ,...,l T * pS r k |l l T * pS r k | )
T * p S .

Confluence laws on co-dendriform dendriform bialgebras:

Consider r T the rightmost path of T , denote R T its number of edges and (e T i ) i its edges 1 ≤ i ≤ R T . Respectively denote L S = #l S to be the number of edges of the leftmost path l S of a tree S, and denote (e S i ) i its edges.

Corollary 3.4.4. The number of terms of

T ⊗ S in ∆ (T S) (resp. in ∆ ≺ (T ≺ S)) is R T +L S -1 R T (resp. R T +L S -1 L S ).
Proof. From the above lemma 3.4.3, the element T ⊗ S will appear when the shuffle path and the cutting path coincide. It suffices to compute the cardinal of P < (T, S) which is the collection of shuffles of two sequences of cardinal R T and L S -1, i.e. R T +L S -1 R T . Proposition 3.4.5. For two planar binary trees T and S, the edges of the rightmost path of T will be denoted (e T i ) i and the edges of the leftmost path of S will be denote (e S i ) i . Denote by q T i (respectively q S i ) the cutting path such that i is the maximal integer such that the first i edges are the first i edges of r T (respectively of l S ), with 0 ≤ i ≤ R T , i.e. q T i = (e T 1 , . . . , e T i , q i+1 , . . . , q |q| ) with q i+1 an edge of S , denote p T j (respectively p S j ) the shuffle path such that j is the maximal integer such that the first j edges are edges of r T (resp. of l S ) with 0 ≤ j ≤ L S .

The confluence law on P BT is given by:

∆ (T S) = R T + L S -1 R T T ⊗ S + q ∈ Q(T ) q = q T i p ∈ P<(T e T i , S) p = p S j i + j -1 i ∆ q (T ) 1 ⊗ ∆ q (T ) 2 * p S + q ∈ Q l (S) q = q S i p ∈ P (T, S e S i ) p = p T i i + j -1 i T * p ∆ q (S) 1 ⊗ ∆ q (S) 2 , ∆ (T ≺ S) = ∆ (T ) 1 ⊗ ∆ (T ) 2 ≺ S , ∆ ≺ (T S) = T ∆ ≺ (S) 1 ⊗ ∆ ≺ (S) 2 , ∆ ≺ (T ≺ S) = R T + L S -1 L S T ⊗ S + + q ∈ Qr(T ) q = q T i p ∈ P (T e T i , S) p = p S j i + j -1 j ∆ q (T ) 1 ⊗ ∆ q (T ) 2 * p S + q ∈ Q(S) q = q S i p ∈ P>(T, S e S i ) p = p T j i + j -1 i T * p ∆ q (S) 1 ⊗ ∆ q (S) 2
Proof. The combinatorial description of the products 3.2.2 and coproducts 3.2.1 gives

∆ (T S) = p∈P<(T,S) q∈Q l (T * pS) ∆ q (T * p S)
Then apply lemma 3.4.3 for the shuffle paths p and cutting paths q. The coefficients appear since for any shuffle path p obtained from p, and for any cutting path q obtained from q, such that only the edges (E(p)∩E(q))∩E(T ) and (E(p) ∩ E(q)) ∩ E(S) are shuffled, then, ∆ q (T * p S) will give the same element as ∆ q (T p ≺ S)

This corollary can be expressed in terms of duplicial and dendriform products with coduplicial and codendriform coproducts with the charateristic map of the cofiltration only without refering to cutting paths and shuffle paths.

Example 3.4.6. For T ∈ F t , S ∈ F s the following confluence laws hold:

∆ (T S) = t + s -1 t T ⊗ S+ 1≤p≤t,1≤q≤s p + q -1 p 1 F q ∆ * (T ) 1 ⊗ (∆ * (T ) 2 * ∆ (S) 1 ) 1 F p ∆ (S) 2 + 1≤p≤t,1≤q≤s p + q -1 q 1 F p ∆ (T ) 1 (∆ (T ) 2 * ∆ (S) 1 ) ⊗ 1 F q ∆ (S) 2
But, as the coduplicial and duplicial structures are needed, it would be easier to refer to the coduplicial-duplicial rigidity theorem of Loday [START_REF] Loday | Generalized bialgebras and triples of operads[END_REF] or the coduplicial-dendriform rigidity theorem 1.3.3.

4 Dendriform operad and Tamari lattice.

Tamari lattice and interval-posets.

We now consider planar binary trees as defined above.

In 1962, Tamari endowed, in his article [START_REF] Tamari | The algebra of bracketings and their enumeration[END_REF], the set of planar binary trees with a structure of poset given by the following covering relation: a planar binary tree T covers a planar binary tree S if there exists a vertex v in S and T such that the three connected components C 1 , C 2 , C 3 obtained by removing v are the same in S and T where

S = v C 1 C 2 C 3 and T = v C 3 C 2 C 1 .
We denote by ≤ the partial order obtained by transitive closure of this covering relations: the obtained poset is a lattice called Tamari lattice.

Chatel and Pons interpreted the Tamari lattice in terms of poset on binary search trees with covering relation given by right rotation, commonly used in sorting algorithms (see [START_REF] Châtel | Counting smaller elements in the Tamari and m-Tamari lattices[END_REF]).

The bijection between the two interpretations is given by labelling internal nodes by integers increasingly from left to right and deleting leaves.

We recall from [START_REF] Châtel | Counting smaller elements in the Tamari and m-Tamari lattices[END_REF] the definition of interval-posets.

Definition 4.1.1 ([7], [START_REF] Châtel | Algebraic combinatorics on order of trees[END_REF]). An interval-poset is a poset with order P labelled with distinct integers {1, . . . , n} such that the following conditions hold:

• a P c and a < c implies that for all a < b < c, we have a P b,

• c P a and a < c implies that for all a < b < c, we have c P b, Example 4.1.2. The four first following posets are not interval-posets. The last one (in green) is an interval poset:

2 1 3 , 2 3 1 , 1 2 3 , 3 2 1 , 1 3 2 4 6 5
.

Chatel and Pons prove in [START_REF] Châtel | Counting smaller elements in the Tamari and m-Tamari lattices[END_REF] the following theorem:

Theorem 4.1.3 (Theorem 2.8 [START_REF] Châtel | Counting smaller elements in the Tamari and m-Tamari lattices[END_REF], [START_REF] Châtel | Algebraic combinatorics on order of trees[END_REF]). Interval-posets are in one-to-one correspondence with intervals of the Tamari lattice. Moreover, the interval I 1 is included in the interval I 2 if and only if I 1 is an extension of I 2 (contains relations of I 2 and possibly some other relations).

We use this characterisation of intervals of the Tamari lattice to describe and count elements of some intervals of the Tamari lattice.

Let us remark that the interval-poset associated with interval [T S; T S]

has two connected components, corresponding respectively to T and S. We can now enumerate elements in this type of interval, using Lemma 3.4.4.

Proposition 4.2.2. The number of elements in the intervals described above is given by: |[T S; T S]|

= R T + L S -1 L S
where R T is the number of vertices on the rightmost path of the planar binary tree T and L S is the number of vertices on the leftmost path of the planar binary tree T , for any planar binary trees T and S.

5 Skew-duplicial bialgebras, co-skew duplicial dendriform algebras.

There exists no extension of the duplicial operad in a "terplicial" operad, i.e. a symmetric set operad sharing the same underlying S n -module as the tridendriform operad and such that the right and the left products are both associative. The terplicial operad defined in the next section is then an extension of a new operad, named the Skew-duplicial operad, generated by two binary products and satisfying for any elements x, y and z:

(x y) z = x (y z) (x y) z = x (y z) (x y) z = x (y z)
Proposition 5.1.1. The free skew-duplicial operad have the same underlying module as duplicial and dendriform operads. The operations and are defined on two planar binary trees S = ∨(S l , S r ) and T = ∨(T l , T r ) by: T S = ∨(T S l , S r ), with T ∅ = T T S = ∨(T l , T r S), with ∅ T = T Proof. The proof is done by checking that the defined product is a skewduplicial product. The freeness of the defined product comes from the freeness of the dendriform product on planar binary trees: indeed the skewduplicial product is equivalent to associating to the dendriform product on binary trees the leading term for the order

S > T if |S l | > |T l | or |S l | = |T l | and |S l | > |T l |.
The dual co-Skew-duplicial coproduct satisfies the following relations:

(∆ ⊗ id) • ∆ = (id ⊗ ∆ ) • ∆ (∆ ⊗ id) • ∆ = (id ⊗ ∆ ) • ∆ (∆ ⊗ id) • ∆ = (id ⊗ ∆ ) • ∆
It is given on planar binary trees by:

∆ (∨(T l ; T r )) = T l ⊗ ∨(∅; T r ) + ∆ (T l ) 1 ⊗ ∨(∆ (T l ) 2 ; T r ) ∆ (∨(T l ; T r )) = ∨(T l ; ∅) ⊗ T r + ∨(T l ; ∆ (T r ) 1 ) ⊗ ∆ (T r ) 2 with ∆ (∨(T l ; ∅)) = ∆ (∨(∅; T r )) = 0.
This operad enables us to introduce a rigidity theorem for co-skew-duplicial dendriform bialgebras, proven using the recursive definitions of products and coproducts: Proposition 5.1.2 (Rigidity theorem for co-skew-duplicial dendriform bialgebras). Any connected dendriform co-skew-duplicial bialgebra satisfying the following confluence laws is free and cofree over its primitive elements:

∆ (T S) = T ∆ (S) 1 ⊗ ∆ (S) 2 ∆ (T ≺ S) = T ⊗ S + T ≺ ∆ (S) 1 ⊗ ∆ (S) 2 + ∆ (T ) 1 ⊗ ∆ (T ) 2 * S ∆ (T S) = T ⊗ S + T * ∆ (S) 1 ⊗ ∆ (S) 2 + ∆ (T ) 1 ⊗ ∆ (T ) 2 S ∆ (T ≺ S) = ∆ (T ) 1 ⊗ ∆ (T ) 2 ≺ S Proposition 5.1.

(Rigidity theorem for co-skew-duplicial duplicial bialgebras). Any connected duplicial co-skew-duplicial bialgebra satisfying the following confluence laws is free and cofree over its primitive elements:

∆ (T S) = T ∆ (S) 1 ⊗ ∆ (S) 2 ∆ (T S) = ∆ (T ) 1 ⊗ ∆ (T ) 2 S ∆ (T S) = T ⊗ S + T ∆ (S) 1 ⊗ ∆ (S) 2 + ∆ (T ) 1 ⊗ ∆ (T ) 2 S ∆ (T S) = ∆ (T ) 1 ⊗ ∆ (T ) 2 S
Proposition 5.1.4 (Rigidity theorem for co-skew-duplicial skew-duplicial bialgebras). Any connected skew-duplicial co-skew-duplicial bialgebra satisfying the following confluence laws is free and cofree over its primitive elements:

∆ (T S) = T ⊗ S + ∆ (T ) 1 ⊗ ∆ (T ) 2 S + T ∆ (S) 1 ⊗ ∆ (S) 2 ∆ (T S) = T ∆ (S) 1 ⊗ ∆ (S) 2 ∆ (T S) = ∆ (T ) 1 ⊗ ∆ (T ) 2 S ∆ (T S) = T ⊗ S + ∆ (T ) 1 ⊗ ∆ (T ) 2 S + T ∆ (S) 1 ⊗ ∆ (S) 2
Example 5.1.5. The products introduced by Vong in [START_REF] Vong | On (non-) freeness of some tridendriform algebras[END_REF] to prove the freeness of F QSym, denoted here ST, satisfy the skew-duplicial relations. Dualising these operations into cooperations gives an algebraic rewriting of Vong's proof as the dendriform operations and the skew-duplical cooperations satisfy the above confluence laws. Indeed, it endows the Solomon-Tits algebra with a skew-duplicial-dendriform structure and the rigidity theorem gives the freeness of ST as a dendriform algebra.

6 Terplicial and tridendriform operads.

Definitions: tridendriform (co)algebras.

Let us recall the relations governing a q-tridendriform algebra linking the tridendriform structure described in [?] for q = 1 and in [START_REF] Chapoton | Opérades différentielles graduées sur les simplexes et les permutoèdres[END_REF] for q = 0: Definition 6.1.1. A q-tridendriform algebra is a vector space A together with three operations ≺: A ⊗ A → A, • : A ⊗ A → A and : A ⊗ A → A, satisfying the following relations:

(a ≺ b) ≺ c = a ≺ (b ≺ c + b c + q b • c), a (b c) = (a ≺ b + a b + q a • b) c, (a b) ≺ c = a (b ≺ c), (a • b) • c = a • (b • c), (a b) • c = a (b • c), (a ≺ b) • c = a • (b c), (a • b) ≺ c = a • (b ≺ c).
Note that the operation * := ≺ +q • + is associative. Moreover, given a q-tridendriform algebra (A, ≺, •, ), the space A equipped with the binary operations ≺ and := q • + is a dendriform algebra. Example 6.1.2. Let T n be the set of all planar reduced rooted trees with n + 1 leaves. Denote by T ∞ = n T n . Given trees t 1 , . . . , t r , let (t 1 , . . . , t r ) be the tree obtained by joining the roots of t 1 , . . . , t r , ordered from left to right, to a new root. Then, any t ∈ T n may be written in a unique way as t = (t 1 , . . . , t r ), with t i ∈ T n i and r i=1 n i + r -1 = n. On the space K[T ∞ ], define operations , • and ≺ recursively as follows:

t | = t • | = | • t = | ≺ t = 0, for all t ∈ T ∞ , | t = t ≺ | = t, for all t ∈ T ∞ , t ≺ w := (t 1 , . . . , t r-1 , t r * w), t • w := (t 1 , . . . , t r-1 , t r * w 1 , w 2 , . . . , w l ),
t w := (t * w 1 , w 2 , . . . , w l ), for t = (t 1 , . . . , t r ) and w = (w 1 , . . . , w l ), where * is the associative product * = +q • + ≺ previously defined.

Note that, even if we need to consider the element | ∈ T 0 as the identity for the product * in order to define the tridendriform structure on

K[T ∞ ], the elements | | , | • | and | | are not defined.
Following [START_REF] Chapoton | Opérades différentielles graduées sur les simplexes et les permutoèdres[END_REF] and [START_REF] Loday | Trialgebras and families of polytopes, Homotopy Theory: Relations with Algebraic Geometry, Group Cohomology, and Algebraic K-theory[END_REF], (K[T ∞ ], , •, ≺) is the free q-tridendriform algebra spanned by the unique element of T 1 . Definition 6.1.3. A q-tridendriform coalgebra, or co-tridendriform coalgebra, is a vector space V endowed with three coproducts ∆ ≺ , ∆ • , ∆ satisfying the following relations:

(∆ ≺ ⊗ id) • ∆ ≺ = (id ⊗ ∆ * ) • ∆ ≺ , (∆ ⊗ id) • ∆ ≺ = (id ⊗ ∆ ≺ ) • ∆ , (∆ * ⊗ id) • ∆ = (id ⊗ ∆ ) • ∆ , (id ⊗ ∆ • ) • ∆ • = (∆ • ⊗ id) • ∆ • , (∆ ⊗ id) • ∆ • = (id ⊗ ∆ • ) • ∆ , (∆ ≺ ⊗ id) • ∆ • = (id ⊗ ∆ ) • ∆ • , (∆ • ⊗ id) • ∆ ≺ = (id ⊗ ∆ ≺ ) • ∆ • .
where ∆ * = ∆ ≺ + q∆ • + ∆ .

A co-augmented conilpotent tridendriform coalgebra C is a coalgebra verifying that: The definition of the operations gives a constructive way to define the cooperations as:

C = ∪ n≥0 F n C where F 0 C = K, F 1 C = {x ∈ C | ∆ ≺ (x) = ∆ (x) = ∆ • (x) = 0}, F n C = {x ∈ C | ∆ ≺ (x) ∈ F n-1 C ⊗2 , ∆ (x) ∈ F n-1 C ⊗2 , ∆ • (x) ∈ F n-1 C ⊗2 }.
∆ (∨(t 1 , . . . , t n )) =∆ * (t 1 ) 1 ⊗ ∨(∆ * (t 1 ) 2 , t 2 , . . . , t n ) + t 1 ⊗ ∨(∅, t 2 , . . . , t n ) ∆ • (∨(t 1 , . . . , t n )) = n-1 i=2 ∨(t 1 , . . . , t i-1 , ∆ * (t i ) 1 ) ⊗ ∨(∆ * (t i ) 2 , t i+1 , . . . , t n ) + ∨ (t 1 , . . . ,t i-1 , ∅) ⊗ ∨(t i , . . . , t n ) + ∨(t 1 , . . . , t i ) ⊗ ∨(∅, t i+1 , . . . , t n ) ∆ ≺ (∨(t 1 , . . . , t n )) = ∨ (t 1 , . . . , t n-1 , ∆ * (t n ) 1 ) ⊗ ∆ * (t n ) 2 + ∨(t 1 , . . . , t n-1 , ∅) ⊗ t n , where ∆ * = ∆ ≺ + q∆ • + ∆ .
This definition gives well-defined coproducts verifying the cotridendriform relations. Note that any free tridendriform algebra is naturally endowed with this dual coalgebra structure.

Dualising the proof for the freeness of T ∞ as a tridendriform algebra, one gets that this structure on T ∞ is the cofree conilpotent tridendriform coalgebra.

Definitions: terplicial (co)algebras.

From the tridendriform operad, we define a new set-operad called terplicial, on which the tridendriform operad is quasi-set (see [START_REF] Burgunder | Rigidity theorem, freeness of algebras and applications[END_REF]), by analogy with the pair (Dend, skew-dupl). It is to be noted that an analogue of the pair (Dend, Dupl) is not possible as the analogue of Dupl with three associative products cannot be defined. Definition 6.2.1. A terplicial algebra is a vector space V endowed with three binary products { , , } satisfying the following relations: and are associative,

(x y) z = x (y z) (x y) z = x (y z) (x y) z = x (y z) (x y) z = x (y z) (x y) z = x (y z)
All the equations but the second and the last coincide with relations satisfied by triduplicial algebra defined by J.-C. Novelli and J.-Y. Thibon in [?].

Consider the planar rooted trees, and denote by ∨(t 1 , . . . , t n ) a planar tree T ∈ T ∞ whose root has arity n and such that the t i are the (possibly empty) subtrees of T rooted in the children of the root of T . We can now describe the free terplicial algebras. Theorem 6.2.2. The free terplicial algebra on a vector space V can be described as the algebra whose underlying vector space has a basis given by reduced planar rooted trees with leaves decorated by V : T er(V ) = ⊕K[T n ] ⊗ V ⊗n . Hence, the dimension of the space of operations of arity n in the triplicial operad is given by the Schroeder-Hipparchus number.

The operations , and on free terplicial algebras are described recursively as follows, for any tree T = ∨(t 1 , . . . , t n ) and S = ∨(s 1 , . . . , s m ), and denoting by ∅ the empty tree:

T S = ∨(t 1 , . . . , t n-1 , t n S) T S = ∨(t 1 , . . . , t n-1 , t n s 1 , s 2 , . . . , s m ) T S = ∨(T s 1 , s 2 . . . , s m ),
given that, ∅ T = T and T ∅ = T.

Example 6.2.3. If T =

and S = , the products are given by: T S = , T S = and T S = .

Proof. T ∞ endowed with these operations satisfy the terplicial relations, see section 8.4.2.

The universal property of terplicial algebras is verified: for any morphism from f : V → A, with A a terplicial algebra, ι : V → T er(V ) the canonical injection, then there exists a unique terplicial morphism φ : T er(V ) → A defined as

∨(t 1 , . . . , t n ) ⊗ v 1 . . . v k 1 v k 1 +1 . . . v k 1 +...+kn → φ(t 1 ⊗ v 1 . . . v k 1 ) (φ(∨(∅, t 2 ) ⊗ 1v k 1 +1 . . . v k 2 ) . . . φ(∨(∅, t n-1 ) ⊗ 1v k n-2 +1 . . . v k n-1 ) φ(∨(∅, ∅) ⊗ 1 • 1)) φ(t n ⊗ v k n-1 +1...kn ) .
The uniqueness of the morphism is obtained by construction.

Dualising the notion of terplicial algebras, into terplicial coalgebras gives: Definition 6.2.4. A terplicial coalgebra, or coterplicial coalgebra, is a vector space C endowed with three coproducts ∆ , ∆ , ∆ : C → C ⊗ C satisfying the following relations:

∆ and ∆ are co-associative,

(∆ ⊗ id) • ∆ = (id ⊗ ∆ ) • ∆ , (∆ ⊗ id) • ∆ = (id ⊗ ∆ ) • ∆ , (∆ ⊗ id) • ∆ = (id ⊗ ∆ ) • ∆ , (∆ ⊗ id) • ∆ = (id ⊗ ∆ ) • ∆ , (∆ ⊗ id) • ∆ = (id ⊗ ∆ ) • ∆ . A co-augmented conilpotent terplicial coalgebra C is a coalgebra veri- fying that: C = ∪ n≥0 F n C where F 0 C = K, F 1 C = {x ∈ C | ∆ (x) = ∆ (x) = ∆ (x) = 0}, F n C = {x ∈ C | ∆ (x) ∈ F n-1 C ⊗2 , ∆ (x) ∈ F n-1 C ⊗2 , ∆ (x) ∈ F n-1 C ⊗2 }.
Example 6.2.5. We introduce the dual coproduct associated to the products , and . They are given inductively on T = ∨(t 1 , . . . , t n ) by:

• if t 1 = ∅, ∆ (T ) = 0 • if t n = ∅, ∆ (T ) = 0 • if n ≤ 2, ∆ (T ) = 0 and, otherwise, ∆ (T ) = t 1 ⊗ ∨(∅, . . . , t n ) + ∆ (t 1 ) 1 ⊗ ∨(∆ (t 1 ) 2 , . . . , t n ), ∆ (T ) = n-1 i=2 ∨(t 1 , . . . , t i-1 , ∅) ⊗ ∨(t i , . . . , t n ) + ∨(t 1 , . . . , t i ) ⊗ ∨(∅, t i+1 , . . . , t n ) + ∨(t 1 , . . . , t i-1 , ∆ (t i ) 1 ) ⊗ ∨(∆ (t i ) 2 , t i+1 , . . . , t n ) , ∆ (T ) = ∨(t 1 , . . . , t n-1 , ∅) ⊗ t n + ∨(t 1 , . . . , t n-1 , ∆ (t n ) 1 ) ⊗ ∆ (t n ) 2 .
It is by duality, the cofree conilpotent terplicial coalgebra on one generator, which can be extended to the cofree conilpotent terplicial coalgebra on generators by decorating the leaves, in a similar manner as the free tridendriform algebras.

Rigidity theorem for bialgebras endowed with terplicial and tridendriform structures

Terplicial bialgebras

Definition 6.3.1. A terplicial bialgebra is a vector space H endowed with a terplicial algebra structure (H, , , ) and a co-terplicial coalgebra structure (H, ∆ , ∆ , ∆ ) satisfying the following mixed ditributive laws:

∆ (T S) =T ⊗ S + ∆ (T ) 1 ⊗ ∆ (T ) 2 S + T ∆ (S) 1 ⊗ ∆ (S) 2 ∆ (T S) =∆ (T ) 1 ⊗ ∆ (T ) 2 S ∆ (T S) =∆ (T ) 1 ⊗ ∆ (T ) 2 S ∆ (T S) =T ∆ (S) 1 ⊗ ∆ (S) 2 ∆ (T S) =T ⊗ S + ∆ (T ) 1 ⊗ ∆ (T ) 2 S + T ∆ (S) 1 ⊗ ∆ (S) 2 + ∆ (T ) ⊗ ∆ (T ) 2 S + T ∆ (S) 1 ⊗ ∆ (S) 2 ∆ (T S) =∆ (T ) 1 ⊗ ∆ (T ) 2 S ∆ (T S) =T ∆ (S) 1 ⊗ ∆ (S) 2 ∆ (T S) =T ∆ (S) 1 ⊗ ∆ (S) 2 ∆ (T S) =T ⊗ S + ∆ (T ) 1 ⊗ ∆ (T ) 2 S + T ∆ (S) 1 ⊗ ∆ (S) 2 .
Example 6.3.2. The vector space T ∞ admits a terplicial bialgebra structure with the coalgebra structure described in example 6.2.5 and the terplicial algebra structure described in theorem 6.2.2.

The proof is postponed to the section 8.4.2 on the combinatorial description of the products and coproducts.

Proposition 6.3.3 (Rigidity theorem for coterplicial terplicial bialgebras).

Any connected terplicial co-terplicial bialgebra is free and cofree over its primitive elements.

Proof. We apply the result of [1, corollary 2.1.4] as the above example give the confluence laws.

The bialgebra T ∞ is then free as a terplicial algebra and cofree as a connected terplicial coalgebra over one element.

Co-terplicial tridendriform bialgebras

Definition 6.3.4. A co-terplicial tridendriform bialgebra is a vector space H endowed with a terplicial coalgebra structure (H, ∆ , ∆ , ∆ ), a tridendriform algebra structure (H, ≺, , ) satisfying the following mixed ditributive laws:

∆ (T ≺ S) =(∆ (T )) 1 ⊗ (∆ (T )) 2 ≺ S ∆ (T • S) =(∆ (T )) 1 ⊗ (∆ (T )) 2 • S ∆ (T S) =T ⊗ S + (∆ (T )) 1 ⊗ (∆ (T )) 2 S + T * (∆ (S)) 1 ⊗ (∆ (S)) 2 ∆ (T ≺ S) =(∆ (T )) 1 ⊗ (∆ (T )) 2 ≺ S ∆ (T • S) =T ⊗ S + (∆ (T )) 1 ⊗ (∆ (T )) 2 • S + T • (∆ (S)) 1 ⊗ (∆ (S)) 2 + (∆ (T )) 1 ⊗ (∆ (T )) 2 S + T ≺ (∆ (S)) 1 ⊗ (∆ (S)) 2 ∆ (T S) =T (∆ (S)) 1 ⊗ (∆ (S)) 2 ∆ (T ≺ S) =T ⊗ S + (∆ (T )) 1 ⊗ (∆ (T )) 2 * S + T ≺ (∆ (S)) 1 ⊗ (∆ (S)) 2 ∆ (T • S) =T • (∆ (S)) 1 ⊗ (∆ (S)) 2 ∆ (T S) =T (∆ (S)) 1 ⊗ (∆ (S)) 2
where * = + ≺ +•. Example 6.3.5. The vector space T ∞ endowed with the coterplicial coalgebra structure given in example 6.2.5 and the tridendriform structure given in example 6.1.2 as a co-terplicial tridendriform bialgebra.

The proof is postponed to section 8.4.3 on the combinatorial description of the terplicial products and coproducts. Proposition 6.3.6 (Rigidity theorem for coterplicial tridendriform bialgebras). Any connected tridendriform co-terplicial bialgebra is free and cofree over its primitive elements.

Proof. We apply the result of [1, corollary 2.1.4] as the above example give the confluence laws.

Therefore the bialgebra T ∞ is free as a tridendriform algebra on one element, and cofree as a connected co-terplicial algebra on one element.

Tridendriform bialgebras

Tridendriform-tridendriform bialgebras:

Let us denote ∆ 1 • = ∆ • , ∆ k+1 • = (id k ⊗ ∆ • ) • ∆ k
• , and

• 1 = •, • k+1 = • k • (id k ⊗ •)
, where • stands for one of the symbols ≺, • or .

For the sake of readability, we will denote

α ≺ := ∆ ≺ + k≥1 (-1) k (id⊗ ≺ ) • ∆ k+1 ≺ , α = ∆ + k≥1 (-1) k ( ⊗id k ) • ∆ k+1
. Definition 6.3.7. A co-tridendriform tridendriform bialgebra is a vector space H endowed with a co-tridendriform coalgebra structure (H, ∆ , ∆ • , ∆ ≺ ) and a tridendriform algebra structure (H, , •, ≺) linked by the confluence laws given by: for any x, y ∈ H

∆ (x y) = ∆ * (x * α (y) 1 ) 1 ⊗ ∆ * (x * α (y) 1 ) 2 α (y) 2 + x * α (y) 1 ⊗ α (y) 2 ∆ (x • y) = ∆ (x) 1 ⊗ ∆ (x) 2 • y ∆ (x ≺ y) = ∆ (x) 1 ⊗ ∆ (x) 2 ≺ y ∆ • (x y) = x ∆ • (y) 1 ⊗ ∆ • (y) ∆ • (x • y) = ∆ • (x) ⊗ ∆ • (x) 2 • y + x • ∆ • (y) 1 ⊗ ∆ • (y) 2 + + α ≺ (x) 1 ≺ (∆ * (α ≺ (x) 2 * α (y) 1 ) 1 ) ⊗ (∆ * (α ≺ (x) 2 * α (y) 1 ) 2 ) α (y) 2 ∆ • (x ≺ y) = ∆ • (x) 1 ⊗ ∆ • (x) 2 ≺ y ∆ ≺ (x y) = x ∆ ≺ (y) 1 ⊗ ∆ ≺ (y) 2 ∆ ≺ (x • y) = x • ∆ ≺ (y) 1 ⊗ ∆ ≺ (y) 2 ∆ ≺ (x ≺ y) = α ≺ (x) 1 ≺ ∆ * (α ≺ (x) 2 * y) 1 ⊗ ∆ * (α ≺ (x) 2 * y) 2 + α ≺ (x) 1 ⊗ α ≺ (x) 2 * y
The definition is considered for q = 1 but can be extended for any q. Example 6.3.8. The vector T ∞ endowed with the tridendriform structures defined in 6.1.4 and 6.1.2 admits these confluence laws.

Proof. Write the confluence laws on trees considering the definitions of the products and coproducts. Then, prove by induction that for any tree T = ∨(t 1 , . . . , t n ) the element α (T ) is equal to t 1 ⊗ ∨(∅, t 2 , . . . , t n ), respectively, α ≺ (T ) is equal to ∨(t 1 , t 2 , . . . , t n-1 , ∅) ⊗ t n . The induction is on the cofiltration with respect to ∆ , ∆ ≺ respectively. Moreover α

• = ∆ • -(≺ •α ≺ ⊗ •α ) • ∆ • applied to T is given by n-1 i=2 ∨(t 1 , . . . , t i ) ⊗ ∨(∅, t i+1 , . . . , t n ) + ∨(t 1 , . . . , t i-1 , ∅) ⊗ ∨(t i , t 2 , . . . , t n ).
Theorem 6.3.9 (Rigidity theorem for co-tridendriform-tridendriform bialgebras). Any connected co-tridendriform tridendriform bialgebra is free and cofree over its primitives.

Proof. We apply the result of [1, corollary 2.1.4] as the above example give the confluence laws.

The cotridendriform tridendriform bialgebra T ∞ is free as a tridendriform algebra and cofree as a co-tridendriform connected coalgebra on one element. Remark 6.3.10. Let (H, ≺, , •, ∆ ≺ , ∆ , ∆ • ) be a conilpotent dual tridendriform bialgebra whose primitive elements are explicitely known.

We denote by proj 1 : H ⊗ H → H the canonical projection of the first component and proj 2 the canonical projection on the second component, we denote by 1 F ≺ 1 the application which is the identity on F ≺ 1 H and null elsewhere, analogously for 1 F 1 , and by p ≺ i (resp. p i ) the composition p ≺ i :=

proj i •(id ⊗ 1 F ≺ 1 ) • ∆ ≺ , (p i := proj i •(1 F 1 ⊗ id) • ∆ ). We then have (α • ) i = p • i on T ∞ where • is either ≺ or and i ∈ {1, 2} on connected coalgebras.
7 Application to the freeness of some tridendriform algebras 7.1 Application to the freeness of the Solomon-Tits algebra as a tridendriform algebra. The Solomon-Tits algebra can be endowed with a tridendriform structure, see for example [START_REF] Novelli | Hopf algebras and dendriform structures arising from parking functions[END_REF][START_REF] Burgunder | Tridendriform structure on combinatorial Hopf algebras[END_REF]. We keep the notations taken in section 2.1.

The concatenation product × : ST r n ⊗ ST s m -→ ST r+s n+m is given by the formula:

f × g := (f (1), . . . , f (n), g(1) + r, . . . , g(m) + r). Similarly, for K = {j 1 < • • • < j l } ⊆ {1, . . . , r}, the co-restriction of x to K is denoted x| K := std(x(s 1 ), . . . , x(s q )), for

x -1 (K) = {s 1 < • • • < s q }.
For an element x ∈ ST r n , we denote by λ(x) the cardinal of x -1 ({r}). Suppose that x -1 (r) = {j 1 < • • • < j λ(x) }, and let x ∈ ST r-1 n-k be the co-restriction x := x| {1,...,r-1} . We denote x as

x = j 1 <•••<j λ(x) x .
Let (n 1 , . . . , n p ) be a composition of n. An element in f ∈ ST n is a (n 1 , . . . , n p )-stuffle if

f (n 1 + • • • + n i ) < f (n 1 + • • • + n i + 1) < • • • < f (n 1 + • • • + n i + n i+1 ), for 0 ≤ i ≤ p -1.
We denote by SH(n 1 , . . . , n p ) the set of all (n 1 , . . . , n p )-stuffles. For a composition (n 1 , . . . , n p ) of n, we denote:

(1) SH ≺ (n 1 , . . . , n p ) the subset of all surjective maps f ∈ SH(n 1 , . . . , n p ) such that f (n

1 ) > f (n 1 + n 2 ) > • • • > f (n).
(2) SH (n 1 , . . . , n p ) the subset of all surjective maps f ∈ SH(n 1 , . . . , n p ) such that f (n 1 ) < f (n 4) SH (n 1 , . . . , n p ) the subset of all surjective maps f ∈ SH(n 1 , . . . , n p ) such that f (n

1 + n 2 ) < • • • < f (n). (3) SH • (n 1 , . . . , n p ) the subset of all surjective maps f ∈ SH(n 1 , . . . , n p ) such that f (n 1 ) = f (n 1 + n 2 ) = • • • = f (n). (
1 ) ≤ f (n 1 + 2 ) ≤ • • • ≤ f (n). Let x ∈ ST r
n , y ∈ ST s m , the tridendriform structure on ST is defined as follows:

x y := f ∈SH (r,s) f • (x × y), x • y := f ∈SH • (r,s) f • (x × y), x ≺ y := f ∈SH ≺ (r,s) f • (x × y).
The work of Vong [START_REF] Vong | On (non-) freeness of some tridendriform algebras[END_REF] can be understood as a construction of a terplicial algebraic structure on ST s m . For x ∈ ST r n , y ∈ ST s m define the operations x y = j x 1 ,...,j x λ(x)

x × y x y = j x 1 ,...,j x λ(x) ,j y 1 ,...,j y λ(y)

x × y

x y = x × y where x = j x 1 ,...,j x λ(x)

x and y = j y 1 ,...,j y λ(x)

y . The relations are checked by direct inspection.

In this section, we focus on proving the freeness of ST as a free tridendriform algebra and terplicial algebra by adding a co-terplicial structure to ST which is dual to the terplicial structure. The confluence laws are those introduced above. This viewpoint permits to give a way to understand the double application of Groebner basis algorithm as seen in the work of Vong as terplicial-tridendriform or terplicial-terplicial bialgebra structure. The rigidity theorem guarantees that the reductions provided will fit the bill which is one of the most tricky challenge when trying to find the "good" reductions.

The co-terplicial structure on ST is combinatorially constructed as follows: for x ∈ ST r n there is a unique way to describe it as x 1 × . . . × x p such that every x i is irreducible that is to say that there do not exists u, v ∈ ST such that x i = u × v. Suppose x = j 1 ,...,j λ(x) x = j 1 ,...,j λ(x) u 1 × . . . × u q where u 1 ×. . .×u q is the irreducible decomposition of x ,

u i ∈ ST s i m i . Denote by U 1 = u 1 × . . . × u p 1 the decomposition x = j 1 ,...,j λ(x) U 1 × u p+1 × . . . × u q with m 1 + . . . m p 1 -1 + λ(x) < j λ(x) ≤ m 1 + . . . m p 1 + λ(x) ∆ (x) = i j 1 ,...,j λ(x) U 1 × u p 1 +1 × . . . × u p 1 +i ⊗ std(u p 1 +i+1 × . . . × u q ) ∆ (x) = i x 1 × . . . × x i ⊗ x i+1 × . . . × x p ∆ (x) = i,l j 1 ,...,j i u 1 × . . . × u l ⊗ j i+1 ,...,j λ(x) u l+1 × . . . × u q
where the last sum runs over i, l such that m 1 + . . . + m l-1 < j i ≤ m 1 + . . . + m l .

The relations are checked as these cooperations are the dual of the terplicial operations. Proposition 7.1.1. The Solomon-Tits algebra is endowed with a terplicial cterplicial bialgebra structure and a terplicial c -tridendriform bialgebra structure.

Proof. The terplicial c -terplicial mixed distributive relations are verified.

The proof is based on the unique decomposition of an element into

x = u x 1 × . . . × u w(x) × j 1 ,...,j λ(x) u w(x)+1 × u x q = u x 1 × . . . × u x
q and the definition of the terplicial operations which for two elements x and y will only modify the place of the maxima of x and y according to the operation considered.

For example the relation: ∆ (x y) = ∆ (x) 1 ⊗ ∆ (x) 2 y + ∆ (x) 1 ⊗ ∆ (x) 2 y +x ∆ (y) 1 ⊗∆ (y) 2 +x ∆ (y) 1 ⊗ (y) 2 +x⊗y is satisfied as the product levels the maxima of x and y while keeping the overall structure of x × y with x = x .

The terplicial c -tridendriform distributive relations are verified. The proof is based on the unique decomposition of an element x = j 1 ,...,j λ(x) u x 1 ×. . .× u x q and the definition of the tridendriform operations which keeps the overall order (in regards to ×) of u x 1 × . . . × u x q in x and of u y 1 × . . . × u y q in y.

Define the product T p S of two trees accordingly to the stuffle path p = (e 1 , . . . , e k ) of T and S inductively as follows:

T p S =                  if e 1 =
∆ (U ) = 1≤j<|l U r U 1 | ∆ r U 1 ,l U r 1 1 ,...,l U r 1 j ,r U l j 1 ,...,r U l j |r U l j | (U ) ∆ (U ) = 1 < i < n 1 ≤ j ≤| l U e i | ∆ e i ,l U e i 1 ,...,l U e i j ,r U l j 1 ,...,r U l j |r U l j )| (U ) ∆ (U ) = 1≤j<|l U | ∆ (l U 1 ,...l U j ,r U l j 1 ,...,r U l j |r U l j | ) (U )

Combinatorial description of the tridendriform operations and cooperations via stuffle paths and cutting paths.

For two trees T, S, we will denote the set of stuffle paths P(T, S), the subset of sequences such that the first edge is the first edge of r T which is not identified with the first edge of l S will be denoted P < (T, S) , the subset such that the first edge is the first edge of of l S which is not identified with the first edge of r T will be denoted P > (T, S), the subset of sequences such that the first edge is the first edge of r T which is identified with the first edge of l S will be denoted P = (T, S). For a tree T denote the set of cutting paths Q(T ), the subset of sequences which start with the leftmost edge of T will be denoted Q > (T ), the subset of sequence which start with the rightmost edge of T will denoted Q < (T ), and the subset of sequences which start with neither the rightmost nor the leftmost edge of T will be denoted Q = (T ). Proposition 8.3.2. The co-tridendriform cooperations defined in 6.1.4 are described as follows:

∆ * (T ) = q∈Q(T ) ∆ q (T ) ∆ ≺ (T ) = q∈Q<(T ) ∆ q (T ) ∆ • (T ) = q∈Q=(T ) ∆ q (T ) ∆ (T ) = q∈Q>(T ) ∆ q (T )
Proof. It is immediate by induction considering the description of ∆ q (T ) for a cutting path q and the constructive description of the coproducts in 6.1.4. be denoted (p i ) 1≤i≤k and the sequence of edges of the cutting path will be denoted (q i ) 1≤i≤l . Two cases can occur p 1 = q 1 or p 1 = q 1 . Suppose p 1 = q 1 , suppose moreover that p 1 ∈ E(T ) \ E(S) (the case p 1 ∈ E(S) \ E(T ) is symmetrical, the case p 1 ∈ E(S) ∩ E(T ) gives the same results choosing either option p 1 ∈ E(T ) or p 1 ∈ E(S)). The definition of the product linked to a stuffle path, and the coproduct linked to a cutting path leads to:

∆ q (T p S) = ∨(t 1 , . . . , t n-1 , ∆ (q 2 ,...,q l ) (t n (p 2 ,...,p k S) 1 )⊗∆ (q 2 ,...,q l ) (t n (p 2 ,...,p k ) S) 2 . Suppose that p 1 ∈ E(T ) ∩ E(S) then ∆ q (T p S) = ∨(t 1 , . . . , t n-1 , ∆ (q 2 ,...,q l ) (t n (p 2 ,...,p k ) s 1 ) 1 ) ⊗ ∨(∆ (q 2 ,...,q l ) (t n (p 2 ,...,p k ) s 1 ) 2 , s 2 , . . . , s n ) .
The case p 1 = q 1 is analogous.

Example 8.4.3. To ease the comprehension of the different paths here is an example of those. Take T = and S = . Consider T p S, with p being the stuffle path given by p = ({e T 1 , e S 1 }, e S 2 , e T 2 , e S 3 , {e T 3 , e S 4 }) represented on the right picture of Figure 4 by the dashed blue path. Consider the cutting path q in T p S represented in the figure as a dotted path. The edges from T are in blue, the edges from S are in red and edges from both, i.e. identified edges, are in purple.

Combinatorial description of the coterplicial-terplicial confluence laws in T ∞ :

We first prove that the operations and cooperation constructed in 6.2.2 verify the terplicial relations.

Proof. The terplicial relations are a consequence of the choice of a stuffle path from a path and a stuffle path and their respective first edges.

For example consider three trees T, S, U denote by (r T i ) 1≤i≤tr , (r S i ) 1≤i≤sr , (r U i ) 1≤i≤ur the edges of their rightmost path, and by (l T i ) 1≤i≤t l , (l S i ) 1≤i≤s l , (l U i ) 1≤i≤u l the edges of their leftmost path. Then,

(T S) U = (T (l S 1 ,...,l S l ,r T 1 ,...,r T tr ) S) (r S 1 ,l U 1 ,...,l U u l ,r S 2 ,...,r S sr ) U = T (l S 1 ,...,l S l ,r T 1 ,...,r T tr ) (S (r S 1 ,l U 1 ,...,l U u l ,r S 2 ,...,r S sr ) U ) = T (S U ) .
We now prove the confluence law given in example 6.3.2.

Proof. Let T = ∨(t 1 , . . . , t n ) and S = ∨(s 1 , . . . , s m ) be two planar trees. The confluence laws are deduced by lemma 8.4.2.

For example for the first confluence law rewrites as, with the notation of section 8.2:

∆ (T S) = 1≤j<|l U e T 1 | ∆ e T 1 ,l U e T 1 1 ,...,l U e T 1 j ,r U l j 1 ,...,r U l j |r U l j | (T (e T 1 ,
∆ (T • S) = p∈P=(T,S) 1≤j<|l S r S 1 | ∆ r S 1 ,l S r 1 1 ,...,l S r 1 j ,r S l j 1 ,...,r S l j |r S l j | (T p S) = T • ∆ (S) 1 ⊗ ∆ (S) 2 .
8.5 Combinatorial confluence laws for the co-tridendriform tridendriform bialgebra structure on T ∞ : A corollary to the above lemma 8.4.2 is that we can count the number of terms of T ⊗ S appearing in coproduct of product in the cotridendriform-tridendrifom bialgebra structure of T ∞ . This gives an easy criterion to say whether a combinatorial algebra is not free as a tridendriform algebra. Consider r T the rightmost path of T and R T its number of edges denoted (e T i ) i . Respectively denote L T = #l T to be the number of edges of the leftmost path l T and denote (e S i ) i its edges. We will denote by D(n, m) the Delannoy number of n, m, [20, A266213]. It is the number of distinct terms appearing in T ≺ S, T • S, T S respectively.

Proof. The proof lies heavily on the precedent lemma 8.4.2: the element T ⊗ S will appear when the cutting path and the stuffle path will coincide. Therefore, it suffices to compute the number of elements of Q(T, S) which is the collection of stuffles of two collections of cardinal R T and L S . We will show that it is D(R T , L S ) by induction on the cardinal R T and LS.

In low dimensions, it is obvious. Suppose the property true for R T < n, L S < m for any T, S ∈ T ∞ and consider two trees T , with R T = n, S with L S = m. The computation of T * S when T = ∨(t 1 , . . . , t n ), S = ∨(s 1 , . . . , s m ) gives through the constructive definitions 6. i the cutting path with 0 ≤ i ≤ R T is the maximal integer such that the first i edges are of r T , i.e. q T i = (e T 1 , . . . , e T i , q i+1 , . . . e |q| ). Analogously denote q S i the cutting path starting with i edges of l S . Denote by p T j the stuffle path with j the maximal integer such that the first j edges are edges of r T exclusively. Analogously for p S j . The confluence laws on T ∞ are given by: ∆ (T S) =D(R T , L S -1) T ⊗ S + q ∈ Q(T ) q = q T i p ∈ P>(T e T i , S) p = p S j D(i, j -1) ∆ q (T ) 1 ⊗ ∆ q (T ) 2 p S + q ∈ Q>(S) q = q S i p ∈ P(T, S e T i ) p = p T j D(i, j -1) T p ∆ q (S) 1 ⊗ ∆ q (S) 2

∆ • (T • S) = D(R T -1, L S -1)T ⊗ S + ∆ • (T ) 1 ⊗ ∆ • (T ) 2 • S + T • ∆ • (S) 1 ⊗ ∆ • (S) 2 + q ∈ Q<(T )
q = q T i p ∈ P(T e T i , S) p = p S j D(i -1, j -1) ∆ q (T ) 1 ⊗ ∆ q (T ) 2 p S + q ∈ Q>(S) q = q T i p ∈ P(T, S e T i ) p = p S j D(i -1, j -1) T p ∆ q (S) 1 ⊗ ∆ q (S) 2 ∆ (T S) = D(R T -1, L S ) T ⊗ S + q ∈ Q<(T ) q = q T i p ∈ P(T e T i , S) p = p T j D(i -1, j) ∆ q (T ) 1 ⊗ ∆ q (T ) 2 p S + q ∈ Q(S) q = q S i p ∈ P>(T, S e T i ) p = p T j D(i -1, j) T p ∆ q (S) 1 ⊗ ∆ q (S) 2

∆ (T • S) =∆ (T ) 1 ⊗ ∆ (T ) 2 • S ∆ (T ≺ S) =∆ (T ) 1 ⊗ ∆ (T ) 2 ≺ S ∆ • (T S) =T ∆ • (S) 1 ⊗ ∆ • (S) 2 ∆ • (T ≺ S) =∆ • (T ) 1 ⊗ ∆ • (T ) 2 ≺ S ∆ ≺ (T S) =T ∆ ≺ (S) 1 ⊗ ∆ ≺ (S) 2 ∆ ≺ (T • S) =T • ∆ ≺ (S) 1 ⊗ ∆ ≺ (S) 2
Proof. The description of the tridendriform products through stuffle paths 8.3.1 and the co-tridendriform coproducts through cutting paths 8.3.2 gives

∆ (T S) = p∈P>(T,S) q∈Q>(T pS)

∆ q (T p S) Then apply lemma 8.4.2. The coefficients appear as for a stuffle path p and a cutting path q, consider any stuffle of the edges (E(p) ∩ E(q)) ∩ E(T ) and (E(p)∩E(q))∩E(S). Consider any path p obtained from p, and any cutting path q obtained from q, such that only the edges (E(p) ∩ E(q)) ∩ E(T ) and (E(p) ∩ E(q)) ∩ E(S) are stuffled, then, ∆ q (T p S) will give the same element as ∆ q (T p S).

As in the dendriform version, this corollary can be expressed in terms of the terplicial and the tridendriform products and coproducts with the characteristic map of the cofiltration only without referring to cutting paths and stuffle paths. D(p, q)1 F p • ∆ (T ) 1 (∆ (T ) 2 * ∆ (S) 1 ) ⊗ 1 F q • ∆ (S) 2 .

But, as the terplicial structure is needed, it would be easier to refer to the co-terplicial terplicial rigidity theorem 6.3.3. 9 Application to the non-freeness of some tridendriform algebras Consider a given tridendriform algebra (A, ≺, •, ). Define on it the associated dual coproduct. This coproduct will be well-defined if as a tridendriform coalgebra it is conilpotent. It is not the case if the algebra as a cyclic relation. For example consider the multi-perm tridendriform algebra in [START_REF] Burgunder | Tridendriform structure on combinatorial Hopf algebras[END_REF]: this algebra has a cyclic relation as [START_REF] Burgunder | Rigidity theorem, freeness of algebras and applications[END_REF] • [1] = [START_REF] Burgunder | Rigidity theorem, freeness of algebras and applications[END_REF] and therefore the coproduct ∆ • (1) is a series and is not well-defined.

Assume the coalgebra is conilpotent A * = ∪ n F n A. The co-filtration is the key to prove the freeness: it suffices to check that for every a, b ∈ A such that a ∈ F n A, b ∈ F m A, the number of terms of a • b, where • ∈ { ; •, ≺} is as defined in corollary 8.5.1 i.e. respectively D(n -1, m), D(m -1, n -1), D(n, m -1).

If the number of elements in the products are verified, the second step, is to use the defined isomorphism between ∪ n k=0 F k A to ⊕ n k=0 T ∞ ⊗ V ⊗k that has been constructed through the lower co-filtrations and check if the compatibility relation coincides.

WSym

The Hopf algebra W Sym of sets of partitions of integers will never be free as a tridendriform algebra as the number of different terms of {{1}} {{1}} = {{1, 2}} + {{1}, {2}} is 2 and it has to be at least 3.

Parking algebras

Parking functions with the tridendriform strucutre given is [START_REF] Novelli | Hopf algebras and dendriform structures arising from parking functions[END_REF] are not free as shown in [START_REF] Vong | On (non-) freeness of some tridendriform algebras[END_REF]. It can be reproven as the structure does not verify as the compatibility relation between the product and the associated dual coproduct do not verify the compatiblity relation of the cotridendriform tridendriform bialgebras.

We recall the tridendriform structure on the parking functions P QSym * .

f ≺ g := where the sums are taken over all pairs of maps (h, k) verifying that hk is parking, std(h) = f and std(k) = g, for f, g ∈ n≥1 PF n . The definition of the associated dual cotridendriform coproduct is:

∆ ≺ (f ) := δ f * (h≺k) =0 1 f * (h ≺ k) h ⊗ k, ∆ • (f ) := δ f * (h•k) =0 1 f * (h • k) h ⊗ k, ∆ (f ) := δ f * (h k) =0 1 f * (h k) h ⊗ k,
where f * is the element defined as f * (k) = δ f k the Kroenecher symbol providing P QSym * with a linear basis given by the f * .

Example 1 . 2 . 4 .

 124 One can consider the cooperations on P BT (K) as the duals with respect to the basis of planar binary trees PBT of the operations i.e. intuitively ∆ ≺ (T ) = a≺b T a ⊗ b and respectively ∆ (T ) = a b T a ⊗ b.

Example 2 . 1 . 1 .

 211 For x = (2, 4, 1, 5, 5, 3, 6, 7, 3, 1, 2, 5) the left to right maxima are in bold red: (2, 4, 1, 5, 5, 3, 6, 7, 3, 1, 2, 5) and LR(x) = (1, 2, 4, 7, 8). The right to left maxima are in bold red: (2, 4, 1, 5, 5, 3, 6, 7, 3, 1, 2, 5) and RL(x) = (8, 12).

Figure 1 .

 1 Figure 1. Path product associated to the shuffle path p = (l S 1 , r T 1 , r T 2 ) (in dashed and red).

Figure 2 .

 2 Figure 2. ∆ * in terms of cutting paths. Proposition 3.2.1. Let T be a binary tree. The co-operations defined in example 1.2.4 verify:

Example 3 . 2 . 3 .

 323 For T = a b and S = c d e , the set of right shuffle paths is P > = {{c, d, e, a, b}, {c, a, b, d, e}, {c, d, a, b, e}, {c, a, d, e, b}, {c, d, a, e, b}, {c, a, d, b, e}} then T p S, with p ∈ P > (T, S), are given respectively by: 3.3 Combinatorial description of the (co)duplicial (co)products on P BT through paths. 3.3.1 Co-duplicial coproducts on P BT and cutting paths Let T be a tree. Denote the edges of its rightmost path by r T 1 , . . . , r T |r T | and the edges of its leftmost path l T 1 , . . . l T |l T | . Let e be an edge of T . Denote T e the subtree of T growing from e (i.e. the target of e is the root of T e ). Proposition 3.3.1. The coduplicial coproducts defined in 1.2.8 verify:

3. 3 . 2

 32 Duplicial products and shuffle paths: Let T and S be two trees. Denote the rightmost path of T by r T and its edges r T 1 , . . . , r T |r T | . Respectively denote the leftmost path of S by l S and its edges l S 1 , . . . l S |l S | . Proposition 3.3.2. The duplicial operations defined in 1.2.6 verify: T S = T * (l 1 ,...,l |l S | ,r T 1 ,...,r T |r T | ) S T S = T * (r T 1 ,...,r T |r T |

4. 2

 2 Dendriform operad and Tamari lattice. Loday introduced the notion of dendriform operad deeply linked with planar binary trees as explained above. He introduced with Ronco a structure of Hopf algebra on planar binary trees in [?]. The link between Tamari posets and dendriform operad enables us to count elements of some intervals of the Tamari lattice. Proposition 4.2.1 ([6], prop 3.2). The dendriform and duplicial products enable the description of the following intervals: [T S; T S] = {X|X ∈ T ≺ S}, for any planar binary trees T and S.

Example 6 . 1 . 4 . 1 T

 6141 As in the dendriform framework, we will consider the coproducts obtained as duals of the above tridendriform products on the vector space generated by planar reduced root trees T ∞ : for every T ∈ T * b the elements T * ∞ defined as T * (S) = δ T S where δ is the Kronecker symbol, thus providing T * ∞ with a linear basis give by T * b . Then, the expressions for the cooperations reads ∆ ≺ (T ) = a,b∈T∞ δ T * (a≺b) =0 * (a≺b) a ⊗ b.

Proposition 8 . 3 . 1 .

 831 The tridendriform operations defined in 6.1.2 are described as follows: Let T and S be two rooted planar trees thenT * S = p∈P(T,S) T p S T ≺ S = p∈P<(T,S)It is immediate by induction through description of T p S and the constructive way to define the operation in 6.1.2.

Figure 4 .

 4 Figure 4. Stuffle and cutting path in a product. T * p S

Corollary 8 . 5 . 1 .

 851 The number of terms ofT ⊗ S appearing in ∆ * (T * S) is D(R T , L S ).As a consequence the number of elementsT ⊗S in ∆ ≺ (T ≺ S) is D(R T , L S -1), in ∆ • (T • S) is D(R T -1, L S -1) and in ∆ (T S) is D(R T -1, L S ).

1 . 2 :

 12 T * S = ∨(T * s 1 , s 2 . . . , s m ) + ∨(t 1 , . . . , t n-1 , t n * s 1 , s 2 , . . . , s m ) + ∨(t 1 , . . . , t n-1 , t n * S). It gives rise to the following inductive property D(R T , L S ) = D(R T , L S -1) + D(R T -1, L S -1) + D(R T -1, L S )which is exactly the defining recurrence relation for the Delannoy numbers. Proposition 8.5.2. The edges of r T are denoted (e T i ) 1≤i≤R T , the edges of l S are denoted (e S i ) 1≤i≤l S . Denote by q T

Example 8 . 5 . 3 . 2 +

 8532 Denote by F t the t th cofiltration with respect to the operation . For example one confluence law reads as follows: forT ∈ F t , S ∈ F s ∆ (T S) =D(t, s -1)T ⊗ S+ 1≤p≤t,1≤q≤s D(p, q)1 F q • ∆ * (T ) 1 ⊗ (∆ * (T ) 2 * ∆ (S) 1 ) 1 F p • ∆ (S)

  and the vertices are obtained as the union of the vertices of r T and l S quotiented by the relation that for two adjacent edges e i

	T * (e 1 p ,...,e m p ) S =	∨(t l , t r * (e 2 p ,...,e m p ) S) ∨(T * (e 2	if e 1 p = e 1 r T

p , e i+1 p in the sequence p, s(e i+1 p ) = t(e i p ). Rewrite the edges (couple of vertices) accordingly.

We will define a product indexed by a shuffle path p, denoted by T * p S, inductively as follows: p ,...,e m p ) s r , s l

  e 1 r T and e 1 = e 1 (e 2 ,...,e k ) s 1 , s 2 , . . . , s m ) if e 1 = e 1 r T and e 1 = e 1 l S ∨(t 1 , . . . , t n-1 , t n (e 2 ,...,e k ) s 1 , s 2 , . . . , s m ) Consider T and S as represented below where t i are subtrees of T and s i are subtrees of S. Denote the edges of the rightmost path of T * by (e T i ) and the edges of the leftmost path of S by (e S i ). Consider the product of T and S indexed by the stuffle path p = (e T Let U = ∨(u 1 , . . . , u n ), denote from left to right e 1 , . . . , e n the edges whose sources is the root. Denote the edges of the leftmost path l U of U by (l U i ) 1≤i≤|l U | , and the rightmost path r U (r U i ) 1≤i≤|l U | .

											l S
							∨(t 1 , . . . , t n-1 , t n (e 2 ,...,e k ) S)
							if e 1 = e 1 r T and e 1 = e 1 l S
	∨(T Example 8.1.1. 1 , e S 1 , e S 2 , {e T 2 , e S 3 }, e T 3 , e T 4 ), where {e T 2 , e S 3 } means that the two considered edges are identified in the
	stuffle path. Then,
													t 4
												t 3
	T =	t 1	t 2 e T 1	t 3 .	t 4 . .	e T 4	, S =	e S 3	s 2 e S s 3 1 . . .	s 1	and T p S =	t 2	s 3 s 2 t 1	s 1	.
	8.2 Combinatorial description of the terplicial (co)structure on
	T ∞ via stuffle paths and trimming edges. Consider two planar rooted
	trees T, S, with r T the rightmost path of T with edges denoted by (e T i ) 1≤i≤k and l S the leftmost path of S with edges denoted (e S i ) 1≤i≤l .
	Proposition 8.2.1. The terplicial operations defined in Theorem 6.2.2 ver-
	ify:				T S = T (e T 1 ,e S 1 ,...,e S l ,e T 2 ,...,e T k ) S
					T S = T ({e T 1 ,e S 1 },e S 2 ,...,e S l ,e T 2 ,...,e T k ) S
					T S = T (e S 1 ,...,e S l ,e T 1 ,...,e T k ) S
	Proposition 8.2.2. The terplicial cooperations defined in Theorem 6.2.2
	verify:

  And the edge j will be either an edge of the leftmost path of S or of the leftmost path of T e T 1 .8.4.3 Combinatorial confluence laws for the coterplicial-tridendriform bial-gebra structure on T ∞ We prove the confluence law given in example 6.3.5:Proof. Let T and S be two planar trees, the confluence laws are deduced from lemma 8.4.2 considering the definitions of the products in 8.3.1 and coproducts in 8.2.2. Indeed, for example:

	e S 1 ,...,e S l ,e T 2 ,...,e T k ) S) ,
	where here U denotes T S.

Theorems 6.3.3 and 6.3.6 give as a corolla that: Proposition 7.1.2. The algebra of ST is free as terplicial algebra and free as a tridendriform algebra.

8 Combinatorial description of the products, coproducts and confluence law on T ∞ .

Path cutting and stuffled paths

8.1.1 Coproducts indexed by a cutting path: Consider a tree T = ∨(t 1 , . . . , t n ).

We will denote from left to right the edges of the tree T attached to the root as e 1 r , • • • , e n r . Let e be an edge in T , define T e the subtree of T growing above the edge e and T e ρ the subtree where the root is the root of T namely ρ and made all the paths from the root to leaves which do not encounter the edge e, together with the root to the target of the edge e (i.e. the cutting edge is part of T e ρ ). Let q be a cutting path in T from the root to a leaf, and denotes its edges (e 1 , . . . , e k ). We will define the cut of a tree through this path q. If the path q is the leftmost path of T , namely l T , define ∆ l T (T ) as:

If the path q is the rightmost path of T , namely r T , define ∆ r T (T ) as:

If q is neither the leftmost nor the rightmost path define ∆ q (T ) as:

Products indexed by a stuffle path

Consider also a tree S = ∨(s 1 , . . . , s m ). Consider the rightmost path of T , denoted r T with its edges ordered from root to leaf denoted by (e i r T ) i , and the leftmost path of S denoted l S , with its edges ordered from root to leaf (e i l S ) i with i integer. Consider the sequence of edges noted (e i p ) resulting in the stuffle -as recalled in section 7.1of the edges of r T and l S . The sequence will start with e 1 r T or e 1 l S or the identification of the two edges. The vertices are obtained as the union of the vertices of r T and l S quotiented by the relations, for two adjacent edges e i p e i+1 p , s(e i+1 p ) = t(e i p ), and if an edge e i r T of r T and an edge e j l S of l S are identified, s(e i r T ) = s(e j l S ) and t(e i r T ) = t(e j l S ). Rewrite the edges (couple of vertices) accordingly. The obtained path is referred to as a stuffle path of T and S.

Example 8.3.3. Consider Figure 3. For a given tree T , we describe the set of cutting path Q(T ) with the colours to indicate their belonging to the subsets Q > (T ) if the cutting path is in red, Q = (T ) if the cutting path is in green, and Q < (T ) if the cutting path is in blue. Then we give the associated coproducts as sum of ∆ q for a cutting path following the left to right order given in the description of Q.

Confluence laws of the bialgebra structures on T ∞

In this section, we will prove a combinatorial version of the confluence laws on the tridendriform-tridendriform bialgebra structure on T ∞ . It is an efficient tool to guess the tridendriform structure that a combinatorial object "should" be free or prove that a given tridendriform structure is not free with little effort. The first step as in the dendriform section is to compute the distributive laws for the products indexed by a stuffle path with the coproducts indexed by a cutting path.

Confluence law for a product indexed by a stuffle path and a coproduct indexed by a cutting path

Lemma 8.4.1. Let T and S be two trees p ∈ P(T, S) a stuffle path, and q ∈ Q(T * p S) a cutting path. Let p ∩ q be the possibly empty path in T p S with edges E(p)∩E(q). Consider also the path in T p S denoted q c composed of the edges E(q) \ (E(p) ∩ E(q)). This path is a path with edges strictly in T or in S denoted q T respectively q S . Proof. The proof is analogous to the proof of lemma 3.4.2: it is proven by induction on the number of leaves. It is clear in low dimensions. Suppose the property true for trees such that the sum of their leaves is equal to n. Consider two trees T = ∨(t 1 , . . . , t n ) and S = ∨(s 1 , . . . , s m ) with total number of trees n + 1. Let the edges of the stuffle path be denoted (p i ) 1≤i≤k and the edges of the cutting path (q i ) 1≤i≤l .

Two cases can occur: q 1 = p 1 then consider the stuffle path (p 2 , . . . , p k ) and the cutting path (q 2 , . . . , q l ) in the trees

and conclude by induction.

If q 1 = p 1 suppose moreover that p 1 is an edge of r T but not an edge of l S (the symmetric being p 1 is an edge of l S but not an edge of r T and is analogous). Then by construction, q 1 is an edge attached to the root of T which is not the rightmost edge. Let say it is the edge such that t o grows from it. So E(q) ⊂ E(T )\E(r T ) as ∆ q (T p S) = ∨(t 1 , . . . , t o-1 , ∆ (q 2 ,...,q l ) (t o ) 1 ))⊗ ∨(∆ (q 2 ,...,q l ) (t o ) 1 ), t o+1 , . . . , t n p 2 ,...,p k S) proving that q is a a path with edges strictly in T . Suppose that p 1 is the first edge of r T identified to the first edge of l S , then one concludes by induction on the trees T 1 = t n , S 1 = s 1 , with the stuffle path (p 2 , . . . , p k ) and cutting path (q 2 , . . . q l ).

With the notation of the above lemma, denote p c the path in T p S defined by the sequence of edges in E(p) \ (E(p) ∩ E(q)), denote by p S the path in T p S define by the sequences of edges (E(p) ∩ E(q) ∩ E(S)) ∪ E(p c ) respectively denote p T the path in T p S the path defined by the sequence of edges (E(p) ∩ E(q) ∩ E(T )) ∪ E(p c ). When E(q) ⊂ E(T ) ∪ E(p ∩ q) then denote [q] T the path in T defined by the sequence of E(q) ∩ E(T ) and if E(q) ⊂ E(S) ∪ E(p ∩ q) then denote by [q] S the path in S defined by the sequence of edges E(q) ∩ E(S). Lemma 8.4.2. Let T and S be two planar trees. Consider a stuffle path p ∈ P(T, S) and a cutting path q ∈ Q(T p S). The two operations are linked through the following confluence law:

Proof. The proof is analogous to the proof of lemma 3.4.3 and is proven by induction on the number of leaves (for n = 1, 2, 3 it is clear). The idea of the proof lies in the fact that the cutting path is determined by a leaf (to which the cutting path leads) and by definition of T p S this leaf is a former leaf of T or of S.

Suppose by induction that the lemma is true when the total number of leaves of the two trees considered equals to n. Then consider two planar trees T = ∨(t 1 , . . . , t n ) and S = ∨(s 1 , . . . , s m ) such that the total number of their leaves equals to n + 1. The sequence of edges of the stuffle path p will Suppose there exists V = {v 1 , . . . , v n } a vector space such that P QSym * ∼ = T ridend(V ) as tridendriform algebras. Consider the morphism ϕ : V → P QSym * such that v 1 ∈ V → 1 and that φ : T ridend(V ) → P QSym * is an isomorphism. Then, consider the example:

The cotridendriform-tridendriform compatibility relation is not satisfied, thus the algebra is not free as a tridendriform algebra. Indeed, the definition of the coproduct on Park only depends on its tridendriform structure and thus will will coincide through ϕ -1 to the one defined on T ∞ .

Here the number of terms of the product is verified for this example, this is why we need to go through the constructed isomorphism.