A Subfamily of Skew Dyck Paths Related to k-ary Trees

Yuxuan Zhang Department of Statistical Science Duke University Durham, NC 27708 USA

                    yz885@duke.edu

Yan Zhuang Department of Mathematics and Computer Science Davidson College 405 N. Main St. Davidson, NC 28035 USA

                 yazhuang@davidson.edu

Abstract

We introduce a subfamily of skew Dyck paths called box paths and show that they are in bijection with pairs of ternary trees, confirming an observation stated previously on the On-Line Encyclopedia of Integer Sequences. More generally, we define k-box paths, which are in bijection with (k + 1)-tuples of (k + 2)-ary trees. A bijection is given between k-box paths and a subfamily of k_{t}-Dyck paths, as well as a bijection with a subfamily of (k, ℓ)-threshold sequences. We also study the refined enumeration of k-box paths by the number of returns and the number of long ascents. Notably, the distribution of long ascents over k-box paths generalizes the Narayana distribution on Dyck paths, and we find that (k − 3)-box paths with exactly two long ascents provide a combinatorial model for the second k-gonal numbers.

1 Introduction

A lattice path is a path in the integer lattice ℤ^{n} consisting of a sequence of steps from a prescribed step set and satisfying prescribed restrictions. Perhaps the most well-studied among classical lattice paths are Dyck paths. A Dyck path of semilength n is a path in ℤ^{2}—consisting of 2n steps from the step set {(1, 1), (1, −1)}—which starts at the origin, ends on the x-axis, and never traverses below the x-axis. The steps (1, 1) are called up steps and are represented by the letter U, and the (1, −1) are called down steps and represented by D. It is well known that the number of Dyck paths of semilength n is the nth Catalan number C_{n} = \binom{2n}{n}/(n + 1).

In 2010, Deutsch, Munarini, and Rinaldi [4] introduced a generalization of Dyck paths called skew Dyck paths, which are defined in the same way except that we also allow left steps L = (−1, −1) as long as up steps never intersect with left steps. (In other words, we cannot have an up step followed by a left step, or a left step followed by an up step.) Thus, Dyck paths are precisely skew Dyck paths without left steps.

Lattice paths with step set S can be represented as words on the alphabet S satisfying appropriate restrictions. In particular, we represent skew Dyck paths as words w over the alphabet {U, D, L} such that w avoids the contiguous subwords UL and LU, the number of Us in w is equal to the total number of Ds and Ls, and the total number of Ds and Ls in any prefix of w is never more than the number of Us in that prefix. See Figure 1 for an example. We use superscript notation to represent consecutive occurrences of the same step, e.g., U^{3} = UUU. We refer to contiguous subwords as factors, and whenever we refer to a factor in a lattice path, we really mean a factor inside the corresponding word.

Figure 1: The skew Dyck path corresponding to the word UDU^{5}DL^{2}DUDL.

Within lattice path enumeration, there is interest in counting paths by the number of occurrences of certain factors; see [3] for an early work on this topic. For example, the number of Dyck paths of semilength n with exactly j UD-factors (a.k.a. peaks) is equal to the Narayana number

N_{n,j} := \frac{1}{n}\binom{n}{j}\binom{n}{j − 1} = \frac{1}{j}\binom{n − 1}{j − 1}\binom{n}{j − 1}.

Our present work concerns UDL-factors in skew Dyck paths. The array of numbers counting skew Dyck paths by semilength and number of UDL-factors is given in OEIS entry \underline{A128728} [12]. Recently, Prodinger [8] derived the functional equation

x^{2}R^{3} − x(2 − x)R^{2} + (1 − x^{2})R − 1 + x + x^{2} − tx^{2} = 0  (1)

for the bivariate generating function R = R(t, x) whose coefficient of t^{k}x^{n} is the number of skew Dyck paths of semilength n with k UDLs. With a computer algebra system such as Maple, one may use Equation (1) to compute a (truncated) series expansion for R, from which it appears that the coefficient of t^{n}x^{3n−1} is equal to \binom{3n−1}{n}/(3n − 1) for all n ≥ 1. This observation had previously been reported on the OEIS page for \underline{A128728} with the following comment:

              Apparently, T(3k-1,k) = binomial(3k-1,k)/(3k-1).

The starting point of this paper was the first author’s undergraduate honors thesis at Davidson College (supervised by the second author), which (among other things) sought to provide an explanation for this observation. It can be shown that among skew Dyck paths with exactly n UDLs, the shortest paths have semilength 3n − 1. We call such paths box paths of size n. (Visually, a UDL-factor in a skew Dyck path is reminiscient of a box protruding from a down-slope of the path.) See Figure 2 for all box paths of size 3.

Figure 2: All box paths of size 3.

We wish to prove that there are \binom{3n−1}{n}/(3n − 1) box paths of size n. The numbers \binom{3n−1}{n}/(3n − 1) have several established combinatorial interpretations, including pairs of ternary trees with n − 1 total nodes. Thus, it suffices to show that box paths and pairs of ternary trees are in bijection.

More generally, define a k-box path of size n to be a skew Dyck path of semilength (k + 2)n − 1 with exactly n UD^{k}L-factors (so that box paths are 1-box paths). We give a recursive bijection between k-box paths and (k + 1)-tuples of (k + 2)-ary trees; this reduces to the above result for k = 1. While one cannot have a UL-factor in a skew Dyck path, we describe a way to make sense of a “0-box path” as being essentially a Dyck path, so the case k = 0 of our result recovers the well-known fact that Dyck paths are in bijection with binary trees. In this way, we can think of k-box paths as being a generalization of Dyck paths.

This paper is organized as follows. We begin with some preliminary definitions in Section 2. Next, we show in Section 3 that k-box paths of size n are in bijection with (k + 1)-tuples of (k + 2)-ary trees with n − 1 total nodes, the number of which is given by the formula

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

These numbers also count (k +1)_{k}-Dyck paths of size n−1 and (k +2, k)-threshold sequences of length n − 1, which are subfamilies of the k_{t}-Dyck paths introduced by Selkirk [11] and of the (k, ℓ)-threshold sequences introduced by Rusu [10], respectively. In Section 4, we give a simple bijection between k-box paths and (k + 1)_{k}-Dyck paths, and in Section 5, we give one between k-box paths and (k + 2, k)-threshold sequences. Finally, in Sections 6–7, we study the distribution of two statistics over k-box paths—the number of returns and the number of long ascents—and give an exact enumeration formula for each. The latter distribution generalizes the Narayana distribution on Dyck paths, and curiously, k-box paths with exactly two long ascents are shown to be counted by the second (k + 3)-gonal numbers.

