Returns and Hills on Generalized Dyck Paths

Naiomi T. Cameron Department of Mathematical Sciences Lewis & Clark College Portland, OR 97219 USA

                  ncameron@lclark.edu

Jillian E. McLeod Department of Mathematics U.S. Coast Guard Academy New London, CT 06320 USA

              jillian.e.mcleod@uscga.edu

Abstract

In 2009, Shapiro posed the following question: “What is the asymptotic proportion of Dyck paths having an even number of hills?” In this paper, we answer Shapiro’s question, as well as a generalization of the question to ternary paths. We find that the probability that a randomly chosen ternary path has an even number of hills approaches 125/169 as the length of the path approaches infinity. Our strategy relies on properties of the Fine number sequence and extends certain relationships between the Catalan and Fine number generating functions.

1 Introduction

Much has been written about patterns of returns and hills on Dyck paths, which are enumerated by the Catalan numbers. Here we begin by extending some of those results to the setting of the sequence,

t_{n} = \frac{1}{2n + 1}\binom{3n}{n},

[figure]

Figure 1: There are t_{3} = 12 non-crossing trees with 4 vertices.

which we will henceforth refer to as the ternary numbers.^{1}

The ternary numbers (A001764) are a well-known sequence, appearing often throughout the literature and having many interpretations. For example, Stanley [12, Exercise 5.45– 46] documents the ternary numbers counting noncrossing trees with n edges (see Figure 1), recursively labeled forests on [n], and plane ternary trees with 3n + 1 vertices. Bearing these combinatorial interpretations in mind, it is not difficult to see that the generating function for the ternary numbers T (z) = ∑_{n=0}^{∞} t_{n}z^{n} satisfies the cubic equation

T (z) = 1 + zT^{3}(z).  (1)

For example, equation (1) can be explained in terms of non-crossing trees by noting that every noncrossing tree is either empty or can be pictorially decomposed as

[figure: T_{1}; T_{2}; T_{3}]

where each of T_{1}, T_{2} and T_{3} is a noncrossing tree. Since each edge of a noncrossing tree is associated with a z in T (z) and T (z) is the generating function for T_{1}, T_{2} and T_{3}, we obtain the relationship in (1).

The ternary numbers can be considered an analogue of the Catalan number sequence A000108, c_{n} = {1 \atop n+1} \binom{2n}{n}, whose generating function C(z) = ∑_{n=0}^{∞} c_{n}z^{n} satisfies C(z) = 1 + zC^{2}(z) and has the closed form

C(z) = {1 − √1 − 4z \atop 2z^{2}} .

Among many other interpretations, the Catalan numbers count Dyck paths, which are paths that start at (0, 0), end at (2n, 0), use up steps U of the form (1, 1), down steps D of the form (1, −1) and never go below the x-axis. For example, UUDUDD is a Dyck path of length 6 and there are a total of c_{3} = 5 possible Dyck paths of length 6. (See Figure 2.)

One way to generalize Dyck paths is to hold the length of the down step D as a parameter.

Definition 1. Let t ≥ 0. A t-Dyck path is a path from (0, 0) to (tn, 0) where n ≥ 0 with step set {U(1, 1)} ∪ {D(1, −t + 1)} which never goes below the x-axis.

Figure 2: Of the c_{3} = 5 Dyck paths of length 6 there are two with no hills.

Figure 3: Of the t_{2} = 3 ternary paths of length 6, there are two with no hills.

In the case where t = 3, we obtain so-called ternary paths which are counted by the ternary numbers. For example, UUUDUD is one of the 3 possible ternary paths of length 6. (See Figure 3.) Using a decomposition argument similar to that used for noncrossing trees, one can show that T (z) is the generating function for the number of ternary paths of length 3n.

In general, it is known that the number of t-Dyck paths of length tn is the generalized Catalan number

\frac{1}{(t − 1)n + 1}\binom{tn}{n}.

Let C_{t}(z) denote the generating function for the generalized Catalan numbers, that is,

C_{t}(z) = ∑_{n=0}^{∞} \frac{1}{(t − 1)n + 1}\binom{tn}{n}z^{n}.

The fact that

C_{t}(z) = 1 + z(C_{t}(z))^{t}

follows immediately from the fact that every t-Dyck path is either the empty path or has the form UP_{1}UP_{2}UP_{3} ⋯ UP_{t−1}DP_{t} where each P_{i} is a t-Dyck path. Note that C_{0}(z) = 1, C_{1}(z) = 1/(1 − z), C_{2}(z) = C(z) is the generating function for the Catalan numbers and

C_{3}(z) = T (z)  (2)

is the generating function for the ternary numbers t_{n} = \frac{1}{2n+1} \binom{3n}{n}. We also want to point out a fact that we use often in this paper. Adopting the conventional notation [z^{n}]A(z) to denote the coefficient of z^{n} in a formal power series A(z), we note that Graham et al. [7] showed via the cycle lemma that

1The reader should not confuse our use of the term “ternary numbers” with any unrelated synonym for base 3 numbers.

[z^{n}]C_{t}^{s}(z) = \frac{s}{tn + s}\binom{tn + s}{n}.  (3)

In this more general context, we want to consider a few of the commonly studied statistics on Dyck paths. One common statistic for Dyck paths is the number of returns. A return on a t-Dyck path is a non-origin point on the path with ordinate 0. An elevated t-Dyck path is a t-Dyck path with exactly one return. Notice that an elevated t-Dyck path has the form UP_{1}UP_{2}UP_{3} ⋯ UP_{t−1}D where each P_{i} is a t-Dyck path. Therefore, we know that the generating function for the number of elevated t-Dyck paths is z(C_{t}(z))^{t−1}. In Section 2.1, we provide a limiting distribution for the number of returns on t-Dyck paths.

Another common statistic associated with Dyck paths is the number of peaks at a certain height. A peak in a t-Dyck path is an occurrence of the sequence UD and the height of a peak is the ordinate of the intersection of its two steps. For Dyck paths, a peak of height one is also known as a hill. More generally though, for t ≥ 1, we define a hill in a t-Dyck path as a ground level subpath of the form U^{t−1}D. Note that a hill in a t-Dyck path is not generally the same as a peak of height t − 1. For instance, there are two 3-Dyck paths of length 6 having no hills, while there is just one 3-Dyck path of length 6 having no peaks at height 2. (See Figure 3.) In this paper, we are more concerned with hills than peaks.

Any discussion of hills among Dyck paths will surely include references to the Fine numbers (\underline{A000957}). The Fine number sequence, which begins

1, 0, 1, 2, 6, 18, 57, 186, 622, 2120, 7338, 25724, 91144, …

has a number of interesting connections to the Catalan sequence. In this paper, f_{n} will denote the nth Fine number and F (z) = ∑_{k=0}^{∞} f_{n}z^{n} will denote the generating function for the Fine numbers, which in its closed form, is

F (z) = \frac{1 − \sqrt{1 − 4z}}{z(3 − \sqrt{1 − 4z})}.

The Fine number sequence is well documented in the literature, notably as the subject of some surveys [1, 2, 3, 4]. Among their numerous applications, the Fine numbers count Dyck paths of length 2n having no hills. For example, of the five Dyck paths of length 6, there are f_{3} = 2 having no hills. See Figure 2. In Sections 3.2 and 4 of this article, we describe and interpret a natural analogue of the Fine number sequence for t-Dyck paths.

The Motzkin numbers (\underline{A001006}) form another combinatorial sequence with deep connections to the Catalan numbers. The Motzkin numbers {m_{n}} count Motzkin paths, which are paths from (0, 0) to (n, 0) with step set {U(1, 1), L(1, 0), D(1, −1)} which never go below the x-axis. If we modify Motzkin paths by requiring that the level step take one of two possible colors, then C^{2}(z) is the generating function for the number of resulting paths. With the further restriction of no level steps on the x-axis, the generating function is F (z). In the effort to describe a Fine analogue for t-Dyck paths, there is a natural encounter with a Motzkin analogue for t-Dyck paths, as we will see in Section 4.

At various points in the paper, we will encounter Riordan arrays. A Riordan array R = (g(z), f(z)) is an infinite lower triangular matrix whose kth column has a generating function given by g(z)f^{k}(z) with g(0) ≠ 0 and f(0) = 0. It is sometimes helpful to use Riordan arrays to summarize statistics on paths and other combinatorial objects and we will do so here when convenient. For example, the entry in row n and column k (where n, k ≥ 0) of the Riordan array (\underline{A033184})

