# An extension of Tamari lattices

Louis-François Préville-Ratelle, Xavier Viennot

► To cite this version:

Louis-François Préville-Ratelle, Xavier Viennot. An extension of Tamari lattices. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.133-144, 10.46298/dmtcs.2535 . hal-01337833

HAL Id: hal-01337833

https://hal.science/hal-01337833

Submitted on 27 Jun 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# An extension of Tamari lattices

Louis-François Préville-Ratelle¹† and Xavier Viennot²‡

¹Instituto de Matemática y Física, Universidad de Talca, 2 norte 685, Talca, Chile.

² LABRI, CNRS, Université de Bordeaux, Bordeaux, France

**Abstract.** For any finite path $v$ on the square lattice consisting of north and east unit steps, we construct a poset Tam$(v)$ that consists of all the paths lying weakly above $v$ with the same endpoints as $v$. For particular choices of $v$, we recover the traditional Tamari lattice and the $m$-Tamari lattice. In particular this solves the problem of extending the $m$-Tamari lattice to any pair $(a, b)$ of relatively prime numbers in the context of the so-called rational Catalan combinatorics.

For that purpose we introduce the notion of canopy of a binary tree and explicit a bijection between pairs $(u, v)$ of paths in Tam$(v)$ and binary trees with canopy $v$. Let $\overline{v}$ be the path obtained from $v$ by reading the unit steps of $v$ in reverse order and exchanging east and north steps. We show that the poset Tam$(v)$ is isomorphic to the dual of the poset Tam$(\overline{v})$ and that Tam$(v)$ is isomorphic to the set of binary trees having the canopy $v$, which is an interval of the ordinary Tamari lattice. Thus the usual Tamari lattice is partitioned into (smaller) lattices Tam$(v)$, where the $v$'s are all the paths of length $n-1$ on the square lattice.

We explain possible connections between the poset Tam$(v)$ and (the combinatorics of) the generalized diagonal coinvariant spaces of the symmetric group.

**Résumé.** Pour tout chemin $v$ sur le réseau carré formé de pas Nord et Est, nous construisons un ensemble partiellement ordonné Tam$(v)$ dont les éléments sont les chemins au dessus de $v$ et ayant les mêmes extrémités. Pour certains choix de $v$ nous retrouvons le classique treillis de Tamari ainsi que son extension $m$-Tamari. En particulier nous résolvons le problème d'étendre le treillis $m$-Tamari à toute paire $(a, b)$ d'entiers premiers entre eux dans le contexte de la combinatoire rationnelle de Catalan.

Pour ceci nous introduisons la notion de canopée d'un arbre binaire et explicitons une bijection entre les paires $(u, v)$ de chemins dans Tam$(v)$ et les arbres binaires ayant la canopée $v$. Soit $\overline{v}$ le chemin obtenu en lisant les pas en ordre inverse et en échangeant les pas Est et Nord. Nous montrons que Tam$(v)$ est isomorphe au dual de Tam$(\overline{v})$ et que Tam$(v)$ est isomorphe à l'ensemble des arbres binaires ayant la canopée $v$, qui est un intervalle du treillis de Tamari ordinaire. Ainsi le traditionnel treillis de Tamari admet une partition en plus petits treillis Tam$(v)$, où les $v$ sont tous les chemins de longueur $n-1$ sur le réseau carré. Enfin nous explicitons les liens possibles entre l'ensemble ordonné Tam$(v)$ et (la combinatoire des) espaces diagonaux coinvariants généralisés du groupe symétrique.

**Keywords:** Tamari lattice, $m$-Tamari lattice, rational Catalan combinatorics, diagonal coinvariant spaces.

<footnote>†preville-ratelle@inst-mat.utalca.cl. LFPR was supported by a Proyecto Fondecyt Postdoctorado 3140298.</footnote>

<footnote>‡viensnot@xavierviensnot.org</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1: A binary tree B and its associated complete binary tree $\bar{B}$ (left). Right rotation on a complete binary tree: the covering relation in the Tamari lattice (right).</figcaption></figure>

# 1 Introduction