2 Preliminaries: k-ary trees and k-Dyck paths

A ternary tree is a rooted tree in which each node has at most three children, which are distinguished as the left child, the middle child, and the right child; see Figure 3 for an example. More generally, a k-ary tree is a tree in which each node has at most k children, all of which are distinguished in the analogous way.

Let T_{n}^{(k)} be the set of k-ary trees with n nodes, and let

C_{k} = C_{k}(x) := ∑_{n=0}^{∞}|T_{n}^{(k)}|x^{n}

be the ordinary generating function for k-ary trees. Note that a k-ary tree is either empty or can be recursively decomposed as a k-tuple of (possibly empty) subtrees, all of which are attached to the root. This leads to the functional equation

C_{k} = 1 + xC_{k}^{k},

Figure 3: A ternary tree with 11 nodes.

from which the formulas

|T_{n}^{(k)}| = [x^{n}] C_{k} = \frac{1}{n}\binom{kn}{n − 1} = \frac{1}{kn + 1}\binom{kn + 1}{n}  (2)

and

[x^{n}] C_{k}^{r} = \frac{r}{n}\binom{kn + r − 1}{n − 1} = \frac{r}{kn + r}\binom{kn + r}{n}  (3)

follow from a straightforward application of Lagrange inversion [6]. Note that the numbers in (3) count r-tuples of k-ary trees with a total of n nodes, and these numbers are called (generalized) Fuss–Catalan numbers and specialize to the Catalan numbers at r = 1 and k = 2.

To make the connection between our skew Dyck paths and k-ary trees, it is easier to work with another family of lattice paths which are in bijection with k-ary trees. Given a positive integer k, a k-Dyck path of size n is a path in ℤ^{2}—with steps U = (1, 1) and D^{(k)} = (k, −k)—that begins at the origin (0, 0), ends at (2kn, 0), and never traverses below the x-axis. Notice that we recover ordinary Dyck paths by setting k = 1, and that the size of a k-Dyck path is equal to its number of D^{(k)} steps.

Every k-Dyck path μ is either the empty path or can be uniquely decomposed in the form

μ = Uμ_{1}Uμ_{2}Uμ_{3} ⋯ Uμ_{k}D^{(k)}μ_{k+1}

where μ_{1}, …, μ_{k+1} are (possibly empty) k-Dyck paths; this is a generalization of the “first return decomposition” for ordinary Dyck paths. Because the decomposition of k-ary trees into subtrees is of the same form, we have a recursive bijection between k-Dyck paths and (k + 1)-ary trees.

Given k ≥ 2, let us call a skew Dyck path an augmented k-Dyck path of size n if it can be obtained by taking a k-Dyck path of size n and replacing each D^{(k)} step with a factor UD^{k−1}LD. See Figure 4 for an example. Clearly, an augmented k-Dyck path cannot have any D or L steps except within a UD^{k−1}LD-factor, so augmented k-Dyck paths of size n are precisely the skew Dyck paths of the form

U^{a_{1}}D^{k−1}LDU^{a_{2}}D^{k−1}LD ⋯ U^{a_{n}}D^{k−1}LD

where a_{1}, a_{2}, …, a_{n} are positive integers. Let D̂_{n}^{(k)} be the set of augmented k-Dyck paths of size n, and D̂^{(k)} := ⨆_{n≥0} D̂_{n}^{(k)}.

⟷

Figure 4: A 3-Dyck path and the corresponding augmented 3-Dyck path.

3 k-box paths and their enumeration

Recall that we defined a box path of size n to be a skew Dyck path of semilength 3n−1 with exactly n UDL-factors. More generally, define a k-box path of size n to be a skew Dyck path of semilength (k + 2)n − 1 with exactly n UD^{k}L-factors. The following proposition shows that k-box paths of size n are the shortest skew Dyck paths with n UD^{k}L-factors.

Proposition 1. Among skew Dyck paths with exactly n UD^{k}L-factors, the paths of smallest semilength are of semilength (k + 2)n − 1.

Proof. Since

\underbrace{U^{k+2}D^{k}LD ⋯ U^{k+2}D^{k}LD}_{n−1 times}U^{k+1}D^{k}L

is a skew Dyck path of semilength (k +2)n−1 with n UD^{k}L-factors, it remains to show that there cannot be a shorter one. Consider an arbitrary skew Dyck path with exactly n UD^{k}Lfactors; note that each UD^{k}L-factor except the last one must be part of a UD^{k}L^{j}D-factor for some positive integer j, as each L step (except the ending step) must be followed by another L step or a D step. This means that we have n − 1 factors of the form UD^{k}L^{j}D along with a UD^{k}L-factor. Note that each factor of the form UD^{k}L^{j}D contributes k + j + 1 to the semilength, whereas the ending UD^{k}L-factor contributes k + 1 to the semilength. And since each j must be at least 1, the semilength must be at least (k +2)(n−1)+k +1 = (k +2)n−1 as desired.

Let B_{n}^{(k)} denote the set of k-box paths of size n, and B^{(k)} := ⨆_{n≥0} B_{n}^{(k)} the set of all k-box paths.

Lemma 2. Every k-box path μ of size n is of the form

U^{a_{1}}D^{k}LD ⋯ U^{a_{n−1}}D^{k}LDU^{a_{n}}D^{k}L

where the a_{1}, a_{2}, …, a_{n} are positive integers. Moreover, as long as a_{1} + a_{2} + ⋯ + a_{n} = (k + 2)n − 1 and no prefix of μ contains fewer Us than the total number of Ds and Ls, then any μ of the form

U^{a_{1}}D^{k}LD ⋯ U^{a_{n−1}}D^{k}LDU^{a_{n}}D^{k}L

is a k-box path of size n.

Proof. This essentially follows from the same reasoning as the proof of Proposition 1. Let μ be a k-box path of size n, so that μ has semilength (k + 2)n − 1 and has n UD^{k}L-factors. As explained in the proof of Proposition 1, each of these UD^{k}L-factors except the last one must be immediately followed by a D step, so we have n − 1 factors of the form UD^{k}LD along with a UD^{k}L-factor. Together, these factors contribute the full (k + 2)n − 1 to the semilength, so μ cannot have any additional D steps or L steps. Therefore, μ must be of the desired form.

