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)} \binom{2n}{n}\), 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, 06A11

Keywords: Tamari posets, planar maps, enumeration, algebraic generating functions

In the 1970s, William Tutte developed a clever algebraic approach, based on certain "invariants", to solve a functional equation that arises in the enumeration of properly colored triangulations. The enumeration of plane lattice walks confined to the first quadrant is governed by similar equations, and has led in the past 20 years to a rich collection of attractive results dealing with the nature (algebraic, D-finite or not) of the associated generating function, depending on the set of allowed steps, taken in \(\{-1, 0,1\}^2\).

We first adapt Tutte's approach to prove (or reprove) the algebraicity of all quadrant models known or conjectured to be algebraic. This includes Gessel's famous model, and the first proof ever found for one model with weighted steps. To be applicable, the method requires the existence of two rational functions called invariant and decoupling function respectively. When they exist, algebraicity follows almost automatically.

Then, we move to a complex analytic viewpoint that has already proved very powerful, leading in particular to integral expressions for the generating function in the non-D-finite cases, as well as to proofs of non-D-finiteness. We develop in this context a weaker notion of invariant. Now all quadrant models have invariants, and for those that have in addition a decoupling function, we obtain integral-free expressions for the generating function, and a proof that this series is D-algebraic (that is, satisfies polynomial differential equations).

Keywords: Lattice walks, enumeration, differentially algebraic series, conformal mappings.

Mathematics Subject Classifications: 05A15, 34K06, 39A06, 30C20, 30D05