Samuele Giraudo
email: samuele.giraudo@univ-mlv.fr

INTERVALS OF BALANCED BINARY TREES IN THE TAMARI LATTICE

Keywords: Balanced binary tree, Tamari lattice, Poset, Grammar, Generating series, Fixedpoint functional equation

We show that the set of balanced binary trees is closed by interval in the Tamari lattice. We establish that the intervals [T, T ′ ] where T and T ′ are balanced binary trees are isomorphic as posets to a hypercube. We introduce synchronous grammars that allow to generate tree-like structures and obtain fixed-point functional equations to enumerate these. We also introduce imbalance tree patterns and show that they can be used to describe some sets of balanced binary trees that play a particular role in the Tamari lattice. Finally, we investigate other families of binary trees that are also closed by interval in the Tamari lattice.

1. Introduction Acknowledgments 2. Preliminaries 2.1. Complete rooted planar binary trees 2.2. Balanced binary trees 2.3. The Tamari lattice 3. Closure by interval of the set of balanced binary trees 3.1. Rotations and balance 3.2. Construction of an imbalance invariant 3.3. The main result 4. Synchronous grammars 4.1. Definitions 4.2. Synchronous grammars and generating series 4.3. Examples 5. Imbalance tree patterns and balanced binary trees 5.1. Imbalance tree patterns 5.2. Minimal and maximal balanced binary trees in the Tamari lattice 6. The subposet of the Tamari lattice of balanced binary trees 6.1. Isomorphism between balanced binary tree intervals and hypercubes 6.2. Enumeration of balanced binary tree intervals 7. Intervals of other binary trees families in the Tamari lattice 7.1. Generalized balanced binary trees 7.2. Weight balanced binary trees 7.3. Binary trees with fixed canopy 7.4. Narayana binary trees References

Introduction

Binary search trees are used as data structures to represent dynamic totally ordered sets (see [START_REF] Aho | Foundations of Computer Science[END_REF][START_REF] Knuth | The Art of Computer Programming[END_REF][START_REF] Cormen | Introduction to algorithms[END_REF]). The algorithms solving classical related problems such as the insertion, the deletion or the search of a given element can be performed in linear time in terms of the depth of the encoding binary tree, and, if the binary tree is balanced, these operations can be made in logarithmic time in terms of the cardinality of the represented set. Recall that a binary tree is balanced if for each node x, the heights of the left and the right subtrees of x differ by at most one.

The algorithmic of balanced binary trees fundamentally relies on the so-called rotation operation. An insertion or a deletion of an element in a dynamic ordered set modifies the binary tree encoding it and can imbalance it. The efficiency of these algorithms comes from the fact that binary search trees can be rebalanced very quickly after the insertion or the deletion, using no more than two rotations [START_REF] Adelson-Velsky | An algorithm for the organization of information[END_REF].

