Intervals in the greedy Tamari posets

We consider a greedy version of the \ (m\) -Tamari order defined on \ (m\) -Dyck paths, recently introduced by Dermenjian. Inspired by intriguing connections between intervals in the ordinary 1-Tamari order and planar triangulations, and more generally by the existence of simple formulas counting intervals in the ordinary \ (m\) -Tamari orders, we investigate the number of intervals in the greedy order on \ (m\) -Dyck paths of fixed size. We find again a simple formula, which also counts certain planar maps (of prescribed size) called \ ( (m+1) \) -constellations. For instance, when \ (m=1\) the number of intervals in the greedy order on 1-Dyck paths of length \ (2n\) is proved to be \ (3 2^n-1 (n+1) (n+2) 2nn\), which is also the number of bipartite maps with \ (n\) edges. Our approach is recursive, and uses a "catalytic" parameter, namely the length of the final descent of the upper path of the interval. The resulting bivariate generating function is algebraic for all \ (m\). We show that the same approach can be used to count intervals in the ordinary \ (m\) -Tamari lattices as well. We thus recover the earlier result of Bousquet-Mélou, Fusy and Préville-Ratelle, who were using a different catalytic parameter. Mathematics Subject Classifications: 05A15, 06A07, 06A11Keywords: Tamari posets, planar maps, enumeration, algebraic generating functions