Raised k-Dyck Paths

Paul Drube Valparaiso University Valparaiso, IN 46383 USA

                 paul.drube@valpo.edu

Abstract

Raised k-Dyck paths are a generalization of k-Dyck paths that may both begin and end at nonzero height. In this paper, we develop closed formulas for the number of raised k-Dyck paths from (0, α) to (ℓ, β), for all height pairs α, β ≥ 0, all lengths ℓ ≥ 0, and all k ≥ 2. This represents a new approach to the enumeration of “simple paths with linear boundaries of rational slope”, as discussed by Krattenthaler in his Handbook of Enumerative Combinatorics. We then expand upon Krattenthaler’s results by enumerating raised k-Dyck paths with a fixed number of returns to ground, a fixed minimum height, and a fixed maximum height, presenting generating functions when closed formulas are not tractable. Specializing our results to either k = 2 or to α < k reveal further connections with preexisting results about height-bounded Dyck paths and “Dyck paths with a negative boundary”, respectively.

1 Introduction

For k ≥ 2, a k-Dyck path of length ℓ and height h is an integer lattice path from (0, 0) to (ℓ, h) that uses steps {U = (1, 1), D = (1, 1 − k)} and stays weakly above the line y = 0. One may verify that the terminal point of every k-Dyck path must satisfy ℓ ≡ h (mod k). Thus we restrict our attention to k-Dyck paths of length kn + h and height h, denoting the collection of all k-Dyck paths of length kn + h and height h by D_{n,h}^{k}.^{1}

It is well known that k-Dyck paths of length kn and height 0 are enumerated by the k-Catalan numbers (or Fuss-Catalan numbers), a one-parameter generalization of the Catalan numbers given by C_{n}^{k} = \frac{1}{kn+1} \binom{kn+1}{n} for all k ≥ 2 and n ≥ 0. In particular, |D_{n,0}^{k}| = C_{n}^{k} for all k ≥ 2 and n ≥ 0. In the case of k = 2, this corresponds to the classic combinatorial interpretation of the Catalan numbers by Dyck paths of length 2n and height 0. For more information about the k-Catalan numbers and their combinatorial interpretations, see Hilton and Pedersen [6], Heubach, Li, and Mansour [5], and Mansour and Ramirez [8]. For even more details about the classic Catalan numbers, see Stanley [12].

1k-Dyck paths of length kn and height km are often referred to as k-Dyck paths of “semi-length” n and “semi-height” m, with D_{n,m}^{k} also sometimes being used to refer to such paths.

Now let C_{k}(t) = ∑_{n=0}^{∞} C_{n}^{k}t^{n} be the ordinary generating function for the k-Catalan numbers. As shown by Hilton and Pedersen [6], the k-Catalan numbers satisfy C_{n+1}^{k} = ∑_{i_{1}+···+i_{k}=n} C_{i_{1}} ⋯ C_{i_{k}} for all n ≥ 0, implying that these generating functions obey C_{k}(t) = tC_{k}(t)^{k} + 1. If we use [t^{n}]p(t) to denote the coefficient of t^{n} in the power series p(t), another standard result asserts |D_{n,h}^{k}| = [t^{n}]C_{k}(t)^{h+1} for all n, h ≥ 0. See Figure 1 for the decomposition that yields this result.

\begin{matrix}P_{0} \\ P_{1} \\ ⋯ \\ P_{h} \end{matrix}

Figure 1: A k-Dyck path P of height h decomposed into a sequence of h + 1 paths P_{i} of height 0, according to the rightmost U steps at each height. Note that some of the P_{i} may be empty.

Also proven by Hilton and Pedersen [6] is that [t^{n}]C_{k}(t)^{r} = \frac{r}{kn+r} \binom{kn+r}{n} = R_{k,r}(n) for all k ≥ 2, n ≥ 0, and r ≥ 1. Here the notation R_{k,r}(n) corresponds to the Raney number (two-parameter Fuss-Catalan number). This gives the closed formula

|D_{n,h}^{k}| = [t^{n}]C_{k}(t)^{h+1} = \frac{h + 1}{kn + h + 1}\binom{kn + h + 1}{n}.  (1)

The primary goal of this paper is to generalize the closed formula of (1) to generalized k-Dyck paths that may begin (as well as end) at any non-zero height, objects that we informally refer to as “raised k-Dyck paths”. These raised k-Dyck paths may be interpreted as a natural generalization of the “k-Dyck paths with negative boundary” (or k_{t}-Dyck paths) investigated by Selkirk [10], Asinowski, Hackl, and Selkirk [1], and Prodinger [9], although our results are developed in such a manner that we need not restrict our attention to starting heights less than k. Raised k-Dyck paths may also be shown to be equivalent to “simple paths with linear boundaries of rational slope”, as investigated by Krattenthaler [7, Section 10.4]

This paper is organized as follows. Section 2 is dominated by our derivation of generating functions and closed formulas for the number of raised k-Dyck paths of arbitrary starting/ending height. This is accomplished via multivariate generating functions and utilizes the generating functions C_{k}(t) for the k-Catalan numbers. In Section 3, we then develop closed formulas for the number of raised k-Dyck paths with a fixed minimum height and a fixed number of returns. In Section 4, we use our results to derive entirely new generating functions for the number of k-Dyck paths of bounded height, a topic where all previous investigations appear to be limited to the k = 2 case or do not account for general starting/ending heights (see [3, 2] for recent discussions concerning k-Dyck paths of bounded height).

2 Raised k-Dyck paths

Once again fix k ≥ 2. For α, β ≥ 0, a raised k-Dyck path of length ℓ and shape (α, β) is an integer lattice path from (0, α) to (ℓ, β) that uses steps {U = (1, 1), D = (1, 1−k)} and stays weakly above the line y = 0. The terminal point of such a path must satisfy ℓ ≡ (β − α) (mod k), justifying our restriction to k-Dyck paths of length kn + β − α and shape (α, β). Denote the set of all k-Dyck paths of length kn+β −α and shape (α, β) by D_{n,(α,β)}^{k}, and then define |D_{n,(α,β)}^{k}| = C_{n,(α,β)}^{k}. Notice that all elements of D_{n,(α,β)}^{k} contain precisely n + β − α up steps and n down steps, meaning that the “n index” of a particular path corresponds to its number of D steps.

It is clear that D_{n,(0,β)}^{k} = D_{n,β}^{k}. It is also clear that D_{n,(β,β)}^{k} is in bijection with integer lattice paths from (0, 0) to (kn, 0) that use step set {U, D} and stay weakly above the line y = −β. Horizontal reflection then places D_{n,(β,β)}^{k} in bijection with the k_{β}-Dyck paths of Selkirk [10] and Asinowski, Hackl, and Selkirk [1]. More generally, whenever α ≥ β, the set D_{n,(α,β)}^{k} is in bijection with generalized k-Dyck paths from (0, 0) to (kn + β, 0) that stay weakly above y = −β and begin with at least α consecutive U steps. This gives additional bijections between our sets and some of the k_{β}-Dyck paths studied by Prodinger [9].