Surprisingly, this operation appears in a different context since it defines a partial order on the set of binary trees of a given size. A binary tree T 0 is smaller than a binary tree T 1 if it is possible to transform T 0 into T 1 by performing a succession of right rotations. This partial order, known as the Tamari order [Tam62, [START_REF] Stanley | Enumerative Combinatorics II[END_REF][START_REF] Knuth | The Art of Computer Programming[END_REF], defines a lattice structure on the set of binary trees of a given size.

Since binary trees are naturally equipped by this order structure induced by rotations, and the balance of balanced binary trees is maintained doing rotations, we would like to investigate if balanced binary trees play a particular role in the Tamari lattice. Our goal is to combine the two points of view of the rotation operation. Computer trials show that the intervals [T, T ′ ] where T and T ′ are balanced binary trees are only made of balanced binary trees. The main goal of this paper is to prove this property. As a consequence, we give a characterization on the shape of these intervals and, using grammars allowing the generation of tree-like structures, enumerate these ones.

This article is organized as follows. In Section 2, we set the essential notions about binary trees and balanced binary trees, and we give the definition of the Tamari lattice in our setting. Section 3 is devoted to establish the main result: The set of balanced binary trees is closed by interval in the Tamari lattice. In Section 4, we define synchronous grammars. This new sort of grammars allows to generate sets of tree-like structures and gives a way to obtain a fixed-point functional equation for the generating series enumerating these. In Section 5, we introduce a notion of binary tree pattern, namely the imbalance tree patterns, and a notion of pattern avoidance. We also define subsets of balanced binary trees whose elements hold a particular position in the Tamari lattice. These sets can also be defined as the balanced binary trees avoiding some given imbalance tree patterns. In Section 6, we look at balanced binary tree intervals and show that they are, as posets, isomorphic to hypercubes. Encoding balanced binary tree intervals by kind of tree-like structures, and by constructing the synchronous grammar generating these trees, we give a fixed-point functional equation satisfied by the generating series enumerating balanced binary tree intervals. We do the same for maximal balanced binary tree intervals. Finally, in Section 7, we investigate three other families of binary trees that are closed by interval in the Tamari lattice: The weight balanced binary trees, the binary trees with a given canopy and the k-Narayana binary trees. We also look at a generalization of balanced binary trees and prove, among other, that the set of usual balanced binary trees is the only set among this generalization that is both closed by interval in the Tamari lattice and the subposet of the Tamari lattice induced by it has nontrivial intervals. This paper is an extended version of [START_REF] Giraudo | Balanced binary trees in the Tamari lattice[END_REF] where only Sections 2, 3, 5 and 6 were developed.

Acknowledgments. The author would like to thank Florent Hivert for introducing him to the problem addressed in this paper, and Jean-Christophe Novelli and Florent Hivert for their invaluable advice and their improvement suggestions. The computations of this work have been done with the open-source mathematical software Sage [S + 10].

Preliminaries

2.1. Complete rooted planar binary trees. In this article, we consider complete rooted planar binary trees and we call these simply binary trees. Recall that a binary tree T is either a leaf (also called empty tree) denoted by ⊥, or a node that is attached through two edges to two binary trees, called respectively the left subtree and the right subtree of T . The (unique) binary tree which has L as left subtree and R as right subtree is denoted by L ∧ R. Let also T n be the set of binary trees with n nodes and T be the set of all binary trees. We use in the sequel the standard terminology (i.e., parent, child, ancestor, path, etc.) about binary trees [START_REF] Aho | Foundations of Computer Science[END_REF].

In our graphical representations, nodes are represented by circles , leaves by squares , and edges by segments or . Besides, we shall represent arbitrary subtrees by big squares like , and arbitrary paths by zigzag lines .

Recall that the infix reading order of the nodes of a binary tree T consists in recursively visiting its left subtree, then its root, and finally its right subtree. We say that a node x of T is the leftmost node if x is the first visited node in the infix order. We also say that a node y is to the right w.r.t. a node x if x appears strictly before y in the infix order and we denote that by x T y. We extend this notation to subtrees, saying that a subtree S of T is to the right w.r.t. a node x if for all nodes y of S we have x T y. For example, consider the binary tree T depicted in Figure 1. The sequence (a, b, c, d, e, f, g, h) is the sequence of all nodes of T visited in the infix order. Hence, a is the leftmost node of T and we have, among other, a T b and c T f . Consider the subtree S of root g. It contains the nodes e, f , g and h. Hence, we have a T S, b T S, c T S and d T S. However, we neither have the relation e T S since S contains e, nor the relation f T S since S contains e and f T e does not hold.

2.2. Balanced binary trees. If T is a binary tree, we shall denote by h(T ) its height, that is the length of the longest path connecting its root to one of its leaves. More formally,

(2.1) h(T ) := 1 + max{h(L), h(R)} if T = L ∧ R, 0 otherwise (T =⊥).
For example, we have h(⊥) = 0, h = 1, and h = 2.

Let us define the imbalance mapping i T which associates an element of Z with a node x of T . It is defined by

(2.2) i T (x) := h(R) -h(L),
where L (resp. R) is the left (resp. right) subtree of x. For example, the imbalance values of the nodes of the binary tree T shown in Figure 1

satisfy i T (a) = 2, i T (b) = 0, i T (c) = -1, i T (d) = 0, i T (e) = 0, i T (f ) = -1, i T (g) = -1 and i T (h) = 0. A node x is balanced if (2.3) i T (x) ∈ {-1, 0, 1}.
Balanced binary trees form a subset of T composed of binary trees which have the property of being balanced:

Definition 2.1. A binary tree T is balanced if all nodes of T are balanced.

Let us denote by B n the set of balanced binary trees with n nodes (see Figure 2 for the first sets) and B the set of all balanced binary trees. The number of balanced binary trees enumerated according to their number of nodes is Sequence A006265 of [Slo] 2.3. The Tamari lattice. The Tamari lattice can be defined in several ways depending on which kind of Catalan object (i.e., objects in bijection with binary trees) the order relation is defined. The most common definitions are made on integer vectors with some conditions [START_REF] Stanley | Enumerative Combinatorics II[END_REF], on forests and binary trees [START_REF] Knuth | The Art of Computer Programming[END_REF], and on Dyck paths [START_REF] Bernardi | Catalan's intervals and realizers of triangulations[END_REF]. We give here the most convenient definition for our use. First, let us recall the right rotation operation:

Definition 2.2. Let T 0 be a binary tree and y be a node of T 0 having a nonempty left subtree. Let S 0 := (A ∧ B) ∧ C be the subtree of root y of T 0 and T 1 be the binary tree obtained by replacing S 0 by A ∧ (B ∧ C) (see Figure 3). Then the right rotation of root y sends T 0 to T 1 .

We write T 0 ⋌ T 1 if T 1 can be obtained by a right rotation from T 0 . We call the relation ⋌ the partial Tamari relation. Note that the application of a right rotation to a binary tree does not change the infix order of its nodes. In the sequel, we mainly talk about right rotations, so we call these simply rotations. We are now in a position to give our definition of the Tamari order. (2.5)

T 0 ⋌ T 1 ⋌ • • • ⋌ T k-1 ⋌ T k .
The Tamari relation is an order relation. Indeed, ≤ T is reflexive and transitive by definition. To prove that ≤ T is antisymmetric, consider the statistic φ : T → N where φ(T ) is the sum for all nodes x of T of the number of the nodes constituting the right subtree of x. It is plain that if T 0 ⋌ T 1 then φ(T 0 ) < φ(T 1 ), showing that ≤ T is antisymmetric.

For n ≥ 0, the set T n with the order relation ≤ T defines a lattice, namely the Tamari lattice (see [START_REF] Huang | Problems of associativity: A simple proof for the lattice property of systems ordered by a semi-associative law[END_REF]). We denote by T n := (T n , ≤ T ) the Tamari lattice of order n (see Figure 4 for some examples). Let T 1 be the binary tree obtained by this rotation, y be the root of T 0 and x be the left child of y in T 0 (see again Figure 3, considering now that y is the root of T 0 and x is the root of T 1 ). Note first that the imbalance values of the nodes of the subtrees A, B and C are not modified by this rotation. Indeed, only the imbalance values of x and y are changed. Since T 0 is balanced, we have i T0 (x) ∈ {-1, 0, 1} and i T0 (y) ∈ {-1, 0, 1}. Thus, the pair (i T0 (x), i T0 (y)) can take nine different values. Here follows the list of the imbalance values of x and y in T 0 and T 1 expressed as (i T0 (x), i T0 (y)) -→ (i T1 (x), i T1 (y)):

(R1) (-1, -1) -→ (1, 1), (R2) (0, -1) -→ (1, 0), (R3) (0, 0) -→ (2, 1), (R4) (1, -1) -→ (2, 0), (R5) (1, 0) -→ (3, 1), (R6) (-1, 0) -→ (2, 2), (R7) (-1, 1) -→ (3, 3), (R8) (0, 1) -→ (3, 2), (R9) (1, 1) -→ (4, 2).
Let us gather these nine sorts of rotations into three different groups, taking into account if the nodes x and y are balanced in T 1 .

• Cases (R1) and (R2), where x and y stay balanced are called conservative balancing rotations; • Cases (R3), (R4) and (R5), where y stays balanced but x not are called simply unbalancing rotations; • Cases (R6), (R7), (R8) and (R9) where x and y are both unbalanced are called fully unbalancing rotations.

This leads to the following properties.

Proposition 3.1. Let T 0 and T 1 be two balanced binary trees such that T 0 ⋌ T 1 . Then, T 0 and T 1 have the same height.

Proof. Since T 0 and T 1 are both balanced, the rotation modifies a subtree S 0 of T 0 such that the imbalance values of the root y of S 0 , and of the left child x of y, satisfy (R1) or (R2). Let S 1 be the binary tree obtained by the rotation of root y from S 0 . Computing the height of S 0 and S 1 , we have h(S 0 ) = h(S 1 ). Thus, since a rotation modifies a binary tree locally, we have h(T 0 ) = h(T 1 ).

Lemma 3.2. Let T 0 be a balanced binary tree and T 1 be an unbalanced binary tree such that T 0 ⋌ T 1 . Then, there exists a node z in T 1 such that i T1 (z) ≥ 2 and the left subtree and the right subtree of z are both balanced.

Proof. Let y be the node of T 0 which is the root of the rotation that transforms T 0 into T 1 and x its left child in T 0 . If this rotation is a simply unbalancing rotation, it satisfies (R3), (R4) or (R5), and the node z := x satisfies the lemma. If this rotation is a fully unbalancing rotation, it satisfies (R6), (R7), (R8) or (R9), and the node z := y of T 1 agrees with the conclusion of the lemma.

Lemma 3.3. Let T 0 be a binary tree and y be a node of T 0 such that all subtrees to the right w.r.t. y are balanced. Then, if the binary tree T 1 is obtained from T 0 by a rotation of root y, all subtrees of T 1 to the right w.r.t. y are balanced.

Proof. Since the rotation operation does not modify the infix order of the nodes and by definition of the relation , if a subtree S is to the right w.r.t. y in T 1 , then S is also to the right w.r.t. y in T 0 . By hypothesis, S is balanced in T 0 , and therefore, it is also balanced in T 1 .

Construction of an imbalance invariant.

Let T be a binary tree, x be a node of T and y be the leftmost node of the subtree of root x in T . We say that x is a witness of imbalance if the following three conditions hold (see Figure 5):

y x ℓ x i T (x) ≥ 2 S y ∈ B S x ℓ ∈ B S x ∈ B T = Figure 5
. The node x is a witness of imbalance of T . Note that the left subtree of y is empty and thus S y has 0 or 1 node.

(W1) The imbalance value of x is greater than or equal to 2; (W2) The left subtree of x is balanced; (W3) The subtrees of T which are to the right w.r.t. y are balanced.

Remark 3.4. If a binary tree T has a witness of imbalance, (W1) guarantees that T is unbalanced.

The aim of this section is to define an additional property that x and y must satisfy to ensure that any binary tree T ′ such that T ≤ T T ′ has still a witness of imbalance. In this way, by showing that T ′ also satisfies this additional property, we will prove that it is impossible to rebalance T through rotations.

Let us already give this property. In what follows, the concepts necessary to understand it will be defined. If y satisfies condition (CC) the height word of the node y is admissible, then, we say that T satisfies the conservation condition. Besides, we say that T has an imbalance invariant if T has a witness of imbalance satisfying the conservation condition.

3.2.1. Height words. Let T be a binary tree, x 1 be a node of T , (x 1 , x 2 , . . . , x ℓ ) be the sequence of all ancestors of x 1 whose are to the right w.r.t. x 1 and ordered from bottom to top, and (S xi ) 1≤i≤ℓ be the sequence of the right subtrees of the x i (see Figure 6). The word u 1 . . . u ℓ of N * defined by u i := h(S xi ) is called the height word of x 1 and denoted by hw T (x 1 ). It is convenient to set hw T (x) := ǫ whenever x is not a node of T . See Figure 7 for some examples of height words associated with some nodes of a binary tree.

3.2.2. Admissible words. Let u := u 1 . . . u n be a word. Let us denote by ℓ(u) the length n of u.

Let Θ : N 2 → N be the rewriting rule defined by

(3.1) Θ(a.b) := max{a, b} + 1 if b -a ∈ {-1, 0, 1}, max{a, b} otherwise.
Note that if A ∧ B is a balanced binary tree, then Θ(h(A). h(B)) = h(A ∧ B). We shall use this simple observation to establish the main result of this section. This rewriting rule is extended to words of N * by Θ(u) := Θ(u 1 .u 2 ).u 3 . . . u ℓ(u) . If 0 ≤ i ≤ ℓ(u) -1, denote by Θ i (u) the iterated application of Θ defined by

(3.2) Θ i (u) := u if i = 0, Θ Θ i-1 (u) otherwise.
Definition 3.5. A word u ∈ N * is admissible if either ℓ(u) ≤ 1 or all words v of the set

(3.3) Θ i (u) : 0 ≤ i ≤ ℓ(u) -2 satisfy v 1 -1 ≤ v 2 .
The set of admissible words is denoted by A. To check if a word u is admissible, iteratively compute the elements of the set (3.3) following (3.2), and check for each of these the inequality of the previous definition. For example, by denoting by Θ -→ the rewriting rule Θ, we can check that u := 00122 is admissible. Indeed, we have

(3.4) 00122 Θ -→ 1122 Θ -→ 222 Θ -→ 32,
and at each step, the condition u 1 -1 ≤ u 2 holds. The word 1234488 is also admissible:

(3.5) 01233778 Θ -→ 2233778 Θ -→ 333778 Θ -→ 43778 Θ -→ 5778 Θ -→ 778 Θ -→ 88.
On the other hand, 3444 is not admissible since we have If u is an nonempty word, let us denote by Ω(u) the height of u, that is the one-letter word Θ ℓ(u)-1 (u). For example, we have Ω(00122) = 4, Ω(01233778) = 9 and Ω(3444) = 6. Note that one can deduce from Definition 3.5 that a word u ∈ N * of length greater than 1 is admissible if and only if for each decomposition u = v.a.w where v ∈ N + , a ∈ N and w ∈ N * , one has Ω(v) -1 ≤ a.

3.2.3. Some properties of admissible words. Let us establish three lemmas on admissible words that will be helpful later to prove our main result. Lemma 3.6. If u is an admissible word, then, for all 1 ≤ i ≤ ℓ(u) -1, one has u i -1 ≤ u i+1 .

Proof. Assume that u is of the form u = v.u i .u i+1 .w with v, w ∈ N * and u i -1 > u i+1 . Since Θ changes a word a.b ∈ N 2 into a letter c ∈ N no smaller than both a and b, we have Ω(v.u i ) ≥ u i . That implies that Ω(v.u i )-1 > u i+1 , showing that u / ∈ A and contradicting the hypothesis.

Lemma 3.7. All prefixes and suffixes of an admissible word are admissible.

Proof. It is immediate, by definition, that all prefixes of an admissible word also are admissible. Let u ∈ A such that ℓ(u) ≥ 2, and w be a nonempty suffix of u. Assume that w / ∈ A. Hence, w is of the form w = x.a.y where x ∈ N + , a ∈ N, y ∈ N * and Ω(x) -1 > a. The word u is of the form u = v.x.a.y where v ∈ N * . Since Θ changes a word a.b ∈ N 2 into a letter c ∈ N no smaller than both a and b, we have Ω(v.x) ≥ Ω(x). Therefore, we have Ω(v.x) -1 > a, showing that u / ∈ A and contradicting the hypothesis. Lemma 3.9. Let T be a balanced binary tree, x be a node of T , and u be the height word of x.

Then u is admissible and Ω(u) ≤ h(T ).

Proof. We proceed by structural induction on the set of balanced binary trees. The lemma is true for the single element T of the set B 1 since by denoting x its node, we have u = hw T (x) = 0 which is admissible and satisfies 0 = Ω(u) ≤ h(T ) = 1. Assume that T = L ∧ R. If x is a node of R, we have u = hw T (x) = hw R (x), and by induction hypothesis, u ∈ A and Ω(u) ≤ h(R). Since h(R) < h(T ), the lemma is satisfied.

If x is a node of L, we have u = hw T (x) = hw L (x). h(R). Since T is balanced, h(R) -h(L) ∈ {-1, 0, 1}, and by induction hypothesis, Ω (hw L (x)) ≤ h(L). Hence, Ω (hw L (x)) -1 ≤ h(R). Moreover, again by induction hypothesis, hw L (x) ∈ A, and hence, u ∈ A. Finally, since Ω(u) ≤ h(R) + 1 ≤ h(T ), the lemma is satisfied.

Lemma 3.10. Let T be a binary tree and y be a node of T such that hw T (y) is admissible and all subtrees of the sequence (S yi ) 1≤i≤ℓ are balanced. Then, for all node x of T such that y T x, the word hw T (x) is admissible.

Proof. If x is an ancestor of y, since y T x, y belongs to the left subtree of x. Hence, hw T (x) is a suffix of hw T (y), and by Lemma 3.7, hw T (x) ∈ A.

Otherwise, let S be the subtree of T such that x is a node of S and the parent of the root of S in T is an ancestor of y. The height word of y is of the form hw T (y) = u. h(S).v where u, v ∈ N * . Since y T S, by hypothesis S is balanced and thus by Lemma 3.9, hw S (x) ∈ A. Thanks to Lemma 3.7, h(S).v ∈ A, and since, by Lemma 3.9, Ω(hw S (x)) ≤ h(S), the word hw T (x) = hw S (x).v is admissible too.

3.3. The main result. We give and prove in this section the main result of this paper. For that, we show through the next two Propositions, that the imbalance invariant defined in Section 3.2 is appropriate to prove that all successors of a binary tree obtained from a balanced binary tree by an unbalancing rotation cannot be rebalanced.

Before going further, let us give one example of a binary that satisfies the conservation condition. Let us consider the following binary tree T :

y S y x S x S x1 . (3.7)
One observes that the imbalance value of the node x is 2, that the left subtree of x is balanced, and that the subtrees to the right w.r.t. y, namely S y , S x , and S x1 are balanced. Hence, x satisfies (W1), (W2), and (W3) and is a witness of imbalance of T . Moreover, one has hw T (y) = 144. Since 144 is an admissible word, T satisfies the conservation condition (CC) and hence, has an imbalance invariant.

Proposition 3.11. Let T 0 be a balanced binary tree and T 1 be an unbalanced binary tree such that T 0 ⋌ T 1 . Then, T 1 has an imbalance invariant.

Proof. Let S 0 := (A ∧ B) ∧ C be the subtree of T 0 modified by the rotation transforming T 0 into T 1 and S 1 := A ∧ (B ∧ C) be the resulting subtree in T 1 . Denote by r the root of this rotation and by q the left child of r in S 0 (see Figure 8). We shall exhibit, in the rest of this proof, a witness of imbalance x of T 1 that satisfies the conservation condition. By Lemma 3.2,

r q A B C T 0 = r q A B C = T 1 Figure 8.
The initial case, an unbalancing rotation at root r is performed into the balanced binary tree T 0 .

q or r is unbalanced in T 1 and has a positive imbalance value. Therefore, we have to consider two cases, depending on the sort of unbalancing rotation which transforms T 0 into T 1 .

Case 1: If it is a simply unbalancing rotation, set x := q and y as the leftmost node of the subtree of root q in T 1 . Since i T1 (x) ≥ 2, (W1) checks out. Moreover, since T 0 is balanced, by Lemma 3.3, the subtrees to the right w.r.t. r are balanced in T 1 , and since A and B ∧ C are balanced, (W2) and (W3) are established. Finally, since T 0 is balanced, Lemma 3.9 shows that hw T0 (y) is admissible. We have

(3.8) hw T0 (y) = hw A (y). h(B). h(C).v,
where v ∈ N * . Besides, we have

(3.9) hw T1 (y) = hw A (y). h(B ∧ C).v = hw A (y).Θ(h(B). h(C)).v, since B ∧ C is balanced. Hence, we have hw T1 (y) = hw A (

y).Θ(h(B). h(C).v), and since hw A (y). h(B). h(C)

.v is admissible, by Lemma 3.8, hw T1 (y) also is. That shows that (CC) is satisfied.

Case 2: Assume that the rotation is fully unbalancing. Set x := r and y as the leftmost node of the subtree of root r in T 1 . Since i T1 (x) ≥ 2, (W1) checks out. Moreover, since T 0 is balanced, by Lemma 3.3, the subtrees to the right w.r.t r are balanced in T 1 , and since B is balanced, (W2) and (W3) are established. Finally, since T 0 is balanced, Lemma 3.9 shows that hw T0 (y) is admissible. We have

(3.10) hw T0 (y) = hw B (y). h(C).v, where v ∈ N * . Besides, (3.11) hw T1 (y) = hw B (y). h(C).v,
and hence hw T1 (y) = hw T0 (y), so that (CC) checks out.

Thereby, we have shown that there exists a node x in T 1 that is a witness of imbalance and satisfies the conservation condition in all case.

Proposition 3.12. Let T 1 and T 2 be two binary trees such that T 1 ⋌T 2 and T 1 has an imbalance invariant. Then, T 2 has an imbalance invariant.

Proof. Let x be a witness of imbalance of T 1 that satisfies the conservation condition, y be the leftmost node of the subtree of root x in T 1 , r be the root of the rotation that transforms T 1 into T 2 , and q be the left child of r in T 1 . For all relative position of r w.r.t. y in T 1 , we shall exhibit a witness of imbalance x ′ of T 2 that satisfies the conservation condition. If necessary, we shall also exhibit the node y ′ of T 2 that is the leftmost node of the subtree of root x ′ .

There are exactly three cases to consider. Note first that since one can perform a rotation of root r, r has a left son, and since y has no left son, r = y. The first case occurs when r is to the left w.r.t. y (Case 1). Otherwise, when r is to the right w.r.t. y, the second case occurs when r is a strict ancestor of y (Case 2). In this case, y is in the left subtree of r. Otherwise, when r is to the right w.r.t. y and r is not a strict ancestor of y, the third case occurs (Case 3). In this last case, the subtree of root r is to the right w.r.t. y.

Case 1: If r is to the left w.r.t. y, the rotation of root r does not modify any of the subtrees to the right w.r.t. y. Thus, x ′ := x is a witness of imbalance of T 2 and satisfies the conservation condition.

Case 2: If r and q are both ancestors of y in T 1 , set C as the right subtree of r and B as the right subtree of q in T 1 . In this case, T 2 is obtained from T 1 by replacing the subtrees B and C by B ∧ C as shown in Figure 9. We have now three possibilities whether B ∧ C is balanced and r is an ancestor of x in T 1 . Case 2.2: If B ∧ C is balanced and r is an ancestor of x in T 1 , set x ′ := x and y ′ := y. One clearly has i T2 (x ′ ) ≥ 2, so that (W1) is satisfied. Moreover, since the left subtree of x ′ in T 2 is not modified by the rotation and hence stays balanced, since B ∧ C is balanced, and since by Lemma 3.3, all subtrees to the right w.r.t. r are balanced in T 2 , (W2) and (W3) check out. Finally, since x satisfies the conservation condition in T 1 , hw T1 (y) ∈ A and we have

(3.13) hw T1 (y) = u. h(B). h(C).v, where u, v ∈ N * . Besides, (3.14) hw T2 (y ′ ) = u. h(B ∧ C).v = u.Θ(h(B). h(C)).v,
since B ∧ C is balanced. Thus, by Lemma 3.8, hw T2 (y ′ ) ∈ A, so that (CC) is satisfied.

Case 2.3: If B ∧ C is balanced and r is a descendant of x in T 1 , we have two possibilities whether q is balanced in T 2 . If it is, set x ′ := x. By Proposition 3.1, the left subtree of x ′ stays balanced in T 2 and i T2 (x ′ ) ≥ 2. Thus, (W1) and (W2) are satisfied. Moreover, by Lemma 3.3, all subtrees to the right w.r.t. x ′ stay balanced in T 2 so that (W3) checks out. Otherwise, if q is not balanced, set x ′ := q. Since the left subtree of x is balanced in T 1 , by Lemma 3.2, i T2 (x ′ ) ≥ 2, and (W1) holds. Moreover, q belongs to the left subtree of x in T 1 which is balanced, and hence, the left subtree of q is balanced in T 2 , so that (W2) holds. Since B ∧ C is balanced and by Lemma 3.3, (W3) also holds. Set now for both cases y ′ as the leftmost node of the subtree of root x ′ in T 2 . The word hw T2 (y ′ ) satisfies exactly same conditions as in the previous case, so that (CC) is satisfied.

Case 3: If the subtree S 1 := (A ∧ B) ∧ C of root r in T 1 is to the right w.r.t. y, set S 2 := A ∧ (B ∧ C)
as the subtree of T 2 obtained by the rotation at root r which transforms T 1 into T 2 (see Figure 10). We have now two cases to consider whether S 2 is balanced or not.

Case 3.1: If S 2 is balanced, by Proposition 3.1, h(S 2 ) = h(S 1 ), and by setting x ′ := x and y ′ := y one has i T2 (x ′ ) = i T1 (x) so that (W1) is satisfied. Moreover, the left subtree of x ′ stays balanced, and by Lemma 3.3, the subtrees to the right w.r.t. x ′ in T 2 also, so that (W2) and (W3) check out. Finally, x ′ also satisfies (CC) in T 2 since hw T2 (y ′ ) = hw T1 (y).

Case 3.2: If S 2 is not balanced, by Proposition 3.11, there exists a node x ′ in S 2 which is a witness of imbalance satisfying the conservation condition, locally in S 2 . Therefore, x ′ satisfies (W1) and (W2) in T 2 . It also satisfies (W3) in T 2 since, by Lemma 3.3, the subtrees of T 2 to the right w.r.t. r stay balanced. It remains to prove that x ′ satisfies the conservation condition in the whole binary tree T 2 . Set y ′ as the leftmost node of the subtree of root

x ′ in y r q A B C T 1 = y r q A B C = T 2 Figure 10
. The third case, r is a node of a subtree S 1 of T 1 satisfying y T1 S 1 .

T 2 . By Proposition 3.11, w := hw S2 (y ′ ) ∈ A, and by Lemma 3.9, w satisfies Ω(w) ≤ h(S 1 ). By hypothesis, hw T1 (y) ∈ A and one has

(3.15) hw T1 (y) = u. h(S 1 ).v, where u, v ∈ N * . Besides, since (3.16) hw T2 (y ′ ) = w.v, one has hw T2 (y ′ ) ∈ A, establishing (CC).
Thereby, we have shown that there exists a node x ′ in T 2 that is a witness of imbalance and satisfies the conservation condition in all case. Theorem 3.13. Let T and T ′ be two balanced binary trees such that T ≤ T T ′ . Then, the interval [T, T ′ ] only contains balanced binary trees. In other words, all successors of a binary tree obtained by an unbalancing rotation from a balanced binary tree are unbalanced.

Proof. Let T 0 and T 2 be two balanced binary trees and T 1 be an unbalanced binary tree. Assume that (3.17)

T 0 ⋌ • • • ⋌ T 1 ⋌ • • • ⋌ T 2 .
By Proposition 3.11, T 1 satisfies the conservation condition. Moreover, by Proposition 3.12, T 2 also satisfies the conservation condition. Hence, T 2 has a witness of imbalance and by Remark 3.4, T 2 is unbalanced. This is contradictory with our hypothesis.

Therefore, the notion of imbalance invariant defined in Section 3.2 is appropriate and hence the set of balanced binary trees is closed by interval in the Tamari lattice.

Synchronous grammars

In this section, we introduce synchronous grammars. These grammars allow to generate planar rooted tree-like structures by allowing these to grow from the root to the leaves step by step. Such trees grow from a single node, the root, and by simultaneously substituting its nodes with no children by new tree-like structures following some fixed substitution rules.

As we shall see, synchronous grammars are convenient tools to enumerate some specified families of planar rooted tree-like structures. Indeed, one can extract a fixed-point functional equation for the generating series enumerating the specified objects from a synchronous grammar subject to two precise conditions that we shall expose. We also present an algorithm to compute the coefficients of this generating series. For example,

(4.2) ev   z   = z and ev     x y x     = x 2 y.
4.1.2. Synchronous grammars.

Definition 4.2. A synchronous grammar S is a triple (B, a, R) where:

• B is a nonempty alphabet, the set of bud labels;

• a is a bud labeled on B, the axiom of S;

• R ⊆ B × D is a finite set such that for all b ∈ B, there is at least one bud tree D such that (b, D) ∈ R. This is the set of substitution rules of S.

Let S := (B, a, R) be a synchronous grammar. For the sake of readability, we will make use of the following notation for substitution rules: If (b, D) is a substitution rule of S, we shall denote it by b -→ S D or by b -→ D if S is fixed. Moreover, we will abbreviate the substitutions rules b

-→ S D 1 , . . . , b -→ S D n by (4.3) b -→ S D 1 + • • • + D n .
Definition 4.3. Let S := (B, a, R) be a synchronous grammar and D 0 be a bud tree with frontier

(b 1 , . . . , b n ) where ev(b i ) = b i for all 1 ≤ i ≤ n.
We say that the bud tree D 1 is derivable from D 0 in S, and we denote that by D 0 S -→ D 1 , if there exists a sequence of substitution rules

(b 1 -→ T 1 , . . . , b n -→ T n ) of R n such
that, by simultaneously substituting the bud b i of D 0 by the root of T i for all 1 ≤ i ≤ n, one obtains D 1 . Definition 4.4. A bud tree D is generated by a synchronous grammar S := (B, a, R) if there exists a sequence (D 1 , . . . , D ℓ-1 ) of bud trees such that

(4.4) a S -→ D 1 S -→ • • • S -→ D ℓ-1 S -→ D.
Moreover, we say that D is generated by a ℓ-steps derivation.

We denote by L (ℓ)

S the set of the bud trees generated by ℓ-steps derivations and by L S the language of S, that is the set of all bud trees generated by S. We also say that S is trim if for all b ∈ B there exists at least one bud tree D generated by S that contains a bud labeled by b. In the sequel, we shall only consider trim synchronous grammars without mentioning it explicitly.

We will illustrate most of the next definitions through the synchronous grammar (4.5)

S epl := {x, y}, x , R ,
where R contains the substitution rules

x -→ x 2 y + x 3 x y , (4.6) y -→ x . (4.7)
Figure 11 shows a derivation in S epl .

E := (D 0 , D 1 ) ∈ V 2 : D 0 S -→ D 1 .
The generating graph of S is the possibly infinite graph G S defined as above where V := L S . This graph is connected and has at most one source, the axiom a. Figure 12 shows an example of a 2-generating graph.

4.1.4. Strict and unambiguous synchronous grammars.

Definition 4.5. A synchronous grammar S := (B, a, R) is strict if there exists a monomial order ≤ B on the set of monomials of Z[B] such that, for all bud tree D 0 generated by S and all bud tree D 1 derivable from D 0 , we have ev(D 0 ) < B ev(D 1 ).

If S is strict, since its set of substitution rules is finite, S generates only finitely many bud trees with a given evaluation, and since its set of buds is finite, S also generates only finitely many bud trees with a given number of buds. Moreover, if S is strict, its generating graph G S is acyclic.

Lemma 4.6. Let S := (B, a, R) be a synchronous grammar. If there exists a total order ≤ B on B such that, for all substitution rule b -→ D of R where D ∈ D 1 we have b < B ev(D), then S is strict. Proof. We extend the total order ≤ B defined on B into a monomial order on the set of monomials of Z[B] by considering the graded lexicographic order on monomials.

Consider now a bud tree D 0 generated by S and a bud tree D 1 derivable from D 0 . If there exists at least one bud of D 0 that is substituted by a bud tree with more than one bud, one has ℓ (ev(D 0 )) < ℓ (ev(D 1 )) and hence ev(D 0 ) < B ev(D 1 ). Otherwise, D 0 and D 1 have the same number of buds. By hypothesis, all buds of the frontier (b 1 , . . . , b n ) of D 0 are substituted by n bud trees each containing the buds c 1 , . . . , c n such that ev(b i ) < B ev(c i ) for all 1 ≤ i ≤ n. Hence, ev(D 0 ) < B ev(D 1 ), implying that S is strict.

For instance, S epl is strict since the order y ≤ B x meets the assumptions of Lemma 4.6. This order can be extended into the monomial order defined by (4.10)

x i y j ≤ B x k y ℓ if i + j < k + l or i + j = k + l and i ≤ k.
Definition 4.7. A synchronous grammar S is unambiguous if for all bud tree D, there exists at most one integer ℓ ≥ 0 and one sequence (D 1 , . . . , D ℓ-1 ) such that (4.4) holds.

The generating graph G S is a tree if and only if S is unambiguous.

Lemma 4.8. Let S := (B, a, R) be a strict synchronous grammar. If for all b ∈ B and for all substitution rules b -→ T 0 and b -→ T 1 of R where T 0 = T 1 there are at the same location in T 0 and T 1 two non-bud nodes that are different, then S is unambiguous.

Proof. Let D be a bud tree generated by S and D 0 and D 1 be two different bud trees derivable from D. Among other substitutions, the bud tree D 0 (resp. D 1 ) is obtained by replacing one of its buds by a bud tree T 0 (resp. T 1 ), and by hypothesis, there are at the same location in T 0 and T 1 two non-bud nodes that are different. Hence, there are at the same location in D 0 and D 1 two non-bud nodes that are different. This shows that all bud trees obtained by performing any sequence of derivations from D 0 and from D 1 are different since they differ by a non-bud node. Moreover, since S is strict, its generating graph contains no cycle, and hence, S is unambiguous.

For instance, Lemma 4.8 shows that S epl is unambiguous since it is strict and the bud x can be substituted by two buds trees with different roots: One of these is of arity 2 while the other one is of arity 3. Let S := (B, a, R) be a strict synchronous grammar. The series S S is well-defined since S is strict. Moreover, if S is also unambiguous, we have

S epl (x, y) = x 2 y + x 3 y + x 3 y 2 + 2x 4 y 2 + x 5 y 2 . (4.16)
and its generating series is of the form (4.17 Proof. If ℓ = 0, the only bud tree generated by 0-step derivations is the axiom a of S. Hence, the lemma is satisfied.

Let ℓ ≥ 1. Assume that there exists the following sequence of derivations in S:

(4.22) a S -→ D 1 S -→ • • • S -→ D ℓ-1 S -→ D ℓ .
Then, by definition, D ℓ is obtained by substituting the buds b i of D ℓ-1 by some buds trees T i . From the polynomial point of view, the monomial ev(D ℓ ) is obtained by the polynomial substitutions ev

(b i ) ← ev(T i ) in S (ℓ-1) S . Hence, S (ℓ)
S is obtained from S Proposition 4.11 gives a formula to extract a fixed-point functional equation for the generating series of a given strict synchronous grammar S := (B, a, R) and Lemma 4.10 gives an algorithm to compute its coefficients by iteration, i.e., by computing the polynomials S (ℓ) S for 0 ≤ ℓ ≤ n where n is a desired order, and then, by summing its terms.

In our example, the generating series of S epl satisfies the fixed-point functional equation

(4.28) S S epl (x, y) = x + S S epl (xy + x 2 y, x).
Note that in some cases it is useful to specialize the generating series S S associated with S. For example, the specialization of an element b of B to 0 allows to annihilate some terms of S S corresponding to bud trees which have buds labeled by b. In this way, the enumeration provided by S S with this specialization takes into account only bud trees generated by S that have no bud labeled by b.

In the same way, it is possible to add some parameters to the substitution rules of S in order to refine the generating series S S . For instance, to take into account the number of application of the substitution rule (4.29)

x -→ x 3

x y , in the bud trees generated by S epl , one has just to set (4.30) subs(x) := xy + x 2 yξ, so that the parameter ξ counts the number of application of this substitution rule. In this way, one can enumerate tree-like structures according to some statistics. By identifying the buds x with leaves, the language L S perf is the set of perfect binary trees, that are binary trees of the sequence (T i ) i≥0 defined by T 0 :=⊥ and

T i+1 := T i ∧ T i .
This synchronous grammar is strict since the number of buds of all bud trees generated by S perf increases after each derivation. Besides, since S perf is strict and R only contains one substitution rule, the generating graph G S perf only contains one maximal path and hence, S perf is unambiguous. Therefore, the series S S perf is well-defined and by Proposition 4.11, it satisfies the fixed-point functional equation .

S perf (x) = x, S (1)
S perf (x) = x 2 , S (2)
S perf (x) = x 4 , S (3)
S perf (x) = x 8 , so that (4.34) S S perf (x) = n≥0 x 2 n = x + x 2 + x 4 + x 8 + • • • 4.3.
By identifying the buds x with leaves, the language of S 23 is the set of balanced 2-3 trees, that are complete rooted planar trees such that each internal node has 2 or 3 children and all paths leading to their leaves have same length (see [START_REF] Odlyzko | Periodic Oscillations of Coefficients of Power Series That Satisfy Functional Equations[END_REF][START_REF] Flajolet | Analytic Combinatorics[END_REF]).

Since each step of derivation increases the number of buds of the generated bud tree, S 23 is strict. Moreover, S 23 satisfies the hypothesis of Lemma 4.8 and hence is unambiguous. Indeed, the two bud trees appearing in the two substitution rules have a different root: One is of arity 2 and the other of arity 3. Thus, the series S S23 is well-defined and by Proposition 4.11, it satisfies the fixed-point functional equation

S

(1)

S23 (x) = x 2 + x 3 , (4.38) S (2) S23 (x) = x 4 + 2x 5 + 2x 6 + 3x 7 + 3x 8 + x 9 . (4.39)
An interpretation of the polynomial S

(2) S23 (x) is the following: By performing 2-steps derivations, S 23 generates one bud tree with 4 buds, two bud trees with 5 buds, two bud trees with 6 buds, three bud trees with 7 buds, three bud trees with 8 buds and one bud tree with 9 buds. 4.3.3. Balanced binary trees. Consider now the synchronous grammar S bal := {x, y}, x , R where R contains the substitution rules

x -→ x -1 y + x 0 x + y 1 x , (4.40) y -→ x . (4.41)
As we shall show, by annihilating the bud trees containing some buds y and by replacing the buds x by leaves, the language of S bal is the set of balanced binary trees. Proposition 4.12. Let D be a bud tree generated by S bal only containing buds x . Then, the non-bud nodes of D are labeled by their imbalance value.

Proof. Each step of derivation leading to D substitutes each x by new bud trees of height two, and each y by new bud trees of height one. Thus, each step of derivation increases by one the height of the subtrees containing a x . Besides, the role of the y is to delay, during one step of derivation, the growth of the branch containing these, to enable the creation of the imbalance values -1 and 1. Since D does not have any y , every growing delay is respected, so that imbalance values are its labels. Proposition 4.12 shows that the bud trees generated by S bal only containing buds x are balanced binary trees. Moreover, a simple structural induction on balanced binary trees shows that every balanced binary tree can be generated by S bal . Indeed, the empty tree can be generated, and, if T is a balanced binary tree and z its root, by induction hypothesis, its left subtree and its right subtree can be generated by S bal . To generate T , one just have to make the first derivation according to the imbalance value of z. Figure 13 shows an example of generation of a balanced binary tree.

By setting y ≤ B x, S bal satisfies the hypothesis of Lemma 4.6 and hence, is strict. Moreover, Lemma 4.8 shows that S bal is unambiguous since all bud trees arising in a right member of the substitution rules of S bal have a different root since their labeling differ. Proposition 4.12 shows that this labeling is consistent. Hence S S bal is well-defined. By Proposition 4.11, the generating series enumerating the elements of L S bal satisfies the fixed-point functional equation (4.42) S S bal (x, y) = x + S S bal (x 2 + 2xy, x).

x

S bal --→ y 1 x S bal --→ x 1 x -1 y S bal --→ x -1 y 1 y 1 x -1 x S bal --→ x 0 x -1 x 1 x 1 x 0 x -1 x 0 x ≈ Figure

S

(2)

S bal (x, y) = 4x 2 y + 2x 3 + 4x 2 y 2 + 4x 3 y + x 4 . (4.45)
As already mentioned, to enumerate balanced binary trees, we have to discard the elements of L S bal that contain a bud labelled by y. Thus, the generating series enumerating balanced binary trees according to their number of leaves is given by the specialization S S bal (x, 0). Note that this fixed-point functional equation is obtained in [BLL88, BLL94, Knu98] by other methods.

Imbalance tree patterns and balanced binary trees

Word patterns and permutations patterns are usually used to describe languages or sets of permutations by considering the set of elements avoiding these ones. We use the same idea to describe sets of binary trees by introducing a notion of binary tree patterns and pattern avoidance.

We show that we can describe in this way some interesting subsets of the set of balanced binary trees according to their particular position in the Tamari lattice. Afterwards, we use the methods developed in the previous section to construct synchronous grammar generating the maximal balanced binary trees in the Tamari lattice and get fixed-point functional equation for the generating series enumerating these.

Imbalance tree patterns.

Definition 5.1. An imbalance tree pattern is a nonempty incomplete rooted planar binary tree with labels in Z.

Let T be a binary tree. We denote by T i the labeled binary tree of shape T whose nodes are labeled by their imbalance value. We say that T admits an occurrence of the imbalance tree pattern p if a connected component of T i has the same shape and same labels as p. Now, given a set P of imbalance tree patterns, we can define the set composed of the binary trees that avoid P , i.e., the binary trees that do not admit any occurrence of the elements of P . For example, the set (5.1)

i : i / ∈ {-1, 0, 1}
describes the set of balanced binary trees, the set (5.2) i : i = 0 describes the set of perfect binary trees and

(5.3)

i j : i, j ∈ Z
describes the set of right comb binary trees, that are binary trees such that each node has an empty left subtree.

As exposed in Section 4.3, synchronous grammars allow to generate binary trees by controlling the imbalance values of their nodes. Hence, they allow to generate binary trees that avoid some imbalance tree patterns. 5.2. Minimal and maximal balanced binary trees in the Tamari lattice.

Minimal and maximal balanced binary trees.

Let us first describe a set of balanced binary trees and its counterpart whose elements are, roughly speaking, at the end of the balanced binary trees subposet of the Tamari lattice.

Definition 5.2. A balanced binary tree T 0 (resp. T 1 ) is maximal (resp. minimal) if, for all binary tree T 1 (resp. T 0 ) such that T 0 ⋌ T 1 , we have T 1 (resp. T 0 ) unbalanced.

By Theorem 3.13, if T 0 (resp. T 1 ) is a maximal (resp. minimal) balanced binary tree, then there does not exist any balanced binary tree T 1 (resp. T 0 ) such that T 0 ≤ T T 1 . Maximal (resp. minimal) balanced binary trees are thus maximal (resp. minimal) elements in the Tamari lattice restricted to balanced binary trees.

Proposition 5.3. A balanced binary tree T is maximal if and only if it avoids the set of imbalance tree patterns (5.4)

P max :=    -1 -1 , 0 -1    .
Similarly, a balanced binary tree T is minimal if and only if it avoids the set of imbalance tree patterns

(5.5)

P min := 1 1 , 1 0 .
Proof. Assume that T is maximal. Then, for all binary tree T 1 such that T ⋌ T 1 we have T 1 unbalanced. Thus, it is impossible to do a conservative balancing rotation into T and, looking at the different sorts of rotations studied in Section 3.1 it avoids the set P max . Conversely, assume that T is a balanced binary tree that avoids the two patterns of P max , then, for every binary tree T 1 such that T ⋌ T 1 , T 1 is unbalanced since for all node y which has a left child x in T , the imbalance values of x and y satisfy one of the seven cases (R3)-(R9) of Section 3.1. Thus, we can only do unbalancing rotations into T , implying that T is maximal.

The second part of the proposition is done in an analogous way, considering left rotations instead of right rotations.

Proposition 5.4. The generating series enumerating maximal balanced binary trees according to the number of leaves of the trees is S max (x, 0, 0) where (5.6) S max (x, y, z) = x + S max (x 2 + xy + yz, x, xy).

Proof. To obtain this fixed-point functional equation, let us consider the synchronous grammar S max := {x, y, z}, x , R where R contains the substitution rules

x -→ x 0 x + y 1 x + z -1
y , (5.7)

y -→ x , (5.8) z -→ y 1 x .
(5.9)

We can apply the same idea developed in the proof of Proposition 4.12 to show that the bud trees generated by S max that only contain buds x have non-bud nodes labeled by their imbalance values. Hence, by identifying in such trees the x with leaves, S max only generates maximal balanced binary trees. Indeed, by Proposition 5.3, the generated trees must avoid the two patterns of P max . To do that, we have to control the growth of the x when they are substituted by bud trees D whose roots have imbalance values of -1. Indeed, if the root of the left subtree of D grows with an imbalance value of -1 or 0, one of the two patterns is not avoided. The idea is to force the imbalance value of the root of the left subtree of D to be 1, role played by the bud z . The role of the bud y is to delay the growth of a branch of the generated bud tree in order to create the imbalance values -1 and 1. Moreover, by structural induction on maximal balanced binary trees, one can also prove that all maximal balanced binary trees can be generated by S max .

By setting y ≤ B x, S max satisfies the hypothesis of Lemma 4.6, and hence, is strict. This synchronous grammar is also unambiguous since it satisfies the hypothesis of Lemma 4.8. Indeed, the roots of all bud trees appearing in a right member of the substitution rules of R are different to one other, due to their labeling.

Finally, since S max is strict and unambiguous, by Proposition 4.11, we obtain the stated fixedpoint functional equation, and the generating series is obtained by the specialization y = 0 and z = 0 in order to ignore bud trees containing a bud labelled by y or by z.

The solution of this fixed-point functional equation gives us the following first values for the number of maximal balanced binary trees in the Tamari lattice:

1, 1, 1, 1, 2, 2, 2, 4, 6, 9, 11, 13, 22, 38, 60, 89, 128, 183, 256, 353, 512, 805, 1336, 2221, 3594, 5665, 8774, 13433, 20359, 30550, 45437, 67086, 98491, 144492, 213876. (5.10) 5.2.2. Interior balanced binary trees. Let us now describe a set of balanced binary trees and its counterpart whose elements are, roughly speaking, in the heart of the balanced binary trees subposet of the Tamari lattice. Definition 5.5. A balanced binary tree T 0 (resp. T 1 ) is right interior (resp. left interior) if all binary tree T 1 (resp. T 0 ) such that T 0 ⋌ T 1 is balanced.

Proposition 5.6. A balanced binary tree T is right interior if and only if it avoids the set of imbalance tree patterns (5.11)

P rint := -1 0 , -1 1 , 0 0 , 0 1 , 1 -1 , 1 0 , 1 1 .
Similarly, a balanced binary tree T is left interior if and only if it avoids the set of imbalance tree patterns

(5.12)

P lint :=    0 1 , - 1
1 , 0 0 , -1 0 , 1 -1 , 0 -1 , -1 -1    .
Proof. Assume that T is right interior. Then, for all binary tree T 1 such that T ⋌ T 1 , T 1 is balanced. Thus, for every node y and its left child x in T , the imbalance values of x and y satisfy (R1) or (R2) of Section 3.1 since one can only do conservative balancing rotations in T . Hence, T must avoid the seven given patterns. Conversely, assume that T is a balanced binary tree that avoids the patterns of P rint . For every node y which has a left child x in T , the imbalance values of x and y satisfy (R1) or (R2). Thus, the rotation of root y in T produces a balanced binary tree and implies that T is interior.

The second part of the proposition is done in an analogous way, considering left rotations instead of right rotations.

In the sequel, we shall only consider right interior balanced binary trees so we call these interior balanced binary trees. This family of binary trees is easily enumerable according to their height: Proposition 5.7. The number a h of interior balanced binary trees of height h is

(5.13) a h =      1 if h ∈ {0, 1, 3}, 2 if h = 2, a h-1 a h-2 otherwise.
Proof. The values of a h for 0 ≤ h ≤ 3 can easily be computed by hand.

Let us first observe that if T := L ∧ R is an interior balanced binary tree of height h ≥ 3, then L and R also are interior balanced binary trees and the imbalance value of the root of T is -1. Indeed, if L or R is not an interior balanced binary tree, then, by Proposition 5.6, L or R would admit an occurrence of a pattern of P rint and hence, would T . Moreover, if the imbalance value of T is not -1, since T is balanced and h(T ) ≥ 3, its left subtree L is nonempty and T would admit an occurrence of a pattern of P rint .

Let us finally show that for all integer h ≥ 4 and all interior balanced binary trees L and R such that h(L) = h -1 and h(R) = h -2, the binary tree T := L ∧ R is an interior balanced binary tree. Since h(L) ≥ 3, according to what we have just shown, the imbalance value of the root x of L is -1. The imbalance value of the root y of T also is -1 and thus, x and y do not form a pattern of P rint in T . Moreover, the root of R and the node x in T do neither form a pattern of P rint . Hence, T is an interior balanced binary tree. That proves (5.13).

The first values of (a h ) h≥0 are (5.14) 1, 1, 2, 1, 2, 2, 4, 8, 32, 256, 8192, 2097152, 17179869184.

By forgetting the first three values, this is Sequence A000301 of [Slo]. Moreover, one has a h = 2 f h-3 for all h ≥ 3, where f i is the i-th Fibonacci number, defined by

f i := i if i ∈ {0, 1}, and
f i := f i-1 + f i-2 otherwise.
Recall that the set of Fibonacci binary trees [START_REF] Cormen | Introduction to algorithms[END_REF] is formed of the elements of the sequence (T i ) i≥0 where T 0 := T 1 :=⊥ and T i+2 := T i+1 ∧ T i . One can prove by structural induction on the set of Fibonacci binary trees that these also are interior balanced binary trees.

Mixed balanced binary trees.

Let us finally characterize balanced binary trees which are neither maximal nor interior.

Definition 5.8. A balanced binary tree T 0 is right mixed (resp. left mixed) if there exists a balanced binary tree T 1 and an unbalanced binary tree T ′ 1 such that T 0 ⋌ T 1 and T 0 ⋌ T ′ 1 (resp. T 1 ⋌ T 0 and T ′ 1 ⋌ T 0 ). Proposition 5.9. A balanced binary tree T is right mixed (resp. left mixed) if and only if it admits at least one occurrence of an imbalance tree pattern of the set P max (resp. P min ) and at least one occurrence of an imbalance tree pattern of the set P rint (resp. P lint ).

Proof. Assume that T is a mixed balanced binary tree. By definition, it is possible to perform a conservative balancing rotation into T . Hence, there are two nodes x and y in T satisfying (R1) or (R2) of Section 3.1 and form an occurrence of a pattern of P max . Moreover, again by definition, it is possible to perform an unbalancing rotation into T . Hence, there are two nodes x ′ and y ′ in T satisfying one of the seven cases (R3)-(R9) of Section 3.1 and form an occurrence of a pattern of P rint .

Conversely, if T admits some occurrences of patterns of both P max and P rint , considering the nine cases of rotation in a balanced binary tree studied in Section 3.1, we see that it is possible to make both a conservative and an unbalancing rotation into T , and hence T is a right mixed balanced binary tree.

The second part of the proposition is done in an analogous way, considering left rotations instead of right rotations.

In the sequel, we shall only consider right mixed balanced binary trees, so we call these mixed balanced binary trees.

Note that, for n ≥ 3, the set B n is a disjoint union of the set M of maximal balanced binary trees, the set N of interior balanced binary trees and the set X of mixed balanced binary trees with n nodes. Indeed, by definition, M and X are disjoint, and in the same way, N and X also are. Consider now a balanced binary tree T which is both maximal and interior. That implies that T is the maximal element of its Tamari lattice, and hence, T is a right comb binary tree. Since T is also balanced, it cannot have more than two nodes.

6. The subposet of the Tamari lattice of balanced binary trees 6.1. Isomorphism between balanced binary tree intervals and hypercubes. Lemma 6.1. Let T 0 and T 1 be two balanced binary trees such that T 0 ≤ T T 1 and y be a node of T 0 . Then:

(i) If the rotation of root y in T 0 is an unbalancing rotation, then, if it exists, the rotation of root y in T 1 is still an unbalancing rotation; (ii) If y has no left child in T 0 , then y has no left child in T 1 .

Proof. (i): If the rotation of root y in T 0 is an unbalancing rotation, it is because the imbalance values of y and its left child x do not satisfy (R1) or (R2) of Section 3.1. Thus, to change these imbalance values, one has to perform rotations to change the height of some subtrees of x and y. By Proposition 3.1, these rotations necessarily unbalance the obtained binary tree. Moreover, by Theorem 3.13, it is impossible to make rotations to balance it again. This shows that if y has a left child in T 1 , it is necessarily a root of an unbalancing rotation.

(ii): This is immediate from the definition of the rotation operation and by the fact that the rotation operation does not change the infix order of the nodes of a binary tree. Lemma 6.1 shows that for all balanced binary trees T 0 and T 1 such that T 0 ≤ T T 1 , a node y cannot become a root of a conservative balancing rotation in T 1 if it is not a root of a conservative balancing rotation in T 0 . Lemma 6.2. Let T 0 and T 1 be two balanced binary trees and y be a node of T 0 such that T 1 is obtained from T 0 by a rotation of root y. Then, denoting by x the left child of y in T 0 , for all balanced binary tree T 2 such that T 1 ≤ T T 2 , x and y cannot be roots of conservative balancing rotations in T 2 .

Proof. Since T 1 is obtained by performing a conservative balancing rotation of root y into T 0 , we have two cases to consider, following the imbalance values of x and y in T 0 . If i T0 (x) = i T0 (y) = -1, then i T1 (x) = i T1 (y) = 1 and x and y are not roots of conservative balancing rotations in T 1 , so that, by Lemma 6.1, x and y cannot be roots of conservative balancing rotations in T 2 . If i T0 (x) = 0 and i T0 (y) -1, then i T1 (x) = 1 and i T1 (y) = 0. For the same reason, x and y cannot be roots of conservative balancing rotations in T 2 .

A hypercube of dimension k can be seen as a poset whose elements are subsets of a set {e 1 , . . . , e k }, and ordered by the relation of inclusion. Let us denote by H k the hypercube poset of dimension k.

We have the following characterization of the shape of balanced binary tree intervals: Theorem 6.3. Let T 0 and T 1 be two balanced binary trees such that T 0 ≤ T T 1 . Then, the poset

([T 0 , T 1 ], ≤ T ) is isomorphic to the hypercube H k ,
where k is the number of rotations needed to transform T 0 into T 1 .

Proof. First, note by Theorem 3.13, that the interval I := [T 0 , T 1 ] only contains balanced binary trees. Hence, all covering relations in I are conservative balancing rotations.

Denote by R the set of nodes y of T 0 such that y is a root of a rotation needed to transform T 0 into T 1 . By Lemma 6.2, R is well defined -it is not a multiset -and if y ∈ R then, denoting by x the left child of y in T 0 , we have x / ∈ R. That implies that T 1 can be obtained from T 0 by performing, for all y ∈ R, a rotation of root y, independently of the order.

Let us now define a bijection between the elements of I and the set of the subsets of R. Let T ∈ I. By definition, it is possible to obtain T by performing some rotations from T 0 . Let R 0 be the set of nodes which are roots of these rotations. Besides, it is possible to obtain T 1 by performing some rotations from T . Let R 1 be the set of nodes which are roots of these rotations. By Lemma 6.1, we have R = R 0 ⊎ R 1 and thus R 0 ⊂ R. The set R 0 characterizes T . Conversely, for each subset R 0 ⊆ R we can construct a unique binary tree T ∈ I. Indeed, T is obtained by doing the rotations of root y for all y ∈ R 0 into T 0 , in any order. This is well-defined, by definition of R.

This shows that the interval I is isomorphic to the poset H k where k is the number of rotations needed to transform T 0 into T 1 .

The first subposets of the Tamari lattice of balanced binary trees are depicted in Figure 14. 6.2. Enumeration of balanced binary tree intervals. Let us make use again of the synchronous grammars to enumerate balanced binary trees intervals. Proposition 6.4. The generating series enumerating balanced binary tree intervals in the Tamari lattice according to the number of leaves of the trees is S bi (x, 0, 0) where (6.1) S bi (x, y, z) = x + S bi (x 2 + 2xy + yz, x, x 2 + xy).

(a) (B 0 , ≤ T ) (b) (B 1 , ≤ T ) (c) (B 2 , ≤ T ) (d) (B 3 , ≤ T ) (e) (B 4 , ≤ T ) (f) (B 5 , ≤ T ) (g) (B 6 , ≤ T ) (h) (B 7 , ≤ T ) (i) (B 8 , ≤ T ) (j) (B 9 , ≤ T ) (k) (B 10 , ≤ T ) (l) (B 11 , ≤ T ) Figure 14.
Hasse diagrams of the first (B n , ≤ T ) posets.

Proof. Let I := [T 0 , T 1 ] be a balanced binary tree interval and R be the set of nodes defined as in the proof of Theorem 6.3 associated with I. The proof of this theorem also shows that I can be encoded by T 0 in which the nodes of R are marked. To generate these objects, we consider a synchronous grammar which generates bud trees where (non-marked) nodes are and marked nodes are . Let us consider the synchronous grammar S bi := {x, y, z}, x , L where L contains the substitution rules

x -→ x -1 y + x 0 x + y 1 x + z -1 y , (6.2) y -→ x , (6.3) z -→ x 0 x + x -1 y . (6.4)
We can apply the same idea developed in the proof of Proposition 4.12 to show that the bud trees generated by S bi that only contain buds x have non-bud nodes labeled by their imbalance values. Hence, identifying in such trees the x with leaves, S bi only generates balanced binary trees such that each of its node r with -1 as imbalance value can be marked provided that its left child has -1 or 0 as imbalance value and is not marked (recall that in this way, r is a root of a conservative balancing rotation). Indeed, if a x is substituted by a marked node, this marked node has a bud z as left child and z can only be substituted by a non-marked node with -1 or 0 as imbalance value. The role of the bud y is to delay the growth of a branch of the generated bud tree in order to create the imbalance values -1 and 1.

By setting y ≤ B z ≤ B x, S bi satisfies the hypothesis of Lemma 4.6, and hence, is strict. This synchronous grammar also is unambiguous since it satisfies the hypothesis of Lemma 4.8. Indeed, the roots of the bud trees arising in a right member of the substitution rules of L are pairwise different, due to their labeling and their marking.

Finally, since S bi is strict and unambiguous, by Proposition 4.11, we obtain the stated fixedpoint functional equation, and the generating series is obtained by the specialization y = 0 and z = 0 in order to ignore bud trees that contain a bud labelled by y or by z.

The solution of this fixed-point functional equation gives us the following first values for the number of balanced binary tree intervals in the Tamari lattice:

1, 1, 3, 1, 7, 12, 6, 52, 119, 137, 195, 231, 1019, 3503, 6593, 12616, 26178, 43500, 64157, 94688, 232560, 817757, 2233757, 5179734, 11676838, 24867480. (6.5)

The interval [T 0 , T 1 ] is a maximal balanced binary tree interval if T 0 (resp. T 1 ) is a minimal (resp. maximal) balanced binary tree. Proposition 6.5. The generating series enumerating maximal balanced binary tree intervals in the Tamari lattice according to the number of leaves of the trees is S mbi (x, 0, 0, 0) where (6.6) S mbi (x, y, z, t) = x + S mbi (x 2 + 2yt + yz, x, x 2 + xy, yt + yz).

Proof. Let I := [T 0 , T 1 ] be a maximal balanced binary tree interval. This interval can be encoded by the minimal balanced binary tree T 0 in which the nodes that are roots of the conservative balancing rotations needed to transform T 0 into T 1 are marked. Moreover, since T 1 is a maximal balanced binary tree, by Proposition 5.3, it avoids the patterns of P max . Hence, the tree-like structure that encodes I must avoid the patterns of P min and not have a node which is root of a conservative balancing rotation not marked if its parent or its left child is not marked.

To generate these objects, we use the synchronous grammar S mbi := {x, y, z, u, v}, x , R where R contains the substitution rules

x -→ v -1 y + x 0 x + y 1 u + z -1
y , (6.7)

y -→ x , (6.8) z -→ x -1 y + x 0 x , (6.9) u -→ v -1 y + z -1 y , (6.10) v -→ y 1 u + z -1 y . (6.11)
We can apply the same idea developed in the proof of Proposition 4.12 to show that the bud trees generated by S mbi that only contain buds x have non-bud nodes labeled by their imbalance values. Hence, identifying in such trees the x with leaves, S mbi only generates minimal balanced binary trees that are maximally marked. Indeed, by Proposition 5.3, the generated tree-like structures must avoid the two patterns of P min . To do that, we have to control the growth of the x when they are substituted by bud trees D whose roots are not marked and have an imbalance value of 1. Indeed, if the root of the right subtree of D grows with an imbalance value of 1 or 0, one of the two patterns is not avoided. The idea is to force the imbalance value of the root of the right subtree of D to be -1, role played by the bud u . Moreover, if the x are substituted by non-marked nodes a labeled by -1, to generate trees that are maximally marked, the left child of a has to be marked, or labeled by 1 (in this case, a is not root of a conservative balancing rotation). This is the role played by the bud v . The bud z appears in these substitution rules only as a left child of a marked node and it is substituted only by nodes with -1 or 0 as imbalance value, that are the only ones authorized for a left child of a root of a conservative balancing rotation. As usual, the role of the bud y is to delay the growth of a branch of the generated bud tree in order to create the imbalance values -1 and 1.

By setting y ≤ B v ≤ B u ≤ B z ≤ B x, S mbi satisfies the hypothesis of Lemma 4.6, and hence, is strict. This synchronous grammar also is unambiguous since it satisfies the hypothesis of Lemma 4.8. Indeed, the roots of each bud trees arising in a right member of the substitution rules of R are different to one other, due to their labeling and their marking.

By Proposition 4.11, the fixed-point functional equation F associated with S mbi is (6.12) F (x, y, z, u, v) = x + F (x 2 + yu + yv + yz, x, x 2 + xy, yv + yz, yu + yz), and, since the variables u and v play the same role, we obtain the stated fixed-point functional equation. The generating series is obtained by the specialization y = 0, z = 0 and t = 0 in order to ignore bud trees that contain a bud labelled by y, z, u, or by v.

The solution of this fixed-point functional equation gives us the following first values for the number of maximal balanced binary tree intervals in the Tamari lattice:

1, 1, 1, 1, 3, 2, 2, 6, 9, 15, 15, 17, 41, 77, 125, 178, 252, 376, 531, 740, 1192, 2179, 4273, 7738, 13012, 20776, 32389, 49841, 75457, 113011, 168888, 252881, 379348. (6.13) We can slightly modify S mbi to take into consideration the dimensions of the hypercubes isomorphic to the enumerated maximal balanced binary tree intervals. For that, we have to count the number of applications of substitution rules that generate a marked node. Let us use for that a parameter ξ. Whence we obtain the generating series defined by the fixed-point functional equation (6.14) S mbi (x, y, z, t, ξ) = x + S mbi (x 2 + 2yt + yzξ, x, x 2 + xy, yt + yzξ, ξ).

First coefficients of x i in P := S mbi (x, 0, 0, 0, ξ) are (6.15)

x 1 P = 1, (6.16)

x 2 P = 1, (6.17)

x 3 P = ξ, (6.18)

x 4 P = 1, (6.19)

x 5 P = 3ξ, (6.20)

x 6 P = ξ + ξ 2 , (6.21)

x 7 P = 2ξ, (6.22)

x 8 P = 1 + 4ξ 2 + ξ 3 , (6.23)

x 9 P = 4ξ + 4ξ 2 + ξ 4 , (6.24)

x 10 P = 3ξ + 9ξ 2 + 3ξ 3 , (6.25)

x 11 P = 9ξ 2 + 6ξ 3 , (6.26)

x 12 P = ξ + 13ξ 2 + 2ξ 3 + ξ 4 , (6.27)

x 13 P = 6ξ + 4ξ 2 + 16ξ 3 + 15ξ 4 , (6.28) x 14 P = 2ξ + 18ξ 2 + 31ξ 3 + 12ξ 4 + 14ξ 5 . Proof. Let T 0 ∈ B {0,1} . Since T 0 is only composed of nodes with 0 or 1 as imbalance value, one can only perform into T 0 rotations of the kind (R3), (R5), (R8) or (R9) studied in Section 3.1. Since these rotations are unbalancing rotations, for all binary tree T 1 such that T 0 ⋌ T 1 , T 1 is not balanced and hence, T 1 / ∈ B {0,1} . By Theorem 3.13, for all binary tree T 2 such that T 1 ≤ T T 2 , T 2 is not balanced, and with greater reason, T 2 / ∈ B {0,1} . Therefore, B {0,1} is closed by interval in the Tamari lattice.

The proof of Proposition 7.4 also shows that every rotation performed into a {0, 1}-balanced binary tree gives a {0, 1}-unbalanced binary tree. That implies that any pair of elements of B {0,1} is incomparable.

Computer trials suggest that for all β ∈ Z, any pair of elements of B {0,β} is incomparable. Hence, the sets B {0,β} seem to be closed by interval in the Tamari lattice. 7.1.4. [-α, β]-balanced binary trees.

Lemma 7.5. For all α ≥ 2, the sets B [-α,0] and B ]-∞,0] are not closed by interval in the Tamari lattice.

