Olivier Bernardi

Nicolas Bonichon

Catalan's intervals and realizers of triangulations

The Stanley lattice, Tamari lattice and Kreweras lattice are three remarkable orders defined on the set of Catalan objects of a given size. These lattices are ordered by inclusion: the Stanley lattice is an extension of the Tamari lattice which is an extension of the Kreweras lattice. The Stanley order can be defined on the set of Dyck paths of size n as the relation of being above. Hence, intervals in the Stanley lattice are pairs of non-crossing Dyck paths. In a former article, the second author defined a bijection Φ between pairs of non-crossing Dyck paths and the realizers of triangulations (or Schnyder woods). We give a simpler description of the bijection Φ. Then, we study the restriction of Φ to Tamari's and Kreweras' intervals. We prove that Φ induces a bijection between Tamari intervals and minimal realizers. This gives a bijection between Tamari intervals and triangulations. We also prove that Φ induces a bijection between Kreweras intervals and the (unique) realizers of stack triangulations. Thus, Φ induces a bijection between Kreweras intervals and stack triangulations which are known to be in bijection with ternary trees.

Introduction

A Dyck path is a lattice path made of +1 and -1 steps that starts from 0, remains non-negative and ends at 0. It is often convenient to represent a Dyck path by a sequence of North-East and South-East steps as is done in Figure 1 The Catalan sequence is a pervasive guest in enumerative combinatorics. Indeed, beside Dyck paths, this sequence enumerates the binary trees, the plane trees, the non-crossing partitions and over 60 other fundamental combinatorial structures [START_REF] Stanley | Enumerative combinatorics[END_REF]Ex. 6.19]. These different incarnations of the Catalan family gave rise to several lattices beside Stanley's. The Tamari lattice appears naturally in the study of binary trees where the covering relation corresponds to right rotation. This lattice is actively studied due to its link with the associahedron (Stasheff polytope). Indeed, the Hasse diagram of the Tamari lattice is the 1-skeleton of the associahedron. The Kreweras lattice appears naturally in the setting of non-crossing partitions. In the seminal paper [START_REF] Kreweras | Sur les partitions non-croisées d'un cycle[END_REF], Kreweras proved that the refinement order on non-crossing partitions defines a lattice. Kreweras lattice appears to support a great deal of mathematics that reach far beyond enumerative combinatorics [START_REF] Mccammond | Noncrosing partitions in surprising locations[END_REF][START_REF] Simion | Noncrossing partitions[END_REF]. Using suitable bijection between Dyck paths, binary trees, non-crossing partitions and plane 1 trees, the three Catalan lattices can be defined on the set of plane trees of size n in such way that the Stanley lattice L S n is an extension of the Tamari lattice L T n which in turn is an extension of the Kreweras lattice L K n (see [START_REF] Knuth | Fascicle 4. Generating all trees -History of combinatorial generation[END_REF]27 and 28]). In this paper, we shall find convenient to embed the three Catalan lattices on the set D n of Dyck paths. The Hasse diagram of the Catalan lattices on D 3 is represented in Figure 2.

(b) (c) (a) n | of such pairs can be calculated using the lattice path determinant formula of Lindström-Gessel-Viennot [START_REF] Gessel | Binomial determinants, paths and hook formulae[END_REF]. It is shown in [START_REF] Sainte-Catherine | Enumeration of certain young tableaux with bounded height[END_REF] that

|L S n | = C n+2 C n -C 2 n+1 = 6(2n)!(2n + 2)! n!(n + 1)!(n + 2)!(n + 3)! . (1)
The intervals of the Tamari lattice were recently enumerated by Chapoton [START_REF] Chapoton | Sur le nombre d'intervalles dans les treillis de tamari[END_REF] using a generating function approach. It was proved that the number of intervals in the Tamari lattice is

|L T n | = 2(4n + 1)! (n + 1)!(3n + 2)! . (2)
Chapoton also noticed that [START_REF] Bonichon | An information upper bound of planar graphs using triangulation[END_REF] is the number of triangulations (i.e. maximal planar graphs) and asked for an explanation. The number |L K n | of intervals of the Kreweras Lattice has an even simpler formula. In [START_REF] Kreweras | Sur les partitions non-croisées d'un cycle[END_REF], Kreweras proved by a recursive method that

|L K n | = 1 2n + 1 3n n . (3)
This is also the number of ternary trees and a bijection was exhibited in [START_REF] Edelman | Multichains, non-crossing partitions and trees[END_REF].

In [START_REF] Bonichon | A bijection between realizers of maximal plane graphs and pairs of non-crossing dyck paths[END_REF], the second author defined a bijection Φ between the pairs of non-crossing Dyck paths (equivalently, Stanley's intervals) and the realizers (or Schnyder woods) of triangulations. The main purpose of this article is to study the restriction of the bijection Φ to the Tamari intervals and to the Kreweras intervals. We first give an alternative, simpler, description of the bijection Φ. Then, we prove that the bijection Φ induces a bijection between the intervals of the Tamari lattice and the realizers which are minimal. Since every triangulation has a unique minimal realizer, we obtain a bijection between Tamari intervals and triangulations. As a corollary, we obtain a bijective proof of Formula (2) thereby answering the question of Chapoton. Turning to the Kreweras lattice, we prove that the mapping Φ induces a bijection between Kreweras intervals and the realizers which are both minimal and maximal. We then characterize the triangulations having a realizer which is both minimal and maximal and prove that these triangulations are in bijection with ternary trees. This gives a new bijective proof of Formula (3).

The outline of this paper is as follows. In Section 2, we review our notations about Dyck paths and characterize the covering relations for the Stanley, Tamari and Kreweras lattices in terms of Dyck paths. In Section 3, we recall the definitions about triangulations and realizers. We then give an alternative description of the bijection Φ defined in [START_REF] Bonichon | A bijection between realizers of maximal plane graphs and pairs of non-crossing dyck paths[END_REF] between pairs of non-crossing Dyck paths and the realizers. In Section 4, we study the restriction of Φ to the Tamari intervals. Lastly, in Section 5 we study the restriction of Φ to the Kreweras intervals.

Catalan lattices

Dyck paths. A Dyck path is a lattice path made of steps N = +1 and S = -1 that starts from 0, remains non-negative and ends at 0. A Dyck path is said to be prime if it remains positive between its start and end. The size of a path is half its length and the set of Dyck paths of size n is denoted by D n .

Let P be a Dyck path of size n. Since P begins by an N step and has n N steps, it can be written as P = N S α1 N S α2 . . . N S αn . We call i th descent the subsequence S αi of P . For i = 0, 1, . . . , n we call i th exceedence and denote by e i (P ) the height of the path P after the i th descent, that is, e i (P ) = i-j≤i α j . For instance, the Dyck path represented in Figure 3 (a) is P = N S 1 N S 0 N S 1 N S 2 N S 0 N S 0 N S 3 and e 0 (P ) = 0, e 1 (P ) = 0, e 2 (P ) = 1, e 3 (P ) = 1, e 4 (P ) = 0, e 5 (P ) = 1, e 6 (P ) = 2 and e 7 (P ) = 0. If P, Q are two Dyck paths of size n, we denote δ i (P, Q) = e i (Q) -e i (P ) and ∆(P, Q) = n i=1 δ i (P, Q). For instance, if P and Q are respectively the lower and upper paths in Figure 3 (b), the values δ i (P, Q) are zero except for δ 1 (P, Q) = 1, δ 4 (P, Q) = 2 and δ 5 (P, Q) = 1. For 0 ≤ i ≤ j ≤ n, we write i P j (resp. i P j) if e i (P ) ≥ e j (P ) and e i (P ) ≤ e k (P ) (resp. e i (P ) < e k (P )) for all i < k < j. In other words, i P j (resp. i P j) means that the subpath N S αi+1 N S αi+2 . . . N S αj is a Dyck path (resp. prime Dyck path) followed by e i (P ) -e j (P ) S steps. For instance, for the Dyck path P of Figure 3 (a), we have 0 P 4, 1 P 4 and 2 P 4 (and many other relations).

We will now define the Stanley, Tamari and Kreweras lattices in terms of Dyck paths. More precisely, we will characterize the covering relation of each lattice in terms of Dyck paths and show that our definitions respects the known hierarchy between the three lattices (the Stanley lattice is a refinement of the Tamari lattice which is refinement of the Kreweras Lattice; see [START_REF] Knuth | Fascicle 4. Generating all trees -History of combinatorial generation[END_REF]27 and 28]).

Stanley lattice. Let P = N S α1 . . . N S αn and Q = N S β1 . . . N S βn be two Dyck paths of size n. We denote by P ≤ S Q if the path P stays below the path Q. Equivalently, e i (P ) ≤ e i (Q) for all 1 ≤ i ≤ n. The relation ≤ S defines the Stanley lattice L S n on the set D n . Clearly the path P is covered by the path Q in the Stanley lattice if Q is obtained from P by replacing a subpath SN by N S. Equivalently, there is an index n and there are well known bijections between the set B n and the set D n . We call σ the bijection defined as follows: the image of the binary tree reduced to a leaf is the empty word and the image of the binary tree B = (B 1 , B 2 ) is the Dyck path σ(B) = σ(B 1 )N σ(B 2 )S. An example is given in Figure 5.

1 ≤ i ≤ n such that β i = α i -1, β i+1 = α i+1 + 1 and β k = α k for all k = i, i + 1.
In [START_REF] Huang | Problems of associativity: A simple proof of the lattice property of systems ordered by a semi-associative law[END_REF], Tamari defined a partial order on the set B n of binary trees and proved to be a lattice. The covering relation for the Tamari lattice is defined has follows: a binary tree B containing a subtree of type X = ((B 1 , B 2 ), B 3 ) is covered by the binary tree B ′ obtained from B by replacing X by (B 1 , (B 2 , B 3 )). The Hasse diagram of the Tamari lattice on the set of binary trees with 4 nodes is represented in Figure 6 (left). Proposition 2.1. Let P = N S α1 . . . N S αn and Q = N S β1 . . . N S βn be two Dyck paths. The path P is covered by the path Q in the Tamari lattice L T n if Q is obtained from P by swapping an S step and the prime Dyck subpath following it, that is, there are indices 1 ≤ i < j ≤ n with α i > 0 and i P j such that

β i = α i -1, β j = α j + 1 and β k = α k for all k = i, j. Corollary 2.2. The Stanley lattice L S
n is a refinement of the Tamari lattice L T n . That is, for any pair of Dyck paths P, Q, P ≤ T Q implies P ≤ S Q.

Proof of Proposition 2.1: Let B be a binary tree and let P = σ(B).

• We use the well known fact that there is a one-to-one correspondence between the subtrees of B and the Dyck subpaths of P which are either a prefix of P or are preceded by an N step. (This classical property is easily shown by induction on the size of P .)

• If the binary tree B ′ is obtained from B by replacing a subtree X = ((B 1 , B 2 ), B 3 ) by X ′ = (B 1 , (B 2 , B 3 )), then the Dyck path Q = σ(B ′ ) is obtained from P by replacing a subpath σ(X) = σ(B 1 )N σ(B 2 )SN σ(B 3 )S by σ(X ′ ) = σ(B 1 )N σ(B 2 )N σ(B 3
)SS; hence by swapping an S step and the prime Dyck subpath following it.

• Suppose conversely that the Dyck path Q is obtained from P by swapping an S step with a prime Dyck subpath N P 3 S following it. Then, there are two Dyck paths P 1 and P 2 (possibly empty) such that W = P 1 N P 2 SN P 3 S is a Dyck subpath of P which is either a prefix of P or is preceded by an N step. Hence, the binary tree B contains the subtree X = σ -1 (W ) = ((B 1 , B 2 ), B 3 ), where B i = σ -1 (P i ), i = 1, 2, 3. Moreover, the binary tree

B ′ = σ -1 (Q) is obtained from B by replacing the subtree X = ((B 1 , B 2 ), B 3 ) by X ′ = (B 1 , (B 2 , B 3 )) = σ -1 (P 1 N P 2 N P 3 SS).
Kreweras lattice. A partition of {1, . . . , n} is non-crossing if whenever four elements 1 ≤ i < j < k < l ≤ n are such that i, k are in the same class and j, l are in the same class, then the two classes coincide. The non-crossing partition whose classes are {1}, {2, 4}, {3}, and {5, 6, 7} is represented in Figure 7. In this figure, each class is represented by a connected cell incident to the integers it contains. and there are well known bijections between non-crossing partitions and Dyck paths. We consider the bijection θ defined as follows. The image of a non-crossing partition π of size n by the mapping θ is the Dyck path θ(π) = N S α1 N S α2 . . . N S αn , where α i is the size of the class containing i if i is maximal in its class and α i = 0 otherwise. An example is given in Figure 7.

