Séminaire Lotharingien de Combinatoire 89 (2025), Article B89b

A LATTICE ON DYCK PATHS CLOSE TO THE TAMARI LATTICE

JEAN-LUC BARIL^{1}, SERGEY KIRGIZOV^{1}, AND MEHDI NAIMA^{2}

In memory of Jean-Marcel Pallo.

Abstract. 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, the numbers of outgoing and incoming edges in the Hasse diagram. We deduce the numbers of coverings, meet and join irreducible elements. As a byproduct, we present a new involution on Dyck paths that transports the bistatistic of the numbers of outgoing and incoming edges to its reverse. Finally, we give a generating function for the number of intervals, and we compare this number with the number of intervals in the Tamari lattice.

1. Introduction and motivation

Many various classes of combinatorial objects are enumerated by the well-known Catalan numbers. For instance, it is the case of Dyck paths, planar trees, rooted binary trees, triangulations, Young tableaux, non-associative products, stack sortable permutations, permutations avoiding a pattern of length three, and so on. A list of over 60 types of such combinatorial classes of independent interest has been compiled by Stanley [28]. Generally, these classes have been studied in the context of the enumeration according to the length and given values of some parameters. Many other authors investigate structural properties of these sets from order theoretical point of view. Indeed, there exist several partial order relations on Catalan sets which endow them with an interesting lattice structure [2, 3, 4, 5, 22, 25, 30]. Of much interest is probably the so-called Tamari lattice [18, 30] which can be obtained equivalently in different ways. The coverings of the Tamari lattice could be different kinds of elementary transformations as reparenthesizations of letter products [17], rotations on binary trees [23, 26], diagonal flips in triangulations [26], and rotations on Dyck paths [6, 8, 12, 23]. The Tamari lattice appears in different domains. Its Hasse diagram is a graph of the polytope called associahedron; it is a Cambrian lattice underlying the combinatorial structure of Coxeter groups; and it has many enumerative properties with tight links with combinatorial objects such as planar maps [9, 10, 11, 13, 20].

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. This is a new attempt to study a lattice structure on a Catalan set, and since it is close to the Tamari lattice, its study becomes natural. We prove that the transitive closure of this relation endows Dyck paths with a lattice structure. It is worth noting that this lattice has been referred to as the pyramid lattice in [3]. We provide a trivariate generating function for the number of Dyck paths with respect to the semilength, and the statistics s and t giving the number of outgoing edges and the number of incoming edges, respectively. As a byproduct, we obtain generating functions and closed forms for the numbers of meet and join irreducible elements, and for the number of coverings. An asymptotic is given for the ratio between the numbers of coverings in the Tamari lattice and those in our lattice. Moreover, we exhibit an involution on the set of Dyck paths that transports the bistatistic (s, t) to (t, s). Finally, we provide the generating function for the number of intervals and we offer some open problems.

1LIB, Université de Bourgogne, B.P. 47 870, 21078 Dijon Cedex France

2Sorbonne Université, CNRS, LIP6, F-75005 Paris, France

E-mail addresses: barjl@u-bourgogne.fr, sergey.kirgizov@u-bourgogne.fr, mehdi.naima@lip6.fr.

2. Notation and definitions

In this section, we provide necessary notation and definitions in the context of Dyck paths, combinatorics and order theory.

Definition 1. A Dyck path is a lattice path in ℕ^{2} starting at the origin, ending on the x-axis and consisting of up-steps U = (1, 1) and down-steps D = (1, −1).

Let D_{n} be the set of Dyck paths of semilength n (i.e., with 2n steps), and D = ⋃_{n≥0} D_{n}. The cardinality of D_{n} is the n-th Catalan number c_{n} = (2n)!/(n!(n+1)!) (see A000108 in [27]). For instance, the set D_{3} consists of the five paths UDUDUD, UUDDUD, UDUUDD, UUDUDD and UUUDDD.

In this article, we will use the first return decomposition of a Dyck path, P = URDS, where R, S ∈ D, and the last return decomposition of a Dyck path, P = RUSD, where R, S ∈ D. Such a decomposition is unique and will be used to obtain a recursive description of the set D. A Dyck path having a first return decomposition with S empty will be called prime, which means that the path touches the x-axis only at the origin and at the end.

Definition 2. A peak in a Dyck path is an occurrence of the subpath UD. A pyramid is a maximal occurrence of U^{k}D^{ℓ}, k, ℓ ≥ 1, in the sense that this occurrence cannot be extended in a occurrence of U^{k+1}D^{ℓ} or in a occurrence of U^{k}D^{ℓ+1}.

We say that a pyramid U^{k}D^{ℓ} is symmetric whenever k = ℓ, and asymmetric otherwise. The weight of a symmetric pyramid U^{k}D^{k} is k. For instance, the Dyck path in the southwest of Figure 1 contains two symmetric pyramids and two asymmetric pyramids.

A statistic on the set D of Dyck paths is a function f from D to ℕ, and a multistatistic is a tuple of statistics (f_{1}, f_{2}, …, f_{t}), t ≥ 2. Given two statistics (or multistatistics) f and g, we say that they have the same distribution (or equivalently, are equidistributed) if, for any k ≥ 0,

card{P ∈ D, f(P) = k} = card{P ∈ D, g(P) = k}.

Below, we define two important statistics for our study.

Definition 3. Let s be the statistic on D where s(P) is the number of occurrences in P of DU^{k}D^{k}, k ≥ 1. Let t be the statistic on D where t(P) is the number of occurrences in P of U^{k}D^{k}D, k ≥ 1.

For instance, for the path P in the southwest of Figure 1, we have s(P) = 3 and t(P) = 4.

We end this section by defining the main concepts of order theory that we will use in this paper. We can find all these definitions in [17] for instance.

A poset L is a set endowed with a partial order relation. Given two elements P, Q ∈ L, a meet (or greatest lower bound) of P and Q, denoted P ∧ Q, is an element R such that R ≤ P, R ≤ Q, and for any S such that S ≤ P, S ≤ Q then we have S ≤ R. Dually, a join (or least upper bound) of P and Q, denoted P ∨ Q, is an element R such that P ≤ R, Q ≤ R, and for any S such that P ≤ S, Q ≤ S then we have R ≤ S. Notice that join and meet elements do not necessarily exist in a poset. A lattice is a poset where any pair of elements admits a meet and a join.