Proof. It is enough to exhibit a chain of the sort T 0 ⋌ T 1 ⋌ T 2 where T 0 , T 2 ∈ B [-α,0] ∩ B ]-∞,0] and T 1 / ∈ B [-α,0] ∪ B ]-∞,0] . The following chain, where nodes are labeled by their imbalance values, is the case:

(7.5) 0 -1 -2 0 0 -1 -2 ⋌ 0 0 0 1 0 -1 -2 ⋌ 0 0 0 0 0 0 0 .
Lemma 7.6. For all α ≥ 2, the sets B [-α,1] and B ]-∞,1] are not closed by interval in the Tamari lattice.

Proof. It is enough to exhibit a chain of the sort

T 0 ⋌ T 1 ⋌ T 2 where T 0 , T 2 ∈ B [-α,1] ∩ B ]-∞,1] and T 1 / ∈ B [-α,1] ∪ B ]-∞,1]
. The following chain, where nodes are labeled by their imbalance values, is the case:

(7.6) 0 -1 -1 0 0 0 -1 -2 ⋌ 0 -1 2 0 2 0 -1 -2 ⋌ 0 -1 1 0 1 0 0 0 .
Lemma 7.7. For all α ≥ 2, the sets B [-α,2] and B ]-∞,2] are not closed by interval in the Tamari lattice.