In [START_REF] Kreweras | Sur les partitions non-croisées d'un cycle[END_REF], Kreweras showed that the partial order of refinement defines a lattice on the set NC n of noncrossing partitions. The covering relation of this lattice corresponds to the merging of two parts when this operation does not break the non-crossing condition. The Hasse diagram of the Kreweras lattice on the set NC 4 is represented in Figure 8 (left). Proposition 2.3. Let P = N S α1 . . . N S αn and Q = N S β1 . . . N S βn be two Dyck paths of size n. The path P is covered by the path Q in the Kreweras lattice L K n if Q is obtained from P by swapping a (non-empty) descent with a Dyck subpath following it, that is, there are indices 1 ≤ i < j ≤ n with α i > 0 and i P j such that

β i = 0, β j = α i + α j and β k = α k for all k = i, j. Corollary 2.4. The Tamari lattice L T
n is a refinement of the Kreweras lattice L K n . That is, for any pair P, Q of Dyck paths, P ≤ K Q implies P ≤ T Q. Lemma 2.5. Let π be a non-crossing partition and let P = θ(π). Let c and c ′ be two classes of π with the convention that i = max(c) < j = max(c ′ ). Then, the classes c and c ′ can be merged without breaking the non-crossing condition if and only if i P j.

Proof: For any index k = 1, . . . , n, we denote by c k the class of π containing k. Observe that the classes c and c ′ can be merged without breaking the non-crossing condition if and only if there are no integers r, s with c r = c s such that r < i < s < j or i < r < j < s. Observe also from the definition of the mapping θ that for all index l = 1, . . . , n, the exceedence e l (P ) is equal to the number of indices k ≤ l such that max(c k ) > l.

• We suppose that i P j and we want to prove that merging the classes c and c ′ does not break the noncrossing condition. We first prove that there are no integers r, s such that i < r < j < s and c r = c s . Suppose the contrary. In this case, there is no integer k ≤ r such that r < max(c k ) ≤ j (otherwise,

c k = c r = c s by the non-crossing condition, hence max(c k ) ≥ max(c s ) > j). Thus, {k ≤ r/ max(c k ) > r} = {k ≤ r/ max(c k ) > j} {k ≤ j/ max(c k ) > j}.
This implies e r (P ) < e j (P ) and contradicts the assumption i P j. It remains to prove that there are no integers r, s such that r < i < s < j and c r = c s . Suppose the contrary and let s ′ = max(c r ). The case where s ′ ≥ j has been treated in the preceding point so we can assume that s ′ < j. In this case, there is no integer

k such that i < k ≤ s ′ and max(c k ) > s ′ (otherwise, c k = c r = c s ′ by the non-crossing condition, hence max(c k ) = max(c r ) = s ′ ). Thus, {k ≤ i/ max(c k ) > i} {k ≤ i/ max(c k ) > s ′ } = {k ≤ s ′ / max(c k ) > s ′ }.
This implies e i (P ) < e s ′ (P ) and contradicts the assumption i P j.

• We suppose now that merging the classes c and c ′ does not break the non-crossing partition and we want to prove that i P j. Observe that there is no integer k such that i < k ≤ j and max(c k ) > j (otherwise, merging the classes c and c ′ would break the non-crossing condition). Thus,

{k ≤ j/ max(c k ) > j} = {k ≤ i/ max(c k ) > j} ⊆ {k ≤ i/ max(c k ) > i}.
This implies e j (P ) ≤ e i (P ). It remains to prove that there is no index s such that i < s < j and e s (P ) < e i (P ). Suppose the contrary and consider the minimal such s. Observe that s is maximal in its class, otherwise e s-1 (P ) = e s (P ) -1 < e i (P ) contradicts the minimality of s. Observe also that i < r = min(c s ) otherwise merging the classes c and c ′ would break the non-crossing condition. By the non-crossing condition, there is no integer k < r such that r ≤ max(c k ) ≤ s.

Thus, {k ≤ r -1/ max(c k ) > r -1} = {k ≤ r -1/ max(c k ) > s} ⊆ {k ≤ s/ max(c k ) > s}.
This implies e r-1 (P ) ≤ e s (P ) < e i (P ) and contradicts the minimality of s.

A bijection between Stanley intervals and realizers

In this section, we recall some definitions about triangulations and realizers. Then, we define a bijection between pairs of non-crossing Dyck paths and realizers.

Triangulations and realizers

Maps. A planar map, or map for short, is an embedding of a connected finite planar graph in the sphere considered up to continuous deformation. In this paper, maps have no loop nor multiple edge. The faces are the connected components of the complement of the graph. By removing the midpoint of an edge we get two half-edges, that is, one dimensional cells incident to one vertex. Two consecutive half-edges around a vertex define a corner. If an edge is oriented we call tail (resp. head ) the half-edge incident to the origin (resp. end).

A rooted map is a map together with a special half-edge which is not part of a complete edge and is called the root. (Equivalently, a rooting is defined by the choice of a corner.) The root is incident to one vertex called root-vertex and one face (containing it) called the root-face. When drawing maps in the plane the root is represented by an arrow pointing on the root-vertex and the root-face is the infinite one. See Figure 10 Triangulations. A triangulation is a map in which any face has degree 3 (has 3 corners). A triangulation has size n if it has n internal vertices. The incidence relation between faces and edges together with Euler formula show that a triangulation of size n has 3n internal edges and 2n + 1 internal triangles.

In one of its famous census paper, Tutte proved by a generating function approach that the number of triangulations of size n is t n = 2(4n+1)! (n+1)!(3n+2)! [START_REF] Tutte | A census of planar triangulations[END_REF]. A bijective proof of this result was given in [START_REF] Poulalhon | Optimal coding and sampling of triangulations[END_REF].

Realizers. We now recall the notion of realizer (or Schnyder wood ) defined by Schnyder [START_REF] Schnyder | Planar graphs and poset dimension[END_REF][START_REF] Schnyder | Embedding planar graphs in the grid[END_REF]. Given an edge coloring of a map, we shall call i-edge (resp. i-tail, i-head ) an edge (resp. tail, head) of color i.

Definition 3.1 ( [START_REF] Schnyder | Planar graphs and poset dimension[END_REF]). Let M be a triangulation and let U be the set of its internal vertices. Let v 0 be the root-vertex and let v 1 , v 2 be the other external vertices with the convention that v 0 , v 1 , v 2 appear in counterclockwise order around the root-face.

A realizer of M is a coloring of the internal edges in three colors {0, 1, 2} such that:

1. Tree condition: for i = 0, 1, 2, the i-edges form a tree T i with vertex set U ∪ {v i }. The vertex v i is considered to be the root-vertex of T i and the i-edges are oriented toward v i .

2. Schnyder condition: in clockwise order around any internal vertex there is: one 0-tail, some 1-heads, one 2-tail, some 0-heads, one 1-tail, some 2-heads. This situation is represented in Figure 11.

We denote by R = (T 0 , T 1 , T 2 ) this realizer. A realizer is represented in Figure 10 (right). Let R = (T 0 , T 1 , T 2 ) be a realizer. We denote by T 0 the tree made of T 0 together with the edge (v 0 , v 1 ). For any internal vertex u, we denote by p i (u) the parent of u in the tree T i . A cw-triangle (resp. ccw-triangle) is a triple of vertices (u, v, w) such that p 0 (u) = v, p 2 (v) = w and p 1 (w) = u (resp. p 0 (u) = v, p 1 (v) = w and p 2 (w) = u). A realizer is called minimal (resp. maximal ) if it has no cw-triangle (resp. ccw-triangle). It was proved in [START_REF] Ossona De | Orientations bipolaires[END_REF][START_REF] Propp | Lattice structure for orientations of graphs[END_REF] that every triangulation has a unique minimal (resp. maximal) realizer. (The appellations minimal and maximal refer to a classical lattice which is defined on the set of realizers of any given triangulation [START_REF] Ossona De | Orientations bipolaires[END_REF][START_REF] Propp | Lattice structure for orientations of graphs[END_REF].)

A bijection between pairs of non-crossing Dyck paths and realizers

In this subsection, we give an alternative (and simpler) description of the bijection defined in [START_REF] Bonichon | A bijection between realizers of maximal plane graphs and pairs of non-crossing dyck paths[END_REF] between realizers and pairs of non-crossing Dyck paths.

We first recall a classical bijection between plane trees and Dyck paths. A plane tree is a rooted map whose underlying graph is a tree. Let T be a plane tree. We make the tour of the tree T by following its border in clockwise direction starting and ending at the root (see Figure 14 (a)). We denote by ω(T ) the word obtained by making the tour of the tree T and writing N the first time we follow an edge and S the second time we follow this edge. For instance, w(T ) = N N SSN N SN N SN SSN N SSS for the tree in Figure 14 (a). It is well known that the mapping ω is a bijection between plane trees with n edges and Dyck paths of size n [START_REF] Knuth | Fascicle 4. Generating all trees -History of combinatorial generation[END_REF].

Let T be a plane tree. Consider the order in which the vertices are encountered while making the tour of T . This defines the clockwise order around T (or preorder ). For the tree in Figure 14 (a), the clockwise order is v 0 < u 0 < u 1 < . . . < u 8 . The tour of the tree also defines an order on the set of corners around each vertex v. We shall talk about the first (resp. last ) corner of v around T .

We are now ready to define a mapping Ψ which associates an ordered pair of Dyck paths to each realizer. Definition 3.2. Let M be a rooted triangulation of size n and let R = (T 0 , T 1 , T 2 ) be a realizer of M . Let u 0 , u 1 , . . . , u n-1 be the internal vertices of M in clockwise order around T 0 . Let β i , i = 1, . . . , n -1 be the number of 1-heads incident to u i and let β n be the number of 1-heads incident to v 1 . Then Ψ(R) = (P, Q), where P = ω -1 (T 0 ) and Q = N S β1 . . . N S βn .

The image of a realizer by the mapping Ψ is represented in Figure 12.

v 0 v 2 v 1 Ψ Φ Figure 12:
The bijections Ψ and Φ.

Theorem 3.3. The mapping Ψ is a bijection between realizers of size n and pairs of non-crossing Dyck paths of size n.

The rest of this section is devoted to the proof of Theorem 3.3. We first prove that the image of a realizer is indeed a pair of non-crossing Dyck paths. Proposition 3.4. Let R = (T 0 , T 1 , T 2 ) be a realizer of size n and let (P, Q) = Ψ(R). Then, P and Q are both Dyck paths and moreover the path P stays below the path Q.

Proposition 3.4 is closely related to the Lemma 3.6 below which, in turn, relies on the following technical lemma.

Lemma 3.5. Let M be a map in which every face has degree three. We consider an orientation of the internal edges of M such that every internal vertex has outdegree 3 (i.e. is incident to exactly 3 tails). Let C be a simple cycle made of c edges. By the Jordan Lemma, the cycle C separates the sphere into two connected regions. We call inside the region not containing the root. Then, the number of tails incident with C and lying strictly inside C is c -3.

Proof: Let v (resp. f, e) be the number of vertices (resp. faces, edges) lying strictly inside C. Note that the edges strictly inside C are internal hence are oriented. The number i of tails incident with C and lying strictly inside C satisfies e = 3v + i. Moreover, the incidence relation between edges and faces implies 3f = 2e + c and the Euler relation implies (f + 1) + (v + c) = (e + m) + 2. Solving for i gives i = c -3. Lemma 3.6. Let R = (T 0 , T 1 , T 2 ) be a realizer. Then, for any 1-edge e the tail of e is encountered before its head around the tree T 0 .

Proof of Lemma 3.6: Suppose a 1-edge e breaks this rule and consider the cycle C made of e and the 0-path joining its endpoints. Using the Schnyder condition it is easy to show that the number of tails incident with C and lying strictly inside C is equal to the number of edges of C (the different possibilities are represented in Figure 13). This contradicts Lemma 3.5.

e e e T 0 T 1 T 2

Figure 13: Case analysis for a 1-edge e whose head appears before its tail around the tree T 0 .

