On the dominance partial ordering of Dyck paths

A. Sapounakis, I. Tasoulas, and P. Tsikouras Department of Informatics University of Piraeus 18534 Piraeus GREECE

                {arissap, jtas, pgtsik}@unipi.gr

Abstract The lattice of Dyck paths with the dominance partial order is studied. The notions of filling and degree of a Dyck path are introduced, studied and used for the evaluation of the Möbius function and its powers. The relation between the symmetric group endowed with the weak Bruhat order and the set of Dyck paths is studied.

1 Introduction

A wide range of articles dealing with lattices of combinatorial objects appear frequently in the literature, e.g., lattices of integer partitions, [4, 20], permutations [11, 21] and noncrossing partitions [8, 17].

In this paper, the lattice of Dyck paths with the dominance partial order and some of its relations to other combinatorial structures are studied.

In Section 2, some basic definitions and notations referring to the set D_{n} of Dyck paths of semilength n, are given.

In Section 3, the rank of a Dyck path is studied and the rank-generating function is exhibited.

In Section 4, the notions of filling and degree of a Dyck path are introduced and studied. Various enumeration results are presented. These notions are used in Section 5 for the evaluation of the Möbius function and its powers. In this context, a new appearance of the Fibonacci numbers (\underline{A000045} of [18]) occurs.

Finally, in Section 6 the relation between the symmetric group S_{n} endowed with the weak Bruhat order and D_{n} is studied. More precisely, a partition of S_{n} into C_{n} (Catalan, (\underline{A000108}) of [18]) classes is constructed, satisfying an ordering condition, and the cardinal numbers of its members are evaluated.

2 Preliminaries

A Dyck path of semilength n is a path in the first quadrant, which begins at the origin, ends at (2n, 0), and consists of steps (1, 1) and (1, −1), called rise and fall respectively.

It is clear that each Dyck path is coded by a word u ∈ {a, ā}^{∗}, called Dyck word, so that every rise (resp. fall) corresponds to the letter a (resp. ā); see Fig. 1.

a a ā ā a a a a a a ā ā a ā ā ā a ā ā ā

Figure 1: A Dyck path and its corresponding word

Throughout this paper we will denote with D the set of all Dyck paths (or equivalently Dyck words). Furthermore, the subset of D that contains the paths u of semilength l(u) = n is denoted by D_{n}.

We denote with ϵ the empty path. Every u ∈ D \ {ϵ} can be uniquely decomposed in the form u = awāv, w, v ∈ D, which is called the first return decomposition of u.

Every Dyck path u that meets the x-axis only at its endpoints (i.e., u = awā, with w ∈ D) is called prime. Every Dyck path can be uniquely decomposed into prime paths [15].

It is well known that Dyck paths are enumerated by the Catalan numbers, with generating function C(x), which satisfies the relation xC^{2}(x) = C(x) − 1.

For a parameter q defined on D, we will denote with F_{q} the generating function of D according to the parameters l, q, i.e.,

F_{q}(x, y) = ∑_{u∈D} x^{l(u)}y^{q(u)}.

A point of a Dyck path is called peak (resp. valley) if it is preceded by a rise (resp. fall) and followed by a fall (resp. rise). A point of a Dyck path is called double rise (resp. double fall) if it is preceded and followed by a rise (resp. fall).

A convenient way to represent a Dyck word is by using dominating sequences. A sequence d = (d_{i})_{i∈[n]} of non-negative integers is called dominating if it satisfies the following two conditions:

(i) ∑_{i=1}^{n} d_{i} = n,

(ii) ∑_{i=1}^{ν} d_{i} ≥ ν, for every ν ∈ [n].

It is well known that every non-empty Dyck word u is uniquely represented by a dominating sequence d(u) = (d_{i})_{i∈l(u)} where d_{1} is the number of a’s before the 1^{st} occurrence of ā in u, and d_{i} is the number of a’s between the (i − 1)^{th} and the i^{th} occurrence of ā in u, where i ∈ [2, l(u)]. For example, the word u = aaāāaāaaāaāā is represented by the sequence d(u) = 2, 0, 1, 2, 1, 0.

A sequence d = (d_{i})_{i∈[n]} dominates another sequence d′ = (d′_{i})_{i∈[n]} iff ∑_{i=1}^{ν} d_{i} ≥ ∑_{i=1}^{ν} d′_{i} for

every ν ∈ [n]. In this case we say that d′ is dominated by d. Notice that every dominating sequence dominates the constant sequence with elements equal to 1.

The dominance partial order “⪯” on D is defined as follows:

u ⪯ w iff l(u) = l(w) and the sequence d(u) is dominated by the sequence d(w), i.e., the path w lies above (in the broad sense) the path u. If u ⪯ w and u ≠ w, we will write u ≺ w.

In the sequel, we will denote (D, ⪯) (resp. (D_{n}, ⪯)) with D (resp. D_{n}).

Narayana and Fulton [12], using an equivalent language, proved that the set of Grand-Dyck paths of fixed length n (i.e., paths defined similarly to Dyck paths but allowed to go below the x-axis, e.g., see [16]) endowed with the dominance order is a distributive lattice. Kreweras [13, 14] has done further work in this context. Ferrari and Pinzani [9] have recently presented a more general approach to this subject.

It is easy to see that D_{n} is a sublattice of the lattice of all Grand-Dyck paths of semilength n, such that if d(w) = (d′_{i})_{i∈[n]}, d(v) = (d′′_{i})_{i∈[n]} we have: d(w ∨ v) = (d_{i})_{i∈[n]}, where

d_{1} = max{d′_{1}, d′′_{1}} and d_{i} = max{∑_{j=1}^{i} d′_{j}, ∑_{j=1}^{i} d′′_{j}} − max{∑_{j=1}^{i−1} d′_{j}, ∑_{j=1}^{i−1} d′′_{j}} for every i ∈ [2, n]

and d(w ∧ v) = (d_{i})_{i∈[n]}, where