Now, assume that μ = U^{a_{1}}D^{k}LD ⋯ U^{a_{n−1}}D^{k}LDU^{a_{n}}D^{k}L satisfies a_{1} + a_{2} + ⋯ + a_{n} = (k + 2)n − 1 and the given prefix condition. These two conditions ensure that μ is a skew Dyck path of semilength (k +2)n−1, and since μ contains exactly n UD^{k}L-factors, it follows that μ is a k-box path of size n.

Remark 3. From Lemma 2 and the correspondence between k-Dyck paths and augmented k-Dyck paths, we see that k-box paths are in bijection with (k + 1)-Dyck paths—which have steps U = (1, 1) and D^{(k+1)} = (k + 1, −k − 1)—but modified so that they end with a special down step D^{(k)} = (k, −k). Equivalently, these are (k + 1)-Dyck paths that end at the line y = k as opposed to the x-axis.

Lemma 2 allows us to establish a decomposition of k-box paths in terms of augmented (k + 1)-Dyck paths. To do so, we need the notion of a return in a skew Dyck path, which is a point on the path where a step ends at the x-axis. Revisiting Figure 2, we see that among box paths of size 3, there are 3 paths with 1 return, 3 paths with 2 returns, and 1 path with 3 returns. More generally, a return to the line y = a is a point where a down step or a left step ends at the line y = a.

Lemma 4. We have

B^{(k)} = { μ_{1}Uμ_{2}U ⋯ μ_{k+1}UD^{k}L : μ_{1}, μ_{2}, …, μ_{k+1} ∈ D̂^{(k+1)} }.

Proof. Let μ ∈ B^{(k)}. Then we can write μ in the desired form in the following way. Let μ_{1} be the prefix of μ up to the penultimate return to the x-axis. (If μ has only one return, then let μ_{1} be empty.) Then, ignoring the next U, let μ_{2} be the prefix of the remaining segment of the path up to the penultimate return to the line y = 1 (again setting μ_{2} to be empty if no such return exists). Then μ_{3}, …, μ_{k+1} are defined in the analogous way. In light of Lemma 2, we see that each μ_{i} must be a skew Dyck path of the form

U^{b_{1}}D^{k}LDU^{b_{2}}D^{k}LD ⋯ U^{b_{m}}D^{k}LD

and is therefore an augmented (k + 1)-Dyck path, as desired.

Conversely, if each μ_{i} is an augmented (k + 1)-Dyck path, then they must each be of the form

U^{b_{1}}D^{k}LDU^{b_{2}}D^{k}LD ⋯ U^{b_{m}}D^{k}LD.

Then μ = μ_{1}Uμ_{2}U ⋯ μ_{k+1}UD^{k}L is of the form

U^{a_{1}}D^{k}LD ⋯ U^{a_{n−1}}D^{k}LDU^{a_{n}}D^{k}L;

moreover, the equation a_{1} + a_{2} + ⋯ + a_{n} = (k + 2)n − 1 and the prefix condition of Lemma 2 follow from the decomposition μ = μ_{1}Uμ_{2}U ⋯ μ_{k+1}UD^{k}L and the fact that each μ_{i} is a skew Dyck path. Then it follows from Lemma 2 that μ is a k-box path.

Theorem 5. The number of k-box paths of size n is equal to the number of (k + 1)-tuples of (k + 2)-ary trees with a total of n − 1 nodes, which is

f_{k,n} := \frac{k + 1}{n − 1}\binom{(k + 2)n − 2}{n − 2} = \frac{1}{(k + 2)n − 1}\binom{(k + 2)n − 1}{n}.

Proof. By Lemma 4, we can uniquely decompose a k-box path of size n as a sequence of k + 1 augmented (k + 1)-Dyck paths with total size n − 1. These are in bijection with (k + 1)-tuples of (k + 1)-Dyck paths with total size n − 1 (we replace each UD^{k}LD-factor with a D^{(k+1)} step), and such paths are in bijection with (k + 2)-ary trees of the same size. The formula \frac{k+1}{n−1} \binom{(k+2)n−2}{n−2} then comes directly from (3), which can be shown to be equal to \frac{1}{(k+2)n−1} \binom{(k+2)n−1}{n} by routine algebraic manipulation.

By taking k = 1, we get that there are \binom{3n−1}{n}/(3n−1) box paths of size n, thus confirming the initial observation which motivated this work.

Remark 6. Our definition of a k-box path is only valid for positive integers k and not for k = 0; after all, a skew Dyck path cannot have a UL-factor as the U and L steps would overlap. Nonetheless, let us examine what would happen if UL-factors were allowed. A “0-box path” would be of the form μUL where μ is an “augmented 1-Dyck path”—i.e., the result of taking a Dyck path and replacing each D step with a ULD. If we delete each ULfactor—that is, we can view the U and L steps as “canceling out”—then the result would be a Dyck path of semilength n − 1 (where n is the number of UL-factors). Conversely, given a Dyck path of semilength n, we can replace each D step with a ULD-factor and append a UL-factor to get a “0-box path” with n UL-factors. Therefore, we can think of a “0-box path” of size n to be a Dyck path of semilength n − 1. Then Theorem 5 recovers the well-known fact that Dyck paths are in bijection with binary trees. Using this interpretation, all of our results later in this paper for k-box paths become valid for k = 0 as well.

Before proceeding, we note that there is a natural subfamily of k-box paths which are equinumerous to (single) (k + 2)-ary trees, namely, those that end with a U^{k+1}D^{k}L-factor. Let us call such paths tailed k-box paths. Note that all 0-box paths are tailed.

Proposition 7. The number of tailed k-box paths of size n is equal to the number of (k + 2)- ary trees with n − 1 nodes, which is

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

Proof. Tailed k-box paths are precisely the k-box paths where μ_{2}, …, μ_{k+1} are all empty in the decomposition given by Lemma 4. Consequently, tailed k-box paths of size n are in bijection with augmented (k + 1)-Dyck paths of size n − 1, which are in bijection with (k + 1)-Dyck paths of size n − 1 and thus (k + 2)-ary trees with n − 1 nodes.

By dividing the formula in Proposition 7 by that in Theorem 5 and simplifying, we find that the proportion of tailed k-box paths among paths in B_{n}^{(k)} is equal to