Lemma 3.7. Let P = N S α1 . . . N S αn be a Dyck path and let T = ω -1 (P ). Let v 0 be the root-vertex of the tree T and let u 0 , u 1 , . . . , u n-1 be its other vertices in clockwise order around T . Then, the word obtained by making the tour of T and writing S βi when arriving at the first corner of u i and N when arriving at the last corner of u i is W = S β0 N α1 S β1 . . . S βn-1 N αn .

Proof: We consider the word W obtained by making the tour of T and writing N S βi when arriving at the first corner of u i and NS when arriving at the last corner of u i for i = 0, . . . , n -1. By definition of the mapping ω, the restriction of W to the letters N, S is W = ω(T ) = P = N S α1 . . . N S αn . Therefore, W = N S β0 (NS) α1 N S β1 (NS) α2 . . . N S βn-1 (NS) αn . Hence, the restriction of W to the letters N, S is

W = S β0 N α1 S β1 N α2 . . . S βn-1 N αn .
Proof of Proposition 3.4: We denote P = N S α1 . . . N S αn and Q = N S β1 . . . N S βn .

• The mapping ω is known to be a bijection between trees and Dyck paths, hence P = ω(T ) is a Dyck path.

• We want to prove that Q is a Dyck path staying above P . Consider the word W obtained by making the tour of T 0 and writing N (resp. S) when we encounter a 1-tail (resp. 1-head). By Lemma 3.7, the word W is S β0 N α1 S β1 N α2 . . . S βn-1 N αn S βn . By Lemma 3.6, the word W is a Dyck path. In particular, S β0 = 0 and n i=1 β i = n i=1 α i = n, hence the path Q returns to the origin. Moreover, for all i = 1, . . . , n, δ i (P, Q) = n j=1 α i -β i ≥ 0. Thus, the path Q stays above P . In particular, Q is a Dyck path.

In order to prove Theorem 3.3, we shall now define a mapping Φ from pairs of non-crossing Dyck paths to realizers and prove it to be the inverse of Ψ. We first define prerealizers. Definition 3.8. Let M be a map. Let v 0 be the root-vertex, let v 1 be another external vertex and let U be the set of the other vertices. A prerealizer of M is a coloring of the edges in two colors {0, 1} such that:

1. Tree condition: for i = 0, 1, the i-edges form a tree T i with vertex set U ∪ {v i }. The vertex v i is considered to be the root-vertex of T i and the i-edges are oriented toward v i .

2. Corner condition: in clockwise order around any vertex u ∈ U there is: one 0-tail, some 1-heads, some 0-heads, one 1-tail.

3. Order condition: for any 1-edge e, the tail of e is encountered before its head around the tree T 0 , where T 0 is the tree obtained from T 0 by adding the edge (v 0 , v 1 ) at the right of the root.

We denote by PR = (T 0 , T 1 ) this prerealizer.

An example of prerealizer is given in Figure 14 (c).

Lemma 3.9. Let PR = (T 0 , T 1 ) be a prerealizer. Then, there exists a unique tree T 2 such that R = (T 0 , T 1 , T 2 ) is a realizer.

In order to prove Lemma 3.9, we need to study the sequences of corner around the faces of prerealizers. If h and h ′ are two consecutive half-edges in clockwise order around a vertex u we denote by c = (h, h ′ ) the corner delimited by h and h ′ . For 0 ≤ i, j ≤ 2, we call (h i , h j )-corner (resp. (h i , t j )-corner, (t i , h j )-corner, (t i , t j )-corner ) a corner c = (h, h ′ ) where h and h ′ are respectively an i-head (resp. i-head, i-tail, i-tail) and a j-head (resp. j-tail, j-head, j-tail).

Proof of Lemma 3.9: Let PR = (T 0 , T 1 ) be a prerealizer and let N = T 0 ∪ T 1 be the underlying map. Let v 0 (resp. v 1 ) be the root-vertex of T 0 (resp. T 1 ) and let U be the set of vertices distinct from v 0 , v 1 . Let T 0 (resp. N ) be the tree (resp. map) obtained from T 0 (resp. N ) by adding the edge (v 0 , v 1 ) at the right of the root. We first prove that there is at most one tree T 2 such that R = (T 0 , T 1 , T 2 ) is a realizer.

• Let f be an internal face of N and let c 1 , c 2 , . . . , c k be the corners of f encountered in clockwise order around T 0 . Note that c 1 , c 2 , . . . , c k also correspond to the clockwise order of the corners around the face f . We want to prove the following properties:

-the corner c 1 is a (t 1 , t 0 )-corner, -the corner c 2 is either a (h 0 , h 0 )-or a (h 0 , t 1 )-corner, -the corners c 3 , . . . , c k-1 are (h 1 , h 0 )-, (h 1 , t 1 )-, (t 0 , h 0 )-or (t 0 , t 1 )-corners, -the corner c k is either a (h 1 , h 1 )-or a (t 0 , h 1 )-corner. First note that by the corner condition of the prerealizers the possible corners are of type (h 0 , h 0 ), (h 0 , t 1 ), (h 1 , h 0 ), (h 1 , h 1 ), (h 1 , t 1 ), (t 0 , h 0 ), (t 0 , h 1 ), (t 0 , t 1 ) and (t 1 , t 0 ). By the order condition, one enters a face for the first time (during a tour of T 0 ) when crossing a 1-tail. Hence, the first corner c 1 of f is a (t 1 , t 0 )-corner while the corners c i , i = 2, . . . , k are not (t 1 , t 0 )-corners. Since c 1 is a (t 1 , t 0 )-corner, the corner c 2 is either a (h 0 , h 0 )-or a (h 0 , t 1 )-corner. Similarly, since c 1 is a (t 1 , t 0 )-corner, the corner c k is either a (h 1 , h 1 )-or a (t 0 , h 1 )-corner. Moreover, for i = 2, . . . , k -1, the corner c i is not a (h 1 , h 1 )nor a (t 0 , h 1 )-corner or c i+1 would be a (t 1 , t 0 )-corner. Therefore, it is easily seen by induction on i that the corners c i , i = 3, . . . , k -1 are either (h 1 , h 0 )-, (h 1 , t 1 )-, (t 0 , h 0 )-or (t 0 , t 1 )-corners.

• By a similar argument we prove that the corners of the external face of N are (h 1 , h 0 )-, (h 1 , t 1 )-, (t 0 , h 0 )-or (t 0 , t 1 )-corners except for the corner incident to v 0 which is a (h 0 , h 0 )-corner and the corner incident to v 1 which is a (h 1 , h 1 )-corner.

• Let v 2 be an isolated vertex in the external face of N . If a tree T 2 with vertex set U ∪ {v 2 } is such that R = (T 0 , T 1 , T 2 ) is a realizer, then there is one 2-tail in each (h 1 , h 0 )-, (h 1 , t 1 )-, (t 0 , h 0 )-or (t 0 , t 1 )-corner of N while the 2-heads are only incident to the (t 0 , t 1 )-corners and to the vertex v 2 . By the preceding points, there is exactly one (t 1 , t 0 ) corner in each internal face and none in the external face. Moreover there is at most one way of connecting the 2-tails and the 2-heads in each face of N . Thus, there is at most one tree T 2 such that R = (T 0 , T 1 , T 2 ) is a realizer.

We now prove that there exists a tree T 2 such that R = (T 0 , T 1 , T 2 ) is a realizer. Consider the colored map (T 0 , T 1 , T 2 ) obtained by -adding an isolated vertex v 2 in the external face of N .

-adding a 2-tail in each (h 1 , h 0 )-, (h 1 , t 1 )-, (t 0 , h 0 )-and (t 0 , t 1 )-corner of N .

-joining each 2-tail in an internal face f (resp. the external face) to the unique (t 0 , t 1 )-corner of f (resp. to v 2 ). We denote by

M = T 0 ∪ T 1 ∪ T 2 ∪ {(v 0 , v 1 ), (v 0 , v 2 ), (v 1 , v 2 )} the underlying map.
• We first prove that the map

M = T 0 ∪ T 1 ∪ T 2 ∪ {(v 0 , v 1 ), (v 0 , v 2 ), (v 1 , v 2 )
} is a triangulation. Let f be an internal face. By a preceding point, f has exactly one (t 1 , t 0 ) corner c and the (h 1 , h 0 )-, (h 1 , t 1 )-, (t 0 , h 0 )-or (t 0 , t 1 )-corners are precisely the ones that are not consecutive with c around f . Thus, the internal faces of N are triangulated (split into sub-faces of degree 3) by the 2-edges. Moreover, the only corners of the external face of N which are not of type (h 1 , h 0 ), (h 1 , t 1 ), (t 0 , h 0 ) or (t 0 , t 1 ) are the (unique) corner around v 0 and the (unique) corner around v 1 . Hence the external face of N is triangulated by the 2-edges together with the edges (v 0 , v 2 ) and (v 1 , v 2 ). Thus, every face of M has degree 3. It only remains to prove that M has no multiple edge. Since the faces of M are of degree 3 and every internal vertex has outdegree 3, the hypothesis of Lemma 3.5 are satisfied. By this lemma, there can be no multiple edge (this would create a cycle of length 2 incident to -1 tails!). Thus, the map M has no multiple edge and is a triangulation.

• We now prove that the coloring R = (T 0 , T 1 , T 2 ) is a realizer of M . By construction, R satisfies de Schnyder-condition. Hence it only remains to prove that T 2 is a tree. Suppose there is a cycle C of 2-edges. Since every vertex in C is incident to one 2-tail, the cycle C is directed. Therefore, the Schnyder condition proves that there are c = |C| tails incident with C and lying strictly inside C. This contradicts Lemma 3.5. Thus, T 2 has no cycle. Since T 2 has |U | edges and |U | + 1 vertices it is a tree.

We are now ready to define a mapping Φ from pairs of non-crossing Dyck paths to realizers. This mapping is illustrated by Figure 14. Consider a pair of Dyck paths P = N S α1 . . . N S αn and Q = N S β1 . . . N S βn such that P stays below Q. The image of (P, Q) by the mapping Φ is the realizer R = (T 0 , T 1 , T 2 ) obtained as follows.

Step 1. The tree T 0 is ω -1 (P ). We denote by v 0 its root-vertex and by u 0 , . . . , u n the other vertices in clockwise order around T 0 . We denote by T 0 the tree obtained from T 0 by adding a new vertex v 1 and an edge (v 0 , v 1 ) at the right of the root.

Step 2. We glue a 1-tail in the last corner of each vertex u i , i = 0, . . . , n -1 and we glue β i 1-heads in the first corner of each vertex u i , i = 1, . . . , n -1 (if u i is a leaf we glue the 1-heads before the 1-tail in clockwise order around u i ). We also glue β n 1-heads in the (unique) corner of v 1 . This operation is illustrated by Figure 14 (b).

Step 3. We consider the sequence of 1-tails and 1-heads around T 0 . Let W be the word obtained by making the tour of T 0 and writing N (resp. S) when we cross a 1-tail (resp. 1-head). By Lemma 3.7, W = N α1 S β1 . . . N αn S βn . Since the path P stays below the path Q, we have δ i (P, Q) = j≤i α j -β j ≥ 0 for all i = 1, . . . , n, hence W is a Dyck path. Thus, there exists a unique way of joining each 1-tail to a 1-head that appears after it around the tree T 0 so that the 1-edges do not intersect (this statement is equivalent to the well-known fact that there is a unique way of matching parenthesis in a well parenthesized word); we denote by T 1 the set of 1-edges obtained in this way. This operation is illustrated in Figure 14 (c).

Step 4. The set T 1 of 1-edges is a tree directed toward v 1 ; see Lemma 3.10 below. Hence, by construction, PR = (T 0 , T 1 ) is a prerealizer. By Lemma 3.9, there is a unique tree T 2 such that R = (T 0 , T 1 , T 2 ) is a realizer and we define Φ(P, Q) = R. In order to prove that step 4 of the bijection Φ is well defined, we need the following lemma.

v 1 v 0 (a) (c) (d) (b) v 0 u 0 u 3 u 5 u 6 u 8 u 2 u 4 u 7 u 1 v 1 v 0 v 1 v 2 v 0
Lemma 3.10. The set T 1 of 1-edges obtained at step 3 in the definition of Φ is a tree directed toward v 1 and spanning the vertices in U 1 = {u 0 , . . . , u n-1 , v 1 }.