In this paper, we generalize the *m*-Tamari lattice to posets of arbitrary paths, as it is explained in section 2. We prove that these posets are actually lattices, that they satisfy a duality property, and that they partition the ordinary Tamari lattice into intervals. We first introduce some basic definitions in section 1.1 and some motivations in section 1.2.

## 1.1 Basic definitions

A binary tree is either empty or a triple (*L*, *r*, *R*) where *L* and *R* are binary trees (left and right subtrees) and *r* is the root of the binary tree. If *L* (resp. *R*) is not empty, its root is called the left (resp. right) child of *r*. A binary tree is complete when all vertices have either two children (internal vertices) or no child (external vertices). Figure 1 displayed the classical bijection between binary trees and complete binary trees. We denote by $\bar{B}$ the complete binary tree associated to *B*.

These two families of trees are enumerated by the well studied Catalan numbers $C_n = \frac{1}{2^{n+1}} \binom{2n+1}{n}$.

We now define the Tamari lattice. The complete binary trees with *n* interior vertices can be equipped with a rotation. As in Figure 1, consider a complete binary tree $\bar{T}$ with an internal vertex *s* such that the left child of *s*, denoted by *t*, is also an internal vertex. Let *A* be the left subtree of *t*, *B* the right subtree of *t* and *C* the right subtree of *s*. Let $\bar{T}'$ be the complete binary tree constructed from $\bar{T}$ such that *t* becomes the right child of *s*, *A* the left subtree of *s*, *B* the left subtree of *t* and *C* the right subtree of *t*. This operation from $\bar{T}$ to $\bar{T}'$ is called a right rotation, and the operation from $\bar{T}'$ to $\bar{T}$ is called a left rotation. The right rotation define the covering relation of the well known Tamari lattice (see [27, 13]), denoted by $\bar{T} \prec \bar{T}'$.

In this article, we consider a path to be a (finite) walk on the square lattice, starting at (0,0), consisting of north and east unit steps denoted by *N* and *E* respectively. The set of ballot paths of height *n* is the set of paths that consist of *n* north steps, *n* east steps and lie weakly above the diagonal, that is, weakly above the path (*N*E)*^n*. They are also counted by the Catalan numbers. By applying a clockwise rotation of 45 degrees on ballot paths so that the diagonal becomes horizontal, these ballot paths become the well known Dyck paths (see Figure 2). The ballot paths can be generalized with a parameter *m* that is a positive integer. The *m*-ballot paths are the paths that consist of *n* north steps, *mn* east steps and lie weakly above the line $y = \frac{x}{m}$, that is, weakly above the path (*N*E*m*)^n.
<figure><img src="image_3.png" /><figcaption>Fig. 2: Ballot path and Dyck path.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>**Fig. 3:** The Tamari covering relation for ballot (Dyck) path (left). The covering relation in the *m*-Tamari lattice (*m*=2) (right).</figcaption></figure>

Using the bijection between complete binary trees with $n$ internal vertices and ballot paths of height $n$, which is called the postorder traversal on edges, the covering relations for the Tamari lattice can be translated into the following procedure on ballot paths. Let $D$ be a ballot path of height $n$. Let $E$ be an east step that precedes a north step in $D$. Draw a diagonal of slope 1 starting at the right extremity of $E$ until it touches $D$ again. Construct $D'$ from $D$ by switching $E$ and the portion of the path above this diagonal. Then the covering relation in the Tamari lattice based on ballot paths becomes $D \prec D'$ (see Figure 3 for such a covering relation). Motivated by the higher diagonal coinvariant spaces of the symmetric group, the covering relation on ballot paths is generalized in [5] to *m*-ballot paths by mimicking the above procedure as follows. Let $D$ be an *m*-ballot path. Let $E$ be an east step that precedes a north step in $D$. Draw a diagonal of slope $1/m$ starting at the right endpoint of $E$ until it touches $D$ again. Construct $D'$ from $D$ by switching $E$ and the portion of the path above this diagonal. Then the covering relation in the *m*-Tamari lattice is given by $D \prec D'$ (see Figure 3 for an example). For more on these lattices and for enumerations of their intervals, we refer the reader to section 5.