Definition 4. An element P ∈ L is join-irreducible (respectively, meet-irreducible) if P = R ∨ S (respectively, P = R ∧ S) implies P = R or P = S.

Definition 5. An interval I in a poset L is a subset of L such that for any P, Q ∈ I, and any R ∈ L, if P ≤ R and R ≤ Q, then R is also in I.

In 1962 [30], the Tamari lattice T_{n} of order n is defined by endowing the set D_{n} with the transitive closure ⪯ of the covering relation

P ⟶^{T} P′

that transforms an occurrence of DUQD in P into an occurrence UQDD in P′, where Q is a Dyck path (possibly empty). The top part of Figure 1 shows an example of such a covering, and Figure 5 illustrates the Hasse diagram of T_{n} for n = 4 (the red edge must be considered). The number of meet (respectively, join) irreducible elements is n(n − 1)/2, and the number of coverings is (n − 1)c_{n}/2 [16] where c_{n} is the n-th Catalan number. In 2006, Chapoton [11] proved that the number of intervals in T_{n} is

\frac{2}{n(n + 1)}\binom{4n + 1}{n − 1}.

Later, Bernardi and Bonichon [7] exhibited a bijection between intervals in T_{n} and minimal realizers.

Now, we introduce a new partial order on D_{n} for n ≥ 0. We endow it with the order relation ≤ defined by the transitive closure of the covering relation

P ⟶ P′

that transforms an occurrence of DU^{k}D^{k} in P into an occurrence U^{k}D^{k}D in P′, where k ≥ 1. For short, we will often use the notation

DU^{k}D^{k} ⟶ U^{k}D^{k}D, k ≥ 1

whenever we need to show where the transformation is applied.

Notice that the covering ⟶ is a particular case of the Tamari covering ⟶^{T} whenever we take Q = U^{k−1}D^{k−1} in the transformation DUQD ⟶^{T} UQDD . Let S_{n} be the poset (D_{n}, ≤). The bottom part of Figure 1 shows an example of such a covering, and Figure 2 illustrates the Hasse diagram of S_{n} for n = 4 (without the red edges which belongs to the

(i)  ⟶^{T}

(ii) ⟶

Figure 1. (i) corresponds to a covering relation for the Tamari Lattice, while (ii) corresponds to the covering relation for the new lattice of this study.

Tamari lattice but not to this new poset). See also Figure 7 for an illustration of the Hasse diagram of the Tamari lattice and this poset for the case n = 6.

In our study, the following facts will sometimes be used explicitly or implicitly:

Fact 1. If P ⟶ P′, then the path P′ is above the path P, that is, for any points (x, y) ∈ P′ and (x, z) ∈ P we have y ≥ z.

Fact 2. If P ⟶ P′ then s(P) − 1 ≤ s(P′) ≤ s(P) and t(P) ≤ t(P′) + 1.

Figure 2. The Hasse diagram of S_{4} = (D_{4}, ≤). The Tamari lattice T_{4} = (D_{4}, ⪯) can be viewed by considering the dotted edge (in red).

3. Lattice structure of S_{n} = (D_{n}, ≤).

In this section, we prove that the poset S_{n} = (D_{n}, ≤) is a lattice and provide some related results.

Lemma 1. For n ≥ 2, any Dyck path P ∈ D_{n}, P ≠ U^{n}D^{n}, contains at least one occurrence of DU^{k}D^{k} for some k ≥ 1.

Proof. For n ≥ 2, in any path from D_{n} not equal to U^{n}D^{n}, there exists an occurrence of DU, and the rightmost occurrence of DU always starts an occurrence of DU U^{ℓ}D^{ℓ}D for some ℓ ≥ 0. □

Lemma 2. For n ≥ 2, any Dyck path P ∈ D_{n}, P ≠ (UD)^{n}, contains at least one occurrence of U^{k}D^{k}D for some k ≥ 1, and then P contains at least one occurrence of UDD.

Proof. By contradiction, let us assume that P does not contain an occurrence UDD. This means that any peak UD is either at the end of P, or it precedes an up-step U, which implies that a down-step cannot be contiguous to another down-step. Thus, P = (UD)^{n} which contradicts the hypothesis P ≠ (UD)^{n}. □

Proposition 1. For any Dyck path P ∈ D_{n}, we have P ≤ U^{n}D^{n} and (UD)^{n} ≤ P, which means that the poset (D_{n}, ≤) admits a maximum element and a minimum element.

Proof. It suffices to apply Lemma 1 and Lemma 2. Indeed, let P be a Dyck path in D_{n}, P ≠ U^{n}D^{n}. Using Lemma 1, P contains at least one occurrence of DU^{k}D^{k}, k ≥ 1. Let P_{1} be the Dyck path obtained from P after applying the covering DU^{k}D^{k} → U^{k}D^{k}D on this occurrence. Due to Fact 1, any point (x, y) in P is below the point (x, z) in P_{1} (i.e., y ≤ z). Iterating the process from P_{1}, we construct a sequence of coverings P → P_{1} → … → P_{r}, r ≥ 1, of Dyck paths that necessarily converges towards a Dyck path without occurrence of DU^{k}D^{k} for some k ≥ 1, i.e., towards U^{n}D^{n}, which implies P ≤ U^{n}D^{n}.

By applying a similar argument, we can easily prove the second inequality. □

Proposition 2. We consider P, Q ∈ D_{n} that satisfy P ≤ Q, P ≠ Q, and such that P = RDS and Q = RUS′ (R is the maximal common prefix of P and Q). Let W be the Dyck path obtained from P by applying the covering P ⟶ W on the leftmost occurrence of DU^{k}D^{k}, k ≥ 1, in DS, then we necessarily have W ≤ Q.