Proof: • Every vertex in U 1 is incident to an edge in T 1 since there is a 1-tail incident to each vertex u i , i = 1, . . . , n -1 and at least one 1-head incident to v 1 since β n > 0.

• We now prove that the tree T 1 has no cycle. Since every vertex in U 1 is incident to at most one 1-tail, any 1-cycle is directed. Moreover, if e is a 1-edge directed from u i to u j then i < j since the last corner of u i appears before the first corner of u j around T 0 . Therefore, there is no directed cycle.

• Since T 1 is a set of n edges incident to n+1 vertices and having no cycle, it is a tree. Since the only sink is v 1 , the tree T 1 is directed toward v 1 (make an induction on the size of the oriented tree T 1 by removing a leaf).

The mapping Φ is well defined and the image of any pair of non-crossing Dyck paths is a realizer. Conversely, by Proposition 3.4, the image of any realizer by Ψ is a pair of non-crossing Dyck paths. It is clear from the definitions that Ψ • Φ (resp. Φ • Ψ) is the identity mapping on pairs of non-crossing Dyck paths (resp. realizers). Thus, Φ and Ψ are inverse bijections between realizers of size n and pairs of non-crossing Dyck paths of size n. This concludes the proof of Theorem 3.3.

Intervals of the Tamari lattice

In the previous section, we defined a bijection Φ between pairs of non-crossing Dyck paths and realizers. Recall that the pairs of non-crossing Dyck paths correspond to the intervals of the Stanley lattice. In this section, we study the restriction of the bijection Φ to the intervals of the Tamari lattice. Since every triangulation has a unique minimal realizer, Theorem 4.1 implies that the mapping Φ ′ which associates with a Tamari interval (P, Q) the triangulation underlying Φ(P, Q) is a bijection. This gives a bijective explanation to the relation between the number of Tamari intervals enumerated in [START_REF] Chapoton | Sur le nombre d'intervalles dans les treillis de tamari[END_REF] and the number of triangulations enumerated in [START_REF] Tutte | A census of planar triangulations[END_REF][START_REF] Poulalhon | Optimal coding and sampling of triangulations[END_REF]. The rest of this section is devoted to the proof of Theorem 4.1. We first recall a characterization of minimality given in [START_REF] Bonichon | An information upper bound of planar graphs using triangulation[END_REF] and illustrated in Figure 15.

Proposition 4.3 ([2]

). A realizer R = (T 0 , T 1 , T 2 ) is minimal if and only if for any internal vertex u, the vertex p 0 (p 1 (u)) is an ancestor of u in the tree T 0 .

Using Proposition 4.3, we obtain the following characterization of the pairs of non-crossing Dyck paths (P, Q) whose image by the bijection Φ is a minimal realizer. Proposition 4.4. Let (P, Q) be a pair of non-crossing Dyck paths and let R = (T 0 , T 1 , T 2 ) = Φ(P, Q). Let u 0 , . . . , u n-1 be the non-root vertices of T 0 in clockwise order. Then, the realizer R is minimal if and only if δ i (P, Q) ≤ δ j (P, Q) whenever u i is the parent of u j in T 0 = ω -1 (P ).

In order to prove Proposition 4.4, we need to interpret the value of δ i (P, Q) is terms of the realizer R = Φ(P, Q). Let u be an internal vertex of the triangulation underlying the realizer R = (T 0 , T 1 , T 2 ). We say that a 1-tail is available at u if this tail appears before the first corner of u in clockwise order around T 0 while the corresponding 1-head appears (strictly) after the first corner of u. u p 0 (p 1 (u))

p 1 (u) v 1 v 2 v 0 Ψ (b) (a)
Figure 15: (a) Characterization of minimality: p 0 (p 1 (u)) is an ancestor of u in T 0 . (b) A minimal realizer and its image by Ψ. Lemma 4.5. Let (P, Q) be a pair of non-crossing Dyck paths and let R = (T 0 , T 1 , T 2 ) = Φ(P, Q). Let u 0 , . . . , u n-1 be the non-root vertices of T 0 in clockwise order. The number of 1-tails available at u i is δ i (P, Q).

Proof of Lemma 4.5: We denote P = N S α1 . . . N S αn and Q = N S β1 . . . N S βn . Let W be the word obtained by making the tour of T 0 and writing N S βi when arriving at the first corner of u i and NS when arriving at the last corner of u i for i = 0, . . . , n -1 (with the convention that β 0 = 0). By definition of the mapping ω, the restriction of W to the letters N, S is ω(T 0 ) = P = N S α1 . . . N S αn . Therefore, W = N S β0 (NS) α1 N S β1 (NS) α2 . . . N S βn-1 (NS) αn . The prefix of W written after arriving at the first corner of u i is N S β0 (NS) α1 N S β1 . . . (NS) αi N S βi . The sub-word S β0 N α1 S β1 . . . N αi S βi corresponds to the sequence of 1-tails and 1-heads encountered so far (N for a 1-tail, S for a 1-head). Thus, the number of 1-tails available at u i is j≤i α j -β j = δ i (P, Q).

Proof of Proposition 4.4:

• We suppose that a vertex u i is the parent of a vertex u j in T 0 and that δ i (P, Q) > δ j (P, Q), and we want to prove that the realizer R = Φ(P, Q) is not minimal. Since u i is the parent of u j we have i < j and all the vertices u r , i < r ≤ j are descendants of u i . By Lemma 4.5, δ i (P, Q) > δ j (P, Q) implies that there is a 1-tail t available at u i which is not available at u j , hence the corresponding 1-head is incident to a vertex u l with i < l ≤ j. Let u k be the vertex incident to the 1-tail t. Since t is available at u i , the vertex u k is not a descendant of u i . But p 0 (p 1 (u k )) = p 0 (u l ) is either u i or a descendant of u i in T 0 . Thus, the vertex u k contradicts the minimality condition given by Proposition 4.3. Hence, the realizer R is not minimal.

• We suppose that the realizer R is not minimal and we want to prove that there exists a vertex u i parent of a vertex u j in T 0 such that δ i (P, Q) > δ j (P, Q). By Proposition 4.3, there exists a vertex u such that p 0 (p 1 (u)) is not an ancestor of u in T 0 . In this case, the 1-tail t incident to u is available at u i = p 0 (p 1 (u)) but not at u j = p 1 (u) (since t cannot appear between the first corner of u i and the first corner of u j around T 0 , otherwise u would be a descendant of u i ). Moreover, any 1-tail t ′ available at u j appears before the 1-tail t around T 0 (otherwise, the 1-edge corresponding to t ′ would cross the 1-edge (u, u j )). Hence, any 1-tail t ′ available at u j is also available at u i . Thus, there are more 1-tails available at u i than at u j . By Lemma 4.5, this implies δ i (P, Q) > δ j (P, Q). Proposition 4.6. . Let (P, Q) be a pair of non-crossing Dyck paths. Let T = ω -1 (P ), let v 0 be the rootvertex of the tree T and let u 0 , . . . , u n-1 be its other vertices in clockwise order. Then, P ≤ T Q if and only if δ i (P, Q) ≤ δ j (P, Q) whenever u i is the parent of u j . Proof: We denote Q = N S β1 . . . N S βn .

• We suppose that P ≤ T Q and want to prove that δ k (P, Q) ≤ δ l (P, Q) whenever u k is the parent of u l . We make an induction on ∆(P, Q). If ∆(P, Q) = 0, then P = Q and the property holds. If ∆(P, Q) > 0 there is a path Q ′ = N S β ′ 1 . . . N S β ′ n such that P ≤ T Q ′ and Q ′ is covered by Q in the Tamari lattice. The three paths P, Q ′ , Q are represented in Figure 16. By definition, there are two indices 1 ≤ i < j ≤ n such that i Q' j and β i = β ′ i + 1, β j = β j -1 and β k = β ′ k for all k = i, j. Thus, δ k (P, Q) = δ k (P, Q ′ ) + 1 if i ≤ k < j and δ k (P, Q) = δ k (P, Q ′ ) otherwise. By the induction hypothesis we can assume that δ k (P, Q ′ ) ≤ δ l (P, Q ′ ) whenever u k is the parent of u l . Suppose there exists u k parent of u l such that δ k (P, Q) > δ l (P, Q). Note that if u k is the parent of u l then k < l and for all k < r ≤ l, the vertex u r is a proper descendant of u k . Since δ k (P, Q) > δ l (P, Q) and δ k (P, Q ′ ) ≤ δ l (P, Q ′ ) we have k < j ≤ l, hence u j is a proper descendant of u k . Note that for all r = 0, . . . , n -1, e r (P ) + 1 is equal to the height of the vertex u r in the tree T (i.e. the distance between v 0 and u r ). Thus, e k (P ) < e j (P ). Moreover, by the induction hypothesis, δ k (P, Q ′ ) ≤ δ j (P, Q ′ ). Hence, e k (Q ′ ) = e k (P ) + δ k (P, Q ′ ) < e j (Q ′ ) = e j (P ) + δ j (P, Q ′ ). But since i ≤ k < j this contradicts the hypothesis i Q' j. We reach a contradiction, hence δ k (P, Q) ≤ δ l (P, Q) whenever u k is the parent of u l .

P δ r (P, Q) Q ′ Q i j
Figure 16: The Dyck paths P ≤ T Q ′ ≤ T Q.

• We suppose that δ k (P, Q) ≤ δ l (P, Q) whenever u k is the parent of u l and want to prove that P ≤ T Q. We make an induction on ∆(P, Q). If ∆(P, Q) = 0, then P = Q and the property holds. Suppose ∆(P, Q) > 0 and let δ = max{δ k (P, Q), k = 0 . . . n}, let e = min{e k (P )/δ k (P, Q) = δ} and let i = max{k/e k (P ) = e and δ k (P, Q) = δ}. Let j be the first index such that i < j ≤ n and u j is not a descendant of u

i (j = n if u i+1 , . . . , u n-1 are all descendants of u i ). Let Q ′ = N S β ′ 1 . . . N S β ′ n with β ′ i = β i + 1, β ′ j = β j -1 and β ′ k = β k for all k = i, j.
The paths P, Q and Q ′ are represented in Figure 16. We want to prove that Q ′ is a Dyck path covered by Q in the Tamari lattice and P ≤ T Q ′ .

-We first prove that Q ′ is a Dyck path that stays above P . First note that δ k (P, Q

′ ) = δ k (P, Q)-1 if i ≤ k < j and δ k (P, Q ′ ) = δ k (P, Q) otherwise. If δ k (P, Q ′ ) < 0, then i ≤ k < j, hence u k is a descendant of u i .
Since the value of δ r (P, Q) is weakly increasing along the branches of T , we have δ k (P, Q) ≥ δ i (P, Q) = δ > 0, hence δ k (P, Q ′ ) ≥ 0. Thus for all k = 0, . . . , n, δ k (P, Q ′ ) ≥ 0, that is, Q ′ stays above P .

-We now prove that P ≤ T Q ′ . Suppose there exist k, l, such that δ k (P, Q ′ ) > δ l (P, Q ′ ) with u k parent of u l . Since δ k (P, Q) ≤ δ l (P, Q), we have k < i ≤ l < j. Since a vertex u r is a descendant of u i if and only if i < r < j, the only possibility is l = i. Moreover, since u k is the parent of u i we have e k (P ) < e i (P ) = e, hence by the choice of e, δ k (P, Q

) < δ = δ i (P, Q). Hence, δ k (P, Q ′ ) = δ k (P, Q) ≤ δ i (P, Q) -1 = δ i (P, Q ′ ).
We reach a contradiction. Thus δ k (P, Q ′ ) ≤ δ l (P, Q ′ ) whenever u k is the parent of u l . By the induction hypothesis, this implies P ≤ T Q ′ . -It remains to prove that Q ′ is covered by Q in the Tamari lattice. It suffices to prove that i Q' j. Recall that for all r = 0, . . . , n -1, e r (P ) + 1 is the height of the vertex u r in the tree T . For all i < r < j, the vertex u r is a descendant of u i hence e r (P ) > e i (P ). Moreover, since the value of δ x (P, Q) is weakly increasing along the branches of T , δ r (P, Q) ≥ δ i (P, Q) for all i < r < j. Thus, for all i < r < j, e r (Q) = e r (P ) + δ r (P,