\frac{((k + 1)n)_{k}}{(k + 1)((k + 2)n − 2)_{k}}

where (x)_{j} denotes the falling factorial (x)_{j} := x(x − 1) ⋯ (x − j + 1). When k = 0, this proportion is always equal to 1, which makes sense in light of Remark 6 because every “0-box path” ends with a UL-factor. For general k, this proportion tends to

lim_{n→∞} \frac{((k + 1)n)_{k}}{(k + 1)((k + 2)n − 2)_{k}} = \frac{(k + 1)^{k−1}}{(k + 2)^{k}}

as n → ∞. In particular, by taking k = 1, we see that approximately 1/3 of box paths of size n end with a UUDL when n is large.

4 A bijection between k-box paths and (k + 1)_{k}-Dyck paths

Recall that a k-Dyck path of size n is a path in ℤ^{2} which begins at the origin (0, 0), ends at (2kn, 0), never traverses below the x-axis, and consists of steps U = (1, 1) and D^{(k)} = (k, −k). A k_{t}-Dyck path of size n (where t is a non-negative integer) is defined in the same way except that the path never traverses below the line y = −t (as opposed to the x-axis), so that we recover k-Dyck paths upon setting t = 0. These generalizations of k-Dyck paths were introduced recently by Selkirk [11] and further studied in [1, 7].

Selkirk found that, for 0 ≤ t ≤ k − 1, the number of k_{t}-Dyck paths of size n is given by the formula

\frac{t + 1}{(k + 1)n + t + 1}\binom{(k + 1)n + t + 1}{n}

[11, Proposition 2.2.2]; comparing with (3), we see that this is the number of (t + 1)-tuples of (k + 1)-ary trees with n total nodes. Given Theorem 5, it follows that k-box paths of size n are equinumerous with (k + 1)_{k}-Dyck paths of size n − 1.

There is a bijection between these paths which is easy to describe. Given a k-box path of size n, we delete the last UD^{k}L-factor and then replace each UD^{k}LD-factor with a D^{(k+1)} step. The result is a prefix of a (k + 1)-Dyck path that ends on the line y = k, and we obtain a (k + 1)_{k}-Dyck path by vertically translating the path down k units, deleting the first k steps of the path, and then horizontally translating the path k units to the left. See Figure 5 for an example. (This bijection does nothing when k = 0, which makes sense because 0-box paths of size n and 1_{0}-Dyck paths of size n − 1 are both Dyck paths of semilength n − 1.)

⟷

Figure 5: A 2-box path and the corresponding 3_{2}-Dyck path.

We note that there is a subfamily of Motzkin paths introduced in [9], called T -Motzkin paths, which are in bijection with pairs of ternary trees. Selkirk gave a bijection between T - Motzkin paths and 2_{1}-Dyck paths [11, Section 8.2.1]. The simplest bijection from T -Motzkin paths to box paths is perhaps obtained by composing Selkirk’s bijection with the inverse of our above bijection for k = 1.

5 A bijection between k-box paths and (k+2, k)-threshold sequences

Given integers n ≥ 1, k ≥ 2, and 0 ≤ ℓ ≤ k − 2, a (k, ℓ)-threshold sequence of length n is a strictly increasing sequence (s_{1}, s_{2}, …, s_{n}) of n integers satisfying ki ≤ s_{i} ≤ kn + ℓ for each i. Threshold sequences were very recently defined and studied by Rusu [10], who showed that (k, ℓ)-threshold sequences of length n are in bijection with (ℓ + 1)-tuples of k-ary trees with n nodes and are therefore another member of the Fuss–Catalan family of combinatorial objects. Below, we give a bijection between k-box paths of size n and (k + 2, k)-threshold sequences of length n − 1.

Let μ = U^{a_{1}}D^{k}LD ⋯ U^{a_{n−1}}D^{k}LDU^{a_{n}}D^{k}L be a k-box path of size n. We claim that the sequence (s_{i})_{1≤i≤n−1} = (s_{1}, s_{2}, …, s_{n−1}) obtained by taking s_{i} = ∑_{j=1}^{i} a_{j} for each 1 ≤ i ≤ n − 1 is a (k + 2, k)-threshold sequence. Clearly this sequence is increasing as each a_{j} is positive, so it suffices to verify that (k + 2)i ≤ s_{i} ≤ (k + 2)(n − 1) + k for each i. Since μ is a k-box path of size n, it has semilength (k + 2)n − 1; this is the number of up steps in μ. Notice that the upper bound (k + 2)(n − 1) + k is equal to (k + 2)n − 2, which is one less than the number of up steps. Because a_{n} ≥ 1 is not accounted for in any of the s_{i}, it follows that

s_{i} + 1 ≤ s_{i} + a_{n} ≤ (k + 2)n − 1

for each i, and thus s_{i} ≤ (k + 2)n − 2. For the lower bound, recall that each UD^{k}Lfactor (except the last one) in μ is immediately followed by a D—hence, each of the U^{a_{i}} for 1 ≤ i ≤ n − 1 is immediately followed by a total of k + 2 down and left steps before encountering another up step. So, if a_{1} + a_{2} + ⋯ + a_{i} = s_{i} were smaller than (k + 2)i, then μ would go below the x-axis. This establishes the lower bound s_{i} ≥ (k + 2)i.

An enumerative combinatorialist will have recognized the map μ ↦ (s_{i})_{1≤i≤n−1} given above as essentially (a restriction of) the classical bijection from compositions to subsets. As such, to recover μ from (s_{i})_{1≤i≤n−1}, we simply take a_{i} = s_{i} − s_{i−1} for each 1 ≤ i ≤ n, where we set s_{0} = 0 and s_{n} = (k + 2)n − 1. It is straightforward to show that this yields a k-box path of size n given any (k + 2, k)-threshold sequence of length n − 1; we leave the details to the reader.

6 Counting k-box paths by returns

Let us now turn our attention to the refined enumeration of k-box paths by statistics, beginning with the number of returns. Define f̀_{k,n,j} to be the number of k-box paths of size n with exactly j returns, and g̀_{k,n,j} the number of augmented k-Dyck paths of size n with exactly j returns. Then take

F̀_{k}(t, x) := ∑_{n=1}^{∞} ∑_{j=1}^{n} f̀_{k,n,j}t^{j}x^{n} and G̀_{k}(t, x) := ∑_{n=0}^{∞} ∑_{j=1}^{n} g̀_{k,n,j}t^{j}x^{n}