(C(z), zC(z)) = ( \begin{matrix}1 \\ 1 & 1 \\ 2 & 2 & 1 \\ 5 & 5 & 3 & 1 \\ 14 & 14 & 9 & 4 & 1 \\ 42 & 42 & 28 & 14 & 5 & 1 \\ 132 & 132 & 90 & 48 & 20 & 6 & 1 \\ & & & … \end{matrix} ) ,  (4)

is [z^{n}]z^{k}C^{k+1}(z), the coefficient of z^{n} in z^{k}C^{k+1}(z). Note also that [z^{n}]z^{k}C^{k+1}(z) is the number of Dyck paths of length 2(n + 1) having exactly k + 1 returns to the x-axis. Riordan arrays form a group under matrix multiplication known as the Riordan group, which has served as both a tool and object of combinatorial study [11]. The product of two Riordan arrays is given by

(g_{1}(z), f_{1}(z)) ∗ (g_{2}(z), f_{2}(z)) = (g_{1}(z)g_{2}(f_{1}(z)), f_{2}(f_{1}(z))) .

One can also express the product of a Riordan array and an infinite column vector as

(g_{1}(z), f_{1}(z)) ∗ h(z) = g_{1}(z)h(f_{1}(z)),

where h(z) is the generating function for the entries of an infinite column vector.

In the study of returns and hills among t-Dyck paths, we will encounter the negative binomial distribution, which often shows up in combinatorial statistics [5], and we wish to remind the reader about the characteristics of a negative binomial distribution. In general, we say Y has the negative binomial distribution with parameters r, p and write Y ∼ negbin(r, p), when

P (Y = k) = \binom{k − 1}{r − 1}p^{r}(1 − p)^{k−r},

or equivalently, Y is the random variable for the trial at which the rth success occurs in a sequence of Bernoulli trials with success probability p. The distribution negbin(r, p) is known to have expected value E(Y) = \frac{r(1−p)}{p} and variance Var(Y) = \frac{r(1−p)}{p^{2}}.

The article is organized as follows. In Section 2, we consider the asymptotic distribution for the number of returns and the number of hills among t-Dyck paths. In Section 3, we compute exact probabilities for the number of hills among Dyck paths of length 2n in order to determine the asymptotic proportion of Dyck paths having an even number of hills. We also introduce an analogue of the Fine numbers for the ternary numbers and determine the asymptotic probability that a ternary path has an even number of hills. In Section 4, we describe a Fine analogue for C_{t}(z) in terms of colored Motzkin-like paths and we present a combinatorial identity involving its generating function.

2 Returns and hills via the Riordan group

In this section, we use the Riordan group to study the number of returns and hills among ternary paths. The ultimate goal is to determine the limiting distribution for the number of returns and for the number of hills among t-Dyck paths.

2.1 The number of returns among ternary paths, t-Dyck paths

First, we describe the generating function for the number of ternary paths having a given number of returns. Recall from equation (2) that C_{3}(z) = T (z) is the generating function for the number of ternary paths.

Proposition 2. Let T (z) be the generating function for the number of ternary paths. For 0 ≤ m ≤ n, z^{m}T^{2m}(z) is the generating function for the number of ternary paths of length 3n having exactly m returns to the x-axis.

Proof. Any ternary path of length 3n where n ≥ 1 has at least one return, i.e., the empty path is the only path with no returns. For n ≥ 0, any nonempty ternary path of length 3n with exactly m returns must has the form

(UP_{1}UQ_{1}D)(UP_{2}UQ_{2}D)(UP_{3}UQ_{3}D) ⋯ (UP_{m}UQ_{m}D)

where each P_{i}, Q_{i} is a (possibly empty) ternary path. When counting ternary paths with T (z), each D is associated with a z, so the generating function for the number of ternary paths with exactly m returns is z^{m}T^{2m}(z).

If r_{n,m} denotes the number of ternary paths of length 3n having m returns to the x-axis, then the following array (\underline{A109971})

(r_{n,m})_{n,m≥0} = ( \begin{matrix}1 \\ 0 & 1 \\ 0 & 2 & 1 \\ 0 & 7 & 4 & 1 \\ 0 & 30 & 18 & 6 & 1 \\ 0 & 143 & 88 & 33 & 8 & 1 \\ 0 & 728 & 455 & 182 & 52 & 10 & 1 \\ & & & … \end{matrix} ) = (1, zT^{2}(z)),  (5)

is a Riordan array whose row sums are the ternary numbers.

Theorem 3. The probability that a randomly chosen ternary path has m returns approaches \frac{4m}{3^{m+1}} as path length approaches infinity. The asymptotic distribution for the (nonzero) number of returns among ternary paths is the negative binomial distribution with parameters 2 and 2/3. Hence, the expected number of returns among ternary paths approaches 2 with variance 3/2.

Proof. We proceed by calculating the associated probabilities. Let Y_{n} ≥ 0 denote the number of returns for a ternary path of length 3n. Let p_{m}(n) be the probability that a randomly chosen ternary path of length 3n has m returns, that is, p_{m}(n) = P (Y_{n} = m). We know from Proposition 2 that the generating function for the number of paths with m returns is z^{m}T^{2m}(z). Making use of (3), we obtain

p_{m}(n) = \frac{[z^{n}]z^{m}T^{2m}(z)}{[z^{n}]T (z)}

= \begin{matrix}\frac{2m}{3(n−m)+2m} & \binom{3(n−m)+2m}{n−m} \\ \frac{1}{2n+1} & \binom{3n}{n} \end{matrix}
= \frac{2m(2n + 1)(n − m + 1)(n − m + 2) ⋯ (n − 1)}{3(3n − m)(3n − m + 1)(3n − m + 2) ⋯ (3n − 1)}
= \frac{2m(2n + 1)(n − 1)\underline{m−1}}{3(3n − 1)\underline{m}}

where x\underline{j} = x(x − 1)(x − 2) ⋯ (x − j + 1). It follows immediately that as n → ∞,

p_{m}(n) → \frac{4m}{3^{m+1}} = \binom{(m + 1) − 1}{1} (\frac{2}{3})^{2} (\frac{1}{3})^{(m+1)−2} = P (Y = m + 1)

where m ≥ 0 and Y ∼ negbin(2, \frac{2}{3}).

So, we see that p_{m}(n) → P (Y = m + 1) where Y ∼ negbin(2, \frac{2}{3}). Notice that Y_{n} = 0 if and only if n = 0. So if we wish to restrict to the case where the number of returns is nonzero, we may consider Y_{n} +1. Since E(Y) = \frac{2(1/3)}{2/3} = 1, we can conclude that E(Y_{n} +1) =

E(Y_{n}) + 1 → E(Y) + 1 = 2 and Var(Y_{n} + 1) = Var(Y_{n}) → Var(Y) = \frac{E(Y)}{2/3} = \frac{3}{2}.

We can also use the Riordan group to determine (exactly) E(Y_{n}), the expected number of returns among ternary paths of length 3n. Observe that the total number of returns among all ternary paths of length 3n is given by the generating function for the infinite column vector,

( \begin{matrix}1 \\ 0 & 1 \\ 0 & 2 & 1 \\ 0 & 7 & 4 & 1 \\ 0 & 30 & 18 & 6 & 1 \\ 0 & 143 & 88 & 33 & 8 & 1 \\ 0 & 728 & 455 & 182 & 52 & 10 & 1 \\ & & & … \end{matrix} ) ( 0 1 2 3 4 5 6 ⋮ ) ,

where the matrix on the left is given in equation (5). In terms of Riordan group multiplication, this product is

(1, zT^{2}(z)) ∗ \frac{z}{(1 − z)^{2}} = \frac{zT^{2}(z)}{(1 − zT^{2}(z))^{2}}
= z (\frac{T}{1 − zT^{2}} )^{2}
= zT^{4}.

The last equality follows from the fact that

\frac{T}{1 − zT^{2}} = \frac{T^{2}}{T − zT^{3}} = \frac{T^{2}}{1} = T^{2}.  (6)

Hence, the expected number of returns among ternary paths of length 3n is

E(Y_{n}) = \frac{[z^{n}]zT^{4}}{[z^{n}]T}