Q) > e i (Q) = e i (P ) + δ i (P, Q) and e r (Q ′ ) = e r (Q) -1 > e i (Q ′ ) = e i (Q) -1. It only remains to show that e j (Q ′ ) ≤ e i (Q ′ ).
The vertex u j is the first vertex not descendant of u i around T , hence e j (P ) ≤ e i (P ). Moreover δ j (P, Q) ≤ δ = δ i (P, Q). Furthermore, the equalities e i (P ) = e j (P ) and δ j (P ) = δ cannot hold simultaneously by the choice of i. Thus, e j (Q) = e j (P ) + δ j (P, Q) < e i (Q) = e i (P ) + δ i (P, Q) and e

j (Q ′ ) = e j (Q) ≤ e i (Q ′ ) = e i (Q) -1. u v 2 v 1 v 0 u ′ u ′′ T 2 T 1 T 3
Figure 18: The vertices u, u ′ = p 0 (u) and u ′′ = p 1 (u ′ ).

-We now prove that the property holds for any non-stack triangulation M without internal vertex of degree 3. If M has no separating triangle then, by the preceding point, the realizer R contains either a cw-or ccw-triangle. Suppose now that M has a separating triangle ∆. We can choose ∆ not containing any other separating triangle. In this case, the triangulation M ′ lying inside the triangle ∆ has no separating triangle and is not stack (since no internal vertex has degree 3). Let t 0 , t 1 , t 2 be the vertices of the triangle ∆. By definition, there are some vertices lying inside the triangle ∆. By Lemma 3.5, there is no tail incident to ∆ and lying inside ∆. Thus, for i = 1, 2, 3, the half-edges incident to the vertex t i and lying inside ∆ are heads. Moreover, the Schnyder condition implies that all the heads incident to t i have the same color. Furthermore, for each color i = 1, 2, 3 there is an i-head incident to one of the vertices t 0 , t 1 , t 2 , otherwise the vertices inside ∆ would not be connected to v i by an i-path. Hence, we can assume without loss of generality that for i = 1, 2, 3, the heads incident to t i and lying inside ∆ are of color i. Thus, the restriction R ′ of R to the triangulation lying inside ∆ is a realizer. By the preceding point, the realizer R ′ contains either a cw-or ccw-triangle, hence so do R.

-We now prove that the property holds for any non-stack triangulation M . Let R be a realizer of a non-stack triangulation M . Let M ′ be the triangulation obtained from M ′ by recursively deleting every internal vertex of degree 3. The triangulation M ′ is not stack and has no internal vertex of degree 3. Moreover, by Lemma 5.3, the restriction R ′ of the realizer R to the triangulation M ′ is a realizer. By the preceding point, the realizer R ′ contains either a cw-or ccw-triangle, hence so do R.

Given Theorem 5.1 and Proposition 5.2, the mapping Φ induces a bijection between the intervals of the Kreweras lattice and the stack triangulations. Stack triangulations are known to be in bijection with ternary trees (see for instance [START_REF] Zickfeld | Integer realizations of stacked polytopes[END_REF]), hence we obtain a new proof that the number of intervals in L K n is 1 2n+1 3n n . The rest of this section is devoted to the proof of Theorem 5.1. We first recall a characterization of the realizers which are both minimal and maximal. This characterization which is illustrated in Figure 19 follows immediately from the characterizations of minimality and of maximality given in [START_REF] Bonichon | An information upper bound of planar graphs using triangulation[END_REF]. The proof Lemma 5.5 of is based on the following result.

Lemma 5.6. Let R = (T 0 , T 1 , T 2 ) be a minimal and maximal realizer and let (P, Q) = Ψ(R). Let v 0 , u 0 , u 1 , . . . , u n = v 1 be the vertices of the tree T 0 in clockwise order. For all indices 0 ≤ i < j ≤ n, the relation i Q j holds if and only if p 1 (u i ) = u j . Moreover, in this case e j (Q) = e i (Q) if and only if p 0 (u i ) = p 0 (u j ) and there is no 1-edge whose head is incident to u j and whose tail appears before the first corner of u i . Proof: Let 0 ≤ i < j ≤ n such that p 1 (u i ) = u j .

• We first prove that for all index r = i + 1, . . . , j -1, the inequality e k (Q) > e i (Q) holds. Let u i1 , . . . , u is be the vertices on the 0-path from u i0 = u i to u is+1 = p 0 (u j ) (that is, p 0 (u i k ) = u i k+1 for all k = 0, . . . , s); see Figure 21. The characterization of minimal and maximal realizers given in Proposition 5.4 implies that p 1 (u i k ) = u j for all k = 1, . . . , s. For all k = 0, . . . , s, we denote by r k the index of the last descendant of u i k around T 0 and we denote r s+1 = j -1. Note that, for all k = 0, . . . , s, the vertices u r k +1 , . . . , u r k+1 are descendants of u i k+1 in T 0 . Hence, for all k = 0, . . . , s and all l = r k + 1, . . . , r k+1 , the inequality e l (P ) > e i (P ) -k holds (since for any index h the value e h (P ) + 1 is the height of the vertex u h is the tree T 0 ). By the minimality condition given by Proposition 4.3, none of the 1-tails available at u i is matched to one the vertices u i+1 , . . . , u r0 (since these vertices are descendants of u i ). Moreover, none of these available 1-tails is matched to one of the vertices u r0+1 , . . . , u j-1 or there would be a crossing with the 1-edge (u i , u j ) (see Figure 21). Hence, the 1-tails available at i are also available at all the vertices u i+1 , . . . , u j -1. Moreover, for all k = 1, . . . , s and all l = r k + 1, . . . , r k+1 the k 1-tails incident to each of the vertices u i0 , . . . , u i k-1 are available at the vertex u l . Thus, given Lemma 4.5, for all k = 0, . . . , s, for all l = r k + 1, . . . , r k+1 , δ l (P, Q) ≤ δ i (P, Q) + k. Thus, for all l = i + 1, . . . , j -1, the inequality e l (Q) = e l (P ) + δ l (P, Q) > e i (Q) = e i (P ) + δ i (P, Q) holds.

• It only remains to prove that the inequality e j (Q) ≤ e i (Q) holds and equality occurs if and only if p 0 (u i ) = p 0 (u j ) and there is no 1-edge whose head is incident to u j and whose tail appears before the first corner of u i .

-Since the realizer R is minimal the vertex p 0 (u j ) is an ancestor of u j in the tree T 0 (by Proposition 4.3). Hence, the inequality e j (P ) ≤ e i (P ) holds and equality occurs if and only if p 0 (u i ) = p 0 (u j ). We now compare the values of δ i (P, Q) and δ j (P, Q) which are the number of tails available at u i and at u j

  (a). The set D n of Dyck paths of length 2n can be ordered by the relation P ≤ S Q if P stays below Q. This partial order is in fact a distributive lattice on D n known as the Stanley lattice. The Hasse diagram of the Stanley lattice on D 3 is represented in Figure 2 (a).

Figure 1 :

 1 Figure 1: (a) A Dyck path. (b) A binary tree. (c) A non-crossing partition.

Figure 2 :

 2 Figure 2: Hasse diagrams of the Catalan lattices on the set D 3 of Dyck paths: (a) Stanley lattice, (b) Tamari lattice, (c) Kreweras lattice.

Figure 3 :

 3 Figure 3: (a) Exceedence of a Dyck path. (b) Differences between two Dyck paths.

Figure 4 :Figure 5 :

 45 Figure 4: Covering relations in (a) Stanley lattice, (b) Tamari lattice.

Figure 6 : 4 .

 64 Figure 6: Hasse diagram of the Tamari lattice L T 4 .

Figure 7 :

 7 Figure 7: A non-crossing partition and its image by the bijection θ.

Figure 8 : 4 .

 84 Figure 8: Hasse diagram of the Kreweras lattice L K 4 .

Figure 9 :

 9 Figure 9: Two examples of covering relation in the Kreweras lattice.

1 Figure 10 :

 110 Figure 10: A rooted triangulation (left) and one of its realizers (right).

Figure 11 :

 11 Figure 11: Edges coloration and orientation around a vertex in a realizer (Schnyder condition).

Figure 14 :

 14 Figure 14: Steps of the mapping Φ : (P, Q) → (T 0 , T 1 , T 2 ). (a) Step 1: build the tree T 0 . (b) Step 2: add the 1-tails and 1-heads. (c) Step 3: join the 1-tails and 1-heads together. (d) Step 4: determine the third tree T 2 .

Theorem 4 . 1 .

 41 The bijection Φ induces a bijection between the intervals of the Tamari lattice L T n and minimal realizers of size n.

Corollary 4 . 2 .

 42 The number of intervals in the Tamari lattice L T n is equal to the number 2(4n+1)! (n+1)!(3n+2)! of triangulations of size n.

Propositions 4 . 4 and

 44 Propositions 4.6 clearly imply Theorem 4.1. Hence, it only remains to prove Proposition 4.6.

Figure 19 :

 19 Figure 19: (a) Condition for a realizer to be both minimal and maximal: p 0 (p 1 (u)) = p 0 (u) or p 1 (p 0 (u)) = p 1 (u). (b) A minimal and maximal realizer and its image by Ψ.

Acknowledgments: The authors are very grateful to Mireille Bousquet-Mélou for pointing them to the enumerative result of Frédéric Chapoton and to Xavier Viennot for fruitful discussions and suggestions.

Intervals of the Kreweras lattice

In this section, we study the restriction of the bijection Φ to the Kreweras intervals.

Theorem 5.1. The mapping Φ induces a bijection between the intervals of the Kreweras lattice L K n and realizers of size n which are both minimal and maximal.

Before commenting on Theorem 5.1, we characterize the realizers which are both minimal and maximal. Recall that a triangulation is stack if it is obtained from the map reduced to a triangle by recursively inserting a vertex of degree 3 in one of the (triangular) internal face. An example is given in Figure 17.

Figure 17: A stack triangulation is obtained by recursively inserting a vertex of degree 3.

Proposition 5.2. A realizer R is both minimal and maximal if and only if the underlying triangulation M is stack. (In this case, R is the unique realizer of M .)

The proof of Proposition 5.2 uses the following Lemma.

Lemma 5.3. Let M be a triangulation and let R = (T 0 , T 1 , T 2 ) be one of its realizers. Suppose that M has an internal vertex v of degree 3 and let M ′ be obtained from M by removing v (and the incident edges). Then, the restriction of the realizer R to the triangulation M ′ is a realizer.

Proof: By Schnyder condition, the vertex v is incident to three tails and no head, hence it is a leaf in each of the trees T 1 , T 2 , T 3 . Thus, the tree condition is preserved by the deletion of v. Moreover, deleting v does not deprive any other vertex of an i-tail, hence the Schnyder condition is preserved by the deletion of v.

Proof of Proposition 5.2:

• We first prove that any realizer R of a stack triangulation M is minimal and maximal, that is, contains neither a cw-nor a ccw-triangle. We proceed by induction on the size of M . If M is reduced to the triangle, the property is obvious. Let M be a stack triangulation not reduced to the triangle. By definition, the triangulation M contains an internal vertex v of degree 3 such that the triangulation M ′ obtained from M by removing v is stack. By Lemma 5.3, the restriction of the realizer R to M ′ is a realizer. Hence, by the induction hypothesis, the triangulation M ′ contains neither a cw-nor a ccw-triangle. Thus, if C is either a cw-or a ccw-triangle of M , then C contains v. But this is impossible since v is incident to no head.

• We now prove that any realizer R of a non-stack triangulation M contains either a cw-or a ccw-triangle.

-We first prove that the property holds if M has no internal vertex of degree 3 nor separating triangle (a triangle which is not a face). It is known that if R contains a directed cycle, then it contains either a cw-or ccw-triangle (proof omitted; see [START_REF] Ossona De | Orientations bipolaires[END_REF]). Thus it suffices to prove that R contains a directed cycle. Let u be the third vertex of the internal triangle incident to the edge (v 1 , v 2 ). The vertex u is such that p 1 (u) = v 1 and p 2 (u) = v 2 (see Figure 18). The vertex u has degree at least 4 and is not adjacent to v 0 (otherwise one of the triangles (v 0 , v 1 , u) or (v 0 , v 2 , u) contains some vertices, hence is separating). Thus,