Proof. Let P_{0} = P → P_{1} → … → P_{k} = Q be a sequence of coverings from P to Q. Let us suppose that the first covering is not applied on the leftmost occurrence of DU^{k}D^{k}, k ≥ 1, in DS. We call D_{0} the first step of this occurrence. Let P_{i} → P_{i+1} be the covering involving D_{0}, and we write P = R′D_{0}U^{k}D^{k}S′ where R is a prefix of R′ and S′ is a suffix of S. Necessarily, the down-step D_{0} is followed by U^{ℓ}D^{ℓ} in P_{i} where ℓ ≥ k. Then, all coverings between P and P_{i} occur on the right of D_{0}U^{k}. We call them α_{1}, …, α_{a}, a ≥ 1. So, there is another sequence of coverings from P to P_{i+1} by applying the following: we first apply the covering β involving D_{0}U^{k}D^{k} in P, then we obtain the path R′U^{k}D^{k}DS′; we apply the coverings α′_{1}, …, α′_{a} (in the same order) where α′_{i} is the covering involving the same occurrence of DU^{b}D^{b} moved by α_{i}, then we obtain R′U^{k}DU^{ℓ−k}D^{ℓ}S′′ for some S′′; finally, we apply an additional covering in order to obtain P_{i+1} = R′U^{ℓ}D^{ℓ}DS′′ (see below for an illustration of this process).

P = R′D_{0}U^{k}D^{k}S′ P_{i} = R′D_{0}U^{ℓ}D^{ℓ}S′′ P_{i+1} = R′U^{ℓ}D^{ℓ}DS′′ R′U^{k}D^{k}DS′ R′U^{k}DU^{ℓ−k}D^{ℓ}S′′ α_{1} α_{a} β α′_{1} α′_{a}

Therefore, we can reach Q from P by first applying the covering involving D_{0}U^{k}D^{k}, which completes the proof. □

As a byproduct of Proposition 2 and by a straightforward induction, we have the following corollary.

Corollary 1. The longest chain between (UD)^{n} and U^{n}D^{n} is of length n(n − 1)/2.

Proof. Due to Proposition 2, the longest chain between (UD)^{n} and U^{n}D^{n} is unique and it can be constructed from (UD)^{n} by applying at each step the leftmost covering. So, the length of this chain is given by 1 + 2 + … + (n − 1), which gives the expected result. □

Theorem 1. The poset (D_{n}, ≤) is a lattice.

Proof. For any P, Q ∈ D, we need to prove that P and Q admit a join and a meet element. Let us start to give the proof of the existence of a join element. We proceed by induction on the semilength of the Dyck paths. For n ≤ 3, S_{n} = (D_{n}, ≤) is isomorphic to the Tamari lattice.

Now, let us assume that S_{n} = (D_{n}, ≤) is a lattice for n ≤ N, and let us prove the result for N + 1. Let P and Q be two paths in D_{N+1}. We distinguish two cases according to the form of the first return decompositions of P and Q.

(1) If P = URDS and Q = UR′DS′ where R and R′ have the same length. Then we apply the induction hypothesis for R and R′ (respectively S and S′), which means that R ∨ R′ (respectively, S ∨ S′) exists. Therefore, the path U(R ∨ R′)D(S ∨ S′) is necessarily the least upper bound of P and Q, which proves that P ∨ Q exists.

(2) Now, let us suppose that P = URDS and Q = UR′DS′ where the length r′ of R′ is strictly less than the length r of R. Let M be an upper bound of P and Q (there is at least one due to Proposition 1). Since r′ < r and due to Fact 1, M has necessarily a decomposition M = UM_{1}DM_{2} where the length of M_{1} is at least r. Therefore, in any sequence of coverings Q → … → M from Q to M, there is necessarily a covering that involves and elevates the down-step just after R′. Due to the definition of the covering ⟶, we can apply such a transformation only when this down-step is followed by an occurrence U^{k}D^{k} for some k ≥ 1.

Assuming S′ = US_{1}DS_{2} and using Proposition 2, we deduce that the inequality Q = UR′DUS_{1}DS_{2} ≤ M is equivalent to UR′DU^{k}D^{k}S_{2} ≤ M where k ≥ 1 is the semilength of US_{1}D. Moreover, this condition is equivalent to Q_{1} := UR′U^{k}D^{k}DS_{2} ≤ M (see Figure 3). It is worth noting that Q_{1} does not depend on the upper bound M. Iterating this process with P and Q_{1}, we can construct two Dyck paths P′ and Q′ such that the condition P ≤ M and Q ≤ M is equivalent to P′ ≤ M and Q′ ≤ M where P′ and Q′ (that do not depend on M) are two Dyck paths lying in the first case of the proof. Using the induction hypothesis, we conclude that P′ ∨ Q′ = P ∨ Q exists.

Considering the two cases, the induction is completed.

The existence of greatest lower bound then follows automatically since the poset is finite with a least element and a greatest element. □

Q = \begin{matrix}R′ \\ S_{1} \\ S_{2} \end{matrix}  ≤ \begin{matrix}R′ \\ S_{2} \end{matrix}  ⟶ \begin{matrix}R′ \\ S_{2} \end{matrix}

Figure 3. An illustration of the construction Q = UR′DUS_{1}DS_{2} ≤ UR′DU^{k}D^{k}S_{2} → UR′U^{k}D^{k}DS_{2} of the case (ii) in the proof of Theorem 1.

4. Coverings, join and meet irreducible elements

For a given Dyck path P, the number of incoming edges (in the Hasse diagram) corresponds to the number t(P) of occurrences U^{a}D^{a}D, a ≥ 1, in P, and the number of outgoing edges (coverings) corresponds to the number s(P) of occurrences DU^{a}D^{a}, a ≥ 1, in P. Let A(x, y, z) be the trivariate generating function where the coefficient of x^{n}y^{k}z^{ℓ} is the number of Dyck paths of semilength n having k possible coverings (or equivalently k outgoing edges), and ℓ incoming edges.

Theorem 2. We have

A(x, y, z) = \frac{R(x, y, z) − \sqrt{4 x (xzy − xy − xz + 1) (xy + xz − x − 1) + R(x, y, z)^{2}}}{2x (xzy − xy − xz + 1)} ,

where R(x, y, z) = x^{2}zy − x^{2}y − x^{2}z + x^{2} − xy − xz + x + 1.

Proof. For short, we set A := A(x, y, z). We consider the last return decomposition of a nonempty Dyck path P, that is P = RUSD where R and S are two Dyck paths. We distinguish six cases.

(1) If R and S are empty, then P = UD and the generating function for this path is x.

(2) If R is not empty and S is empty, the generating function for these paths is (A−1)xy.

(3) If R is empty and S = U^{a}D^{a} with a ≥ 1, then the generating function for these paths is \frac{x^{2}z}{1−xz}.

(4) If R is not empty and S = U^{a}D^{a} with a ≥ 1, then the generating function for these paths is \frac{x^{2}z}{1−xz}(A − 1)y.