There also exists a bijection between D_{n,(α,β)}^{k} and the “simple paths with linear boundaries of rational slope” considered by Krattenthaler [7]. For non-negative integers μ and a pair of points (a, b), (c, d) satisfying a ≥ μb, c ≥ μd, Krattenthaler defines L((a, b) → (c, d) | x ≥ μy) to be the set of integer lattice paths from (a, b) to (c, d) that use steps {E = (1, 0), N = (0, 1)} and stay weakly below x = μy. One may show |D_{n,(α,β)}^{k}| = C_{n(α,β)}^{k} = |L((0, −β) → (n, kn − α) | x ≥ ky)| via the bijection Ψ that takes the path P ∈ D_{n,(α,β)}^{k} with steps P = s_{1}s_{2} ⋯ s_{ℓ} to the lattice path Ψ(P) ∈ L((0, −β) → (n, kn − α) | x ≥ ky) with steps Ψ(P) = ψ(s_{ℓ}) ⋯ ψ(s_{2})ψ(s_{1}), where ψ(U) = N and ψ(D) = E. For an example of this bijection, see Figure 2.

Before proceeding to our enumerations, notice that a trivial path of length ℓ = 0 only exists when n = 0 and α = β. In this case we have C_{0,(β,β)}^{k} = 1. Also note that C_{n,(α,β)}^{k} = 0 whenever kn + β − α < 0. This corresponds to the fact that every element of D_{n,(α,β)}^{k} with α > β requires some minimal number of D steps in order to end at the correct height.

Fundamental to much of our approach is the following recurrence. In this and subsequent results, we automatically set C_{n,(α,β)}^{k} = 0 whenever α < 0 or β < 0.

Proposition 1. For all k ≥ 2, n ≥ 0, and α, β ≥ 0 other than n = 0 and α = β, we have

C_{n,(α,β)}^{k} = C_{n,(α+1,β)}^{k} + C_{n−1,(α−k+1,β)}^{k}.

\begin{matrix}s_{1} \\ s_{7} \end{matrix}  ⇔  \begin{matrix}(2, 3) \\ (0, −2) \\ ψ(s_{1}) \\ ψ(s_{7}) \end{matrix}

Figure 2: An example of the bijection Ψ between raised k-Dyck paths D_{n,(α,β)}^{k} and simple paths in L((0, −β) → (n, kn − α) | x ≥ ky). Here k = 3, n = 2, α = 1, and β = 2.

Proof. Observe that n = 0 and α = β corresponds to trivial paths, which cannot be decomposed as outlined below. Excepting that case, let S_{U} be the subset of D_{n,(α,β)}^{k} including all paths that begin with a U step, and let S_{D} be the subset of D_{n,(α,β)}^{k} including all paths that begin with a D step. Eliminating the first step of every P ∈ S_{U} gives a path of length kn + β − α − 1 = kn + β − (α + 1) and shape (α + 1, β), placing S_{U} in bijection with D_{n,(α+1,β)}^{k}. Eliminating the first step of every P ∈ S_{D} gives a path of length kn + β − α − 1 = k(n − 1) + β − (α − k + 1) and shape (α − k + 1, β), placing S_{D} in bijection with D_{n−1,(α−k+1,β)}^{k}.

Fully utilizing the recurrence of Proposition 1 requires multivariate generating functions. Simultaneously accounting for all shapes (α, β), define C_{k}(q, r, t) = ∑_{α,β,n≥0} C_{n,(α,β)}^{k}q^{α}r^{β}t^{n}. For reasons that will become clear in upcoming sections, we separately denote the ordinary generating function for paths of fixed shape (α, β) by C_{k,(α,β)}(t) = ∑_{n≥0} C_{n,(α,β)}^{k}t^{n} = [q^{α}r^{β}]C_{k}(q, r, t).

For fixed shape (α, β), observe that the order of C_{k,(α,β)}(t) is the smallest non-negative integer n that such n ≥ \frac{α−β}{k−1} , corresponding to the minimal number of D steps in a path of shape (α, β). In particular, if α ≤ β then C_{k,(α,β)}(t) has order 0. When α ≤ β, the minimal coefficient is always [t^{0}]C_{k,(α,β)}(t) = 1, corresponding to the unique path of shape (α, β) with zero D steps. When α > β, the minimal coefficient of C_{k,(α,β)}(t) may or may not be 1.

Proposition 1 may be used to derive the following relationship for C_{k}(q, r, t):

Theorem 2. For all k ≥ 2, we have

C_{k}(q, r, t) = \frac{∑_{i≥0} (C_{k}(t)^{i+1} − q^{i+1}) r^{i}}{1 − q + q^{k}t} .

Proof. The recurrence of Proposition 1 is equivalent to C_{n,(α,β)}^{k} = C_{n,(α−1,β)}^{k} − C_{n−1,(α−k,β)}^{k} for all n ≥ 0 and α ≥ 1. This suggests a relation that includes C_{k}(q, r, t) = qC_{k}(q, r, t) − q^{k}tC_{k}(q, r, t). Accounting for the α = 0 case, where shape (0, β) paths are generated by C_{k}(t)^{β+1}, requires an additional ∑_{i≥0} C_{k}(t)^{i+1}r^{i} term on the right side. Also accounting for the trivial case of n = 0 and α = β, to which Proposition 1 doesn’t apply, we have the full recurrence

C_{k}(q, r, t) = qC_{k}(q, r, t) − q^{k}tC_{k}(q, r, t) + ∑_{i≥0} C_{k}(t)^{i+1}r^{i} − ∑_{i≥0} q^{i+1}r^{i}.  (2)

The generating function of Theorem 2 may be used to derive closed formulas for all of the C_{n,(α,β)}^{k}, regardless of starting height. In all that follows, we set \binom{a}{b} = 0 whenever a < 0 or b < 0.

Theorem 3. For all k ≥ 2 and n, α, β ≥ 0, we have

C_{n,(α,β)}^{k} = (∑_{i≥0}(−1)^{i} \frac{β + 1}{k(n − i) + β + 1}\binom{k(n − i) + β + 1}{n − i}\binom{α − (k − 1)i}{i}) − (−1)^{n}\binom{α − β − 1 − (k − 1)n}{n}.

Proof. Specializing the formula of Theorem 2 to fixed β gives

[r^{β}]C_{k}(q, r, t) = \frac{C_{k}(t)^{β+1} − q^{β+1}}{1 − q + q^{k}t}
= (C_{k}(t)^{β+1} − q^{β+1}) (1 + (q − q^{k}t) + (q − q^{k}t)^{2} + ⋯) .  (3)

One may verify that the coefficient of q^{α} in (1 + (q − q^{k}t) + (q − q^{k}t)^{2} + ⋯) is

∑_{i≥0}(−1)^{i}\binom{α − (k − 1)i}{i}t^{i}.

