Samuele Giraudo

DUALITY OF GRADED GRAPHS THROUGH OPERADS

Keywords: 2010 Mathematics Subject Classification. 05C05, 06A07, 05C25, 18D50 Poset, Lattice, Dual graded graph, Tree, Nonsymmetric operad. 1

A

. Pairs of graded graphs, together with the Fomin property of graded graph duality, are rich combinatorial structures providing among other a framework for enumeration. The prototypical example is the one of the Young graded graph of integer partitions, allowing us to connect number of standard Young tableaux and numbers of permutations. Here, we use operads, that algebraic devices abstracting the notion of composition of combinatorial objects, to build pairs of graded graphs. For this, we first construct a pair of graded graphs where vertices are syntax trees, the elements of free nonsymmetric operads. This pair of graphs is dual for a new notion of duality called φ-diagonal duality, similar to the ones introduced by Fomin. We also provide a general way to build pairs of graded graphs from operads, wherein underlying posets are analogous to the Young lattice. Some examples of operads leading to new pairs of graded graphs involving integer compositions, Motzkin paths, and -trees are considered.

relating the numbers λ of standard Young tableaux of shape λ and number of permutations is one of the most fascinating identities appearing in algebraic combinatorics. This formula, admitting a lot of different proofs [Sag01], arises in the context of representations of symmetric groups and the Robinson-Schensted correspondence. One of its proofs is surprisingly beautiful and uses the Young lattice Y on integer partitions and its structure of a differential poset [START_REF] Stanley | Differential posets[END_REF]. Such a poset satisfies the relation

U U -UU = I (0.0.2)
where I is the identity map, and U (resp. U ) is the linear map sending each element of the poset to the formal sum of its coverings (resp. of the elements it covers). One can interpret (0.0.1) as an identity between Hasse walks of length in Y starting from the empty integer partition to an integer partition of rank and returning to the empty integer partition.

A natural question concerns the generalization of this concept of differential posets, in order to obtain new combinatorial proofs similar to the previous formula or to discover new ones. In this context, the notion of graded graph duality [Fom94] makes sense. Here, we work not only with posets but with multigraphs wherein analogs of (0.0.2) hold between two different graphs, called pairs of dual graphs. All this maintains close connections with algebra since, from the origins, the Hasse diagram of Y is in fact the Bratteli diagram (or multiplication graph) of the algebra of the symmetric functions on the basis of Schur functions λ , where edges encode the multiplication by 1 . A striking and nice fact is that one can construct similar graphs for other algebraic structures [START_REF] Nzeutchap | Graded Graphs and Fomin's -correspondences associated to the Hopf Algebras of Planar Binary Trees, Quasi-symmetric Functions and Noncommutative Symmetric Functions[END_REF]LS07] like the algebra of the noncommutative symmetric functions or the Hopf algebra of planar binary trees [START_REF] Hivert | The Algebra of Binary Search Trees[END_REF].

The starting motivation of this work was to link this theory of duality of graded graphs with the theory of operads, with the aim to construct new pairs of dual graded graphs and explore the combinatorial properties they offer. Operads [Mé15,LV12,Gir18] are algebraic structures wherein elements are themselves operations, and can be composed. From a combinatorial point of view, operads allow to insert combinatorial objects inside other ones to form bigger ones [Gir15]. Since operads enclose a rich combinatorics, we can expect that these structures are good combinatorial sources to build interesting graphs.

We begin by constructing a pair (S • (G) U V) of graphs where vertices are the elements of free nonsymmetric operads, that are planar rooted trees decorated on an alphabet G. The graphs (S • (G) U) and (S • (G) V) are dual with respect to a new notion of duality called φ-diagonal duality, generalizing in a certain way some of the previous ones. Also, the poset for which (S • (G) U) is the Hasse diagram has some combinatorial properties like to be a meet-semilattice and to have all intervals that are distributive lattices. Then, given an operad satisfying some not so restrictive properties, we extend the previous construction to build a pair of graded graphs ( • U V), potentially φ-diagonal dual. We consider four examples: the pair corresponding with the associative operad (which is called the chain in [Fom94]), with the diassociative operad [START_REF] Loday | Dialgebras. In Dialgebras and related operads[END_REF] (which is not φ-diagonal dual but is φdiagonal self-dual), with the operad of integer compositions [Gir15] (which leads to the composition poset introduced in [START_REF] Bjöner | An analogue of Young's lattice for compositions[END_REF]), and with the operad of Motzkin paths [Gir15] (which is φ-diagonal dual). This paper is organized as follows. Section 1 contains the preliminary definitions used in the rest of the document including graded graphs, formal power series on combinatorial objects, syntax trees, and nonsymmetric operads. We also set here our definition of φdiagonal duality. We then introduce in Section 2 two graded graphs of syntax trees: the prefix graded graph (S • (G) U) and the twisted prefix graded graph (S • (G) V). We prove here in particular that the pair of graded graphs (S • (G) U V) is φ-diagonal dual for a certain linear map φ. Some combinatorial properties of these graphs are established: the numbers of Hasse walks in the prefix graded graphs are related with the hook-length formula of trees [Knu98] and the numbers of Hasse walks in the twisted ones are related with a variation of this formula. In Section 3, we study the posets associated with the prefix graded graphs. In particular, we describe the structure of the intervals of these posets. Finally, Section 4 is devoted to generalize the previous constructions of graded graphs in order to obtain pairs of graded graphs from nonsymmetric operads subjected to some conditions. We apply these constructions to some operads introduced in [Gir15], involving integer compositions, Motzkin paths, and -trees.

General notations and conventions. All the considered vector spaces are defined over a ground field K of characteristic zero. For any integers and , [ ] denotes the set { + 1 }. For any integer , [ ] denotes the set [1 ]. The empty word is denoted by .

G , ,

We start by setting up our context by providing definitions about graded sets, series, graded graphs, and nonsymmetric operads. We introduce also the notion of φ-diagonal duality.

1.1. Graded graphs and diagonal duality. The aim of this section is to make some recalls about graded graphs and their associated formal power series, about graded graph duality, and to introduce φ-diagonal duality.

1.1.1. Graded sets. A graded set is a set expressed as a disjoint union

G := ∈N G( ) (1.1.1)
such that all G( ), ∈ N, are sets. The rank rk( ) of an ∈ G is the unique integer such that ∈ G( ). A graded set is combinatorial if all G( ), ∈ N, are finite. In this case, the generating series G ( ) of G is defined by

G ( ) := ∈G rk( ) (1.1.2)
and counts the elements of G with respect to their ranks. If G 1 and G 2 are two graded sets, a map ψ : G 1 → G 2 is a graded set morphism if for any ∈ G 1 , rk(ψ( )) = rk( ).

Besides G 2 is a graded subset of G 1 if for any ∈ N, G 2 ( ) ⊆ G 1 ( ).

1.1.2. Polynomials and series. We shall consider in the sequel linear spans of graded sets G, denoted by K G . The dual space K G of K G is by definition the space of the maps f : G → K, called G-series. Let f 1 and f 2 be two G-series. The scalar product of f 1 and f 2 is the element

f 1 f 2 := ∈G f 1 ( )f 2 ( ) (1.1.3)
of K. Note that the scalar product may be not defined for some G-series. For any subset X of G, the characteristic series of X is the G-series ch(X) satisfying, for any ∈ G, ch(X)( ) = [ ∈ X], where [-] is the Iverson bracket. By a slight abuse of notation, we denote simply by the G-series ch({ }). Let f ∈ K G . Observe that for any ∈ G,

f = f( ). The support of f is the set Supp(f) := { ∈ G : f = 0} An element of G appears in f if ∈ Supp(f)
. By a slight abuse of notation, this property is denoted by ∈ f. By exploiting the vector space structure of K G , any G-series f expresses as

f = ∈G f (1.1.4)
This notation using potentially infinite sums of elements of G accompanied with coefficients of K is common in the context of formal power series. In the sequel, we shall define and handle some G-series using the notation (1.1.4). A G-series having a finite support is a G-polynomial. The space K G can be seen as the subspace of K G consisting in all G-polynomials. The Hadamard product of two G-series f 1 and f 2 is the series f 1 f 2 defined, for any ∈ G, by

f 1 f 2 := f 1 f 2
The space of all generating series on one formal parameter is denoted by K . The trace of a G-series f is the generating series tr(f) of K defined by tr(f) :

= ∈G f rk( ) (1.1.5)
This series might be ill-defined when G is not combinatorial. Observe that if f is the characteristic series of G, then tr(f) is the generating series of G.

1.1.3. Graded graphs. A graded graph [Fom94] is a pair (G U) where G is a combinatorial graded set of vertices and U : K G → K G is a linear map such that U( ) ∈ K G( + 1)
for any ∈ G( ). In the sequel, I is the identity map on K G .

Given a pair ( ) ∈ G 2 , let us set ω U ( ) := U( ) . We say that ( ) is an edge of (G U) if ω U ( ) = 0. In this case the weight of this edge is ω

U ( ). A path from 1 ∈ G to ∈ G is a sequence ( 1 ), 1, of vertices of G such that for any ∈ [ -1], ( +1
) is an edge of (G U). The length of ( 1 ) is -1 and its weight is

ω U ( 1 ) := ∈[ -1] ω U ( +1 ) (1.1.6)
As a particular case, the weight of any path of length 0 is 1. The set of all paths of (G U) from to is denoted by U ( ). When for all ( ) ∈ G 2 , the coefficients ω U ( ) are nonnegative integers, (G U) is natural. In this case, one can interpret any edge ( ) ∈ G 2 as a bunch of ω U ( ) multi-edges from to . Hence, for any ∈ G, the sum of the weights of all paths from to can be interpreted as the number of multipaths from to . When moreover all coefficients ω U ( ) belong to {0 1}, (G U) is simple. Besides, when there is an element 0 of G such that for any ∈ G, there is a path from 0 to , (G U) is rooted and 0 is the root of the graded graph. Observe that if (G U) is rooted, its root is unique. In this case, for any ∈ G, an initial path to is a path from 0 to in (G U).

The poset of (G U) is the poset (G ) wherein if there is a path in (G U) from the vertex to the vertex of G. The covering relation of this poset is denoted by U and it satisfies, for any ∈ G,

U

if and only if appears in U( ).

We shall draw graded graphs where edges are implicitly oriented from top to bottom. The weight of an edge is written onto it, with the convention that undecorated edges have weight 1. For instance, Figure 1 Young lattice [START_REF] Stanley | Differential posets[END_REF]. Recall that in Y, vertices are integer partitions (represented as Young diagrams) and U(λ) is the sum of all partitions that can be obtained by adding one box to the integer partition λ.

Let U : K G → K G be the adjoint map of U. Due to the fact that G is combinatorial and K G is a graded space decomposing as

K G = ∈N K G( ) (1.1.7)
with finite dimensional homogeneous components K G( ) , 0, the space K G can be identified with its graded dual K G . Therefore, for any ∈ G,

U ( ) = ∈G U( ) = ∈G ω U ( ) (1.1.8)
In the case where (G U) is rooted, the hook series of (G U) is the G-series h U defined by the functional equation

h U = [ = 0] + U ( ) h U (1.1.9) For any ∈ G, h U is the hook coefficient of in (G U).
Proposition 1.1.1. Let (G U) be a rooted graded graph. For any ∈ G,

h U = ∈ U (0 ) ω U ( ) (1.1.10) Moreover, h U = (I -U) -1 (0).
Proof. We proceed by induction on the rank of . When = 0, since (G U) is rooted, we necessarily have = 0. Therefore, since [0 = 0] = 1 and U (0) = 0, the property is satisfied in this case. Otherwise, = 0 and we have by definition of hook series,

h U = U ( ) h U = ∈G U( ) h U = ∈G U( ) h U (1.1.11)
Now, for any ∈ G, if appears in U( ), then the rank of is -1, and by induction hypothesis, h U satisfies (1.1.10). Since all paths from 0 to in (G U) decompose as paths from 0 to elements of rank -1 followed by edges from to , the statement of the proposition follows.

Let us establish the second part of the statement. For this, we prove that for any ∈ G,

U rk( ) (0) = h U (1.1.12)
by induction on the rank of . If = 0, since (G U) is rooted, = 0, and since 0 U 0 (0) = 1 and 0 h U = 1, the property is satisfied. Assume that 1. By (1.1.11) and by induction hypothesis,

h U = ∈G U( ) h U = ∈G U( ) U rk( ) (0) = U rk( ) (0) (1.1.13)
Since finally (I -U) -1 = ∈N U , the stated expression for h U follows. When (G U) is moreover natural, Proposition 1.1.1 says that the hook coefficient of any ∈ G can be interpreted as the number of initial multipaths to in (G U). These coefficients define a statistics on the elements of G which can be of independent combinatorial interest. For instance, the hook coefficient of a partition λ in Y is given by the hook-length formula [START_REF] Frame | The hook graphs of the symmetric groups[END_REF], is also the number of initial paths to λ, and is also the number of standard Young tableaux of shape λ. Therefore, a standard Young tableau of shape λ is to the integer partition λ what an initial path to ∈ G is to in the case where (G U) is a natural rooted graded graph. Moreover, the initial paths series of (G U) is the generating series ip U := tr(h U ). By definition, for any ∈ N, the coefficient ip U can be interpreted as the number of initial multipaths of (G U) of length . In the case of Y, we obtain the generating series counting the standard Young tableaux as initial path series (see Sequence A000085 of [Slo] for its coefficients).

1.1.4. Pairs of graded graphs. A pair of graded graphs is a triple (G U V) such that both (G U) and (G V) are graded graphs. When (G U) and (G V) are both natural, (G U V) is natural. When (G U) and (G V) are both rooted and share the same root 0, (G U V) is rooted and 0 is the root of (G U V). A returning path from ∈ G to ∈ G is a pair (

) such that is a path from to in (G U) and is a path from to in (G V). The length of (

) is the length of (or equivalently, of ) and its weight is

ω U V := ω U ( )ω V (1.1.14)
When (G U V) is rooted, a returning initial path to is a returning path from 0 to in (G U V) and the returning hook series of (G U V) is the G-series rh U V defined by

rh U V := h U h V (1.1.15) For any ∈ G, rh U V is the returning hook coefficient of in (G U V).
Proposition 1.1.2. Let (G U V) be a rooted pair of graded graphs. For any ∈ G,

rh U V = ∈ U (0 ) ∈ V (0 ) ω U V (1.1.16)
Proof. By definition of returning hook series,

rh U V = h U h V = h U h V (1.1.17)
By Proposition 1.1.1, the statement of the proposition follows.

When (G U V) is moreover natural, Proposition 1.1.2 says that the returning hook coefficient of any ∈ G can be interpreted as the number of returning initial paths to in (G U V). These coefficients define a statistics on the elements of G which can be of independent combinatorial interest. For instance, by seeing Y as a pair of graded graphs with V = U, the returning hook coefficient of a partition λ in Y is given by the square of the hook-length formula. Therefore, a pair of standard Young tableaux of the same shape λ is to the integer partition λ what a returning initial path to ∈ G is to in the case where (G U V) is a natural rooted pair of graded graphs. Moreover, the returning initial paths series of (G U V) is the generating series rip U V := tr(rh U V ) By definition, for any ∈ N, the coefficient of rip U V can be interpreted as the number of returning initial multipaths of (G U V) of length . In the case of Y, we obtain the generating series counting the permutations as returning initial paths series (see (0.0.1) and [Sag01]). 1.1.5. Dual graded graphs. Let (G U V) be a pair of graded graphs. One says that (G U V) is φ-diagonal dual if φ : K G → K G is a diagonal linear map that is, for any ∈ G, φ( ) = λ where λ ∈ K, and

V U -UV = φ (1.1.18)
This notion is a generalization of -duality, and hence, of -duality and duality of graded graphs (see [Fom94]). Indeed, in the case where φ( ) = rk( ) for any ∈ G, one recovers -duality. Duality of graded graphs is very closely connected with the theory of -differential posets [START_REF] Stanley | Differential posets[END_REF]. In the case where (G U U) is φ-diagonal dual, we say that (G U) is φ-diagonal self-dual.

Proposition 1.1.3. Let (G U V) be a pair of φ-diagonal dual graded graphs. For any 0,

V U = U V + 1 2 0 1 + 2 = -1 U 1 φU 2 (1.1.19)
Proof. We proceed by induction on . When = 0, the property holds since the lefthand side of (1.1.19) is V U 0 = V I = V while its right-hand side is U 0 V = IV = V Assume that the property holds for a 0. Hence, by induction hypothesis and by using Relation (1.1.18) implied by of φ-diagonal duality of (G U V), we have

V U +1 = V U U = U V U + 1 2 0 1 + 2 = -1 U 1 φU 2 +1 = U (φ + UV ) + 1 2 0 1 + 2 = -1 U 1 φU 2 +1 = U +1 V + U φ + 1 2 0 1 + 2 = -1 U 1 φU 2 +1 = U +1 V + 1 2 0 1 + 2 = U 1 φU 2 (1.1.20) establishing (1.1.19).
Observe that when (G U V) is a pair of φ-diagonal dual graded graphs such that φ commutes with U, there exists an ∈ K such that the map φ satisfies φ( ) = for any ∈ G. This implies that in this case, (G U V) is a pair of -dual graphs and Proposition 1.1.3 brings us the well-known identity [START_REF] Stanley | Differential posets[END_REF] V U = U V + U -1

(1.1.21) holding for any 0.

1.2. Syntax trees. We set here elementary definitions and notations about syntax trees and composition operations on syntax trees. Most of these notions can be found in [Gir18, Chapter 3.].

1.2.1. Elementary definitions. An alphabet is a graded set G such that G(0) = ∅. The elements of G are letters. The arity |a| of a letter a ∈ G is its rank. A G-tree (also called G-syntax tree) is a planar rooted tree such that its internal nodes of arity are decorated by letters of arity of G. More precisely, a G-tree is either the leaf or a pair a t 1 t |a| where a ∈ G and t 1 , . . . , t |a|] are G-trees. Unless otherwise specified, we use in the sequel the standard terminology (such as node, internal node, leaf, edge, root, child, ancestor, etc.) about planar rooted trees [START_REF] Knuth | The Art of Computer Programming[END_REF] (see also [Gir18]). Let us set here the most important definitions employed in this work.

