Chains with Small Intervals in the Lattice of Binary Paths

I. Tasoulas, K. Manes, A. Sapounakis, and P. Tsikouras Department of Informatics University of Piraeus 18534 Piraeus Greece

                               jtas@unipi.gr
                              kmanes@unipi.gr
                             arissap@unipi.gr
                              pgtsik@unipi.gr

Abstract

We call an interval [x, y] in a poset small if y is the join of some elements covering x. In this paper, we study the chains of paths from a given arbitrary (binary) path P to the maximum path having only small intervals. More precisely, we obtain and use several formulas for the enumeration of chains having only small intervals and minimal length. For this, we introduce and study the notions of filling and degree of a path, giving in addition some related statistics.

1 Introduction

Let P_{n} be the set of all (binary) paths P of length |P | = n, i.e., lattice paths P = p_{1}p_{2} ⋯ p_{n}, starting from the origin of a pair of axes, where each step p_{i}, i ∈ [n], is either an upstep u = (1, 1) or a downstep d = (1, −1), connecting two consecutive points of the path. We denote by |P |_{u} (resp., |P |_{d}) the number of upsteps (resp., downsteps) of P. An ascent (resp., descent) of P is a maximal sequence of u’s (resp., d’s) in P. A peak (resp., valley) of the path is the last point of an ascent (resp., descent). Clearly, every peak (resp., valley) is either the middle point of an occurrence of ud (resp., du), or the endpoint of an occurrence of u (resp.,

d) at the end of the path. The height of a point of the path P is its y-coordinate. We denote by lv(P) (resp., hv(P)) the height of the lowest (resp., highest) valley of P. A low valley of P is a valley of P with height lv(P). We set P = ⋃_{n≥0} P_{n}, where P_{0} consists of only the empty path ε (the path which has no steps).

A Dyck path is a path that starts and ends at the same height and lies weakly above this height. In this paper, we will denote Dyck paths using lower case letters. The set of Dyck paths of length 2n is denoted by D_{n}, and we set D = ⋃_{n≥0} D_{n}, where D_{0} = {ε}. It is well known that |D_{n}| = C_{n}, where C_{n} = \frac{1}{n+1} \binom{2n}{n} is the n-th Catalan number, (sequence \underline{A000108} in the OEIS [10]). Every Dyck path of the form u^{n}d^{n}, where n ≥ 0, is called pyramid. A Dyck prefix (resp., Dyck suffix) is a path which is a prefix (resp., suffix) of a Dyck path. Every non-initial point of a Dyck prefix having height zero is called return. A prime Dyck path is a Dyck path with only one return point. It is well known that every non-empty Dyck path a is the product of prime Dyck paths, i.e., a = ua_{1}dua_{2}d ⋯ ua_{k}d, where a_{i} ∈ D, i ∈ [k]. Every Dyck prefix (resp., Dyck suffix) P can be uniquely decomposed in the form P = a_{0}ua_{1} ⋯ ua_{k} (resp., P = a_{0}da_{1} ⋯ da_{k}), where a_{i} ∈ D, i ∈ [0, k], k ≥ 0.

A natural (partial) ordering on P_{n} is defined via the geometric representation of the paths P, Q ∈ P_{n}, where P ≤ Q whenever P lies (weakly) below Q. Obviously, Q covers P whenever Q is obtained from P by turning exactly one valley of P into a peak. This ordering is better understood by considering the following alternative encoding of binary paths: Every P ∈ P_{n} can be described uniquely by the sequence (h_{i}(P))_{i∈[n]} of the heights of its points, so that P ≤ Q iff h_{i}(P) ≤ h_{i}(Q), i ∈ [n]. Then, the join and meet of P, Q are given by:

h_{i}(P ∨ Q) = max{h_{i}(P), h_{i}(Q)} and h_{i}(P ∧ Q) = min{h_{i}(P), h_{i}(Q)}.

From these relations, it follows immediately that the poset (P_{n}, ≤), or simply P_{n}, is a finite distributive lattice. Clearly, P_{n} is self-dual, with minimum and maximum elements the paths 0_{n} = d^{n} = \underbrace{dd ⋯ d}_{n times} and 1_{n} = u^{n} = \underbrace{uu ⋯ u}_{n times} respectively.

We note that the length of every maximal chain of the interval [P, Q], where P = p_{1}p_{2} ⋯ p_{n} and Q = q_{1}q_{2} ⋯ q_{n}, is equal to

l(P, Q) = \frac{1}{2} ∑_{i=1}^{n}(h_{i}(Q) − h_{i}(P)) = ∑_{i=1}^{n}(n − i + 1) · ([q_{i} = u] − [p_{i} = u]),

where [S] is the Iverson binary notation, i.e., for every proposition S, [S] = 1 if S is true, and 0 if S is false. Hence, the lattice P_{n} is graded with rank equal to \binom{n+1}{2}, and its rank function is

ρ(P) = \frac{1}{2} (∑_{i=1}^{n} h_{i}(P) + \binom{n + 1}{2}) = ∑_{i=1}^{n}(n − i + 1)[p_{i} = u].

This lattice appears in the literature in various equivalent forms (e.g., binary words [3, p. 92], subsets of [n] [5], permutations of [n] [12, p. 402], partitions of n into distinct parts [11], threshold graphs [7]). The sublattice D_{n} of Dyck paths has been studied by several authors (e.g., [2, 9]). Manes et al. [6] have recently presented a bijection between comparable pairs of paths of this lattice and Dyck prefixes of odd length.

Every path P can be decomposed as

P = u^{k_{1}}du^{k_{2}−k_{1}}du^{k_{3}−k_{2}}d ⋯ u^{k_{m}−k_{m−1}}du^{k_{m+1}−k_{m}},  (1)

where m = |P |_{d} and (k_{i})_{i∈[m+1]} is a non-decreasing sequence of integers. For i ∈ [m], the term k_{i} is the number of u’s before the i-th downstep of P and k_{m+1} = |P |_{u}. In the sequel, we will write P = (k_{i})_{i∈[m+1]} to denote the encoding of P by this sequence. This sequence is an extension of the notion of P -sequences defined by Pallo and Racca [8] for binary trees, and used by Germain and Pallo [2] in an equivalent form for Dyck paths, in order to prove that D_{n} is a distributive graded lattice. It is well known (e.g., see [4, Theorem 10.7.1]) that, using this encoding, the cardinality of every interval [P, Q] in P_{n} can be evaluated for every pair of paths P, Q when the two paths end at the same point (i.e., |P |_{d} = |Q|_{d}). Indeed, we have

|[P, Q]| = det_{i,j∈[m]} (\binom{μ_{i} − k_{j} + 1}{j − i + 1}) ,  (2)

where P = (k_{i}), Q = (μ_{i}), i ∈ [m + 1].

In order to evaluate the cardinality |[P, Q]| for two paths P, Q ∈ P_{n} that do not end at the same point (i.e., |Q|_{d} < |P |_{d}), we partition the interval [P, Q] into intervals [P_{i}, Q_{i}], i ∈ [0, |P |_{d} − |Q|_{d}], of paths ending at the same point, where P_{i} (resp., Q_{i}) is the path obtained by turning the last |P |_{d} − |Q|_{d} − i d’s of P into u’s (resp., the last i u’s of Q into d’s). Thus, we obtain

|[P, Q]| = ∑_{i=0}^{|P |_{d}−|Q|_{d}} |[P_{i}, Q_{i}]|.  (3)

In this work, we will mainly deal with the intervals [a, u^{|a|/2}d^{|a|/2}] and [P, u^{|P |}] for a ∈ D and P ∈ P, using the notation I(a) = |[a, u^{|a|/2}d^{|a|/2}]| and J(P) = |[P, u^{|P |}]|.

In this paper we study chains from a certain path P to the maximum path such that each member of the chain is the join of some covers of the previous element, i.e., chains with small intervals only. More formally, we say that a chain (or more generally a multichain) C : P_{0} ≤ P_{1} ≤ ⋯ ≤ P_{k} in P has (only) small intervals if P_{i} is obtained by turning some valleys of P_{i−1} into peaks, for every i ∈ [k].

In Section 2, we introduce and study the notions of filling and degree of a path P ∈ P_{n}, which will be used for the evaluation of the number f(P) of minimal P −1_{n} chains with small intervals. Apart from this, the filling and the degree are of independent interest and they are related to some interesting statistics. Although Sapounakis et al. [9] have already defined them for the sublattice D_{n} of Dyck paths, these new notions are not simple extensions of the old ones. Furthermore, we give a connection between minimal chains with small intervals and the powers of the Möbius function.