Proof. It is enough to exhibit a chain of the sort

T 0 ⋌ T 1 ⋌ T 2 where T 0 , T 2 ∈ B [-α,2] ∩ B ]-∞,2] and T 1 / ∈ B [-α,2] ∪ B ]-∞,2]
. The following chain, where nodes are labeled by their imbalance values, is the case:

(7.7) 0 -1 1 0 -1 -2 ⋌ 0 3 3 0 -1 -2 ⋌ 0 2 2 0 0 0 .
Lemma 7.8. For all α ≥ 2 and β ≥ 3, the sets B [-α,β] and B ]-∞,β] are not closed by interval in the Tamari lattice.

Proof. It is enough to exhibit a chain of the sort

T 0 ⋌ T 1 ⋌ T 2 where T 0 , T 2 ∈ B [-α,β] ∩ B ]-∞,β] and T 1 / ∈ B [-α,β] ∪ B ]-∞,β]
. By setting β ′ := β -1 and β ′′ := β + 1, the following generic chain, where nodes are labeled by their imbalance values, and where the edges depicted by denote a right comb binary tree with β -3 nodes, is the case:

(7.8) 0 β ′ 0 -1 -2 ⋌ β ′′ β 0 -1 -2 ⋌ β β ′ 0 0 0 .
Theorem 7.9. Let V be an interval of Z containing 0. The set B V is closed by interval in the Tamari lattice if and only if V ∈ {{0}, {-1, 0}, {0, 1}, {-1, 0, 1}, Z}.