(5) If S = S′U^{a}D^{a} with a ≥ 1 and S′ not empty (R is possibly empty), then the generating function for these paths is \frac{x^{2}z}{1−xz}(A − 1)yA.

(6) If S does not end with U^{a}D^{a}, a ≥ 1, then the generating function for these paths is AxB where B is the generating function for nonempty Dyck paths that do not end with a pyramid U^{a}D^{a}, a ≥ 1. Using the complement, we have B = A − 1 − x − \frac{x^{2}z}{1−xz} − x(A − 1)y − \frac{x^{2}z}{1−xz}(A − 1)y where 1 is for the empty path; x is for UD; \frac{x^{2}z}{1−xz} is for the paths of the form U^{a}D^{a}, a ≥ 2; x(A − 1)y is for the paths RUD with R not empty; and \frac{x^{2}z}{1−xz}(A − 1)y is for the paths RU^{a}D^{a}, a ≥ 2.

Summarizing the three cases, we obtain the functional equation

A = 1 + x + (A − 1)xy + \frac{x^{2}z}{1 − xz} + \frac{x^{2}z}{1 − xz} (A − 1)y + \frac{x^{2}z}{1 − xz} (A − 1)yA

+ Ax (A − 1 − x − \frac{x^{2}z}{1 − xz} − x(A − 1)y − \frac{x^{2}z}{1 − xz} (A − 1)y) ,

and a simple calculation provides the result.

□

The first terms of the series expansion are

1 + x + (z + y) x^{2} + (y^{2} + 3 yz + z^{2}) x^{3} + (y^{3} + 5 y^{2}z + 5 yz^{2} + z^{3} + 2 yz) x^{4}

+ (y^{4} + 7 y^{3}z + 13 y^{2}z^{2} + 7 yz^{3} + z^{4} + 5 y^{2}z + 5 yz^{2} + 3 yz) x^{5} + O (x^{6}) .

Remark 1. Observe that R(x, y, z) = R(x, z, y) and A(x, y, z) = A(x, z, y), which means that (t, s) and (s, t) are equidistributed on D_{n}, n ≥ 1. In the following, we will show the existence of an involution on D_{n} that transports the bistatistic (t, s) to (s, t) (see Definition 3).

Corollary 2. The generating function E(x) where the coefficient of x^{n} is the total number of possible coverings over all Dyck paths of semilength n (or equivalently the number of edges in the Hasse diagram) is

E(x) = \frac{−1 + 4x + (1 − 2x) \sqrt{1 − 4x}}{2 (1 − 4x) (1 − x)}.

The coefficient of x^{n} is given by

∑_{k=0}^{n−2} \binom{2k + 2}{k}.

The ratio between the numbers of coverings in T_{n} and S_{n} tends towards 3/2.

Proof. We obtain E(x) by calculating ∂_{y}(A(x, y, 1))|_{y=1}. Now we set F (x) = \frac{E(x)(1−x)}{x}. Noticing that F (x) = x · ∂_{x}(C(x)) where C(x) is the generating function for the Catalan numbers satisfying C(x) = 1 + xC(x)^{2}. So, we deduce directly that

f_{n} := [x^{n}]F (x) = \frac{n}{n + 1}\binom{2n}{n}.

Then, we have

[x^{n}]E(x) = ∑_{k=1}^{n−1} f_{k} = ∑_{k=1}^{n−1} \frac{k}{k + 1}\binom{2k}{k} = ∑_{k=0}^{n−2} \binom{2k + 2}{k}.

Considering the asymptotics of [x^{n}]E(x) and (n − 1)c_{n}/2 (using classical methods, see [14] for instance), the limit of the ratio between the number of coverings in T_{n} and S_{n} is 3/2. □

The first terms of the series expansion of E(x) are

x^{2} + 5 x^{3} + 20 x^{4} + 76 x^{5} + 286 x^{6} + 1078 x^{7} + 4081 x^{8} + 15521 x^{9} + O (x^{10}) ,

and the sequence of coefficients corresponds to A057552 in [27].

Let K(x) be the generating function where the coefficient of x^{n} is the number of meet irreducible elements (Dyck paths with only one outgoing edge). Using the symmetry y ⟷ z in A(x, y, z), K(x) is also the generating function where the coefficient of x^{n} is the number of join irreducible elements (Dyck paths with only one incoming edge).

Corollary 3. We have

K(x) = \frac{x^{2}}{(x − 1)(2x − 1)},

and the coefficient of x^{n} is 2^{n−1} − 1 for n ≥ 1.

Proof. The generating function corresponds to the coefficient of y in the series expansion of A(x, y, 1), i.e., [y]A(x, y, 1) = ∂_{y}(A(x, y, 1))|_{y=0}. □

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 x^{n} is the number of such paths.

Corollary 4. We have

L(x) = 3x^{3} + \frac{(x + 2) x^{4}}{1 − x − x^{2}} ,

and the coefficient of x^{n} is 0 whenever n ≤ 2, is 3 whenever n = 3, and is the Fibonacci number F_{n−1} otherwise, where F_{n} is defined by F_{n} = F_{n−1} + F_{n−2} with F_{1} = F_{2} = 1.

Proof. For n ≤ 2, there is no such paths. For n = 3, there are three such paths, UUDDUD, UDUUDD and UUDUDD. For n ≥ 4, the number of these paths is exactly the coefficient of y^{2}x^{n} in A(x, y, y), i.e., [y^{2}x^{n}]A(x, y, y) = \frac{(x+2)x^{4}}{1−x−x^{2}} . □

For n ≥ 4, we remark that any path from L should contain exactly one occurrence of DU^{k}D^{k}, with k ≥ 1, to guarantee the existence of a unique outgoing edge, and exactly one occurrence of U^{k}D^{k}D for the incoming edge. Thus, it must avoid overlapping UDU anywhere except for the tail, which necessarily has a shape U UD UD D^{ℓ} for some ℓ > 0. Figure 4 presents a bijection between words of length n ≥ 4 from L and Knuth–Fibonacci words of length n − 3, i.e., binary words avoiding consecutive 1s, discussed for example in Knuth’s book [19, p. 286]. To construct the corresponding binary word, we read the Dyck path from left to right, write 1 for any up-step which starts a UDU pattern, and 0 otherwise. The resulting word will always end with 011, so we forget about these last 3 symbols.