d_{1} = min{d′_{1}, d′′_{1}} and d_{i} = min{∑_{j=1}^{i} d′_{j}, ∑_{j=1}^{i} d′′_{j}} − min{∑_{j=1}^{i−1} d′_{j}, ∑_{j=1}^{i−1} d′′_{j}} for every i ∈ [2, n].

We note that the least (resp. greatest) element of D_{n} is 0_{n} = (aā)^{n} (resp. 1_{n} = a^{n}ā^{n}). Finally, for every n ≥ 2, 1_{n} covers one and only one element of D_{n}, namely a^{n−1}āaā^{n−1}.

The Hasse diagram of D_{4} coded by dominating sequences is given in Fig. 2.

All unexplained notations and definitions for posets and Dyck paths can be found in [20] and [5], respectively.

3 Chains and Ranks

In this section we first evaluate the length of maximal chains in intervals of D_{n}. For this, notice first that for u, w ∈ D_{n} with d(u) = (d_{i})_{i∈[n]} and d(w) = (d′_{i})_{i∈[n]}, w covers u iff there exists j ∈ [n − 1] such that d′_{i} = d_{i} for every i ≠ j, j + 1 and d′_{j} = d_{j} + 1, d′_{j+1} = d_{j+1} − 1.

From the above observation, we deduce that every path w which covers the path u is obtained by turning a valley (x, y) of u into the peak (x, y + 2).

Figure 2: The Hasse diagram of D_{4}

Proposition 3.1. Let u, w ∈ D_{n} with u ⪯ w and d(u) = (d_{i})_{i∈[n]}, d(w) = (d′_{i})_{i∈[n]}. Then, the length of every maximal chain C of [u, w] is equal to

∑_{i=1}^{n} i(d_{i} − d′_{i}).

Proof. We will use induction with respect to the length k of C. If k = 1 then w covers u; so there exists j ∈ [n − 1] with d_{i} = d′_{i} for every i ∈ [n] \ {j, j + 1} and d′_{j} = d_{j} + 1, d′_{j+1} = d_{j+1} − 1.

Hence

∑_{i=1}^{n} i(d_{i} − d′_{i}) = j(d_{j} − d′_{j}) + (j + 1)(d_{j+1} − d′_{j+1})
= j(−1) + (j + 1)1 = 1.

Since in this case the only maximal chain of [u, w] is {u, w} and has length 1, the result holds when k = 1.

Suppose now that the result holds for every maximal chain of [u, w] of length k, for every u, w ∈ D_{n} with u ≺ w. We will prove that the result also holds for any maximal chain C of [u, w] of length k + 1.

If v is the predecessor of w, then C \ {w} is a maximal chain of [u, v] of length k; so by the induction hypothesis we have

k = ∑_{i=1}^{n} i(d_{i} − d′′_{i})

where d(v) = (d′′_{i})_{i∈[n]}.

Since ∑_{i=1}^{n} i(d′′_{i} − d′_{i}) = 1, we obtain that ∑_{i=1}^{n} i(d_{i} − d′_{i}) = k + 1. □

If we apply the previous proposition for u = 0_{n} and w = 1_{n} we obtain that every maximal chain in D_{n} has length equal to n(n − 1)/2. Thus, the lattice D_{n} is graded of rank \binom{n}{2}.

In the sequel, we investigate the parameter “rank” of D defined as follows : ρ(ϵ) = 0 and for u ≠ ϵ, ρ(u) is the rank of u in D_{l(u)}.

By Proposition 3.1, it follows easily that if u ≠ ϵ with d(u) = (d_{i})_{i∈l(u)}, then

ρ(u) = l(u)(l(u) + 1)/2 − ∑_{i=1}^{l(u)} id_{i}.  (1)

Ferrari and Pinzani [9] give an equivalent expression of the above relation through the notion of the area of a Dyck path. Using relation (1) (or alternatively its equivalent relation in [9]), we can deduce that the parameter “rank” satisfies the following properties:

(i) ρ(wv) = ρ(w) + ρ(v),

(ii) ρ(awā) = ρ(w) + l(w), for every w, v ∈ D.

Taking into account the above properties and the fact that every Dyck path is either empty or of the form awāv, where w, v ∈ D, we can easily deduce the following relation.

F_{ρ}(x, y) = 1 + xF_{ρ}(xy, y)F_{ρ}(x, y).  (2)

Furthermore, if f_{n}(y) = \begin{matrix}( & {n \atop 2} & ) \\ ∑ \\ k=0 \end{matrix} a_{n,k}y^{k}, where a_{n,k} denotes the number of elements of D_{n} of

rank k, then by relation (2) we have

∑_{n=0}^{∞} f_{n}(y)x^{n} = 1 + x (∑_{n=0}^{∞} f_{n}(y)y^{n}x^{n}) (∑_{n=0}^{∞} f_{n}(y)x^{n})

or, equivalently,

∑_{n=0}^{∞} f_{n+1}(y)x^{n} = ∑_{n=0}^{∞} (∑_{ν=0}^{n} f_{ν}(y)f_{n−ν}(y)y^{ν}) x^{n}.

Hence we obtain the following result.

Proposition 3.2. The rank-generating function of D_{n} is given by the following recursive formula

f_{n+1}(y) = ∑_{ν=0}^{n} f_{ν}(y)f_{n−ν}(y)y^{ν},

where f_{0}(y) = 1.

4 Fillings and Degrees

In this section we first introduce and study the notion of the filling of a Dyck path.

The filling ũ of u ∈ D \ {ϵ} is defined to be the Dyck path obtained by turning each valley (x, y) of u into the peak (x, y + 2). The filling of the empty path is assumed to be the empty path.

For example, if u = aaāāaaāaāā then ũ = aaāaāaaāāā.

The main properties of the filling are given in the following proposition, which is easy to prove.

Proposition 4.1. For a non-empty Dyck path u we have :

i) l(ũ) = l(u), u ⪯ ũ and u = ũ if u = 1_{l(u)}. ii) The length l(u, ũ) of the interval [u, ũ] is equal to the number val(u) of all valleys of u. iii) The cardinal number of the interval [u, ũ] is equal to 2^{val(u)}. iv) If u ⪯ v, then ũ ⪯ ṽ.