This implies that

[q^{α}r^{β}]C_{k}(q, r, t) =

C_{k}(t)^{β+1} ∑_{i≥0}(−1)^{i}\binom{α − (k − 1)i}{i}t^{i} − ∑_{i≥0}(−1)^{i}\binom{α − β − 1 − (k − 1)i}{i}t^{i}. (4)

As noted in Section 1, C_{k}(t)^{β+1} may be rewritten as C_{k}(t)^{β+1} = ∑_{i≥0} \frac{β+1}{ki+β+1} \binom{ki+β+1}{i}t^{i}. This transforms the first term from the right side of (4) into a convolution of two power series. Extracting the coefficient of q^{α} from both terms of (4) yields our formula for [q^{α}r^{β}t^{n}]C_{k}(q, r, t) = C_{n,(α,β)}^{k}.

Using the aforementioned bijection between D_{n,(α,β)}^{k} and L((0, −β) → (n, kn − α) | x ≤ ky), one may verify that the closed formula of Theorem 3 is in agreement with Krattenthaler [7, Theorem 10.4.7]. However, in addition to presenting a novel method of proof for Krattenthaler’s result, our methodology is a more natural setting for the consideration of standard path statistics such as “maximum height”, “number of returns”, “number of peaks”, and “number of valleys”. To the best of our knowledge, nothing from this point forward is equivalent to anything in Krattenthaler [7] or appears elsewhere in the literature.

Inspecting the formula of Theorem 3, observe that the trailing term can only be nonzero when α > β. Also, at least one of the binomial coefficients from each term of the summation is zero unless i ≤ min(n, \frac{α}{k}).

All of this means that the formula of Theorem 3 is much simpler when the starting height α is relatively small. In particular, when 0 ≤ α ≤ k − 1, the leading summation contains only a single nonzero term and we have the following.

Corollary 4. For all k ≥ 2, β ≥ 0, and 0 ≤ α ≤ k − 1, we have

C_{n,(α,β)}^{k} = \begin{cases}\frac{β+1}{kn+β+1} \binom{kn+β+1}{n} = R_{k,β+1}(n), & if n > 0; \\ 1, & if n = 0 and α ≤ β; \\ 0, & if n = 0 and α > β. \end{cases}

Proof. When n > 0 and α ≤ k − 1, the final term from Theorem 3 is always zero and the leading summation simplifies to a single term. When n = 0, Theorem 3 gives \frac{β+1}{β+1} \binom{β+1}{0} − \binom{α−β−1}{0}.

Still restricting our attention to 0 ≤ α ≤ k − 1, we can alternatively begin with (4) to recast Corollary 4 is terms of the generating functions C_{k,(α,β)}(t) = [q^{α}r^{β}]C_{k}(q, r, t):

Corollary 5. For all k ≥ 2, β ≥ 0, and 0 ≤ α ≤ k − 1, we have

C_{k,(α,β)}(t) = \begin{cases}C_{k}(t)^{β+1}, & if α ≤ β; \\ C_{k}(t)^{β+1} − 1, & if α > β. \end{cases}

Proof. By (4), when 0 ≤ α ≤ k − 1 we have [q^{α}r^{β}]C_{k}(q, r, t) = C_{k}(t)^{β+1}\binom{α}{0} − \binom{α−β−1}{0}.

Corollaries 4 and 5 place our work in agreement with Selkirk [10] and Asinowski, Hackl, and Selkirk [1], assuming we restrict ourselves to their range of 0 ≤ α ≤ k − 1. In this case, observe that Corollaries 4 and 5 may also be proven by placing D_{n,(α,β)}^{k} in bijection with D_{n,(0,β)}^{k} via the map that adds α consecutive U steps to the beginning of every P ∈ D_{n,(α,β)}^{k}. This bijection fails when α > k − 1, since it is no longer the case that every P ∈ D_{n,(0,β)}^{k} must begin with α > k − 1 consecutive U steps.

Computation of C_{k,(α,β)}(t) becomes increasingly difficult as one extends above α = k − 1. See Appendix A for a comparison of the sequences generated by C_{k,(α,0)}(t) to previouslycataloged sequences in the OEIS (the On-Line Encyclopedia of Integer Sequences) [11], for small k ≥ 2 and various shapes (α, β).

2.1 Raised k-Dyck paths, k = 2 case

As with most combinatorial objects related to the k-Catalan numbers, investigating raised k-Dyck paths becomes much easier in the case of k = 2. In this subsection, we present a series of results involving the C_{n,(α,β)}^{k} that hold only when k = 2.

The primary reason the k = 2 case is simpler is the fact that the left-right reflection of a raised 2-Dyck path still qualifies as a raised 2-Dyck path. In particular, reflecting a 2-Dyck path of length 2n + β − α and shape (α, β) results in a 2-Dyck path of length 2n + β − α = 2(n + β − α) + α − β shape (β, α). In terms of generating functions, this prompts:

Proposition 6. For all α, β ≥ 0, we have

C_{2,(β,α)}(t) = t^{β−α}C_{2,(α,β)}(t).

Notice that Proposition 6 holds even if β − α < 0. If α > β, then C_{2,(α,β)}(t) has order α − β and t^{β−α}C_{2,(α,β)}(t) is a valid (order 0) power series. When dealing with the k = 2 case, Proposition 6 allows us to restrict our attention to shapes (α, β) where β ≥ α.

Our next result is a replacement of the generating function equation (4) from the proof of Theorem 3 that holds only when k = 2.

Theorem 7. For all α, β ≥ 0, we have

C_{2,(α,β)}(t) = ∑_{i=0}^{min(α,β)} t^{α−i}C_{2}(t)^{α+β+1−2i}.

Proof. For each n ≥ 0, we partition D_{n,(α,β)}^{2} into sets S_{n,0}, …, S_{n,min(α,β)}, where S_{n,i} includes all paths whose lowest point lies along y = i. As shown in Figure 3, every path P ∈ S_{i,n} may be decomposed into a sequence of (α − i) + (β − i) + 1 sub-paths of shape (0, 0). Notice that this decomposition includes α − i “external” down steps that aren’t included within one of the shape-(0, 0) sub-paths. If we define the generating function S_{i}(t) = ∑_{n≥0} |S_{n,i}|t^{n}, this decomposition implies that S_{i}(t) = t^{α−i}C_{2}(t)^{α+β+1−2i}.

\begin{matrix}⋯ \\ (0, 0) \\ (0, 0) \\ ⋯ \\ (0, 0) \\ ⋯ \\ (0, 0) \\ (0, 0) \\ ⋯ \end{matrix}

Figure 3: The decomposition of a path P ∈ D_{n,(α,β)}^{2} into a sequence of (α − i) + (β − i) + 1 sub-paths of shape (0, 0), as referenced in the proof of Theorem 7.