## 1.2 Rational Catalan combinatorics (a, b)

Let $a$ and $b$ be two relatively prime integers. We consider paths starting at (0, 0) on the square lattice with north and east steps and strictly above the line $y = \frac{a}{b}x$, excluding the start and end points (see [7]). They are called (*a*, *b*)-ballot paths (or (*a*, *b*)-Dyck paths), and their study is the subject of very recent work under the term “rational Catalan combinatorics” (see [2, 3, 14, 15, 20] for more on this subject). The classical ballot paths and their extensions with any integer $m$ are particular cases of such (*a*, *b*)-ballot paths. The simple Catalan ballot paths are obtained by putting $(a, b) = (n, n+1)$, and their $m$-extensions are obtained by putting $(a, b) = (n, mn+1)$.

An open question is to give an extension of the Tamari lattice, and more generally of the *m*-Tamari lattice to any pair $(a, b)$ of relatively prime integers. We propose an answer to this question, by giving
a far more general extension of these Tamari lattices and in particular give a construction of a rational
$(a, b)$-Tamari lattice.

## 2 Extension: The Tamari lattice Tam$(v)$, where $v$ is an arbitrary path

Let $v$ be an arbitrary path, starting at (0,0). Consider all the lattice paths lying weakly above $v$ that start at (0,0) and finish at the end of $v$. We define the poset Tam$(v)$ on this set of paths with a covering relation. Let $u$ be such a path above $v$. Let $p$ be a lattice point on $u$. We define the horizontal distance $horiz_v(p)$ to be the maximum number of east steps that can be added to the right of $p$ without crossing $v$. An example of these horizontal distances is given in Figure 4 (left). Suppose that $p$ is preceded by an east step $E$ and

<figure><img src="image_5.png" /><figcaption>**Fig. 4:** A pair (u,v) of paths with the horizontal distance $horiz_v(p)$ (left). The covering relation defining the poset Tam$(v)$ (right).</figcaption></figure>

followed by a north step in $u$. Let $p'$ be the first lattice point in $u$ that is after $p$ and such that $horiz_v(p') = horiz_v(p)$. As in Figure 4 (right), let $D_{[p,p']}$ be the subpath of $u$ that starts at $p$ and finishes at $p'$. Let $u'$ be the path obtained from $u$ by switching $E$ and $D_{[p,p']}$.

We define the covering relation to be $u \prec_v u'$ (see Figure 4 (right) for an example). Then the poset Tam$(v)$ is the transitive closure $\le_v$ of this relation. It is easy to see that Tam$((NE^m)^n)$ is the $m$-Tamari lattice.

For $v$ an arbitrary path, let $\overline{v}$ be the path obtained by reading $v$ backward and replacing the east steps by north steps and vice versa. We can now state our main results:

**Theorem 1** For any path $v$, Tam$(v)$ is a lattice.

Recall from the first section that the usual Tamari lattice on complete binary trees with $n$ interior vertices is isomorphic to the lattice Tam$((NE)^n)$.

**Theorem 2** The lattice Tam$(v)$ is isomorphic to the dual of Tam$(\overline{v})$.
For any pair $(a, b)$ of relatively prime integers, we define the lattice $Tam(a, b)$ as to be the lattice $Tam(v)$ where $v$ is the minimum path above the segment passing through the origin $(0, 0)$ and the point $(a, b)$. The duality between $Tam(v)$ and $Tam(v)$ becomes the duality between $Tam(a, b)$ and $Tam(b, a)$ (see Figure 5). In this Figure we have drawn with brown dotted arrows the covering relation for the Young lattices $Y(v)$ of Ferrers diagrams included in the Ferrers diagram defined by the path $v$. The lattice $Y(v)$ can be seen as a refinement of the lattice $Tam(v)$, and in that case, by the simple symmetry exchanging rows and columns, the lattice $Y(v)$ is isomorphic to $Y(v)$.

<figure><img src="image_6.png" /><figcaption>Fig. 5: Duality and rational Catalan combinatorics: the lattices $Tam(5,3)$ and $Tam(3,5)$.</figcaption></figure>