= \begin{matrix}\frac{4}{3(n−1)+4} & \binom{3(n−1)+4}{n−1} \\ \frac{1}{2n+1} & \binom{3n}{n} \end{matrix}
= \frac{4(3n + 1)n}{(3n + 1)(2n + 2)}
= \frac{2n}{n + 1}.

And we have verified that indeed, the expected number of returns for ternary paths approaches 2.

We may also compute (exactly) the variance Var Y_{n} by considering the square of the number of returns. Notice that

( \begin{matrix}1 \\ 0 & 1 \\ 0 & 2 & 1 \\ 0 & 7 & 4 & 1 \\ 0 & 30 & 18 & 6 & 1 \\ 0 & 143 & 88 & 33 & 8 & 1 \\ 0 & 728 & 455 & 182 & 52 & 10 & 1 \\ & & & … \end{matrix} ) ( 0 1 4 9 16 25 36 ⋮ ) = (1, zT^{2}(z)) ∗ \frac{z + z^{2}}{(1 − z)^{3}}

= \frac{zT^{2}}{(1 − zT^{2})^{3}} + \frac{z^{2}T^{4}}{(1 − zT^{2})^{3}}
= \frac{zT^{4}}{1 − zT^{2}} + z^{2}T^{7}
= zT^{5} + z^{2}T^{7}

which implies that

Var Y_{n} = EY_{n}^{2} − (EY_{n})^{2}
= \frac{[z^{n}]zT^{5} + z^{2}T^{7}}{[z^{n}]T} − (\frac{2n}{n + 1})^{2}

= \begin{matrix}\frac{4}{3(n−1)+4} & \binom{3(n−1)+4}{n−1} \\ \frac{1}{2n+1} & \binom{3n}{n} \end{matrix}

and Var Y_{n} → \frac{3}{2} as n → ∞.

Now in the case of Dyck paths, the expected number of returns approaches 3 with variance 4 and the limiting distribution is negbin(2, \frac{1}{2}). Naturally, it would be nice to know the corresponding statistics for generalized Dyck paths, and it is possible do so given the fact that the generating function for the number t-Dyck paths having exactly m returns is z^{m}C_{t}^{(t−1)m}(z). The necessary calculations that follow proceed almost exactly as above and we obtain the following result.

Theorem 4. Let Y_{n} denote the random variable for the number of returns among t-Dyck paths of length tn and let Y = lim_{n→∞} Y_{n}. Then

Y ∼ negbin (2, \frac{t − 1}{t})

Hence, the expected number of returns among nontrivial t-Dyck paths approaches \frac{t+1}{t−1} with variance \frac{2t}{(t−1)^{2}} .

Proof. If Y_{n} denotes the number of returns among t-Dyck paths of length tn, then

P (Y_{n} = m) = \frac{(t − 1)m((t − 1)n + 1)n\underline{m}}{tn(tn − 1)\underline{m}}

which approaches

\frac{m(t − 1)^{2}}{t^{m+1}} = \binom{m + 1 − 1}{2 − 1} (\frac{t − 1}{t})^{2} (\frac{1}{t})^{m−1}

as n → ∞.

2.2 The number of hills among ternary paths, t-Dyck paths

We begin this subsection with the observation that the formula for the number of ternary paths of length 3n having exactly k hills is not as nice as the formula we saw for the number of returns in the previous subsection. This is due to the fact that counting hills among ternary paths requires an analogue to the Fine numbers.

Let F_{t}(z) be the generating function for the number of t-Dyck paths of length tn having no hills. (In the case where t = 2, F_{t}(z) is the generating function for the Fine numbers.) It follows that the generating function for the number of t-Dyck paths of length tn having exactly m hills is z^{m}F_{t}^{m}(z) and the nth row of the Riordan array (F_{t}(z), zF_{t}(z)) gives a distribution of the t-Dyck paths of length tn by number of hills. Though there is no closed formula for the entries of (F_{t}(z), zF_{t}(z)), there is much that can be said about this Riordan array and in Sections 3.2 and 4, we indulge the reader with more detail in the case when t = 3. The following identity extends naturally from the relationship between the Catalan and Fine numbers:

C_{t}(z) = \frac{F_{t}(z)}{1 − zF_{t}(z)} ⟺ F_{t}(z) = \frac{C_{t}(z)}{1 + zC_{t}(z)}  (7)

Because this identity will come in handy now, we will use it here without proof. However, the interested reader is directed to Theorem 14 in Section 4 for further exploration and justification of (7).

Because there is no nice closed formula for the number of hills among t-Dyck paths, some care must be taken to give a closed formula for the exact probability that a ternary path has a given number of hills. Again, we defer to Section 3.2 for the necessary details regarding this computation. At present, however, we can use the Riordan group to compute the moments for the asymptotic distribution of hills among ternary paths, and in fact more generally, among t-Dyck paths.

Theorem 5. The expected number of hills among t-Dyck paths approaches \frac{2}{t} (\frac{t−1}{t})^{t−2} with

variance \frac{2}{t} (\frac{t−1}{t})^{t−2} (\frac{t^{t−1}+(t−1)^{t−2}}{t^{t−1}} ) as path length approaches infinity. In particular, the expected number of hills among ternary paths approaches \frac{4}{9} with variance \frac{44}{81}.

Proof. Let X_{n} denote the random variable for the number of hills on a t-Dyck path of length tn. It is relatively straightforward to compute the first moment E(X_{n}). The generating function for the total number of hills among t-Dyck paths is simply zC_{t}^{2}(z) — this is true because every hill is preceded and followed by a t-Dyck path of some length. Hence,

E(X_{n}) = \frac{[z^{n}]zC_{t}^{2}}{[z^{n}]C_{t}} = \frac{[z^{n−1}]C_{t}^{2}}{[z^{n}]C_{t}}

= \begin{matrix}\frac{2}{t(n−1)+2} & \binom{t(n−1)+2}{n−1} \\ \frac{1}{(t−1)n+1} & \binom{tn}{n} \end{matrix}

= \frac{2n(tn − (t − 1))!((t − 1)n + 1)!}{(tn)!((t − 1)n − (t − 3))!}

= \frac{2((t − 1)n + 1)\underline{t−2}}{t(tn − 1)\underline{t−2}} ,

where x\underline{j} = x(x − 1)(x − 2) ⋯ (x − j + 1). Consequently, we see that E(X_{n}) → \frac{2}{t} (\frac{t−1}{t})^{t−2} as n → ∞.

To compute the second moment E(X_{n}^{2}), we need to compute the sum of the squares of the number of hills among t-Dyck paths of length tn. Here, we will make use of Riordan group algebra. Given that the generating function for the sequence of squares is \frac{z+z^{2}}{(1−z)^{3}} , we want to consider the sequence obtained by the Riordan product

(F_{t}, zF_{t}) ∗ \frac{z + z^{2}}{(1 − z)^{3}} = \frac{zF_{t}^{2} + z^{2}F_{t}^{3}}{(1 − zF_{t})^{3}}

= \frac{zF_{t}^{2}}{(1 − zF_{t})^{3}} + z^{2}C_{t}^{3}

= \frac{zC_{t}^{3}}{\frac{C_{t}}{1+zC_{t}}} + z^{2}C_{t}^{3}

= zC_{t}^{2} + 2z^{2}C_{t}^{3},

which gives us the sum of the squares of the number of hills among t-Dyck paths. Hence, the second moment is

E(X_{n}^{2}) = \frac{[z^{n}]zC_{t}^{2} + 2z^{2}C_{t}^{3}}{[z^{n}]C_{t}}

= E(X_{n}) + \frac{[z^{n−2}]2C_{t}^{3}}{[z^{n}]C_{t}}

= E(X_{n}) + 2 \begin{matrix}\frac{3}{t(n−2)+3} & \binom{t(n−2)+3}{n−2} \\ \frac{1}{(t−1)n+1} & \binom{tn}{n} \end{matrix}

= \frac{2((t − 1)n + 1)\underline{t−2}}{t(tn − 1)\underline{t−2}} + \frac{6(n − 1)n}{(t(n − 2) + 3)(t(n − 2) + 4)} \frac{((t − 1)n + 1)\underline{2t−4}}{(tn)\underline{2t−4}}

and E(X_{n}^{2}) → \frac{2}{t} (\frac{t−1}{t})^{t−2} + \frac{6}{t^{2}} (\frac{t−1}{t})^{2t−4} = \frac{2}{t} (\frac{t−1}{t})^{t−2} (\frac{t^{t−1}+3(t−1)^{t−2}}{t^{t−1}} )