to be the bivariate generating functions for counting k-box paths and augmented k-Dyck paths, respectively, by the number of returns. Also let

G_{k}(x) := ∑_{n=0}^{∞} |D̂_{n}^{(k)}|x^{n} = ∑_{n=0}^{∞} \frac{1}{(k + 1)n + 1}\binom{(k + 1)n + 1}{n}x^{n}.

be the ordinary generating function for augmented k-Dyck paths. For simplicity, let us write F̀_{k} = F̀_{k}(t, x), G̀_{k} = G̀_{k}(t, x), and G_{k} = G_{k}(x).

The distribution of the number of returns over k-Dyck paths (also given by the numbers g̀_{k,n,j}) was previously studied by Cameron and McLeod [2]. We need the generating function G̀_{k} in order to derive a formula for f̀_{k,n,j}.

Lemma 8. We have

F̀_{k} = \frac{txG_{k+1}^{k}}{1 − txG_{k+1}^{k+1}} .

Proof. Recall that every augmented k-Dyck path μ is either the empty path or can be uniquely decomposed as

μ = Uμ_{1}Uμ_{2}Uμ_{3} ⋯ Uμ_{k}UD^{k−1}LDμ_{k+1}

where the μ_{1}, …, μ_{k+1} are augmented k-Dyck paths. In this decomposition, observe that the number of returns of μ is one more than the number of returns of μ_{k+1}, and the number of UD^{k−1}LD-factors in μ is one more than the total number of such factors in the μ_{1}, …, μ_{k+1}. Hence, we have the functional equation

G̀_{k} = 1 + txG_{k}^{k}G̀_{k},

which gives us

G̀_{k} = \frac{1}{1 − txG_{k}^{k}} .

From the decomposition for k-box paths given in Lemma 4 and similar reasoning, we see that

F̀_{k} = txG_{k+1}^{k}G̀_{k+1} = \frac{txG_{k+1}^{k}}{1 − txG_{k+1}^{k+1}}

as desired.

Theorem 9. The number of k-box paths of size n with exactly j returns is equal to

f̀_{k,n,j} = \frac{j(k + 1) − 1}{n − j}\binom{(k + 2)n − j − 2}{n − j − 1} = \frac{j(k + 1) − 1}{(k + 2)n − j − 1}\binom{(k + 2)n − j − 1}{n − j}.

Proof. Using Lemma 8 and the formula for Fuss–Catalan numbers (which give the coefficients of G_{k}^{r}), we obtain

[t^{j}x^{n}] F̀_{k} = [t^{j}x^{n}] \frac{txG_{k+1}^{k}}{1 − txG_{k+1}^{k+1}}

= [t^{j}x^{n}] ∑_{j=0}^{∞} t^{j+1}x^{j+1}G_{k+1}^{j(k+1)+k}

= [t^{j}x^{n}] ∑_{j=1}^{∞} t^{j}x^{j}G_{k+1}^{(j−1)(k+1)+k}

= [x^{n−j}] G_{k+1}^{j(k+1)−1}

= \frac{j(k + 1) − 1}{n − j}\binom{(k + 2)(n − j) + j(k + 1) − 2}{n − j − 1}

= \frac{j(k + 1) − 1}{n − j}\binom{(k + 2)n − j − 2}{n − j − 1}

= \frac{j(k + 1) − 1}{(k + 2)n − j − 1}\binom{(k + 2)n − j − 1}{n − j}.

For k = 0, we recover the formula

f̀_{0,n+1,j+1} = \frac{j}{2n − j} \binom{2n − j}{n}

n j  1  2  3  4  5  6  7  8
1  1
2  1  1
3  3  3  1
4  12  12  5  1
5  55  55  25  7  1
6  273  273  130  42  9  1
7  1428 1428  700  245  63  11  1
8  7752 7752 3876 1428  408  88  13  1

Table 1: The number of box paths of size n with j returns.

n j  1  2  3  4  5  6  7  8
1  1
2  2  1
3  9  5  1
4  52  30  8  1
5  340  200  60  11  1
6  2394 1425  456  99  14  1
7  17710 10626 3542  847  147  17  1
8 135720 81900 28080 7150 1400  204  20  1

Table 2: The number of 2-box paths of size n with j returns.

for the number of Dyck paths of semilength n with j returns [3, Section 6.6]. The arrays of the numbers f̀_{k,n,j} for k = 1 and k = 2 are displayed in Tables 1–2. The array for k = 1 can be found in entry \underline{A143603} of the OEIS [12].

Remark 10. Notice that each row of Tables 1–2 is (weakly) decreasing. This observation can be confirmed by calculating

f̀_{k,n,j} − f̀_{k,n,j+1} = \frac{((k + 1)j − 2)((k + 2)n − j − 3)!}{((k + 1)n − 2)!(n − j)!},

which is non-negative for all k ≥ 1, n ≥ 2, and 1 ≤ j ≤ n − 1. There is also a simple combinatorial proof for this fact by way of an injection from paths in B_{n}^{(k)} with j + 1 returns to those with j returns. Given μ ∈ B_{n}^{(k)} with j + 1 returns, we can obtain a path μ′ ∈ B_{n}^{(k)} with j returns by deleting the first U step after the first return and inserting it at the very beginning of the path. Then the position where μ had its first return is where μ′ has its first return to the line y = 1, and so we can recover μ from μ′ by deleting the first U step and inserting it immediately after the first return to y = 1. See Figure 6 for an example. Note that this reverse procedure is not well-defined in general, since the first return to y = 1 might be in the middle of a D^{k}LD-factor or the ending D^{k}L-factor. (When k = 0, this happens when our Dyck path μ′ begins with a UD-factor.) Thus, this injection is not a bijection.

⟷

Figure 6: A 2-box path with 2 returns and the corresponding 2-box path with 1 return.