**Theorem 3** The usual Tamari lattice $Tam((NE)^n)$ can be partitioned into disjoint intervals $I(v)$ indexed by the unitary paths $v$ consisting of a total of $n-1$ east and north steps, i.e.

$$Tam((NE)^n) = \bigcup_{|v|=n-1} I(v),$$

where each $I(v) \cong Tam(v)$.

An example of Theorem 3 is given in Figure 6.
<figure><img src="image_7.png" /><figcaption>**Fig. 6:** The decomposition of the Tamari lattice on complete binary trees with 4 interior vertices into the union of 8 disjoint intervals $Tam(v)$ (Theorem 3).</figcaption></figure>

## 3 Canopy of a binary tree

For any binary tree $B$, we construct a word $w(B)$ on the alphabet $\{a, \bar{a}, b, \bar{b}\}$. Walking clockwise around $B$ and starting at the root, we write the letter $a$ when we walk on a left edge for the first time and $\bar{a}$ when we walk on a left edge for the second time. Similarly we repeat with the letters $b$ and $\bar{b}$ for the right edges (see Figure 7 (left) for an example).

<figure><img src="image_8.png" /><figcaption>**Fig. 7:** Walk around a binary tree $B$: the word $w(B)$ (left). Second definition of the canopy (right).</figcaption></figure>

From $w(B)$, we construct two subwords. The first subword $u(B)$ is obtained by keeping track only of
<figure><img src="image_9.png" /></figure>

<figure><img src="image_10.png" /><figcaption>**Fig. 8:** The words $w(B)$, $u(B)$ and $v(B)$ associated to the binary tree in Figure 7 (left). The pair $(u,v)$ of paths associated to a binary tree in Figure 7(right).</figcaption></figure>

the two letters $\{\bar{a}, \bar{b}\}$ in $w(B)$. We identify a path with $u(B)$ by replacing in this sequence the letter $\bar{a}$ by a north step and $\bar{b}$ by an east step. The canopy $v(B)$ of $B$, which is also a subword of $w(B)$, is obtained similarly by keeping track only of the letters $\{\bar{a}, \bar{b}\}$. We identify a path with $v(B)$ by replacing in this sequence the letter $\bar{a}$ by a north step and $\bar{b}$ by an east step(i). The concept of the canopy was introduced using a different terminology in [21]. For the binary tree in Figure 7 (left), we show an example of all these words in Figure 8 (left) and draw the paths $u(B)$ and $v(B)$ in Figure 8 (right).

It is no accident that we use the same letter $v$ for the canopy as the letter that defines the poset in the previous section. Before explaining this, we can mention an easy property:

**Lemma 4** For any given binary tree $B$, the path $u(B)$ is weakly above the canopy (also a path) $v(B)$.

Let $\bar{B}$ be a complete binary tree with $n$ vertices. It is not difficult to prove that the canopy can also be defined using the following equivalent definition.

The second definition of the canopy, which is defined in [21], can be described as follows. Walking around $\bar{B}$ clockwise starting at the root, record the sequence of left and right external edges, except the first and last external edges. From this sequence, construct a path by changing the right external edges into north steps and the left external edges into east steps. The path obtained is also the canopy (see Figure 7 (right) for an example). Because of this definition, we define the interior canopy of the complete binary tree $\bar{B}$ to be the canopy of $B$.

In the proofs of the main theorems, we need a third definition of the canopy. We do not explicit its definition here. It is based on ordering the vertices of the binary tree $B$ in the so-called symmetric order (also called infix or in-order), and considering a certain order on the left edges of $B$. The sequence of "right heights" of these left edges is related to the sequence of distances between the pairing vertical edges of the paths $u$ and $v$ (the labels of the path $v$ in Figure 9).

# 4 Proofs of the main theorems

The proofs of the main theorems rely on the following 3 propositions.

<footnote>(i) So by abuse of notation, we will refer to the paths $u(B)$ and $v(B)$.</footnote>
**Proposition 5** The map defined in Section 3 associating the pair $(u, v)$ to a binary tree is a bijection from the set of binary trees with $n$ vertices to the set of unordered pairs of non-crossing paths, consisting each of a total of $n-1$ north and east steps, with the same endpoints.