the other case is symmetrical). By Schnyder condition, the vertex u ′′ lies inside the cycle C made of the edges (v 0 , v 1 ), (v 1 , u) and the 0-path from u to v 0 . By Schnyder condition, the 1-path from u ′′ to v 1 stays strictly inside C. Let C ′ be the cycle made of the edges (v 1 , u), (u, u ′ ) and the 1-path from u ′ to v 1 . By Schnyder condition, the 2-path from u ′′ to v 2 starts inside the cycle C ′ , hence cut this cycle. Let v be the first vertex of C ′ on the 2-path from u ′′ to v 2 . The vertex v is incident to a 2-head lying inside C ′ , hence by Schnyder condition v = u. Thus, the cycle made of the edges (u, u ′ ), (u ′ , u ′′ ) and the 2-path from u ′′ to u is directed.

Proposition 5.4 ([2]

). A realizer R = (T 0 , T 1 , T 2 ) is both minimal and maximal if and only if for any internal vertex u, either p 0 (p 1 (u)) = p 0 (u) or p 1 (p 0 (u)) = p 1 (u).

Let R = (T 0 , T 1 , T 2 ) be a realizer of a triangulation M and let u, u ′ be two vertices distinct from v 0 and v 2 . We say that there is a 1-obstruction between u and u ′ if there is a 1-edge e such that the tail of e appears before the first corner of u while its head appears strictly between the first corner of u and the first corner of u ′ around the tree T 0 . This situation is represented in Figure 20. Using Proposition 5.4, we obtain the following property satisfied by realizers which are both minimal and maximal. Lemma 5.5. Let R = (T 0 , T 1 , T 2 ) be a minimal and maximal realizer and let (P, Q) = Ψ(R). Let v 0 , u 0 , u 1 , . . . , u n = v 1 be the vertices of the tree T 0 in clockwise order. Then, for all indices 0 ≤ i < j ≤ n, the relation i Q j holds if and only if the three following properties are satisfied:

(1) the vertex u j is an ancestor of u i in the tree

there is no 1-obstruction between u i and u j .

respectively (by Lemma 4.5).

-We first prove that any 1-tails available at u j is also available at u i . No 1-tail available at u j is incident to a vertex u l with r 0 < l < j or the corresponding 1-edge would cross the edge (u i , u j ) (see Figure 21). Moreover, the characterization of minimal and maximal realizers given in Proposition 5.4 implies that no 1-tail available at u j is incident to a vertex u l with i < l ≤ r 0 (since these vertices are descendants of u i ).

Hence, any the 1-tail available at u j is also available at u i .

-We now prove any 1-tail available at u i is available at u j except if the corresponding 1-head is incident to u j . Clearly, no 1-tail available at u i is such that the corresponding 1-head is incident to a vertex u l with r 0 < l < j or the 1-edge under consideration would cross the edge (u i , u j ) (see Figure 21). Since the realizer R is minimal, there is no 1-tail available at u i and such that the corresponding 1-head is a vertex u l with i < l ≤ r 0 (since these vertices are descendants of u i ). Hence, if a 1-tail available at u i is not available at u j , then the corresponding 1-head is incident to u j .