We note that since the parameter val defined by the number of valleys follows the Narayana distribution [5], we deduce that the number a_{n,k} of all u ∈ D_{n} such that the interval [u, ũ] contains exactly k elements is equal to

a_{n,k} = \begin{cases}\frac{1}{n} \binom{n}{λ}\binom{n}{λ−1}, & if k = 2^{λ}, λ ∈ ℕ^{∗}; \\ 0, & if k ≠ 2^{λ}, λ ∈ ℕ^{∗}. \end{cases}

Next, we consider the Dyck paths which are fillings of Dyck paths. For this, we need the following characterization.

Proposition 4.2. A Dyck path u is a filling of a Dyck path iff u is prime and avoids āāaa.

Proof. If u = ṽ for some v ∈ D, then clearly u has no valleys on level zero and so u is prime. Furthermore, if u contains a āāaa, then there exists a valley (x, y) of u such that the points (x − 1, y + 1) and (x + 1, y + 1) are a double fall and a double rise of u, respectively. It follows that the points (x, y), (x − 1, y + 1) and (x + 1, y + 1) remain unchanged during the generation of u from v, so that (x, y) is also a valley of v. This contradicts the definition of the filling, since (x, y + 2) is not a peak of u.

Conversely, assume that u is prime and avoids āāaa. Let v be the path that we obtain from u by turning each peak (x, y) of u into the valley (x, y − 2). Clearly, since u is prime it has no low peaks, hence v never crosses the x-axis and so v ∈ D. In order to show that ṽ = u, it is enough to show that every valley of v is generated by a peak of u according to the above procedure. Indeed, if this is not true and (x, y) is a valley of v that is not generated in such a way, then (x, y) must be a valley of u, too. Since u avoids āāaa, it follows that at least one of the points (x − 1, y + 1) and (x + 1, y + 1) is a peak of u and hence a valley of v, which contradicts the fact that (x, y) is a valley of v. □

We remark that the Dyck path v constructed by turning each peak of a Dyck path u into a valley as in the converse of the above proof, is the least Dyck path with the property ṽ = u. In this case, we say that v is the antifilling of u.

In the following, we study the set D̃ of all Dyck paths that are fillings of Dyck paths.

Proposition 4.3. The generating function F of D̃ according to semilength satisfies the equation

F (x) = 1 + xF^{2}(x) − x^{2}F (x).  (3)

Furthermore, the number a_{n} of all Dyck paths of semilength n that are fillings of Dyck paths is given by the formula

a_{n} = ∑_{k=[n/2]}^{n} \frac{(−1)^{n−k}}{k} \binom{k}{n − k}\binom{3k − n}{k − 1}, for n ≥ 2  (4)

whereas a_{0} = a_{1} = 1.

Proof. Let A be the set of all Dyck paths that avoid āāaa and A(x) its generating function according to semilength.

Clearly, by the previous proposition, every non-empty element of D̃ can be written uniquely in the form awā where w ∈ A, so that F (x) = 1 + xA(x).

Furthermore, we can easily check that every non-empty element u ∈ A can be written uniquely in one of the following forms: u = aāv, u = awā or u = awāaāv where w, v ∈ A and w ≠ ϵ.

Thus, we have:

A(x) = 1 + xA(x) + x(A(x) − 1) + x^{2}(A(x) − 1)A(x).

So

x^{2}A^{2}(x) − (x − 1)^{2}A(x) + 1 − x = 0

and hence

xF^{2}(x) − (1 + x^{2})F (x) + 1 = 0

which gives formula (3).

For the proof of formula (4) we consider the generating function F (x, y) satisfying the equation

F (x, y) = 1 + y(xF^{2}(x, y) − x^{2}F (x, y)).  (5)

If we set P (λ) = xλ^{2} − x^{2}λ, then F (x, y) = 1 + yP (F (x, y)); so applying the Lagrange inversion formula with respect to the variable y, in the form given by Deutsch [5], we obtain that

[y^{k}]F = \frac{1}{k}[λ^{k−1}](P (1 + λ))^{k}  (6)

for every k ∈ ℕ^{∗}.

Furthermore, we have

(P (1 + λ))^{k} = x^{k} ∑_{ν=0}^{k} ∑_{ρ=0}^{k} \binom{k}{ν}\binom{k}{ρ}λ^{ν}(λ − x)^{ρ}

= ∑_{ν=0}^{k} ∑_{ρ=0}^{k} ∑_{i=0}^{ρ}(−1)^{ρ−i}\binom{k}{ν}\binom{k}{ρ}\binom{ρ}{i}λ^{ν+i}x^{k+ρ−i}.

Then, for i = k − ν − 1, from relation (6) we obtain that

[y^{k}]F = \frac{1}{k} ∑_{ρ=0}^{k} ∑_{ν=0}^{k−1}(−1)^{ρ−k+ν+1}\binom{k}{ν}\binom{k}{ρ}\binom{ρ}{k − ν − 1}x^{ρ+ν+1}.

Thus,

F (x, y) = 1 + ∑_{k=1}^{∞} ∑_{ρ=0}^{k} ∑_{ν=0}^{k−1}(−1)^{ρ−k+ν+1} \frac{1}{k}\binom{k}{ν}\binom{k}{ρ}\binom{ρ}{k − ν − 1}x^{ρ+ν+1}y^{k}

= 1 + xy + ∑_{n=2}^{∞} ∑_{k=[n/2]}^{n} ∑_{ν=0}^{k−1}(−1)^{n−k} \frac{1}{k}\binom{k}{ν}\binom{k}{n − ν − 1}\binom{n − ν − 1}{k − ν − 1}x^{n}y^{k}

= 1 + xy + ∑_{n=2}^{∞} ∑_{k=[n/2]}^{n}(−1)^{n−k} \frac{1}{k}\binom{k}{n − k}\binom{3k − n}{k − 1}x^{n}y^{k}.

Thus, since by relations (3) and (5) we have F (x) = F (x, 1), it follows that