The bijection between binary trees and pairs of paths $(u, v)$ was introduced in a different form ([12], [28] slides 42-53). We have described here a new version of the bijection which fits our purpose. We describe the reverse bijection in terms of a "push-gliding algorithm", which is a kind of "jeu de taquin" on a binary tree attached to a path. The algorithm starts with an empty binary tree and the path $v$ where the vertical edges are labeled by the horizontal distance to the path $u$. Reading the path $v$, from bottom to top, sliding is performed according to each labeled vertical edge and pushing according to each horizontal edge. For each pushing, a new edge is introduced in the binary tree attached to the path. At the end the path is empty and we get the binary tree related to pair $(u, v)$, (see Figure 9).

<figure><img src="image_11.png" /><figcaption>Fig. 9: The "push-gliding" algorithm</figcaption></figure>

**Proposition 6** The set $I(v)$ of complete binary trees having interior canopy $v$ is an interval of the ordinary Tamari lattice on complete binary trees with $|v| + 1$ interior vertices.

This proposition is well known, see for example Proposition 3.5 in [22] where the Boolean lattice appears as a quotient of the Tamari lattice. The intervals $I(v)$ are the fibres over points of the usual map from the Tamari lattice to the Boolean lattice. These intervals can also be viewed as the images under the map from the symmetric group to the Tamari lattice of the set of permutations with a fixed descent set. Here we give a direct combinatorial proof. The max and min element of the interval can be defined easily from the "push-gliding" algorithm mentioned above.
**Proposition 7** For any path $v$, the poset $I(v)$ is isomorphic to $\mathrm{Tam}(v)$.

The proof relies on a lemma relating the sequence of horizontal distances $\mathrm{horiz}_v(p)$ of the vertices $p$ of the path $u$ to the sequence of right heights of the vertices of the corresponding binary tree $B$ when traversed in postorder. Then the proof continues by studying the relation between the canopy and the rotation in binary tree. For binary trees with a given canopy, the rotations are restricted, and such rotations can be shown to be equivalent to the covering relation for $\mathrm{Tam}(v)$ using the lemma mentioned previously.
We can now prove our main theorems of section 2.

**Proof of Theorem 1:** An interval of a lattice is always a lattice, therefore $I(v)$ is a lattice by Proposition 6, and so is $\mathrm{Tam}(v)$ by Proposition 7. $\square$

**Proof of Theorem 2:** After applying a reflection to a binary tree with canopy $v$, it is easy to see using the second definition of canopy, that the canopy of this tree (obtained by reflection) is precisely $\bar{v}$. The left and right rotation on a complete binary tree are exchanged and we deduce from the constructions of $\mathrm{Tam}(v)$ and $\mathrm{Tam}(\bar{v})$ that these lattices are isomorphic up to duality (also called anti-isomorphic). $\square$

**Proof of Theorem 3:** We partition the complete binary trees with $n$ interior vertices into sets of trees with the same interior canopy. We then apply Proposition 7 to each set of trees. $\square$

# 5 Connections with the diagonal coinvariant spaces and perspectives

Our work has been influenced by the combinatorics of the “generalized” diagonal coinvariant spaces of the symmetric group. We give a brief description of the subject here, and refer the reader to [4, 5, 8, 9, 16] for more details.

