The enumeration of generalized Tamari intervals

Abstract

Let $v$ be a grid path made of north and east steps. The lattice $\mathrm{T}\mathrm{AM}(\mathrm{v})$, based on all grid paths weakly above $v$ and sharing the same endpoints as $v$, was introduced by Préville-Ratelle and Viennot (2014) and corresponds to the usual Tamari lattice in the case $v=(NE{)}^n$. Our main contribution is that the enumeration of intervals in $\mathrm{T}\mathrm{AM}(\mathrm{v})$, over all $v$ of length $n$, is given by $\frac{2(3n+3)!}{(n+2)!(2n+3)!}$. This formula was first obtained by Tutte(1963) for the enumeration of non-separable planar maps. Moreover, we give an explicit bijection from these intervals in $\mathrm{T}\mathrm{AM}(\mathrm{v})$ to non-separable planar maps.

19 pages, 11 figures. Title changed, originally titled "From generalized Tamari intervals to non-separable planar maps (extended abstract)", submitted

References in corpus (1)

• Sur le nombre d'intervalles dans les treillis de Tamari

Cited by in corpus (12)

• Planar triangulations, bridgeless planar maps and Tamari intervals
• Hopf dreams and diagonal harmonics
• A trinity of duality: non-separable planar maps, $\beta$-(1,0) trees and synchronized intervals
• The Steep-Bounce Zeta Map in Parabolic Cataland
• Fighting fish and two-stack sortable permutations
• A partial order on Motzkin paths
• Bijective link between Chapoton's new intervals and bipartite planar maps
• Three Fuss-Catalan posets in interaction and their associative algebras
• Cambrian triangulations and their tropical realizations
• $F$- and $H$-Triangles for $\nu$-Associahedra
• The $s$-weak order and $s$-permutahedra I: combinatorics and lattice structure
• Bijections between planar maps and planar linear normal $\lambda$-terms with connectivity condition