a_{0} = a_{1} = 1 and a_{n} = ∑_{k=[n/2]}^{n}(−1)^{n−k} \frac{1}{k}\binom{k}{n − k}\binom{3k − n}{k − 1}, for n ≥ 2. □

By formula (4) by obtain the sequence 1,1,1,2,5,13,35,97,275,…, which also counts the number of Dyck paths that avoid aaāā (\underline{A086581} of [18]). This can also be seen by proving that the set of all antifillings coincides with the set of all Dyck paths that avoid aaāā.

The rest of this section deals with the notion of the degree of a Dyck path. For this, we define the i^{th} filling u^{(i)} of a non-empty Dyck path u recursively, as follows:

u^{(0)} = u and u^{(i)} = { \atop u^{(i−1)}}, for i ≥ 1.

We define the degree δ(u) of u ∈ D \ {ϵ} to be the least non-negative integer such that u^{(δ(u))} = 1_{l(u)}. The degree of the empty path is assumed to be equal to zero. For example, if u = aaāāaaāaāā then δ(u) = 4.

The main properties of the degree are given in the following result.

Proposition 4.4. For every non-empty Dyck path u we have:

i) δ(ũ) = δ(u) − 1, for every u ≠ 1_{l(u)}. ii) δ(auā) = δ(u). iii) 0 ≤ δ(u) ≤ l(u) − 1, and δ(u) = l(u) − 1 iff u is non-prime. iv) If u ≺ v, then δ(v) ≤ δ(u).

Proof. i) is obvious, whereas ii) is based on the equality (awā)^{(i)} = aw^{(i)}ā, for every i ∈ ℕ.

For the proof of iii) we first show by induction with respect to the semilength of u that if u is non-prime then δ(u) = l(u) − 1.

Indeed, if l(u) = 2, then u = aāaā and δ(u) = 1 = l(u) − 1. Assume that the result holds for every non-prime Dyck path with semilength equal to n − 1, where n ≥ 3, and let u be a non-prime path of semilength n. Then, using the prime decomposition of u, there exists a finite sequence (w_{i})_{i∈[k]}, k ≥ 2, of Dyck words such that

u = aw_{1}āaw_{2}āa ⋯ āaw_{k−1}āaw_{k}ā.

It follows easily that

ũ = aw̃_{i}aāw̃_{2}aā ⋯ aāw̃_{k−1}aāw̃_{k}ā.

If we set

z = w̃_{i}aāw̃_{2}aā ⋯ aāw̃_{k−1}aāw̃_{k},

then z ∈ D, l(z) = n − 1, ũ = azā and z is non-prime. Thus, by the induction hypothesis we have δ(z) = l(z) − 1 and so

δ(u) = δ(ũ) + 1 = δ(z) + 1 = l(z) = l(u) − 1.

Next, we note that 0 ≤ δ(u) and δ(u) = 0 iff u = 1_{l(u)}. Furthermore, if u ≠ 1_{l(u)}, there exists ν ∈ ℕ such that u = a^{ν}wā^{ν}, where w is a non-prime Dyck path.

Then, by ii) we deduce that

δ(u) = δ(w) = l(w) − 1 ≤ l(u) − 1.

It remains to check that δ(u) < l(u) − 1 for every prime Dyck path u. Indeed, u = awā with w ∈ D, so that δ(u) = δ(w) ≤ l(w) − 1 = l(u) − 2.

Finally, we show iv) using induction with respect to the semilength of u. It is clear that the result is true when l(u) = 1. Assuming that the result holds for Dyck paths of semilength n − 1, where n ≥ 2, we will show that if u, v ∈ D_{n} with u ≺ v then δ(v) ≤ δ(u). Clearly, by iii), it is enough to restrict ourselves to the case where u is a prime word. Thus, if u = au′ā where u′ ∈ D_{n−1}, it follows easily that v = av′ā, where v′ ∈ D_{n−1} and u′ ≺ v′. From the induction hypothesis it follows that δ(v) = δ(v′) ≤ δ(u′) = δ(u). □

We conclude this section with the following result.

Proposition 4.5. The number of all u ∈ D_{n}, n ≥ 2, with degree equal to k, where k ∈ [n − 1], is equal to C_{k+1} − C_{k}.

Proof. Clearly, since every non-empty Dyck path u can be written uniquely in either of the forms u = awā or u = awāv, where w, v ∈ D and v ≠ ϵ, applying Proposition 4.4 we obtain that

F_{δ}(x, y) = 1 + xF_{δ}(x, y) + xC(xy)(C(xy) − 1).

It follows that

F_{δ}(x, y) = \frac{1 + y^{−1} ∑_{n=1}^{∞} C_{n}(xy)^{n} − x ∑_{n=0}^{∞} C_{n}(xy)^{n}}{1 − x}

= \frac{1 + ∑_{n=1}^{∞} (C_{n} − C_{n−1}) y^{n−1}x^{n}}{1 − x}

= (∑_{n=0}^{∞} g_{n}(y)x^{n}) (∑_{n=0}^{∞} x^{n}) ,

where

g_{n}(y) = \begin{cases}(C_{n} − C_{n−1}) y^{n−1}, & if n ≥ 1; \\ 1, & if n = 0. \end{cases}

Therefore, we have

F_{δ}(x, y) = ∑_{n=0}^{∞} ∑_{k=0}^{n} g_{k}(y)x^{n}

= ∑_{n=0}^{∞} x^{n} + ∑_{n=2}^{∞} ∑_{k=1}^{n−1}(C_{k+1} − C_{k})y^{k}x^{n},

which gives the required result. □

5 The Möbius function

In this section we study the Möbius function of D and its powers. We recall [20] that the Möbius function μ of a poset (P, ⪯) is defined by

μ(x, y) = − ∑_{x⪯z≺y} μ(x, z) for x ≺ y and μ(x, x) = 1.

Furthermore, the k-th power of μ, for k ≥ 2, is defined by

μ^{k}(x, y) = ∑_{x=x_{0}⪯x_{1}⪯···⪯x_{k}=y} μ(x_{0}, x_{1})μ(x_{1}, x_{2}) ⋯ μ(x_{k−1}, x_{k}).