Let $X = (x_{i,j})_{\substack{1 \le i \le k \\ 1 \le j \le n}}$ be a matrix of variables. A permutation $\sigma$ of the symmetric group $S_n$ permutes the variables columnwise by $\sigma(X) = (x_{i,\sigma(j)})_{\substack{1 \le i \le k \\ 1 \le j \le n}}$, i.e. $\sigma(x_{i,j}) = x_{i,\sigma(j)}$. This action can be directly extended to all the polynomials in $\mathbb{C}[X]$. All the variables in a same row of $X$ are said to be contained in the same set of variables. Since $X$ contains $k$ rows, there are $k$ sets of variables. Let $\mathcal{J}$ be the ideal generated by constant free invariant polynomials under this action. The diagonal coinvariant spaces of $S_n$ are defined as $\mathcal{D}\mathcal{R}_{k,n} := \mathbb{C}[X]/\mathcal{J}$. They can be generalized using an additional parameter $m$ that is a positive integer. The higher diagonal coinvariant spaces of the symmetric group are defined as $\mathcal{D}\mathcal{R}_{k,n}^m := \varepsilon^{m-1} \otimes \mathcal{A}^{m-1}/\mathcal{J}\mathcal{A}^{m-1}$, where $\varepsilon$ is the sign representation and $\mathcal{A}$ is the ideal generated by alternants, i.e. polynomials $f(X)$ such that $\sigma f(X) = \varepsilon(\sigma)f(X), \forall \sigma \in S_n$. Note that $\mathcal{D}\mathcal{R}_{k,n} = \mathcal{D}\mathcal{R}_{k,n}^1$. The $\mathcal{D}\mathcal{R}_{k,n}^m$ are representations of $S_n$ because the action given above can be applied to the quotient space $\mathcal{D}\mathcal{R}_{k,n}^m$. They are graded with respect to the degree of each set of variables. We denote the subspace of alternants of $\mathcal{D}\mathcal{R}_{k,n}^m$ by $\mathcal{D}\mathcal{R}_{k,n}^m \varepsilon$.

In the case $k=1$, they are classical [26] and the dimensions of $\mathcal{D}\mathcal{R}_{1,n}^m \varepsilon$ and $\mathcal{D}\mathcal{R}_{1,n}^m$ are given by 1 and $n!$, respectively.

In the case $k=2$, they were first defined and studied by Garsia and Haiman because of their connections with the Macdonald polynomials. It was proven by Haiman [18] that the dimensions of $\mathcal{D}\mathcal{R}_{2,n}^m \varepsilon$ and $\mathcal{D}\mathcal{R}_{2,n}^m$ are given by $\frac{1}{(m+1)n+1} \binom{(m+1)n+1}{mn}$ and $(mn+1)^{n-1}$, respectively. The first number corresponds
to the number of *m*-ballot paths of height *n* and the second one to the number of *m*-parking functions of height *n*. The *m*-parking functions of height *n* are simply the *m*-ballot paths labelled on the north steps, with the labels in the set {1, 2, ..., *n*} such that consecutive north steps are labelled increasingly. The spaces *DR*<sub>2,*n*</sub><sup>*m*</sup> have been studied by many researchers for more than 20 years. Despite that, there are still some important unresolved conjectures left in the field. We mention only one here. The *m*-shuffle conjecture [17] states that the graded Frobenius series of *DR*<sub>2,*n*</sub><sup>*m*</sup> is equal to a *q*, *t*-weighted sum on *m*-parking functions, which involves the combinatorial statistics *area* and *dinv*, and some quasi-symmetric functions associated to these *m*-parking functions.

For the case $k=3$, Haiman [19] conjectured in the 1990's that the dimensions of $\mathcal{DR}_{3,n}^{\epsilon}$ and $\mathcal{DR}_{3,n}$ are equal to $\frac{2}{n(n+1)} \binom{4n+1}{n-1}$ and $2^n(n+1)^{n-2}$ respectively.

Independently of all this story, Chapoton [10] proved in 2006 that the number of intervals in the Tamari lattice based on complete binary trees with *n* interval vertices is given by $\frac{2}{n(n+1)} \binom{4n+1}{n-1}$. In 2008, the *m*-Tamari lattice was introduced in [5] and it was conjectured that the number of intervals and labelled intervals in the *m*-Tamari lattice are given by $\frac{m+1}{n(mn+1)} \binom{(m+1)^2n+m}{n-1}$ and $(m+1)^n(mn+1)^{n-2}$, respectively. A labelled interval in the *m*-Tamari lattice is simply an interval where the top path is decorated as a *m*-parking function. Refinements of these two results were proven in [8, 9].