However, when k = 1 and j = 1, we claim that this injection is in fact a bijection. Let μ′ ∈ B_{n}^{(1)} (for some n ≥ 2) have only 1 return. The first return to the line y = 1 cannot be followed by a L step, because then we are forced to have μ′ = UUDL which is of size n = 1. Moreover, the first return to the line y = 1 cannot be preceded by a L step; otherwise, that L step would be followed by a D step which would end the path (since μ′ has only 1 return), yet box paths must end with an L. Therefore, the first return to y = 1 is not in the middle of a DLD-factor or the ending DL-factor, so the reverse procedure described above is well-defined for all paths in B_{n}^{(1)} with 1 return. Hence f̀_{1,n,1} = f̀_{1,n,2} for all n ≥ 2, as suggested by the j = 1 and j = 2 columns of Table 1. Similarly, in the k = 0 case, a Dyck path of semilength n ≥ 2 with only 1 return cannot begin with a UD-factor, so we have f̀_{0,n,2} = f̀_{0,n,3} for all n ≥ 3.

Recall that f_{k,n} denotes the total number of k-box paths of size n. Using our formulas for f_{k,n} and f̀_{k,n,j} from Theorems 5 and 9, together with the sum command in Maple, we were able to find closed-form formulas for the expressions

\frac{∑_{j=1}^{n} jf̀_{k,n,j}}{f_{k,n}} and \frac{∑_{j=1}^{n} j^{2}f̀_{k,n,j}}{f_{k,n}} − (\frac{∑_{j=1}^{n} jf̀_{k,n,j}}{f_{k,n}} )^{2}

giving the average value and variance, respectively, for the number of returns.

Corollary 11. Among k-box paths of size n, the average number of returns is

\frac{(k + 2)((k + 2)n − 1)}{(k + 1)((k + 1)n + 1)}

and the variance in the number of returns is

\frac{(k + 2)((k + 2)n − 1)((2k + 1)(k + 1)n − 2)(n − 1)}{(k + 1)^{2}((k + 1)n + 1)^{2}((k + 1)n + 2)}.

As n → ∞, the average tends to (k+2)^{2}/(k+1)^{2} and the variance to (2k+1)(k+2)^{2}/(k+ 1)^{4}, which are approximately 1 and 0, respectively, when k is large.

We note that the average number of returns of a k-box path is one more than the number of returns to the line y = −k of the (k + 1)_{k}-Dyck path obtained via the bijection from Section 4. In fact, Corollary 11 is equivalent to the mean and variance formulas (specialized appropriately) from Selkirk’s Propositions 6.2.1 and 6.2.2 [11]. (Selkirk did not derive an exact enumeration formula for k_{t}-Dyck paths with a given number of returns to y = −t.)

7 Counting k-box paths by long ascents

As mentioned in the introduction, the number of peaks (UD-factors) is another statistic whose distribution over Dyck paths is well known. However, a k-box path of size n has exactly n peaks, so simply counting k-box paths by peaks does not yield anything new. Another parameter is the number of ascents: maximal consecutive subsequences of up steps. Ascents and peaks coincide in Dyck paths and skew Dyck paths—every ascent ends in a peak and every peak is at the end of an ascent—although they have different distributions on some other families of lattice paths like Motzkin paths. Since it is also true that a k-box path of size n has exactly n ascents, let us instead count k-box paths by the number of long ascents: ascents consisting of at least two up steps.

Let f́_{k,n,j} be the number of k-box paths of size n with exactly j long ascents, and ǵ_{k,n,j} the number of augmented k-Dyck paths of size n with exactly j long ascents. Then define the bivariate generating functions

F́_{k}(t, x) := ∑_{n=1}^{∞} ∑_{j=1}^{n} f́_{k,n,j}t^{j}x^{n} and Ǵ_{k}(t, x) := ∑_{n=0}^{∞} ∑_{j=1}^{n} ǵ_{k,n,j}t^{j}x^{n};

we write F́_{k} = F́_{k}(t, x) and Ǵ_{k} = Ǵ_{k}(t, x) for simplicity.

Lemma 12. We have the functional equations

F́_{k} = xǴ_{k+1}^{k}(Ǵ_{k+1} − 1 + t)  (4)

and

Ǵ_{k} = 1 + xǴ_{k}^{k}(Ǵ_{k} − 1 + t).  (5)

Proof. We begin by proving (5). Recall that every augmented k-Dyck path μ is either the empty path (which contributes the 1 on the right-hand side) or can be uniquely decomposed as

μ = Uμ_{1}Uμ_{2}Uμ_{3} ⋯ Uμ_{k}UD^{k−1}LDμ_{k+1}

where the μ_{1}, …, μ_{k+1} are augmented k-Dyck paths. Observe the following:

• The number of UD^{k−1}LD-factors in μ is one more than the total number of such factors in the μ_{1}, …, μ_{k+1}.

• If μ_{k} is nonempty, then long ascents of μ are in correspondence with long ascents of the μ_{1}, …, μ_{k+1}. Otherwise, if μ_{k} is empty, then the number of long ascents in μ is exactly one more than the total number of long ascents in the μ_{1}, …, μ_{k+1}.

Thus we have (5). Equation (4) follows from the decomposition given by Lemma 4 and similar reasoning.

Theorem 13. The number of k-box paths of size n with exactly j long ascents is equal to

f́_{k,n,j} = \frac{1}{j}\binom{(k + 1)n − 2}{j − 1}\binom{n − 1}{j − 1}.

While we are mainly interested in the numbers f́_{k,n,j}, we note that a formula for ǵ_{k,n,j} is obtained by specializing (6) below at r = 1.

Proof. Let G̃_{k} := Ǵ_{k} − 1. Then substituting Ǵ_{k} = G̃_{k} + 1 into (5) and simplifying gives us

G̃_{k} = x(G̃_{k} + 1)^{k}(G̃_{k} + t) = xR(G̃_{k})

where R(u) = (u + 1)^{k}(u + t). Let ϕ(u) = (u + 1)^{r}. Applying Lagrange inversion [6], we obtain

[t^{j}x^{n}] Ǵ_{k}^{r} = [t^{j}x^{n}] (G̃_{k} + 1)^{r}

= [t^{j}x^{n}] ϕ(G̃_{k})

= \frac{1}{n} [t^{j}u^{n−1}] ϕ′(u)R(u)^{n}

= \frac{r}{n} [t^{j}u^{n−1}] (u + 1)^{kn+r−1}(u + t)^{n}

= \frac{r}{n} [t^{j}u^{n−1}] ∑_{i=0}^{kn+r−1} \binom{kn + r − 1}{i}u^{i} ∑_{l=0}^{n} \binom{n}{l}u^{n−l}t^{l}

= \frac{r}{n} [t^{j}u^{n−1}] ∑_{l=0}^{n} ∑_{i=0}^{kn+r−1} \binom{kn + r − 1}{i}\binom{n}{l}t^{l}u^{n−l+i}