It is known [3] that if (P, ⪯) is a locally finite distributive lattice, then its Möbius function is given by the formula

μ(x, y) = \begin{cases}(−1)^{ν}, & if y is a join of ν elements covering x; \\ 0, & if y is not a join of elements covering x. \end{cases}

For the lattice of Dyck paths, we have that v ∈ (u, ũ] with l(u, v) = ν iff v is obtained by turning ν of the valleys of u into peaks or, equivalently, iff v is a join of ν elements of D covering u. Thus, from the above formula we obtain the following result.

Proposition 5.1. The Möbius function of D is given by the formula

μ(u, v) = \begin{cases}(−1)^{l(u,v)}, & if u ⪯ v ⪯ ũ; \\ 0, & otherwise \end{cases}

for every u, v ∈ D, where l(u, v) denotes the length of the interval [u, v].

In the sequel we study the powers of the Möbius function of D_{n}. For this, we need the following result, which is an easy consequence of Proposition 5.1.

Corollary 5.2. For every multichain u_{0} ⪯ u_{1} ⪯ ⋯ ⪯ u_{k} in D_{n} with

μ(u_{0}, u_{1})μ(u_{1}, u_{2}) ⋯ μ(u_{k−1}, u_{k}) ≠ 0

we have u_{i} ⪯ ũ_{i−1} and u_{i} ⪯ u_{0}^{i} for every i ∈ [k].

Clearly, if u ∈ D_{n} and k < δ(u), for every multichain u = u_{0} ⪯ u_{1} ⪯ ⋯ ⪯ u_{k} = 1_{n} we have that u^{(k)} ≺ u_{k} so that, by the above Corollary, we deduce that

μ(u_{0}, u_{1})μ(u_{1}, u_{2}) ⋯ μ(u_{k−1}, u_{k}) = 0.

This shows that μ^{k}(u, 1_{n}) = 0 for every k < δ(u).

In the following result we consider the case where k = δ(u).

Proposition 5.3. Let u ∈ D_{n} and j, ν ∈ ℕ^{∗} such that u^{(j)} = 0_{l(u)}^{ν}. Then, we have that

μ^{δ(u)}(u, 1_{n}) = (−1)^{l(u^{(j)},1_{n})}μ^{j}(u, u^{(j)}).

Proof. Let u = u_{0} ⪯ u_{1} ⪯ ⋯ ⪯ u_{δ(u)} = 1_{n} be a multichain of D_{n} with

μ(u_{0}, u_{1})μ(u_{1}, u_{2}) ⋯ μ(u_{δ(u)−1}, u_{δ(u)}) ≠ 0;

then, by Corollary 5.2 it follows that u_{i} ⪯ ũ_{i−1} and u_{i} ⪯ u^{(i)} for every i ∈ [δ(u)]. We show that u_{i} = u^{(i)} for every i ≥ j.

Indeed, if this is not true, let ξ be the greatest element of [j, δ(u)] such that u_{ξ} ≺ u^{(ξ)}. Clearly, since u_{δ(u)} = 1_{l(u)} = u^{(δ(u))}, we have that ξ < δ(u). Since u^{(ξ+1)} = u_{ξ+1} ⪯ ũ_{ξ} ⪯ u^{(ξ+1)}, we obtain that u^{(ξ+1)} = ũ_{ξ}. Furthermore, since u^{(ξ)} = 0_{n}^{(ν+ξ−j)}, u^{(ξ+1)} = 0_{n}^{(ν+ξ−j+1)} and the antifilling of 0_{n}^{(k+1)} is 0_{n}^{(k)}

for every k ∈ [n − 2], we obtain that u^{(ξ)} is the antifilling of u^{(ξ+1)}, though ũ_{ξ} = u^{(ξ+1)} and u_{ξ} ≺ u^{(ξ)}, which is a contradiction.

Thus, u_{i} = u^{(i)} for every i ≥ j.

It follows that

μ^{δ(u)}(u, 1_{n}) = ∑ μ(u_{0}, u_{1})μ(u_{1}, u_{2}) ⋯ μ(u_{j−1},u^{(j)})μ(u^{(j)},u^{(j+1)})μ(u^{(j+1)},u^{(j+2)}) ⋯ μ(u^{(δ(u)−1)},u^{(δ(u))})

where the sum is taken over all multichains u = u_{0} ⪯ u_{1} ⪯ ⋯ u_{j} = u^{(j)} of D_{n}. Since, by Proposition 5.1, we have

μ(u^{(j)}, u^{(j+1)})μ(u^{(j+1)}, u^{(j+2)}) ⋯ μ(u^{(δ(u)−1)}, u^{(δ(u))})
= (−1)^{l(u^{(j)},u^{(j+1)})}(−1)^{l(u^{(j+1)},u^{(j+2)})} ⋯ (−1)^{l(u^{(δ(u)−1)},u^{(δ(u))})}
= (−1)^{l(u^{(j)},1_{n})},

we deduce that

μ^{δ(u)}(u, 1_{n}) = (−1)^{l(u^{(j)},1_{n})}μ^{j}(u, u^{(j)}). □

Remark Let N be the set of all non-empty Dyck paths u such that ũ = 0_{l(u)}^{ν} for some ν ∈ ℕ^{∗}. Then, taking j = 1 in the previous proposition, we obtain that

μ^{δ(u)}(u, 1_{l(u)}) = (−1)^{l(ũ,1_{l(u)})}μ(u, ũ)
= (−1)^{l(ũ,1_{l(u)})}(−1)^{l(u,ũ)}
= (−1)^{l(u,1_{l(u)})}

for every u ∈ N.

In particular if u = 0_{n} for some n ∈ ℕ^{∗}, we have that δ(u) = n − 1 and

μ^{n−1}(0_{n}, 1_{n}) = (−1)^{\binom{n}{2}}.

Thus, by Lemma 4.1 in [6] we deduce that the zeta polynomial of D_{n} satisfies the following formula

Z(D_{n}, −k) = \begin{cases}(−1)^{\binom{n}{2}}, & if k = n − 1; \\ 0, & if 1 ≤ k < n − 1. \end{cases}