-Given Lemma 4.5, the preceding points imply that the inequality δ i (P, Q) ≤ δ j (P, Q) holds and equality occurs if and only if there is no 1-edge whose head is incident to u j and whose tail appears before the first corner of u i . Hence, e j (Q) = e j (P ) + δ j (P, Proof of Lemma 5.5:

• We suppose that i Q j and we want to prove the properties (1), ( 2) and ( 3).

(1) Since i Q j, there are indices

Hence u j is a ancestor of u i in the tree T 1 .

(2) Since e i k (P ) = e i (P ) for all k ≤ s, Lemma 5.6 implies p 0 (u i k ) = p 0 (u i ) for all k ≤ s. Moreover, p 1 (u is ) = u j , thus Proposition 5.4 implies that either p 0 (u

This situation is represented in Figure 22.

(3) We want to prove that there is no 1-obstruction between u i and u j . We suppose that the tail of a 1-edge e appears before the first corner of u i around T 0 and we want to prove that the corresponding 1-head h is not incident to a vertex u k with i < k < j. Clearly, if the 1-head h is incident to a vertex u k with i < k < j, then the vertex u k is either one of the vertices u i0 , u i2 , . . . , u is or one of their descendants (otherwise, the edge e would cross one of the 1-edges (u i0 , u i1 ), . . . ,(u is , u is+1 ); see Figure 22). Since

. . , u is . Moreover, since the realizer R is minimal, Proposition 4.3 implies that u k is not a (proper) descendant of one of the vertices i 0 , . . . , i s . Thus, the 1-head h is not incident to a vertex u k with i < k < j and e is not creating a 1-obstruction.

• We suppose that the vertices u i and u j satisfy the properties (1), ( 2) and ( 3) and want to prove that i Q j.

Observe first that by property (1), there are indices i 0 = i, i 1 , . . . , i s+1 = j such that p 1 (u i k ) = u i k+1 .

-We first prove that, for all k = 1, . . . , s, p 0 (u i k ) = p 0 (u i ); this situation is represented in Figure 22. Suppose the contrary and consider the first index k ∈ {1, . . . , s} such that p 0 (u i k ) = p 0 (u i ). In this case,

Since the realizer R is minimal and maximal, Proposition 5.4 implies that u i k = p 1 (p 0 (u i k-1 ) = p 1 (p 0 (u i )). Thus, the vertices u i k+1 , . . . , u is+1 are distinct from p 1 (p 0 (u i )) and are ancestors of p 0 (u i ) in the tree T 1 . In particular, u j = u is+1 = p 1 (p 0 (u i )), and p 0 (u j ) = p 0 (u i ). This contradicts Property (2).

-We now prove that for all index k = 1, . . . , s there is no 1-edge e whose head is incident to u i k and whose tail appears before the first corner of u k-1 . Suppose that such a 1-edge e exist. Observe that the 1-tail t of the edge e do not appear before the first corner of u i otherwise the edge e creates a 1-obstruction between u i and u j . Hence, the 1-tail t is incident either to one of the vertices u i0 , . . . , u i k-2 or to one of their descendants (otherwise, the edge e would cross one of the 1-edges (u i0 , u i1 ), . . . ,(u i k-2 , u i k-1 ); see Figure 22). Moreover, the 1-tail t is not incident to the vertices u i0 , . . . , u i k-2 , otherwise e would create a cycle in the tree T 1 . Lastly, since the realizer R is minimal, the 1-tail t is not incident to a descendant of u i l , l = 0, . . . , k -2.

Thus the 1-tail t does not appear before the first corner of u k-1 .

-By Lemma 5.6, the preceding points imply i k Q i k+1 and e i k (Q) = e i (Q) for all k = 0 . . . s. Thus, i Q j.

. . . . . . Proof of Theorem 5.1: Let P = N S α1 . . . N S αn and Q = N S β1 . . . N S βn be two Dyck paths and let R = (T 0 , T 1 , T 2 ) = Φ(P, Q). Let v 0 , u 0 , u 1 , . . . , u n = v 1 be the vertices of the tree T 0 in clockwise order.

• We suppose that P ≤ K Q and we want to prove that the realizer R is minimal and maximal. We proceed by induction on ∆(P, Q).

-We first suppose that ∆(P, Q) = 0, that is P = Q, and we want to prove that R is minimal and maximal. Let W be the word obtained by making the tour of T 0 and writing N (resp. S) when following an edge of T 0 for the first (resp. second) time and writing N (resp. S) when crossing a 1-tail (resp. 1-head). By definition of the mapping ω, the restriction of W to the letters N, S is ω(T 0 ) = N S α1 . . . N S αn N S. Moreover, for all i = 0, . . . , n there are α i 1-heads incident to the first corner of u i and one 1-head incident to its last corner. Thus, W = N (NS) α1 N S α1 (NS) α2 . . . N S αn-1 (NS) αn N S αn S. Between any letter N of W and the corresponding letter S there is exactly one letter N . Thus, for any internal vertex u, the vertex p 1 (u) is the first vertex appearing after the last corner of u around T 0 (that is, the first vertex which is not a descendant of u appearing after u around T 0 ). By Proposition 5.4, this implies that R is minimal and maximal.

-We now suppose that ∆(P, Q) > 0. In this case, there is a Dyck path Q ′ = N S β ′ 1 . . . N S β ′ n covered by Q in the Kreweras lattice and such that P ≤ K Q ′ . Since Q ′ is covered by Q is the Kreweras lattice, there are indices 0 ≤ i < j ≤ n such that i Q' j and β i = 0, β j = β ′ i + β ′ j and β k = β ′ k for all k = i, j (this situation is represented in Figure 23 (a)). By the induction hypothesis, the realizer R ′ = (T ′ 0 , T ′ 1 , T ′ 2 ) = Φ(P, Q ′ ) is both minimal and maximal. Moreover, by definition of the bijection Φ, the trees T 0 and T ′ 0 are the same. We use this fact to identify the vertices in the prerealizers PR = (T 0 , T 1 ) and PR ′ = (T 0 , T ′ 1 ) that we denote by v 0 , u 0 , u 1 , . . . , u n = v 1 in clockwise order around T 0 = T ′ 0 . We also denote by p ′ 1 (u) the parent of any vertex u in T ′ 1 .

• We first prove that for any vertex v,

5 implies that there is no 1-obstruction between u i and u j in the realizer R ′ . Thus, the β ′ i 1-heads incident to u i can be unglued from the first corner of u i and glued to the first corner of u j without creating any crossing in the prerealizer PR ′ = (T 0 , T ′ 1 ) (the transfer of the β ′ i 1-heads is represented in Figure 23 (b)). Let PR ′′ = (T 0 , T ′′ 1 ) be the colored map obtained. Clearly, PR ′′ = (T 0 , T ′′ 1 ) satisfies the tree condition (T ′′ 1 is a tree), the corner condition (the 1-heads are in first corners, the 1-tails are in last corners) and the order condition (any 1-tail appears before the corresponding 1-head around T 0 ), therefore PR ′′ is a prerealizer. Moreover, for all i = 0, . . . , n, there 20 are β i 1-heads incident to the vertex u i . Thus, by definition of the mapping Φ, the prerealizer PR ′′ is equal to PR = (T 0 , T 1 ). Since the only difference between the prerealizers PR ′ and PR is that the 1-heads incident to u i in PR ′ are incident to u j in PR, the property holds.

• We now prove that the realizer R = (T 0 , T 1 , T 2 ) is minimal and maximal. If the realizer R is not both minimal and maximal, there is a vertex u such that p 1 (u) = p 1 (p 0 (u)) and p 0 (p 1 (u)) = p 0 (u). Since the realizer R ′ is both minimal and maximal, either

). Thus, p 0 (p ′ 1 (u)) = p 0 (u) and p ′ 1 (u) = u i . Hence, p 0 (u i ) = p 0 (u) and p 1 (u) = u j . Moreover, since i Q' j, Lemma 5.5 implies that either p 0 (u

which is also forbidden. We reach a contradiction.

The prerealizer PR ′′ is obtained from PR ′ = (T 0 , T ′ 1 ) by moving β ′ i 1-heads from the first corner of u i to the first corner of u j .

• We suppose that the realizer R is minimal and maximal and we want to prove that P ≤ K Q. We proceed by induction on ∆(P, Q). If ∆(P, Q) = 0, then P = Q and the property holds. We suppose now that ∆(P, Q) > 0 and we denote by v 0 , u 0 , u 1 , . . . , u n = v 1 the vertices of the tree T 0 in clockwise order.

-We first prove that there are indices 0 ≤ k < i < j ≤ n such that p 0 (u k ) = p 0 (u i ) and p 1 (u k ) = u j . We suppose that no such indices exist and we want to prove that P = Q. Let u be an internal vertex. If u has a sibling in T 0 appearing after u around T 0 , then p 1 (u) is the first such sibling (since the indices i, j, k do not exist), else p 1 (u) = p 1 (p 0 (u)) (since the realizer R is minimal and maximal). Thus, for any vertex u, p 1 (u) is the first vertex appearing after the last corner of u around T 0 . Let W be the word obtained by making the tour of T 0 and writing N (resp. S) when following an edge of T 0 for the first (resp. second) time and writing N (resp. S) when crossing a 1-tail (resp. 1-head). By definition of the mapping ω, the restriction of W to the letters N, S is ω(T 0 ) = N S α1 . . . N S αn N S. Moreover, for all i = 0, . . . , n there are β i 1-heads in the first corner of u i and one 1-head in its last corner. Thus, W = N (NS) α1 N S β1 (NS) α2 . . . N S βn-1 (NS) αn N S βn S. Moreover, between any letter N of W and the corresponding letter S there is exactly one letter N . Thus,

-Let k < i < j be as described in the preceding point with k maximal and i minimal with respect to k (i.e. u i is the first sibling of u k appearing after u k around the tree T 0 ). This situation is represented in Figure 24.

Observe that no 1-head is incident to u i in the prerealizer PR = (T 0 , T 1 ) (see Figure 24), hence β i = 0,. Let H be the set of 1-heads incident to u j and such that the corresponding 1-tail is either incident to u k or to one of its descendants. One can unglue the 1-heads in H from the first corner of u j and glue them to the first corner of u i without creating any crossing (see Figure 24). Moreover, the resulting colored map PR ′ is easily seen to be a prerealizer that we denote by PR ′ = (T 0 , T ′ 1 ). Let R ′ be the realizer corresponding to the prerealizer PR ′ and let Q ′ = N S β ′ 1 . . . N S β ′ n be the Dyck path such that Φ(P, Q ′ ) = R ′ . By definition of Φ, we have β ′ i = |H|, β ′ j = β j -|H| and β ′ l = β l for all l = i, j. -We now prove that the realizer R ′ = Φ(P, Q ′ ) is minimal and maximal. By Proposition 5.4, we only need to prove that for every internal vertex u, either p 0 (p ′ 1 (u)) = p 0 (u) or p ′ 1 (p 0 (u)) = p ′ 1 (u), where p ′ 1 (u) 21 denotes the parent of u in the tree T ′ 1 . Suppose that there is a vertex u not satisfying this condition. Note first that u = u k since p 0 (p ′ 1 (u k )) = p 0 (u k ). Since the realizer R is minimal and maximal, either p 0 (p 1 (u)) = p 0 (u) or p 1 (p 0 (u)) = p 1 (u). Suppose first p 0 (p 1 (u)) = p 0 (u). In this case, the vertex u is a descendant of u k (otherwise, p 0 (p ′ 1 (u)) = p 0 (p 1 (u)) = p 0 (u)), and p ′ 1 (u) = u j (for the same reason). Therefore, p 0 (u j ) = p 0 (p 1 (u)) = p 0 (u) implies that u j is a descendant of u k . This is impossible since u j appears after u i around T 0 . Suppose now that p 1 (p 0 (u)) = p 1 (u). In this case, the vertex u is a descendant of u k (otherwise, p ′ 1 (p 0 (u)) = p 1 (p 0 (u)) = p 1 (u) = p ′ 1 (u)), and p 1 (p 0 (u)) = p 1 (u) = u j (for the same reason). Thus p ′ 1 (p 0 (u)) = p ′ 1 (u) = u i . We reach again a contradiction. -We now prove that the Dyck path Q ′ is covered by Q in the Kreweras lattice. By definition of the covering relation in the Kreweras lattice L K , it suffices to prove that i Q' j. Since the realizer R ′ is minimal and maximal, it suffices to prove that the conditions (1), ( 2) and (3) of Lemma 5.5 hold. Clearly, there is no 1-obstruction between the vertices u i and u j in the realizer R ′ (see Figure 24), hence condition (3) holds. Moreover, since the realizer R is minimal and maximal, either p 0 (u k ) = p 0 (u j ) or p 1 (p 0 (u k )) = u j . Thus, either p 0 (u i ) = p 0 (u j ) or p 1 (p 0 (u i )) = u j , hence condition (2) holds. Let i = i 1 , i 2 , . . . , i s be the indices of the siblings of u k appearing between u k and u j in clockwise order around T 0 (see Figure 24). By the choice of k, we get p 1 (u ir ) = u ir+1 for all r < s. Moreover, since the realizer R is minimal and maximal, either p 0 (u k ) = p 0 (u j ) or p 1 (p 0 (u k )) = u j . If either case, we get p 1 (u s ) = u j . Thus, p ′ 1 (u ir ) = p 1 (u ir ) = u ir+1 for all r < s, and p ′ 1 (u s ) = p 1 (u s ) = u j . Hence, u j is an ancestor of u i in the tree T ′ 1 , that is, condition (1) holds.

-The realizer R ′ = Φ(P, Q ′ ) is minimal and maximal, hence by the induction hypothesis P ≤ K Q ′ . Moreover, the path Q ′ is covered by Q in the Kreweras lattice. Thus, P ≤ K Q.

The vertices u k , u i , u j in the prerealizer PR = (T 0 , T 1 ) and PR ′ = (T 0 , T ′ 1 ).


domain: info shs

text:
Brigitte Trousse

Brigitte Trousse " Mygreenservices

"MyGreenservices, un projet en mode " living lab " piloté par Inria Sophia Antipolis relatif à la co-création de services environnementaux basés sur des capteurs (citoyens, Ville de Nice)"

Step 3: Defining the rules

Step 4: Collecting during the experiment and Pre-processing data inside the living Lab, mainly with FocusLab server With the objective to study ithe relevant of its generic IoT dedicated methods (D4.3.3 8).

Step 5: Sending the data to Elliot

«•

  MyGreenservices, un projet en mode « living lab » piloté par Inria Sophia Antipolis relatif à la co-création de services environnementaux basés sur des capteurs (citoyens, Ville de Nice)» Brigitte TROUSSE Chercheur Inria (Sophia Antipolis) & Représentante Inria du LL ICT Usage Lab & Coordinatrice coté français du projet CPCFQ 1 Institut national de recherche sous double tutelle ministérielle (Industrie et Recherche) • menant des recherches en Informatique et Mathématiques, sciences qui jouent un rôle central dans la « révolution numérique » actuelle • Devise Inria: « mettre l'excellence scientifique au service du transfert industriel et de la société » Brigitte Trousse

A

  d'un Living Lab? B. Exemple de MyGreenServices dans le cadre du projet européen ELLIOT (2010-2013) Co-conception avec les citoyens et professionnels de services verts projet européen FP7 ICT ELLIOT) Knowledge •Increase awreness on IoT paradigm •Update knowledge on the impact of air quality in daily lives Social •Generate enthusiasm for IoT based services •Improve interest for air quality measurement •Provide trustful services •Foster citizen involvement in air quality measurement •Encourage collaborative tagging and information sharing Business •Provide robust, relevant and customised environmental information •Provide easy to use and engaging green services •Change citizen behaviour towards a more sustainable lifestyle •Respect citizen privacy and confidentiality 4 types): Logs of MyGreenServices (2x16 days), Logs from gamified forum (2x16 days), Contents of the forum, IoT data (more than 4 milions of measures)

-

  Networking and openess = high (expe1) If %users inactive > 90% then S1.1= low If %users proactive > 2% then S1.1 = high S1.1 = Medium for the rest Thresholds: common rule Questionnaire Q2 (did MGS encourage you to participate and share knowledge?) And logs (frequency of connexions, statistics froom the forum) B7.1 Data protection : high To compute this property, we use two indirect questions: Q4/Q14: do you feel that your personal data are protected by MyGreenServices Q15: please specify To compute this property, we use the user answers to two indirect questions (Q7, Q9) from questionnaire Q4. •Q4/Q7: Would you recommend the portal to your friends? •Q4/Q9: Have you recommended MyGreenServices to your friends / acquaintances? Participants were aware of air quality awareness. The awareness can be considered as a first step in the behavior changing process. -Elaboration of a community of 50 active contributors (citizen/ professionals, cocreators/data producers).`3 seroius games, Importance of community management -UX Improvement of the second version MyGreenServices based on user feedback which is very helpful -Deployment of a complete living lab process involving citizen and applying Ksb model to measure experience at each step based on both qualitative and quantitative data -Environmental sensors/devices Challenges -New smart low cost environmental sensors and devices -More studies for UX measurement supports towards more advanced KPIs linked to advanced data analysis methods and linked to user IoT contexts -Make sustainable such a open data portal: experiments on new economic models with more sensors and more citizen-18 18

Présidente de l'association France Living Labs ,

	-Données environnementales (qualité de l'air, bruit) -> article atelier.net	vivant »
	• Impliquée dans la communauté nationale et européenne des living labs depuis 2007-2008. partenaire de l'association ENoLL (European Network of Living Labs) et co-responsbale

• Chargée de recherche Inria (Sophia Antipolis) en Intelligence Artificielle et en fouille de données appliquée à l'analyse des usages. Ex-responsable scientifique de l'équipe-projet AxIS www-sop.inria.fr/axis • Conduite du projet expérimental MyGreenServices en mode « laboratoire

du LL ICT usage Lab (1 ère vague ENoLL), membre du conseil d'adminsitration d'ENoLL • Coordinatrice coté français du projet CPCFQ Francophonie Living lab

A. Dimensions d'un Living Lab

B. Exemple de MyGreenServices dans le cadre du projet européen ELLIOT (2010ELLIOT ( -2013) )

KBS Results Experiment 2

Improvment of mainly 3 KSB properties (already high) B2.1 Reliability judgement of IoT data (100% instead of 75%) S1.1 Social networking and Openess (57% instead of 50%) B7.1 Data protection high as in expe 1

B.7 (suite) Exemples de résultats


Laisney Patrice
email: patrice.laisney@univ-amu.fr

A model for design activity in technological education

Keywords:

This paper discusses the design activities of students in secondary school in France. Computer Aided Design (CAD) tools are now part of the capacity of design professionals. It is therefore apt to reflect on their integration into the technological education. Has the use of graphical tools changed students' performance, and if so in what direction, in phase of seeking solutions through a design activity in a situation of teaching and learning?

The influence of CAD tools on professional design activities has been the subject of much research, but little has focused on student activity. Thus, analysing student work through an experimental device, we ask that students produce more solutions without using CAD tools. Do CAD activities encourage the modeling of a particular solution? Does drawing by hand before CAD activities support the production of various solutions and define them more precisely? Through the analysis of solutions developed by students, including traces of their activity (sketches, digital files), we test our hypotheses. Finally, these studies contribute to the understanding the teaching-learning of design process by proposing a model for design activity in technological education.

Context of the study

This paper completes a study published in 2014 [START_REF] Laisney | Role of graphics tools in the learning design process[END_REF]. It analysed design activities of students when faced with situations which require solving design problems. We focused on the role of CAD tools. More specifically, we considered the relationship between sketch realization (hand-drawing) and the use of CAD tools in the activity of students, especially in the early stages of research. Through analysis of drawings made by students as they use or do not use CAD tools, we aim to understand the creative process they employ.

The findings of this study relate to the fact that it is important to consider the introduction of these tools in promoting and facilitating the process of finding solutions. Our results confirm our hypothesis that hand-drawingas is the case for architects and designersfavours a broader search for solutions. The introduction of a second phase, CAD tools, provides a model of the object that is enriched due to the assistance the tools provide to students. As such, CAD is required in the process of object design.

The scope of this research and its findings is contingent to situations, problems and specific tools. To complete these results, we propose to test new situations and new tools. These studies contribute to the understanding the teaching-learning of design processes by proposing a model for design activity in technological education.

Model for analysing teaching of design activity

Creative design, a model for design activity

The general model of the design activity borrowed from [START_REF] Lebahar | Le dessin d'architecte : simulation graphique et re ́duction d'incertitude[END_REF] identifies three main stages to describe the process of architectural design. This general model of the cognitive aspects of design assimilates this activity in "resolution of badly defined problems" (Simon, 1991) and is characterized by "creative design". This notion of creativity develops through the mechanisms which it involves: exploration, generation of solutions and evaluation. But especially, this model takes into account an essential aspect of design activity, which concerns drawing in all its forms, including with the use of computing tools. The drawing is at the same time a representational medium and a tool of thought. More precisely, the sketch is considered as an integral part of creative design activities. It is defined as the dominating tool of thought for designers. Drawing is indeed seen by specialists in cognitive psychology [START_REF] Goël | Sketches of Thought[END_REF][START_REF] Schön | The reflexive practitionner : how profesionals think in action[END_REF] as a representation of mental activity, fixing the ideas in the first phases of design. But more than that, these drawn visual representations, which take several forms following the design phases, are recombined, modified and adapted. In Lebahar's model, graphic intermediaries appear in each of the stages:

The architectural diagnosis; in this first phase the architect seeks to identify and define the problem to be solved with regard to the constraints. She is then in the phase of exploration and the result will be a first graphic "base of simulation", a mix of notes and first drawings.

Research for the object through graphic simulation; from then on, the designer is going to work on generation of the solutions and their evaluation, in an incremental and iterative process. The drawing is going to be the privileged medium for this approach. It represents, as underlined by Lebahar, "the object in creation and the thought which creates it".

The establishment of the model of construction; in this phase the designer defines precise graphic representations, intended to make clear the solution for the builders. It is the "definitive decision" concerning the whole project (plans, precise drawings with a specified scale, etc.). [START_REF] Rabardel | Fonctionnalités et compétences dans la mise en oeuvre de systèmes graphiques techniques[END_REF] work on the implementation of graphics systems allows us to consider the analysis of graphics intermediaries involved in all three stages of Lebahar's model in a triple point functionally, semiotic and cognitive. The graphics are intermediate semiotic objects embedded in complex tasks that are functional to the task at hand. For example the shapes, the size, the subject, the structure or the function are among the aspects of the object useful for the designer action. This action raises various transformations operated on the subject (manufacturing, assembly) as well as mental operations of treatment of the information inherent to the resolution process of design problems. So, the drawing is a tool, an instrument which the subject uses to solve design problems. Design is so considered as a creative process of an object by progressive elaboration of a mental representation and a graphical representation of this object by the subject.

The role of the graphic tools [START_REF] Lebahar | Simulation activity of CAD draftsman during a design task[END_REF][START_REF] Lebahar | La conception en design industriel et en architecture. Désir, pertinence, coopération et cognition[END_REF] studied the place of the tools of CADin particular where articulation enters traditional drawing "by hand" and modeling by means of CAD software. "Whitefield showed, by comparing the works of industrial designers drawing by hand, in those produced by designers using a CAD system, that the first ones tended to investigate several possibilities of alternative solutions (strategy in width), while the second, more concentrated on their operations of modeling on computer, more got into detail and developed only a unique solution, during all the process (in-depth strategy)" (Lebahar, 2007, free translation, p. 146). According to Lebahar, "strategy in width" is rather connected to drawing by hand, while the in-depth strategy depends on the implementation of a CAD system.

Other research on the use of CAD software by industrial designers [START_REF] Asperl | How to teach CAD[END_REF][START_REF] Bonnardel | Design activities and creativity: from the analysis of cognitive factors to creative design support[END_REF][START_REF] Bonnardel | The Impact of Technology on Creativity in Design: An Enhancement[END_REF][START_REF] Chester | Teaching for CAD expertise[END_REF] shows that most CAD software do not really support creativity and are after all only a range of "computing techniques". First of all at the cognitive level, their methods of construction of a digital model tend to impose choices on the user and do not base themselves on the indistinct data of the design initial phases; this is reflected by the fact that the designer is forced at an early stage to handle specific geometric entities. The systems do not know how to manipulate vague, indistinct data characteristic of the problem-solving stage. At the contextual level, meanwhile, the modes of representation and interaction paradigms they offer do not place the user in an optimal context for creation.

We underlined the importance which holds the drawing in the design first phases as the "freedom" which it infers in the generation of the solutions to a problem, essentially thanks to an intuitive relationship with the designer. He goes away nevertheless in quite a different direction for the CAD software. At this stage, these studies show that while CAD tools are sophisticated, it is still beneficial to incorporate hand-drawings in the design activity, and especially in the teaching of technology.

From the point of view of the teaching-learning processes, [START_REF] Martin | Instrumentation, créativité en éducation artistique : Le cas de l'utilisation des outils de création numérique à l'école. (Doctorat)[END_REF] shows the contribution that can be made to schools by computing tools which aid the learning of drawing. The use of a digital tool can help the children while they copy a model, but does not improve their capacity to use their own internal model. At middle school level, Pektas and Erkip (2006) show the necessary level of "familiarization" with CAD tools to favour pupils' commitment in the design task, as well as the role of the representations. All these works agree on the fact that on one hand, the computing tools must be adapted to the teaching-learning process, and on the other, it is important to take into account the representations in every stage of the process.

To conclude, this study is interested in the development of design activities by pupils within the framework of technology education, which traditionally centers on the use of tools [START_REF] Brandt-Pomares | Technological Education : The issue of Information retrieval via the Internet[END_REF]. We propose to use a model built by considering a "grey area" in which the use of traditional design or CAD tools will help the process of finding solutions for pupils of middle school. This "grey area" corresponding to this particular time that students spend to use one drawing tool or another, we intend to understand. We think that creativity could be expressed through the variety of solutions developed by pupils.

At the methodological level, we propose to analyze the student activity. The analysis of the activity has been described in many studies [START_REF] Engeström | Developmental work research: Expanding activity theory in practice[END_REF]Leontiev, 1972;[START_REF] Vygotski | Thought and language[END_REF]. It's a way to look at what the teacher asks the students to work through and it offers insights to students and what pupils actually do.

Methodology

Our hypothesis is that use to drawing "by hand" favours the shaping of a bigger variety of solutions, while the use of the CAD tool particularly favours the deepening of a solution. As a result, the order in which the pupils would be advised to use these tools would also have an influence. Preceding CAD activity with an activity without recourse to computing tools should end in the production of valid solutions with regard to the constraints, more numerous, more varied and defined, with more precision at the end of the process. We therefore formalize the following three operational hypotheses: the pupils produce more solutions when not using the CAD tools (H1); the CAD favours the modeling of one solution in particular (H2); drawing by hand prior to the CAD activity favours the production process of solutions, several possibilities and more detail (H3).

Research plan

To test our hypotheses, we proposed a plan in which the pupils are requested to solve a "closed" problem. The teachers ask their pupils to fit out a space in house. The following instruction was given to the pupils: "Your work consists of proposing solutions to fit out a house by respecting the constraints of the specifications".

It should be noted that teachers, agreed to participate in the experiment, were asked to intervene as little as possible and avoid guiding the actions of pupils. The specifications given to students are as follows in We want to implement tools already used by teachers, which are recommended on the various sites of academic resources for technological education in France. Sweet Home 3D software, based on features inspired by traditional "intuitive" design, seems to offer a quick route to learning.

During the first session (modality 1), group A has to realize the design task by exclusively using the traditional method of drawing "by hand". Meanwhile, group B (modality 2) has to realize the same task by exclusively using the Sweet Home 3D software. During the second session (modality 3) both groups (A and B) are again confronted with the same task; that is, they have to pursue their research to find solutions, but this time they have the freedom to choose the graphic representation tools. To verify the impact that the pupils' familiarization with the software could have, we shall test two populations of pupils: those who "know it", because they have already used it within the framework of teaching realized by the teacher during the previous sessions, and those who "discover it".

Data and analysis indicators

The pupils made their graphic productions in the conditions of an ordinarily functioning middle school technology course of technology in the middle school, in class and with their usual teacher. At the end of sessions 1 and 2 and for each of modalities 1, 2 and 3, all the written and digital files produced by the pupils were collected.

We coded the various solutions according to the distribution and the choices to fit out these areas. From the choices made and their combination, we can determine all the solutions to this problem. Indeed, there are five solutions at least for the choice of distribution, four solutions to fit out the sleep area. Altogether, there are only twenty solutions. Illustration 1 proposes an example of a solution.

Illustration 1: Solution (to the left) and production (to the right)

Concerning the first hypothesis, the indicators are the numbers of productions and solutions represented by the pupils according to the tool used. Every paper or computer file developed by the pupils will be called a production, whatever its state of elaboration; that is, for example, even if it is a simple sketch or an incomplete digital model. Any production will be considered as an eligible solution; that is, a possible solution to the problem posed. An eligible solution is not necessarily at this stage a finalized solution to the problem. The numbers of productions and solutions so found during the three modalities of the experimental plan will allow the comparison between both groups A and B.

Concerning the second hypothesis, the indicator is the state of elaboration of the models represented by the pupils of both groups A and B, in three modalities. It will take into account the dimensional respect through manipulation of the scale of representation, the presence of decoration elements and material texture and the deepening of a unique solution deducted from the number of solutions developed by pupil.

Finally, concerning the third hypothesis, the indicators are of two kinds: the variety of the solutions developed in three modalities and graphic tools chosen and used in the third (free) modality between the sessions 1 and 2 for groups A and B. The variety of solutions will be measured with regard to the diversity of the proposals.

Results and data analysis Number of productions and solutions

Each production by a pupil is identified as the result of a work which ends in the realization of graphic. The productions retained as solutions include only the graphic tracks which represent a structural organization of distribution (Illustration 2).

Illustration 2: Solution with Sweet Home 3D (to the left) and by hand (to the right)

We counted the number of "solutions" produced by the pupils. The number of productions and solutions developed by all the pupils at the end of the first session appear in tables 4-6. The analysis of the number of productions and solutions confirms our first hypothesis, according to which the pupils produce more solutions without using the CAD tools. Indeed, on one hand table 4 shows that the pupils in group A realize more productions and solutions than the pupils in group B, while on the other, tables 5 and 6 show that this difference is not due to any pupils in particular but to a general tendency which concerns the majority of the pupils. The pupils in group A are capable of developing mainly more than a production (or solution) while the pupils of the group B do not rarely propose it any more of one. 4, that both groups are equivalent in terms of constitution (Khi2 = 0.028; Ddl = 1; p<0.05). More than that, we think it is not the group's composition that influences the number of productions and solutions, but the role played by the graphic intermediaries in the tasks. Nevertheless, we observe in tables 5 and 6 significant differences (Khi2 = 94,888 and Khi2 = 59,671; Ddl = 2; p<0.05) which we attribute to the task and the fact that in one case the pupils use the traditional method of drawing "by hand", while in the other they use CAD tools.

Difference between knowledge and discovery of the software

In order to look to the effects of pupils' level of familiarization with the software, we differentiated the population into two groups: those with prior experience of CAD and without.

Main results

For a 'closed' design problem, the exploration phase of the search for a solution grows rich by using drawing "by hand". Indeed, the use of traditional drawing in the early stages of finding solutions allows pupils to rough draw solutions to design problem. The pupils are all capable of producing drawings which allow the expression of their ideas. The results of the experiment tend to show that the use of traditional drawing before CAD tools are used allows the pupils to develop quantitatively more solutions. The Sweet Home 3D software seems to be considered early in the process of finding solutions. We note nevertheless that in this case, the exploration of a range of possiblities is reduced and the pupils aim at only one solution. The general model of the design activity proposed by [START_REF] Lebahar | Le dessin d'architecte : simulation graphique et re ́duction d'incertitude[END_REF][START_REF] Lebahar | La conception en design industriel et en architecture. Désir, pertinence, coopération et cognition[END_REF] is interesting to understand the design activity of architects and designers. However, it is not fully efficient to analyse the design activity of pupils in a context of teaching and learning in the classroom. We therefore propose a new model (Illustration 3) adapted from Lebahar to better understand the design process in

table 1 :

 1

	Use a container (12m x 2,5m x 2,6m)

Table 1 :

 1 SpecificationsWe analysed the productions realized by more than 300 pupils (aged 12) in France confronted with a design task. Table2presents the distribution of the tested population.

	Middle	1	2	3	4	5	6
	school
	Nb of divisions	1	2	3	2	2	4
	Nb of pupils	27	35	59	42	43	100
	Sweet		Prior experience			No prior experience
	Home 3D

Table 2 :

 2 Tested pupil populationSimilarly, classes are divided into two groups, A and B, which are balanced (no group level) and correspond to those established by the teacher who has responsibility within the institution.

	Table 3 presents the three working modalities corresponding to what the pupils had to make
	during two 50-minute sessions.
	Sessions	Group A	Group B
	1	Modality 1 "by hand"	Modality 2 "SketchUp"
	2	Modality 3 "freedom of choice"

Table 3 :

 3 Plan of the experimental device

Table 4 :

 4 Number of productions and solutions elaborated

	Session 1	Nb of pupils Productions	Solutions
	Group A	157	251	214
	Group B	149	154	128

Table 5 :

 5 Number of productions developed by pupil

	Session 1	1 production	2 productions + 2 productions
	Group A	70	83	4
	Group B	142	6	0
	Total	212	89	4

Table 6 :

 6 Number of solutions developed by pupil Our methodological precaution, with no level group, is confirmed by statistical test. Confirmatory tests show, as seen in table

Table 7 :

 7 Table7give the number of productions and solutions developed by the pupils in group B at the end of the first session. Number of productions and solutions developed by group B Proportionally, the number of productions and solutions realized by pupils in group B who discovered the software and those who know it is of the same order.

	Session 1	Nb of pupils Productions	Solutions
	(No prior experience)	94	98	78
	Group B
	(Prior experience)	55	57	51
	Total	149	155	129