= \frac{r}{n} [t^{j}u^{n−1}] ∑_{l=0}^{n} ∑_{m=n−l}^{(k+1)n+r−l−1} \binom{kn + r − 1}{m + l − n}\binom{n}{l}t^{l}u^{m}

= \frac{r}{n}\binom{kn + r − 1}{j − 1}\binom{n}{j}.  (6)

Now, from (4), we have

F́_{k} = xǴ_{k+1}^{k+1} − xǴ_{k+1}^{k} + xtǴ_{k+1}^{k}.

n j  1  2  3  4  5  6  7  8
1  1
2  1  1
3  1  4  2
4  1  9  15  5
5  1  16  56  56  14
6  1  25  150 300 210  42
7  1  36  330 1100 1485 792 132
8  1  49  637 3185 7007 7007 3003 429

Table 3: The number of box paths of size n with j long ascents.

Using (6), we obtain

[t^{j}x^{n}] F́_{k} = [t^{j}x^{n−1}] Ǵ_{k+1}^{k+1} − [t^{j}x^{n−1}] Ǵ_{k+1}^{k} + [t^{j−1}x^{n−1}] Ǵ_{k+1}^{k}

= \frac{k + 1}{n − 1}\binom{(k + 1)n − 1}{j − 2}\binom{n − 1}{j − 1} − \frac{k}{n − 1}\binom{(k + 1)n − 2}{j − 2}\binom{n − 1}{j − 1}

+ \frac{k}{n − 1}\binom{(k + 1)n − 2}{j − 1}\binom{n − 1}{j};

this simplifies to the desired formula for f́_{k,n,j} (as can be verified using Maple).

Observe that the f́_{k,n,j} specialized at k = 0 are Narayana numbers; more precisely, we have f́_{0,n,j} = N_{n−1,j} for all n ≥ 2 and 1 ≤ j ≤ n. This is because, in the k = 0 case, all ascents are long ascents, and ascents in Dyck paths correspond directly to peaks (as noted earlier).

The arrays of the numbers f́_{k,n,j} for k = 1 and k = 2 are displayed in Tables 3–4.

Remark 14. Let us record and discuss a few observations from Tables 3–4.

• The main diagonal of Table 3 consists of Catalan numbers and that of Table 4 enumerates box paths. In general, the numbers

f́_{k+1,n,n} = \frac{1}{n}\binom{(k + 2)n − 2}{n − 1} = \frac{1}{(k + 2)n − 1}\binom{(k + 2)n − 1}{n} = f_{k,n}

count k-box paths of size n. In fact, there is a simple bijection between k-box paths of size n and (k + 1)-box paths of size n with all ascents long: we replace every UD^{k}Lfactor with a UUD^{k+1}L-factor. (If k = 0, then we replace each D with a UUDLD and then append a UUDL to the end of the path.)

n j  1  2  3  4  5  6  7  8
1  1
2  1  2
3  1  7  7
4  1  15  45  30
5  1  26  156 286 143
6  1  40  400 1400 1820 728
7  1  57  855 4845 11628 11628 3876
8  1  77 1617 13475 51205 92169 74613 21318

Table 4: The number of 2-box paths of size n with j long ascents.

• The j = 2 column of Table 3 consists of perfect squares and that of Table 4 consists of second pentagonal numbers. These are the k = 4, 5 cases of the second k-gonal numbers [5, Section 1.8], which are defined by taking the formula

\frac{n}{2}((k − 2)n − (k − 4))

for the ordinary k-gonal numbers and replacing n with −n. More generally, we have

f́_{k,n+1,2} = \frac{1}{2}((k + 1)(n + 1) − 2)n

= \frac{n}{2}((k + 3) − 4 + ((k + 3) − 2)n)

which forms the sequence of second (k+3)-gonal numbers. The second k-gonal numbers have been well studied from the perspective of number theory, but we are not aware of any previous combinatorial interpretation for these numbers that are valid for general values of k. Hence, this result seems interesting enough for us to state it as a theorem below.

• Table 3 consists of three pairs of consecutive repeating numbers, each three rows apart: (1, 1), (56, 56), and (7007, 7007). Similarly, Table 4 has (7, 7) and (11628, 11628), which are four rows apart. In general, we have

f́_{k,(k+2)i−1,(k+1)i−1} = f́_{k,(k+2)i−1,(k+1)i}

for all k, i ≥ 1, as can be checked using Theorem 13. Is there a bijective proof?

Theorem 15. For all k ≥ 3 and n ≥ 1, the nth second k-gonal number is equal to the number f́_{k−3,n+1,2} of (k − 3)-box paths of size n + 1 with exactly two long ascents.

Remark 16. It can be verified that

(f́_{k,n,j})^{2} − f́_{k,n,j−1}f́_{k,n,j+1}

= \frac{n(2(k + 1)n + k − (k + 2)j)}{(n − j + 1)j^{2}(j + 1)((k + 1)n + j)}\binom{(k + 1)n − 2}{j − 1}^{2}\binom{n − 1}{j − 1}^{2} > 0

for all n ≥ 2, k ≥ 0, and 1 < j < n. In other words, for fixed n and k, the sequences {f́_{k,n,j}}_{0≤j<n} are log-concave and thus unimodal. It would be interesting to find a combinatorial proof for log-concavity via constructing an appropriate injection.

As with the case with returns, we can use our formulas for f́_{k,n,j} and f_{k,n} along with the sum command in Maple to obtain a closed expression for the average number of long ascents. However, we were unable to use Maple to evaluate the summation ∑_{j=1}^{n} j^{2}f́_{k,n,j} needed for the variance. Instead, we evaluate this summation directly with the help of Vandermonde’s identity

∑_{j=0}^{r} \binom{p}{j}\binom{q}{r − j} = \binom{p + q}{r}.

This approach also allows us to evaluate ∑_{j=1}^{n} jf́_{k,n,j} which is needed for the mean, and so we demonstrate both for the sake of completeness.

Lemma 17. We have

∑_{j=1}^{n} jf́_{k,n,j} = \binom{(k + 2)n − 3}{n − 1} and ∑_{j=1}^{n} j^{2}f́_{k,n,j} = \frac{(k + 1)n^{2} − n − 1}{(k + 2)n − 3}\binom{(k + 2)n − 3}{n − 1}.