We close this section by enumerating the sets N ∩ D_{n}.

For this, we consider the set

N_{ν,n} = {u ∈ D_{n} : ũ = 0_{n}^{ν}}

where ν ∈ ℕ^{∗} and ν ≤ n − 1.

Clearly, for every p ∈ ℕ^{∗}, by considering the bijection u → a^{p}uā^{p} we can deduce that

|N_{ν,n}| = |N_{ν+p,n+p}|  (7)

for every p ∈ ℕ^{∗}.

Furthermore, we have the following result.

Proposition 5.4. For every ν ∈ ℕ^{∗}, the sequence (N_{ν,n}), n ≥ ν + 1 satisfies the following relation

|N_{ν,n}| = F_{n−ν+2},

where (F_{n}) denotes the Fibonacci sequence.

Proof. In view of relation (7) it is enough to show that

|N_{1,n}| = F_{n+1}

for every n ≥ 2.

Clearly, since |N_{1,2}| = 2 and |N_{1,3}| = 3, it is enough to show that

|N_{1,n}| = |N_{1,n−1}| + |N_{1,n−2}|

for every n ≥ 4.

Every element of N_{1,n} is obtained by turning some peaks of ˜0_{n} into valleys. However, in this procedure for the generation of the elements of N_{1,n} we must turn at least one of each pair of consecutive peaks into valleys.

Thus, if A_{1} (resp. A_{2}) is the set that consists of all elements of N_{1,n} that pass from the point (2, 0) (resp. (2, 2)), then {A_{1}, A_{2}} is a partition of N_{1,n}.

Clearly, A_{1} = N_{1,n−1} and since the elements of A_{2} must pass from the point (4, 0), we have A_{2} = N_{1,n−2}, which gives the required result. □

We note that using the previous proposition, we obtain by a simple summation that |N ∩ D_{n}| = F_{n+3} − 3, (\underline{A006327} of [18]).

6 Dyck paths and permutations

We recall that a simple reduction of a permutation π = π(1)π(2) ⋯ π(n) is a permutation obtained from π by interchanging some π(i) with π(i + 1), provided that π(i) > π(i + 1).

The weak Bruhat order ⋉ is defined on the symmetric group S_{n} as follows:

σ ⋉ π iff σ can be obtained from π by a sequence of simple reductions. The poset (S_{n}, ⋉) is a well known distributive lattice, graded of rank \binom{n}{2} and has many

interesting properties [7, 19]. In the following, we examine the connection between the lattices (S_{n}, ⋉) and (D_{n}, ⪯). For this, we first define the set L_{n} of all finite sequences (A_{i})_{i∈[n]} of

pairwise disjoint subsets of [n] such that [ν] ⊆ ⋃_{i=1}^{ν} A_{i} for every ν ∈ [n] and ⋃_{i=1}^{n} A_{i} = [n].

For example, L_{3} = {({1}, {2}, {3}) , ({1}, {2, 3}, ∅) , ({1, 2}, ∅, {3}),

({1, 2}, {3}, ∅) , ({1, 3}, {2}, ∅), ({1, 2, 3}, ∅, ∅)}.

We will show that the sets S_{n} and L_{n} can be identified.

Indeed, for σ ∈ S_{n} and i ∈ [n] we define A_{i}^{σ} to be the set of all elements j ∈ [n] for which there exist exactly i − 1 elements of σ, which are less than j and lie on the left of j in σ.

We can easily check that the sequence (A_{i}^{σ})_{i∈[n]} belongs to L_{n}.

Conversely, if (A_{i})_{i∈[n]} ∈ L_{n} then there exists unique σ ∈ S_{n} such that A_{i}^{σ} = A_{i} for every i ∈ [n].

For the construction of σ we define recursively a finite sequence (σ_{j})_{j∈[n]}, such that σ_{j} ∈ S_{j} and for j > 1 with j ∈ A_{i} where i ∈ [n], σ_{j} is generated from σ_{j−1} by inserting j before the i^{th} element of σ_{j−1} if i < j, or by placing j at the end of σ_{j−1} if i = j. Then, for σ = σ_{n} we have A_{i}^{σ} = A_{i} for each i ∈ [n].

From the above discussion we have the following result.

Proposition 6.1. The mapping σ → (A_{i}^{σ})_{i∈[n]} is a bijection between the sets S_{n} and L_{n}.

Remark. Using the above bijection we can characterize the set of all permutations of S_{n}(312) (i.e. the ones avoiding the pattern 312) as follows: σ ∈ S_{n}(132) iff for every j, k ∈ [n] with j ∈ A_{i}^{σ}, k ∈ A_{l}^{σ} and i < l we have that j < k.

Indeed, assume that σ ∈ S_{n}(312) and j, k ∈ [n] with j ∈ A_{i}^{σ}, k ∈ A_{l}^{σ}, i < l and j > k. Since i < l, we have that j lies on the left of k and there exists some element m which is less that k and lies between them in σ. Then, the triplet jmk is an appearance of the pattern 312 in σ, which is a contradiction.

Conversely, assume that the sequence (A_{i}^{σ})_{i∈[n]} satisfies the above condition though σ contains the pattern 312. Let jmk be the first appearance of the pattern 312 in σ, with j ∈ A_{i}^{σ} and k ∈ A_{l}^{σ}. It follows that each element lying on the left of j in σ that is less than j is also less than k. Thus, i < l although j > k, which is a contradiction.

From the above remark it follows that if σ ∈ S_{n}(312), then every non-empty A_{i}^{σ} consists of consecutive integers.

Next, we consider the family of sets (Γ_{u})_{u∈D_{n}}, where

Γ_{u} = {σ ∈ S_{n} : d(u) = (|A_{i}^{σ}|)_{i∈[n]}}.

Proposition 6.2. The family (Γ_{u})_{u∈D_{n}} is a partition of S_{n} such that if σ ∈ Γ_{u}, π ∈ Γ_{w} and π covers σ, then w covers u.

Proof. We first show that Γ_{u} ≠ ∅, for every u ∈ D_{n}. Indeed, if d(u) = (d_{i})_{i∈[n]}, set A_{1} = [d_{1}]

