Intervals in the greedy Tamari posets

Abstract

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 $\frac{3\cdot 2^{n-1}}{(n+1)(n+2)}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$, 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 the first author, Fusy and Préville-Ratelle, who were using a different catalytic parameter.

24 pages

References in corpus (3)

• About a possible analytic approach for walks in the quarter plane with arbitrary big jumps
• Counting lattice walks by winding angle
• On Differentially Algebraic Generating Series for Walks in the Quarter Plane

Cited by in corpus (8)

• Enumeration of three-quadrant walks via invariants: some diagonally symmetric models
• On the stationary distribution of reflected Brownian motion in a wedge: differential properties
• Quadrant Walks Starting Outside the Quadrant
• Walks avoiding a quadrant and the reflection principle
• Differential algebraic generating series of weighted walks in the quarter plane
• Waiting Times for Ties in Random Competitions
• Enumeration of three quadrant walks with small steps and walks on other M-quadrant cones
• Some Open Problems related to Creative Telescoping