If β ≥ α, the formula of Theorem 7 may be rewritten as C_{2,(α,β)}(t) = ∑_{i=0}^{α} t^{i}C_{2}(t)^{β−α+2i+1}. Similarly, if α ≥ β, Theorem 7 may be rewritten as C_{2,(α,β)}(t) = ∑_{i=0}^{β} t^{α−β+i}C_{2}(t)^{α−β+2i+1}. Together these identities ensure C_{2,(β,α)}(t) = t^{β−α}C_{2,(α,β)}(t), placing Theorem 7 in agreement with Proposition 6.

Temporarily restricting our attention to the case of β ≥ α, also note that we may use the identity C_{2}(t) = tC_{2}(t)^{2} + 1 to rewrite the formula above as

C_{2,(α,β)}(t) = C_{2}(t)^{β−α+1} ∑_{i=0}^{α}(tC_{2}(t)^{2})^{i} = C_{2}(t)^{β−α+1} ∑_{i=0}^{α}(C_{2}(t) − 1)^{i}.  (5)

More significantly, Theorem 7 may used to develop a closed formula for arbitrary C_{n,(α,β)}^{2}, giving a simpler replacement of Theorem 3 that holds only when k = 2.

Theorem 8. For all n, α, β ≥ 0, we have

C_{n,(α,β)}^{2} = ∑_{i=0}^{min(α,β)} \frac{α + β + 1 − 2i}{2n + β − α + 1}\binom{2n + β − α + 1}{n − α + i}.

Proof. Fixing n ≥ 0 and applying the definition of Raney numbers, we have

[t^{n}]t^{α−i}C_{2}(t)^{α+β+1−2i} = [t^{n−α+i}]C_{2}(t)^{α+β+1−2i}