Proof. Since B {0} only contains perfect binary trees and there is at most one such element with a given number of nodes, B {0} is closed by interval. Moreover, by Proposition 7.4, B {0,1} is closed by interval, and by Proposition 7.3, B {-1,0} also is. By Theorem 3.13, B {-1,0,1} is closed by interval. Finally, since B Z = T , B Z is obviously closed by interval. If V is an interval of Z containing 0 and that does not fit into the previous cases, necessarily V or V ∼ satisfies the assumptions of Lemma 7.5, 7.6, 7.7, or 7.8. Thus, by Proposition 7.3, B V is not closed by interval. Theorem 7.9 emphasizes the special role played by balanced binary trees in the Tamari lattice. Indeed, the interval V := [-1, 1] of Z is the only interval different from Z such that B V is closed by interval in the Tamari lattice and such that the subposet of the Tamari lattice induced by B V contains nontrivial intervals (see Theorem 6.3 and Figure 14). The sequence (w n ) n≥0 of the number of weight balanced binary trees with n nodes satisfies straightforwardly the recurrence relation (7.11)

w n =      1 if n ∈ {0, 1}, 2w k w k-1 if n = 2k, w 2 k where n = 2k + 1, otherwise.
This is Sequence A110316 of [Slo]. First values are (7.12) Lemma 7.11. For all nonempty weight balanced binary tree T , the following relation between its height and its number of nodes holds