In Section 3, which is the main part of this paper, we evaluate the number f(P) for an arbitrary path P ∈ P_{n}. We do this by producing several formulas concerning special classes of paths, the combination of which completes the general case. Finally, we show that for specific classes of paths the map f is related to the zeta function.

2 Filling and degree of a path

For every path P ∈ P_{n} \ {1_{n}}, we call the join of all elements covering P filling of P, and we denote it by P̃. We also define ˜1_{n} = 1_{n}, for n ≥ 0. Obviously, the filling of P is obtained by turning every valley of P into a peak. For example, if P = dduudududdd, then P̃ = duduududddu.

We note that for every P, Q ∈ P_{n} with P ≤ Q < 1_{n} we have that P < P̃ ≤ Q̃.

It is easy to check that the interval [P, P̃] is isomorphic to the Boolean lattice B_{k}, where k is the number of valleys of P, for each P ∈ P_{n}.

In the following result we characterize the set of fillings of P_{n}. For the proof, we can easily show by induction, using the first valley decomposition, that a path P is a filling iff every valley of P is adjacent to a peak.

Proposition 1. A path P is a filling of some path in P iff P ≠ d and it satisfies all of the following conditions:

(i) P avoids d^{2}u^{2};

(ii) P does not start with du^{2};

(iii) P does not end with d^{2}.

In the next result, we use the above characterization in order to enumerate the fillings of P_{n}.

Proposition 2. The number a_{n} of fillings of P_{n} is the (n+1)-th tribonacci number (sequence \underline{A000213} in the OEIS [10]), given by

a_{n} = a_{n−1} + a_{n−2} + a_{n−3}, n ≥ 3,  (4)

and a_{0} = a_{1} = 1, a_{2} = 3.

Proof. Let P̃_{n} be the set of fillings in P_{n}. For n = 0, 1, 2 we have that P̃_{0} = {ε}, P̃_{1} = {u}, P̃_{2} = {uu, ud, du} and hence, |P̃_{0}| = |P̃_{1}| = 1 and |P̃_{2}| = 3. For n ≥ 3, P̃_{n} can be partitioned into the following three sets:

P̃_{n,1} = {P ∈ P̃_{n} : P starts with uu or dd},
P̃_{n,2} = {P ∈ P̃_{n} : P starts with ud},
P̃_{n,3} = {P ∈ P̃_{n} : P starts with du}.

By deleting the first step of each path of P̃_{n,1}, we can easily check that |P̃_{n,1}| = |P̃_{n−1}| =

a_{n−1}. Similarly, by deleting the first two (resp., three) steps of every path in P̃_{n,2} (resp., P̃_{n,3}), we obtain that |P̃_{n,2}| = |P̃_{n−2}| = a_{n−2} (resp., |P̃_{n,3}| = |P̃_{n−3}| = a_{n−3}), which gives relation (4).

Using the notion of the filling, we restate that a chain C : P_{0} ≤ P_{1} ≤ ⋯ ≤ P_{k} has small intervals iff P_{i} ≤ P̃_{i−1}, for every i ∈ [k].

For every path P ∈ P_{n} we define inductively a finite sequence of paths P^{(i)} in P_{n}, as follows: P^{(0)} = P, and P^{(i)} = { \atop P^{(i−1)}} whenever P^{(i−1)} ≠ 1_{n}. The number δ(P) for which P^{(δ(P))} = 1_{n} is called the degree of P. Clearly, the chain C : P_{0} = P^{(0)} ≤ P^{(1)} ≤ ⋯ ≤ P^{(δ(P))} = 1_{n} is a P − 1_{n} chain with small intervals and length δ(P). In the following result, we establish the minimality of δ(P) with respect to this property.

Proposition 3. The length of every chain from a path P ∈ P_{n} to 1_{n}, with small intervals is greater than or equal to δ(P).

Proof. Let C : P = P_{0} ≤ P_{1} ≤ ⋯ ≤ P_{k} = 1_{n} be a chain with P_{i} ≤ P̃_{i−1}, for every i ∈ [k]. For every j ∈ [δ(P)], we denote by i_{j} the greatest element of [k] such that P_{i_{j}−1} ≤ P^{(j−1)}. It follows that P^{(j−1)} < P_{i_{j}} ≤ { \atop P_{i_{j}−1}} ≤ P^{(j)}, so that every interval [P^{(j−1)}, P^{(j)}] contains an element of the chain C, giving automatically that δ(P) ≤ k.

We now come to the evaluation of δ(P) for every path P ∈ P_{n}. Clearly, we have δ(1_{n}) = 0, δ(0_{n}) = n − 1 and δ(P̃) = δ(P) − 1 for P ≠ 1_{n}. In the general case, we will see that δ(P) is closely related to lv(P) (the height of the lowest valley of P). Indeed, since P̃ is obtained by turning all valleys of P into peaks, it follows that the heights of their low valley points will differ by exactly one, i.e., lv(P̃) = lv(P) + 1, for P ≠ u^{|P |}, u^{|P |−1}d. It follows that

lv(P^{(i)}) = lv(P^{(i−1)}) + 1, 1 ≤ i ≤ δ(P) − 1.

Summing for all i, we obtain that

lv(P^{(δ(P)−1)}) = lv(P^{(0)}) + δ(P) − 1,

so that

|P | − 2 = lv(P) + δ(P) − 1,

giving the following result.

Lemma 4. For every path P ∈ P with P ≠ u^{|P |} the degree δ(P) is given by the formula

δ(P) = |P | − 1 − lv(P).

Proposition 5. The number of paths of P_{n} having degree k equals

\binom{min\{n, k\}}{⌊\frac{k+2}{2}⌋}

for 1 ≤ k ≤ 2n − 1, n ∈ ℕ^{∗}.

Proof. Let Δ_{n,k} be the set of all P ∈ P_{n} with δ(P) = k, and let M_{n,k}, N_{n,k} be its subsets of paths which start with u and d respectively.

We first prove that for n ≥ 2 we have that

|M_{n,k}| = |Δ_{n−1,k}| ,  (5)

and

|N_{n,k}| = \begin{cases}0, & if k < n; \\ |DP_{n−1}| , & if k = n; \\ |Δ_{n−1,k−2}| , & if k > n, \end{cases}  (6)

where DP_{n} is the set of Dyck prefixes of length n, which is well known that it is enumerated by the binomial \binom{n}{⌊n/2⌋}, (sequence \underline{A001405} in the OEIS [10]). Indeed, by deleting the first u from each path of M_{n,k} we obtain a path in Δ_{n−1,k}, giving a bijection between the sets M_{n,k} and Δ_{n−1,k} which justifies relation (5).

On the other hand, for the proof of relation (6), we consider the following cases:

(i) if k < n, then lv(P) ≥ 0, so that every P ∈ Δ_{n,k} starts with u, giving N_{n,k} = ∅.

(ii) k ≥ n; by deleting the first d from each path P ∈ N_{n,k} we obtain a path Q such that if k = n, then lv(P) = −1, or equivalently Q ∈ DP_{n−1}, whereas if k > n, then δ(Q) = k − 2, i.e., Q ∈ Δ_{n−1,k−2}; this gives a bijection between the sets N_{n,k} and DP_{n−1} if k = n, and between the sets N_{n,k} and Δ_{n−1,k−2} if k > n, justifying relation (6).

Clearly, the result holds for n = 1, whereas for n ≥ 2, using (5) and (6), we proceed by induction on n.

If k < n, then |Δ_{n,k}| = |Δ_{n−1,k}| = \binom{k}{⌊ \frac{k+2}{2} ⌋}.

If k = n, then |Δ_{n,n}| = |Δ_{n−1,n}| + |DP_{n−1}| = \binom{min\{n−1,n\}}{⌊ \frac{n+2}{2} ⌋} + \binom{n−1}{⌊ \frac{n−1}{2} ⌋} = \binom{n−1}{⌊ \frac{n+2}{2} ⌋} + \binom{n−1}{⌊ \frac{n−1}{2} ⌋} =

\binom{n}{⌊ \frac{n+2}{2} ⌋}.

If k > n, then |Δ_{n,k}| = |Δ_{n−1,k}| + |Δ_{n−1,k−2}| = \binom{n−1}{⌊ \frac{k+2}{2} ⌋} + \binom{n−1}{⌊ \frac{k}{2} ⌋} = \binom{n}{⌊ \frac{k+2}{2} ⌋}.