The duality that is proved in this article shows that the number of intervals in Tam((N^mE)^n) is the same as in the *m*-Tamari lattice Tam((NE^m)^n). Using refinements and calculations, it seems that the number of labelled intervals in Tam((NE^m)^n) is equal to the number of labelled intervals on east steps in Tam((N^mE)^n), where the labelled intervals on east steps are defined by assigning the labels in the set {1, 2, ..., *n*} on east steps of the upper path, and such that the labels on consecutive east steps are increasing. Note that for *m* = 1, this is easy to prove since you can obtain without difficulty the same functional equations for both cases from recurrences. But we have not been able to do so in the case *m* > 1. It would be interesting to see if the ideas presented in [11] could help prove this equality.

More recently, some researchers (see [1, 2, 6, 20]) have extended the combinatorics of the $\mathcal{DR}_{2,n}^m$ by considering paths and parking functions above the line with endpoints (0,0) and $(b, a)$, where $a, b$ are arbitrary positive integers$^{(ii)}$. They defined the combinatorial statistics area and dinv on these objects. So this rational Catalan combinatorics can be seen as the combinatorics of some possible generalizations of the spaces $\mathcal{DR}_{2,n}^m$. Even though these spaces have not yet been shown to exist, some preliminary calculations [6] suggest that they do. One might try now to define a dinv statistic on paths and parking functions above an arbitrary path consisting of east and north steps, even if it is not known to be possible.

It remains to be seen if our lattices Tam(*v*), for arbitrary paths *v*, will give a combinatorial setup for the not yet defined generalizations$^{(iii)}$ of the spaces $\mathcal{DR}_{3,n}^m$. It will be interesting to verify this as the theory of the “generalized” diagonal coinvariant spaces develops.

We finish this article by mentioning that in a forthcoming paper [23], it will be shown that the total number of intervals in the lattices Tam(*v*), for all the paths *v* of length *n*, is given by $\frac{2(3n+3)!}{(n+2)!(2n+3)!}$, which is the same as the number of rooted non-separable planar maps with *n* + 2 edges (sequence A000139 of OEIS).

<footnote>(ii) Note that the paths above the line with endpoints (0,0) and (mn, n) are the same as the paths above the line with endpoints (0,0) and (mn + 1, n), this is why we use the term extension.</footnote>

<footnote>(iii) As it is explained in the previous paragraph, at the moment it is not known if these generalizations exist.</footnote>
Acknowledgements

We are very grateful to Luc Lapointe for inviting the two authors to Talca, making the collaboration between them possible, for many fruitful discussions and for his constant support during the entire process of this work.

LFPR would like to thank François Bergeron for many fruitful discussions, in particular for providing the first author a conjectural formula that was one of his motivations for this work, and to Ruben Escobar and Miles Jones for multiple corrections.

XV is grateful to Kurusch Ebrahimi-Fard, Vincent Pilaud and Juanjo Rué for inviting him to the workshop in Madrid (27-29 November 2013) "Recent trends in algebraic and geometric combinatorics" to present part of this work, together with some related work (see [28]), and to Mireille Bousquet-Mélou, Michael Drmota, Christian Krattenthaler and Marc Noy for inviting him at the Oberwolfach workshop (3-7 March 2014) "Enumerative Combinatorics" to present the work described in this paper.

References

[1] D. Armstrong, Rational Catalan Combinatorics, Personal website, http://www.math.miami.edu/ armstrong/.

[2] D. Armstrong, B. Rhoades and N. Williams, Rational associahedra and noncrossing partitions, *Electronic J. Combin.*, 20(3): Paper 54, 27, 2013.

[3] D. Armstrong, N.A. Loehr and G.S.Warrington, Rational parking functions and Catalan numbers, ArXiv: 1403.1845, 2014.

[4] F. Bergeron, *Algebraic combinatorics and coinvariant spaces*, CMS Treatises in Mathematics, Canadian Math. Soc., Ottawa, ON, 2009.

[5] F. Bergeron and L.-F. Préville-Ratelle, Higher trivariate diagonal harmonics via generalized Tamari posets, *J. Comb.* 3(3):317-341, 2012.

[6] F. Bergeron, A. Garsia, E. Leven and G. Xin, Compositional $(km, kn)$-shuffle conjectures, ArXiv: 1404.4616, 2014.