Proof. First, observe that setting p = (k + 1)n − 2 and q = r = n − 1 in Vandermonde’s identity yields

∑_{j=0}^{n−1} \binom{(k + 1)n − 2}{j}\binom{n − 1}{j} = \binom{(k + 2)n − 3}{n − 1}.  (7)

We also have

∑_{j=0}^{n−1} j\binom{(k + 1)n − 2}{j}\binom{n − 1}{j} = ((k + 1)n − 2) ∑_{j=0}^{n−1} \binom{(k + 1)n − 3}{j − 1}\binom{n − 1}{j}

= ((k + 1)n − 2) ∑_{j=0}^{n−2} \binom{(k + 1)n − 3}{j}\binom{n − 1}{j + 1}

= ((k + 1)n − 2) ∑_{j=0}^{n−2} \binom{(k + 1)n − 3}{j}\binom{n − 1}{n − j − 2}

= ((k + 1)n − 2)\binom{(k + 2)n − 4}{n − 2},  (8)

where the last equality is Vandermonde’s identity at p = (k+1)n−3, q = n−1, and r = n−2. Using (7), we obtain

∑_{j=1}^{n} jf́_{k,n,j} = ∑_{j=1}^{n} \binom{(k + 1)n − 2}{j − 1}\binom{n − 1}{j − 1}

= ∑_{j=0}^{n−1} \binom{(k + 1)n − 2}{j}\binom{n − 1}{j}

= \binom{(k + 2)n − 3}{n − 1},

and using both (7) and (8), we have

∑_{j=1}^{n} j^{2}f́_{k,n,j} = ∑_{j=1}^{n} j\binom{(k + 1)n − 2}{j − 1}\binom{n − 1}{j − 1}

= ∑_{j=0}^{n−1}(j + 1)\binom{(k + 1)n − 2}{j}\binom{n − 1}{j}

= ∑_{j=0}^{n−1} j\binom{(k + 1)n − 2}{j}\binom{n − 1}{j} + ∑_{j=0}^{n−1} \binom{(k + 1)n − 2}{j}\binom{n − 1}{j}

= ((k + 1)n − 2)\binom{(k + 2)n − 4}{n − 2} + \binom{(k + 2)n − 3}{n − 1}

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

Lemma 17 and Theorem 5 lead immediately to the following.

Proposition 18. Among k-box paths of size n, the average number of long ascents is

\frac{n((k + 1)n − 1)}{(k + 2)n − 2}

and the variance in the number of long ascents is

\frac{((k + 1)n − 1)((k + 1)n − 2)n(n − 1)}{((k + 2)n − 2)^{2}((k + 2)n − 3)}.

For large n, the expected number of long ascents is approximately (k + 1)n/(k + 2) and the variance is approximately (k + 1)^{2}n/(k + 2)^{3}.

Returning to the connection between k-box paths and k_{t}-Dyck paths, let μ be a k-box path and μ′ the associated (k +1)_{k}-Dyck path under the bijection from Section 4. If the final ascent of μ is long, then the number of long ascents of μ is one more than the number of peaks of μ′. Otherwise, if the final ascent of μ has length 1, then the number of long ascents of μ is equal to the number of peaks of μ′. Selkirk gives mean and variance formulas for the number of peaks in k_{t}-Dyck paths, which does not translate directly to Proposition 18 but come close, due to the slight difference between peaks in (k + 1)_{k}-Dyck paths and long ascents in k-box paths.

8 Acknowledgments

The work in this paper was initiated as part of the first author’s honors thesis project at Davidson College (under the supervision of the second author); we thank Heather Smith Blake, Claire Merriman, Jonad Pulaj, and Carl Yerger for serving on the first author’s thesis committee and giving feedback on his work. We also thank Ira Gessel for pointing out the applicability of Vandermonde’s identity in proving Lemma 17, Sarah Selkirk for her generous feedback on an earlier draft of this manuscript, and an anonymous referee for their suggestions. The second author was partially supported by an AMS-Simons Travel Grant and NSF grant DMS-2316181.

References

[1] Andrei Asinowski, Benjamin Hackl, and Sarah J. Selkirk, Down-step statistics in generalized Dyck paths, Discrete Math. Theor. Comput. Sci. 24(1) (2022), Paper No. 17.

[2] Naiomi T. Cameron and Jillian E. McLeod, Returns and hills on generalized Dyck paths, J. Integer Sequences 19 (2016), Article 16.6.1.

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

[4] Emeric Deutsch, Emanuele Munarini, and Simone Rinaldi, Skew Dyck paths, J. Statist. Plann. Inference 140 (2010), 2191–2203.

[5] Elena Deza and Michel Marie Deza, Figurate numbers, World Scientific Publishing Co., 2012.

[6] Ira M. Gessel, Lagrange inversion, J. Combin. Theory Ser. A 144 (2016), 212–249.

[7] Clemens Heuberger, Sarah J. Selkirk, and Stephan Wagner, Enumeration of generalized Dyck paths based on the height of down-steps modulo k, Electron. J. Combin. 30(2023), Paper No. 1.26.

[8] Helmut Prodinger, Skew Dyck paths without up-down-left, Art Discrete Appl. Math. 7 (2024), Paper No. 1.01.

[9] Helmut Prodinger, Sarah J. Selkirk, and Stephan Wagner, On two subclasses of Motzkin paths and their relation to ternary trees. In Algorithmic Combinatorics: Enumerative Combinatorics, Special Functions and Computer Algebra—In Honour of Peter Paule on his 60th Birthday, Texts Monogr. Symbol. Comput., pp. 297–316. Springer, 2020.

[10] Irena Rusu, Raney numbers, threshold sequences and Motzkin-like paths, Discrete Math. 345 (2022), Paper No. 113065.

[11] Sarah Jane Selkirk, On a generalisation of k-Dyck paths, Master’s thesis, Stellenbosch University, 2019.

[12] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electroni-

    cally at https://oeis.org.

2020 Mathematics Subject Classification: Primary 05A15; Secondary 05A10, 05A19. Keywords: skew Dyck path, k-ary tree, k_{t}-Dyck path, threshold sequence, Narayana number, second k-gonal number.

(Concerned with sequences \underline{A128728} and \underline{A143603}.)

Received August 1 2023; revised version received November 21 2023. Published in Journal of Integer Sequences, January 19 2024.

Return to Journal of Integer Sequences home page.