Now, we may compute the variance of X_{n} as follows

Var(X_{n}) = E(X_{n}^{2}) − (E(X_{n}))^{2}

= \frac{2((t − 1)n + 1)\underline{t−2}}{t(tn − 1)\underline{t−2}} + \frac{6(n − 1)n}{(t(n − 2) + 3)(t(n − 2) + 4)} \frac{((t − 1)n + 1)\underline{2t−4}}{(tn)\underline{2t−4}}

− (\frac{2((t − 1)n + 1)\underline{t−2}}{t(tn − 1)\underline{t−2}} )^{2}

and notice that Var(X_{n}) → \frac{2}{t} (\frac{t−1}{t})^{t−2}+ \frac{6}{t^{2}} (\frac{t−1}{t})^{2t−4}− \frac{4}{t^{2}} (\frac{t−1}{t})^{2t−4} = \frac{2}{t} (\frac{t−1}{t})^{t−2} (\frac{t^{t−1}+(t−1)^{t−2}}{t^{t−1}} ) as n → ∞.

The relationship between the asymptotic mean and variance for the number of hills provides the initial evidence for the following conjecture.

Conjecture 6. Let X_{n} denote the random variable for the number of hills among t-Dyck paths of length tn and let X = lim_{n→∞} X_{n}. Then

X ∼ negbin (2, \frac{t^{t−1}}{t^{t−1} + (t − 1)^{t−2}} )

The evidence for this conjecture is based on verification of the result in the case where t ≤ 3 (see Section 3) and the computation of the moments E(X_{n}^{m}). To compute E(X_{n}^{m}), we consider the mth power of the number of hills. The generating function for the power

sequence 0^{m}, 1^{m}, 2^{m}, 3^{m}, … is \frac{e_{m}(z)}{(1 − z)^{m+1}} , where

e_{m}(z) = ∑_{k=1}^{m} e_{m,k}z^{k}

is the Eulerian polynomial of degree m and

e_{m,k} = ∑_{j=0}^{k} (−1)^{j}(k − j)^{m}\binom{m + 1}{j}

are the Eulerian numbers (\underline{A008292}). To find the mth moment for the number of hills, we consider the Riordan product

(F_{t}, zF_{t}) ∗ \frac{e_{m}(z)}{(1 − z)^{m+1}} = ∑_{k=1}^{m} e_{m,k} \frac{z^{k}F_{t}^{k+1}}{(1 − zF_{t})^{m+1}}

Now we may compute the expected value of X_{n}^{m}, making use of identity (7), as follows:

E(X_{n}^{m}) = \frac{[z^{n}] ∑_{k=1}^{m} e_{m,k} \frac{z^{k}F_{t}^{k+1}}{(1 − zF_{t})^{m+1}}}{[z^{n}]C_{t}}

= \frac{∑_{k=1}^{m} e_{m,k} [z^{n}] z^{k}C_{t}^{k+1} (\frac{C_{t}}{F_{t}} )^{m−k}}{[z^{n}]C_{t}}

= ∑_{k=1}^{m} e_{m,k} \frac{[z^{n−k}] C_{t}^{k+1}(1 + zC_{t})^{m−k}}{[z^{n}]C_{t}}

= ∑_{k=1}^{m} (∑_{j=0}^{m−k} e_{m,k}\binom{m − k}{j} \begin{matrix}\frac{j+k+1}{t(n−(j+k))+j+k+1} & \binom{t(n−(j+k))+j+k+1}{n−(j+k)} \\ \frac{1}{tn+1} & \binom{tn+1}{n} \end{matrix})

= \frac{1}{[z^{n}]C_{t}(z)} ∑_{k=1}^{m} (∑_{j=0}^{m−k} e_{m,k}\binom{m − k}{j}[z^{n}]z^{j+k}C_{t}^{j+k+1})

Using Mathematica, this quantity has been verified to match the moments of

negbin (2, \frac{t^{t−1}}{t^{t−1} + (t − 1)^{t−2}} )

for t ≤ 10 and m ≤ 20.

3 Dyck paths and ternary paths with an even number of hills

In this section, we provide a response and extension to the following question posed by L. Shapiro [2] in a private communication: “What is the asymptotic proportion of Dyck paths having an even number of hills?” Our approach relies on properties of the Fine numbers, though it is also possible to use the techniques of the last section to answer the question. Along the way we uncover some interesting combinatorial relationships between the Fine and Catalan numbers sequences and one of their many generalizations.

3.1 Even number of hills among Dyck paths

Recall that F (z) = ∑_{n=0}^{∞} f_{n}z^{n} is the generating function for the Fine numbers. Our first observation is that the number of Dyck paths of length 2n having exactly k hills is given by the (n, k)-th entry of th Riordan array (\underline{A065600})