(7.13) h(T ) = ⌊log 2 (n(T ))⌋ + 1.
Proof. We proceed by structural induction on the set of nonempty weight balanced binary trees. The lemma is true for the one-node binary tree. Assume now that (7.13) holds for both the weight balanced binary trees L and R such that T := L ∧ R is weight balanced. We have now two cases to consider, depending if L and R have the same number of nodes or not. If n(L) = n(R), set k := n(L). We have

⌊log 2 (n(T ))⌋ + 1 = ⌊log 2 (2k + 1)⌋ + 1 (7.14) = ⌊log 2 (2) + log 2 (k + 1/2)⌋ + 1 (7.15) = ⌊log 2 (k + 1/2)⌋ + 2 (7.16) = ⌊log 2 (k)⌋ + 2 (7.17) = h(L) + 1 (7.18) = h(R) + 1 (7.19) = h(T ). (7.20)
The equality between (7.16) and (7.17) is provided by the fact that k is an integer. The equality between (7.17) and (7.18) follows by induction hypothesis.

If n(L) = n(R), assume without lost of generality that n(L) = n(R) + 1 and set k := n(L). An analog computation as above implies (7.13).

Proposition 7.12. The set of weight balanced binary trees is a subset of the set of the (height) balanced binary trees.

Proof. We proceed by structural induction on the set of weight balanced binary trees to show that each weight balanced binary tree is also (height) balanced. This property is true for both the empty tree and the one-node binary tree. Assume now that this property holds for two weight balanced binary trees L and R such that T := L∧R is weight balanced. By Lemma 7.11, we have