Let t = a t 1 t |a| be a G-tree. For any word of positive integers, let t( ) be the partial map defined recursively as follows.

(i) If = , then t( ) := t; (ii) If = 1 2 with 1 and 1 ∈ [|a|], then t( ) := t 1 ( 2 ); (iii) Otherwise, t( ) is not defined.
A node of t is any word of positive integers such that t( ) is well-defined. In this case, t( ) is the -suffix subtree of t. Moreover, for any ∈ [ ] where is the arity of the node in t, t( ) is the -th subtree of in t. A node of t is internal if is a proper prefix of an other node of t. A leaf of t is a node of t which is not internal. We denote by (t) (resp.

• (t), (t)) the set of all nodes (resp. internal nodes, leaves) of t.

The degree deg(t) (resp. arity |t|) of t is its number of internal nodes (resp. leaves). The only G-tree of degree 0 and arity 1 is the leaf and is denoted by . For any a ∈ G( ), the corolla decorated by a is the tree c(a) consisting in one internal node decorated by a having as children leaves. The leaves of t are totally ordered by their position in (t) with respect to the lexicographic order. They are thus implicitly indexed from 1 to |t|. is a G-tree of degree 5 and arity 8. Its root is decorated by c and has arity 3. Moreover, we have 1.2.2. Graded sets of syntax trees and partial compositions. Given an alphabet G, we denote by S (G) (resp. S • (G)) the graded set of all the G-trees where the rank of a tree is its arity (resp. its degree). When G is finite, the graded set S • (G) is combinatorial and its generating series S • (G) ( ), counting its elements with respect to their degrees, satisfies