The minimal P − 1_{n} chains with small intervals which, according to Proposition 3, must have length equal to δ(P), are closely related to the powers of the Möbius function μ of P. Indeed, if f is the map on P defined by

f(P) = # P − 1_{n} chains of length δ(P) with small intervals,

then we have the following result.

Proposition 6. For every path P ∈ P we have that

μ^{k}(P, 1_{|P |}) = \begin{cases}0, & if k < δ(P); \\ (−1)^{l(P,1_{|P |})}f(P), & if k = δ(P). \end{cases}

Proof. Since P is a distributive locally finite lattice, it follows (e.g., see [1, Proposition 3.7, p. 90]) that the Möbius function of P has the following formula

μ(P, Q) = \begin{cases}(−1)^{l(P,Q)}, & if P ≤ Q ≤ P̃; \\ 0, & otherwise. \end{cases}

Furthermore, for k ≥ 1, we can easily check that

μ^{k}(P, Q) = ∑ ∏_{i=1}^{k} μ(P_{i−1}, P_{i}),

where the sum is taken over all multichains C : P = P_{0} ≤ P_{1} ≤ ⋯ ≤ P_{k} = Q of length k with small intervals, so that

μ^{k}(P, Q) = (−1)^{l(P,Q)} · (# P − Q multichains of length k with small intervals).

Then, for Q = 1_{|P |}, using Proposition 3, the required formula follows automatically.

3 Counting minimal chains with small intervals

In this section, we evaluate the number f(P) of minimal P − 1_{n} chains of length δ(P) with small intervals, for every path P ∈ P. We will use the notation P′ (resp., P^{∗}) for the path obtained by turning every low valley of P (resp., every valley of P, except the last one if P ends with d) into a peak.

Note that f(1_{n}) = 1, for every n ≥ 0. Clearly, we have f(uP) = f(P) for every P ∈ P, so that it is enough to evaluate f(P) when P is a Dyck prefix. In the following result, we give a recursive formula for the map f.

Proposition 7. For every path P ∈ P_{n} \ {1_{n}} we have that

f(P) = ∑_{Q∈[P′,P̃]} f(Q).

Proof. Let C : P = P_{0} ≤ P_{1} ≤ ⋯ ≤ P_{k} = 1_{n}, where k = δ(P), be a k-chain from P to 1_{n} with small intervals. Then, since P_{i−1} ≤ P_{i} ≤ P̃_{i−1} for every i ∈ [k], we can easily prove by induction that P_{i}^{(k−i)} = 1_{n}, i.e., δ(P_{i}) = k − i, for every i ∈ [k]. In particular, δ(P_{1}) = k − 1, which by Lemma 4 gives that lv(P_{1}) = lv(P) + 1. This shows that P_{1} ∈ [P′, P̃]. Moreover, if we delete P from C we obtain a (k − 1)-chain from P_{1} to 1_{n} with small intervals.

On the other hand, given Q ∈ [P′, P̃], by adding P in the beginning of every δ(Q)-chain from Q to 1_{n} with small intervals, we obtain a δ(P)-chain from P to 1_{n} with small intervals.

Thus, the result follows automatically by decomposing the δ(P)-chains from P to 1_{n} with small intervals according to their second member.

Corollary 8. For every P ∈ P we have that

f(P) = 1 iff all valleys of P have the same height.

Every path P ∈ P can be decomposed (not necessarily uniquely) as a product of a Dyck suffix P_{1} followed by a Dyck prefix P_{2}. In the following result we give a recursive formula of f that utilizes this decomposition.

Proposition 9. If P = P_{1}P_{2}, where P_{1} is a Dyck suffix and P_{2} is a Dyck prefix, then f(P) = f(P_{1})f(dP_{2}).

Proof. Without loss of generality we may assume that P starts with d, P_{1} ≠ d and P_{2} ≠ ε.

We use induction with respect to the length and to the (dual) partial order, i.e., assuming that the result holds for every path Q (that starts with d) for which |Q| < |P |, or |Q| = |P | and Q > P, we will prove that the result holds for P.

We decompose P_{1}, P_{2} as follows:

P_{1} = R_{1}ad, P_{2} = ubR_{2},

where R_{1} (resp., R_{2}) is a Dyck suffix (resp., Dyck prefix), a (resp., b) may be either empty, or a path that starts with d (resp., ends with u), ends at height 0 and it is bounded by the line y = −1 (see Figure 1).

P = R1 ab R2 y = −1

Figure 1: The decomposition of P = P_{1}P_{2}

Then, we have that

P′_{1} = R_{1}a′u,  (dP_{2})′ = udb′R_{2},  P′ = R_{1}a′udb′R_{2},
P̃_{1} = R_{1}^{∗}a^{∗}u,  d̃P_{2} = ud b̃ R̃_{2},  P̃ = R_{1}^{∗}a^{∗}ud b̃ R̃_{2}.

It follows that every Q ∈ [P′, P̃] can be uniquely decomposed as

Q = Q_{1}udQ_{2},

where Q_{1} ∈ [R_{1}a′, R_{1}^{∗}a^{∗}], Q_{2} ∈ [b′R_{2}, b̃R̃_{2}]. Clearly, since Q_{1} is a Dyck suffix and Q_{2} is a Dyck prefix with Q > P and |Q_{1}|, |Q_{2}| ≤ |P | − 2, we have that

f(Q) = f(Q_{1}udQ_{2}) = f(Q_{1}ud)f(dQ_{2}) = f(Q_{1})f(dud)f(udQ_{2})
= f(Q_{1})f(du)f(udQ_{2}) = f(Q_{1}u)f(udQ_{2}),

and therefore

f(P) = ∑_{Q∈[P′,P̃]} f(Q) = ∑_{Q_{2}∈[b′R_{2},b̃R̃_{2}]^{Q_{1}∈[R_{1}a′,R^{∗}_{1}a^{∗}]}} f(Q_{1}u)f(udQ_{2})

= ∑_{Q_{1}u∈[R_{1}a′u,R_{1}^{∗}a^{∗}u]} f(Q_{1}u) ∑_{udQ_{2}∈[udb′R_{2},udb̃R̃_{2}]} f(udQ_{2})

= ∑_{Q_{1}u∈[P′_{1},P̃_{1}]} f(Q_{1}u) ∑_{udQ_{2}∈[(dP_{2})′,d̃P_{2}]} f(udQ_{2})

= f(P_{1})f(dP_{2}),

completing the proof.

Corollary 10. If P is a Dyck prefix with at least one return point, then f(dP) = f(P).

Proof. We use induction with respect to the length of the path. Clearly, since P has at least one return point, it can be written as P = uadR, where a ∈ D and R is a Dyck prefix. Then, using Propositions 7, 9 and the induction hypothesis, we have that

f(duad) = ∑_{Q∈[udau,uda^{∗}u]} f(Q) = ∑_{b∈[a,a^{∗}]} f(udbu) = ∑_{b∈[a,a^{∗}]} f(udb)f(du)

= ∑_{b∈[a,a^{∗}]} f(ub)f(du) = ∑_{b∈[a,a^{∗}]} f(ubu) = ∑_{Q∈[uau,ua^{∗}u]} f(Q) = f(uad).

It follows that f(dP) = f(duad)f(dR) = f(uad)f(dR) = f(P).

From the two previous results it follows that the map f on the set of Dyck paths is multiplicative. Moreover, since every Dyck prefix can be uniquely decomposed in the form aQ, where a = ε or a = ua_{1}d ⋯ ua_{k}d, a_{i} ∈ D, i ∈ [k] and Q = ε or Q = uP for some Dyck prefix P, for the evaluation of f it is enough to restrict ourselves to the two cases f(uad) and f(duP), where a ∈ D and P is a Dyck prefix. For this, we introduce a new kind of multichains for Dyck paths, based on the heights of the valleys of the paths.

We say that a multichain of Dyck paths C : σ_{0} ≤ σ_{1} ≤ ⋯ ≤ σ_{h}, where h = hv(σ_{0}) (the height of the highest valley of σ_{0}) is of type v iff for every j ∈ [h] the paths σ_{j}, σ_{j−1} have the same valleys at every height at most h − j.

Example 11. The multichain C : σ_{0} ≤ σ_{1} ≤ σ_{2} ≤ σ_{3} with

σ_{0} = u^{2}du^{2}du^{2}d^{2}u^{2}d^{3}ud^{2}u^{3}du^{2}dud^{2}udud^{3},
σ_{1} = u^{2}du^{2}du^{2}d^{2}u^{2}d^{3}ud^{2}u^{3}du^{3}d^{3}udud^{3},
σ_{2} = u^{2}du^{4}d^{2}udud^{3}ud^{2}u^{5}du^{2}d^{4}ud^{3},
σ_{3} = u^{4}du^{2}d^{2}ududud^{4}u^{6}dud^{4}ud^{3}

is of type v, whereas the multichain σ_{0} ≤ σ_{1} ≤ σ_{2} ≤ s with s = u^{5}du^{3}d^{3}ud^{3}udu^{4}dudud^{3}ud^{4} is not of type v (see Figure 2).

\begin{matrix}σ_{0} \\ σ_{1} \\ σ_{2} \\ σ_{3} \\ s \end{matrix}

Figure 2: The multichain of example 11

For a, s ∈ D with a ≤ s we denote by v(a, s) the number of all a − s multichains of type v. Clearly, we have v(a, s) ≠ 0 iff a, s have exactly the same low valleys. Furthermore, we can easily check that

v(ua_{1}d ⋯ ua_{k}d, us_{1}d ⋯ us_{k}d) = ∏_{i=1}^{k} v(ua_{i}d, us_{i}d)

when a_{i} ≤ s_{i} for every i ∈ [k], and that

v(uad, usd) = ∑_{t≤s} v(a, t).  (7)

In the following Proposition, we give an alternative formula of v on the pairs of prime Dyck paths, which will be used in the sequel.

Proposition 12. For every a, s ∈ D with a ≤ s we have that

v(uad, usd) = ∑_{w∈[a,a^{∗}]} v(w, s).

Proof. In view of formula (7), it is enough to construct a bijection between the set of a − t multichains of type v for all t ≤ s, and the set of w−s multichains of type v for all w ∈ [a, a^{∗}].

A key property of Dyck paths that we will use throughout the proof is the following: If two Dyck paths t, r of length 2n have the same valleys for every height at most j, then they coincide up to height j + 1, and if t ≤ r then every valley of r at height j + 1 is necessarily also a valley of t. Note also that given a multichain σ_{0} ≤ σ_{1} ≤ ⋯ ≤ σ_{h} of type v and if 0 ≤ j ≤ i ≤ h, then σ_{j}, σ_{i} have the same valleys at every height at most h − i.

In order to exhibit the required bijection, for a multichain a = σ_{0} ≤ σ_{1} ≤ ⋯ ≤ σ_{h} = t of type v with t ≤ s, we set σ_{h+1} = s and we first construct a sequence of Dyck paths τ_{i}, i ∈ [0, h + 1], where τ_{i} is the Dyck path obtained by turning into peaks all valleys of σ_{i} at height j that are not also valleys of σ_{h+1−j}, for every j ≤ h − i. Clearly, we have τ_{0} ∈ [a, a^{∗}] and τ_{h+1} = s.

Furthermore, τ_{i−1} ≤ τ_{i} for every i ∈ [h + 1]. Indeed, all valleys of σ_{i−1}, σ_{i} at height j ≤ h − i which turn into peaks for the construction of τ_{i−1}, τ_{i} are the same, whereas the valleys of σ_{i−1} at height h − i + 1 that turn into peaks are not valleys of σ_{h+1−(h−i+1)} = σ_{i}, so that σ_{i} (let alone τ_{i}) passes at least two units above these valleys and hence, τ_{i−1} is weakly below τ_{i}.

Set w = τ_{0}; hence, w ∈ [a, a^{∗}]. Moreover, τ_{h+1−k} = w, where k = hv(w). Indeed, clearly σ_{0}, σ_{h+1−k} have the same valleys at every height at most k − 1. It follows that the valleys of τ_{0}, τ_{h+1−k} that are either at height at most k − 1, or at height k and have been created by the above construction are the same. Furthermore, if there exists a valley of τ_{0} at height k that has not been created by the construction, then this valley is also a valley of both σ_{0}, σ_{h+1−k} so that it is also a valley of τ_{h+1−k}. Thus, since the height of the highest valley of τ_{0} is k, the paths τ_{0}, τ_{h+1−k} have the same valleys, which gives τ_{0} = τ_{h+1−k}.

We define s_{i} = τ_{i+(h+1−k)}, i ∈ [0, k]. It is easy to check that w = s_{0} ≤ s_{1} ≤ ⋯ ≤ s_{k} = s is a multichain of type v.

For the converse we note that the peaks of τ_{i} at height j + 2 generated according to the above construction from σ_{i} for j ≤ h − i, are exactly these peaks of τ_{i} that are peaks of τ_{0} and not of a.

Now, for a multichain w = s_{0} ≤ s_{1} ≤ ⋯ ≤ s_{k} = s with hv(w) = k, we define a multichain

w = τ_{0} ≤ τ_{1} ≤ ⋯ ≤ τ_{h+1} = s

with

τ_{i} = \begin{cases}s_{0}, & i ∈ [0, h + 1 − k]; \\ s_{i−(h+1−k)}, & i ∈ [h + 2 − k, h + 1]. \end{cases}

Finally, we define σ′_{i}, i ∈ [0, h] to be the Dyck path obtained by turning all peaks of τ_{i} at height j + 2 that are also peaks of w but not peaks of a into valleys, for every j ≤ h − i.

Clearly, we have σ′_{0} = a and σ′_{h} ≤ s.

Furthermore, we can analogously prove that a = σ′_{0} ≤ σ′_{1} ≤ ⋯ ≤ σ′_{h} ≤ s is a multichain of type v and σ_{i} = σ′_{i} for every i ∈ [0, h].

In order to illustrate the bijection in the proof of Proposition 12 we give the following example.

Example 13. Let a = u^{2}du^{2}du^{2}d^{2}u^{2}d^{3}ud^{2}u^{3}du^{2}dud^{2}udud^{3}, t = u^{4}du^{2}d^{2}ududud^{4}u^{6}dud^{4}ud^{3} and s = u^{5}du^{3}d^{3}ud^{3}udu^{4}dudud^{3}ud^{4}. For the multichain a = σ_{0} ≤ σ_{1} ≤ σ_{2} ≤ σ_{3} = t of Example 11 (see Figure 2), using the construction in the proof of Proposition 12, we have that

w = τ_{0} = τ_{1} = u^{3}du^{2}dududud^{2}ud^{2}udu^{3}du^{2}d^{2}ud^{2}ud^{3},
τ_{2} = u^{3}du^{3}d^{2}udud^{2}ud^{2}udu^{4}du^{2}d^{4}ud^{3},
τ_{3} = u^{4}du^{2}d^{2}ududud^{3}udu^{5}dud^{4}ud^{3}

and

τ_{4} = s.

Then, the multichain w = s_{0} ≤ s_{1} ≤ s_{2} ≤ s_{3} = s, where s_{i} = τ_{i+1}, i ∈ [3], is the corresponding w − s multichain of type v (see Figure 3).

\begin{matrix}τ_{0} = τ_{1} \\ τ_{2} \\ τ_{3} \\ s = τ_{4} \end{matrix}

Figure 3: The multichain produced in Example 13 from the multichain of type v of Example 11

In the following result, we give a formula for the evaluation of f on prime Dyck paths. In the proof, we use the following obvious consequence of Proposition 7:

f(uad) = ∑_{w∈[a,a^{∗}]} f(w), for every Dyck path a.  (8)

Proposition 14. For every Dyck path a ∈ D we have that

f(uad) = ∑_{s≥a} v(a, s)I(s).  (9)

Proof. We prove the required formula by induction on the length of a.

Clearly, it holds for a = ε. Now, let a = ua_{1}dua_{2}d ⋯ ua_{k}d, where a_{i} ∈ D, for i ∈ [k], k ∈ ℕ^{∗}. Each w ∈ [a, a^{∗}] has a common low valley with a. Assume that the r-th low valley of a, r ∈ [k], is the leftmost such valley. Then, w = uw_{1}udw_{2} ⋯ udw_{r}dβ, where w_{i} ∈ [a_{i}, a_{i}^{∗}], for i ∈ [r], β ∈ [b_{r}, b_{r}^{∗}] and b_{r} = ua_{r+1}dua_{r+2}d ⋯ ua_{k}d, r ∈ [k]; (note that b_{k} = ε). Then, using the induction hypothesis, equation (8) and Proposition 12, we have that

f(uad) = ∑_{w∈[a,a^{∗}]} f(w) = ∑_{r=1}^{k} ∑_{i∈[r]^{w_{i}∈[a_{i},a^{∗}_{i}]}} f(uw_{1}udw_{2} ⋯ udw_{r}d) ∑_{β∈[b_{r},b_{r}^{∗}]} f(β)

= ∑_{r=1}^{k} ∑_{i∈[r]^{w_{i}∈[a_{i},a^{∗}_{i}]}} ∑_{s≥w_{1}udw_{2}···udw_{r}} v(w_{1}udw_{2} ⋯ udw_{r}, s)I(s)f(ub_{r}d)

= ∑_{r=1}^{k} ∑_{i∈[r]^{w_{i}∈[a_{i},a^{∗}_{i}]}} ∑_{i∈[r]^{s_{i}≥w_{i}}} (∏_{i=1}^{r} v(w_{i}, s_{i})) I(s_{1}uds_{2} ⋯ uds_{r})f(ub_{r}d)

= ∑_{r=1}^{k} ∑_{i∈[r]^{s_{i}≥a_{i}}} (∏_{i=1}^{r} ∑_{w_{i}∈[a_{i},a_{i}^{∗}]} v(w_{i}, s_{i})) I(s_{1}uds_{2} ⋯ uds_{r})f(ub_{r}d)

= ∑_{r=1}^{k} ∑_{i∈[r]^{s_{i}≥a_{i}}} (∏_{i=1}^{r} v(ua_{i}d, us_{i}d)) I(s_{1}uds_{2} ⋯ uds_{r})f(ub_{r}d).  (10)

On the other hand, given a path s ∈ D with s ≥ a, having the same low valleys with a, we set s = us_{1}dus_{2}d ⋯ us_{k}d, where s_{i} ∈ D and s_{i} ≥ a_{i} for every i ∈ [k]. Clearly, as before, we can decompose every path c ∈ [s, u^{|s|/2}d^{|s|/2}] with respect to the leftmost common low valley with a, i.e., c = uϕdχ where ϕ, χ ∈ D, ϕ ≥ s_{1}uds_{2} ⋯ uds_{r} and χ ≥ us_{r+1}dus_{r+2}d ⋯ us_{k}d, for some r ∈ [k].

It follows that

∑_{s≥a} v(a, s)I(s) = ∑_{r=1}^{k} ∑_{i∈[k]^{s_{i}≥a_{i}}} (∏_{i=1}^{k} v(ua_{i}d, us_{i}d)) I(s_{1}uds_{2} ⋯ uds_{r})I(us_{r+1}dus_{r+2}d ⋯ us_{k}d)

= ∑_{r=1}^{k} ∑_{i∈[r]^{s_{i}≥a_{i}}} (∏_{i=1}^{r} v(ua_{i}d, us_{i}d)) I(s_{1}uds_{2} ⋯ uds_{r}) ∑_{t≥b_{r}} v(b_{r}, t)I(t)

= ∑_{r=1}^{k} ∑_{i∈[r]^{s_{i}≥a_{i}}} (∏_{i=1}^{r} v(ua_{i}d, us_{i}d)) I(s_{1}uds_{2} ⋯ uds_{r})f(ub_{r}d).  (11)

The required formula follows from (10) and (11).

Example 15. For a = u^{2}d^{2}u^{3}dudud^{3}, from formula (9) we have that f(u^{3}d^{2}u^{3}dudud^{4}) =

f(uad) = ∑_{s≥a} v(a, s)I(s).

Clearly, there are five s ≥ a which have the same low valleys with a, namely: s_{i} = u^{2}d^{2}a_{i}, i ∈ [5] where a_{1} = u^{3}dudud^{3}, a_{2} = u^{4}d^{2}ud^{3}, a_{3} = u^{3}du^{2}d^{4}, a_{4} = u^{4}dud^{4} and a_{5} = u^{5}d^{5}.

We can easily check by the definition of v that v(a, s_{1}) = 1, v(a, s_{2}) = v(a, s_{3}) = 2, v(a, s_{4}) = 4 and v(a, s_{5}) = 5.

Furthermore, using formula (2) we have that

I(s_{1}) = | [(2, 2, 5, 6, 7, 7, 7), (7, 7, 7, 7, 7, 7, 7)] | = | [(2, 2, 5, 6), (7, 7, 7, 7)] |

= |\begin{matrix}6 & \binom{6}{2} & \binom{3}{3} & \binom{2}{4} \\ 1 & 6 & \binom{3}{2} & \binom{2}{3} \\ 0 & 1 & 3 & \binom{2}{2} \\ 0 & 0 & 1 & 2 \end{matrix}| = 71,

I(s_{2}) = | [(2, 2, 6, 6, 7, 7, 7), (7, 7, 7, 7, 7, 7, 7)] | = | [(2, 2, 6, 6), (7, 7, 7, 7)] |

= |\begin{matrix}6 & \binom{6}{2} & \binom{2}{3} & \binom{2}{4} \\ 1 & 6 & \binom{2}{2} & \binom{2}{3} \\ 0 & 1 & 2 & \binom{2}{2} \\ 0 & 0 & 1 & 2 \end{matrix}| = 51,

I(s_{3}) = | [(2, 2, 5, 7, 7, 7, 7), (7, 7, 7, 7, 7, 7, 7)] | = | [(2, 2, 5), (7, 7, 7)] | = |\begin{matrix}6 & \binom{6}{2} & \binom{3}{3} \\ 1 & 6 & \binom{3}{2} \\ 0 & 1 & 3 \end{matrix}| = 46,

I(s_{4}) = | [(2, 2, 6, 7, 7, 7, 7), (7, 7, 7, 7, 7, 7, 7)] | = | [(2, 2, 6), (7, 7, 7)] | = |\begin{matrix}6 & \binom{6}{2} & \binom{2}{3} \\ 1 & 6 & \binom{2}{2} \\ 0 & 1 & 2 \end{matrix}| = 36,

I(s_{5}) = | [(2, 2, 7, 7, 7, 7, 7), (7, 7, 7, 7, 7, 7, 7)] | = | [(2, 2), (7, 7)] | = |\begin{matrix}6 & \binom{6}{2} \\ 1 & 6 \end{matrix}| = 21.

From the above we obtain that f(u^{3}d^{2}u^{3}dudud^{4}) = 514.

In the following result we show that, for specific Dyck paths, the map f is related to the zeta function. We recall that the zeta function of a poset X is given by the formula

ζ(x, y) = \begin{cases}1, & x ≤ y; \\ 0, & otherwise, \end{cases}

for x, y ∈ X. Moreover, it is well known (e.g., see [12, p. 263]) that ζ^{k}(x, y) counts the number of x − y multichains in X of length k, for k ≥ 0.

Corollary 16. If a is a product of pyramids, then

f(u^{k}ad^{k}) = ζ^{k+1}(a, u^{|a|/2}d^{|a|/2}),

for every k ≥ 0.

Proof. For k = 0 the result obviously holds.

We now prove that for k ≥ 0 we have that

v(u^{k}ad^{k}, u^{k}sd^{k}) = ζ^{k}(a, s).

Indeed, we can easily see that hv(u^{k}ad^{k}) = k, and that every k-multichain from u^{k}ad^{k} to u^{k}sd^{k} of type v is of the form

u^{k}ad^{k} = u^{k}σ_{0}d^{k} ≤ ⋯ ≤ u^{k}σ_{k−1}d^{k} ≤ u^{k}σ_{k}d^{k} = u^{k}sd^{k},

producing the a − s multichain

a = σ_{0} ≤ ⋯ ≤ σ_{k−1} ≤ σ_{k} = s.

Then, for k ≥ 1, by Proposition 14 we have that

f(u^{k}ad^{k}) = ∑_{s≥u^{k−1}ad^{k−1}} v(u^{k−1}ad^{k−1}, s)I(s)

= ∑_{s≥a} v(u^{k−1}ad^{k−1}, u^{k−1}sd^{k−1})I(s)

= ∑_{s≥a} ζ^{k−1}(a, s)I(s) = ζ^{k+1}(a, u^{|a|/2}d^{|a|/2}).

Since f is multiplicative on D, by using formula (9) we can evaluate f for every Dyck path. For Dyck prefixes that are not Dyck paths, it is enough to evaluate f(duP), where P is a Dyck prefix. We achieve this in formula (13) of the following Proposition, the proof of which, although it shares some common ideas with the proof of formula (9), it is much more complicated. The difficulty lies in the fact that it is not possible to prove (13) directly by induction, so that we introduce and prove the more general equality (14) which concerns a pair of paths (P, R) where a lexicographic induction applies. We also note that in this proof, we use several times the following obvious consequence of Proposition 7:

f(duP) = ∑_{Q∈[P,P̃]} f(dQ), for every Dyck prefix P .  (12)

Proposition 17. For every Dyck prefix P = a_{0}ua_{1} ⋯ ua_{k}, k ≥ 0, a_{i} ∈ D, i ∈ [0, k], we have that

f(duP) = ∑ ∏_{i=0}^{k} v(a_{i}, s_{i})J(s_{0}V_{1}),  (13)

where the sum is taken over all sequences (s_{i}), i ∈ [0, k], of Dyck paths with s_{i} ≥ a_{i}, and over all sequences of Dyck prefixes (V_{i}), i ∈ [k + 1], with V_{i} ≥ us_{i}V_{i+1}, i ∈ [k], and V_{k+1} = ε.

Proof. Let a Dyck prefix R = b_{0}ub_{1} ⋯ ub_{λ}, λ ≥ 0, b_{i} ∈ D, i ∈ [0, λ].

For the pair (P, R) we consider the equality

∑_{Q∈[R,R̃]} f(duP Q) = ∑ ∏_{i=0}^{k} v(a_{i}, s_{i}) ∏_{i=0}^{λ} v(b_{i}, t_{i})J(s_{0}V_{1}),  (14)

where the sum is taken over all sequences (s_{i}), i ∈ [0, k], (t_{i}), i ∈ [0, λ], of Dyck paths with s_{i} ≥ a_{i} and t_{i} ≥ b_{i}, and over all sequences of Dyck prefixes (V_{i}), i ∈ [k + λ + 2], with V_{i} ≥ us_{i}V_{i+1}, i ∈ [k], V_{k+1} ≥ t_{0}V_{k+2}, V_{k+i+1} ≥ ut_{i}V_{k+i+2}, i ∈ [λ], and V_{k+λ+2} = ε.

Clearly, formula (13) is a special case of equality (14) for R = ε.

We prove equality (14) by induction. More precisely, assuming that (14) holds for every pair (P_{1}, R_{1}) with either |P_{1}| + |R_{1}| < |P | + |R|, or |P_{1}| + |R_{1}| = |P | + |R| with |R_{1}| < |R|, we prove that (14) also holds for the pair (P, R).

We restrict ourselves to the case P ∉ D, since the case P = a_{0} ∈ D is similar and easier to prove. We consider the following cases:

1. Assume that R = u^{λ}.

We first note that if λ > 0, then by the induction hypothesis we deduce that equality (14) holds for the pair (P u^{λ}, ε), from which we can easily obtain that (14) holds also for the pair (P, u^{λ}). Thus, we restrict ourselves to the case R = ε, so that now it is enough to prove formula (13).

We set H = a_{1}ua_{2} ⋯ ua_{k} and we consider two subcases:

1(i). Assume that a_{0} = ε, i.e., P = uH. Then, by formula (12), and by equality (14) for the pair (ε, H), it follows that

f(duP) = ∑_{Q∈[H,H̃]} f(duQ) = ∑ ∏_{i=1}^{k} v(a_{i}, s_{i})J(V_{1}),

where the sum it taken over all sequences (s_{i}), i ∈ [k], of Dyck paths with s_{i} ≥ a_{i} and over all sequences (V_{i}), i ∈ [k + 1] with V_{1} ≥ s_{1}V_{2}, V_{i} ≥ us_{i}V_{i+1}, i ∈ [2, k], and V_{k+1} = ε. Since J(V_{1}) = J(uV_{1}), we can replace V_{1} by uV_{1}, thus verifying formula (13).

1(ii). Assume that a_{0} ≠ ε. We set a_{0} = uγ_{1}duγ_{2}d ⋯ uγ_{ν}d and δ_{r} = uγ_{r+1}duγ_{r+2}d ⋯ uγ_{ν}d, ν ∈ ℕ^{∗}, r ∈ [ν].

Every Q ∈ [P, P̃] can be decomposed according to the leftmost common low valley with P (see Figure 4).

\begin{matrix}γ_{1} \\ γ_{2} \\ γ_{r} \\ γ_{ν} \\ H \\ P = \end{matrix}

Q = w1 w2 wr Q^{1}

or

Q = w_{1} w_{2} w_{ν} Q_{2} w_{i} ∈ [γ_{i}, γ_{i}^{∗}], i ∈ [ν], Q_{1} ∈ [δ_{r}uH, { \atop δ_{r}uH}], Q_{2} ∈ [H, H̃].

Figure 4: The decomposition of Q ∈ [P, P̃] according to the leftmost common low valley of P, Q.

Using formula (12) and the above decomposition we have that

f(duP) = ∑_{Q∈[P,P̃]} f(dQ)

\begin{matrix}= ∑_{r=1}^{ν} ∑_{i∈[r]^{w_{i}∈[γ_{i},γ^{∗}_{i}]}} ∑_{Q∈[δ_{r}uH,{ \atop δ_{r}uH}]} f(duw_{1}ud ⋯ w_{r−1}udw_{r}dQ) \\ + ∑_{i∈[ν]^{w_{i}∈[γ_{i},γ^{∗}_{i}]}} ∑_{Q∈[H,H̃]} f(duw_{1}ud ⋯ w_{ν}udQ) \end{matrix}

\begin{matrix}= ∑_{r=1}^{ν} ∑_{i∈[r]^{w_{i}∈[γ_{i},γ^{∗}_{i}]}} f(uw_{1}ud ⋯ w_{r−1}udw_{r}d) ∑_{Q∈[δ_{r}uH,{ \atop δ_{r}uH}]} f(dQ) \\ + ∑_{i∈[ν]^{w_{i}∈[γ_{i},γ^{∗}_{i}]}} ∑_{Q∈[H,H̃]} f(duw_{1}ud ⋯ w_{ν}udQ). \end{matrix}  (15)

Then, using Proposition 14, and equality (14) for the pair (w_{1}ud ⋯ w_{ν}ud, H) we have that

f(duP) = ∑_{r=1}^{ν} ∑_{i∈[r]^{w_{i}∈[γ_{i},γ^{∗}_{i}]}} ∑_{i∈[r]^{t_{i}≥w_{i}}} ∏_{i=1}^{r} v(w_{i}, t_{i})I(t_{1}ud ⋯ t_{r−1}udt_{r})f(duδ_{r}uH)

+ ∑_{w_{i}∈[γ_{i},γ_{i}^{∗}]} ∑_{i∈[ν]^{t_{i}≥w_{i}}} ∑_{i∈[k]^{s_{i}≥a_{i}}} ∑_{\begin{matrix}W_{1}≥s_{1}V_{2} \\ V_{i}≥us_{i}V_{i+1},i∈[2,k] \\ V_{k+1}=ε \end{matrix}} ∏_{i=1}^{ν} v(w_{i}, t_{i}) ∏_{i=1}^{k} v(a_{i}, s_{i})J(t_{1}ud ⋯ t_{ν}udW_{1})

= ∑_{r=1}^{ν} ∑_{i∈[r]^{t_{i}≥γ_{i}}} (∏_{i=1}^{r} ∑_{i∈[r]^{w_{i}∈[γ_{i},γ^{∗}_{i}]}} v(w_{i}, t_{i})) I(t_{1}ud ⋯ t_{r−1}udt_{r})f(duδ_{r}uH)

+ ∑_{s_{i}≥a_{i},i∈[k]^{t_{i}≥γ_{i},i∈[ν]}} ∑_{\begin{matrix}W_{1}≥s_{1}V_{2} \\ V_{i}≥us_{i}V_{i+1},i∈[2,k] \\ V_{k+1}=ε \end{matrix}} ∏_{i=1}^{k} v(a_{i}, s_{i}) (∏_{i=1}^{ν} ∑_{i∈[ν]^{w_{i}∈[γ_{i},γ^{∗}_{i}]}} v(w_{i}, t_{i})) J(t_{1}ud ⋯ t_{ν}udW_{1}).

Finally, using formula (13) for the path δ_{r}uH and Proposition 12, we obtain that f(duP)

= ∑_{r=1}^{ν} ∑_{i∈[r]^{t_{i}≥γ_{i}}} ∏_{i=1}^{r} v(uγ_{i}d, ut_{i}d)I(t_{1}ud ⋯ t_{r−1}udt_{r})·

∑_{s_{i}≥a_{i},i∈[k]^{t_{i}≥γ_{i},i∈[r+1,ν]}} ∑_{V_{k+1}=ε^{V_{i}≥us_{i}V_{i+1},i∈[k]}} v(δ_{r}, ut_{r+1}d ⋯ ut_{ν}d) ∏_{i=1}^{k} v(a_{i}, s_{i})J(ut_{r+1}d ⋯ ut_{ν}dV_{1})

+ ∑_{s_{i}≥a_{i},i∈[k]^{t_{i}≥γ_{i},i∈[ν]}} ∑_{\begin{matrix}W_{1}≥s_{1}V_{2} \\ V_{i}≥us_{i}V_{i+1},i∈[2,k] \\ V_{k+1}=ε \end{matrix}} ∏_{i=1}^{k} v(a_{i}, s_{i}) ∏_{i=1}^{ν} v(uγ_{i}d, ut_{i}d)J(t_{1}ud ⋯ t_{ν}udW_{1})

\begin{matrix}= ∑_{\begin{matrix}s_{i}≥a_{i},i∈[0,k] \\ s_{0}=ut_{1}d···ut_{ν}d \end{matrix}} ∏_{i=0}^{k} v(a_{i}, s_{i})· \\ ∑_{\begin{matrix}W_{1}≥s_{1}V_{2} \\ V_{i}≥us_{i}V_{i+1}, \\ i∈[2,k] \\ V_{k+1}=ε \end{matrix}} (∑_{r=1}^{ν} I(t_{1}ud ⋯ t_{r−1}udt_{r})J(ut_{r+1}d ⋯ ut_{ν}duW_{1}) + J(t_{1}ud ⋯ t_{ν}udW_{1})) . \end{matrix} (16)

Clearly, since the number ∑_{r=1}^{ν} I(t_{1}ud ⋯ t_{r−1}udt_{r})J(ut_{r+1}d ⋯ ut_{ν}duW_{1}) (resp., the number

J(t_{1}ud ⋯ t_{ν}udW_{1})) counts the set of all paths greater than or equal to s_{0}uW_{1} that have (resp., do not have) low valleys we obtain that

∑_{r=1}^{ν} I(t_{1}ud ⋯ t_{r−1}udt_{r})J(ut_{r+1}d ⋯ ut_{ν}duW_{1}) + J(t_{1}ud ⋯ t_{ν}udW_{1}) = J(s_{0}uW_{1}),

so that, by setting V_{1} = uW_{1} in formula (16), we obtain (13).

2. Assume that R ≠ u^{λ}. Then, we set R = u^{μ}b_{μ}ub_{μ+1} ⋯ ub_{λ}, where μ is the least integer such that b_{μ} ≠ ε.

It is enough to restrict ourselves to the case where μ = 0 (i.e., b_{0} ≠ ε), since the general case follows easily by applying equality (14) for the pair (P u^{μ}, b_{μ}ub_{μ+1} ⋯ ub_{λ}).

Furthermore, we can restrict ourselves to the case where R ∉ D (i.e., λ > 0), since the case where R ∈ D is similar and easier to prove.

Set b_{0} = uη_{1}duη_{2}d ⋯ uη_{ξ}d, θ_{r} = uη_{r+1}duη_{r+2}d ⋯ uη_{ξ}d, ξ ∈ ℕ^{∗}, r ∈ [ξ], and T = b_{1}ub_{2} ⋯ ub_{λ}.

By decomposing each Q ∈ [R, R̃] according to the leftmost low common valley with R, as before we have that

∑_{Q∈[R,R̃]} f(duP Q) = ∑_{r=1}^{ξ} ∑_{i∈[r]^{w_{i}∈[η_{i},η^{∗}_{i}]}} ∑_{Q∈[θ_{r}uT,{ \atop θ_{r}uT}]} f(duP uw_{1}ud ⋯ w_{r−1}udw_{r}dQ)

+ ∑_{i∈[ξ]^{w_{i}∈[η_{i},η^{∗}_{i}]}} ∑_{Q∈[T,T̃]} f(duP uw_{1}ud ⋯ w_{ξ}udQ).  (17)

It is enough to prove that the first (resp., second) sum on the RHS of the above equality is equal to the part of the second sum in equality (14) which has (resp., does not have) low valleys.

Clearly, by applying (14) for the pair (P uw_{1}ud ⋯ w_{r−1}udw_{r}, θ_{r}uT) for r ∈ [ξ], we have that

\begin{matrix}∑_{Q∈[θ_{r}uT,{ \atop θ_{r}uT}]}f(duP uw_{1}ud ⋯ w_{r−1}udw_{r}dQ) \\ = ∑ ∏_{i=0}^{k} v(a_{i}, s_{i}) v(uw_{1}ud ⋯ w_{r−1}udw_{r}d, usd) v(θ_{r}, z_{r}) ∏_{i=1}^{λ} v(b_{i}, t_{i})J(s_{0}V_{1}), \end{matrix} (18)

where the sum is taken over all sequences (s_{i}), i ∈ [0, k], (t_{i}), i ∈ [λ], s, z_{r} and (V_{1}, …, V_{k}, W_{k+1}, V_{k+2}, …, V_{k+λ}) with s_{i} ≥ a_{i}, t_{i} ≥ b_{i}, s ≥ w_{1}udw_{2}ud ⋯ w_{r−1}udw_{r}, z_{r} ≥ θ_{r}, V_{i} ≥ us_{i}V_{i+1}, i ∈ [k − 1], V_{k} ≥ us_{k}usdW_{k+1}, W_{k+1} ≥ z_{r}V_{k+2}, V_{k+i+1} ≥ ut_{i}V_{k+i+2}, i ∈ [λ], and V_{k+λ+2} = ε.

Clearly, we have

v(uw_{1}ud ⋯ w_{r−1}udw_{r}d, usd) = ∑_{ϕ≤s} v(w_{1}ud ⋯ w_{r−1}udw_{r}, ϕ) = ∑_{i∈[r]^{ϕ_{i}≥w_{i}}} ∏_{i=1}^{r} v(w_{i}, ϕ_{i}),

where ϕ_{i} ∈ D, i ∈ [r], and ϕ_{1}ud ⋯ ϕ_{r−1}udϕ_{r} ≤ s. Then, by substituting in equality (18), summing in terms of (W_{i}), i ∈ [r], changing the order of summation and using Proposition 12, in an analogous way as the one used in the proof of formula (15), we can easily deduce that

∑_{i∈[r]^{w_{i}∈[η_{i},η^{∗}_{i}]}} ∑_{Q∈[θ_{r}uT,{ \atop θ_{r}uT}]} f(duP uw_{1}ud ⋯ w_{r−1}udw_{r}dQ)

= ∑ ∏_{i=0}^{k} v(a_{i}, s_{i}) ∏_{i=1}^{r} v(uη_{i}d, uϕ_{i}d) v(θ_{r}, z_{r}) ∏_{i=1}^{λ} v(b_{i}, t_{i})J(s_{0}V_{1}),  (19)

where s_{i} ≥ a_{i}, i ∈ [0, k], t_{i} ≥ b_{i}, i ∈ [λ], ϕ_{i} ≥ η_{i}, i ∈ [r], s ≥ ϕ_{1}ud ⋯ ϕ_{r−1}udϕ_{r}, z_{r} ≥ θ_{r}, V_{i} ≥ us_{i}V_{i+1}, i ∈ [k − 1], V_{k} ≥ us_{k}usdW_{k+1}, W_{k+1} ≥ z_{r}V_{k+2}, V_{k+i+1} ≥ ut_{i}V_{k+i+2}, i ∈ [λ], and V_{k+λ+2} = ε.

Then, by setting t_{0} = uϕ_{1}d ⋯ uϕ_{r}dz_{r} and V_{k+1} = usdW_{k+1}, the RHS of equality (19) becomes

∑ ∏_{i=0}^{k} v(a_{i}, s_{i}) ∏_{i=0}^{λ} v(b_{i}, t_{i})J(s_{0}V_{1}),

where the sum is taken over all sequences (s_{i}), (t_{i}), (V_{i}) with the same restrictions as in equality (14), with the extra condition that the r-th low valley of t_{0} (and b_{0}) coincides with the first low valley of V_{k+1}.

Next, by summing in terms of r ∈ [ξ], we deduce that the first sum on the RHS of equality (17) coincides with the part of the second sum in (14) for which V_{k+1} has low valleys.

Finally, for the second sum on the RHS of equality (17), by applying (14) for the pair (P uw_{1}ud ⋯ w_{ξ}ud, T), we have that

∑_{i∈[ξ]^{w_{i}∈[η_{i},η^{∗}_{i}]}} ∑_{Q∈[T,T̃]} f(duP uw_{1}ud ⋯ w_{ξ}udQ) = ∑_{i∈[ξ]^{w_{i}∈[η_{i},η^{∗}_{i}]}}∑ ∏_{i=0}^{k} v(a_{i}, s_{i}) ∏_{i=1}^{ξ} v(w_{i}, ϕ_{i}) ∏_{i=1}^{λ} v(b_{i}, t_{i})J(s_{0}V_{1}),

where the sum is taken over all sequences (s_{i}), (ϕ_{i}), (b_{i}) with s_{i} ≥ a_{i}, i ∈ [0, k], ϕ_{i} ≥ w_{i}, i ∈ [ξ], b_{i} ≥ t_{i}, i ∈ [λ], and over all sequences (V_{1}, …, V_{k+1}, W_{k+2}, V_{k+3}, …, V_{k+λ+2}) with V_{i} ≥ us_{i}V_{i+1}, i ∈ [k], V_{k+1} ≥ uϕ_{1}ud ⋯ ϕ_{ξ}udW_{k+2}, W_{k+2} ≥ t_{1}V_{k+3}, V_{k+i+1} ≥ ut_{i}V_{k+i+2}, i ∈ [2, λ], and V_{k+λ+2} = ε.

By changing the order of summation on the RHS of the above equality, using Proposition 12, as before, and setting t_{0} = uϕ_{1}d ⋯ uϕ_{ξ}d, V_{k+2} = uW_{k+2} we deduce easily that the second sum on the RHS of equality (17) coincides with the part of the second sum in (14) for which V_{k+1} has no valleys, which completes the proof of equality (14).

Example 18. For P = u^{2}du^{2}d^{3}u^{2}d, by formula (13) we have that f(du^{3}du^{2}d^{3}u^{2}d) = f(duP) = ∑ v(u^{2}du^{2}d^{3}, s_{0}) v(ud, s_{1})J(s_{0}V_{1}), where the sum is taken over all prime Dyck paths s_{0}, s_{1} with s_{0} ≥ u^{2}du^{2}d^{3} and s_{1} ≥ ud, and all Dyck prefixes V_{1} with V_{1} ≥ us_{1}.

It is easy to check that s_{0} = u^{2}du^{2}d^{3} or s_{0} = u^{4}d^{4}, s_{1} = ud and V_{1} = u^{2}d or V_{1} = u^{3}. Furthermore, for these s_{0}, s_{1} we have that v(u^{2}du^{2}d^{3}, s_{0}) = 1 and v(ud, s_{1}) = 1 so that

f(du^{3}du^{2}d^{3}u^{2}d) = J(u^{2}du^{2}d^{3}u^{2}d) + J(u^{2}du^{2}u^{3}u^{3}) + J(u^{3}dud^{3}u^{2}d) + J(u^{3}dud^{3}u^{3})
+ J(u^{4}d^{4}u^{2}d) + J(u^{4}d^{4}u^{3}).

Then, by formulas (3) and (2) we obtain that

J(u^{2}du^{2}d^{3}u^{2}d)

= |[u^{11}, u^{11}]| + |[u^{2}du^{8}, u^{10}d]| + |[u^{2}du^{2}du^{5}, u^{9}d^{2}]| + |[u^{2}du^{2}d^{2}u^{4}, u^{8}d^{3}]|

+ |[u^{2}du^{2}d^{3}u^{3}, u^{7}d^{4}]| + |[u^{2}du^{2}d^{3}u^{2}d, u^{6}d^{5}]| = 1 + |[(2), (10)]| + |[(2, 4), (9, 9)]| + |[(2, 4, 4), (8, 8, 8)]| + |[(2, 4, 4, 4), (7, 7, 7, 7)]| + |[(2, 4, 4, 4, 6), (6, 6, 6, 6, 6)]|

= 1 + 11 − 2 + |\begin{matrix}8 & \binom{6}{2} \\ 1 & 6 \end{matrix}| + |\begin{matrix}7 & \binom{5}{2} & \binom{5}{3} \\ 1 & 5 & \binom{5}{2} \\ 0 & 1 & 5 \end{matrix}| + |\begin{matrix}6 & \binom{4}{2} & \binom{4}{3} & \binom{4}{4} \\ 1 & 4 & \binom{4}{2} & \binom{4}{3} \\ 0 & 1 & 4 & \binom{4}{2} \\ 0 & 0 & 1 & 4 \end{matrix}| + |\begin{matrix}5 & \binom{3}{2} & \binom{3}{3} & \binom{3}{4} & \binom{1}{5} \\ 1 & 3 & \binom{3}{2} & \binom{3}{3} & \binom{1}{4} \\ 0 & 1 & 3 & \binom{3}{2} & \binom{1}{3} \\ 0 & 0 & 1 & 3 & \binom{1}{2} \\ 0 & 0 & 0 & 1 & 1 \end{matrix}|

= 1 + 9 + 33 + 65 + 75 + 35 = 218.

Similarly, we find that J(u^{2}du^{2}d^{3}u^{3}) = 183, J(u^{3}dud^{3}u^{2}d) = 166, J(u^{3}dud^{3}u^{3}) = 141, J(u^{4}d^{4}u^{2}d) = 114 and J(u^{4}d^{4}u^{3}) = 99, so that we obtain that f(du^{3}du^{2}d^{3}u^{2}d) = 921.

In the last result, we show that for specific paths, the map f is also related to the zeta function.

Corollary 19. If a is a product of pyramids, then

f(du^{k}a) = ζ^{k+1}(a, u^{|a|}),

for every k ≥ 1.

Proof. We apply Proposition 17 for the Dyck prefix P = u^{k−1}a. Firstly, for k = 1 we obtain that

f(dua) = J(a) = ζ^{2}(a, u^{|a|}).

Next, for k ≥ 2 we obtain that

f(dua) = ∑ J(V_{1}),

where the sum is taken over all sequences (V_{i}), i ∈ [k] of Dyck prefixes with V_{i} ≥ uV_{i+1}, i ∈ [k − 1], V_{k−1} ≥ uaV_{k} and V_{k} = ε.

Each such sequence (V_{i}), i ∈ [k], produces a unique multichain (W_{i}), i ∈ [0, k − 1], of length k − 1 from u^{k−1}a to V_{1}, defined by W_{0} = u^{k−1}a and W_{i} = u^{k−i−1}V_{k−i}, i ∈ [k − 1].

Then, formula (13) gives that

f(dua) = ∑_{V_{1}≥u^{k−1}a} ζ^{k−1}(u^{k−1}a, V_{1})J(V_{1}) = ζ^{k+1}(u^{k−1}a, u^{k−1+|a|}) = ζ^{k+1}(a, u^{|a|}).

References

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

[2] C. Germain and J. Pallo, Two shortest path metrics on well-formed parentheses strings, Inform. Process. Lett. 60 (1996), 283–287.

[3] D. E. Knuth, The Art of Computer Programming, Vol. 4A, Addison-Wesley, 2011.

[4] C. Krattenthaler, Lattice path enumeration, in M. Bona ed., Handbook of Enumerative Combinatorics, CRC Press, 2015, pp. 589–678.

[5] B. Lindström, Conjecture on a theorem similar to Sperner’s, in R. Guy, H. Hanani, N. Sauer, and J. Schönheim, eds., Combinatorial Structures and Their Applications, Gordon and Breach, 1970, p. 241.

[6] K. Manes, I. Tasoulas, A. Sapounakis, and P. Tsikouras, Counting pairs of noncrossing binary paths: A bijective approach, Discrete Math. 342 (2019), 352–359.

[7] R. Merris and T. Roby, The lattice of threshold graphs, JIPAM. J. Inequal. Pure Appl. Math., 6 (1) (2005), Article 2.

[8] J. Pallo and R. Racca, A note on generating binary trees in A-order and B-order, Int. J. Comput. Math. 18 (1985), 27–39.

[9] A. Sapounakis, I. Tasoulas, and P. Tsikouras, On the dominance partial ordering of Dyck paths, J. Integer Sequences 9 (2006), Article 06.2.5.

[10] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, available at

https://oeis.org, 2019.

[11] R. P. Stanley, Some applications of algebra to combinatorics, Discrete Appl. Math. 34 (1991), 241–277.

[12] R. P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd edition, Cambridge University Press, 2011.

2010 Mathematics Subject Classification: Primary 05A19; Secondary 05A15, 06A07. Keywords: binary path, Dyck path, partial order of paths, chain of paths.

(Concerned with sequences \underline{A000108}, \underline{A000213}, and \underline{A001405}.)

Received May 8 2019; revised versions received August 29 2019; September 27 2019. Published in Journal of Integer Sequences, December 29 2019.

Return to Journal of Integer Sequences home page.