00 ·^{·^{·}} 10 ·^{·^{·}} 010·^{·^{·}} 011

Figure 4. Bijection between L and binary words avoiding consecutive 1s except the tail 011.

In order to exhibit an involution on D_{n} that transports the bistatistic (s, t) to (t, s), we need to define the following subsets of D_{n}. Let D_{n}^{1} (respectively, D_{n}^{2}), be the set of Dyck paths P ∈ D_{n} such that P ends with DUD^{k}, k ≥ 2 (respectively, ends with DU^{r}D^{k}, r ≥ 2, k ≥ 3 and r ≠ k). Less formally, D_{n}^{1} is the set of paths where the last run of down-steps is of length at least two, and the last run of up-steps is of length 1; D_{n}^{2} is the set of paths where the last run of down-steps is of length at least two, the last run of up-steps is of length at least 2, and they do not end with U^{ℓ}D^{ℓ} for any ℓ ≥ 1. We set D^{i} = ⋃_{n≥0} D_{n}^{i} for i ∈ {1, 2}. For instance, we have UUDUDD ∈ D_{3}^{1} and UUUDDUUDDD ∈ D_{5}^{2}.

Below, we define recursively an involution ϕ from D into itself as follows:

\{ \begin{matrix}ϕ(ϵ) & = ϵ, & & (i) \\ ϕ(U^{k}D^{k}) & = (UD)^{k}, & k ≥ 1, & (ii) \\ ϕ(RU^{k}D^{k}) & = ϕ(R)^{♯}(UD)^{k−1}, & k ≥ 2, & (iii) \\ ϕ(R_{0}UR_{1} … UR_{k}UD^{k+1}) & = ϕ(R_{0})Uϕ(R_{1}) … Uϕ(R_{k})UD^{k+1}, & k ≥ 1, & (iv) \\ ϕ(R_{0}UR_{1} … UR_{k}U^{r+1}D^{k+r+1}) & = ϕ(R_{0})Uϕ(R_{1}) … Uϕ(R_{k})UD^{k+1}(UD)^{r}, & k, r ≥ 1, & (v) \end{matrix}

where R and R_{k} are nonempty Dyck paths, and R_{i}, 0 ≤ i ≤ k − 1, are Dyck paths (possibly empty), and ϕ(R)^{♯} is obtained from ϕ(R) by inserting an occurrence UD on the last peak of ϕ(R), i.e., if ϕ(R) = R′UD^{k}, then ϕ(R)^{♯} = R′UUDD^{k} (see below for the image by ϕ of paths of the form RUD).

It is worth noticing that the definition of ϕ is given on a subset P_{1} of D, consisting of Dyck paths of the forms ϵ, U^{k}D^{k} with k ≥ 1, RU^{k}D^{k} with k ≥ 2 and R nonempty, and Dyck paths in D^{1} ∪ D^{2}. This means that the above definition of ϕ does not explicitly provide the image of paths of the form RUD, i.e., paths in D\P_{1}. However, this definition implicitly gives the image of paths in D\P_{1} by considering the reverse of cases (iii) and (v) (this is possible because we have ϕ(D^{1}) = D^{1}, and ϕ(P_{1}\D^{1}) = D\D^{1}). Then we obtain an involution ϕ on the entire set D. For instance, we have ϕ(UUUDDD) = UDUDUD, ϕ(UUDDUD) = UDUUDD, ϕ(UDUUDD) = UUDDUD, ϕ(UUDUDD) = UUDUDD and ϕ(UDUDUD) = UUUDDD.

Let P be a Dyck path. We recall (see Definition 3) that s(P) (respectively t(p)) gives the number of occurrences DU^{k}D^{k} (respectively U^{k}D^{k}D), k ≥ 1, in P.

(ii) k ≥ 1  ⟷^{ϕ} k ≥ 1

(iii) \begin{matrix}R \\ k ≥ 2 \end{matrix}  ⟷^{ϕ} \begin{matrix}ϕ(R)^{♯} \\ k − 1 ≥ 1 \end{matrix}

(iv) \begin{matrix}R_{0} \\ R_{1} \\ R_{k} \end{matrix}  ⟷^{ϕ} \begin{matrix}ϕ(R_{0}) \\ ϕ(R_{1}) \\ ϕ(R_{k}) \end{matrix}

(v) \begin{matrix}R_{0} \\ R_{1} \\ R_{k} \\ r ≥ 1 \end{matrix}  ⟷^{ϕ} \begin{matrix}ϕ(R_{0}) \\ ϕ(R_{1}) \\ r ≥ 1 \\ ϕ(R_{k}) \end{matrix}

Figure 5. An illustration of the involution ϕ for the cases (ii)-(v).

Theorem 3. The map ϕ is an involution on D that preserves the semilength, and that transports the bistatistic (s, t) to (t, s). Moreover, ϕ preserves the number of asymmetric pyramids, and preserves the sum of the weights of symmetric pyramids.

Proof. We proceed by induction on the semilength n of the paths. We assume the result for paths of semilength at most n, and we prove the result for the semilength n + 1. We distinguish four cases according to the definition of ϕ (we omit the case (i) since n + 1 ≥ 1).

(ii) If P = U^{n+1}D^{n+1} then we have ϕ(P) = (UD)^{n+1}, s(P) = 0 = t(ϕ(P)), and t(P) =

n = s(ϕ(P)). (iii) If P = RU^{k}D^{k}, with R nonempty and k ≥ 2, then we have ϕ(P) = ϕ(R)^{♯}(UD)^{k−1},

s(P) = t(R) + 1, and using the induction hypothesis, this is equal to t(ϕ(R)) + 1 = t(ϕ(P)^{♯}). Moreover, we have t(P) = t(R)+k −1 and using the induction hypothesis, this is equal to s(ϕ(R)) + k − 1 = s(ϕ(P)^{♯}) + k − 1 = s(ϕ(P)^{♯}(UD)^{k−1}) = s(ϕ(P)).

(iv) If P = R_{0}UR_{1} … UR_{k}UD^{k+1}, then we have ϕ(P) = ϕ(R_{0})Uϕ(R_{1}) … Uϕ(R_{k})UD^{k+1}, and s(P) = ∑_{i=0}^{k} s(R_{i}) + 1, and using the induction hypothesis, this is equal to ∑_{i=0}^{k} t(ϕ(R_{i})) + 1 = t(ϕ(R_{0})Uϕ(R_{1}) … Uϕ(R_{k})UD^{k+1}) = t(ϕ(P)). A similar argument allows us to prove t(P) = s(ϕ(P)).

(v) If P = R_{0}UR_{1} … UR_{k}UD^{k+1}, then we have

ϕ(P) = ϕ(R_{0})Uϕ(R_{1}) … Uϕ(R_{k})UD^{k+1}(UD)^{r},

and s(P) = ∑_{i=0}^{k} s(R_{i}) + 1, and using the induction hypothesis, this is equal to ∑_{i=0}^{k} t(ϕ(R_{i}))+1 = t(ϕ(R_{0})Uϕ(R_{1}) … Uϕ(R_{k})UD^{k+1}(UD)^{r}) = t(ϕ(P)). The equality t(P) = s(ϕ(P)) is obtained in the same way.

Considering all these cases, we obtain the result by induction. □

Notice that Theorem 3 allows us to retrieve the symmetry obtained by Theorem 2, but unfortunately, the involution ϕ does not induce a symmetry on the lattice (D_{n}, ≤).

5. Enumeration of intervals

In this section, we provide the generating function and a closed form for the number of intervals in the lattice S_{n}. The method is inspired by the work of Bousquet-Mélou and Chapoton [10]. We will use a catalytic variable that considers the size of last run of downsteps. We introduce the bivariate generating function

I(x, y) = ∑_{n,k≥1} a_{n,k}x^{n}y^{k},

where a_{n,k} is the number of intervals in S_{n} such that the upper path ends with k down-steps exactly. We also define

J(x, y) = ∑_{n,k≥1} b_{n,k}x^{n}y^{k},

where b_{n,k} is the number of intervals in S_{n} such that the upper path is prime and ends with k down-steps exactly (recall that a Dyck path is prime whenever it only touches the x-axis at its beginning and its end).

Lemma 3. The following functional equation holds:

I(x, y) = J(x, y) + I(x, 1) · J(x, y).

Proof. Let (P, Q) be an interval in S_{n} where P is the lower bound and Q the upper bound. We distinguish two cases.

(1) If Q is prime, then the contribution for these intervals is simply J(x, y).

(2) Otherwise, Q is not prime and it has a last return decomposition Q = RUSD with R, S ∈ D and R not empty. This implies that P is of the form P = P_{1}P_{2} where P_{1}, P_{2} ∈ D, and P_{2} and USD have the same length. This induces a bijection from intervals in this case with pairs of intervals I_{1} := (P_{1}, R) and I_{2} := (P_{2}, USD), where I_{1} is any interval of of smaller length, and I_{2} is any interval (of smaller length) lying in the case (1). Therefore, the contribution for the intervals in this case is I(x, 1)·J(x, y).

Considering the two cases, we obtain the expected result. □

Lemma 4. The following functional equation holds:

J(x, y) = xy + xyI(x, y) + \frac{J(x, y) − J(x, 1)}{y − 1} · C(xy)xy^{2},

where C(x) is the generating function for Catalan numbers, i.e., C(x) = 1 + xC(x)^{2}.

Proof. Let (P, Q) be an interval in S_{n} where P is the lower bound and Q the upper bound. We distinguish three cases.

(1) If P = UD and Q = UD, then the contribution is xy.

(2) If P is prime, then we have P = UP′D and we necessarily have Q = UQ′D (i.e., Q is prime) where P′ and Q′ are nonempty Dyck paths. Thus, the contribution for these intervals is xyI(x, y).

(3) Otherwise, P is not prime which means that it has a last return decomposition P = RUSD with R, S ∈ D and R not empty (see the bottom of Figure 6). As Q is prime, in any path of coverings P → P_{1} → ⋯ → Q from P to Q, there is necessarily a covering that involves and elevates the up-step just after R. We can apply such a transformation only when the suffix P delimited by this up-step is of the form U^{k}D^{k} for some k ≥ 1. This condition implies that Q is necessarily of the form Q = Q′U^{k}D^{k+ℓ} where Q′ is a prefix of Dyck path and ℓ ≥ 1 (see the top of Figure 6 for an illustration of the form of Q = Q′U^{k}D^{k+ℓ}). Let h ≥ 1 be the height of the right point of the last up-step of Q′. Then, we necessarily have h ≥ ℓ ≥ 1.

U^{k} D^{k+ℓ} h _{Length of USD=2k} _{Prefix Q′} ↕ Q = Q′U^{k}D^{k+ℓ} =

_{USD} _{R} P = RUSD =

Figure 6. The form of the upper bound Q = Q′U^{k}D^{k+ℓ}, ℓ ≥ 1, and the form of the lower bound P = RUSD.

On the other hand, any Q of this form (i.e., Q = Q′U^{k}D^{k+ℓ} with h ≥ ℓ ≥ 1) is candidate for an upper bound of an interval (P, Q) = (RUSD, Q′U^{k}D^{k+ℓ}) if and only if (R, Q′D^{ℓ}) and (USD, U^{k}D^{k}) are two intervals, which is equivalent to the condition (R, Q′D^{ℓ}) is an interval (indeed, (USD, U^{k}D^{k}) is always an interval).

So, for each interval of the form (R, Q′D^{ℓ}), h ≥ ℓ ≥ 1, we can construct h intervals of the form (RUSD, Q′′U^{k}D^{k+ℓ}, 1 ≤ ℓ ≤ h, where Q′′ is the greatest prefix of Q′ ending by an up-step, i.e., the intervals

(RUSD, Q′′D^{h−1}U^{k}D^{k+1}),
(RUSD, Q′′D^{h−2}U^{k}D^{k+2}),
. . . . . .
(RUSD, Q′′DU^{k}D^{k+h−1}),
(RUSD, Q′′U^{k}D^{k+h}).

Considering this study, the contribution for the intervals in this case is given by

xyC(xy) · ∑_{h≥1} ∑_{n≥1} b_{n,h}x^{n}(y + y^{2} + … + y^{h}) = xy^{2}C(xy) · ∑_{h≥1} ∑_{n≥1} b_{n,h}x^{n} \frac{y^{h} − 1}{y − 1},

that can be expressed as

xy^{2}C(xy) · (∑_{h≥1} ∑_{n≥1} b_{n,h}x^{n} \frac{y^{h}}{y − 1} − ∑_{h≥1} ∑_{n≥1} b_{n,h}x^{n} \frac{1}{y − 1}) = C(xy)xy^{2} · \frac{J(x, y) − J(x, 1)}{y − 1}.

Considering the three cases, we obtain the expected result. □

From Lemma 3 and Lemma 4 and after a straightforward substitution, we obtain a system of equations.

Theorem 4. The following system of functional equations holds:

\{ \begin{matrix}I(x, y) & = \frac{J(x,y)}{1−J(x,1)}, \\ J(x, y) & = xy + xy \frac{J(x,y)}{1−J(x,1)} + \frac{J(x,y)−J(x,1)}{y−1} · C(xy)xy^{2}. \end{matrix}

In order to compute J(x, 1), we use the kernel method [1, 24] on

J(x, y) · (1 − \frac{xy}{1 − J(x, 1)} − \frac{C(xy)xy^{2}}{y − 1} ) = xy − \frac{J(x, 1)}{y − 1} · C(xy)xy^{2}.

This method consists in cancelling the factor of J(x, y) by finding y as an algebraic function y_{0} of J(x, 1) and x. So, if we substitute y_{0} for y on the right-hand side of the equation, then it necessarily equals zero (in order to counterbalance the cancellation on the left-hand side). So, we deduce the following system of equations that allows us to determine J(x, 1), and then J(x, y):

\{ \begin{matrix}1 − \frac{xy_{0}}{1−J(x,1)} − \frac{C(xy_{0})xy_{0}^{2}}{y_{0}−1} & = 0, \\ xy_{0} − \frac{J(x,1)}{y_{0}−1} · C(xy_{0})xy_{0}^{2} & = 0. \end{matrix}

So, we deduce y_{0} = \frac{1+4x−\sqrt{1−8x}}{8x}, and the following theorem.

Theorem 5. The generating function J(x, y) for the number of intervals (P, Q) where Q is prime, with respect to the semilength and the size of the last run of down-steps is

J(x, y) = \frac{xy (−1 + J (x, 1 )) (J (x, 1 ) C (xy) y − y + 1)}{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) = \frac{1 − \sqrt{1 − 8x}}{4},

and C(x) is the generating function for Catalan numbers, i.e., C(x) = 1 + xC(x)^{2}.

The series expansion of J(x, 1) is

x + 2 x^{2} + 8 x^{3} + 40 x^{4} + 224 x^{5} + 1344 x^{6} + 8448 x^{7} + 54912 x^{8} + 366080 x^{9} + O (x^{10}) ,

where the sequence of coefficients corresponds to the sequence A052701 in [27] that counts outerplanar maps with a given number of edges [15]. The n-th coefficient is given by the closed form

2^{n−1}c_{n−1},

where c_{n} = (2n)!/(n!(n + 1)!) is the n-th Catalan number A000108 in [27].

The series expansion of J(x, y) is

yx + 2 y^{2}x^{2} + (5 y + 3) y^{2}x^{3} + (14 y^{2} + 15 y + 11) y^{2}x^{4} + (42 y^{3} + 61 y^{2} + 68 y + 53) y^{2}x^{5}

+ (132 y^{4} + 233 y^{3} + 325 y^{2} + 363 y + 291) y^{2}x^{6} + O (x^{7}) ,

Theorem 6. The generating function I(x, y) for the number of intervals (P, Q) with respect to the semilength and the size of the last run of down-steps is

I(x, y) = J(x, y) · \frac{3 − \sqrt{1 − 8x}}{2(x + 1)},

and the generating function I(x, 1) for the number of intervals (P, Q) with respect to the semilength is

I(x, 1) = \frac{1 − 2 x − \sqrt{1 − 8x}}{2(x + 1)}.

The series expansion of I(x, 1) is

x + 3 x^{2} + 13 x^{3} + 67 x^{4} + 381 x^{5} + 2307 x^{6} + 14589 x^{7} + 95235 x^{8} + 636925 x^{9} + O(x^{10}),

where the sequence of coefficients corresponds to the sequence A064062 in [27] that counts simple outerplanar maps with a given number of vertices [15]. The n-th coefficient is given by the closed form

\frac{1}{n} ∑_{m=0}^{n−1}(n − m)\binom{n + m − 1}{m}2^{m}.

An asymptotic approximation for the ratio of the numbers of intervals in T_{n} and S_{n} is

\frac{2^{5n+ \frac{5}{2}}}{n · 3^{3n+ \frac{1}{2}}} .

The series expansion of I(x, y) is

yx + (2 y + 1) yx^{2} + (5 y^{2} + 5 y + 3) yx^{3} + (14 y^{3} + 20 y^{2} + 20 y + 13) yx^{4}

+ (42 y^{4} + 75 y^{3} + 98 y^{2} + 99 y + 67) yx^{5} + O (x^{6}) .

6. Going further

We discussed here several open questions related to the lattice S_{n} = (D_{n}, ≤).

Question 1. Finding a combinatorial interpretation of the equality J(x, 1) = x + 2J(x, 1)^{2}.

An outerplanar map [15] is a connected planar multigraph with a specific embedding in the 2-sphere, up to oriented homeomorphisms, where a root edge is selected and oriented, and such that all its vertices are in the outer face.

Question 2. Find a nice bijection between intervals in S_{n} and the simple outerplanar maps with a given number of vertices.

The distance between two Dyck paths P and Q is the length of a shortest path between P in Q in the underlying undirected graph of the poset.

Question 3. Is there a polynomial time algorithm to compute the distance between two Dyck paths in S_{n}?

The diameter is the maximum distance between any two vertices.

Question 4. For n ≥ 3, we conjecture that the diameter of S_{n} is 2n − 4, and that this value corresponds to the distance between (UD)^{n} and UU(UD)^{n−2}DD.

The Möbius function [29] of S_{n}, μ : S_{n} → ℤ is defined recursively by

μ(P) = − ∑_{Q<P} μ(Q) if P ≠ (UD)^{n}, with initial condition μ((UD)^{n}) = 1.

Question 5. For n ≥ 2, is there an efficient and non-recursive algorithm to compute the Möbius function of S_{n} as in [21]?

An m-Dyck path of size n is a path on ℕ^{2}, starting at the origin and ending at (2nm, 0), consisting of up-steps (m, m) and down-steps (1, −1). In the literature, these paths have been endowed with a lattice structure that generalizes the Tamari lattice [8, 9].

Question 6. Is it possible to generalize this study for m-Dyck paths?

The Tamari covering transforms an occurrence of DUP D into UP DD without any constraints on the structure of a Dyck path P. The covering relation discussed in this paper can be viewed as the following restriction of the Tamari covering: we only allow DUP D ⟶ UP DD whenever the path P avoids consecutive pattern DU. This opens the way to the further generalization: pattern-avoiding Tamari poset is given by the transitive closure of the covering DUP D ⟶ UP DD where P avoids a given consecutive pattern ν. It is easy to prove that any Dyck path of semilength n can be obtained from (UD)^{n} by a sequence of such pattern-aware transformations for any ν. For k ≥ 1, n ≥ k + 2, if ν = U^{k}, then the poset will have at least two non comparable maximal elements U^{n}D^{n} and UDU^{k+1}D^{k+1}. In general the situation is not that simple, for example, if ν = UDU the poset has a minimum and maximum element, but some pairs of paths do not have a greatest lower bound. However, if ν = UUDU then it seems that we obtain a lattice structure. So, it becomes natural to ask the following.

Question 7. Could we characterize patterns ν inducing a lattice structure in the patternavoiding version of the Tamari poset?

Acknowledgements

The authors are grateful to the referees for their detailed comments and corrections, which helped improve the paper. Jean-Luc Baril and Sergey Kirgizov were partially supported by ANR PiCs (ANR-22-CE48-0002) and ANR ARTICO funded by Bourgogne-Franche-Comté region. Mehdi Naima was supported from the CNRS through the MITI interdisciplinary programs.

Figure 7. Hasse diagram of S_{6} = (D_{6}, ≤) (black edges). The Tamari lattice T_{6} = (D_{6}, ⪯) can be viewed by considering black and red edges.

References

[1] C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, and D. Gouyou-Beauchamps. Generating functions for generating trees. Discrete Math., 246, 2002, 29–55.

[2] E. Barcucci, A. Bernini, L. Ferrari, and M. Poneti. A distributive lattice structure connecting Dyck paths, noncrossing partitions and 312-avoiding permutations. Order, 22(4) (2005), 311–328.

[3] J.-L. Baril, M. Bousquet-Mélou, S. Kirgizov, and M. Naima. The ascent lattice on Dyck paths. To appear in Electron. J. Combin., (2025).

[4] J.-L. Baril, and J.-M. Pallo. The phagocyte lattice of Dyck words. Order, 23(2-3) (2006), 97–107.

[5] J.-L. Baril, and J.-M. Pallo. The pruning-grafting lattice of binary trees. Theoretical Computer Science, 409(3) (2008), 382–293.

[6] J.-L. Baril, and J.-M. Pallo. A Motzkin filter in the Tamari lattice. Discrete Math., 338 (2015), 1370– 1378.

[7] O. Bernardi, and N. Bonichon. Intervals in Catalan lattices and realizers of triangulations. J. Combin. Theory, Ser. A, 116 (2009), 55—75.

[8] F. Bergeron, and L.-F. Préville-Ratelle. Higher trivariate diagonal harmonics via generalized Tamari posets. J. Comb. 3(3) (2012), 317–341.

[9] M. Bousquet-Mélou, É. Fusy, and L.-F. Préville-Ratelle. The number of intervals in the m-Tamari lattices. Electron. J. Combin., 18(2) (2011), paper 31.

[10] M. Bousquet-Mélou, and F. Chapoton. Intervals in the greedy Tamari posets. Comb. Theory, 4(1) (2024), paper 5.

[11] F. Chapoton. Sur le nombre d’intervalles dans les treillis de Tamari. Sém. Lothar. Combin., 55 (2006), Art. B55f (electronic).

[12] F. Chapoton. Some properties of a new partial order on Dyck paths. Algebraic Combin., 3(2) (2020), 433–463.

[13] W. Fang, and L.-F. Préville-Ratelle. The enumeration of generalized Tamari intervals. Europ. J. Combin., 61 (2017), 69–84.

[14] P. Flajolet, and R. Sedgewick. Analytic combinatorics, Cambridge University Press, Cambridge, 2009.

[15] I. Geffner, and M. Noy. Counting outerplanar maps. Electron. J. Combin., 24(2) (2017), P2.3.

[16] W. Geyer. On Tamari lattices. Discrete Math., 133 (1994), 99–122.

[17] G. Grätzer. General lattice theory. Second edition, Birkhäuser, 1998.

[18] S. Huang, and D. Tamari. Problems of associativity: A simple proof for the lattice property of systems ordered by a semi-associative law. J. Combin. Theory, Ser. A, 13 (1972), 7–13.

[19] D.E. Knuth. The art of computer programming, vol. 3: Sorting and searching. 2nd ed. Addison-Wesley, 1998.

[20] F. Müller-Hoissen, J.-M. Pallo, and J. Stasheff (eds.). Associahedra, Tamari lattices and related structures. Progress in Mathematics, vol. 299, Birkhäuser, 2012.

[21] J.-M. Pallo. An algorithm to compute the Möbius function of the rotation lattice of binary trees. RAIRO Informatique Théorique et Applications, 27 (1993), 341–348.

[22] J.-M. Pallo, and R. Racca. A note on generating binary trees in A-order and B-order. Intern. J. Computer Math., 18 (1985), 27–39.

[23] J.-M. Pallo. Right-arm rotation distance between binary trees. Inf. Process. Lett., 87(4) (2003), 173–177.

[24] H. Prodinger. The kernel method: a collection of examples. Sém. Lothar. Combin., 50 (2004), Paper B50f.

[25] R. Simion, and D. Ullman. On the structure of the lattice of noncrossing partitions. Discrete Math., 98 (1991), 193–206. ¡

[26] D.D. Sleator, R.E. Tarjan, and W.P. Thurston. Rotation distance, triangulations and hyperbolic geometry. J. Amer. Math. Soc., 1 (1988), 647–681.

[27] N.J.A. Sloane. The On-line Encyclopedia of Integer Sequences, available electronically at http://oeis.org.

[28] R.P. Stanley. Catalan numbers. Cambridge University Press, 2015.

[29] R.P. Stanley. Supersolvable lattices. Alg. Univ., 2 (1972), 197–217.

[30] D. Tamari. The algebra of bracketings and their enumeration. Nieuw Archief voor Wiskunde, 10 (1962), 131–146.