[7] M.T.L. Bizley, Derivation of a new formula for the number of minimal lattice paths from (0,0) to (km, kn) having just t contacts with the line my = nx and having no points above this line; and a proof of Grossman's formula for the number of paths which may touch but do not rise above this line, *J. Inst. Actual.*, 80:55-62, 1954.

[8] M. Bousquet-Mélou, E. Fusy and L.-F. Préville-Ratelle, The number of intervals in the $m$-Tamari lattices, *Electron. J. Combin.*, 18(2):Research paper 31, 26p. (electronic), 2011, ArXiv 1106.1498.

[9] M. Bousquet-Mélou, G. Chapuy and L.-F. Préville-Ratelle, The representation of the symmetric group on $m$-Tamari intervals, *Adv. Maths.*, 247:309-342, 2013.

[10] F. Chapoton, Sur le nombre d'intervalles dans les treillis de Tamari, *Sém. Lothar. Combin.*, Art. B55f, 18 pp. (electronic), 2006.
[11] G. Chatel and V. Pons, Counting smaller elements in the Tamari and *m*-Tamari lattices, in *Proceed-ings FPSAC 2013*, Paris, DMTCS, 463-474, 2013, ArXiv: 1212.0751.

[12] M. Delest and X. Viennot, Algebraic languages and polyominoes enumeration, *Theoretical Comp. Science*, 34: 169-206, 1984.

[13] H. Friedman and D. Tamari, Problèmes d'associativité: une structure de treillis fini induite par une loi demi-associative, J. Combinatorial Theory, 2:215-242, 1967.

[14] E. Gorsky and A. Negut, Refined knot invariants and Hilbert schemes, ArXiv: 1304.3328, 2013.

[15] E. Gorsky, M. Mazin and M. Vazirani, Affine permutations and rational slope parking functions, ArXiv: 1403.0303, 2014.

[16] J. Haglund, *The q,t-Catalan numbers and the space of diagonal harmonics*, Volume 41 of University Lecture Series, Amer. Math. Soc., Providence, RI, 2008.

[17] J. Haglund, M. Haiman, N. Loehr, J.B. Remmel and A. Ulyanov, A combinatorial formula for the character of the diagonal coinvariants, *Duke Math. J.*, 126(2):195-232, 2005.

[18] M. Haiman, Vanishing theorems and character formulas for the Hilbert scheme of points in the plane, *Invent. Math.*, 149(2):371-407, 2002.

[19] M. Haiman, Conjectures on the quotient ring by diagonal invariants, *J. Algebraic Combin.*, 3(1):17-76, 1994.

[20] T. Hikita, Affine Springer fibers of type A and combinatorics of diagonal coinvariants, ArXiv: 1203.5878, 2012.

[21] J.-L. Loday and M.O. Rocco, Hopf algebra of the planar binary trees, *Adv. Math.*, 139(2):293-309, 1998.

[22] J.-L. Loday and M.O. Ronco, Order structure on the algebra of permutations and of planar binary trees, *J. of Algebraic Combinatorics*, 15, 253-270, 2002.

[23] L.-F. Préville-Ratelle, On the number of canopy intervals in the Tamari lattices, in preparation.

[24] L.-F. Préville-Ratelle and X. Viennot, An extension of Tamari lattice, ArXiv:1406.3787, full version of this extended abstract to be published in *Trans. Amer. Math. Soc*.

[25] R.P. Stanley, *Enumerative Combinatorics*, Vol 2, Cambridge University Press, Cambridge, 1999.

[26] R. Steinberg, Differential equations invariant under finite reflection groups, *Trans. Amer. Math. Soc.*, 112:392-400, 1964.

[27] D. Tamari, The algebra of bracketings and their enumeration, *Nieuw Archief voor Wiskunde*, 1962.

[28] X. Viennot, Canopy of binary trees, intervals in associahedra and exclusion model in physics, Workshop "Recent trends in Algebraic and Geometric Combinatorics", ICMAT, Madrid, 28 Nov 2013, slides of the talk at: http://www.xavierviennot.org/xavier/exposes_files/Madrid_nov13v2.pdf