and for i > 1, A_{i} = ∅ iff d_{i} = 0 and A_{i} = [∑_{j=1}^{i−1} d_{j} + 1, ∑_{j=1}^{i} d_{j}] iff d_{i} ≠ 0. It follows that the

sequence (A_{i})_{i∈[n]} belongs to L_{n} and |A_{i}| = d_{i} for every i ∈ [n], so that by Proposition 6.1 there exists σ ∈ S_{n} such that d(u) = (|A_{i}^{σ}|)_{i∈[n]} and σ ∈ Γ_{u}.

Next, if σ ∈ S_{n}, since the sequence (A_{i}^{σ})_{i∈[n]} belongs to L_{n}, it follows that (|A_{i}^{σ}|)_{i∈[n]} is a dominating sequence, so that there exists unique u ∈ D_{n} such that d(u) = (|A_{i}^{σ}|)_{i∈[n]} and hence σ ∈ Γ_{u}.

This shows that ⋃_{u∈D_{n}} Γ_{u} = S_{n}, and since the sets Γ_{u} are pairwise disjoint, the family

(Γ_{u})_{u∈D_{n}} is a partition of S_{n}.

Finally, since π covers σ, there exists unique k ∈ [n − 1] such that

σ(j) = π(j) for every j ∈ [n] \ {k, k + 1} and σ(k) = π(k + 1) < π(k) = σ(k + 1).

Then, if π(k) ∈ A_{ν}^{π} we have that π(k) ∈ A_{ν+1}^{σ}, A_{i}^{π} = A_{i}^{σ} for every i ∈ [n] \ {ν, ν + 1}, A_{ν}^{π} = A_{ν}^{σ} ∪ {π(k)}, A_{ν+1}^{π} = A_{ν+1}^{σ} \ {π(k)}.

Thus, since d(u) = (|A_{i}^{σ}|)_{i∈[n]}, d(w) = (|A_{i}^{π}|)_{i∈[n]}, |A_{i}^{π}| = |A_{i}^{σ}| for every i ∈ [n]\{ν, ν + 1}, |A_{ν}^{π}| = |A_{ν}^{σ}| + 1, and |A_{ν+1}^{π}| = |A_{ν+1}^{σ}| − 1, we deduce that w covers u. □

Remarks

1. By Proposition 6.2 it follows easily that if σ ∈ Γ_{u} and π ∈ Γ_{w} with σ ⋉ π, then u ⪯ w.

2. Since Γ_{0_{n}} = {ˆ0_{n}} and Γ_{1_{n}} = {ˆ1_{n}} where ˆ0_{n} and ˆ1_{n} are the least and greatest element of S_{n} respectively, by Proposition 6.2 it follows that for u ∈ D_{n} we have

ρ(σ) = ρ(u) for every σ ∈ Γ_{u},

where ρ denotes the rank function.

3. Following the first part of proof of Proposition 6.2 we realize that the sequence (A_{i}^{σ})_{i∈[n]} constructed for every u ∈ D_{n} satisfies the conditions of the previous remark and hence σ ∈ S_{n}(312). Since the number of permutations of S_{n}(312) is equal to C_{n}, we deduce that each Γ_{u} contains exactly one element of S_{n}(312). Thus, we can define a bijection f from S_{n}(312) to D_{n}, such that f(σ) = u iff σ ∈ Γ_{u}. This bijection has been also presented in different ways in [1], [2] and [10].

In the following, we will evaluate the cardinal number of Γ_{u} for a Dyck path u ∈ D_{n} with n ≥ 2. For this we need to consider the Dyck path u′ ∈ D_{n−1} obtained from the path u = a^{ν}āτ ∈ D_{n} if we delete its first peak, i.e., the path u′ = a^{ν−1}τ.

Lemma 6.3. For every u ∈ D_{n} with d(u) = (d_{i})_{i∈[n]} and d(u′) = (d′_{i})_{i∈[n−1]}, we have

d′_{1} = d_{1} + d_{2} − 1, d′_{i} = d_{i+1} for every i ∈ [2, n − 1]

and

|Γ_{u}| = \binom{d_{1} + d_{2} − 1}{d_{2}}|Γ_{u′}|.  (8)

Proof. Clearly, the proof of the first part of this lemma is evident. So we restrict ourselves to the proof of relation (8).

For σ′ ∈ Γ_{u′} and a subset B ⊆ A_{1}^{σ′} with |B| = d_{2}, we consider the finite sequence (A_{i})_{i∈[n]} defined as follows :

A_{1} = {1} ∪ {x : x − 1 ∈ A_{1}^{σ′} \ B}, A_{2} = {x : x − 1 ∈ B} and A_{i} = {x : x − 1 ∈ A_{i−1}^{σ′}} for i ≥ 3.

Then, since (A_{i}^{σ})_{i∈[n−1]} ∈ L_{n−1}, by the previous construction it follows that (A_{i})_{i∈[n]} ∈ L_{n}, so that by Proposition 6.1 there exists unique σ ∈ S_{n} such that

A_{1}^{σ} = {1} ∪ {x : x − 1 ∈ A_{1}^{σ′} \ B}, A_{2}^{σ} = {x : x − 1 ∈ B} and A_{i}^{σ} = {x : x − 1 ∈ A_{i−1}^{σ′}}. So |A_{1}^{σ}| = 1 + (|A_{1}^{σ′}| \ |B|) = d_{1}, |A_{2}^{σ}| = |B| = d_{2} and |A_{i}^{σ}| = |A_{i−1}^{σ′}| = d′_{i−1} = d_{i} for every

i ≥ 3. Thus, d(u) = (|A_{i}^{σ}|)_{i∈[n]} and σ ∈ Γ_{u}.

Moreover, we will show that every σ ∈ Γ_{u} is generated by a unique pair (σ′, B) as above. Indeed, given σ ∈ Γ_{u} we consider the sequence (A′_{i})_{i∈[n−1]} of sets in [n − 1] defined by