(F (z), zF (z)) = ( \begin{matrix}1 \\ 0 & 1 \\ 1 & 0 & 1 \\ 2 & 2 & 0 & 1 \\ 6 & 4 & 3 & 0 & 1 \\ 18 & 13 & 6 & 4 & 0 & 1 \\ 57 & 40 & 21 & 8 & 5 & 0 & 1 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,  (8)

where F (z) is the generating function for the Fine numbers.

It has been shown that the proportion of Dyck paths having no hills approaches 4/9. This result, which appears in [4], follows from something described there as the “hill-killer” identity:

C(z) + 1 = (z + 2)F (z)  (9)

which implies that

c_{n} = f_{n−1} + 2f_{n}  (10)

for n ≥ 1. Dividing both sides of (10) by c_{n} and using the fact that c_{n−1}/c_{n} ∼ 1/4, one can reveal that

f_{n}/c_{n} ∼ 4/9.  (11)

To find the proportion of Dyck paths having exactly one hill, we can make use of the following useful identity:

(2z + z^{2})F^{2}(z) − (1 + 2z)F (z) + 1 = 0,  (12)

a result proven combinatorially by Cheon et al. [2]. If a_{n} is the number of Dyck paths of length 2n having one hill then zF^{2}(z) is the generating function for a_{n} (\underline{A065601}). Identity (12) implies that

2a_{n} + a_{n−1} = f_{n} + 2f_{n−1}  (13)

for n ≥ 1. Using the fact that f_{n}/c_{n} ∼ 4/9, c_{n−1}/c_{n} ∼ 1/4 and (13), we find the proportion of Dyck paths having exactly one hill approaches 8/27, that is,

a_{n}/c_{n} ∼ 8/27.  (14)

This can be further generalized by multiplying both sides of (12) by z^{k−1}F^{k−1}, as

z^{k+1}F^{k+1} + 2z^{k}F^{k+1} − z^{k−1}F^{k} − 2z^{k}F^{k} + z^{k−1}F^{k−1} = 0  (15)

to obtain a more general “hill-killer” recurrence.

Proposition 7. Let f_{n,k} denote the number of Dyck paths of semilength n having exactly k hills. That is, f_{n,k} = [z^{n}]z^{k}F^{k+1}. Then

f_{n−1,k} + 2f_{n,k} − f_{n,k−1} − 2f_{n−1,k−1} + f_{n−1,k−2} = 0  (16)

Proof. Follows directly from (15).

We may now use the recurrence in Proposition 7 to answer Shapiro’s question.

Theorem 8. The proportion of Dyck paths having an even number of hills approaches 5/8 as the length of the paths approaches infinity.

Proof. Dividing both sides of equation (16) by c_{n} leads to the following:

\frac{f_{n−1,k}}{c_{n−1}} · \frac{c_{n−1}}{c_{n}} + 2\frac{f_{n,k}}{c_{n}} − \frac{f_{n,k−1}}{c_{n}} − 2\frac{f_{n−1,k−1}}{c_{n−1}} · \frac{c_{n−1}}{c_{n}} + \frac{f_{n−1,k−2}}{c_{n−1}} · \frac{c_{n−1}}{c_{n}} = 0  (17)

Let L_{k} := lim_{n→∞} \frac{f_{n,k}}{c_{n}} be the asymptotic proportion of Dyck paths having k hills. Using

the fact that lim_{n→∞} \frac{c_{n−1}}{c_{n}} = \frac{1}{4}, equation (17) implies

\frac{1}{4}L_{k} + 2L_{k} − L_{k−1} − 2L_{k−1} · \frac{1}{4} + L_{k−2} · \frac{1}{4} = 0

which simplifies to

\frac{9}{4}L_{k} = \frac{3}{2}L_{k−1} − \frac{1}{4}L_{k−2}  (18)

for k ≥ 2. Note that L_{0} = 4/9 and L_{1} = 8/27, as we saw in equations (11) and (14). Solving the linear recurrence in (18) gives,

L(z) := ∑_{k=0}^{∞} L_{k}z^{k} = \frac{4}{9 − 6z + z^{2}} = \frac{4/9}{(1 − z/3)^{2}} ,

the (asymptotic) probability distribution for the number of hills. Hence,

[z^{k}]L(z) = (k + 1) · \frac{4}{9} (\frac{1}{3})^{k}

which is the negative binomial distribution with index 2 and parameter 2/3. (Incidentally, this is the same as the asymptotic distribution for the number of returns among ternary paths, as we saw in Section 2.1.)

To obtain the asymptotic probability that a Dyck path has an even number of hills, take the sum of the even indexed coefficients of L(z), which is

∑_{k=0}^{∞} [z^{2k}]L(z) = ∑_{n=0}^{∞} (2k + 1) · \frac{4}{9} (\frac{1}{9})^{k} = \frac{5}{8}

3.2 Even number of hills among ternary paths

Here we extend our approach in Section 3.1 to answering Shapiro’s question about Dyck paths and determine the asymptotic probability that a randomly chosen ternary path has an even number of hills. In this extension, we encounter and interpret the appropriate analogue of the Fine numbers for the ternary numbers. Recall from (2) that C_{3}(z) = T (z) denotes the generating function for the ternary numbers

t_{n} = \frac{1}{2n + 1}\binom{3n}{n}

The Riordan array (\underline{A110616})

(T (z), zT (z)) = ( \begin{matrix}1 \\ 1 & 1 \\ 3 & 2 & 1 \\ 12 & 7 & 3 & 1 \\ 55 & 30 & 12 & 4 & 1 \\ 273 & 143 & 55 & 18 & 5 & 1 \\ 1428 & 728 & 273 & 88 & 25 & 6 & 1 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,  (19)

counts ternary paths ending at height k ≥ 0. The (n, k)th entry is the number of ternary paths with length 3n + k and terminal height k.

Let t_{n,k} denote the (n, k)th entry of (19), so that t_{n,0} = t_{n}. Then t_{n,k} = [z^{n}]z^{k}T^{k+1} = [z^{n−k}]T^{k+1}, which as a consequence of (2) and (3) is

t_{n,k} = \frac{k + 1}{2n − k + 1}\binom{3n − 2k}{n − k}.  (20)

This fact can be used to show that lim_{n→∞} t_{n−1}/t_{n} = 4/27.

The generating function T^{2}(z) for the nonzero terms in the second column of (19) corresponds to \underline{A006013} which counts

• elevated ternary paths of length 3(n + 1),

• ground level points on all ternary paths of length 3n,

• leaves at the root of all noncrossing trees with n + 2 vertices,

• even trees with 2(n + 1) edges where the degree of the root is two, and

• a third of the leaves at the root of all ternary trees with 3(n + 1) edges.

[figure: 1; k; N_{1}; N_{2}; N_{3}; e]

Figure 4: A nonempty noncrossing tree N with no leaf at its root must have the form above.

It is not hard to show, using (20), that the average number of ground level points on all ternary paths approaches 3, that is lim_{n→∞} t_{n+1,1}/t_{n} = 3. Similarly, since the number of

leaves at the root for all noncrossing trees of order n + 1 is given by t_{n,1} = [z^{n}]zT^{2}(z) = [z^{n−1}]T^{2}(z) = \frac{1}{n} \binom{3n−2}{n−1}, one can show that the average number of leaves at the root t_{n,1}/t_{n} approaches 4/9.

Next we offer an analogue to the Fine number sequence for the ternary numbers. We will refer to a ternary path having no hills as a ternary-Fine path. Let F_{3}(z) denote the generating function for the number of ternary-Fine paths of length 3n. The sequence corresponding to F_{3}(z) begins 1, 0, 2, 7, 34, 171, … (\underline{A023053}).

Theorem 9. If T (z) is the generating function for the number of ternary paths of length 3n and F_{3}(z) is the generating function for the number of ternary paths of length 3n having no

hills, then T (z) = \frac{F_{3}(z)}{1 − zF_{3}(z)} and equivalently, F_{3}(z) = \frac{T (z)}{1 + zT (z)}.

Proof. Every ternary path can be decomposed according to its number of hills. A ternary path with k hills would have the form

(P_{1}UUD)(P_{2}UUD) ⋯ (P_{k}UUD)P_{k+1}

where each P_{i} is a (possibly empty) ternary path with no hills. The associated generating function is z^{k}F_{3}^{k+1}(z) and summing over all k ≥ 0 provides the result.

In addition to ternary-Fine paths of length 3n, F_{3}(z) also counts

• paths from (0, 0) to (n, 0) which never go below the x-axis and use step set {U(1, 1)} ∪ {L_{k}(1, 0) : k = 1, 2, 3} ∪ {D_{k}(1, −1) : k = 1, 2, 3} ∪ {D(1, −2)} but L_{1}, L_{2}, L_{3}, D_{3} are not allowed to touch the x-axis,

• noncrossing trees with n + 1 vertices having no leaves at the root,

• 2-plane trees with n + 1 vertices, root labeled 2 and no leaves at the root

A detailed justification of the first bullet above will be presented in Section 4.

Remark 10. We may refer to the sequence associated with F_{3}(z) as the ternary-Fine numbers. It is worth noting that using the Lindstrom-Gessel-Viennot nonintersecting path system argument for determinants [6, 9], one may conclude that the Hankel transform of the ternary-Fine numbers is equal to the Hankel transform of the ternary numbers (\underline{A051255}).

Next we discuss the limiting distribution for the number of hills among ternary paths. Before proceeding, we present a few generating function identities for F_{3} which prove useful in accomplishing this.

Theorem 11. Let F_{3}(z) be the generating function for the number of ternary paths of length 3n having no hills. Then

zF_{3}(z)T^{2}(z) = F_{3}(z) + zF_{3}(z) − 1

Proof. First, rewrite this equation as

F_{3} = 1 + zF_{3}(T^{2} − 1).

We shall prove this last statement combinatorially in terms of noncrossing trees. F_{3} counts noncrossing trees having no leaves at the root. Observe that any noncrossing tree N with no leaf at the root is either empty or it consists of the following components: (A) the “longest” edge e from the root (that is, the edge e from 1 to k, where k is as large as possible); (B) subtrees N_{1}, N_{2} (not both empty) attached to the left and right of k respectively, and; (C) a (possibly empty) subtree N_{3} with no leaves at its root attached to the root 1. See Figure 4. Since, z counts (A), T^{2} − 1 counts (B) and F_{3} counts (C), it is clear that 1 + zF_{3}(T^{2} − 1) also counts the number of noncrossing trees having no leaf at the root.

The two preceding theorems can be used to give the following recursive identity for the F_{3}(z). Note that Theorem 12 can be thought of as an analogue of the Fine number identity (12) referenced in [2]. In Section 4, we will consider the generalization of this identity for t-Dyck paths.

Theorem 12. Let F_{3}(z) be the generating function for the number of ternary paths of length 3n having no hills. Then

F_{3}^{3}(z − z^{2} − z^{3}) + F_{3}^{2}(2z + 3z^{2}) − F_{3}(1 + 3z) + 1 = 0  (21)

Proof. First, we establish the following preliminary result:

T^{2} = F_{3}^{2}(1 − z − z^{2}) + F_{3}(2 + 3z) − 2  (22)

We begin with the observation from Theorem 9 that

zT^{2} = \frac{zF_{3}^{2}}{(1 − zF_{3})^{2}}

which implies

zF_{3}^{2} = zT^{2}(1 − 2zF_{3} + z^{2}F_{3}^{2})
zF_{3}^{2} = zT^{2} − 2z^{2}T^{2}F_{3} + z^{3}T^{2}F_{3}^{2})
zT^{2} = zF_{3}^{2} + 2z^{2}T^{2}F − z^{3}T^{2}F_{3}^{2}.

Now, using Theorem 11, we obtain

zT^{2} = zF_{3}^{2} + 2z^{2}T^{2}F − z^{3}T^{2}F_{3}^{2}
zT^{2} = zF_{3}^{2} + 2zF_{3} + 2z^{2}F_{3} − 2z − z^{2}F_{3}^{2} − z^{3}F_{3}^{2} + z^{2}F_{3}
T^{2} = F_{3}^{2}(1 − z − z^{2}) + F_{3}(2 + 3z) − 2.

Multiplying both sides of equation (22) by zF and using Theorem 11 provides the result.

The number of ternary paths of length 3n having exactly k hills is given by the (n, k)th entry of the Riordan matrix (\underline{A101371})

(F_{3}(z), zF_{3}(z)) = ( \begin{matrix}1 \\ 0 & 1 \\ 2 & 0 & 1 \\ 7 & 4 & 0 & 1 \\ 34 & 14 & 6 & 0 & 1 \\ 171 & 72 & 21 & 8 & 0 & 1 \\ 905 & 370 & 114 & 28 & 10 & 0 & 1 \\ & & ⋯ \end{matrix} ) .  (23)

Notice that the row sums of (23) are the ternary numbers. Let f̃_{n,k} := [z^{n}]z^{k}F_{3}^{k+1} denote the (n, k)th entry of (23), so that f̃_{n,0} = f̃_{n}.

Now Theorem 12 suggests a recursion for f̃_{n,k}. By multiplying both sides of (21) by z^{k−1}F^{k−1}, we have

F_{3}^{k+2}(z^{k} − z^{k+1} − z^{k+2}) + F_{3}^{k+1}(2z^{k} + 3z^{k+1}) − F_{3}^{k}(z^{k−1} + 3z^{k}) + z^{k−1}F_{3}^{k−1} = 0,

for all k ≥ 1, and by taking the nth coefficient of this last expression, we obtain the following recursion for the triangle in (23):

f̃_{n+1,k+1} − f̃_{n,k+1} − f̃_{n−1,k+1} + 2f̃_{n,k} + 3f̃_{n−1,k} − f̃_{n,k−1} − 3f̃_{n−1,k−1} + f̃_{n−1,k−2} = 0 (24)

for all n ≥ 1 and k ≥ 2.

We can now also answer Shapiro’s question in the context of ternary paths.

Theorem 13. The proportion of ternary paths having an even number of hills approaches 125/169 as the length of the paths approaches infinity.

Proof. Let L̃_{k} denote the asymptotic probability that a ternary path has k hills. That is, let

L̃_{k} = lim_{n→∞} \frac{f̃_{n,k}}{t_{n}} .

We will use equation (22) to find a generating function for L̃_{k}. Divide both sides of equation (24) by t_{n} and let n tend to infinity.

Notice that as n → ∞,

\frac{f̃_{n+1,k}}{t_{n}} = \frac{f̃_{n+1,k}}{t_{n+1}} · \frac{t_{n+1}}{t_{n}} → \frac{27}{4}L̃_{k}

and

\frac{f̃_{n−1,k}}{t_{n}} = \frac{f̃_{n−1,k}}{t_{n−1}} · \frac{t_{n−1}}{t_{n}} → \frac{4}{27}L̃_{k}.

With these two observations and using recursion (24), we have

(\frac{27}{4} − 1 − \frac{4}{27}) L̃_{k+1} + (2 + 3 · \frac{4}{27}) L̃_{k} − (1 + 3 · \frac{4}{27}) L̃_{k−1} + \frac{4}{27}L̃_{k−2} = 0 (25)
⇒ \frac{605}{108}L̃_{k+1} + \frac{22}{9}L̃_{k} − \frac{13}{9}L̃_{k−1} + \frac{4}{27}L̃_{k−2} = 0 (26)

Using this recurrence, along with initial conditions L̃_{0}, L̃_{1}, and L̃_{2}, we can determine that the generating function for L̃_{k} is

L̃(z) = ∑_{k=0}^{∞} L̃_{k}z^{k} = \frac{324z + 405}{605 + 264z − 156z^{2} + 16z^{3}} = (\frac{9}{11 − 2z} )^{2} = (\frac{9/11}{1 − 2z/11})^{2} (27)

(We refer the interested reader to Appendix A for a verification of the initial conditions L̃_{0}, L̃_{1}, and L̃_{2}.) Hence, the proportion of ternary paths having k hills is

[z^{k}]L̃(z) = (k + 1) · \frac{81}{121} (\frac{2}{11})^{k}

which is the negative binomial distribution negbin(2, 9/11) with mean 4/9 and variance 44/81. Finally, the proportion of ternary paths having an even number of hills is given by

∑_{k=0}^{∞} [z^{2k}]L̃(z) = \frac{81}{121} ∑_{k=0}^{∞} (2k + 1) · (\frac{4}{121})^{k} = \frac{125}{169}

4 Generalized Fine and Motzkin analogues

In this section, we generalize the Fine analogue from the previous section and provide some interpretations. In particular, we give a generating function identity for which Theorem 12 is a special case. In connection with this generalized Fine analogue, we also introduce an analogue for the Motzkin numbers and discuss some of its interpretations.

Recall that a t-Dyck path is a path from (0, 0) to (tn, 0) with step set {U(1, 1)} ∪ {D(1, −t + 1)} which never goes below the x-axis and that C_{t}(z) is the generating function for the number of t-Dyck paths of length tn, that is,

C_{t}(z) = ∑_{n=0}^{∞} \frac{1}{(t − 1)n + 1}\binom{tn}{n}z^{n}.

Let’s start with our Fine analogue.

Theorem 14. Let F_{t}(z) be the generating function for the number of t-Dyck paths having no hills. Then

C_{t}(z) = \frac{F_{t}(z)}{1 − zF_{t}(z)}.

Proof. This follows from the fact that t-Dyck paths can be sorted according to their number of hills. A t-Dyck path with k hills would have the form

F_{0}U^{t−1}DF_{1}U^{t−1}DF_{2} ⋯ U^{t−1}DF_{k},

where each F_{i} is a t-Dyck path with no hills. Hence, the generating function for the number of t-Dyck paths with k hills is z^{k}(F_{t}(z))^{k+1} and summing from k = 0 to infinity gives the result.

Note that F_{1}(z) = 1, F_{2}(z) = F (z) is the generating function for the Fine numbers and F_{3}(z) = F_{3}(z) is the Fine analogue of Section 3.2. In this paper, we have seen non-obvious generating function identities for F_{2}(z) and F_{3}(z) which we want to understand in terms of F_{t}(z). Recalling the approach to equation (12) which was used in [2], we first want to consider a different path interpretation of F_{t}(z).

Consider the set of paths from (0, 0) to (n, 0) with step set {(1, 1)} ∪ {(1, −k + 1) : k = 1, 2, … t} which never go below the x-axis. In the case when t = 2, these are Motzkin paths. Hence, we will refer to these paths in general as [t]-Motzkin paths. There is a well-known correspondence between these [t]-Motzkin paths, plane [t]-trees and other combinatorial structures [12]. With an appropriate coloring, these objects become another manifestation of the generalized Catalan numbers. Remark 15. The reader should be careful to distinguish the [t]-Motzkin paths described here from “t-Motzkin paths” that have been described elsewhere in the literature. For instance, in [2] the term “2-Motzkin path” is used to describe a path with step set

{U(1, 1), L_{1}(1, 0), L_{2}(1, 0), D(1, −1)}.

3 3 3 3 3 3 3 3 3

Figure 5: There are 27 + 9 + 9 + 9 + 1 = 55 binomial [3]-Motzkin paths of length 3. Each up step of the form (1, 1) can be just one color; each level step of the form (1, 0) can be one of 3 colors; each down step of the form (1, −1) can be one of 3 colors; each down step of the form (1, −2) can be just one color.

However, here, the step set for [t]-Motzkin paths has cardinality t+1. If we let M_{t}(z) denote the generating function for the number of [t]-Motzkin paths of length n, then M_{1}(z) = C_{1}(z) = 1/(1 − z), M_{2}(z) = M(z) and

M_{3}(z) = 1 + z + 2z^{2} + 5z^{3} + 13z^{4} + 36z^{5} + 104z^{6} + 309z^{7} + ⋯,

is \underline{A036765}. Based on a natural decomposition of [t]-Motzkin paths by initial step, one can easily see that

M_{t}(z) = ∑_{k=0}^{t} z^{k}(M_{t}(z))^{k}.

Definition 16. Let t ≥ 1. A binomial [t]-Motzkin path is a path from (0, 0) to (n, 0) with step set

⋃_{k=0}^{t} \{S_{i}(1, −k + 1) : i = 1, 2, …, \binom{t}{k}\}

= \{S_{1}(1, 1)\} ∪ \{S_{1}(1, 0), …, S\binom{t}{1}(1, 0)\}
∪\{S_{1}(1, −1), …, S\binom{t}{2}(1, −1)\} ∪ …
⋯ ∪ \{S_{1}(1, −k + 1), …, S\binom{t}{k}(1, −k + 1)\} ∪ …
∪\{S_{1}(1, −t + 3), …, S\binom{t}{t−2}(1, −t + 3)\} ∪
\{S_{1}(1, −t + 2), …, S\binom{t}{t−1}(1, −t + 2)\} ∪ \{S_{1}(1, −t + 1)\}

which never goes below the x-axis. That is to say, there are 2^{t} possible steps to choose from. Each step has the form S_{i}(1, −k+1) where k = 0, 1, …, t. Each S_{i}(1, −k+1) is distinguished with a color i where i is between 1 and \binom{t}{k}.

Example 17. See Figure 5 for a depiction of binomial [3]-Motzkin paths of length 3. There are 55 binomial [3]-Motzkin paths of length 3. Since each up step U is one color, each level step L is one of 3 colors, each down step D_{1} of the form (1, −1) is one of 3 colors and the down step D_{2} of the form (1, −2) can only be one color, we have 27 paths of the form LLL, 9 of the form LUD_{1}, 9 of the form ULD_{1}, 9 of the form UD_{1}L and 1 of the form UUD_{2}.

In general, binomial [t]-Motzkin paths are counted by generalized Catalan numbers.

Theorem 18. The generating function for the number of binomial [t]-Motzkin paths of length n is (C_{t}(z))^{t}.

Proof. To see this, suppose M_{t}^{∗}(z) is the generating function for binomial [t]-Motzkin paths. Each binomial [t]-Motzkin path is either (1) empty, (2) of the form LP_{1} where L is a level step and P_{1} is a colored t-Motzkin path, or (3) of the form UP_{1}UP_{2}UP_{3} ⋯ UP_{k−1}D_{k}P_{k} where k = 2, …, t, U is an up step, each P_{i} is a binomial [t]-Motzkin path and D_{k} is a down step of the form (1, −k + 1). Since there are \binom{t}{1} types of level step and \binom{t}{k} types of down step of the form (1, −k + 1), we have

M_{t}^{∗}(z) = 1 + \binom{t}{1}zM_{t}^{∗}(z) + \binom{t}{2}z^{2}(M_{t}^{∗}(z))^{2} + \binom{t}{3}z^{3}(M_{t}^{∗}(z))^{3} + ⋯

= ∑_{k=0}^{t} \binom{t}{k}z^{k}(M_{t}^{∗}(z))^{k}
= (1 + zM_{t}^{∗}(z))^{t},

which implies that

1 + zM_{t}^{∗} = (M_{t}^{∗})^{1/t}.  (28)

Since (C_{t}(z))^{t} satisfies (28) and M_{t}^{∗}(0) = 1 = C_{t}(0), it must be that M_{t}^{∗}(z) = (C_{t}(z))^{t} = (C_{t}(z) − 1)/z.

There is of course a natural bijection ϕ between binomial [t]-Motzkin paths of length n and t-Dyck paths of length t(n + 1). Suppose P is a binomial [t]-Motzkin path. To create ϕ(P), first start with U^{t−1}. Then reading P from left to right, whenever we encounter a step S_{i}(1, −k + 1) with color i, we adjoin a unique subpath P_{k,i} of length t consisting of k down steps of the form D(1, −k + 1) and t − k U’s. Since there are \binom{t}{k} possibilities for the color i and \binom{t}{k} possible paths P_{k,i}, we can indeed assign each color i with a unique path P_{k,i}. Notice that the adjoining of P_{k,i} would add a net of −t(k − 1) to the height of the path. Complete ϕ(P) by adjoining the final step D(1, −t + 1). The resulting path ϕ(P) is a path of length tn + t using U(1, 1)’s and D(1, −k + 1)’s, which never goes below the x-axis, i.e., a t-Dyck path. The inverse map ϕ^{−1} is achieved by reading a t-Dyck from left to right, t consecutive steps at a time (ignoring the first t − 1 U′s and the last D) and then reversing the step to subpath assignment.

It is known that binomial [2]-Motzkin paths having no level steps on the x-axis are counted by the Fine numbers with generating function F (z) = F_{2}(z). Given the bijection ϕ described above, it is clear that a 2-Dyck path with a hill would correspond to binomial [2]-Motzkin paths with at least one level step on the x-axis. For t ≥ 3, we want to give an interpretation of F_{t}(z) in terms of binomial [t]-Motzkin paths which is consistent with the case when t = 2. Considering the map ϕ, one can imagine how a level step on the x-axis in a binomial [t]-Motzkin path could create a hill in a t-Dyck path, but clearly for t ≥ 3, simply disallowing such level steps would not be sufficient to generate F_{t}(z).

Theorem 19. F_{t}(z) is the generating function for the number of binomial [t]-Motzkin paths of length n with the following step restrictions:

1. no level steps allowed on the x-axis and

2. only \binom{t−1}{k−1} colors are allowed for down steps of the form (1, −k + 1) which end on the x-axis.

We may refer to the restricted binomial [t]-Motzkin paths described in Theorem 19 as t-Fine paths.

Proof. Let H_{t}(z) be the generating function for the number of t-Fine paths of length n. First, we will show that H_{t}(z) satisfies:

H_{t}(z) = 1 + zH_{t}(z)[(C_{t}(z))^{t−1} − 1]  (29)

To see this, observe that every t-Fine path is either empty or has a return. If the t-Fine path has a return, then it has the form

(UP_{1})(UP_{2}) ⋯ (UP_{k−1})D_{k}F,

where each P_{i} is a binomial [t]-Motzkin path, D_{k} is the down step of the form (1, −k + 1) incident with the first return and F is a t-Fine path. Since D_{k} can be one of \binom{t−1}{k−1} colors and k = 2, 3, …, or t, we have

H_{t} = 1 + zH_{t} [∑_{k=2}^{t} \binom{t − 1}{k − 1}(zC_{t}^{t})^{k−1}]

= 1 + zH_{t} [∑_{k=1}^{t−1} \binom{t − 1}{k}(C_{t} − 1)^{k}]
= 1 + zH_{t}[((C_{t} − 1) + 1)^{t−1} − 1]
= 1 + zH_{t}[(C_{t})^{t−1} − 1],

which implies that C_{t}^{t−1} = \frac{H_{t} − 1 + zH_{t}}{zH_{t}} or equivalently,

\frac{C_{t} − 1}{zC_{t}} = \frac{H_{t} + zH_{t} − 1}{zH_{t}}.

And on the other hand, we have from Theorem 14 that

\frac{C_{t} − 1}{zC_{t}} = \frac{\frac{F_{t}}{1−zF_{t}} − 1}{z \frac{F_{t}}{1−zF_{t}}} = \frac{F_{t} + zF_{t} − 1}{zF_{t}}.

Hence, given H_{t}(0) = 1 = F_{t}(0), it must be that H_{t}(z) = F_{t}(z).

Finally, we observe that as a direct consequence of Theorem 14 and the fact that C_{t} = 1 + zC_{t}^{t}, we have the following generating function identity for F_{t}(z).

Theorem 20.

1 + zF_{t}^{t} + ∑_{k=0}^{t−1} [\binom{t − 1}{k} + \binom{t}{k + 1}z] (−1)^{k+1}z^{k}F_{t}^{k+1} = 0

Proof. Using Theorem 14, we obtain

C_{t}(z) = 1 + zC_{t}^{t}(z)
⟹ F_{t}(z) = 1 − zF_{t}(z) + zC_{t}^{t−1}(z)F_{t}(z)
⟹ F_{t}(z) = \frac{(1 − zF_{t}(z))^{t}}{(1 − zF_{t}(z))^{t−1}} + \frac{z(F_{t}(z))^{t}}{(1 − zF_{t}(z))^{t−1}}
⟹ F_{t}(z)(1 − zF_{t}(z))^{t−1} = (1 − zF_{t}(z))^{t} + z(F_{t}(z))^{t}

and the result follows from the Binomial Theorem.

5 Conclusions and further work

Our study of returns and hills on t-Dyck paths has shown that, asymptotically speaking, the number of returns is easier to determine than the number of hills. We established that the asymptotic distribution for the number of returns among t-Dyck paths is negative binomial with parameters (2, \frac{t−1}{t}). Furthermore, in response to L. Shapiro’s question, we have established that the probability that a randomly chosen Dyck path has an even number of hills approaches \frac{5}{8} and the probability that a randomly chosen ternary path has an even number of hills approaches \frac{125}{169}. Hence, it is apparently more likely for a ternary path to have an even number of hills than for a Dyck path to have an even number of hills. In this case, we have used a recursive identity for the generalized Fine functions F_{2}(z) and F_{3}(z) to determine the exact probabilities needed to reach our conclusion. While such a recursive identity for F_{t}(z) exists for all t (Theorem 20), the efficiency of its use decreases as t increases. In Section 2.2, we have provided strong evidence that the asymptotic distribution for the number of hills among t-Dyck paths is in fact negative binomial with parameters (2, \frac{t^{t−1}}{t^{t−1}+(t−1)^{t−2}} ) , and it would be very desirable to make this evidence conclusive.

6 Acknowledgments

The authors wish to thank an anonymous referee for valuable suggestions which improved the quality of the paper.

A Initial conditions for L̃_{n}

Here are the computations to determine L̃_{0}, L̃_{1}, and L̃_{2} as initial conditions for the recurrence in (26).

Equation (22) implies that, for n ≥ 1,

t_{n+1,1} = f̃_{n+1,1} − f̃_{n,1} − f̃_{n−1,1} + 2f̃_{n,0} + 3f̃_{n−1,0}  (30)

Dividing both sides of (30) by t_{n+1}, we obtain:

\frac{t_{n+1,1}}{t_{n+1}} = \frac{f̃_{n+1,1}}{t_{n+1}} − \frac{f̃_{n,1}}{t_{n}} · \frac{t_{n}}{t_{n+1}} − \frac{f̃_{n−1,1}}{t_{n−1}} · \frac{t_{n−1}}{t_{n}} · \frac{t_{n}}{t_{n+1}} + 2\frac{f̃_{n,0}}{t_{n}} · \frac{t_{n}}{t_{n+1}} + 3\frac{f̃_{n−1,0}}{t_{n−1}} · \frac{t_{n−1}}{t_{n}} · \frac{t_{n}}{t_{n+1}}
⇒ \frac{4}{9} = L̃_{1} − L̃_{1} (\frac{4}{27}) − L̃_{1} (\frac{4}{27})^{2} + 2L̃_{0} (\frac{4}{27}) + 3L̃_{0} (\frac{4}{27})^{2}

⇒ \frac{4}{9} = L̃_{1} (1 − \frac{4}{27} − (\frac{4}{27})^{2}) + L̃_{0} (2 (\frac{4}{27}) + 3 (\frac{4}{27})^{2})
⇒ \frac{4}{9} = \frac{605}{81}L̃_{1} + \frac{264}{81}L̃_{0}
⇒ 324 = 605L̃_{1} + 264L̃_{0}
⇒ 2^{2} · 3^{4} = 5 · 11^{2}L̃_{1} + 2^{3} · 3 · 11L̃_{0}

Now, if we multiply equation (22) by zT^{2}, we obtain

zT^{4} = zF_{3}^{2}T^{2}(1 − z − z^{2}) + zF_{3}T^{2}(2 + 3z) − 2zT^{2}

Using Theorem 11, we can simplify this to

zT^{4} + 2zT^{2} = (F_{3}^{2} + zF_{3}^{2} − F_{3})(1 − z − z^{2}) + (F_{3} + zF_{3} − 1)(2 + 3z)
⇒ zT^{4} + 2zT^{2} = F_{3}^{2}(1 − 2z^{2} − z^{3}) + F_{3}(1 + 6z + 4z^{2}) − (2 + 3z)

and therefore, we have for n ≥ 2,

t_{n+2,3} + 2t_{n,1} = f̃_{n+1,1} − 2f̃_{n−1,1} − f̃_{n−2,1} + f̃_{n} + 6f̃_{n−1} + 4f̃_{n−2}  (31)

Dividing both sides of (31) by t_{n+1}, we obtain

2 (\frac{4}{27}) + 2 (\frac{4}{9}) (\frac{4}{27}) = L̃_{1} − 2L̃_{1} (\frac{4}{27})^{2} − L̃_{1} (\frac{4}{27})^{3}

+ L̃_{0} (\frac{4}{27}) + 6L̃_{0} (\frac{4}{27})^{2} + 4L̃_{0} (\frac{4}{27})^{3}

⇒ \frac{8 · 13}{3^{5}} = L̃_{1} [1 − 2 (\frac{4}{27})^{2} − (\frac{4}{27})^{3}] + L̃_{0} [\frac{4}{27} + 6 (\frac{4}{27})^{2} + 4 (\frac{4}{27})^{3}]
⇒ 2^{3} · 3^{4} · 13 = 5 · 11^{2} · 31 · L̃_{1} + 2^{2} · 11 · 131 · L̃_{0}

(Note that (20) can be used to conclude that lim_{n→∞} t_{n+2,3}/t_{n+1} = 2.)

With two equations and two unknowns, we can determine L̃_{0} and L̃_{1}.

L̃_{0} = \frac{2^{3}}{11^{2}} = \frac{81}{121}  (32)

L̃_{1} = \frac{2^{2} · 3^{4}}{11^{3}} = \frac{324}{1331}  (33)

Now, equation (21) can be used to determine L̃_{2}. Equation (21) implies that for n ≥ 1,

f̃_{n} + 3f̃_{n−1} = f̃_{n+1,2} − f̃_{n,2} − f̃_{n−1,2} + 2f̃_{n,1} + 3f̃_{n−1,1}  (34)

Dividing both sides by t_{n−1}, we obtain

L̃_{0} (\frac{27}{4}) + 3L̃_{0} = L̃_{2} (\frac{27}{4})^{2} − L̃_{2} (\frac{27}{4}) − L̃_{2} + 2L̃_{1} (\frac{27}{4}) + 3L̃_{1}
\frac{39}{4}L̃_{0} = \frac{605}{16}L̃_{2} + \frac{66}{4}L̃_{1}

⇒ L̃_{2} = \frac{2^{2} · 3^{5}}{11^{4}} = \frac{972}{14641}  (35)

References

[1] E. Barcucci, E. Pergola, R. Pinzani, and S. Rinaldi, ECO method and hill-free generalized Motzkin paths, Sém. Lothar. Combin. 46 (2001/2), Article B46b. Available at

     https://www.emis.de/journals/SLC/wpapers/s46rinaldi.html.

[2] G. Cheon, S. Lee, and L. Shapiro, The Fine numbers refined, European J. Combin. 31 (2010), 120–128.

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

[4] E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math. 241 (2001), 241–265.

[5] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.

[6] I. Gessel and G. Viennot, Binomial determinants, paths, and hook length formulae, Adv. in Math. 58 (1985), 300–321.

[7] R. Graham, D. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1994.

[8] N. Gu, H. Prodinger, and S. Wagner, Bijections for a class of labeled plane trees, Europ. J. Combin. 31 (2010), 720–732.

[9] B. Lindström, On vector representations of induced matroids, Bull. London Math. Soc. 5 (1973), 85–90.

[10] The On-Line Encyclopedia of Integer Sequences, published electronically at

http://oeis.org, 2016.

[11] L. Shapiro, S. Getu, W.-J. Woan, and L. Woodson, The Riordan group, Discrete Math. 34 (1991), 229–239.

[12] R. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05A16, 11B83. Keywords: Catalan number, ternary number, Dyck path, Fine number, Motzkin number, hill, return, lattice path statistics.

(Concerned with sequences \underline{A000108}, \underline{A000957}, \underline{A001006}, \underline{A001764}, \underline{A006013}, \underline{A008292}, \underline{A023053}, \underline{A033184}, \underline{A036765}, \underline{A051255}, \underline{A065600}, \underline{A065601}, \underline{A101371}, \underline{A109971}, and \underline{A110616}.)

Received February 5 2016; revised versions received May 19 2016; June 13 2016. Published in Journal of Integer Sequences, June 15 2016.

Return to Journal of Integer Sequences home page.