{'fraction_non_alphanumeric': 0.04979048558047819, 'fraction_numerical': 0.01626817845698792, 'mean_word_length': 3.3794257340241796, 'pattern_counts': {'":': 0, '<': 45, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 39, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Counting smaller elements in the Tamari and m-Tamari lattices

We introduce new combinatorial objects, the interval- posets, that encode intervals of the Tamari lattice. We then find a combinatorial interpretation of the bilinear operator that appears in the functional equation of Tamari intervals described by Chapoton. Thus, we retrieve this functional equation and prove that the polynomial recursively computed from the bilinear operator on each tree T counts the number of trees smaller than T in the Tamari order. Then we show that a similar m + 1-linear operator is also used in the functionnal equation of m-Tamari intervals. We explain how the m-Tamari lattices can be interpreted in terms of m+1-ary trees or a certain class of binary trees. We then use the interval-posets to recover the functional equation of m-Tamari intervals and to prove a generalized formula that counts the number of elements smaller than or equal to a given tree in the m-Tamari lattice.


Introduction
The combinatorics of planar binary trees is known to have very interesting algebraic properties. Loday and Ronco first introduced the Hopf Algebra PBT based on these objects [13]. It was re-built by Hivert, Novelli and Thibon [11] through the introduction of the sylvester monoid. The structure of PBT involves a very nice object which is connected to both algebra and classical algorithmic: the Tamari lattice.
It was introduced by Tamari himself in 1962 as an order on formal bracketings [17] and was proved later to be a lattice [12]. It can be realized as a polytope called the associahedron. On binary trees, it can be described by a very common operation in algorithmic: the right rotation (see Figure 4). More generally, the cover relations of the Tamari order can be given on many other combinatorial objects counted by Catalan numbers [15], like Dyck paths.
In this paper, we study the enumeration of the intervals of the Tamari lattice. Surprisingly, the number of intervals is given by a very beautiful formula (1) I n = 2 n(n + 1) where I n is the number of intervals of the Tamari lattice of binary trees of size n. It was proven by Chapoton [8] using a functional equation on the generating function of the intervals. Very recently, Bergeron and Préville-Ratelle introduced a new set of lattices generalizing the Tamari lattice [5]. They are called the m-Tamari lattices and their elements are counted by the m-Catalan numbers. In this case also, one can obtain a formula counting the number intervals (2) I n,m = m + 1 n(mn + 1) (m + 1) 2 n + m n − 1 .
This was conjectured in [5] and proved in [7]. The proof also uses a functional equation that generalizes the classical case studied by Chapoton.
Here, we propose refined versions of both these results by studying a new object that we call interval-poset. Each interval-poset corresponds to an interval of the Tamari lattice. To construct these, we use the strong relations between the Tamari order and the weak order on permutations. It has been known since Björner and Wachs [6] that linear extensions of a certain labelling of binary trees correspond to intervals of the weak order on permutations. This was more explicitly described in [11] with sylvester classes. The elements of the basis P of PBT are defined as a sum on a sylvester class of elements of FQSym. The PBT algebra also admits two other bases H and E which actually correspond to respectively initial and final intervals of the Tamari order. They can be indexed by plane forests and, with a well chosen labelling, their linear extensions are intervals of the weak order on permutations corresponding to a reunion of sylvester classes. By combining the forests of the initials and finals intervals of two comparable trees in one single poset, we obtain what we call an interval-poset. Its linear extensions are exactly the sylvester classes corresponding to the interval in the weak order. This new object has nice combinatorial properties and allows to perform computations on Tamari intervals. Thereby, we give a new proof of the formula of Chapoton (1). This proof is based on the study of a bilinear operator that already appeared in [8] but was not explored yet. It leads to the definition of a new family of polynomials: Definition 1.1. Let T be a binary tree, the polynomial B T (x) is recursively defined by where L and R are respectively the left and right subtrees of T . We call B T (x) the Tamari polynomial of T and the Tamari polynomials are the set of all polynomials obtained by this process.
This family of polynomials is yet unexplored in this context but seems to appear in a different computation made by Chapoton on rooted trees [9]. Our approach on Tamari interval-posets allows us to prove the following theorem in Section 3.3: Theorem 1.2. Let T be a binary tree. Its Tamari polynomial B T (x) counts the trees smaller than or equal to T in the Tamari order according to the number of nodes on their left border. In particular, B T (1) is the number of trees smaller than or equal to T .
Symmetrically, ifB T is defined by exchanging the role of left and right children in Definition 1.1, then it counts the number of trees greater than or equal to T according to the number of nodes on their right border.
It was shown in [7] that the m-Tamari lattices can be seen as ideals of the Tamari lattice of size n × m. Therefore, an interval of the m-Tamari lattice is an interval of Tamari which satisfies some conditions. This can be expressed in terms of interval-posets. Thus, it allows us to easily generalize our results to the m-Tamari case. We re-obtain the functional equation on the generating function described in [7] along with a generalization of Theorem 1.2 to count smaller elements in the m-Tamari lattices.
We first recall in Section 2 some definitions and properties of the Tamari lattice. We then introduce the notion of interval-poset to encode a Tamari interval. In Section 3, we show the implicit bilinear operator that appears in the functional equation of the generating functions of Tamari intervals. We then explain how interval-posets can be used to give a combinatorial interpretation of this bilinear operator and thereby give a new proof of the functional equation. Theorem 1.2 follows naturally. In Section 3.4, we discuss the similarity between Tamari polynomials and some bivariate polynomials that appeared in the context of flows of rooted trees [9]. Section 4 is dedicated to the study of the m-Tamari lattices defined in [5]. A functional equation for the intervals of these lattices is shown in [7] and contains a m+1-linear operator that generalizes the binary case. In Section 4.2, we explain how the m-Tamari lattice can be seen on a certain class of binary trees which are in bijection with m + 1ary trees. Thus, we are able to use again the interval-posets with a generalized combinatorial m+1-operator to reobtain the functional equation of intervals of the m-Tamari order. We then prove Theorem 4.13, the generalization of Theorem 1.2 for the m-Tamari order.
2. Interval-posets of Tamari 2.1. The Tamari order on paths and binary trees. Originally, the Tamari lattice has been described on bracketing [17] but it is also commonly defined on Dyck paths. Definition 2.1. A Dyck path of size n is a lattice path from the origin (0, 0) to the point (2n, 0) made from a sequence of up steps (1, 1) and down steps (1, −1) such that the path stays above the line y = 0.
A Dyck path can also be considered as a binary word by replacing up steps by the letter 1 and down steps by 0. We call a Dyck path primitive if it only touches the line y = 0 on its end points. A rotation consists of switching a down step d with the primitive Dyck path starting right after d, see Figure 1. The Tamari order on Dyck paths is defined as the transitive and reflexive closure of the rotation operation: a path D ′ is greater than a path D if it can be obtained by applying a sequence of right rotation on D. It is indeed an order and even a lattice [17,12]. See Figure 2 for the lattices on Dyck paths of sizes 3 and 4.
A binary tree is recursively defined by being either the empty tree (∅) or a pair of binary trees, respectively called left and right subtrees, grafted on an internal node. If a tree T is composed of a root node x with A and B as respectively left and right subtrees, we write T = x(A, B). The number of nodes of a tree T is called the size of T .
There are many ways to define a bijection between Dyck paths and binary trees. The one we use here is the common one when working on the Tamari order. Similarly to a binary tree, a Dyck path can be seen as a recursive binary object: it is either an empty path or a word D 1 1D 2 0 where D 1 and D 2 are two Dyck paths (potentially empty ones). The subpath D 1 corresponds to the left factor of D up to the last touching point of D before the end. Consequently, if D is primitive, D 1 is empty. If both D 1 and D 2 are empty, then D is the only dyck path of size 1: the word 10. We define recursively the binary tree T corresponding to D. If D is the empty word, then T is the empty tree. Otherwise, T is a binary tree whose left subtree (resp. right rubstree) corresponds to D 1 (resp. D 2 ). See Figure 3 for an example of the bijection. Figure 3. Bijection between Dyck paths and binary trees Through this bijection, the rotation on Dyck paths can be interpreted directly in terms of binary trees. It is a well known operation called the right rotation used especially to balance binary trees in sorting algorithms [4].

←→
Definition 2.2. Let y be a node of T with a non-empty left subtree x. The right rotation of T on y is a local rewriting which follows Figure 4, that is replacing y(x(A, B), C) by x(A, y(B, C)) (note that A, B, or C might be empty). Figure 4. Right rotation on a binary tree.
The right rotation is then the cover relation of the Tamari order on binary trees, as illustrated on Figure 5.

2.2.
Relation with the weak order. The definition of the Tamari lattice on binary trees allows for a nice description of the relation between the Tamari order and the weak order on permutations [11]. The Tamari order is indeed both a sublattice and a quotient lattice of the weak order. To give the explicit construction, we need an extra notion on binary trees. Definition 2.3. A binary search tree is a labelled binary tree where for each node of label k, any label in his left (resp. right) subtree is lower than or equal to (resp. greater than) k.  Figure 7 shows an example of a binary search tree. There is only one way to label a binary tree of size n with distinct labels 1, . . . , n to make it a binary search tree. We call this the binary search tree labelling of the tree and often identify the two objects. Such a labelled tree can be interpreted as a poset. For example, the tree 1 2 3 is the poset where 1 and 3 are smaller than 2. We write 1 ⊳ 2 and 3 ⊳ 2. A linear extension of this poset is a permutation where if a ⊳ b in the poset, then the number a is before b in the permutation. For example, the linear extensions of the above tree are 132 and 312. The set of linear extensions of a given tree is called the sylvester class of the tree: it forms an interval of the right weak order as illustrated on Figure 7. The sylvester classes of the binary trees of size n form a partition of S n . The ordering between classes is well defined as a quotient order of the weak order and it corresponds to the Tamari order on binary trees [11]. This is illustrated by Figure 6: two binary trees T 1 and T 2 are such that T 1 ≤ T 2 if and only if there exists two linear extensions σ 1 and σ 2 of respectively T 1 and T 2 such that σ 1 ≤ σ 2 for the right weak order.  Figure 7. A binary search tree and its corresponding sylvester class 2.3. Construction of interval-posets. We now introduce more general objects: interval-posets in bijection with the intervals of the Tamari order. Let us first recall two bijections between binary search trees and forests of planar trees. We say that a binary search tree has an increasing relation between a and b if a < b and a ⊳ b, which means a is in the left subtree of b. Symmetrically, a binary search tree has a decreasing relation if a < b and b ⊳ a, i.e., b is in the right subtree of a. From a binary search tree T , one can construct a poset containing only increasing (resp. decreasing) relations of T . These posets are actually forests, we call them the initial and final forest of the binary tree.
Definition 2.4. The initial forest (noted F ≤ ) of a binary search tree T is a forest poset on the nodes of T containing only increasing relations and such that: It is equivalent to the following construction: • if a node labelled x has a left son labelled y in T then the node x have a son y in F ; • if a node labelled x has a right son labelled y in T then the node x have a right brother y in T ′ . In the same way, one can define the final forest (noted F ≥ ) by inversing the roles of the right and left son in the previous construction or, in terms of posets: These constructions are actually well known bijections between binary trees and planar forests. The tree is recursively retrieved from the forest. On the initial forest, the root of the corresponding binary tree is the left-most (minimal) root of the forest trees. The left subtree is obtained recursively from the subtrees of the root and the right subtree from the remaining trees of the forest. The construction is symmetric for the final forest. Both bijections are illustrated on Figure 8.
The sufficient and necessary condition for a labelled poset to be an initial (resp. final) forest can be easily described.
Lemma 2.5. Let F be a labelled poset. Then F is the final forest of a binary tree T if for every c ⊳ F a we have c > a and b ⊳ F a for every b such that a < b < c. Symmetrically, F is the initial forest of a binary tree T if for every a ⊳ F c, we have a < c and b ⊳ F c for every b such that a < b < c.
Proof. The final and initial forests cases are symmetric, we only give the proof of the final forest case.
First let us proof that the final forest F = F ≥ (T ) of a binary tree T satisfies the necessary condition. Let c > a be such that c ⊳ F a. By construction of F , we also have c ⊳ T a which means that c is in the right subtree of a. Let b be such that a < b < c. Only three configurations are possible: either a is in the left subtree of b, or a  and b are not comparable in T , or b is in the right subtree of a. The first configuration never happens because it implies that c is in the left subtree of b which contradicts the binary search tree condition. Then, if a and b are not comparable, it means they have a common root b ′ with a < b ′ < b and a is in the left subtree of b ′ . The situation is then similar to the previous one and leads to a contradiction as c is also in the left subtree of b ′ . Only the third configuration is possible which makes b ⊳ T a and by construction b ⊳ F a. Now, let F be a labelled poset satisfying the condition of the final forest. The poset F is made of r connected components F 1 , . . . F r . For each F i , there is a unique minimal poset element x i : y ⊳ F x i for all y ∈ F i . We call it the root of F i . Indeed, if x, x ′ , and y are in F i with y ⊳ F x and y ⊳ F x ′ then either x < x ′ < y and x ′ ⊳ F x or x ′ < x < y and x ⊳ F x ′ . As all relations of F are decreasing relations, x i is also the minimal label of F i : y > x i for all y ∈ F i . Furthermore, if x i and x j are the roots of two different components F i and F j then x i < x j implies y < z for all y ∈ F i and z ∈ F j . Now, following the construction described by Figure 8, we set k to be the maximal label among the roots x 1 , . . . , x r . If we cut out the root k from its connected component, the remaining poset F L still satisfies the condition and all its labels are bigger than k. The poset F R made from the other remaining connected components also satisfy the condition and all its label are smaller than k. Then we can recursively construct the binary tree T = k(T L , T R ) where T L and T R are obtained from respectively F L and F R . By construction, T is a binary search tree and F = F ≥ (T ).
We have seen that the linear extensions of a binary tree T form an interval of the right weak order. The linear extensions of the initial and final forests of T correspond to initial and final intervals [6] and can be interpreted in terms of the Tamari order. Proof. We only give the proof for F ≥ (T ). By symmetry of the right weak order and the Tamari order, it also proves the result for F ≤ (T ). Let α T be the minimal element of the sylvester class of T . We want to prove that the linear extensions of where ω is the maximal element of the right weak order. Because the Tamari order is a quotient of the right weak order, the Proposition is entirely proven by this result.
Let us recall that a coinversion (a, b) of a permutation σ is couple of numbers such that a < b and b appears before a in σ. As an example, (1, 4) is a coinversion of 2431 as well as (1, 2), (3, 4) and (1, 3). We have that µ ≤ σ in the right weak order if and only if the coinversions of µ are contained in the coinversions of σ. For the previous example, the permutation µ = 2314 is smaller than σ because its coinversions (1,2) and (1, 3) are also coinversions of σ.
The linear extensions of F ≥ (T ) are the permutations containing all coinverions (a, b) where b ⊳ F ≥ a. It is clear by construction that a linear extension of F ≥ (T ) contains these coinversions. It is also a sufficient condition. Indeed let σ be a permutation that is not a linear extension of F ≥ (T ). Then there is (a, b) with b ⊳ F ≥ a and a before b in σ. The permutation σ does not contain the coinversion (a, b).
Finally, the permutation α T contains exactly the coinversions given by the F ≥ (T ) relations (it does not contain other coinversions). Indeed, it is known [11] that α T is read on the binary search tree by a recursive printing: left subtree, right subtree, root. Let b > a be such that F ≥ (T ) does not contain the relation b ⊳ F ≥ a. It means b is not on the right subtree of a. There are only two possible configurations: either a is on the left subtree of b, either they have a common root b ′ and a is on the left subtree of b ′ and b on the right subtree of b ′ . In both cases, a is read before b in α T and then α T does not contain the coinversion (a, b).
To conclude, the linear extensions of F ≥ (T ) are the permutations whose coinversions contain the coinversions of α T . In other words, they are the permutations greater than or equal to α T .
If two trees T and T ′ are such that T ≤ T ′ , then F ≥ (T ) and F ≤ (T ′ ) share some linear extensions (by Proposition 2.6). More precisely, we denote by ExtL(F ) the set of linear extensions of a poset F . Then is the minimal permutation (resp. maximal permutation) of the sylvester class of T (resp. T ′ ). This set corresponds exactly to the linear extensions of the trees of the interval [T, T ′ ] in the Tamari order. It is then natural to construct a poset that would contain relations of both F ≥ (T ) and F ≤ (T ′ ), see Figure 9 for an example. That is what we call an interval-poset, the characterisation follows naturally from Lemma 2.5.
Definition 2.7. An interval-poset P is a poset such that the following conditions hold: • a ⊳ P c and a < c implies that for all a < b < c, we have b ⊳ P c, • c ⊳ P a and a < c implies that for all a < b < c, we have b ⊳ P a. And conversely, interval-posets are the only labelled posets whose linear extensions are intervals of the right weak order [α T 1 , ω T 2 ] with α T 1 (resp. ω T 2 ) the minimal permutation (resp. maximal permutation) of a sylvester class.
Proof. Let [T 1 , T 2 ] be an interval of the Tamari order. We build a poset containing all the relations from both F ≥ (T 1 ) and F ≤ (T 2 ). Note that relations from F ≥ (T 1 ) and F ≤ (T 2 ) together never lead to a contradiction. Indeed any linear extension of T 1 for example satisfies both by Proposition 2.6. It is clear by Lemma 2.5 that the resulting poset is an interval-poset.
Conversely, from an interval-poset P , we build F ≥ and F ≤ by keeping respectively decreasing and increasing relations of P . By Lemma 2.5, the two resulting posets are respectively a final forest of a binary tree T 1 and an initial forest of a binary tree T 2 . Let σ be a linear extension of P whose sylvester class corresponds to a binary tree T ′ . By definition, the permutation σ is also a linear extension of F ≥ and F ≤ and we have 10 by Proposition 2.6 that Many operations on intervals can be easily done on interval-posets, all with trivial proofs. Proposition 2.9.
(i) The intersection between two intervals I 1 and I 2 is given by the interval-poset I 3 containing all relations of I 1 and I 2 . If I 3 is a valid poset, then it is a valid interval-poset, otherwise the intersection is empty. (8) φ(y) = 1 + y + 3y 2 + 13y 3 + 68y 4 + . . . .
In [8], Chapoton gives a refined version of φ, where I n,m is the number of intervals [T 1 , T 2 ] of trees of size n such that T 1 has exactly m nodes on its left border. This gives The statistic of the number of nodes on the left border is well known [1]. On Dyck paths, it corresponds to the number of touch points: the number of contacts between the path and the bottom line [2]. It can also be read on F ≥ (T ): it is the number of connected components. The refined generating functions Φ can be expressed by (11) Φ(x, y) = I

P(I)
summed on all interval-posets. We prove the following theorem.
Theorem 3.2. The generating function Φ(x, y) satisfies the functional equation This theorem was already proven by Chapoton in [8] 1 . In Section 3.2, we give a new proof of the theorem based on a combinatorial interpretation of the operator B. Let us define now what we call the composition of interval-posets.
Definition 3.3. Let I 1 and I 2 be two interval-posets of size respectively k 1 and k 2 . Then B(I 1 , I 2 ) is the formal sum of all interval-posets of size k 1 + k 2 + 1 where, (i) the relations between vertices 1, . . . , k 1 are exactly the ones from I 1 , (ii) the relations between k 1 + 2, . . . , k 1 + k 2 + 1 are exactly the ones from I 2 shifted by k 1 + 1, (iii) we have i ⊳ k 1 + 1 for all i ≤ k 1 , (iv) there is no relation k 1 + 1 ⊳ j for all j > k 1 + 1. The sum we obtain by composing interval-posets actually corresponds to all possible ways of adding decreasing relations between the second poset and the new vertex k 1 +1, as seen on Figure 12. Especially, there is no relations between vertices 1, . . . , k 1 and k 1 +2, . . . , k 1 +k 2 +1. Indeed, condition (iii) makes it impossible to have any relation j ≺ i with i < k 1 +1 < j as this would imply by Definition 2.7 that k 1 +1 ≺ i. And condition (iv) makes it impossible to have i ≺ j as this would imply k 1 + 1 ≺ j.

We call this operation the composition of intervals and extend it by bilinearity to all linear sums of intervals.
The number of elements in the sum is given by trees(I 2 ) + 1. Indeed, if x 1 < x 2 < · · · < x m are the tree roots of F ≥ (I 2 ), a decreasing relation x i ⊳ k 1 + 1 can be added only if all relations x j ⊳ k 1 + 1 for j < i have already been added. We then obtain (14) B(I 1 , where P i is the interval-poset where exactly i relations have been added: (1) Q α , the binary tree obtained by grafting k(T 1 , ∅) on the left of the leftmost node of T 2 , (2) Q ω , the binary tree k(T 1 , T 2 ), (3) and Q ′ , the binary tree k(T ′ 1 , T ′ 2 ). Then we have (15) B(I 1 , Proof. The composition of I 1 and I 2 is a sum of interval-posets P 0 , . . . , P m where m = trees(I 2 ) and where P i is the interval-poset where exactly i decreasing relations have been added. The maximal tree of all intervals is always the same as they all share the same increasing relations. This maximal tree is Q ′ = k(T ′ 1 , T ′ 2 ). The final forest F ≥ (P 0 ) of P 0 contains trees(I 1 ) + trees(I 2 ) + 1 connected components. The nodes on the left border of its minimal tree are given by those of T 1 , then k, then those of T 2 , i.e. this is exactly Q α . Let Q i be the minimal tree of P i . To go from P i to P i+1 , a decreasing relation is added to the vertex k: this corresponds to a rotation between the node k of Q i and its parent node. This process ends when T 2 is entirely been passed on the right of the node k. We then obtain the tree Q m = Q ω .
The interval between Q α and Q ω is actually a saturated chain: As an example, the interpretation of the computation on Figure 12 in terms of intervals is given on Figure 13.
The composition of intervals can be decomposed into two different operations: a left product • and a right product ← − δ .
Definition 3.5. Let I 1 and I 2 be two interval-posets such that trees(I 2 ) = m with x 1 < x 2 < · · · < x m the roots of the trees of F ≥ (I 2 ). Let α and ω be respectively the label of minimal value of I 2 and the label of maximal value of I 1 . Then (1) I 1 •I 2 is the interval-poset obtained by a shifted concatenation of I 1 and I 2 with the increasing relations y ⊳ α for all y ∈ I 1 . (2) I 1 ← − δ I 2 is the sum of the m + 1 interval-posets P 0 , P 1 , . . . , P m where P i is the shifted concatenation of I 1 and I 2 with exactly i added decreasing relations: x j ⊳ ω for j ≤ i.
From the description of the composition given by (14), it is clear that where u is the interval-poset with a single vertex. The order on the two operations is not important: 3.2. Enumeration of interval-posets. The B operator can also be decomposed into two operations, where And we have The composition of interval-posets is a combinatorial interpretation of the B operator as stated in the following Proposition.
Proof. Let I 1 and I 2 be two interval-posets. The left product I 1 •I 2 is the shifted concatenation of I 1 and I 2 on which only increasing relations have been added. Clearly, (26) P(I 1 •I 2 ) = y size(I 1 )+size(I 2 ) x trees(I 1 )+trees(I 2 ) = P(I 1 ) P(I 2 ) which proves (23). Now, let I 2 be such that trees(I 2 ) = m and let x 1 < x 2 < · · · < x m be the roots of F ≥ (I 2 ). By definition, where exactly i decreasing relations have been added between roots x 1 , . . . , x i of F ≥ (I 2 ) and the vertex with maximal label of I 1 . We have trees(P i ) = trees(I 1 ) + trees(I 2 ) − i because each added decreasing relation reduces the number of trees by one. Then Now, to prove theorem 3.2, we only need the following proposition.
Proposition 3.7. Let I be an interval-poset, then, there is exactly one pair of intervals I 1 and I 2 such that I appears in the composition B(I 1 , I 2 ).
Proof. Let I be an interval-poset of size n and let k be the vertex of I with maximal label such that i ≺ k for all i < k. The vertex 1 satisfies this property, so one can always find such a vertex. We prove that I only appears in the composition of I 1 by I 2 , where I 1 is formed by the vertices and relations of 1, . . . , k − 1 and I 2 is formed by the re-normalized vertices and relations of k + 1, . . . , n. Note that one or both of these intervals can be of size 0.
Conditions (i), (ii), and (iii) of Definition 3.3 are clearly satisfied by construction. If condition (iv) is not satisfied, it means that we have a relation k ≺ j with j > k. Then, by definition of an interval-poset, we also have ℓ ≺ j for all k < l < j and by definition of k, we have i ≺ k ≺ j for all i < k, so for all i < j, we have i ≺ j. This is not possible as k has been chosen to be maximal among vertices with this property.
This proves that I appears in the composition of I 1 by I 2 . Now, if I appears in B(I ′ 1 , I ′ 2 ), the vertex k ′ = |I ′ 1 | + 1 is by definition the vertex where for all i < k ′ , we have i ≺ k ′ and for all j > k ′ , we have k ′ ⊀ j, this is exactly the definition of k. So k ′ = k which makes I ′ 1 = I 1 and I ′ 2 = I 2 .
where B T is the Tamari polynomial of Definition 1.1. Theorem 1.2 is proved by the following proposition. Proof. Let T be a binary tree of size n such that T = k(T L , T R ). The interval-poset of the initial interval [T 0 , T ] is F ≤ (T ), the initial forest of T . From Proposition 2.9 (iii), the sum S T is the sum of all intervalposets I which extends F ≤ (T ) by adding only decreasing relations.
Let I be an interval of S T . Let I L and I R be the sub-posets obtained by restricting I to respectively 1, . . . , k − 1 and k + 1, . . . , n. By the recursive definition of initial forests given by Figure 8, I L and I R are poset extensions of respectively F ≤ (T L ) and F ≤ (T R ) where only decreasing relations have been added. And then I L ∈ S T L and I R ∈ S T R . Finally, it is clear that I ∈ B(I L , I R ). Indeed, I is a poset extension of F ≤ (T ) and so i ⊳ k for i < k and k ⋪ j for j > k.
Conversely, if I L and I R are elements of respectively S T L and S T R , then any interval I of B(I L , I R ) is in S T . Indeed, by construction, I is an extension of F ≤ (T ) where only decreasing relations have been added.
For a given tree T , the coefficient of the monomial with maximal degree in x in B T is always 1. It corresponds to the initial interval F ≤ (T ). The interval with the maximal number of decreasing relations corresponds to [T, T ]. An example of B T and of the computation of smaller trees is presented in Figure 14.  And if we set T = k(T L , T R ), by the induction hypothesis, we have that B T L = P(S T L ) and B T R = P(S T R ). The result is then a direct consequence of Propositions 3.6 and 3.8, 3.4. Bivariate polynomials. In some very recent work [9], Chapoton computed some bivariate polynomials that seem to be similar to the ones we study. By computing the first polynomials of [9, formula (7)], one notices [10] that for b = 1 and t = 1 − 1/x it is equal to B T (x), where T is a binary tree with no left subtree. The non planar rooted tree corresponding to T is the non planar version of the planar forest F ≥ (T ).
A b parameter can be also be added to our formula. For an interval [T ′ , T ], it is either the number of nodes in T ′ which have a right subtree, or in the interval-poset the number of nodes x with a relation y ⊳ x and y > x. By a generalization of the linear function P, one can associate a monomial in b, x, and y with each interval-poset. The bilinear form now reads: where f and g are polynomials in x, b, and y. Proposition 3.6 still holds, since a node with a decreasing relation is added in all terms of the composition but one. As an example, in Figure 12, one has B(y 3 With this definition of the parameter b, the bivariate polynomials B T (x, b) where T has no left subtree seem to be exactly the ones computed by Chapoton in [9] when taken on t = 1 − 1/x. This correspondence and its meaning in terms of algebra and combinatorics should be explored in some future work. They can also be interpreted as words on a binary alphabet and the notion of primitive path still holds. Indeed, a primitive path is a mballot path which does not touch the line y = x m outside its extremal points. From this, the definition of the rotation on Dyck path given in Section 2 can be naturally extended to m-ballot-paths, see Figure 15.
When interpreted as a cover relation, the rotation on m-ballot paths induces a well defined order, and even a lattice [5]. This is what we call the m-Tamari lattice or T (m) n , see Figure 16 for an example.  A formula counting the number of intervals in T (m) n was conjectured in [5] and was proven recently in [7]. The authors use a functional equation that is a direct generalization of (12). Let Φ (m) (x, y) be the generating function of intervals of the m-Tamari lattice where y is the size n and x a statistic called number of contacts, then [7, formula (3)] reads 2 where B (m) is a m + 1-linear form defined by Expanding (12), we obtain a sum of m + 1-ary trees. This leads to think that the formula of Theorem 1.2 for counting smaller elements in the lattice generalizes in the m-Tamari case, this is indeed true and we prove it in this section. It is then possible to compute the binary tree image of the minimal m-Dyck path by the bijection described in Section 2. We call this tree the (n, m)-comb: it is a left-comb of n right-combs of size m, as illustrated on Figure 18. The m-Tamari lattice is then given by the upper ideal of the (n, m)-comb, see Figure 19. It is possible to describe these trees in terms of a (m + 1)-structure.

Interpretation in terms of trees. It was proven in [7] that T
m-ballot path m-Dyck path Binary tree The tree T L is the left subtree of the first root note. The right subtree is formed by T R 1 on which the second root node has been grafted on the left of its leftmost node. The right subtree of this root node is then T R 2 on which the third root node has been grafted and so on. If a tree T R i is empty, then the i + 1 root node is directly the right child of the root node i.

Proposition 4.2. A binary tree T is a m-binary tree if and only if it is of size n × m and its binary search tree satisfies:
This property can be checked on Figure 21 which is the binary search tree of the m-binary tree of Figure 20.
Proof. The property is proved by induction on n. Let T be a m-binary tree composed of the m-binary trees T L , T R 1 , . . . , T Rm which satisfy (45) by induction hypothesis. We prove that T also satisfies (45). The root of T is labelled by x = |T L | + 1. Because T L is a m-binary tree, we have that |T L | = k.m for some k ∈ N, and so x = k.m + 1. The m-binary tree structure makes it clear that Besides, the labelling of T L in T has not been changed, the one of T Rm Figure 19. The lattice T (2) 3 on m-binary tree has been shifted by |T L | + m, the one of T R m−1 has been shifted by |T L | + |T Rm | + m and so on. The labels are shifted by multiples of m only which means that (45) still holds on T . Now let T be a binary search tree which satisfies (45), we have to prove that T satisfies the recursive structure of m-binary tree. Let x be the root of T . The node x does not precede any element of T so it has to be of the form x = k.m + 1 for some 0 ≤ k < n. Let T L be the left subtree of T , then |T L | = km and by induction, T L is a m-binary tree. We have x + 1 ⊳ x, i.e., x + 1 is in the right subtree of x. More precisely, it is the leftmost node of the right subtree. Let T R 1 be the binary tree in-between x and x + 1. For 0 ≤ a < n and Figure 20. Structure of m-binary trees with an example for m = 2: T L is in red, T R 1 is in dotted blue and T R 2 is in dashed green.  This description of the m-Tamari lattices on m-binary trees allows for a generalization of our results from Section 3. We can also use it to answer questions asked in [7] and give the full description of the m-Tamari lattices on m + 1-ary trees.
Indeed, it is easy to associate a m+1-ary tree with a m-binary tree. If T is a non empty m-binary tree composed of T L , T R 1 , . . . , T Rm , it is associated with the m+1-ary treeT whose subtrees areT L ,T R 1 , . . . ,T Rm . An example is given on Figure 22.
The bijection between Dyck paths and binary trees gives us the bijection between m-Dyck paths and m-binary trees and so from m-ballot paths and m + 1-ary trees. It can also be described directly.The mballot paths also satisfy a m + 1-ary structure. A m-ballot path D is recursively described by x + 1

R2
Type 2 rotation Figure 24. Rotations of type 1 and 2 in m-binary trees and m + 1-ary trees which is exactly the structure of the corresponding m + 1-ary tree as illustrated by Figure 22. With this bijection, the m-Tamari lattice can be given directly on m + 1-ary trees which we did in Figure 23. The cover relation can be understood from the m-binary tree rotations. There are two kinds of rotations on m-binary trees: between the root of T L and the root of T , and between another root node of T and the leftmost node of a tree T R i . This gives us two kind of rotations on m + 1-ary trees (see Figure 24): from the left branch to the first right branch, and from one right branch to the next one.
where ≻ and ≺ δ are the left and right products defined in (19) and (20).
This new definition of B (m) (48) is equivalent to the previous one (43) and this theorem is just a reformulation of Propostion 8 of [7]. In this section, we propose a new proof by generalizing the concept of interval-poset. By composing two m-interval-posets, one does not obtain a sum on m-interval-posets: the sizes are not multiples of m anymore. We have to generalize the B composition to a m-composition which has to be a m + 1-linear operator. A simple translation of (48) in terms of • and ← − δ is not enough. Indeed, it wouldn't generate all m-interval-posets. However, the following expression reflects the m-binary structure given by Figure 20. We then rewrite (48) by using this observation. As an example, for m = 3, one obtains The ≺ δ x operation can be interpreted on interval-posets.
Definition 4.7. Let I 1 and I 2 be two interval-posets such that trees(I 2 ) = k. Let y be the maximal label of I 1 and x 1 , . . . , x k be the roots of F ≥ (I 2 ). Then I 1 ≺ δ x I 2 is the sum of the k interval-posets P 1 , . . . , P k where P i is the shifted concatenation of I 1 and I 2 with the i added decreasing relations: x j ⊳ y for j ≤ i.
The sum I 1 ← − δ x I 2 is just the sum I 1 ← − δ I 2 of Definition 3.5 minus the P 0 poset (the shifted concatenation with no extra decreasing relation). In particular, this means that the obtained interval-posets all have the relation 2 ⊳ 1 because 1 is always the minimal root of F ≥ (I 2 ).
where u the interval-poset containing a single vertex. Recursively, the definition reads By redoing this operation, we obtain that R(I R 1 , . . . , I Rm ) is a sum of interval-posets which all have the relations m ⊳ m − 1 ⊳ . . . ⊳ 1. The labels of I Rm are shifted by m, those of I R m−1 by m + |I Rm | and so on until I R 1 whose labels have been shifted by m + |I R 2 | + · · · + |I Rm |. This means that R(I R 1 , . . . , I Rm ) is an m-interval-poset. So is I L • R(I R 1 , . . . , I Rm ) because the left product on two m-interval-posets is still a m-interval-poset.
As an example, here is a detailed computation for m = 2. (65) As explained in the proof, the intervals resulting of a m-compositions all share the same maximal tree given by the structure of the m-binary tree. The minimal trees range from a tree where all minimal trees of composed intervals have been grafted at the left of one another to the m-binary tree formed by all minimal trees. This illustrated in the case where m = 2 on Figure 25.
The vertices a 1 , . . . , a m satisfy Condition (iii) of Proposition 4.9. They allow us to cut I into m + 1 subposets. If a j = ∅ then I R j = ∅, otherwise I R j is the subposet of I of which a j is the minimal label.
All conditions of Proposition 4.9 are satisfied and so I ∈ B (m) (I L , I R 1 , . . . , I Rm ). Besides, the vertices a 1 , . . . , a m are the only one to satisfy Condition (iii) of Proposition 4.9 without adding any increasing relations to I 0 : they give the only way to cut the poset I. With Propositions 4.10 and 4.11, we now have a new proof of the functional equation (42) already described in [7]. We can go further and give a generalized version of Theorem 1.2.

4.4.
Counting smaller elements in m-Tamari. Proof. Let I 0 be the interval [T 0 , T ] where T 0 is the (n, m)-comb, i.e., the minimal m-binary tree. The increasing relations of I 0 are the ones of T and the decreasing relations are (45). We cut I 0 into the subposets I L , I R 1 , I R 2 , . . . , I Rm following the cutting of T (the labels of I R j in I 0 are the ones of T R j in T ). By construction, the m-intervalposets I L , I R 1 , . . . , I Rm are the initial m-Tamari intervals of respectively T L , T R 1 , . . . , T Rm .
Let P be an interval-poset of the sum S T , i.e. an poset extension of I 0 where only decreasing relations have been added. By cutting P in the same way than I 0 , then P L , P R 1 , . . . , P Rm are extensions of respectively I L , I R 1 , . . . , I Rm and so appear respectively in S T L , S T R 1 , . . . , S T Rm . And by Proposition 4.9, because the increasing relations of P are those of I 0 , then P ∈ B (m) (P L , P R 1 , . . . , P Rm ).
Conversely, if P L , P R 1 , . . . , P Rm are elements of respectively S L , S R 1 , . . . , S Rm , then the increasing relations of the elements of B (m) (P L , P R 1 , . . . , P Rm ) are those of T which make them elements of S T .