A LATTICE ON DYCK PATHS CLOSE TO THE TAMARI LATTICEJEAN-LUC BARIL1 , SERGEY KIRGIZOV1 , AND MEHDI NAIMA2Abstract. We introduce a new poset structure on Dyck paths where the covering relation
is a particular case of the relation inducing the Tamari lattice. We prove that the transitive
closure of this relation endows Dyck paths with a lattice structure. We provide a trivariate
generating function counting the number of Dyck paths with respect to the semilength, thenumbers of outgoing and incoming edges in the Hasse diagram. We deduce the numbers ofcoverings, meet and join irreducible elements. We give a generating function for the numberof intervals, and we compare this number with the number of intervals in the Tamari lattice.
Finally, we present a sequent calculus capturing this new Lattice.

In this paper, we introduce a new poset structure on Dyck paths where the covering relation
is a particular case of the covering relation that generates the Tamari lattice [3, 5]. A Dyck
path is a lattice path in N2 starting at the origin, ending on the x-axis and consisting of upsteps U = (1, 1) and down steps D = (1, −1). Let Dn be the set of Dyck paths of semilengthn (i.e., with 2n steps), and D = ∪n≥0 Dn . The cardinality of Dn is the n-th Catalan number
cn = (2n)!/(n!(n + 1)!) (see A000108 1).
A peak in a Dyck path is an occurrence of the subpath U D. A pyramid is a maximal
occurrence of U k Dℓ , k, ℓ ≥ 1, in the sense that this occurrence cannot be extended in aoccurrence of U k+1 Dℓ or in a occurrence of U k Dℓ+1 . We say that a pyramid U k Dℓ is symmetricwhenever k = ℓ, and asymmetric otherwise. The weight of a symmetric pyramid U k Dk is k.
For instance, the Dyck path in the south west of Figure 1b contains two symmetric pyramids
and two asymmetric pyramids.
In 1962 [5], the Tamari lattice Tn of order n is defined by endowing the set Dn with theTtransitive closure ⪯ of the covering relation P −→ P ′ that transforms an occurrence ofDU QD in P into an occurrence U QDD in P ′ , where Q is a Dyck path (possibly empty).
The top part of Figure 1b shows an example of such a covering, and Figure 1a illustrates theHasse diagram of Tn for n = 4 (the red edge must be considered).
Now, we introduce a new partial order on Dn for n ≥ 0. We endow it with the orderedrelation ≤ defined by the transitive closure of the following covering relation P −→ P ′ thattransforms an occurrence of DU k Dk in P into an occurrence U k Dk D in P ′ , where k ≥ 1. For
short, we will often use the notation DU k Dk −→ U k Dk D, k ≥ 1 whenever we need to show
where the transformation is applied.
TNotice that the covering −→ is a particular case of the Tamari covering −→ wheneverTwe take Q = U k−1 Dk−1 in the transformation DU QD −→ U QDD . Let Sn be the poset(Dn , ≤). The bottom part of Figure 1b shows an example of such a covering, and Figure 1a1LIB, Université de Bourgogne, B.P. 47 870, 21078 Dijon Cedex France
Sorbonne Université, CNRS, LIP6, F-75005 Paris, France
E-mail addresses: barjl@u-bourgogne.fr, sergey.kirgizov@u-bourgogne.fr,mehdi.naima@lip6.fr.
1All sequences referenced in this paper can be found in [4]
21

T(i)

−→(ii)−→(b) (i) corresponds to a covering relation for
the Tamari Lattice, while (ii) corresponds tothe covering relation for the new lattice of
this study.

(a) The Hasse diagram of S4 = (D4 , ≤). The
Tamari lattice T4 = (D4 , ⪯) can be viewed byconsidering the dotted edge (in red).

illustrates the Hasse diagram of Sn for n = 4 (without the red edges which belongs to theTamari lattice but not to this new poset).
Theorem 1. The poset (Dn , ≤) is a lattice.
Theorem 2. We haveA(x, y, z) =R(x, y, z) −p4 x (xzy − xy − xz + 1) (xy + xz − x − 1) + R(x, y, z)2,2x (xzy − xy − xz + 1)