(7.21) h(R) -h(L) = ⌊log 2 (n(R))⌋ -⌊log 2 (n(L))⌋,
and since T is weight balanced, we have

| n(R) -n(L)| ≤ 1 so that | h(R) -h(L)| ≤ 1.
By induction hypothesis, L and R are (height) balanced, proving that T also is.

Proposition 7.13. Let T 0 and T 1 be two weight balanced binary trees such that T 0 ≤ T T 1 . Then, the interval [T 0 , T 1 ] only contains weight balanced binary trees.

Proof. Let us show that for all binary tree T , any rotation operation performed into T does not decrease the weight imbalance values of any node of T . Let y be a node in T and x its left child. Let (A ∧ B) ∧ C be the subtree of root y in T . Let T ′ be the binary tree obtained by the rotation of root y from T . We have the following weight imbalance values:

(7.22) wi T (x) = n(B) -n(A), wi T (y) = n(C) -n(B) -n(A) -1, and
(7.23) wi T ′ (x) = n(B) + n(C) + 1 -n(A), wi T ′ (y) = n(C) -n(B),
showing that wi T ′ (x) > wi T (x) and wi T ′ (y) > wi T (y). Besides, note that the rotation does not change the weight imbalance values of the other nodes of T . This shows that the set of weight balanced binary trees is closed by interval in the Tamari lattice since, by starting from a weight balanced binary tree T and by performing a rotation that gives a weight unbalanced binary tree T ′ , there exists a node z of T ′ such that wi T ′ (z) ≥ 2 and it is impossible to decrease this value so that each binary tree greater than T ′ is not weight balanced.

Note that the proof of Proposition 7.13 also proves that for all k ≥ 0, the sets of k-weight balanced binary trees, that are the sets of binary trees T such that for all node x of T , the relation |wi T (x)| ≤ k holds, are closed by interval in the Tamari lattice.

Since by Proposition 7.12, weight balanced binary trees are also (height) balanced, by Proposition 7.13 and Theorem 6.3, the intervals of weight balanced binary trees are isomorphic to a hypercube. However, the set of weight balanced binary trees has an additional property:

Proposition 7.14. The restriction of the Tamari order on the set of weight balanced binary trees is a graded poset.

Proof. Let us characterize the conservative weight balancing rotations. Let T 0 := (A ∧ B) ∧ C and T 1 := A ∧ (B ∧ C) be two weight balanced binary trees such that T 1 is obtained by a rotation at the root y of T 0 . Denote by x the left child of y in T 0 . Note that the rotation that transforms T 0 into T 1 cannot be a conservative weight balancing rotation if wi T0 (x) = 1 or wi T0 (y) = 1 since, following the proof of Proposition 7.13, the imbalance values of x and y both increase after a rotation. Here follows the list of the weight imbalance values of the nodes x and y in T 0 and T 1 expressed as (wi T0 (x), wi T0 (y)) -→ (wi T1 (x), wi T1 (y)):

(R'1) (-1, -1) -→ (2 n(A) -1, n(A)), (R'2) (0, -1) -→ (2 n(A) + 1, n(A)), (R'3) (-1, 0) -→ (2 n(A), n(A) + 1), (R'4) (0, 0) -→ (2 n(A) + 2, n(A) + 1).

Hence, we have four kind of rotations to explore:

Case 1: Regarding (R'1), we necessarily have n(A) = 1. Indeed, if n(A) ≥ 2, y would not be weight balanced in T 1 , and if n(A) = 0, since wi T0 (x) = -1, that would imply that n(B) = -1, which is absurd. Hence, since n(A) = 1, we have n(B) = 0 and n(C) = 1. Thus, there is only one pair (T 0 , T 1 ) satisfying this kind of conservative weight balancing rotation: (7.24) T 0 = -→ = T 1 .

Case 2: Concerning (R'2), we necessarily have n(A) = 0. Indeed, if n(A) ≥ 1, x would not be weight balanced in T 1 . Hence, since n(A) = 0, we have n(B) = 0 and n(C) = 0. Thus, there is only one pair (S 0 , S 1 ) that satisfies this kind of conservative weight balancing rotation:

(7.25) S 0 = -→ = S 1 .

Case 3: Regarding (R'3), we necessarily have n(A) = 0. That implies h(B) = -1, which is absurd. Hence, (R'3) cannot be a conservative weight balancing rotation.

Case 4: Concerning (R'4), x satisfies wi T1 (x) ≥ 2, and thus (R'4) is not a case of a conservative weight balancing rotation.

Hence, we only have two sorts of conservative weight balancing rotations. They are the ones depicted in (7.24) and (7.25).

Since each such rotation suppresses exactly one subtree of the form S 0 and adds exactly one subtree of the form S 1 , we can define a map φ : T → N where φ(T ) is the number of subtrees of the form S 1 in T . Hence, since by Proposition 7.13 the covering relations of the Tamari lattice restricted to the weight balanced binary trees are only conservative weight balancing rotations, the statistic φ is a ranking function of the Tamari lattice restricted to these elements, and shows that this poset is graded. 7.3. Binary trees with fixed canopy. The canopy cnp(T ) (see [START_REF] Loday | Hopf Algebra of the Planar Binary Trees[END_REF] and [START_REF] Viennot | Up-down sequences of permutations, paths and canopy of binary trees[END_REF]) of a binary tree T is the word on the alphabet {0, 1} obtained by browsing the leaves of T from left to right except the first and the last one, writing 0 if the considered leaf is oriented to the right, 1 otherwise (see Figure 15). Proof. Let us prove first that C u is closed by interval in the Tamari lattice. Consider a binary tree T 0 and y one of its nodes. Let (A ∧ B) ∧ C the subtree of T 0 of root y and T 1 be the binary tree obtained by the rotation of root y from T 0 . Regardless A and C, if B is not empty, we have cnp(T 0 ) = cnp(T 1 ); Otherwise, B is a leaf and its orientation changes from right to left. Thus, cnp(T 1 ) is lexicographically not smaller than cnp(T 0 ), which proves that C u is closed by interval.

We give now a counting argument to prove that C u also is an interval of the Tamari lattice. Let T be a maximal element among C u . Thus, each rotation changes the canopy of T , and hence, for every node y which has a left child x in T , x has no right child. The set of such maximal binary trees, denoted M, is characterized by the following regular specification (see [START_REF] Flajolet | Analytic Combinatorics[END_REF] for a general survey on regular specifications):

(7.28)

M = L × × M + {⊥},
where L is the set of left comb binary trees. It admits the following generating series M (x), which enumerates the elements of M according to their number of nodes:

(7.29)

M (x) = 1 -x 1 -2x = 1 + n≥1 2 n-1 x n .
Moreover, for all n ≥ 1 there are exactly 2 n-1 sets C u where ℓ(u) = n -1, and there are the same number of such maximal binary trees. That implies that there is exactly one maximal element in each C u . By the same reasoning, we can show that there is exactly one minimal tree in each C u , proving the result.

The statement of Proposition 7.15 is already known [START_REF] Loday | Order Structure on the Algebra of Permutations and of Planar Binary Trees[END_REF], only our proof is new. Proof. Consider a node y of T 0 and let (A ∧ B) ∧ C the subtree of T 0 of root y and T 1 be the binary tree obtained by the rotation of root y from T 0 . Regardless A and C, if B is not empty, T 0 and T 1 have the same number of nodes that have a right child; Otherwise, the number of right children increases by one in T 1 . Hence, in every chain T 0 ≤ T T 1 ≤ T . . . ≤ T T ℓ , we have nar(T 0 ) ≤ nar(T 1 ) ≤ • • • ≤ nar(T ℓ ). That proves that the set of k-Narayana binary trees is closed by interval in the Tamari lattice.

Proposition 7.17. For all k ≥ 0, the set of k-Narayana binary trees with n nodes is the disjoint union of the sets C u where ℓ(u) = n -1 and u contains k occurrences of 1.

Proof. It is enough to show that for all binary tree T of canopy u, the number of 1 in u is nar(u). Let us show this property by structural induction on the set of binary trees. If T is empty, this property is clearly satisfied. Assume now that T := L ∧ R, and set v := cnp(L) and w := cnp(R). We have now to deal four cases whether L and R are empty or not. Case 1: If L and R are empty, T is the one-node binary tree and the property is satisfied.

Case 2: If L and R are both not empty, then cnp(T ) = v.0.1.w. Since nar(T ) = nar(L) + nar(R) + 1, by induction hypothesis, the property is satisfied. Case 3: If L is empty and R not, then cnp(T ) = 1.w. Since nar(T ) = nar(R) + 1, by induction hypothesis, the property is satisfied. Case 4: If R is empty and L not, then cnp(T ) = v.0. Since nar(T ) = nar(L), by induction hypothesis, the property is satisfied.

Corollary 7.18. For all k ≥ 0, the set of k-Narayana binary trees with n nodes is a disjoint union of intervals in the Tamari lattice.

Proof. The property follows from the fact that the set of k-Narayana binary trees with n nodes is the union of some binary trees with a given canopy (Proposition 7.17) and that the sets of binary trees with a given canopy are intervals of the Tamari lattice (Proposition 7.15).

Figure 1 .

 1 Figure 1. An example of binary tree.

Figure 3 .

 3 Figure 3. The right rotation of root y.

Figure 4 .

 4 Figure 4. The Tamari lattices T 3 and T 4 . The smallest elements are at the top.

Figure 6 .Figure 7 .

 67 Figure 6. The sequence (S xi ) 1≤i≤ℓ associated with the node x 1 .

Lemma 3. 8 .

 8 If u.v is an admissible word such that ℓ(v) ≥ 2, the word u.Θ(v) is still admissible. Proof. If u is empty, the lemma follows immediately. Assume that u is nonempty. The word u.v is of the form u.v = u.a.b.w where a, b ∈ N and w ∈ N * . Set c := Θ(a.b) = Ω(a.b). The word u.c.w = u.Θ(v) is admissible if the two inequalities Ω(u) -1 ≤ c and Ω(u.c) ≤ Ω(u.a.b) hold. Since u.a.b.w ∈ A, we have Ω(u) -1 ≤ a, and since c = Θ(a.b), then c ≥ a and thus, Ω(u) -1 ≤ c, showing the first inequality. Set d := Ω(u). The second inequality amounts to prove that Ω(d.c) ≤ Ω(d.a.b), which is equivalent to prove Ω(d.Ω(a.b)) ≤ Ω(d.a.b). This relation holds in general for any letters a, b, d ∈ N, showing that u.Θ(v) ∈ A. 3.2.4. Admissible height words. Let us prove two lemmas relating admissible words and height words.

Case 2. 1 :

 1 If B ∧ C is unbalanced, set x ′ := r and y ′ as the leftmost node of B ∧ C. One has (3.12) hw T1 (y) = u. h(B). h(C).v, where u, v ∈ N * . Since x satisfies the conservation condition in T 1 , hw T1 (y) ∈ A. Thus, by Lemma 3.6, we have h(B) -1 ≤ h(C) so that i T2 (x ′ ) ≥ 2 and (W1) is satisfied. Moreover, since B is balanced, and by Lemma 3.3, all subtrees to the right w.r.t. x ′ are also balanced in T 2 , (W2) and (W3) are established. Finally, by Lemma 3.10, hw T1 (y ′ ) ∈ A, and since hw T2 (y ′ ) = hw T1 (y ′ ), (CC) checks out.

Figure 9 .

 9 Figure9. The second case, r is an ancestor of y and y T1 r.

  4.1. Definitions. 4.1.1. Bud trees. Definition 4.1. Let B be a nonempty finite alphabet. A B-bud tree, or simply a bud tree if B is fixed, is a nonempty incomplete rooted planar tree where the leaves, namely the buds, are labeled on B. Set for the sequel B := {b 1 , . . . , b k } as a nonempty finite alphabet. Denote by D n the set of B-bud trees with n buds and by D the set of all B-bud trees. The set of all buds of a bud tree D is denoted by Buds(D) and the frontier of D is the sequence (b 1 , . . . , b n ) of its buds, read from left to right. If b is a bud, we shall denote by ev(b) the evaluation of b, that is the element of B labeling b. Moreover, the evaluation ev(D) of D is the monomial of Z[B] defined by (4.1) ev(D) := b∈Buds(D) ev(b).

Figure 11 .

 11 Figure 11. A 1-step derivation in S epl .

Figure 12 .

 12 Figure 12. The 2-generating graph of S epl .

4. 2 .

 2 Synchronous grammars and generating series. Definition 4.9. Let S := (B, a, R) be a synchronous grammar. The ℓ-generating series S (ℓ) S of S is the polynomial of Z[B] defined by (4.11) S (ℓ) S (b 1 , . . . , b k ) := ev(D ℓ ). Moreover, if S is strict, the generating series S S of S is the element of Z[[B]] defined by (4.12) S S (b 1 , . . . , b k ) := ℓ≥0 S (ℓ) S (b 1 , . . . , b k ).

  (4.13) S S (b 1 , . . . , b k ) = D ∈ L S ev(D), and for all monomial u := b α1 1 . . . b α k k , the coefficient [u]S S is the number of bud trees generated by S that have u as evaluation, i.e., a frontier made of α i occurrences of buds labeled by b i , for all 1 ≤ i ≤ k. For example, the first ℓ-generating series of S epl are S (0) S epl (x, y) = x, (4.14) S (1) S epl (x, y) = xy + x 2 y,

S

  ) S S epl (x, y) = x + xy + 2x 2 y + x 3 y + x 3 y 2 + 2x 4 y 2 + x 5 y 2 + • • •For all b ∈ B let us define the polynomials subs(b) of Z[B] by (4.18) subs(b) := (b,D) ∈ R ev(D). For instance, for S epl one directly obtains from (4.6) and (4.7) subs(x) = xy + x 2 y, (4.19) subs(y) = x. (4.20) Lemma 4.10. Let S := (B, a, R) be a synchronous grammar. For all ℓ ≥ 0, S (b 1 , . . . , b k ) = ev(a) if ℓ = 0, S (ℓ-1) S (subs(b 1 ), . . . , subs(b k )) otherwise.

SS

  polynomial substitution b ← subs(b) for each b ∈ B, showing (4.21). Proposition 4.11. Let S := (B, a, R) be a strict synchronous grammar. The generating series S S satisfies the fixed-point functional equation (4.23) S S (b 1 , . . . , b k ) = ev(a) + S S (subs(b 1 ), . . . , subs(b k )). Proof. Using Lemma 4.10, we obtain S S (b 1 , . . . , b k ) = ℓ≥0 (subs(b 1 ), . . . , subs(b k )) (4.27) = ev(a) + S S (subs(b 1 ), . . . , subs(b k )).

4. 3 .

 3 Examples. Let us consider three examples of synchronous grammars to illustrate the concepts that we have presented. Let us start with a very simple example. 4.3.1. Perfect binary trees. Let the synchronous grammar S perf := {x}, x , R where R contains the unique substitution rule (4.31)x -→ x x .

  (4.32) S S perf (x) = x + S S perf (x 2 ), and enumerate perfect binary trees according to their number of leaves. First S

2 .

 2 Balanced 2-3 trees. Let the synchronous grammar S 23 := {x}, x , R where R contains the

  (4.36) S S23 (x) = x + S S23 (x 2 + x 3 ),and enumerate balanced 2-3 trees according to their number of leaves. First polynomials S

  Figure 13. Generation of a balanced binary tree by the synchronous grammar S bal .

7. 2 .

 2 Weight balanced binary trees. Denote by n(T ) the number of nodes of the binary tree T . Let us define the weight imbalance mapping wi T which associates an element of Z with a node x of T . It is defined by (7.9) wi T (x) := n(R) -n(L), where L (resp. R) is the left (resp. right) subtree of x. A node x is weight balanced if (7.10) wi T (x) ∈ {-1, 0, 1}. Definition 7.10. A binary tree T is weight balanced if all nodes of T are weight balanced.

Figure 15 .

 15 Figure 15. The canopy of this binary tree is 0100101. For all u ∈ {0, 1} * , define the set C u by (7.26) C u := {T ∈ T : cnp(T ) = u} . Note that the sets of binary trees with a given canopy play a role in a injective Hopf morphism relating the Hopf algebra of noncommutative symmetric functions Sym [GKL + 94] and the Hopf algebra of binary trees PBT [LR98, HNT05]. Recall that the fundamental basis of PBT is {P T } T ∈T and is indexed by binary trees. One can see the fundamental basis of Sym as a basis {P u } u∈{0,1} * indexed by binary words. The injective Hopf morphism β : Sym ֒→ PBT also satisfies (see [Gir11]) (7.27) β(P u ) =

7. 4 .

 4 Narayana binary trees. Let T be a binary tree. Denote by nar(T ) the number of nodes of T that have a nonempty right child. We say that T is a k-Narayana binary tree if nar(T ) = k. These binary trees are enumerated by the Narayana numbers[START_REF] Narayana | Sur les treillis formés par les partitions d'un entier[END_REF] (see Sequence A001263 of[Slo]). First values are n #{T ∈ T n : nar(T ) = k}, k = 0, . . . , Proposition 7.16. For all k ≥ 0 and T 0 and T 1 two k-Narayana binary trees such that T 0 ≤ T T 1 , the interval [T 0 , T 1 ] only contains k-Narayana binary trees.

  7.1.3. {0, 1}-balanced binary trees. Using the methods developed in Section 4, one can enumerate {0, 1}-balanced binary trees according to their number of leaves, and obtain the fixed-point The set of {0, 1}-balanced binary trees is closed by interval in The Tamari lattice.

	functional equation
	(7.3)	S 01 (x, y) = x + S 01 (x 2 + xy, x),
	where the generating series of {0, 1}-balanced binary trees is the specialization S 01 (x, 0). First
	values are
	(7.4) 1, 1, 1, 1, 1, 2, 2, 2, 3, 5, 7, 9, 11, 13, 17, 26, 42, 66, 97, 134, 180, 241, 321, 424, 564, 774, 1111.
	Proposition 7.4.

As example, the coefficient of x 12 of S mbi (x, 0, 0, 0, ξ) says that in the poset (B 11 , ≤ T ), there is one maximal 1-dimensional hypercube, thirteen maximal 2-dimensional hypercubes, two maximal 3-dimensional hypercubes and one maximal 4-dimensional hypercube (see Figure 14).

Note that Proposition 3.1 implies that all binary trees of the connected components of the posets (B n , ≤ T ) have same height. However, the converse is false: There is two connected components in the poset (B 5 , ≤ T ) and each binary tree of B 5 has same height. 7. Intervals of other binary trees families in the Tamari lattice 7.1. Generalized balanced binary trees.

7.1.1. Definitions. Let V be a subset of Z. We say that a binary tree T is V -balanced if for all node x of T , i T (x) ∈ V . Let us denote by B V the set of V -balanced binary trees. Note that the set of balanced binary trees is B [-1,1] . It is clear that 0 must always belongs to V since a binary tree necessarily has a node with both empty left and right subtrees; Otherwise, B V would be empty. A natural question about V -balanced binary trees demands to characterize the sets V such that B V is closed by interval in the Tamari lattice.

Let T be a binary tree. Denote by T ∼ the binary tree obtained by exchanging the right and left subtrees of each of its nodes. More formally, (7.1)

For instance, one has

If V is a subset of Z, let us also denote by V ∼ the set {-v : v ∈ V }.

A symmetry.

Lemma 7.1. Let T 0 and T 1 be two binary trees such that T 0 ≤ T T 1 . Then, T ∼ 1 ≤ T T ∼ 0 . Proof. Assume that S 0 ⋌ S 1 where S 0 = (A ∧ B) ∧ C and S 1 = A ∧ (B ∧ C). Hence, we have

). Thus, S ∼ 1 ⋌ S ∼ 0 , and the result follows from the fact that ≤ T is the reflexive and transitive closure of ⋌.

Lemma 7.2. For all V ⊆ Z, the application ∼ yields a bijection between the sets B V and B V ∼ . Proof. It is immediate, from the definition of ∼, that the application ∼ is an involution. It then remains to show that if T ∈ B V , then T ∼ ∈ B V ∼ . Let x be a node of T and L (resp. R) be the left (resp. right) subtree of x. We have v :

Proposition 7.3. For all V ⊆ Z, the set B V is closed by interval in the Tamari lattice if and only if the set B V ∼ also is.

Proof. Assume that B V ∼ is closed by interval in the Tamari lattice. By contradiction, assume that there exist T 0 , T 2 ∈ B V and T 1 / ∈ B V such that T 0 ≤ T T 1 ≤ T T 2 . By Lemma 7.1, we have T ∼ 2 ≤ T T ∼ 1 ≤ T T ∼ 0 , and by Lemma 7.2, T ∼ 0 , T ∼ 2 ∈ B V ∼ and T ∼ 1 / ∈ B V ∼ . That implies that B V ∼ is not closed by interval in the Tamari lattice, which is contradictory with our hypothesis.