= \frac{α + β + 1 − 2i}{2(n − α + i) + (α + β + 1 − 2i)}\binom{2(n − α + i) + (α + β + 1 − 2i}{n − α + i}.

Our closed formula for C_{n,(α,β)}^{2} = [t^{n}]C_{2,(α,β)}(t) follows from the summation of Theorem 7.

3 Raised k-Dyck paths, filtered by minimum height and returns

For the rest of this paper, we focus upon the enumeration of raised k-Dyck paths that satisfy additional conditions. We begin by developing formulas for the number of paths P ∈ D_{n,(α,β)}^{k} that have a fixed minimum height and paths P ∈ D_{n,(α,β)}^{k} that have a certain number of “returns to ground”. Enumerating raised k-Dyck paths that have a fixed maximum height is delayed until Section 4.

3.1 Raised k-Dyck paths, by minimum height

For traditional k-Dyck paths, all of which necessarily begin at height y = 0, it is unnecessary to categorize paths according to their minimum y-coordinate. For raised k-Dyck paths of shape (α, β), this question becomes non-trivial when both α > 0 and β > 0.

Take a path P ∈ D_{n,(α,β)}^{k}. If P stays weakly above y = m, we say that P is bounded from below by m. Then let L_{n,(α,β)}^{k,m} denote the collection of all P ∈ D_{n,(α,β)}^{k} that are bounded from below by m. For any such set, there exists a clear bijection between L_{n,(α,β)}^{k,m} and D_{n,(α−m,β−m)}^{k} whereby paths in L_{n,(α,β)}^{k,m} are shifted m units downward. As such, we focus upon enumerating paths that actually obtain a fixed minimum height.

So once again take P ∈ D_{n,(α,β)}^{k}. If P is bounded from below by m yet is not bounded from below by m + 1, meaning that m is the minimum y-coordinate among all points (x_{i}, y_{i}) along P, we say that P has a minimum height of m. Then let _{m}D_{n,(α,β)}^{k} to denote the set of all raised k-Dyck paths of length kn + β − α and shape (α, β) with minimum height m, and set |_{m}D_{n,(α,β)}^{k}| = _{m}C_{n,(α,β)}^{k}. For fixed shape (α, β) and fixed m, define the generating function mC_{k,(α,β)}(t) = ∑_{n≥0} _{m}C_{n,(α,β)}^{k}t^{n}.

Obviously, all P ∈ D_{n,(α,β)}^{k} have a minimum height that falls in the range 0 ≤ m ≤ min(α, β). It follows that D_{n,(α,β)}^{k} = ⋃_{i=0}^{min(α,β)} _{m}D_{n,(α,β)}^{k} and hence that

C_{k,(α,β)}(t) = ∑_{i=0}^{min(α,β)}_{m}C_{k,(α,β)}(t)

for all k ≥ 2 and all shapes (α, β). By construction, we also have_{m}D_{n,(α,β)}^{k} = L_{n,(α,β)}^{k,m}−L_{n,(α,β)}^{k,m+1}. Using the bijection for the L_{n,(α,β)}^{k,m} mentioned above, this final fact gives:

Proposition 9. For all k ≥ 2, n, α, β ≥ 0 and 0 ≤ m ≤ min(α, β), we have

mC_{n,(α,β)}^{k} = C_{n,(α−m,β−m)}^{k} − C_{n,(α−m−1,β−m−1)}^{k}.

The drawback with Proposition 9 is that it relies upon the extremely lengthy formula of Theorem 3. This motivates the alternative characterization of _{m}C_{n,(α,β)}^{k} given below, which has the added benefit of relating all our results to enumerations of raised k-Dyck paths of shape (α, 0).

Theorem 10. For all k ≥ 2, α, β ≥ 0 and 0 ≤ m ≤ min(α, β), we have

mC_{k,(α,β)}(t) = C_{k,(α−m,0)}(t)C_{k}(t)^{β−m}.

Proof. As shown in Figure 4, every path P ∈ _{m}D_{n,(α,β)}^{k} may be decomposed according to the rightmost point at its minimum height of y = m. When 0 ≤ m < β, this decomposition gives the relationship _{m}C_{k,(α,β)}(t) = C_{k,(α−m,0)}(t)C_{k,(0,β−m−1)}(t). When m = β, we have the relationship _{m}C_{k,(α,β)}(t) = C_{k,(α−m,0)}(t). Both cases simplify to the stated equation.

\begin{matrix}(α−m, 0) \\ (0, β−m−1) \end{matrix}  (α−β, 0)

Figure 4: The two possible decompositions of a path P ∈ _{m}D_{n,(α,β)}^{k} with minimum height m, one for m < β (left) and one for m = β (right). The (a_{i}, b_{i}) denote the effective shape of each subpath.

Avoiding the even more involved calculation suggested by Proposition 9, we use Theorem 10 to develop an (admittedly still inelegant) closed formula for the _{m}C_{n,(α,β)}^{k}:

Theorem 11. For all k ≥ 2, n, α, β ≥ 0, and m ≤ 0 ≤ min(α, β), we have

mC_{n,(α,β)}^{k} = (∑_{i≥0}(−1)^{i} \frac{2β − m + 1}{k(n − i) + 2β − m + 1}\binom{k(n − i) + 2β − m + 1}{n − i}\binom{α − (k − 1)i}{i})

− (∑_{i≥0}(−1)^{i} \frac{β − m}{k(n − i) + β − m}\binom{k(n − i) + β − m}{n − i}\binom{α − m − 1 − (k − 1)i}{i}) .

Proof. Applying (4) from the proof of Theorem 3 to our identity from Theorem 10, we see that _{m}C_{n,(α,β)}^{k} = C_{k}(t)^{β−m}C_{k,(α−m,0)}(t) may be rewritten as

C_{k}(t)^{2β−m+1} ∑_{i≥0}(−1)^{i}\binom{α − m − (k − 1)i}{i}t^{i} − C_{k}(t)^{β−m} ∑_{i≥0}(−1)^{i}\binom{α − m − 1 − (k − 1)i}{i}t^{i}.

(6)

Recalling the standard identity C_{k}(t)^{r} = ∑_{i≥0} \frac{r}{ki+r} \binom{ki+r}{i}t^{i}, both of the terms from (6) are transformed into convolutions, from which the two summations of the theorem may be extracted.

As was the case in Section 2, all of these formulas become much simpler when we restrict our attention to small α or to k = 2. When α − m ≤ k − 1 we may apply Corollary 5 to the C_{k,(α−m,0)}(t) term from Theorem 10 and derive the following:

Corollary 12. For all k ≥ 2, n, β ≥ 0, and m, α ≥ 0 such that 0 ≤ α − m ≤ k − 1, we have

mC_{n,(α,β)}^{k} = \begin{cases}\frac{β−m+1}{kn+β−m+1} \binom{kn+β−m+1}{n}, & if m = α; \\ \frac{β−m+1}{kn+β−m+1} \binom{kn+β−m+1}{n} − \frac{β−m}{kn+β−m} \binom{kn+β−m}{n}, & if m < α ≤ k − 1 + m. \end{cases}

Proof. By Corollary 5 and Theorem 10, when m = α we have C_{k,(α−m,0)}(t) = C_{k}(t) and thus that _{m}C_{k,(α,β)}(t) = C_{k}(t)^{β−m+1}. Similarly, when m < α < k − 1 + m we have C_{k,(α−m,0)}(t) = C_{k}(t) − 1 and thus that _{m}C_{k,(α,β)}(t) = C_{k}(t)^{β−m+1} − C_{k}(t)^{β−m}. Our closed formulas then follow from the identity [t^{n}]C_{k}(t)^{r} = \frac{r}{kn+r} \binom{kn+r}{n}.

As for the k = 2 case, in the course of proving Theorem 7 we already enumerated paths in C_{n,(α,β)}^{2} with minimal height m. It may be verified that the formula below corresponds to [t^{n}]t^{α−m}C_{2}(t)^{α+β+1−2m} = [t^{n}]C_{2,(α−m)}(t)C_{2}(t)^{β−m}, placing it in agreement with Theorem 10.

Corollary 13. For all n, α, β ≥ 0 and 0 ≤ m ≤ min(α, β), we have

mC_{n,(α,β)}^{2} = \frac{α + β + 1 − 2m}{2n + β − α + 1}\binom{2n + β − α + 1}{n − α + m}.

One unrelated consequence of Theorem 10 is the following decomposition of C_{k,(α,β)}(t) into a sum that is indexed by minimal height:

C_{k,(α,β)}(t) = ∑_{i=0}^{min(α,β)} C_{k,(α−m,0)}(t)C_{k}(t)^{β−m}.  (7)

Comparison of Proposition 9 and Theorem 10 also gives an unexpected equation whereby shape (α, β) paths may enumerated in terms of paths with shapes of the form (α′, 0) and (0, β′).

Corollary 14. For all k ≥ 2 and α, β ≥ 0, we have

C_{k,(α,β)}(t) = ∑_{i=0}^{min(α,β)} C_{k,(α−i,0)}(t)C_{k}(t)^{β−i}.

Proof. Equating the right sides of Theorem 10 and (a generating function-equivalent version of) Proposition 9 when m = 0 gives the relation below, which holds whenever α > 0 and β > 0:

C_{k,(α,β)}(t) = C_{k,(α,0)}(t)C_{k}(t)^{β} + C_{k,(α−1,β−1)}(t).  (8)

Repeated application of this relation until α = 0 or β = 0 yields the desired equation.

3.2 Raised k-Dyck paths, by returns

Our next goal is to enumerate paths P ∈ D_{n,(α,β)}^{k} with a specific number of “returns to ground”. By a return to ground, we mean a D step whose right endpoint lies on the line y = 0. When α = 0, the initial point (0, 0) of a path does not qualify as a return to ground.

Denote the set of all raised k-Dyck paths of length kn + β − α and shape (α, β) with precisely ρ returns to ground by D_{n,(α,β),ρ}^{k}, and let |D_{n,(α,β),ρ}^{k}| = C_{n,(α,β),ρ}^{k}. As every path in D_{n,(α,β)}^{k} contains precisely n down steps, C_{n,(α,β),ρ}^{k} = 0 if ρ > n. When α > 0, we may have C_{n,(α,β),ρ}^{k} = 0 even if ρ ≤ n.

In this section it is once again beneficial to preemptively fix a shape (α, β) and deal with the generating functions C_{k,(α,β)}(t) = [q^{α}r^{β}]C_{k}(q, r, t). Filtering by the number of returns, we then define C_{k,(α,β)}(t, z) = ∑_{n,ρ≥0} C_{n,(α,β),ρ}^{k}t^{n}z^{ρ}.

In the classic case of α = 0, we quickly recap the standard result. Here, every path in D_{n,(0,β),ρ}^{k} may be decomposed according to its returns as in Figure 5. This decomposition gives

Proposition 15. For all k ≥ 2 and β ≥ 0, we have

C_{k,(0,β)}(t, z) = ∑_{i≥0} z^{i}t^{i}C_{k}(t)^{β+i(k−1)}.

Proof. For paths P ∈ D_{n,(0,β)}^{k} with precisely ρ returns, the decomposition of Figure 5 yields the generating function C_{k,(0,β−1)}(t) (tC_{k,(0,k−2)}(t))^{ρ} = t^{ρ}C_{k}(t)^{β} (C_{k}(t)^{k−1})^{ρ}.

\begin{matrix}(0, k − 2) \\ (0, k − 2) \\ ⋯ \\ (0, β − 1) \end{matrix}

Figure 5: The general form of a path P ∈ D_{n,(0,β)}^{k} with precisely ρ returns to ground, along with the effective shape of each subpath.

Theorem 16. For all k ≥ 2 and β, n, ρ ≥ 0, we have

C_{n,(0,β),ρ}^{k} = \frac{kρ + β − ρ}{kn + β − ρ}\binom{kn + β − ρ}{n − ρ}.

Proof. By Proposition 15, C_{n,(0,β),ρ}^{k} = [t^{n}]t^{ρ}C_{k}(t)^{β+ρ(k−1)} = [t^{n−ρ}]C_{k}(t)^{β+ρ(k−1)}.

The case of α > 0 is similar yet slightly more complex, seeing as elements of D_{n,(α,β),ρ}^{k} need not have a return to ground. This necessitates two distinct decompositions for elements of D_{n,(α,β),ρ}^{k}, both of which are shown in Figure 6. As with Proposition 15, this decomposition prompts

Proposition 17. For all k ≥ 2 and β ≥ 0 with α > 0, we have

C_{k,(α,β)}(t, z) = C_{k,(α−1,β−1)}(t) + ∑_{i≥1} z^{i}t^{i}C_{k,(α−1,k−2)}(t)C_{k}(t)^{β+(i−1)(k−1)}.

Proof. The first term corresponds to the first decomposition in Figure 6. The sum corresponds to the second decomposition in Figure 6, where paths P ∈ D_{n,(α,β)}^{k} with ρ returns have generating function

C_{k,(α−1,k−2)}(t) (tC_{k,(0,k−2)}(t))^{ρ−1} tC_{k,(0,β−1)}(t) = t^{ρ}C_{k,(α−1,k−2)}(t) (C_{k}(t)^{k−1})^{ρ−1} C_{k}(t)^{β}.

(α−1, β−1)  \begin{matrix}(α−1, k−2) \\ (0, k − 2) \\ ⋯ \\ (0, β − 1) \end{matrix}

Figure 6: The two possible decompositions for a path P ∈ D_{n,(α,β)}^{k} with α > 0, one for paths with no returns (left) and one for paths with precisely ρ > 0 returns (right).

Theorem 18. For all k ≥ 2 and β, n, ρ ≥ 0 with α > 0, we have

C_{n,(α,β),ρ}^{k} = \begin{cases}C_{n,(α−1,β−1)}^{k}, & if ρ = 0; \\ ∑_{i=0}^{n−ρ} C_{i,(α−1,k−2)}^{k}R_{k,β+(ρ−1)(k−1)}(n − ρ − i), & if ρ > 0. \end{cases}

Proof. Using Proposition 17, C_{n,(α,β),0}^{k} = [t^{n}]C_{k,(α−1,β−1)}(t) when ρ = 0. For ρ > 0 we have

C_{n,(α,β),ρ}^{k} = [t^{n}]t^{ρ}C_{k,(α−1,k−2)}(t)C_{k}(t)^{β+(ρ−1)(k−1)} = [t^{n−ρ}]C_{k,(α−1,k−2)}(t)C_{k}(t)^{β+(ρ−1)(k−1)}. (9)

Given the complexity of the formula from Theorem 3, substituting closed formulas into Theorem 18 becomes very lengthy for arbitrary (α, β). However, when 0 < α ≤ k, we can apply Corollary 4 (or Corollary 5) to arrive at the much simpler identity shown below.

Corollary 19. For all k ≥ 2 and β, n, ρ ≥ 0 with 0 < α ≤ k, we have

C_{n,(α,β),ρ}^{k} = \begin{cases}\frac{kρ+β−ρ}{kn+β−ρ} \binom{kn+β−ρ}{n−ρ}, & if 0 < α ≤ k − 1; \\ \frac{kρ+β−ρ}{kn+β−ρ} \binom{kn+β−ρ}{n−ρ} − \frac{kρ+β−ρ−(k−1)}{kn+β−ρ−(k−1)} \binom{kn+β−ρ−(k−1)}{n−ρ}, & if α = k. \end{cases}

Proof. Applying Corollary 5 to the C_{k,(α−1,k−2)}(t) terms of Theorem 18, note that α−1 ≤ k−2 implies α ≤ k − 1, whereas α − 1 > k − 2 along with α − 1 ≤ k − 1 together imply α = k.

As expected, the k = 2 case is also comparatively succinct. Not at all expected is that a specialization of Theorem 18 to k = 2 gives a simpler result when ρ > 0 than when ρ = 0.

Corollary 20. For all β, n, ρ ≥ 0 with α > 0, we have

C_{n,(α,β),ρ}^{k} = \begin{cases}∑_{i=0}^{min(α−1,β−1)} \frac{α + β − 1 − 2i}{2n + β − α + 1}\binom{2n + β − α + 1}{n − α + 1 + i}, & if ρ = 0; \\ \frac{α + β + ρ − 1}{2n + β − α − ρ + 1}\binom{2n + β − α − ρ + 1}{n − α − ρ + 1}, & if ρ > 0. \end{cases}

Proof. The ρ = 0 case follows immediately from an application of Theorem 8 to Theorem 18. For the ρ > 0 case, by Proposition 6 we have C_{n,(α,β),ρ}^{2} = [t^{n}]t^{ρ}C_{2,(α−1,0)}(t)C_{2}(t)^{β+ρ−1}. Using Proposition 17 then gives the following, to which we apply the definition of Raney numbers:

C_{n,(α,β),ρ}^{2} = [t^{n}]t^{ρ+α−1}C_{2,(0,α−1)}(t)C_{2}(t)^{β+ρ−1} = [t^{n−ρ−α+1}]C_{2}(t)^{α+β+ρ−1}.  (10)

4 Raised k-Dyck paths of bounded height

The results of Section 2 may also be used to enumerate (raised) k-Dyck paths of bounded height. This allows for a derivation of easily-computable generating functions that hold for all k ≥ 2 and shapes (α, β), expanding upon the discussions of non-raised, height-bounded lattice paths in Baril and Prodinger [3], Bousquet-Mélou [4], or Bacher [2].

So take a raised k-Dyck path P ∈ D_{n,(α,β)}^{k}. If P stays weakly below y = M, we say that P is bounded from above by M. We use U_{n,(α,β)}^{k,M} to denote the collection of all P ∈ D_{n(α,β)}^{k} that are bounded from above by M, and set |U_{n,(α,β)}^{k,M}| = U_{n,(α,β)}^{k,M}. Clearly, U_{n,(α,β)}^{k,M} = 0 unless α, β ≤ M.

Fixing 0 ≤ α, β ≤ M, we define the generating function U_{k,(α,β)}^{M}(t) = ∑_{n≥0} U_{n,(α,β)}^{k,M}t^{n}. The primary goal of this section is to relate the U_{k,(α,β)}^{M}(t) to the generating functions C_{k,(α′,β′)}(t) of Section 2, from which one may derive closed formulas for the U_{n,(α,β)}^{k,M} using Theorem 3.

Before deriving a relationship for general U_{k,(α,β)}^{M}(t), we consider the special case of β = M:

Lemma 21. For all k ≥ 2, α ≥ 0, and M ≥ 0, we have

U_{k,(α,M)}^{M}(t) = \frac{C_{k,(α,M)}(t)}{1 + C_{k,(M+1,M)}(t)}.

Proof. Every path P ∈ D_{n,(α,M)}^{k} may be decomposed in one of the two ways shown in Figure 7, depending upon whether or not the path rises above y = M. This prompts the identity

C_{k,(α,M)}(t) = U_{k,(α,M)}^{M}(t) + U_{k,(α,M)}^{M}(t)C_{k,(M+1,M)}(t).  (11)

Lemma 21 may still be applied to derive our general identity:

Theorem 22. For all k ≥ 2, M ≥ 0, and 0 ≤ α, β ≤ M, we have

U_{k,(α,β)}^{M}(t) = C_{k,(α,β)}(t) − \frac{C_{k,(α,M)}(t)C_{k,(M+1,β)}(t)}{1 + C_{k,(M+1,M)}(t)}.

(α, M)  \begin{matrix}(α, M) \\ (M +1, M) \end{matrix}

Figure 7: The two decompositions for a path P ∈ D_{n,(α,M)}^{k}, as used in the proof of Lemma 21.

Proof. Via an equivalent decomposition of paths P ∈ D_{n,(α,β)}^{k} to that in Figure 7, we have

C_{k,(α,β)}(t) = U_{k,(α,β)}^{M}(t) + U_{k,(α,M)}^{M}(t)C_{k,(M+1,β)}(t).  (12)

Rearranging (12) and applying Lemma 21 then gives

U_{k,(α,β)}^{M}(t) = C_{k,(α,β)}(t)−U_{k,(α,M)}^{M}(t)C_{k,(M+1,β)}(t) = C_{k,(α,β)}(t)−\frac{C_{k,(α,M)}(t)C_{k,(M+1,β)}(t)}{1 + C_{k,(M+1,M)}(t)}. (13)

Recall that the order of C_{k,(α,β)}(t) goes to ∞ and α → ∞. This implies that the order of C_{k,(α,M)}(t)C_{k,(M+1,β)}(t) goes to ∞ as M → ∞, and thus that the order of \frac{C_{k,(α,M)}(t)C_{k,(M+1,β)}(t)}{1+C_{k,(M+1,M)}(t)} goes to ∞ as M → ∞. This allows us to conclude that number of initial terms for which [t^{n}]U_{k,(α,β)}^{M}(t) = [t^{n}]C_{k,(α,β)}(t) goes to ∞ and M → ∞, as one would expect for k-Dyck paths with an arbitrarily high upper bound.

Also observe that, if M < k − 1, then we have both M + 1 ≤ k − 1 and α, β ≤ M. This means that we can apply Corollary 5 to the rightmost term from Theorem 22 as below:

\frac{C_{k,(α,M)}(t)C_{k,(M+1,β)}(t)}{1 + C_{k,(M+1,M)}(t)} = \frac{C_{k}(t)^{M+1} (C_{k}(t)^{β+1} − 1)}{C_{k}(t)^{M+1}} = C_{k}(t)^{β+1} − 1.  (14)

When M < k − 1 and α ≤ β, this gives the expected result

U_{k,(α,β)}^{M}(t) = C_{k}(t)^{β+1} − (C_{k}(t)^{β+1} − 1) = 1,

corresponding to the fact that only the “trivial” path (i.e., the unique path with zero D steps) stays weakly below y = M when M < k − 1. When M < k − 1 and α > β, we similarly get the expected result of U_{k,(α,β)}^{M}(t) = 0, reflecting the fact that every path of such a shape (α, β) must have at least one D step and thus can’t stay weakly below y = M.

Explicit calculations involving the generating function U_{k,(α,β)}^{M}(t) become increasingly difficult when M ≥ k − 1, but Theorem 22 may always be used with with Theorem 3 to calculate the sizes U_{n,(α,β)}^{k,M} = [t^{n}]U_{k,(α,β)}^{M}(t). See Appendix A for explicit calculations of the sequences generated by the U_{k,(α,β)}^{M}(t) for various k ≥ 2 and small M in the case of (α, β) = (0, 0).

For one final application, note that Theorem 22 may be used to enumerate the number of raised k-Dyck paths that actually obtain a fixed maximum height. This follows immediately from the fact that raised k-Dyck paths of maximum height M are precisely those paths that stay weakly below y = M yet fail to stay weakly below y = M − 1.

So let H_{n,(α,β)}^{k,M} denote the set of all P ∈ D_{n,(α,β)}^{k} that obtain a maximum height of M, and let |H_{n,(α,β)}^{k,M}| = H_{n,(α,β)}^{k,M}. In terms of the generating function H_{k,(α,β)}^{M}(t) = ∑_{n≥0} H_{n,(α,β)}^{k,M}t^{n}, Theorem 22 immediately yields the following result.

Corollary 23. For all k ≥ 2, M ≥ 0 and 0 ≤ α, β ≤ M, we have

H_{k,(α,β)}^{M}(t) = U_{k,(α,β)}^{M}(t) − U_{k,(α,β)}^{M−1}(t) = \frac{C_{k,(α,M−1)}(t)C_{k,(M,β)}(t)}{1 + C_{k,(M,M−1)}(t)} − \frac{C_{k,(α,M)}(t)C_{k,(M+1,β)}(t)}{1 + C_{k,(M+1,M)}(t)}.

As with the U_{k,(α,β)}^{M}(t), the H_{k,(α,β)}^{M}(t) become increasing exhausting to calculate when M becomes large. For M < k − 1, it is still easy to verify that we get the expected results of H_{k,(α,β)}^{M}(t) = 1 when α ≤ β and H_{k,(α,β)}^{M}(t) = 0 when α > β. See Appendix A for explicit calculations of the sequences generated by the H_{k,(α,β)}^{M}(t) for various k ≥ 2 and M ≥ k in the case of (α, β) = (0, 0).

A Appendix: Explicit Calculations

Below are comparisons of the sequences generated by C_{n,(α,β)}(t) to preexisting sequences in the OEIS, for k = 2, 3, 4. All sequences were calculated on Maple 19 via (4) from the proof Theorem 3. All listed sequences are identical up to shifting or the complete absence of (one or more) initial terms.

Notice how Proposition 6 ensures that the k = 2 table is symmetric along the main diagonal, whereas the k = 3, 4 tables are not symmetric along the main diagonal. For all tables, Corollary 5 ensures that all sequences with α ≤ k − 1 correspond to convolutions of the k−Catalan numbers.

β = 0  β = 1  β = 2  β = 3  β = 4  β = 5  β = 6  β = 7
α = 0 \underline{A000108} \underline{A000108} \underline{A000245} \underline{A002057} \underline{A000340} \underline{A003517} \underline{A000588} \underline{A003518}
α = 1 \underline{A000108} \underline{A000108} \underline{A000245} \underline{A002057} \underline{A000340} \underline{A003517} \underline{A000588} \underline{A003518}
α = 2 \underline{A000245} \underline{A000245} \underline{A026012} \underline{A026016} \underline{A026013} \underline{A026017} \underline{A026014} \underline{A026018}
α = 3 \underline{A002057} \underline{A002057} \underline{A026016} \underline{A026029} \underline{A026026} \underline{A026030} \underline{A026027} \underline{A026031}
α = 4 \underline{A000340} \underline{A000340} \underline{A026013} \underline{A026026}  –  –  –  –
α = 5 \underline{A003517} \underline{A003517} \underline{A026017} \underline{A026030}  –  –  –  –
α = 6 \underline{A000588} \underline{A000588} \underline{A026014} \underline{A026027}  –  –  –  –
α = 7 \underline{A003518} \underline{A003518} \underline{A026018} \underline{A026031}  –  –  –  –

Table 1: A comparison of the sequences generated by C_{2,(α,β)}(t) to preexisting sequences in the OEIS.

β = 0  β = 1  β = 2  β = 3  β = 4  β = 5
α = 0 \underline{A001764} \underline{A006013} \underline{A001764} \underline{A006629} \underline{A102893} \underline{A006630}
α = 1 \underline{A001764} \underline{A006013} \underline{A001764} \underline{A006629} \underline{A102893} \underline{A006630}
α = 2 \underline{A001764} \underline{A006013} \underline{A001764} \underline{A006629} \underline{A102893} \underline{A006630}
α = 3 \underline{A334680}  –  \underline{A334680}  –  –  –
α = 4 \underline{A336945} \underline{A030983} \underline{A336945}  –  –  –
α = 5 \underline{A334976} \underline{A334977} \underline{A334976}  –  –  –

Table 2: A comparison of the sequences generated by C_{3,(α,β)}(t) to preexisting sequences in the OEIS.

β = 0  β = 1  β = 2  β = 3  β = 4  β = 5
α = 0 \underline{A002293} \underline{A069271} \underline{A006632} \underline{A002293} \underline{A196678} \underline{A006633}
α = 1 \underline{A002293} \underline{A069271} \underline{A006632} \underline{A002293} \underline{A196678} \underline{A006633}
α = 2 \underline{A002293} \underline{A069271} \underline{A006632} \underline{A002293} \underline{A196678} \underline{A006633}
α = 3 \underline{A002293} \underline{A069271} \underline{A006632} \underline{A002293} \underline{A196678} \underline{A006633}
α = 4 \underline{A334682}  –  –  \underline{A334682}  –  –
α = 5  –  \underline{A334608}  –  –  –  –

Table 3: A comparison of the sequences generated by C_{4,(α,β)}(t) to preexisting sequences in the OEIS.

Below are comparisons of the sequences generated by U_{k,(0,0)}^{M}(t) to preexisting sequences in the OEIS, for k = 2, 3, 4. All sequences were calculated on Maple 19 via Theorem 22, and are identical to the listed sequences up to shifting or the absence of (one or more) initial terms.

k = 2  k = 3  k = 4
M = 0  1  1  1
M = 1 (1)_{n≥0}  1  1
M = 2 (2^{n})_{n≥0} (1)_{n≥0}  1
M = 3 \underline{A001519} (2^{n})_{n≥0} (1)_{n≥0}
M = 4 \underline{A124302} (3^{n})_{n≥0} (2^{n})_{n≥0}
M = 5 \underline{A080937} \underline{A001835} (3^{n})_{n≥0}
M = 6 \underline{A024175} \underline{A081704} (4^{n})_{n≥0}
M = 7 \underline{A080938} \underline{A083881} \underline{A004253}
M = 8 \underline{A033191}  –  –
M = 9 \underline{A211216}  –  \underline{A261399}
M = 10  –  –  \underline{A143648}
M = 11  –  –  –
M = 12  –  –  –

Table 4: A comparison of the sequences generated by U_{k,(0,0)}^{M}(t) to preexisting sequences in the OEIS. An entry of 1 (without parentheses) corresponds to the sequence 1, 0, 0, 0, . . ..

References

[1] A. Asinowski, B. Hackl, and S. J. Selkirk, Down-step statistics in generalized Dyck paths, Discrete Math. Theor. Comput. Sci. 24 (1) (2022), Paper no. 17.

[2] A. Bacher, Generalized Dyck paths of bounded height, arxiv preprint arXiv:1303.2724

[math.CO], 2013. Available at http://arxiv.org/abs/1303.2724.

[3] J. L. Basil and H. Prodinger, Enumeration of partial Łukasiewicz paths, Enumer. Comb. Appl. 3 (1) (2023), Paper no. S2R2. Available at https://ecajournal.haifa.ac.il/

Volume2023/ECA2023_S2A2.pdf.

[4] M. Bousquet-Mélou, Discrete excursions, Sém. Lothar. Combin. 58 (2008), Article B57d.

[5] S. Heubach, N. Y. Li, and T. Mansour, Staircase tilings and k-Catalan structures, Discrete Math. 308 (2008), 5954–5964.

[6] P. Hilton and J. Pedersen, Catalan numbers, their generalizations, and their uses, Math. Intelligencer 13 (2) (1991), 64–75.

[7] C. Krattenthaler, Lattice path enumeration, in Handbook of Enumerative Combinatorics, CRC Press, 2015, pp. 220–234.

[8] T. Mansour and J. L. Ramirez, Enumerations on polyominoes determined by Fuss-Catalan words, Australas. J. Combin. 81 (2021), 447–457.

[9] H. Prodinger, On k-Dyck paths with a negative boundary, arxiv preprint arXiv:1912.06930 [math.CO], 2020. Available at http://arxiv.org/abs/1912.06930.

[10] S. J. Selkirk, On a generalisation of k-Dyck paths. Master’s thesis, Stellenbosch University, 2019.

[11] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2023. Available

at https://oeis.org.

[12] R. P. Stanley, Catalan Numbers, Cambridge University Press, 2015.

2020 Mathematics Subject Classification: Primary 05A15; Secondary 05A19. Keywords: lattice path, Catalan number, Fuss-Catalan number.

(Concerned with sequences \underline{A000108}, \underline{A000245}, \underline{A000340}, \underline{A000588}, \underline{A001519}, \underline{A001764}, \underline{A001835}, \underline{A002057}, \underline{A002293}, \underline{A003517}, \underline{A003518}, \underline{A004253}, \underline{A006013}, \underline{A006629}, \underline{A006630}, \underline{A006632}, \underline{A006633}, \underline{A024175}, \underline{A026012}, \underline{A026013}, \underline{A026014}, \underline{A026016}, \underline{A026017}, \underline{A026018}, \underline{A026026}, \underline{A026027}, \underline{A026029}, \underline{A026030}, \underline{A026031}, \underline{A030983}, \underline{A033191}, \underline{A069271}, \underline{A080937}, \underline{A080938}, \underline{A081704}, \underline{A083881}, \underline{A102893}, \underline{A124302}, \underline{A143648}, \underline{A196678}, \underline{A211216}, \underline{A261399}, \underline{A334608}, \underline{A334680}, \underline{A334682}, \underline{A334976}, \underline{A334977}, and \underline{A336945}.)

Received May 24 2023; revised version received June 6 2023. Published in Journal of Integer Sequences, June 10 2023.

Return to Journal of Integer Sequences home page.