t(1) = b = c(b) t(2) = t(3) = c a a t(32) = a = c(a) (
S • (G) ( ) = 1 + G S • (G) ( ) (1.2.3) Given t s ∈ S • (G) and ∈ [|t|]
, the partial composition t • s is the G-tree obtained by grafting the root of s onto the -th leaf of t. For instance, by considering the previous graded set G of Section 1. Moreover, for any ∈ (t), we shall denote by t • s the G-tree obtained by grafting the root of s into the leaf of t. For instance, the partial composition shown in (1.2.4) is the same as the one obtained by composing the two considered trees through • 22 since the 5-th leaf of the first tree is 22. By a slight but convenient abuse of notation, given a b ∈ G and ∈ [|a|], we shall in some cases simply write a • b instead of c(a) • c(b). Moreover, when the context is clear, we shall even write a for c(a). In addition, given some G-trees s 1 , .

• : ( ) × ( ) → ( + -1) 1 1 (1.3.1)
called partial compositions, and a distinguished element 1 ∈ (1), the unit of . This data has to satisfy, for any ∈ , the three relations

( • ) • + -1 = • • ∈ [| |] ∈ [| |] (1.3.2a) ( • ) • +| |-1 = • • ∈ [| |] < (1.3.2b) 1 • 1 = = • 1 ∈ [| |] (1.3.2c)
Since we consider in this work only nonsymmetric operads, we shall call these simply operads. The arity | | of any ∈ is its rank. An operad is combinatorial if is combinatorial as a graded set.

Given an operad , one defines the full composition maps of as the maps

• : ( ) × ( 1 ) × • • • × ( ) → ( 1 + • • • + ) 1 1 1 1 (1.3.3)
defined, for any ∈ ( ) and 1 ∈ , by

• [ 1 ] := ( (( • ) • -1 -1 ) ) • 1 1 (1.3.4)
When is combinatorial, the Hilbert series ( ) of is the generating series ( ). If 1 and 2 are two operads, a graded set morphism ψ : 1 → 2 is an operad morphism if it sends the unit of 1 to the unit of 2 and commutes with partial composition maps. We say that 2 is a suboperad of 1 if 2 is a graded subset of 1 , 1 and 2 have the same unit, and the partial compositions of 2 are the ones of 1 restricted on 2 . For any subset G of , the operad generated by G is the smallest suboperad G of containing G. When When G is combinatorial and satisfies G(1) = ∅, the Hilbert series S (G) ( ) satisfies

S (G) ( ) = + G S (G) ( ) (1.3.6)
Free operads satisfy the following universality property. The free operad S (G) is the unique operad (up to isomorphism) such that for any operad and any graded set morphism : G → , there exists a unique operad morphism ψ : S (G) → such that the factorization = ψ • c holds. In other terms, the diagram

G S (G) c ψ (1.3.7)
commutes.

Presentations and treelike expressions.

A presentation of an operad is a pair (G ≡) such that G is an alphabet, ≡ is an operad congruence of S (G), and is isomorphic to S (G)/ ≡ . In most of the practical cases, G is a subset of such that G is a minimal generating set of .

When

satisfies (0) = ∅, is in particular an alphabet. For this reason, S ( ) is a well-defined free operad. The evaluation map of is the map ev : S ( ) → defined as the unique surjective operad morphism satisfying, for any ∈ , ev(c( )) = . Given S a subset of , a treelike expression on S of an element of is a -tree t belonging to the fiber ev -1 ( ) and such that all internal nodes of t are decorated by elements of S. The set of all treelike expressions on S of is denoted by S ( ).

1.3.4. Linear operads. The partial and the full composition operations of an operad extend by linearity on the space K . This fact will be used implicitly in the sequel. Moreover, it is convenient in what follows, when ∈ ( ) and ∈ , to set • := 0 whenever / ∈ [ ]. This convention will be used also implicitly in the sequel. Besides, when is in particular the free operad on G, by a slight abuse of notation, for any a ∈ G and S (G)-polynomials 1 , . . . , |a| , we shall write a( 1 |a| ) for c(a)

• 1 |a| .

G

The objective of this section is to introduce two graded graphs of syntax trees which are φ-diagonal dual for a certain map φ. These graphs will be used as raw material in the next sections in order to associate pairs of graded graphs with operads.

2.1. Prefix graded graphs. We begin by introducing prefix graded graphs and present some of their combinatorial properties.

2.1.1. First definitions and properties. For any finite alphabet G, let (S • (G) U) be the graded graph wherein, for any t ∈ S • (G),

U(t) := a∈G ∈[|t|] t • a (2.1.1) We call (S • (G) U) the G-prefix graph. Since G is finite, U(t) is a S • (G)-polynomial.
Moreover, since all trees appearing in U(t) are of rank deg(t) + 1, the G-prefix graph is a well-defined graded graph. Observe that this graded graph is simple and that it admits as root. Figure 2 shows examples of such graphs.

An internal node of a G-tree t is maximal if has only leaves as children. The set of all maximal nodes of t is denoted by m • (t). For any ∈ m • (t), the deletion of in t is the G-tree del (t) obtained by replacing the node of t by a leaf. By relying on these definitions, the adjoint map of U satisfies, for any t ∈ S • (G), 2.1.2. Diagonal self-duality. We give here a necessary and sufficient condition on the alphabet G for the fact that (S

U (t) = ∈ m • (t) del (t) (2.1.2)
• (G) U) is φ-diagonal self-dual. Proposition 2.1.1. The graded graph (S • (G) U) is φ-diagonal self-dual if and only if G is the empty alphabet or a singleton alphabet. When G is a singleton, φ : K S • (G) → K S • (G) satisfies φ(t) = (|t| -# m • (t)) t (2.1.3)
for any G-tree t.

Proof. First of all, when G is empty, (S • (G) U) is immediately φ-diagonal self-dual for the zero map φ. Assume that G is the singleton {a}. When t = , since (U U -UU )() = , the property is satisfied. Assume now that t has at least one internal node. All terms of (U U)(t) are obtained by changing a leaf of t into an internal node decorated by a, and then by suppressing a maximal internal node of the obtained tree. Then, in particular when the suppressed internal node is the one which has been just added, t occurs in (U U)(t).

For this reason, the coefficient of the term t is |t|. Moreover, all terms of (UU )(t) are obtained by suppressing a maximal internal node of t, and then by changing a leaf into an internal node decorated by a of the obtained tree. For this reason, the coefficient of the term t is m • (t). Finally, since all trees different from t appearing (U U)(t) or in (UU )(t) are the same and have all 1 as coefficient, the statement of the proposition follows.

Conversely, assume that G is not empty neither a singleton. Hence, there exist a b ∈ G with a = b, and we have in particular

(U U -UU )(a) = U     c∈G ∈[|a|] a • c     -U() = (#G)|a| a - c∈G c (2.1.4) Since b appears in (2.1.4), this shows that (S • (G) U) is not φ-diagonal self-dual. 2.1.3. Path enumeration. Recall that if ( ) is a finite poset, a linear extension of is a bijective map σ : → [# ] such that for any ∈ , implies σ( ) σ( ),
where is the natural total order on the set of natural numbers [# ]. The linear extension σ can be encoded by the permutation

( 1 # ) (2.1.5)
of elements of , wherein for any ∈ , σ( ) is the position of in the word (2.1.5).

Observe that if is the disjoint union of some posets 1 , . . . , , 0, each permutation encoding a linear extension σ of is obtained by shuffling the permutations encoding respectively linear extensions σ 1 , . . . , σ of 1 , . . . , . Therefore, if each , ∈ [ ], has linear extensions, then has the multinomial

1 ! := ( 1 + • • • + )! 1 ! ! (2.1.6)
as number of linear extensions.

The poset induced by a G-tree t is the poset P(t) := ( • (t) ) wherein for any ∈

• (t),
if is an ancestor of . The number h(t) of all linear extensions of P(t) is given by the hook-length formula for rooted planar trees [Knu98] and satisfies

h(t) = deg(t)! ∈ • (t) deg(t( )) (2.1.7)
By elementary computations involving multinomial coefficients, and by structural induction on G-trees, one can show that these numbers satisfy the recurrence relation

h() = 1 (2.1.8a) h a( s 1 s |a| ) = deg(s 1 ) deg s |a| ! ∈[|a|] h(s ) (2.1.8b)
for any a ∈ G and any G-trees s 1 , . . . , s |a| .

Proposition 2.1.2. For any finite alphabet G, the hook series of (S • (G) U) satisfies t h U = h(t) for any G-tree t.

Proof. Let us proceed by induction on the degree of the G-trees. By definition of h U , h U = 1, and since h() = 1, the property holds. Now, let t be a G-tree of degree 1. We have, by definition of h U , by (2.1.2), and by induction hypothesis,

t h U = U (t) h U = ∈ m • (t) del (t) h U = ∈ m • (t) del (t) h U = ∈ m • (t)
h(del (t))

(2.1.9)

From the definition of P(t), it follows that any permutation encoding a linear extension of

P(t) writes as (1) ( -2) (2.1.10)
where the permutation

( -2) encodes a linear extension of P(del (t)) and is a maximal node of t. This leads, by (2.1.9), to t h U = h(t).

For any alphabet G, let G be the arity of a letter having a maximal arity in G.

Proposition 2.1.3. For any finite alphabet G, the initial path series of (S • (G) U) satisfies

ip U = ∈[1+( G -1) ] θ( ) (2.1.11)
for any 0, where θ( ) satisfies the recurrence θ( ) = 0 for any 0 and ∈ Z, θ(0 1) = 1, and θ(

) = a∈G |a| ( + 1 -|a|) θ( -1 + 1 -|a|) (2.1.12)
for any 1 and 1.

Proof. Let us prove that θ(

) is the number of initial paths in (S • (G) U) to elements of degree and arity by induction on 0. First, since there are no syntax trees of arity 0 or less, θ( ) = 0 for any 0 and ∈ Z. Moreover, since θ(0 1) = 1, the property is satisfied because is the unique tree of degree 0 and arity 1, and there is exactly one initial path to . Assume now that 1. Any initial path to a tree t of degree and arity decomposes as an initial path to a tree t of degree -1 such that t appears in U(t ). Hence, there is an ∈ [|t |] and an a ∈ G such that t = t • a. This implies that |t | = + 1 -|a| and |a|

. By induction hypothesis, there are θ( -1 |t |) initial paths to trees of degree -1 and arity |t |. Therefore, due to the fact that initial paths to trees of degree decompose as explained before, θ( ) satisfies the claimed property. Finally, (2.1.11) is a consequence of the fact that a G-tree of degree has 1 as minimal arity and 1 + ( G -1) as maximal arity. Indeed, this maximal arity is reached for trees consisting only in internal nodes of a maximal arity G .

Here are the sequences of the first coefficients of some initial paths series of (S • (G) U): These are respectively Sequences A000142, A001147, A000165, and A112487 of [Slo].

2.2. Twisted prefix graded graphs. We now introduce a second sort of graded graphs and present some of their combinatorial properties. The aim is to study this graded graph in order to show in the next section that, together with the first kind of graded graphs, this forms a pair of φ-diagonal dual graded graphs.

First definitions and properties.

For any finite alphabet G, let V : This recursive definition for V is convenient to set up proofs by induction of properties involving this map. Nevertheless, we shall consider also a non-recursive description relying on the following definitions. Let t be a G-tree decomposing as t = s • (a • s ) where s and s are G-trees, ∈ (s), ∈ [|a|], and a ∈ G. The contraction of the internal node of t is the G-tree con (t) := s • s . For instance, by considering the same alphabet G as in the previous example, the contraction of the node 2 of the G-tree

K S • (G) → K S • (G) be the linear map satisfying the recurrence V () := 0 (2.2.1a) V (a( s )) := s (2.2.1b) V a( s 1 s |a| ) := ∈[2 |a|] a( s 1 s -1 V s s +1 s |a| ) (2.
t := a a a c c a = a c • 2    c • 3 a a a    (2.2.3) is con 2 (t) = a c • 2 a a a = a c a a a (2.2.4)
Observe that when is a maximal internal node of t, one has con (t) = del (t).

Besides, an internal node of t is quasi-maximal if admits no occurrence of the letter 1 and all are leaves for all ∈ [2 ] where is the arity of in t. In other words, the path connecting the root of t with does never go through a first edge of an internal node and has only leaves as children except possibly at first position. We denote by qm • (t) the set of all quasi-maximal nodes of t. For instance, by considering the same alphabet G as in the previous examples, here is a G-tree wherein its quasi-maximal nodes are framed: (2.2.5)

Observe that for any ∈ qm

• (t), one has t = s • (a • 1 s
) where s and s are G-trees, possibly leaves. Therefore, con (t) is well-defined.

By relying on these definitions, the map V rephrases, in a non-recursive way, as follows.

Proposition 2.2.1. For any finite alphabet G and any G-tree t, the map V satisfies

V (t) = ∈ qm • (t) con (t) (2.2.6)
Proof. We proceed by induction on the degree of t. If = 0, then t = and we have V () = 0. Moreover, since has no internal node, the right-hand side of (2.2.6) is equal to 0. Hence, the property holds here. Assume now that 1. If t decomposes as t = a( s ) where a ∈ G and s is a G-tree, we have V (t) = s and, since the root of t is the only quasi-maximal node of t, the right-hand side of (2.2.6) is equal to con (t) = s. Hence, the property holds here also. It remains to explore the case where t decomposes as t = a( s 1 s |a| ) where a ∈ G and s 1 , . . . , s |a| are G-trees such that there is a ∈ [2 |a|] such that s = . We have, by definition of V and by induction hypothesis,

V (t) = ∈[2 |a|] a( s 1 s -1 V s s +1 s |a| ) = ∈[2 |a|] a( s 1 s -1 ∈ qm • ( s ) con s s +1 s |a| ) (2.2.7)
Now, the last member of (2.2.7) is equal to the right-hand side of (2.2.6) since qm

• (t) = ∈[2 |a|] : ∈ qm • s (2.2.8)
This says that the quasi-maximal nodes of t come from the quasi-maximal nodes of the s ,

∈ [2 |a|]. Whence (2.2.6) is established.
It follows from Proposition 2.2.1 that for any G-tree t, all the trees appearing in V (t) have deg(t) -1 as degree. For this reason, the graph (S • (G) V) is graded and the rank of a G-tree is its degree. We call (S • (G) V) the G-twisted prefix graph. Besides, again by Proposition 2.2.1, for any G-tree t, the trees appearing in V (t) have trivial coefficients. For this reason, the graph (S • (G) V) is simple. Moreover, one can prove by structural induction on G-trees that any G-tree t different from the leaf admits at least one internal node which is quasi-maximal. For this reason, if t is a G-tree different from the leaf, V (t) = 0, implying that (S • (G) V) admits as root. Observe also that when G contains only unary letters, (S • (G) V) is the line.

Since V is the adjoint map of V , we can provide a recursive description of V from the recursive definition of V of (2.2.1a), (2.2.1b), and (2.2.1c). Indeed, it is possible to show by induction on the degrees of the G-trees that V satisfies Observe that when G contains at least one letter a such that |a| 2, (S

V() = a∈G a (2.2.9a) V b( s 1 s |b| ) = a∈G a • 1 b( s 1 s |b| ) +   ∈[2 |b|] b( s 1 s -1 V s s +1 s |b| )   (2.
• (G) V) is not φ-diagonal self-dual. Indeed, (V V -VV )(a • 1 a) = V     b∈G b • 1 (a • 1 a) +     ∈[2 |a|] b∈G a • b • 1 a         -V(a) = (#G) a • 1 a + (#G)(|a| -1) a • 1 a - b∈G b • 1 a -     ∈[2 |a|] b∈G a • b     = (#G)|a| a • 1 a - b∈G b • 1 a -     ∈[2 |a|] b∈G a • b     (2.2.11)
Besides, in the particular case where G = G(2) = {a} the map V satisfies the recurrence

V () = 0 (2.2.12a) V (a( s )) = s (2.2.12b) V (a( s 1 s 2 )) = a( s 1 V (s 2 ) ) (2.2.12c)
for any G-trees s, s 1 , and s 2 such that s 2 = . It follows by induction on the degrees of the G-trees that for any G-tree t, there is at most one term appearing in V (t). For this reason, the graph (S(G) V) is a tree. Proof. We proceed by induction on the degree of t. If = 0, then t = , and since P () has exactly one linear extension which is the empty one, and h (t) = 1, the property is satisfied. If 1, then t = a( s 1 s |a| ) for an a ∈ G and G-trees s 1 , . . . , s |a| . From the definition of P (t), it follows that any permutation encoding a linear extension of P (t) writes as

1 (1) 1 ( ) 1 (1) ( ) (2.2.15)
where the permutation

(1) ( ) encodes a linear extension of P (s 1 ) and the per-

mutation 1 (1)
( ) encodes a linear extension of P a( s 2 s |a| ) . Indeed, by definition of the order relation of P (t), all the nodes (1) , . . . , ( ) of s 1 are smaller than the root of t, and the root of t is itself smaller than all the nodes (1) , . . . , ( ) Proof. Let us proceed by induction on the degree of the G-trees. By definition of h V , h V = 1, and since h () = 1, the property holds. Now, let t be a G-tree of degree 1. We have, by definition of h V , by Proposition 2.2.1, and by induction hypothesis,

t h V = V (t) h V = ∈ qm • (t) con (t) h V = ∈ qm • (t) con (t) h V = ∈ qm • (t) h (con (t)) (2.2.17)
From the definition of P (t), it follows that any permutation encoding a linear extension of P (t) writes as (1) ( -1)

(2.2.18)

where the permutation (1) ( -1) encodes a linear extension of P (con (t)) and is a quasi-maximal node of t. This leads, by using Lemma 2.2.2, to t h V = h (t).

Here are the sequences of the first coefficients of some initial paths series of (S • (G) V): The first and third ones are respectively Sequences A000108 and A151374 of [Slo]. The two other ones do not appear for the time being in [Slo].

1
2.3. Diagonal duality. We prove here that the pair of graded graphs consisting in the G-prefix graph and the G-twisted prefix graph is φ-diagonal dual. The description of the map φ requires the use of a particular statistics on G-trees introduced here.

Non-first leaves statistics.

Let G be an alphabet and t be a G-tree. A leaf of t is non-first if admits no occurrence of the letter 1. In other words, the path connecting the root of t with does never go through a first edge of an internal node. We denote by nf (t) the set of all non-first leaves of t. For instance, by considering the same alphabet G as in the previous examples, here is a G-tree wherein its non-first leaves are framed:

() = 1 (2.3.2a) nfl(a( s )) = |a| -1 (2.3.2b) nfl a( s 1 s |a| ) = ∈[2 |a|] nfl s (2.3.2c)
for any a ∈ G and any G-trees s, s 1 , . . . , s |a| such that there is at least a ∈ [2 |a|] satisfying s = .

Diagonal duality.

Theorem 2.3.1. For any finite alphabet G, the pair of graded graphs (S • (G) U V) is φ-diagonal dual for the linear map φ :

K S • (G) → K S • (G) satisfying φ(t) = (#G)nfl(t) t (2.3.3)
for any G-tree t.

Proof. Let us consider the G-tree polynomial

(t) := (V U -UV )(t) = b∈G 0 V (t • b) -V (t) • b (2.3.4)
Notice that we use here the convention exposed in Section 1.3.4 about extension by linearity of the composition maps of operads in order to write the sum (2.1.1) without bounding . Nevertheless, this sum is finite. We proceed by structural induction on G-trees to show that (t) = φ(t).

We have to consider three cases following t. First, when t = , we immediately have (t) = (#G). Since nfl() = 1, the property is satisfied. Second, when t is of the form t = a( s 1

) for an a ∈ G and a G-tree s 1 , we obtain

(t) = b∈G 0 V (a( s 1 ) • b) -s 1 • b =    b∈G 0 V (a( s 1 • b )) -s 1 • b    +    b∈G ∈[2 |a|] V   a( s 1 -2 b )       =    b∈G 0 s 1 • b -s 1 • b    +    b∈G ∈[2 |a|] a( s 1 -2 V (b) )    = b∈G ∈[2 |a|] a( s 1 ) = (#G)(|a| -1)t (2.3.5)
Since t has the considered form, nfl(t) = |a| -1. Hence, (t) = (#G)nfl(t) t, so that the property is satisfied. Finally, it remains to consider the case where t is of the form t = a( s 1 s |a| ) for an a ∈ G and for G-trees s 1 , . . . , s |a| where there is at least a ∈ [2 |a|] such that s = . In this case, we obtain

(t) = b∈G 0 ∈[2 |a|] a( s 1 • b s -1 V s s +1 s |a| ) + • • • + a( s 1 s -1 V s • b s +1 s |a| ) + • • • + a( s 1 s -1 V s s +1 s |a| • b ) -a( s 1 • b s -1 V s s +1 s |a| ) -• • • -a( s 1 s -1 V s • b s +1 s |a| ) -• • • -a( s 1 s -1 V s s +1 s |a| • b ) = b∈G 0 ∈[2 |a|] a( s 1 s -1 V s • b s +1 s |a| ) -a( s 1 s -1 V s • b s +1 s |a| ) = b∈G 0 ∈[2 |a|] a( s 1 s -1 V s • b -V s • b s +1 s |a| ) (2.3.6)
By induction hypothesis, we get b∈G 0

V s • b -V s • b = (V U -UV ) s = s = φ s (2.3.7)
We now obtain from (2.3.6), (2.3.7), and (2.3.2c) that

(t) = ∈[2 |a|] a( s 1 s -1 φ s s +1 s |a| ) = ∈[2 |a|] (#G)nfl s a( s 1 s -1 s s +1 s |a| ) = (#G)nfl(t) t (2.3.8)
Therefore, (t) = (#G)nfl(t) t establishing the statement of theorem.

Figure 3 shows an example of a pair of φ-diagonal dual graded graphs.

Bracket tree.

As already noticed before, when G = G(2) = {a} the graph (S • (G) V) is a tree. Moreover, (S • (G) U V) is a pair of dual graded graphs isomorphic to the pair consisting in the finite order ideals of the infinite binary tree and the Bracket tree, known from [Fom94] (see also [START_REF] Hivert | The Algebra of Binary Search Trees[END_REF]). One can see Theorem 2.3.1 as a generalization of this prototypical instance for the present case of G-trees and φ-diagonal duality.

P

We present here a combinatorial study of the posets of the G-prefix graphs. In particular we look at their lattice properties, the structure of their intervals, enumerate the trees in a given interval, and enumerate all intervals with respect to the degrees of theirs bounds.

3.1. Posets and their intervals. We begin by describing the order relation and covering relation of the posets of G-prefix graphs. We prove that any interval of these posets are distributive lattices Proof. Assume that s p t. By definition of the G-prefix poset, there exist an integer 0, letters a 1 , . . . , a of G, and positive integers 1 , . . . , such that t = ( ((s

• 1 a 1 ) • 2 a 2 ) ) • a (3.1.1)
It follows straightforwardly by induction on that there exist G-trees r 1 , . . . , r |s| such that t = s • r 1 r |s| Therefore, s is a prefix of t.

Conversely, assume that s is a prefix of t. Hence, there exist G-trees r 1 , . . . , r |s| such that t = s • r 1 r |s| By (1.3.4),

t = s • |s| r |s| • |s|-1 r |s|-1 • 1 r 1 (3.1.2)
and, by expressing now each tree r , ∈ [|s|], by means of partial compositions involving letters of G, and by arranging this expression so that it becomes bracketed from the left to the right by using Relation (1.3.2a), one obtains an expression of the same form as (3.1.1) for t. Therefore, s p t.

The second part of the statement is a direct consequence of the fact that the adjoint map U of the map U of the G-prefix graph satisfies (2.1.2).

Distributive lattices.

Let G be a finite alphabet. Let ∧ be the binary operation on S • (G), called intersection, defined recursively by By seeing G-trees as terms, the term encoded by t ∨ t is in fact, if it exists, the unification of the terms encoded by the G-trees t and t (see [START_REF] Baader | Term rewriting and all that[END_REF][START_REF]Term Rewriting Systems[END_REF]).

t ∧ := =: ∧ t (3.1.
Proposition 3.1.5. For any finite alphabet G, the G-prefix poset is a meet-semilattice for the operation ∧. Moreover, each interval [s t] of this poset is a distributive lattice for the operations ∧ and ∨.

Proof. Lemma 3.1.3 says that the G-prefix poset is a meet-semilattice for the operation ∧. Moreover, by Lemma 3.1.4, the operation ∨ is well-defined for any pair of elements of the interval I := [s t] since t is an upper bound of any pair of trees of I. Hence, I is a join-semilattice and thus also a lattice for the operations ∧ and ∨.

Let us now prove that I is a distributive lattice. We proceed by structural induction on the three G-trees r 1 , r 2 , and r 3 of I to show that α r 1 r 2 r 3 = β r 1 r 2 r 3 where α r 1 r 2 r 3 := r 1 ∧(r 2 ∨ r 3 ) and β r 1 r 2 r 3 := (r 1 ∧ r 2 ) ∨(r 1 ∧ r 3 ) First, we have

α r 2 r 3 = ∧(r 2 ∨ r 3 ) = (3.1.10) and β r 2 r 3 = ( ∧ r 2 ) ∨( ∧ r 3 ) = ∨ = (3.1.11)
Second, we have

α r 1 r 3 = r 1 ∧( ∨ r 3 ) = r 1 ∧ r 3 (3.1.12) and β r 1 r 3 = (r 1 ∧ ) ∨(r 1 ∧ r 3 ) = ∨(r 1 ∧ r 3 ) = r 1 ∧ r 3 (3.1.13)
Similarly, the relation α r 1 r 2 = r 1 ∧ r 2 = β r 1 r 2 holds. We can now assume that r 1 , r 2 , and r 3 are different from the leaf. Moreover, since r 1 p t, r 2 p t, and r 3 p t, the roots of r 1 , r 2 , and r 3 are decorated by the same letter a of G. Therefore,

α r 1 r 2 r 3 = r 1 ∧ a( r 2 (1) ∨ r 3 (1) r 2 (|a|) ∨ r 3 (|a|) ) = a( r 1 (1) ∧(r 2 (1) ∨ r 3 (1)) r 1 (|a|) ∧(r 2 (|a|) ∨ r 3 (|a|)) ) = a( α r 1 (1) r 2 (1) r 3 (1) α r 1 (|a|) r 2 (|a|) r 3 (|a|) ) (3.1.14) and β r 1 r 2 r 3 = a( r 1 (1) ∧ r 2 (1) r 1 (|a|) ∧ r 2 (|a|) ) ∨ a( r 1 (1) ∧ r 3 (1) r 1 (|a|) ∧ r 3 (|a|) ) = a( (r 1 (1) ∧ r 2 (1)) ∨(r 1 (1) ∧ r 3 (1)) (r 1 (|a|) ∧ r 2 (|a|)) ∨(r 1 (|a|) ∧ r 3 (|a|)) ) = a( β r 1 (1) r 2 (1) r 3 (1) β r 1 (|a|) r 2 (|a|) r 3 (|a|) ) (3.1.15)
By induction hypothesis, the relation α r 1 r 2 r 3 = β r 1 r 2 r 3 follows.

Structure of the intervals.

A G-tree t is stringy if any internal node of t has at most one child which is an internal node. A G-tree t is co-irreducible in S • (G) p if t covers at most one element.

Proposition 3.1.6. For any finite alphabet G, the set of co-irreducible elements of the G-prefix poset is the set of all stringy G-trees. Moreover, the number of such elements of degree 1 is G (1) G (1) -1 where G is the derivative of G ( ) with respect to .

Proof. We use here Proposition 3.1.2 and its description of the covering relation U of the G-prefix poset in terms of deletion of maximal nodes. First, if t is a stringy G-tree different from the leaf, by definition of stringy trees, t admits exactly one maximal internal node . Therefore, del (t) is the only tree covered by t. Conversely, if t covers exactly one G-tree t , then t has only one maximal internal node. This implies that t is stringy. This establishes the first part of the statement.

By definition, a stringy G-tree t decomposes as

t = a 1 • 1 (a 2 • -2 ( (a -1 • -1 a ) )) (3.1.16)
where (a 1 a ) is a sequence of elements of G and ( 1 -1 ) is a sequence of indices satisfying ∈ |a | for any ∈ [ -1]. This tree t is moreover entirely specified by these two sequences. For this reason, by denoting by θ( ) the number of stringy G-trees of degree 0, we have

θ( ) = (a1 a )∈G |a 1 | |a -1 | = a∈G |a| -1 (#G) = G (1) -1 G (1) (3.1.17)
This shows the second part of the statement.

Here are the sequences of the first numbers of stringy G-trees: between respectively an interval of S • (G) p and an interval of S • (G ♦ 5 ) p .

A shadow is defined recursively as being a (possibly empty) finite multiset 1 of shadows. A shadow encodes hence a nonplanar undecorated rooted tree. For any G-tree t different from the leaf, we construct the shadow sh(t) recursively by sh(t) := sh(t( )

) : ∈ [ ] and t( ) = (3.1.21)
where is the arity of the root of t. For instance, sh

     a a c e c a      = ∅ ∅ ∅ ∅ = (3.1.22)
Given a shadow , the poset induced by is the poset P( ) on its set of nodes different from the root wherein a node is smaller than a node if is an ancestor of . In other words, P( ) is the poset having as Hasse diagram the nonplanar rooted tree without its root. Besides, we say that a poset ( ) is a forest poset if and imply or for all ∈ . Observe that any poset induced by a shadow is a forest poset and conversely, for any forest poset , there is a shadow such that and P( ) are isomorphic.

For any poset ( ), let (J( ) ∧ ∨) be the lattice wherein J( ) := {X ⊆ : ∈ X and ∈ and imply ∈ X} (3.1.23) and the operation ∧ (resp. ∨) is the intersection (resp. the union) of the sets. In other words, J( ) is the set of all order ideals of ordered by inclusion. The Fundamental theorem for distributive lattices (see [START_REF] Stanley | Enumerative Combinatorics[END_REF]) states that for any finite distributive lattice , there exists a unique finite poset such that and J( ) are isomorphic as lattices. An element of a finite lattice is join-irreducible if covers exactly one element. It is known that the set of all join-irreducible elements of J( ) forms a subposet of J( ) which is isomorphic as a poset to . Lemma 3.1.8. Let be a shadow. The set of join-irreducible elements of the lattice J(P( )) is the set of the nonempty saturated chains of P( ).

Proof. Let us denote by

the covering relation of the poset P( ). First, ∅ is not a joinirreducible element of J(P( )) since ∅ covers no elements. Any nonempty saturated chain

1 • • • -1 of P( ) covers exactly the chain 1 • • •
-1 so that any nonempty saturated chain is join-irreducible. Finally, if X is an element of J(P( )) which is not a chain, there are ∈ X such that and are incomparable in P( ). Since P( ) is a forest poset, we can assume that and are maximal elements of X. Hence, X covers the elements X \ { } and X \ { } of J(P( )). This shows that X is not join-irreducible and establishes the statement of the lemma. Lemma 3.1.9. For any finite alphabet G and any G-trees r 1 , . . . , r , the set of joinirreducible elements of the lattice [c(♦ ) ♦ ( r 1 r )] is the set of all G ♦ -trees of the form c(♦ ) • r where ∈ [ ] and r is a stringy tree, different from the leaf, and a prefix of r .

Proof. We use here Proposition 3.1.2 and its descriptions of the order relation p and of the covering relation U of the G-prefix poset respectively in terms of prefixes of G-trees and of deletion of maximal nodes. Let t := c(♦ ) • r . Since r is stringy, t also is. For this reason, t covers at most one element in [c(♦ ) ♦ ( r 1 r )] Moreover, due to the fact that r is by hypothesis different from the leaf, there is a G-tree r , a ∈ [|r |], and a letter a ∈ G such that r = r • a. Now, by using Relation (1.3.2a) satisfied by the partial composition maps of S • (G ♦ ), we have

t = c(♦ ) • r = c(♦ ) • r • a = c(♦ ) • r • + -1 a (3.1.24)
This shows that t covers only c(♦ ) • r . It remains to show that when t is a tree different from the description of the statement of the lemma, t covers zero or two or more elements. First, if t = c(♦ ), t covers no elements. Second, if t = c(♦ )• r where r is not stringy, there are at least two maximal internal nodes in r . By removing one of these internal nodes, one obtains at least two different trees r 1 and r 2 covered by r . Thus, c(♦ )• r 1 and c(♦ )• r 2 are both covered by t. Finally, it remains to consider the case where t = c(♦ ) • [r 1 r ] where r 1 , . . . , r are G-trees such that for any ∈ [ ], r p r , and there are at least two indices

∈ [ ] such that = , r = , and r = . By Lemma 3.1.1, t ∈ [c(♦ ) ♦ ( r 1 r )] These assumptions on t lead to the fact that t is covered by two different trees, respectively obtained by replacing r (resp. r ) by any tree covered by r (resp. r ). All this establishes the statement of the lemma. Proposition 3.1.10. For any finite alphabet G and any G-trees s, t such that s p t, the interval [s t] of S • (G) p is isomorphic as a lattice to J(P( )) where := sh ♦ |s| ( t \ s ) .

Proof. By Proposition 3.1.7, the interval [s t] is isomorphic as a poset to the interval c ♦ |s| ♦ |s| ( r 1 r |s| ) where r 1 r |s| is the G-forest t \ s. Therefore, the statement of the proposition is equivalent to saying that

c ♦ |s| ♦ |s| ( r 1 r |s| ) J P sh ♦ |s| ( r 1 r |s| ) (3.1.25)
By Lemmas 3.1.8 and 3.1.9, the respective sets of join-irreducible elements of the two lattices J P sh ♦ |s| ( r 1 r |s| ) and c ♦ |s| ♦ |s| ( r 1 r |s| ) are in one-to-one correspondence. They also preserves the ordering so that these two subposets are isomorphic as posets. Now, since by Proposition 3.1.5, c ♦ |s| ♦ |s| ( r 1 r |s| ) is a finite distributive lattice, by the Fundamental theorem for finite distributive lattices, the statement of the proposition follows.

Theorem 3.1.11. For any finite alphabet G and any G-trees s, t, s , and t such that s p t and s p t , the intervals [s t] and [s t ] of S • (G) p are isomorphic as posets if and only if

sh ♦ |s| ( t \ s ) = sh ♦ |s | ( t \ s ) (3.1.26)
Proof. Proposition 3.1.10 brings a one-to-one correspondence between shadows and intervals of S • (G) p up to lattice isomorphism. This is equivalent to the statement of the theorem.

For instance, by considering the same alphabet G as in the previous example, Theorem 3.1.11 says that since sh

     ♦ 3 ( e a a c e \ c e )      = = sh      ♦ 2 (

Enumerative properties.

We end the study of the G-prefix posets by describing a way to count the elements of a given interval and by enumerating all its intervals with respect to the degrees of their minimal and maximal elements.

3.2.1. Cardinalities of intervals. The load ld( ) of a shadow := 1 is the integer ld( ) recursively defined by ld( 1) :=

∈[ ] (1 + ld( )) (3.2.1)
For instance, the load of the shadow appearing in (3.1.22) is 20. Indeed, by labeling each node of by the load of the subtree of rooted at , we have

1 1 1 1 4 20 (3.2.2)
Proposition 3.2.1. For any finite alphabet G and any G-trees s and t such that

s p t, in S • (G) p , #[s t] = ld sh ♦ |s| ( t \ s ) (3.2.3) Proof. Let θ(t) := #[ t]. By Proposition 3.1.2, θ(t)
is the number of prefixes of t. By Lemma 3.1.1, any prefix r of t is either the leaf, or when t is not the leaf, the roots of r and t have the same label a ∈ G and each r( ) is a prefix of t( ) for all ∈ [|a|]. Hence,

θ(t) = 1 + ∈[|a|] θ(t( )) (3.2.4)
Moreover, by definition of the maps sh and ld, we have

ld(sh(♦ 1 ( t \ ))) = ld(sh(♦ 1 • 1 t)) = θ(t
S • (G) ( ) = 1 + G S • (G) ( ) - G S • (G) ( ) + G S • (G) ( ) (3.2.7)
Proof. Let [s t] be an interval of S • (G) p . By Proposition 3.1.2, s is a prefix of t. Moreover, Proposition 3.1.7 implies that this interval [s t] can be encoded as the tree obtained by marking in t the common internal nodes between s and t. Since s is a prefix of t, if a node different from the root is marked, its father is also marked. Now, let F( ) and G( ) be the two series satisfying

F( ) = G( ) + a∈G F( ) |a| (3.2.8a) G( ) = 1 + a∈G G( ) |a| (3.2.8b)
The series G( ) enumerates the G-trees with respect to their degree by the parameter , and due to the previous description of the encoding of intervals, F( ) enumerates the marked trees with respect to their degree by the parameter and their number of marked nodes by the parameter . Now, by bringing in play the series G ( ), these two series express as For instance, when G consists in one binary letter, G ( ) = 2 and S • (G) ( ) satisfies

F( ) = G( ) + G (F( )) (3.2.9a) G( ) = 1 + G (G( )) (3.2.9b) This implies that F( ) = 1 + G (G( )) + G (F( )) (3.2.10a) G( ) = F( ) - G (F( )) (3.2.
1-S • (G) ( )+ S • (G) ( ) 2 + S • (G) ( ) 2 -2 2 S • (G) ( ) 3 + 2 3 S • (G) ( ) 4 = 0 (3.2.11)
and S • (G) ( ) = 1 + (1 + ) + 2 1 + + 2 2 + 5 + 6 + 5 2 + 5 3 3 + 2 7 + 10 + 9 2 + 7 3 + 7 4 4 + 14 3 + 5 + 5 2 + 4 3 + 3 4 + 3 5 5 + • • • (3.2.12)

The coefficients of S • (G) (1 ) are 1 2 6 21 80 322 1348 5814 (3.2.13) and form Sequence A121988 of [Slo], enumerating the vertices of the multiplihedra, which form a sequence of posets [START_REF] Stasheff | H-spaces from a homotopy point of view[END_REF].

G

The aim of this section is to extend the previous definitions of G-prefix graded graphs and G-twisted prefix graded graphs so that vertices of the graphs can be any combinatorial objects endowed with the structure of an operad subjected to some conditions. This generalization, applied on free operads -that are operad of G-trees endowed with the partial composition of trees-gives back the previous graded graphs. As we shall see, the pairs of graded graphs thus obtained are not always φ-diagonal dual. We end this section by presenting some examples of such pairs of graded graphs. 4.1. Prefix and twisted prefix graded graphs. We start by introducing the notion of homogeneous and finitely generated operad. We then describe the construction of a pair of graded graphs from any homogeneous and finitely generated operad. Proof. This follows from the following algorithm to compute a minimal set G of generators of up to a given arity. First, since (0) = ∅ and (1) = {1}, then G(1) = ∅. Now, assume that there is an 1 such that we know the sets G( ) for all ∈ [ ]. A candidate for G( + 1) is the set ( + 1) \ G where G is the graded set consisting exactly in the elements of G up to arity . In other terms, this candidate for G( + 1) contains the elements of arity + 1 of which cannot be obtained by composing elements of arity of G. The fact that G(1) = ∅ ensures that the arity of any partial composition • where ∈ and ∈ G (resp.

∈ G and ∈ ) is greater than the arity of (resp. ). For this reason, the set G( + 1) is unique, so that the given candidate for this set is the only possible one. Finally, since by construction G is minimal, the statement of lemma follows.

By Lemma 4.1.1, we shall denote by G the unique minimal generating set of any operad satisfying (0) = ∅ and (1) = {1}. Moreover, given the alphabet G , there is a unique operad congruence ≡ such that S (G )/ ≡ Indeed, ≡ satisfies necessarily t ≡ t for all t t ∈ S (G ) such that ev(t) = ev(t ). For this reason, admits (G ≡ ) as unique presentation. These properties arising from the fact that (0) = ∅ and (1) = {1} are consequences of the previous lemma, used implicitly in the sequel.

Let be an operad such that (0) = ∅ and (1) = {1}. If the presentation (G ≡ ) of is such that for any t t ∈ S (G ), t ≡ t implies deg(t) = deg(t ), then is homogeneous. Besides, if G is finite, then is finitely generated. In the sequel, we shall mainly consider homogeneous and finitely generated operads.

Given an homogeneous operad , the degree deg( ) of ∈ is the degree of a treelike expression of on G . Observe that since is homogeneous, if admits two treelike expressions t and t , we necessarily have deg(t) = deg(t ) so that deg( ) is well-defined. Moreover, we denote by • the graded set wherein for any 0, • ( ) is the set of all elements of having as degree. Remark that if is finitely generated, since is by definition a quotient of S (G ), and since S • (G ) is combinatorial, • is also combinatorial.

= ( ((1 • 1 a 1 ) • 2 a 2 ) ) • a (4.1.2)
where 0, a 1 a ∈ G , and 1 2 ∈ N, there is at least a path from 1 to in ( • U). Hence, this graded graph admits as root. Finally, since all coefficients of U( ) are obviously nonnegative, the statement of the proposition is established.

Observe that when is free, then S (G ), and ( • U) and (S • (G ) U) coincide as graded graphs. where V : K • → K • is the linear map defined recursively by

V ( ) := a∈G a • 1 +        b∈G 1 |b| ∈ =b•[ 1 |b| ] ∈[2 |b|] b • 1 -1 V +1 |b|        (4.1.4)
In words, this says that ∈ • appears in V( ) if there is a treelike expression t on G of and a treelike expression t on G of such that t appears in V(t ), where this last occurrence of V is the linear map of the G -twisted prefix graph (S • (G ) V) (see Section 2.2.1). We call ( • V) the twisted prefix graph of . Proposition 4.1.3. Let be an homogeneous and finitely generated operad. The twisted prefix graph of is a simple rooted graded graph.

Proof. Since is finitely generated, G is finite and thus, the sum appearing in (4.1.4) is finite. Therefore, (S • (G ) V) is a well-defined graded graph. Let ∈ • such that appears in V( ). Then, there are s ∈ G ( ), t ∈ G ( ) such that t appears in V(s). Since G -twisted prefix graphs are ranked by the degrees of the G -trees, we have deg(t) = deg(s) + 1. Therefore, and since is homogeneous so that each element of • as a welldefined degree, deg( ) = deg( )+1. Hence, V sends any element of • of degree 0 to a sum of elements of degrees +1. This implies that ( • V) is a graded graph. Moreover, as noticed in Section 2.2.1, for each G -tree t different from the leaf, V (t) = 0. This implies that for any G -tree s different from the leaf, there is a G -tree t such that s appears in V(t). For this reason, for any ∈ • such that = 1, there is an ∈ • such that V( ) = . Therefore, and because 1 is the only element of of degree 0, ( • V) admits 1 as root. Finally, directly by definition, all coefficients of V( ) are 0 or 1. This establishes the statement of the proposition.

Observe that when is free, ( • V) and (S • (G ) V) coincide as graded graphs. Besides, when is an homogeneous and finitely generated operad, by Propositions 4.1.2 and 4.1.3, the two graded graphs ( • U) and ( • V) are both ranked by the degrees of their elements. Hence, ( • U V) is a pair of graded graphs. Proof. By Proposition 4.1.2, this construction produces from an homogeneous and finitely presented operad a well-defined poset • p . It remains to prove that this construction sends operad morphisms to poset morphisms and preserves their injectivity and surjectivity. For this, let and be two homogeneous and finitely presented operads, and ψ : → be an operad morphism. Let also ∈ • and assume that p . By Proposition 4.2.1, there are s ∈ G ( ) and t ∈ G ( ) such that s p t. By the universality property of free operads (See Section 1.3.2), the map ψ is entirely specified by the map : G → satisfying (a) = ψ(a) for all a ∈ G . Let ¯ : G → S (G ) be a map sending any a ∈ G to a treelike expression on G of (a). Let also s (resp. t ) be the G -tree obtained by replacing each internal node a ∈ G of s (resp. t) by ¯ (a). By construction, we have ev(s ) = ψ( ) and ev(t ) = ψ( ). Moreover, since s p t, by Proposition 3.1.2, s is a prefix of t. This implies by construction of s and t that s p t . Hence, by Proposition 4.2.1, we have ψ( ) p ψ( ). Therefore, ψ is a poset morphism. Finally, injections and surjections are preserved since operad morphisms are sent to poset morphisms without any change.

As a consequence of Theorem 4.2.3, if is an homogeneous and finitely generated operad, then the operad surjection ev : S (G ) → is a surjective poset morphism from S • (G ) p to • p .

4.3.

Examples. Before ending this paper, we consider here some examples of pairs of graded graphs constructed from some homogeneous and finitely generated operads. Some of these pairs of graded graphs are φ-diagonal dual and some other not. Most of the considered operads arise in a combinatorial context.

( 2 ) • 1 c( 2 ) ≡ As c( 2 ) • 2 c( 2 ) (4.3.2)
Therefore, As is homogeneous and finitely presented.

The pair (As • U V) of graded graphs satisfies U( ) = +1 and V( ) = +1 for any 1 (see Figure 4). This very elementary example of pair of graded graphs is dual and for any ∈ N (see Figure 5). This pair of graded graphs is not φ-diagonal dual since for instance, (V U -UV )(10) = 3 (10) + 2 (01) Nevertheless, we have the following property. Observe that these relations describe respectively the treelike expressions for the elements 000, 001, 011, and 010 of Comp. Therefore, Comp is homogeneous and finitely generated.

Observe that these relations describe respectively the treelike expressions for the elements 000, 0010, 0100, and 01010 of Motz. Therefore, Motz is homogeneous and finitely generated. Observe moreover that, since the generator 010 is ternary, Motz is not a binary operad.

The pair of graded graphs (Motz • U V) satisfies for any ∈ Motz (see Figure 7). for any ∈ Motz.

Proof. By a straightforward computation, by using (4.3.17 where the factors to collapse are framed. Observe also that the prefix poset of Motz is not a meet-semilattice since 00 p 0010, 00 p 0100, 010 p 0010, 010 p 0100, 00 and 010 are incomparable, and 0010 and 0100 are incomparable.

We do not have a concise combinatorial description for these hook coefficients.

P

We finish this work by presenting three open questions and research directions.

As seen in Section 4.3, the pair of graded graphs associated with the operads As, Comp, Motz, and FCat , 0, are φ-diagonal dual, while the pair of graded graphs of Dias is not. By computer exploration, we conjecture that some classical operads appearing in the literature have also this property of φ-diagonal duality for their pair of graded graphs. This is the case for the 2-associative operad 2As [LR06], for the operad As 2 [Dot09], for the dipterous operad Dip [LR03], and for the duplicial operad Dup [START_REF] Loday | Generalized Bialgebras and Triples of Operads[END_REF]. The first question is to obtain in general a necessary and sufficient condition for an homogeneous and finitely presented operad for the φ-diagonal duality of its pair of graded graphs ( • U V). Ideally, this condition should relate to the presentation of .

The second question concerns applications of φ-diagonal duality to enumerative problems. We propose to understand to what extent this generalized version of graph duality helps to obtain enumerative formulas. Recall that classical graph duality [Fom94] leads, from the identity V U = U V + U -1 , 0, to a proof of (0.0.1) relating numbers of standard Young tableaux and numbers of permutations. A starting point is to use Proposition 1.1.3 and the Relation (1.1.19), which is a generalization of the previous identity, in order to relate other families of combinatorial objects in a similar way.

A last research direction consists in, rather than considering operads to construct graded graphs, use operad to construct trees. Roughly speaking, a tree can be built from a graded graph by deleting some of its edges. To obtain such a tree, we can consider a variant of the map U (see (4.1.1)) wherein the apparitions of certain terms are forbidden. This could be achieved by the use of colored operads [Yau16] since the partial composition maps of these structures is restricted due to the use of colors. A similar mechanism is used in [START_REF] Giraudo | Colored operads, series on colored operads, and combinatorial generating systems[END_REF] wherein graphs of some colored versions of combinatorial objects are built. The main interest to search for trees instead of graded graphs relies on the fact that trees can be thought as generating trees. These structures can be used to design efficient algorithms for the exhaustive generation of the objects or for random generation. The aim is to build a framework leading to such generating trees from any family of combinatorial objects endowed with the structure of a homogeneous and finitely presented operad.

Introduction 1 .

 1 Graded graphs, trees, and operads 1.1. Graded graphs and diagonal duality 1.2. Syntax trees 1.3. Nonsymmetric operads 2. Graded graphs of syntax trees 2.1. Prefix graded graphs 2.2. Twisted prefix graded graphs 2.3. Diagonal duality 3. Posets of syntax trees 3.1. Posets and their intervals 3.2. Enumerative properties 4. Graded graphs from operads 4.1. Prefix and twisted prefix graded graphs 4

  shows the Young graded graph Y. The poset of Y is the 0 F . The Young graded graph up to integer partitions of size 4.

  For instance, if G := G(2) G(3) with G(2) := {a b} and G(3) := {c},

  G = and G is minimal with respect to the inclusion among the subsets of G satisfying this property, G is a minimal generating set of and its elements are generators of . An operad congruence of is an equivalence relation ≡ respecting the arities and such that, for any ∈ , ≡ and≡ implies • ≡ • for any ∈ [| |].The ≡-equivalence class of any ∈ is denoted by [ ] ≡ . Given an operad congruence ≡, the quotient operad / ≡ is the operad on the set of all ≡-equivalence classes and defined in the usual way. 1.3.2. Free operads. Let G be an alphabet. The free operad on G is the operad defined on the graded set S (G) wherein the partial compositions • are the partial compositions of G-trees. By considering the previous graded set G of Section 1.2.1, one has, as an example of a full composition in S (G),

  G = {a} with |a| = 2 up to degree 3. G = {e c} with |e| = 1 and |c| = 3 up to degree 2 and with some trees of degree 3.F. Two graded graphs (S•(G) U).

  1 1 2 6 24 120 720 5040 for G = {a} with |a| = 2 (2.1.13a) 1 1 3 15 105 945 10395 135135 for G = {c} with |c| = 3 (2.1.13b) 1 2 8 48 384 3840 46080 645120 for G = {a b} with |a| = |b| = 2 (2.1.13c) 1 2 10 82 938 13778 247210 5240338 for G = {a c} with |a| = 2 |c| = 3 (2.1.13d)

  2.1c)for any a ∈ G and any G-trees s, s 1 , . . . , s |a| such that there is at least a ∈ [2 |a|] such that s = . For instance, for G = {e a c} where |e| = 1, |a| = 2, and |c| = 3, one has V

  2.9b)for any b ∈ G and any G-trees s 1 , . . . , s |b| . For instance, by considering the same alphabet G as in the previous example, one has for instance

  us define the non-first leaves statistics t nfl(t) by setting nfl(t) = # nf (t). Immediately from the definition of non-first leaves, this statistics on S(G) satisfies the recurrence nfl

F.

  The pair (S • (G) U V) of φ-diagonal dual graded graphs where G := {a c} with |a| = 2 and |c| = 3. 3.1.1. Prefix posets. Let G be a finite alphabet. The G-prefix poset is the poset S • (G) p of (S • (G) U).

  for G = {a b} with |a| = |b| = 2 (3.1.18c) 1 2 10 50 250 1250 6250 31250 for G = {a c} with |a| = 2 |c| = 3 (3.1.18d)A G-forest is a nonempty word of G-trees. The length of a G-forest is the number of trees it contains. If s p t, the difference between t and s is the G-forest t \ s := (r 1 r |s| ) such that r 1 , . . . , r |s| are the unique G-trees such that t = s • r 1 r |s| Moreover, from any G-forest (r 1 r ), we denote by ♦ ( r 1 r ) the G ♦ -tree obtained by grafting the G-trees r 1 , . . . , r to a root decorated by the letter ♦ of arity , where G ♦ is the alphabet G {♦ }.For instance, by considering the same alphabet G as in the previous examples, Proposition 3.1.7 says that one has the isomorphism 

  these two intervals of S • (G) p .

  10b) and since by construction S • (G) ( ) = F( ) the stated relation for S • (G) ( ) follows.

4.1. 1 .

 1 Homogeneous operads and degrees. Let us begin by an elementary result on the minimal generating sets of operads satisfying some conditions. Lemma 4.1.1. If is an operad such that (0) = ∅ and (1) = {1}, then admits a unique minimal generating set.

4.1. 3 .

 3 Twisted prefix graded graphs. For any homogeneous and finitely generated operad , let ( • V) be the graded graph wherein, for any ∈ • , V( ) := ch Supp V ( ) (4.1.3)

4.3. 1 .

 1 Associative operad. The associative operad As is the operad wherein As( ) := { } for all 1, and • := + -1 for all 1, 1, and ∈ [ ]. This operad admits the presentation (G As ≡ As ) where G As := { 2 } (4.3.1) and ≡ As is the smallest operad congruence of S (G As ) satisfying c

  graph (As• U).

  graph (As• V).

F.

  The pair (As• U V) of graded graphs.is known as the chain in[Fom94]. The hook series of (As • U) satisfies Diassociative operad. The diassociative operad Dias is the operad wherein Dias( ) is the set of all words of length 1 on the alphabet {0 1} having exactly one occurrence of 0. The partial composition • of two such words and consists in replacing the -th letter of by , where is the word obtained from by replacing all its letters by max{ }. This operad has been introduced in[START_REF] Loday | Dialgebras. In Dialgebras and related operads[END_REF] under a slightly different form (see also[START_REF] Chapoton | On some anticyclic operads[END_REF][START_REF] Giraudo | Pluriassociative algebras I: The pluriassociative operad[END_REF]). This operad admits the presentation (G Dias ≡ Dias ) whereGDias = {01 10} (4.3.4) and ≡ Dias is the smallest operad congruence of S (G Dias ) satisfying c(01) • 1 c(01) ≡ Dias c(01) • 2 c(01) ≡ Dias c(01) • 2 c(10) (4.3.5a) c(01) • 1 c(10) ≡ Dias c(10) • 2 c(01) (4.3.5b) c(10) • 1 c(01) ≡ Dias c(10) • 1 c(10) ≡ Dias c(10) • 2 c(10) (4.3.5c)Observe that these relations describe respectively the treelike expressions for the elements 011, 101, and 110 of Dias. Therefore, Dias is homogeneous and finitely generated.The pair of graded graphs (Dias • U V) satisfies

  graph (Dias• V) up to elements of degree 4.F . The pair (Dias• U V) of graded graphs. Proposition 4.3.1. The graded graph (Dias • U) is φ-diagonal self-dual for the linear map φ : K Dias • → K Dias • satisfying φ 1 01 = ([ = 0] + [ = 0] + 8By a straightforward computation, by using (4.3.6), we can show that the relation (U U -UU ) 1 01 = φ 1 01 holds for all 0, establishing the statement of the proposition. The hook series of (Dias • U) satisfies h U = (0) + (01) + (10) + 3 (011) + 2 (101) + 3 (110) + 15 (0111) + 9 (1011) + 9 (1101) + 15 (1110) + 105 (01111) + 60 (10111) + 54 (11011) + 60 (11101) + 105 (11110) + • • • (4.3.9) These coefficients form Triangle A059366 of [Slo]. 4.3.3. Operad of integer compositions. The operad of integer compositions Comp is the operad wherein Comp( ) is the set of all words of length 1 on the alphabet {0 1} beginning by 0. The partial composition • of two such words and consists in replacing the -th letter of by if = 0 and by ¯ if = 1 where ¯ is the one complement of . This operad has been introduced in [Gir15] and admits the presentation G Comp ≡ Comp where G Comp = {00 01} (4.3.10) and ≡ Comp is the smallest operad congruence of S G Comp satisfying c(00) • 1 c(00) ≡ Comp c(00) • 2 c(00) (4.3.11a) c(01) • 1 c(00) ≡ Comp c(00) • 2 c(01) (4.3.11b) c(01) • 1 c(01) ≡ Comp c(01) • 2 c(00) (4.3.11c) c(00) • 1 c(01) ≡ Comp c(01) • 2 c(01) (4.3.11d)

Proposition 4.3. 3 .

 3 The pair (Motz • U V) of graded graphs is φ-diagonal dual for the linear map φ :K Motz • → K Motz • satisfying φ( ) = (2 + #{ ∈ [| | -1] : = +1 }) (4.3.19)

  ) and (4.3.18), we can infer the relation (V U -UV )( ) = φ( ) for all ∈ Motz, establishing the statement of the proposition.The hook series of (Motz • U) satisfies h U = (0) + (00) + 2 (000) + (010) + 6 (0000) + 2 (0010) + 2 (0100) + (0110) + 6 (00010) + 6 (00100) + 3 (00110) + 6 (01000) + 2 (01010) + 3 (01100) + 2 (01110) + (01210) + 6 (001010) + 3 (001210) + 6 (010010) + 6 (010100) + 3 (010110) + 3 (011010) + 2 (011210) + 3 (012100) + 2 (012110) + (012210) + 6 (0101010) + 3 (0101210) + 3 (0121010) + 2 (0121210) + (0123210) + • • • (4.3.20)We do not have a concise combinatorial description for these hook coefficients.Besides, by representing any element of Motz as a path in the quarter plane (that is, by drawing points ( -1 ) for all ∈ [| |] and by connecting all pairs of adjacent points by segments), in the prefix poset of Motz, one has p if and only if can be obtained from by collapsing into points some factors of that are Motzkin paths. For instance,

  or is an ancestor of but is not in the first subtree of , or is in the first subtree of . For instance, by considering the same alphabet G as in the previous examples, in the twisted poset induced by the G-tree ∈ G and any G-trees s 1 , . . . , s |a| . For instance, by considering the G-tree t defined in (2.2.13), one has h (t) = 4. For any alphabet G and any G-tree t, the number of linear extensions of the poset P (t) is h (t).

	for any a Lemma 2.2.2.
								:=
	( • (t) ) wherein for any		∈ • (t), one has	if = , or =	where	2
	and	is any word of integers, or = 1 where	is any word of integers. In other
	words, this says that one has	a if = , t := c e	c c	e	a	(2.2.13)
							a
	we have 11 1	, 12	, 1 12,	2,	3,	31,	311, and 311 31 3.
	For any G tree t, let the statistics t	h (t) satisfying the recurrence relation
						h () = 1	(2.2.14a)
			h a( s 1		s |a| ) = deg(s 2 )	deg s |a| !	h (s )	(2.2.14b)
								∈[|a|]

2.2.2. Path enumeration.

The twisted poset induced by a G-tree t is the poset P (t)

  of, respectively, P (s 2 ), . . . , P s |a| . Moreover, again by definition of , for any ∈ [2 |a|], ∈ • s , and ∈ • s , if = then the nodes and of t are incomparable in P (t). Thus, by (2.1.6), P a( s 2 s |a| ) has deg(s 2 ) deg s |a| ! linear extensions. Finally, since each P (s ), ∈ [|a|], has by induction hypothesis h (s ) linear extensions, it follows from (2.2.14b) that P (t) admits h (t) linear extensions. By Lemma 2.2.2, and in pursuit of the previous example, the G-tree defined in (2.2.13) has four linear extensions. The four permutations encoding these are

	(11 1 12 2 311 31 3)	(2.2.16a)
	(11 1 12 311 2 31 3)	(2.2.16b)
	(11 1 12 311 31 2 3)	(2.2.16c)
	(11 1 12 311 31 3 2)	(2.2.16d)

Proposition 2.2.3. For any finite alphabet G, the hook series of (S • (G) V) satisfies t h V = h (t) for any G-tree t.

  Besides, for any G-trees s and t, s is a prefix of t if there exist G-trees r 1 , . . . , r |s| such that t = s • r 1 r For any finite alphabet G, the order relation p of the G-prefix poset satisfies s p t if and only if the G-tree s is a prefix of the G-tree t. Moreover, the covering relation

	Proof. This follows directly from the definition of the notion of prefix just introduced.
	Proposition 3.1.2.

|s| Lemma 3.1.1. Let G be an alphabet, and s and t be two G-trees. Then, s is a prefix of t if and only if s = , or the roots of s and t are both decorated by the same letter a ∈ G, and for all ∈ [|a|], s( ) is a prefix of t( ). U of the G-prefix poset satisfies s U t for any G-trees s and t if and only if there is ∈ m • (t) such that s = del (t).

  We use here Proposition 3.1.2 and its description of the order relation p of the G-prefix poset in terms of prefixes of G-trees. Let us denote by L(t t ) the set all lower bounds of {t t }. By structural induction on t and t , we show that max p L(t t ) exists and that max {} since the leaf is the only G-tree which is a common prefix of both t and t .Hence, the statement of the lemma holds in this case. For the last case to consider, one has a = a , and it follows by induction hypothesis that [|a|], s := max p L(t t ) Now, since for any ∈ [|a|], s is a prefix of both t and t , and since all trees different from the leaf of L(t t ) have a root decorated by a, by Lemma 3.1.1, t ∧ t is a prefix of both t and t so that t ∧ t ∈ L(t t ). To show finally that t ∧ t is the greatest element of L(t t ), assume that r is a G-tree of L(t t ). First, the root of r is decorated by a. Second, since for any ∈ [|a|], r( ) is a prefix of both t and t , and since s is the greatest G-tree which is a common prefix of t and t , r( ) is a prefix of s . Therefore, by Lemma 3.1.1, this implies that r is a prefix of t ∧ t and establishes the statement of the lemma. {t} so that the statement of the lemma holds in this case. Assume now that t and t are both different from the leaf so that t = a( t 1 t |a| ) and t = a ( t 1 t |a | ) where a a ∈ G and t 1 , . . . t |a| , t 1 , . . . , t |a | are G-trees. Since {t t } admits, by hypothesis, an upper bound, both t and t have to be prefixes of a same G-tree. This implies that a = a . , and since all trees of U(t t ) have a root decorated by a, by Lemma 3.1.1 both t and t are prefixes of t ∨ t so that t ∨ t ∈ U(t t ). To show finally that t ∨ t is the least element of U(t t ), assume that r is a G-tree to U(t t ). Since for any ∈ [|a|], both t and t are prefixes of r( ), and since s is the smallest G-tree admitting both t and t as prefixes, s is a prefix of r( ). Therefore, by Lemma 3.1.1, this implies that t ∨ t is a prefix of r and establishes the statement of the lemma.

	t ∧ t = a( t 1 ∧ t 1	t |a| ∧ t |a| ) = a( s 1	s |a| )	(3.1.5)
	where for any ∈ (3.1.6b)
	and where
	a( t 1	a( t 1 c t a a( t 1 e a t a t |a| ) ∧ b( s 1 ∧ e c a a a a ∨ c	s |b| ) := = c a a = c a a a	3a) (3.1.3b) (3.1.4) (3.1.8)
	It follows by induction hypothesis that
	t ∨ t = a( t 1 ∨ t 1	t |a| ∨ t |a| ) = a( s 1	s |a| )	(3.1.9)
	where for any ∈ [|a|], s := min

|a| ) ∧ a( t 1 t |a| ) := a( t 1 ∧ t 1 t |a| ∧ t |a| ) (3.1.3c) for any a b ∈ G such that a = b, and any G-trees t, t 1 , . . . , t |a| , t 1 , . . . , t |a| , and s 1 , . . . , s |b| . From an intuitive point of view, t ∧ t is the tree obtained by considering the largest common part between the G-trees t and t starting from their roots. For instance, Lemma 3.1.3. For any finite alphabet G and any G-trees t and t , t ∧ t is greatest lower bound of {t t } in the G-prefix poset. Proof. p L(t t ) = t ∧ t . First, immediately from the definition of ∧, we have ∧ t = t ∧ = and L( t) = L(t ) = {} so that the statement of the lemma holds in this case. Assume now that t and t are both different from the leaf so that t = a( t 1 t |a| ) and t = a ( t 1 t |a | ) where a a ∈ G and t 1 , . . . t |a| , t 1 , . . . , t |a | are G-trees. If a = a , we have t ∧ t = and L(t t ) = In the same way, let ∨ be the partial binary operation on S • (G), called union, defined recursively by t ∨ := t =: ∨ t (3.1.6a) a( t 1 t |a| ) ∨ a( t 1 t |a| ) := a( t 1 ∨ t 1 t |a| ∨ t |a| ) |a| ) ∨ b( s 1 s |b| ) (3.1.7) is not defined, for any a b ∈ G such that a = b, and any G-trees t, t 1 , . . . , t |a| , t 1 , . . . , t |a| , and s 1 , . . . , s |b| . From an intuitive point of view, t ∨ t is the tree obtained by superimposing t and t . For instance, Lemma 3.1.4. For any finite alphabet G and any G-trees t and t such that {t t } admits an upper bound in the G-prefix poset, t ∨ t is well-defined and is the least upper bound of {t t }. Proof. We use here Proposition 3.1.2 and its description of the order relation p of the G-prefix poset in terms of prefixes of G-trees. Let us denote by U(t t ) the set of all upper bounds of {t t }. By structural induction on t and t , we show that min p U(t t ) exists and that min p U(t t ) = t ∨ t . First, immediately from the definition of ∨, we have ∨ t = t ∨ = t and U( t) = U(t ) = p U(t t ). Observe that the G-tree specified by (3.1.9) is well-defined by induction hypothesis. Indeed, by calling r an upper bound of {t t }, for any ∈ [|a|], r is an upper bound of {t t }. Now, since for any ∈ [|a|], both t and t are prefixes of s

  is the product of the cardinalities of [ r 1 ], . . . , r |s| where r 1 r |s| is the forest t \ s.3.2.2. Generating series of the intervals. Let us consider now the generating series

	)	(3.2.5)
	Finally, by Proposition 3.1.7, Equation (3.2.3) is a consequence of the fact the cardinality
	of [s t]

  For any finite alphabet G, the series S

	S • (G) ( ) :=	deg(s) deg(t)	(3.2.6)
	s t∈S • (G)
	s p t
	enumerating all intervals [s t] of S • (G) p with respect to the degree of s (parameter )
	and the degree of t (parameter ).
	Proposition 3.2.2.

• (G) ( ) satisfies

  4.1.2. Prefix graded graphs. For any homogeneous and finitely generated operad , let ( • U) be the graded graph wherein, for any ∈ • , In words, this says that ∈ • appears in U( ) with a coefficient λ where λ is the number of pairs (a ) ∈ G × N such that = • a. We call ( • U) the prefix graph of . As a side remark, this graph is the derivation graph of the so-called monochrome bud generating system of introduced in[START_REF] Giraudo | Colored operads, series on colored operads, and combinatorial generating systems[END_REF]. Since is finitely generated, for any ∈ • , U( ) is an • -polynomial, so that U is a well-defined map from K • to K • . Moreover, since is homogeneous, each element of has a well-defined degree. For any ∈ • , the degree of • a where ∈ [| |] and a ∈ G is deg( ) + 1. Therefore, U sends any element of • of degree 0 to a sum of elements of degrees + 1. This shows that ( • U) is a graded graph. Moreover, since by (1.3.2a), any ∈ writes as

	Proposition 4.1.2. Let be an homogeneous and finitely generated operad. The prefix
	graph of is a natural rooted graded graph.
	Proof.
	U( ) :=	• a	(4.1.1)
	a∈G
	∈[| |]

  4.2. Posets from operads.Let us study the posets of the prefix graphs of prefix graphs built from operads. 4.2.1. Prefix posets. Let be a homogeneous and finitely generated operad. The prefix poset of is the poset • p of ( • U). Observe that G is the set of the atoms of the prefix poset of . expression on G of . Moreover, by definition of the G -prefix graded graph, this is equivalent to the fact that there is a path from s to t in (S • (G ) U). Therefore, s p t.if and only if s p t where s (resp. t) is a treelike expression on G of (resp. ). By Proposition 3.1.2, this is equivalent to the fact that s is a prefix of t. Hence, we have t = s • r 1 r |s| for some G -trees r 1 , . . . , r |s| . This says that ev(t) = ev s • r 1 r |s| and, since ev is an operad morphism, that = • ev(r 1 ) ev r |s| This is, by definition of the order relation p on • , equivalent to the fact that p . The second part of the statement is a direct consequence of the definition of the map U. The construction sending any homogeneous and finitely generated operad to its prefix poset • p and sending any morphism ψ : → of homogeneous and finitely generated operads and to the same map between • and • , is a functor preserving injections and surjections from the category of homogeneous and finitely generated operads to the category of posets.

	Proof. By Proposition 4.2.1, we have
	4.2.2. Functorial construction.
	Theorem 4.2.3.
	Proposition 4.2.1. Let be an homogeneous and finitely generated operad. For any
	∈ • , we have
	Proof. By definition of the prefix poset of ,	p	is equivalent to the fact that there exist
	an integer	0, generators a 1 , . . . , a of G , and positive integers 1 , . . . , such that
		= ( (( • 1 a 1 ) • 2 a 2 ) ) • a	(4.2.1)
	Let s be any treelike expression on G of . From (4.2.1), the tree
		t := ( ((s • 1 a 1 ) • 2 a 2 ) ) • a	(4.2.2)
	is a treelike For any	∈ • , is a prefix of if there exist some elements 1 , . . . , | | of • such
	that = • 1	| |
	Proposition 4.2.2. Let be an homogeneous and finitely generated operad. The order
	relation p of the prefix poset of satisfies	p	if and only if is a prefix of for any
	∈ • . Moreover, the covering relation U of the prefix poset of satisfies

p if and only if there exist s ∈ G ( ) and t ∈ G ( ) such that s p t in the G-prefix poset S • (G) p . U for any ∈ • if and only if there is an a ∈ G and an ∈ [| |] such that = • a. p

Proposition 3.1.7. Let G be a finite alphabet, and s and t be two G-trees such that s p t. As subposets of S • (G) p , one has the poset isomorphisms

where r 1 r |s| is the G-forest t \ s.

Proof. We use here Proposition 3.1.2 and its description of the order relation p of the G-prefix poset in terms of prefixes of G-trees. Let us call the poset [ r 1 ]×

The pair of graded graphs (Comp

(4.3.12) and V( ) = 0 + 1 (4.3.13) for any ∈ Comp (see Figure 6). The poset of (Comp • U) is the composition poset 4.3.5. Operads of -trees. For any integer 0, the operad of -trees FCat is the operad wherein FCat ( ) is the set of all words of length 1 of nonnegative integers such that 1 = 0 and, for all ∈ [ -1], +1 + . The partial composition • of two words and consists in replacing the -th letter of by where is the word obtained by incrementing by all its letters. This operad has been introduced in [Gir15] and admits the presentation (G FCat ≡ FCat ) where

and ≡ FCat is the smallest operad congruence of S (G FCat ) satisfying

Observe that this relation describes the treelike expressions for the element 0 1 ( 1 + 2 ) of FCat . Therefore, FCat is homogeneous and finitely generated.

The pair of graded graphs (FCat

for any ∈ FCat (see Figure 8).

Proposition 4.3.4. For any 0, the pair (FCat • U V) of graded graphs is φ-diagonal dual for the linear map φ :

for any ∈ FCat .

Proof. By a straightforward computation, by using (4.3.24) and (4.