where R(x, y, z) = x2 zy − x2 y − x2 z + x2 − xy − xz + x + 1.
Corollary 1. The generating function E(x) where the coefficient of xn is the total numberof possible coverings over all Dyck paths of semilength n (or equivalently the number of edges
in the Hasse diagram) is√−1 + 4x + (1 − 2x) 1 − 4x
E(x) =.
2 (1 − 4x) (1 − x)P
2k+2. The ratio between the numbers of coverings in
The coefficient of xn is given by n−2
k=0kTn and Sn tends towards 3/2.
Let K(x) be the generating function where the coefficient of xn is the number of meet
irreducible elements (Dyck paths with only one outgoing edge). Using the symmetry y ←→ zin A(x, y, z), K(x) also is the generating function where the coefficient of xn is the numberof join irreducible elements (Dyck paths with only one incoming edge).
2x
Corollary 2. We have K(x) = (x−1)(2x−1), and the coefficient of xn is 2n−1 − 1 for n ≥ 1.

Denote by L the set of paths with only one outgoing edge and only one incoming edge.
Let L(x) be the generating function where the coefficient of xn is the number of such paths.
2

4

Corollary 3. We have L(x) = 3x3 + (x+2)x, and the coefficient of xn is 0 whenever n ≤ 2,1−x−x2
is 3 whenever n = 3, and is the Fibonacci number Fn−1 otherwise, where Fn is defined by
Fn = Fn−1 + Fn−2 with F1 = F2 = 1.
Now, we provide the generating function and a close form for the number of intervals in
the lattice Sn . The method is inspired by the work ofP
Bousquet-Mélou and Chapoton [1]. We
introduce the bivariate generating function I(x, y) = n,k≥1 an,k xn y k , where an,k corresponds
to the number of intervals
the upper path ends with k down-steps exactly.
Pin Sn suchn thatkWe also define J(x, y) = n,k≥1 bn,k x y , where bn,k corresponds to the number of intervalsin Sn such that the upper path is prime and ends with k down-steps exactly (recall that aDyck path is prime whenever it only touches the x-axis at its beginning and its end).
Theorem 3. The generating function J(x, y) for the number of intervals (P, Q) where Q isprime, with respect to the semilength and the size of the last run of down steps isxy (−1 + J (x , 1 )) (J (x , 1 ) C (xy) y − y + 1)
J(x, y) =J (x , 1 ) C (xy) xy 2 − C (xy) xy 2 − xy 2 − J (x , 1 ) y + xy + J (x , 1 ) + y − 1√with J(x, 1) = 1− 41−8x , and C(x) is the g.f. for Catalan numbers, i.e. C(x) = 1 + xC(x)2 .
The sequence of coefficients corresponds to the sequence A052701 that counts outerplanarmaps with a given number of edges [2]. The n-th coefficient is given by the close form
2n−1 cn−1 , where cn = (2n)!/(n!(n + 1)!) is the n-th Catalan number A000108.
Theorem 4. The generating function I(x, y) for the number of intervals (P, Q) with respect√1−8x
to the semilength and the size of the last run of down steps is I(x, y) = J(x, y) · 3−2(x+1),and the generating function I(x, 1) for the number of intervals (P, Q) with respect to thesemilength is√
1 − 2 x − 1 − 8xI(x, 1) =.
2(x + 1)
where the sequence of coefficients corresponds to the sequence A064062 that counts simple
outerplanar maps with a given number of vertices [2]. The n-th coefficient is given by then−1 mPclose form n1(n − m) n+m−12 .
mm=0From a more logical point of view we will see how to find a sequent calculus inspired from
Lambek’s product rule and adapted to the Tamari Lattice in [6] that captures the structureof this lattice and present our current results on it.
References[1] M. Bousquet-Mélou, and F. Chapoton. Intervals in the greedy Tamari posets. ArXiv, arXiv:2303.18077.
[2] I. Geffner, and M. Noy. Counting outerplanar maps. The Electronic Journal of Combinatorics, 24(2)(2017), P2.3.
[3] S. Huang, and D. Tamari. Problems of associativity: A simple proof for the lattice property of systems
ordered by a semi-associative law. J. Combinatorial Theory Ser. A, 13 (1972), 7–13.
[4] N. J. A. Sloane. The On-line Encyclopedia of Integer Sequences, available electronically at http://oeis.org.
[5] D. Tamari. The algebra of bracketings and their enumeration. Nieuw Archief voor Wiskunde, 10 (1962),
131–146.
[6] N. Zeilberger. A sequent calculus for a semi-associative law. Logical Methods in Computer Science, 15,2019.
3