A′_{1} = {x : x + 1 ∈ A_{1}^{σ} ∪ A_{2}^{σ}}, A′_{i} = {x : x + 1 ∈ A_{i+1}^{σ}},

as well as the set

B = {x : x + 1 ∈ A_{2}^{σ}} ⊆ A′_{1}.

Then, (A′_{i}) ∈ L_{n−1} and so by Proposition 6.1 there exists a unique σ′ ∈ S_{n−1} such that A′_{i} = A_{i}^{σ′} for every i ∈ [n − 1]. It follows that σ′ ∈ Γ_{u′} and hence (σ′, B) is the required pair.

Thus, since |A_{1}^{σ′}| = d_{1} + d_{2} − 1 and |B| = d_{2}, we deduce that each permutation σ′ ∈ Γ_{u′} generates exactly \binom{d_{1}+d_{2}−1}{d_{2}} permutations σ ∈ Γ_{u} according to the above procedure.

This shows that

|Γ_{u}| = \binom{d_{1} + d_{2} − 1}{d_{2}}|Γ_{u′}|. □

Proposition 6.4. If u ∈ D_{n} with d(u) = (d_{i})_{i∈[n]}, we have that

|Γ_{u}| = ∏_{j=1}^{n−1} \frac{∑_{i=1}^{j} d_{i} − j + 1}{d_{j}!}.

Proof. We consider the finite sequence (u_{j})_{j∈[n]} of Dyck paths, where u_{1} = u and for j > 1 the Dyck path u_{j} is obtained from u_{j−1} by deleting its first peak.

Clearly, u_{j} ∈ D_{n−j+1} for every j ∈ [n]; if d(u_{j}) = (d_{i}^{j})_{i∈[n−j+1]}, by Lemma 6.3 we have that

d_{1}^{j} = d_{1}^{j−1} + d_{2}^{j−1} − 1, d_{i}^{j} = d_{i+1}^{j−1}

and

|Γ_{u_{j−1}}| = \binom{d_{1}^{j−1} + d_{2}^{j−1} − 1}{d_{2}^{j−1}}|Γ_{u_{j}}|  (9)

for every j ∈ [2, n].

It is easy to check that d_{2}^{j−1} = d_{j} and d_{1}^{j−1} + d_{2}^{j−1} − 1 = ∑_{i=1}^{j} d_{i} − j + 1, for every j ∈ [2, n].

Furthermore, using the previous equalities and applying formula (9) for every j ∈ [2, n], we obtain that

|Γ_{u}| = ∏_{j=2}^{n} \binom{∑_{i=1}^{j} d_{i} − j + 1}{d_{j}}|Γ_{u_{n}}|

= ∏_{j=1}^{n−1} \frac{∑_{i=1}^{j} d_{i} − j + 1}{d_{j}!}.

□

We note that since the family (Γ_{u})_{u∈D_{n}} is a partition of S_{n}, by the previous proposition we obtain an identity for the factorial number, i.e.,

∑_{d} ∏_{j=1}^{n−1} \frac{∑_{i=1}^{j} d_{i} − j + 1}{d_{j}!} = n!

where the sum is taken over all dominating sequences d = (d_{i})_{i∈[n]}.

References

[1] J. Bandlow and K. Killpatrick, An Area-to-Inv bijection between Dyck paths and 312avoiding permutations, Electronic J. Combin., 8 (1) (2001), #R40.

[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 (2005), 311–328.

[3] M. Barnabei and E. Pezzoli, Gian-Carlo Rota on combinatorics, in J. P. S. Kung, ed., Möbius Functions, Birkhauser, 1995, pp. 83–104.

[4] T. Brylawski, The lattice of integer partitions, Discrete Math. 6 (1973), 210–219.

[5] E. Deutsch, Dyck path enumeration, Discrete Math. 204 (1999), 167–202.

[6] P. H. Edelman, Zeta polynomials and the Möbius function, European J. Combin. 1 (1980), 335–340.

[7] P. Edelman and C. Greene, Balanced tableaux, Adv. in. Math. 63 (1987), 42–99.

[8] P. H. Edelman and R. Simion, Chains in the lattice of noncrossing partitions, Discrete Math. 126 (1994), 107–119.

[9] L. Ferrari and R. Pinzani, Lattices of lattice paths, J. Statist. Plann. Inference 135 (2005), 77–92.

[10] M. Fulmek, Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three, Adv. Appl. Math., 30 (2003), 607–632.

[11] G. Guilbaud and P. Rosenstiehl, Analyse algébrique d’un scrutin, Math. Sci. Hum. 4 (1963), 9–33.

[12] T. V. Narayana and G. E. Fulton, A note on the compositions of an integer, Canad. Math. Bull. 1 (1958), 169–173.

[13] G. Kreweras, Sur une classe de problèmes de dénombrement liés au treillis des partitions d’entiers, Cahiers du B.U.R.O. 6 (1965), 5–105.

[14] G. Kreweras and H. Niederhausen, Solution of an enumerative problem connected with lattice paths, European J. Combin. 2 (1981), 55–60.

[15] A. Panayotopoulos and A. Sapounakis, On the prime decomposition of Dyck words, J. Combin. Math. Combin. Comput. 40 (2002), 33–39.

[16] E. Pergola, Two bijections for the area of Dyck paths, Discrete Math. 241 (2001), 435–447.

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

[18] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences (2005), published electronically at http://www.research.att.com/˜ njas/sequences/.

[19] R. Stanley, On the number of reduced decompositions of elements of Coxeter groups, European J. Combin. 5 (1984), 359–372.

[20] R. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge University Press, 1997.

[21] D. Tamari, The algebra of bracketings and their enumeration, Nieuw. Arch. Wisk. 10 (1962), 131–146.

2000 Mathematics Subject Classification: Primary 06A07; Secondary 06D99. Keywords: Dyck paths, lattices, dominating sequences.

(Concerned with sequences \underline{A000045}, \underline{A000108}, \underline{A006327}, and \underline{A086581}.)

Received September 15 2005; revised version received April 18 2006. Published in Journal of Integer Sequences, May 19 2006.

Return to Journal of Integer Sequences home page.