Colored Motzkin Paths of Higher Order^{1}

Isaac DeJager LeTourneau University Longview, Texas 75602 USA

                   IsaacDeJager@letu.edu

Madeleine Naquin Spring Hill College Mobile, Alabama 36608 USA

             madeleine.c.naquin@email.shc.edu

Frank Seidl University of Michigan Ann Arbor, Michigan 48109 USA

                     fcseidl@umich.edu

Paul Drube Valparaiso University Valparaiso, Indiana 46383 USA

                   paul.drube@valpo.edu

Abstract

Motzkin paths of order ℓ are a generalization of Motzkin paths that use steps U = (1, 1), L = (1, 0), and D_{i} = (1, −i) for every positive integer i ≤ ℓ. We further generalize order-ℓ Motzkin paths by allowing for various coloring schemes on the edges of our paths. These (α⃗, β⃗)-colored Motzkin paths may be enumerated via proper Riordan arrays, mimicking the techniques of Aigner in his treatment of “Catalan-like numbers”. After an investigation of their associated Riordan arrays, we develop bijections between (α⃗, β⃗)-colored Motzkin paths and a variety of well-studied combinatorial objects. Specific coloring schemes (α⃗, β⃗) allow us to place (α⃗, β⃗)-colored Motzkin paths in bijection with different sub-classes of generalized k-Dyck paths, including k-Dyck paths that remain weakly above horizontal lines y = −a, k-Dyck paths whose peaks all have the same height modulo-k, and Fuss-Catalan generalizations of Fine paths. A general bijection is also developed between (α⃗, β⃗)-colored Motzkin paths and certain sub-classes of k-ary trees.

1Research supported by NSF Grant DMS-1559912.

1 Introduction

A Motzkin path of length n and height m is an integer lattice path from (0, 0) to (n, m) that uses the step set {U = (1, 1), L = (1, 0), D = (1, −1)} and remains weakly above the horizontal line y = 0. We denote the set of all such Motzkin paths by M_{n,m} and let |M_{n,m}| = M_{n,m}. The cardinalities M_{n,0} = M_{n} correspond to the Motzkin numbers, a well-known integer sequence (\underline{A001006}) that begins as 1, 1, 2, 4, 9, 21, 51, 127, . . .. For more information about the Motzkin numbers and their various combinatorial interpretations, see Aigner [1], Bernhart [5], and Donaghey and Shapiro [9].

For any α, β ≥ 0, an element of M_{n,m} is said to be an (α, β)-colored Motzkin path of length n and height m if each of its L steps at height y = 0 is labeled by one of α colors and each of its L steps at height y > 0 is labeled by one of β colors. By the “height” of a step in a lattice path we mean the y-coordinate of its right endpoint. We denote the set of all (α, β)-colored Motzkin paths by M_{n,m}(α, β) and let |M_{n,m}(α, β)| = M_{n,m}(α, β). By analogy with above, for fixed α, β we henceforth refer to the integer sequences (M_{n,0}(α, β))_{n≥0} as the (α, β)-colored Motzkin numbers. See Figure 1 for an illustration of the set M_{3,0}(1, 2). That example establishes our convention of using positive integers for our “colors”.

1 1 1  1  1  2  1

Figure 1: All (1, 2)-colored Motzkin paths in the set M_{3,0}(1, 2).

Our notion of colored Motzkin paths are actually a special case of the labeled lattice paths investigated by Flajolet [11]. Using Flajolet’s scheme of edge labeling, our (α, β)-colored Motzkin paths correspond to b_{0} = α, b_{i} = β for all i ≥ 1, and a_{i} = c_{i} = 1 for all i ≥ 0. Our scheme has been chosen to be amenable to the Riordan array-oriented methodologies of Aigner [2], methodologies that will also admit an intuitive generalization to “higher-order” paths in Section 2.

It should also be noted that our (α, β)-colored Motzkin paths specialize to the “k-colored Motzkin paths” of Barrucci et al. [4] or Sapounakis and Tsikouras [19, 20] when α = β = k. Our definition is also distinct from the (u, l, d)-colored Motzkin paths of Woan [23, 24] or Mansour, Schork and Sun [15]. In those papers, U, L, and D steps are all colored and there is no distinction between L steps at various heights.

It is clear that M_{n,m}(α, β) = 0 unless 0 ≤ m ≤ n, as well as that M_{0,0}(α, β) = 1. For n ≥ 1, the cardinalities M_{n,m}(α, β) may be computed via the recursion of Proposition 1.1, variations of which already appear elsewhere.

Proposition 1.1. For all n ≥ 1 and 0 ≤ m ≤ n,

M_{n,m}(α, β) = \begin{cases}M_{n−1,m−1}(α, β) + βM_{n−1,m}(α, β) + M_{n−1,m+1}(α, β), & if m ≥ 1; \\ αM_{n−1,0}(α, β) + M_{n−1,1}(α, β), & if m = 0. \end{cases}

Proof. For m ≥ 1, partition the paths of M_{n,m}(α, β) according to their final step. The subset of those paths that end with a U step are in bijection with M_{n−1,m−1}(α, β), those that end with a D step are in bijection with M_{n−1,m+1}(α, β), and those that end with a L step of a fixed color are in bijection with M_{n−1,m}(α, β), for each of the β colors. The m = 1 case is similar, although here the elements of M_{n,m}(α, β) cannot end in a U step and the final L steps may carry α possible colors.

Using Proposition 1.1, one may define an infinite lower-triangular array whose (n, m)-entry is M_{n,m}(α, β). See Figure 2 for the first four rows of this triangle, which we refer to as the (α, β)- colored Motzkin triangle. Notice that the upper-leftmost nonzero entry of this triangle corresponds to (n, m) = (0, 0).

1

α  1
α^{2} + 1  α + β  1
α^{3} + 2α + β α^{2} + αβ + β^{2} + 2 α + 2β 1

Figure 2: The first four nonzero rows of the (α, β)-colored Motzkin triangle.

We will be interested primarily in the leftmost nonzero column of the (α, β)-Motzkin triangle. Ranging over various (α, β), these are the (α, β)-colored Motzkin numbers and constitute one class of what Aigner [2] refers to as “Catalan-like numbers”. Shown in Table 1 are the sequences associated with all 0 ≤ α, β ≤ 4, many of which are well-represented in the literature.

β = 0  β = 1  β = 2  β = 3 β = 4
α = 0 \underline{A126120} Riordan numbers (R_{n})  Fine numbers (F_{n})  \underline{A117641} \underline{A185132}
α = 1 \underline{A001405} Motzkin numbers (M_{n}) Catalan numbers (C_{n}) \underline{A033321}  -
α = 2 \underline{A054341}  \underline{A005773}  Catalan numbers (C_{n+1}) \underline{A007317} \underline{A033543}
α = 3 \underline{A126931}  \underline{A059738}  \binom{2n+1}{n+1}  \underline{A002212} \underline{A064613}
α = 4  -  -  \underline{A049027}  \underline{A026378} \underline{A005572}

Table 1: Integer sequences corresponding to the (α, β)-colored Motzkin numbers, for various choices of (α, β). Numbered entries correspond to OEIS [25]. Dashes correspond to sequences that currently do not appear on OEIS.

As with the Catalan-like numbers of Aigner [2], our notion of (α, β)-colored Motzkin paths is most efficiently recast within the language of proper Riordan arrays. Let d(t), h(t) be a pair of formal power series such that d(0) ≠ 0, h(0) = 0 and h′(0) ≠ 0. The proper Riordan array R(d(t), h(t)) associated with these power series is an infinite, lower-triangular array whose (i, j)- entry is d_{i,j} = [t^{i}]d(t)h(t)^{j}. Here was adopt the standard convention where [t^{i}]p(t) denotes the coefficient of the t^{i} in the power series p(t). See Rogers [18] or Merlini et al. [16] for more background information on Riordan arrays.

Fundamental to the theory of Riordan arrays is the fact that every proper Riordan array R(d(t), h(t)) is uniquely determined by a pair of power series A(t) = ∑_{i=0}^{∞} a_{i}t^{i} and Z(t) = ∑_{i=0}^{∞} z_{i}t^{i} such that

d_{i,j} = \begin{cases}a_{0}d_{i−1,j−1} + a_{1}d_{i−1,j} + a_{2}d_{i−1,j+1} + ⋯, & for all j ≥ 1; \\ z_{0}d_{i−1,0} + z_{1}d_{i−1,1} + z_{2}d_{i−1,2} + ⋯, & for j = 0. \end{cases}  (1)

These series are referred to as the A-sequence and Z-sequence of R(d(t), h(t)), respectively. It may be shown that the A- and Z-sequences of R(d(t), h(t)) satisfy

h(t) = tA(h(t)),  d(t) = \frac{d(0)}{1 − tZ(h(t))}.  (2)

With this terminology in hand, Proposition 1.1 immediately guarantees that the (α, β)-colored Motzkin triangle is a proper Riordan array for every choice α, β ≥ 0. In particular, the (α, β)- colored Motzkin triangle is the proper Riordan array with A-sequence A(t) = 1 + βt + t^{2} and Z-sequence Z(t) = α + t.

1.1 Outline of paper

The goal of this paper is to adapt the aforementioned phenomena to “higher-order” Motzkin paths, a generalization of traditional Motzkin paths whose step set includes a down step D_{i} = (1, −i) for every positive integer 1 ≤ i ≤ ℓ up to some fixed upper bound ℓ. Section 2 defines the relevant notion of coloring for higher-order Motzkin paths, describes the proper Riordan arrays that enumerate these colored paths, and proves a series of general results about those proper Riordan arrays. Section 3 then introduces a series of combinatorial interpretations for colored higher-order Motzkin paths that directly generalize the combinatorial interpretations suggested by Table 1. In particular, colored higher-order Motzkin paths are placed in bijection with various classes of generalized k-Dyck paths, entirely new generalizations of Fine paths, k-Dyck paths whose peaks only occur at specific heights, and various subsets of k-ary trees. Appendix A closes the paper by comparing the first columns of our proper Riordan arrays against sequences in OEIS [25] for various “easy” colorations, providing impetus for future investigations.

2 Higher-order Motzkin paths

Fix ℓ ≥ 1. An order-ℓ Motzkin path of length n and height m is an integer lattice path from (0, 0) to (n, m) that uses step set {U = (1, 1), D_{0} = (1, 0), D_{1} = (1, −1), …, D_{ℓ} = (1, −ℓ)} and remains weakly above the horizontal line y = 0. We denote the set of all such paths by M_{n,m}^{ℓ}, and let |M_{n,m}^{ℓ}| = M_{n,m}^{ℓ}. Note that order-1 Motzkin paths correspond to the traditional notion of Motzkin paths, so that M_{n,0}^{1} = M_{n,0} are the Motzkin numbers.

For ℓ > 1, our notion of order ℓ Motzkin paths are distinct from the “higher-rank” Motzkin paths studied by Mansour, Schork and Sun [15] or Sapounakis and Tsikouras [19]. In particular, our order-ℓ Motzkin paths don’t allow for up steps of multiple slopes. In the limit of ℓ → ∞, our order-ℓ Motzkin paths correspond to the Łukasiewicz paths investigated by Cheon, Kim and Shapiro [7].

We now look to color order-ℓ Motzkin paths in a way that directly generalizes the Riordan array properties of Section 1. So fix ℓ ≥ 1, and let α⃗ = (α_{0}, …, α_{ℓ−1}), β⃗ = (β_{0}, …, β_{ℓ−1}) be any pair of ℓ-tuples of non-negative integers. An (α⃗, β⃗)-colored Motzkin path is an element of M_{n,m}^{ℓ} where each D_{i} step that ends at height y = 0 is labeled by one of α_{i} colors, and each D_{i} step that ends at height y > 0 is labeled by one of β_{i} colors, for each 0 ≤ i ≤ ℓ − 1. We denote the set of all (α⃗, β⃗)-colored Motzkin paths by M_{n,m}^{ℓ}(α⃗, β⃗) and let |M_{n,m}^{ℓ}(α⃗, β⃗)| = M_{n,m}^{ℓ}(α⃗, β⃗). For fixed ℓ, α⃗, β⃗, we refer to the sequences (M_{n,0}^{ℓ}(α⃗, β⃗))_{n≥0} as the (α⃗, β⃗)-colored Motzkin numbers of order ℓ.

See Figure 3 for an example of order 2 Motzkin paths. Notice that the only steps which fail to receive colors are U steps and down steps D_{ℓ} of maximal negative slope.

Higher-order Motzkin paths (with colored edges) have previously appeared in the literature, as a special case of the “simple excursions” studied by Banderier and Flajolet [3]. Our approach differs from that of Banderier and Flajolet in that we distinguish between steps that end at height y = 0 and steps that end at height y > 0. This means that many results from Subsection 2.1 may be recovered from Banderier and Flajolet if we restrict ourselves to the specific case of α⃗ = β⃗.

1 1 1  1 1  1 2  1 1  2 1  1 1

2 1  3 1  1 2  2 2  3 2
Figure 3: All paths in M_{3,0}^{2}(α⃗, β⃗) with α⃗ = (1, 2), β⃗ = (3, 3).

It is once again clear that M_{n,m}^{ℓ}(α⃗, β⃗) = 0 unless 0 ≤ m ≤ n, as well as that M_{0,0}^{ℓ}(α⃗, β⃗) = 1. For any pair α⃗, β⃗, we may then assemble an infinite, lower-triangular array whose (n, m) entry is M_{n,m}^{ℓ}(α⃗, β⃗). We call this triangle the (α⃗, β⃗)-colored Motzkin triangle.

As with the (α, β)-colored Motzkin triangle of Section 1, the (α⃗, β⃗)-colored Motzkin triangle is a proper Riordan array for every choice of α⃗ and β⃗:

Proposition 2.1. Fix ℓ ≥ 1, and let α⃗ = (α_{0}, …, α_{ℓ−1}), β⃗ = (β_{0}, …, β_{ℓ−1}) be any pair of ℓ-tuples of non-negative integers. Then the (α⃗, β⃗)-colored Motzkin triangle is a proper Riordan array with A- and Z-sequences

A(t) = 1 + β_{0}t + ⋯ + β_{ℓ−1}t^{ℓ} + t^{ℓ+1}, Z(t) = α_{0} + α_{1}t + ⋯ + α_{ℓ−1}t^{ℓ−1} + t^{ℓ}.

Proof. In a manner similar to the proof of Proposition 1.1, we demonstrate the recurrences

M_{n,m}^{ℓ}(α⃗, β⃗) = \begin{cases}M_{n−1,m−1}^{ℓ}(α⃗, β⃗) + β_{0}M_{n−1,m}^{ℓ}(α⃗, β⃗) + ⋯ + M_{n−1,m+ℓ}^{ℓ}(α⃗, β⃗), & if m ≥ 1; \\ α_{0}M_{n−1,0}^{ℓ}(α⃗, β⃗) + α_{1}M_{n−1,1}^{ℓ}(α⃗, β⃗) + ⋯ + M_{n−1,ℓ}^{ℓ}(α⃗, β⃗), & if m = 1. \end{cases}

For m ≥ 1, we partition the paths of M_{n,m}^{ℓ}(α⃗, β⃗) according to their final step. Those paths that end with a U step are in bijection with M_{n−1,m−1}^{ℓ}(α⃗, β⃗), and those that end with a D_{i} step of a fixed color are in bijection with M_{n−1,m+i}^{ℓ}(α⃗, β⃗), for every 0 ≤ i ≤ ℓ and for each of the β_{i} colors of that i. The m = 1 case is similar, although here the elements of M_{n,m}^{ℓ}(α⃗, β⃗) cannot end with a U step and the D_{i} steps can carry one of α_{i} possible colors.

Proposition 2.1 may be used to quickly generate elements of the (α⃗, β⃗)-colored Motzkin triangle. In the order-ℓ case, the (α⃗, β⃗)-colored Motzkin numbers of order ℓ constitute a 2ℓ-dimensional array of integer sequences that can be compared to previously-studied results, as in Table 1. Appendix A presents a series of tables that test the resulting sequences against OEIS [25], for a variety of “nice” choices of α⃗, β⃗ in the ℓ = 2 case.

2.1 General properties of colored Motzkin triangles

We begin by proving a number of general identities involving the (α⃗, β⃗)-colored Motzkin numbers and their associated Riordan arrays. Much of what follows is most easily cast in terms of generating functions. As such, for any m, ℓ, α⃗, β⃗ we define the ordinary generating function M_{m}^{ℓ}(α⃗, β⃗, t) = ∑_{n=0}^{∞} M_{n,m}^{ℓ}(α⃗, β⃗)t^{n}. In the specific case of ℓ = 1, many of the results below follow directly from the work of Flajolet [11], whereas the special case of α⃗ = β⃗ is in alignment with the results of Banderier and Flajolet [3].

Our first result relates the m ≥ 1 columns of the (α⃗, β⃗)-colored Motzkin triangle to the m = 0 column, letting us characterize the d(t), h(t) series of the associated Riordan arrays.

Proposition 2.2. Fix ℓ ≥ 1 and take any pair of ℓ-tuples of non-negative integers α⃗, β⃗. For every m ≥ 1,

M_{m}^{ℓ}(α⃗, β⃗, t) = tM_{0}^{ℓ}(α⃗, β⃗, t)M_{m−1}^{ℓ}(β⃗, β⃗, t) = t^{m}M_{0}^{ℓ}(α⃗, β⃗, t)M_{0}^{ℓ}(β⃗, β⃗, t)^{m}.

Proof. Every height-m path may be decomposed into a height-0 path and a height-(m − 1) path as shown below, with the intermediate U step in that image being the rightmost U step that ends at height 1. The labels inside the boxes denote the colorings applicable to each subpath, with the second coloration changing because none of its steps terminate at an overall height of 0.

\begin{matrix}(α⃗, β⃗) \\ (β⃗, β⃗) \\ (n, m) \end{matrix}

The decomposition implied above immediately demonstrates the first equality. The second equality follows from repeated application of the first equality.

Corollary 2.3. For any ℓ ≥ 1 and any pair of ℓ-tuples of non-negative integers α⃗, β⃗, the (α⃗, β⃗)- colored Motzkin triangle is the proper Riordan array R(d(t), h(t)) with d(t) = M_{0}^{ℓ}(α⃗, β⃗, t) and h(t) = tM_{0}^{ℓ}(β⃗, β⃗, t).

Proof. From Proposition 2.2, we see that the j^{th}-column of the (α⃗, β⃗)-colored Motzkin triangle

has generating function t^{j}M_{0}^{ℓ}(α⃗, β⃗, t)M_{0}^{ℓ}(β⃗, β⃗, t)^{j} = M_{0}^{ℓ}(α⃗, β⃗, t) (tM_{0}^{ℓ}(β⃗, β⃗, t))^{j}.

Unfortunately, Corollary 2.3 is only of practical use if we have an explicit formula for the generating functions M_{0}^{ℓ}(α⃗, β⃗, t), and such a formula will not be attempted here. Still of conceptual interest is the well-known fact that the row-sums of the Riordan array R(d(t), h(t)) has generating function d(t)/(1 − h(t)). As the row-sums of the (α⃗, β⃗)-colored Motzkin triangle enumerate (α⃗, β⃗)- Motzkin paths of length n and any height m ≥ 0, we have:

Corollary 2.4. For any ℓ ≥ 1 and any pair of ℓ-tuples of non-negative integers α⃗, β⃗, the generating function for (α⃗, β⃗)-colored Motzkin paths of length n and any height m ≥ 0 is

∑_{m=0}^{∞} M_{m}^{ℓ}(α⃗, β⃗, t) = \frac{M_{0}^{ℓ}(α⃗, β⃗, t)}{1 − tM_{0}^{ℓ}(β⃗, β⃗, t)} = M_{0}^{ℓ}(α⃗, β⃗, t) (1 + tM_{0}^{ℓ}(β⃗, β⃗, t) + t^{2}M_{0}^{ℓ}(β⃗, β⃗, t)^{2} + ⋯) .

Of greater practical importance is the alternative characterization of row-sums presented below, which applies only when α⃗ = β⃗. In Section 3, this result will allow us to immediately translate every combinatorial interpretations for (α⃗, α⃗)-colored Motzkin numbers into an associated combinatorial interpretation for (α⃗ + ê_{1}, α⃗)-colored Motzkin numbers.

Theorem 2.5. Fix ℓ ≥ 1 and take any ℓ-tuple of non-negative integers α⃗. If ê_{1} = (1, 0, …, 0), the generating function for (α⃗, α⃗)-colored Motzkin paths of length n and any height m ≥ 0 is

∑_{m=0}^{∞} M_{m}^{ℓ}(α⃗, α⃗, t) = M_{0}^{ℓ}(α⃗ + ê_{1}, α⃗, t).

Proof. We construct a bijection ϕ_{n} from S = ⋃_{m=0}^{∞} M_{n,m}^{ℓ}(α⃗, α⃗) to M_{n,0}^{ℓ}(α⃗ + ê_{1}, α⃗), for arbitrary n ≥ 0. So take any path P ∈ S, and assume that P has height m. Then P contains precisely m up steps that are “visible” from the right, meaning that they are the rightmost U steps at their particular height. Replacing these U steps with (temporarily-uncolored) level steps yields a path with m uncolored D_{0} steps at height y = 0. Coloring these D_{0} steps with a new color α_{0} + 1 results in a unique element ϕ_{n}(P) ∈ M_{n,0}^{ℓ}(α⃗ + ê_{1}, α⃗).

See Figure 4 for an example of this map ϕ_{n}. This process is clearly invertible. As the only D_{0} steps at height 0 with the new color α_{0} + 1 are those added by ϕ_{n}, the inverse map ϕ_{n}^{−1} involves replacing all D_{0} steps of color (α_{0} + 1) with U steps.

1 1 1  ⇔  1 2 1 2 1

Figure 4: An example of the bijection from the proof of Theorem 2.5, here with ℓ = 2, m = 2, and α⃗ = (1, 1).

The proof of Theorem 2.5 does not extend to the colorations where α⃗ ≠ β⃗, as the bijection ϕ_{n} may translate D_{i} steps that end at nonzero height to D_{i} steps that end at height 0. One may still apply Proposition 2.2 to Theorem 2.5 to obtain the more general formula below.

Corollary 2.6. Fix ℓ ≥ 1 and take any pair of ℓ-tuples of non-negative integers α⃗, β⃗. If ê_{1} = (1, 0, …, 0), the generating function for (α⃗, β⃗)-colored Motzkin paths of length n and any height m ≥ 0 is

∑_{m=0}^{∞} M_{m}^{ℓ}(α⃗, β⃗, t) = M_{0}^{ℓ}(α⃗, β⃗, t) + tM_{0}^{ℓ}(α⃗, β⃗, t)M_{0}^{ℓ}(β⃗ + ê_{1}, β⃗, t).

Proof. Partially-expanding the summation ∑_{m=0}^{∞} M_{m}^{ℓ}(α⃗, β⃗, t) and applying Proposition 2.2 to every M_{m}^{ℓ}(α⃗, β⃗, t) with m ≥ 1 gives

∑_{m=0}^{∞} M_{m}^{ℓ}(α⃗, β⃗, t) = M_{0}^{ℓ}(α⃗, β⃗, t) + ∑_{m=1}^{∞} M_{m}^{ℓ}(α⃗, β⃗, t) = M_{0}^{ℓ}(α⃗, β⃗, t) + ∑_{m=1}^{∞} tM_{0}^{ℓ}(α⃗, β⃗, t)M_{m−1}^{ℓ}(β⃗, β⃗, t).

Rewriting the expression above and applying Theorem 2.5 to the result gives

= M_{0}^{ℓ}(α⃗, β⃗, t) + tM_{0}^{ℓ}(α⃗, β⃗, t) ∑_{m=0}^{∞} M_{m}^{ℓ}(β⃗, β⃗, t) = M_{0}^{ℓ}(α⃗, β⃗, t) + tM_{0}^{ℓ}(α⃗, β⃗, t)M_{0}^{ℓ}(β⃗ + ê_{1}, β⃗, t).

We now turn to results involving standard transforms of (α⃗, β⃗)-colored Motzkin numbers. Given an integer sequence (a_{i})_{i≥0}, recall that the binomial transform of that sequence is the integer sequence (b_{i})_{i≥0} that satisfies b_{n} = ∑_{i=0}^{n} \binom{n}{i}a_{i} for all n ≥ 0. The following theorem characterizes the binomial transform of an arbitrary column in the (α⃗, β⃗)-colored Motzkin triangle. It should be noted that the ℓ = 1, m = 0 case of this theorem, along with the combinatorial interpretation shown in Table 1, recovers the well-known result that the binomial transform of the Motzkin numbers is the (shifted) Catalan numbers.

Theorem 2.7. Fix ℓ ≥ 1 and m ≥ 0, and take any pair of ℓ-tuples of non-negative integers α⃗, β⃗. If ê_{1} = (1, 0, …, 0), the binomial transform of the sequence (M_{n,m}^{ℓ}(α⃗, β⃗))_{n≥0} is the sequence (M_{n,m}^{ℓ}(α⃗ + ê_{1}, β⃗ + ê_{1}))_{n≥0}. Explicitly,

∑_{i=0}^{n} \binom{n}{i}M_{i,m}^{ℓ}(α⃗, β⃗) = M_{n,m}^{ℓ}(α⃗ + ê_{1}, β⃗ + ê_{1}).

Proof. The set M_{n,m}^{ℓ}(α⃗ + ê_{1}, β⃗ + ê_{1}) may be partitioned into the subsets ⋃_{i=0}^{n−m} S_{i}, where a path P ∈ M_{n,m}^{ℓ}(α⃗ + ê_{1}, β⃗ + ê_{1}) lies in S_{i} if and only if it contains precisely i level steps of the final color for its given height (i total D_{0} steps colored either α_{0} + 1 or β_{0} + 1). Deleting those D_{0} steps defines map ψ_{i} : S_{i} → M_{n−i,m}^{ℓ}(α⃗, β⃗) for each 0 ≤ i ≤ n − m. Each map ψ_{i} is clearly surjective but not injective, with differing locations for the i deleted level steps ensuring that \binom{n}{i} distinct elements of S_{i} map to each path in M_{n−i,m}^{ℓ}(α⃗, β⃗). It follows that |S_{i}| = \binom{n}{i}M_{n−i,m}^{ℓ}(α⃗, β⃗) for all 0 ≤ i ≤ n − m, from which the result follows.

3 Combinatorial interpretations of higher-order colored Motzkin numbers

For the remainder of this paper, we develop bijections between a variety of well-understood combinatorial objects and collections of (α⃗, β⃗)-colored Motzkin paths. This will result in a collection of new combinatorial interpretations for (α⃗, β⃗)-colored Motzkin numbers that directly generalize the order ℓ = 1 combinatorial interpretations of Table 1.

3.1 Higher-order colored Motzkin numbers and k-Dyck paths

Our first set of combinatorial objects are k-Dyck paths, sometimes referred to as k-ary paths. For any k ≥ 2, a k-Dyck path of length n and height m is an integer lattice path from (0, 0) to (n, m) that uses the step set {U = (1, 1), D_{k−1} = (1, 1 − k)} and remains weakly above y = 0. It is obvious that k-Dyck paths are in bijection with (α⃗, β⃗)-colored Motzkin paths of order (k − 1) and coloring α⃗ = β⃗ = 0. We look for more interesting bijections here.

It can be shown that a point (x, y) may lie on a k-Dyck path only if n ≡ m (mod k). This motivates our choice of dealing only with k-Dyck paths of length kn for some n ≥ 0. We denote the collection of k-Dyck paths of length kn (“semilength” n) and height km (“semiheight” m) by D_{n,m}^{k}, and let |D_{n,m}^{k}| = D_{n,m}^{k}.

It is well-known that k-Dyck paths of height 0 are enumerated by the k-Catalan numbers (one-parameter Fuss-Catalan numbers) as D_{n,0}^{k} = C_{n}^{k} = \frac{1}{kn+1} \binom{kn+1}{n}. Fixing k ≥ 2, we define the ordinary generating function C_{k}(t) = ∑_{n=0}^{∞} C_{n}^{k}t^{n}. It is also well-known that these generating functions satisfy C_{k}(t) = 1 + tC_{k}(t)^{k} for all k ≥ 2. For more information about k-Dyck paths and other combinatorial interpretations of the k-Catalan numbers, see Hilton and Pedersen [14] or Heubach, Li and Mansour [13].

In the order ℓ = 1 case, Table 1 reveals a bijection between D_{n,0}^{2} and (2, 2)-colored Motzkin paths, as well as a bijection between D_{n+1,0}^{2} and (1, 2)-colored Motzkin paths. These are the bijections that we look to generalize in this subsection. To do this, begin by observing that D_{n+1,0}^{2} is in bijection with “generalized 2-Dyck paths” of semilength n that stay weakly above the line y = −1, via the map that deletes the initial U step and final D_{1} step of each P ∈ D_{n+1,0}^{2}.

So fix k ≥ 2 and take any a ≥ 0. We define a generalized k-Dyck path of depth a, semilength n, and semiheight m to be an integer lattice path from (0, 0) to (kn, km) that uses the step set {U = (1, 1), D_{k−1} = (1, 1 − k)} and stays weakly above the line y = −a. By analogy with above, we denote the set of all such paths by D_{n,m}^{k,a} and let |D_{n,m}^{k,a}| = D_{n,m}^{k,a}.

The sets D_{n,m}^{k,a} were investigated as “k-Dyck paths with a negative boundary” by Prodinger [17], who showed that D_{n,0}^{k,a} = \frac{a+1}{kn+a+1} \binom{kn+a+1}{n} when 0 ≤ a ≤ k − 1. Our results will apply over the same range of depths and may be applied to give an alternative derivation of Prodinger’s closed formula in terms of proper Riordan arrays.

Now fix k ≥ 2 and a ≥ 0, and define D^{k,a} to be the infinite, lower-triangular array of nonnegative integers whose (n, m) entry (for 0 ≤ m ≤ n) is D_{n,m}^{k,a}. Our approach is to show that these integer triangles represent the same proper Riordan arrays as (α⃗, β⃗)-colored Motzkin triangles for particular choices of α⃗, β⃗.

Theorem 3.1. For any k ≥ 2 and 0 ≤ a ≤ k − 1, D^{k,a} is a proper Riordan array with A- and Z-sequences

A(t) = (1 + t)^{k}, Z(t) = \frac{(1 + t)^{k} − (1 + t)^{k−a−1}}{t} .

Proof. As in the proof of Proposition 2.1, it suffices to prove the recurrences

D_{n,m}^{k,a} = \begin{cases}\binom{k}{0}D_{n−1,m−1}^{k,a} + ⋯ + \binom{k}{k}D_{n−1,m+k−1}^{k,a}, & if m ≥ 1; \\ (\binom{k}{1} − \binom{k−a−1}{1}) D_{n−1,0}^{k,a} + ⋯ + (\binom{k}{k} − \binom{k−a−1}{k}) D_{n−1,k−1}^{k,a}, & if m = 0. \end{cases}

For any m ≥ 0, we partition D_{n,m}^{k,a} into sets S_{Q_{2}} whereby P ∈ D_{n,m}^{k,a} lies in S_{Q_{2}} if P decomposes as P = Q_{1}Q_{2} for the length-k terminal subpath Q_{2}. For P = Q_{1}Q_{2}, observe that Q_{1} ∈ D_{n−1,m−1+j}^{k,a} if Q_{2} contains precisely j down steps. This implies that |S_{Q_{2}}| = D_{n−1,m−1+j}^{k,a} for every valid choice of Q_{2}, via the bijection that takes P = Q_{1}Q_{2} to Q_{1}.

All that’s left is to enumerate length-k subpaths Q_{2} that end with semiheight m ≥ 0, contain precisely 0 ≤ j ≤ k down steps, and remain weakly above y = −a. When m ≥ 1, it is impossible for such a subpath (for any j) to go below y = 0 and still end at height (k − 1)m. This would require a full complement of k up steps to travel from y = −1 to a height of at least (k − 1), and we’re assuming that Q_{2} began with non-negative height. It follows that there are \binom{k}{j} valid choices of Q_{2} with precisely j down steps when m ≥ 1, giving the first line of our desired recurrence.

When m = 0, not all \binom{k}{j} potential subpaths Q_{2} will remain weakly above y = −a. We enumerate the “bad” length-k subpaths that that go below y = −a. Every such “bad” subpath Q_{2} has a rightmost step p that terminates at height −a−1. We claim that p may only be followed by up steps. This is because, if p were followed by any D_{k−1} steps, then p would also need to be followed by at least (k − 1) + (a + 1) ≥ k up steps if we want Q_{2} to end at height 0. It follows that “bad” subpaths Q_{2} must decompose as Q_{2} = Q_{3}pU^{a+1}, with the j down steps of Q_{2} being distributed among the k − a − 1 steps of the sub-subpath Q_{3}p. It follows that there are precisely \binom{k−a−1}{j} “bad” choices of Q_{2} with precisely j down steps, and thus that there are precisely \binom{k}{j} − \binom{k−a−1}{j} valid choices of Q_{2} with precisely j down steps. This gives the second line of our desired recurrence.

Corollary 3.2. Fix k ≥ 2. For all n ≥ 0, 0 ≤ m ≤ n, and 0 ≤ a ≤ k − 1, the equality D_{n,m}^{k,a} = M_{n,m}^{k−1}(α⃗, β⃗) holds for (k − 1)-tuples α⃗ = (α_{0}, …, α_{k−2}) and β⃗ = (β_{0}, …, β_{k−2}) with α_{i} = \binom{k}{i+1} − \binom{k−a−1}{i+1} and β_{i} = \binom{k}{i+1} for all 0 ≤ i ≤ k − 2.

Proof. This follows directly from a comparison of Proposition 2.1 and Theorem 3.1.

Note the order shift of Corollary 3.2: generalized k-Dyck paths correspond to order-(k − 1) colored Motzkin paths. Also notice this represents a bijection between generalized Dyck paths of length kn and colored Motzkin paths of length n. The reason that Theorem 3.1 and Corollary 3.2 fail to generalize to a ≥ k is because generalized Dyck paths of those depths may have negative semidepth m, making it is impossible to arrange the cardinalities D_{n,m}^{k,a} into a proper Riordan array.

For k = 2, 3, 4, the (k − 1)-tuples (α⃗, β⃗) that result from Corollary 3.2 are summarized in Table 2. See Appendix A for how these colorations fit within the broader scheme of (α⃗, β⃗)-colored Motzkin paths.

\begin{matrix}α⃗, β⃗ & a = 0 & a = 1 & a = 2 & a = 3 \\ k = 2 & (1), (2) & (2), (2) & - & - \\ k = 3 & (1, 2), (3, 3) & (2, 3), (3, 3) & (3, 3), (3, 3) & - \\ k = 4 & (1, 3, 3), (4, 6, 4) & (2, 5, 4), (4, 6, 4) & (3, 6, 4), (4, 6, 4) & (4, 6, 4), (4, 6, 4) \end{matrix}

Table 2: (k − 1)-tuples α⃗, β⃗ such that D_{n,m}^{k,a} = M_{n,m}^{k−1}(α⃗, β⃗), as proven in Corollary 3.2.

As it will be helpful in upcoming subsections, we briefly outline one explicit bijection between D_{n,m}^{k,a} and M_{n,m}^{k−1}(α⃗, β⃗) for the tuples α⃗, β⃗ of Corollary 3.2. So take P ∈ M_{n,m}^{k−1}(α⃗, β⃗), and take any step p of P that begins at height y_{1} and ends at height y_{2}. We replace p with a length-k subpath with step set {U, D_{k−1}} that begins at height ky_{1} and ends at height ky_{2}. If p is a U step, the only way to do this is with a subpath of k consecutive U steps. If p is a D_{i} step, the new subpath must contain precisely i + 1 total D_{k−1} steps and k − i − 1 total U steps. There are \binom{k}{i+1} such length-k subpaths: the specific subpath chosen is determined by the coloring of the D_{i} step being replaced. All such length-k subpaths stay above y = 0 (and hence above y = −a) when y_{2} ≥ 1, whereas some subpaths may go below y = −a when y_{2} = 0. The colorations (α⃗, β⃗) of Corollary 3.2 provide the number of valid length-k subpaths. See Figure 5 for an example of this bijection.

1 2 1 2  ⇔

Figure 5: An example of our bijection between M_{n,m}^{k−1}(α⃗, β⃗) and D_{n,m}^{k,a} for k = 2 and a = 1. Here, U steps in the Motzkin path are replaced by a UU subpath in the 2-Dyck , D_{1} steps are replaced by DD, D_{0} steps of color 1 are replaced by UD, and D_{0} steps of color 2 are replaced by DU. Notice that forbidding D_{0} steps of color 2 at height y = 0 prevents the resulting 2-Dyck path from dropping below y = 0.

Theorem 3.1 may be used to find the generating functions d(t), h(t) of the proper Riordan array R(d(t), h(t)) with entries D_{n,m}^{k,a}. As seen in Corollary 3.3, these Riordan arrays are “Fuss-Catalan triangles” of the type introduced by He and Shapiro [12] and further examined by Drube [10].

Corollary 3.3. For any k ≥ 2 and 0 ≤ a ≤ k − 1, D^{k,a} is the proper Riordan array R(d(t), h(t)) with d(t) = C_{k}(t)^{a+1} and h(t) = tC_{k}(t)^{k}.

Proof. Given A(t) and Z(t) from Theorem 3.1, we merely need to verify the identities of (2). Using the k-Catalan identity C_{k}(t) = 1 + tC_{k}(t)^{k}, we have

tA(h(t)) = t(1 + tC_{k}(t)^{k})^{k} = tC_{k}(t)^{k} = h(t), and

\frac{d(0)}{1 − tZ(h(t))} = \frac{1}{1 − t (\frac{(1+tC_{k}(t)^{k})^{k}−(1+tC_{k}(t)^{k})^{k−a−1}}{tC_{k}(t)^{k}} )} = \frac{1}{1 − \frac{C_{k}(t)^{k}−C_{k}(t)^{k−a−1}}{C_{k}(t)^{k}}}

= \frac{1}{\frac{C_{k}(t)^{k}−C_{k}(t)^{k}+C_{k}(t)^{k−a−1}}{C_{k}(t)^{k}}} = \frac{C_{k}(t)^{k}}{C_{k}(t)^{k−a−1}} = C_{k}(t)^{a+1} = d(t).

For one final result involving k-Dyck paths, notice that the a = k − 1 case of Corollary 3.2 places D_{n,m}^{k,k−1} in bijection with M_{n,m}^{k−1}(α⃗, β⃗) for which α⃗ = β⃗. We may then apply Theorem 2.5 to enumerate generalized k-Dyck paths of fixed length and any semiheight.

Corollary 3.4. Fix k ≥ 2. For all n ≥ 0, the equality ∑_{m=0}^{n} D_{n,m}^{k,k−1} = M_{n,m}^{k−1}(α⃗, α⃗) holds for the (k − 1)-tuple α⃗ = (α_{0}, …, α_{k−2}) with α_{0} = k + 1 and α_{i} = \binom{k}{i+1} for all 1 ≤ i ≤ k − 2.

3.2 Higher-order colored Motzkin numbers and (k,r)-Fine paths

Our second set of combinatorial objects are subsets of k-Dyck paths that we refer to as (k, r)-Fine paths. These are an entirely new notion that intuitively generalize the concept of Fine paths from k = 2 to all k ≥ 2.

A Fine path of length n and height m is an element of D_{n,m}^{2} that lacks a subpath of the form UD_{1} ending at height y = 0. Forbidden subpaths of this type are called “hills”, meaning that Fine path are 2-Dyck paths that lack hills. It is well-known that Fine paths of height 0 are enumerated by the Fine numbers (F_{n})_{n≥0}, an integer sequence (\underline{A000957}) that begins 1, 0, 1, 2, 6, 18, . . .. The Fine numbers have an ordinary generating function F (t) that satisfies F (t) = \frac{1}{1−t^{2}C_{2}(t)^{2}} = \frac{C_{2}(t)}{1+tC_{2}(t)}. For more results about Fine paths and the Fine numbers, see Deutsch and Shapiro [8].

The notion of a “hill” becomes more ambiguous when you generalize from 2-Dyck paths to k-Dyck paths when k > 2. For fixed k ≥ 2, we identify k − 1 competing definitions for a Fuss-Catalan analogue of Fine paths, each of which forbids different classes of subpaths that end at height 0. So fix k ≥ 2, and take any 1 ≤ r ≤ k − 1. A (k, r)-Fine path of semilength n and semiheight m is an element of D_{n,m}^{k} that lacks a subpath of the form U^{r}D_{k−1} that ends at height 0. Clearly, (k, r_{1})-Fine paths are a subset of (k, r_{2})-Fine paths for all r_{1} < r_{2}. See Figure 6 for a simple example.

Figure 6: A trio of 3-Dyck paths, the first of which is both (3, 2)-Fine and (3, 1)-Fine, the second of which is (3, 2)-Fine but not (3, 1)-Fine, and the third of which is neither (3, 2)-Fine nor (3, 1)-Fine. Generalized “hills” are shown in red.

As in Subsection 3.1, we further generalize the notion of (k, r)-Fine paths to paths that stay weakly above y = −a for any 0 ≤ a ≤ k − 1. We define a generalized (k, r)-Fine path of depth a, semilength n, and semiheight m to be an element of D_{n,m}^{k,a} lacking a subpath of the form U^{r}D_{k−1} that ends at height 0. We denote the set of all such paths F_{n,m}^{k,a,r} and let |F_{n,m}^{k,a,r}| = F_{n,m}^{k,a,r}. We refer to the sequences (F_{n,0}^{k,0,r})_{n≥0} as the (k, r)-Fine numbers.

Also mirroring Subsection 3.1, for any k ≥ 2, a ≥ 0, and 1 ≤ r ≤ k − 1 we define F^{k,a,r} to be the infinite, lower-triangular array whose (n, m) entry (for 0 ≤ m ≤ n) is F_{n,m}^{k,a,r}. Our approach is once again to identify the proper Riordan array associated with each triangle F^{k,a,r} and compare the results to Proposition 2.1.

Theorem 3.5. For any k ≥ 2, 0 ≤ a ≤ k − 1, and 1 ≤ r ≤ k − 1, F^{k,a,r} is a proper Riordan array with A- and Z-sequences

A(t) = (1 + t)^{k}, Z(t) = \frac{(1 + t)^{k} − (1 + t)^{k−a−1}}{t} − (1 + t)^{k−r−1}.

Proof. The argument is largely equivalent to the proof of Theorem 3.1. The only difference comes in the m = 0 case, where we also need to exclude potential length-k terminal subpaths Q_{2} that introduce a “hill” of the form U^{r}D_{k−1}.

As a point along a k-Dyck path can only return to y = 0 when its x-coordinate is divisible by k, all subpaths Q_{2} that introduce a hill U^{r}D_{k−1} must do so over their final r + 1 steps. This leaves k −r −1 steps at the beginning of our terminal subpath, the totality of which must begin at height kj (for some j ≥ 0) and end at height y = k − 1 − r. It follows that, if Q_{2} begins at height kj and ends at height 0, it must contain precisely j + 1 steps of type D_{k−1}, and that precisely j of those D_{k−1} steps must be within its first k − r − 1 steps. All of this means there are precisely \binom{k−r−1}{j} potential subpaths Q_{2} that begin at height kj, end at height 0, and introduce a hill of the form U^{r}D_{k−1}.

Since they must reach a height of k−1−r ≥ 0 after their first k−r−1 steps, the aforementioned restrictions of when a k-Dyck path can return to y = 0 ensures that none of the \binom{k−r−1}{j} hillintroducing subpaths Q_{2} enumerated above can go below y = 0. This ensures that no potential subpaths Q_{2} are “doubly excluded” when citing the proof of Theorem 3.1, and we may modify the m = 0 recurrence from that theorem to give F_{n,0}^{k,a,r} = (\binom{k}{1} − \binom{k−a−1}{1} − \binom{k−r−1}{0}) F_{n−1,0}^{k,a,r} + ⋯ + (\binom{k}{k} − \binom{k−a−1}{k} − \binom{k−r−1}{k−1}) F_{n−1,k−1}^{k,a,r}.

The desired A-sequence carries over from Theorem 3.1, whereas the desired Z-sequence follows directly from the recurrence above.

Corollary 3.6. Fix k ≥ 2. For all n ≥ 0, 0 ≤ m ≤ n, 0 ≤ a ≤ k − 1, and 1 ≤ r ≤ k − 1, the equality F_{n,m}^{k,a,r} = M_{n,m}^{k−1}(α⃗, β⃗) holds for the (k − 1)-tuples α⃗ = (α_{0}, …, α_{k−2}) and β⃗ = (β_{0}, …, β_{k−2}) with α_{i} = \binom{k}{i+1} − \binom{k−a−1}{i+1} − \binom{k−r−1}{i} and β_{i} = \binom{k}{i+1} for all 0 ≤ i ≤ k − 2.

Proof. Follows from a comparison of Proposition 2.1 and Theorem 3.5

For k = 2, 3, 4 and a = 0, the (k −1)-tuples (α⃗, β⃗) guaranteed by Corollary 3.6 are summarized in Table 3. Once again, see Appendix A for how these colorations fit within the wider context of (α⃗, β⃗)-colored Motzkin paths.

The explicit bijection between D_{n,m}^{k,a} and M_{n,m}^{k−1}(α⃗, β⃗) from Subsection 3.1 restricts to a bijection between F_{n,m}^{k,a,r} and a (distinct) set of colored Motzkin paths M_{n,0}^{k−1}(α⃗, β⃗), with α⃗, β⃗ as determined by Corollary 3.6. Also similar to Subsection 3.1 is the fact Theorem 3.5 may be used to characterize the integer triangles F^{k,a,r} as proper Riordan arrays:

\begin{matrix}α⃗, β⃗ & a = 0, r = 1 & a = 0, r = 2 & a = 0, r = 3 \\ k = 2 & (0), (2) & - & - \\ k = 3 & (0, 1), (3, 3) & (0, 2), (3, 3) & - \\ k = 4 & (0, 1, 2), (4, 6, 4) & (0, 2, 3), (4, 6, 4) & (0, 3, 3), (4, 6, 4) \end{matrix}

Table 3: (k − 1)-tuples α⃗, β⃗ such that F_{n,0}^{k,a,r} = M_{n,0}^{k−1}(α⃗, β⃗), as proven in Corollary 3.6.

Corollary 3.7. For any k ≥ 2, 0 ≤ a ≤ k − 1, and 1 ≤ r ≤ k − 1, F^{k,a,r} is the proper Riordan array R(d(t), h(t)) with d(t) = \frac{C_{k}(t)^{k}}{C_{k}(t)^{k−a−1}+tC_{k}(t)^{2k−r−1}} and h(t) = tC_{k}(t)^{k}.

Proof. We use A(t), Z(t) from Theorem 3.5 to verify the identities of (2). As A(t) is the same as in Subsection 3.1, verification of h(t) is identical to the proof of Corollary 3.3. Verification of d(t) now takes the form

\frac{d(0)}{1 − tZ(h(t))} = \frac{1}{1 − (\frac{(1+tC_{k}(t)^{k})^{k}−(1+tC_{k}(t)^{k})^{k−a−1}}{tC_{k}(t)^{k}} − (1 + tC_{k}(t)^{k})^{k−r−1})}

= \frac{1}{1 − t (\frac{C_{k}(t)^{k}−C_{k}(t)^{k−a−1}}{tC_{k}(t)^{k}} − C_{k}(t)^{k−r−1})} = \frac{1}{1 − 1 + \frac{C_{k}(t)^{k−a−1}}{C_{k}(t)^{k}} + tC_{k}(t)^{k−r−1}}

\frac{C_{k}(t)^{k}}{C_{k}(t)^{k−a−1} + tC_{k}(t)^{2k−r−1}} = d(t).

Substituting a = 0 into d(t) from Corollary 3.7 provides a relatively simple relationship for the generating function F_{k,r}(t) of the (k, r)-Fine numbers (F_{n,0}^{k,0,r})_{n≥0} as F_{k,r}(t) = \frac{C_{k}(t)}{1+tC_{k}(t)^{k−r}}. Observe

that this formula simplifies to the well-known relationship of F (t) = \frac{C_{2}(t)}{1+tC_{2}(t)} in the case of k = 2, r = 1.

3.3 Higher-order colored Motzkin numbers and k-Dyck paths with restrictions on peak heights

We now consider subsets of k-Dyck paths whose peaks must appear at a fixed height, modulo k. By a “peak” we mean any subpath of the form UD_{k−1}, with the height of a peak equaling the height of (the right end of) the U step in the subpath.

For any 0 ≤ i ≤ k − 1, we say that P ∈ D_{n,m}^{k,a} has peak parity i if the height of every one of its peaks is equivalent to i (mod k). We denote the subset of D_{n,m}^{k,a} consisting of all paths with peak parity i by D_{n,m}^{k,a}(i). To avoid the ambiguity of categorizing paths of length 0, which have no peaks, we henceforth restrict our attention to sets D_{n,m}^{k,a}(i) with n > 0.

The goal of this subsection is to generalize the following pair of identities, which were originally proven by Callan [6]:

1. The set D_{n,0}^{2,0}(0) consisting of all 2-Dyck paths with peaks only at even height is enumerated by the Riordan numbers R_{n} = M_{n,0}(0, 1).

2. The set D_{n,0}^{2,0}(1) consisting of all 2-Dyck paths with peaks only at odd height is enumerated by the shifted Motzkin numbers M_{n−1} = M_{n−1,0}(1, 1).

The parity-0 case, corresponding to Callan’s first identity, may be directly generalized as follows:

Theorem 3.8. Fix k ≥ 2 and 0 ≤ a ≤ k − 1. Then |D_{n,m}^{k,a}(0)| = M_{n,m}^{k−1}(α⃗,1) for all n, m, where 1 = (1, 1, …, 1) and α⃗ = (α_{0}, …, α_{k−2}) satisfies

α_{i} = \begin{cases}1, & if i < a; \\ 0, & if i ≥ a. \end{cases}

Proof. As points (x, y) along P ∈ D_{n,m}^{k,a}(0) must satisfy x ≡ y (mod k), all peaks in P ∈ D_{n,m}^{k,a}(0) must have x-coordinates that are divisible by k. This means that every such P may be subdivided into a sequence of length-k subpaths, each of which is of the form (D_{k−1})^{i}U^{k−i} for some 0 ≤ i ≤ k. For the subpath (D_{k−1})^{i}U^{k−i}, the subheight of the terminal point minus the subheight of the initial point is 1 − i. Also notice that the lowest point in the subpath (D_{k−1})^{i}U^{k−i} is k − i units lower than the terminal point of the subpath.

We define an explicit bijection ψ : M_{n,m}^{k−1}(α⃗,1) → D_{n,m}^{k,a}(0) that is similar to the bijection described in Subsection 3.1. So take any P ∈ M_{n,m}^{k−1}(α⃗,1). To obtain ψ(P), replace each U step of P with the length-k subpath U^{k}, and (for each 0 ≤ i ≤ k − 1) replace each D_{i} step of P with the length-k subpath (D_{k−1})^{i+1}U^{k−i−1}. For an example of this map, see Figure 7.

The map ψ is clearly injective, and its image is clearly some subset of generalized k-Dyck path of semilength n and semiheight m. By construction, all peaks in ψ(P) are at a height of 0 (mod k). As the steepest allowable down steps of P ending at height 0 are D_{a−1}, the “lowest-dipping” lengthk subpaths of ψ(P) that end at height 0 are (D_{k−1})^{a}U^{k−a} and they reach a minimum height of y = −a. Thus ψ(P) remains weakly above y = −a. The fact that ψ is surjective follows from the observation that elements of D_{n,m}^{k,a}(0) have one allowable length-k subpath with a particular overall change in subheight. The choice of α⃗ restricts the options for subpaths that end at subheight 0 to those that stay weakly above y = −a.

⇔

Figure 7: An example of the bijection between D_{n,m}^{k,a}(0) and M_{n,m}^{k−1}(α⃗,1) from the proof of Theorem 3.8, here for k = 3, n = 4, a = m = 0. In this case α⃗ = 0, so colors have been suppressed.

Corollary 3.9. Fix k ≥ 2. Then |D_{n,m}^{k,0}(0)| = M_{n,m}^{k−1}(0,1) for all n ≥ 0 and 0 ≤ m ≤ n, where 0 = (0, 0, …, 0) and 1 = (1, 1, …, 1).

The primary insight in generalizing Callan’s second identity is that D_{n,0}^{2,0}(1) lies in bijection with D_{n−1,0}^{2,1}(0). This follows from the map that deletes the initial U step and the final D_{1} step of any P ∈ D_{n,0}^{2,0}(1), and then shifts the resulting path down by one. Generalizing this map gives:

Corollary 3.10. Fix k ≥ 2. Then |D_{n,m}^{k,0}(k − 1)| = M_{n−1,m}^{k−1}(1,1) for all n ≥ 1 and 0 ≤ m ≤ n, where 1 = (1, 1, …, 1).

Proof. We establish a bijection ϕ : D_{n,0}^{k,0}(k − 1) → D_{n−1,0}^{k,k−1}(0). For any P ∈ D_{n,0}^{k,0}(k − 1), it must be the case that P decomposes as P = U^{k−1}P′D_{k−1}. Here P′ begins and ends at height k − 1 and thus corresponds to some Q ∈ D_{n−1,0}^{k,k−1}. As P has peak parity k − 1, the path Q must have peak parity 0. The map ϕ(P) = Q represents our desired bijection.

Applying Lemma 3.8 then gives |D_{n,0}^{k,0}(k − 1)| = |D_{n−1,0}^{k,k−1}(0)| = M_{n−1,0}^{k−1}(α⃗,1), where α_{i} = 1 for all i < k − 1 and thus for all coordinates 0 ≤ i ≤ k − 2.

The difficulty in generalizing Theorem 3.8 to peak parities other than 0 or k − 1 derives from the nature of our bijection between D_{n,m}^{k,a} and M_{n,m}^{k−1}(α⃗, β⃗). In particular, that bijection requires the Dyck paths have a length that is divisible by kn. The decomposition technique of Corollary 3.10 could be extended to paths of arbitrary peak parity h, but the required decomposition P = U^{h}P′D_{k−1} only leaves a central subpath P′ with length divisible by kn when h = k − 1.

3.4 Higher-order colored Motzkin numbers and k-ary trees

For one final collection of combinatorial interpretations, we turn our attention to k-ary trees. For any k ≥ 1, a k-ary tree is a rooted tree in which every vertex has at most k children. A complete k-ary tree is a k-ary tree in which every vertex has either 0 children or k children. We denote the set of all k-ary trees with precisely n edges by T_{n}^{k}, and the collection of all complete k-ary trees with precisely n edges by K_{n}^{k}.

It is well known that 2-ary trees are enumerated by the Motzkin numbers as |T_{n}^{2}| = M_{n,0}(1, 1), and that complete k-ary trees are enumerated by the k-Catalan numbers as |K_{kn}^{k}| = C_{n}^{k} = M_{n,0}^{k}(0,0) for every k ≥ 2. See Aigner [1] or Hilton and Pedersen [14] for bijections establishing these results. These are the combinatorial interpretations that we look to generalize in this subsection.

In order to consistently describe our generalized bijection, we represent k-ary trees so that the root lies at the top of the tree and all children always appear lower than their parents. One may then order the vertices of T ∈ T_{n}^{k} via a depth-first search, from left-to-right, and label each edge with one less than the integer assigned to the vertex at its bottom end. See the left side of Figure 8 for an example. This edge ordering may be used to define a generalized bijection T_{n}^{k} and M_{n,0}^{k−1}(1,1):

Proposition 3.11. For any n ≥ 0 and k ≥ 2, |T_{n}^{k}| = M_{n,0}^{k−1}(1,1), where 1 = (1, 1, …, 1).

Proof. To define our bijection ϕ : T_{n}^{k} → M_{n,0}^{k−1}(1,1), proceed through the edges of T ∈ T_{n}^{k} in the order defined by our depth-first search. Then construct the path ϕ(T) ∈ M_{n,0}^{k−1}(1,1) as follows, from left to right. If a particular edge is not a rightmost child, append a U step to the end of the partial path. If an edge is a rightmost child, and if the vertex at its top end has precisely i children, append a D_{i−1} step to the end of the partial path.

The resulting path ϕ(T) clearly ends at (n, 0) and uses the correct step set for an element of M_{n,0}^{k−1}(1,1). The fact that ϕ(T) remains weakly above y = 0 is a consequence of the depth-first search: in our edge ordering, the children of any fixed vertex have labels that increase from left to right. This means that the D_{i−1} step associated with the rightmost child is always added after the U steps of its i − 1 non-rightmost siblings.

To see that ϕ is a bijection, notice that T may be uniquely recovered from ϕ(T) as follows. For every D_{i} step in ϕ(T) with i ≥ 1, identify the i total U steps that are “visible” to that D_{i} step from the left. These matchings (which we represent via horizontal “lasers” that travel under ϕ(T)) correspond to siblings in the associated tree T. Nesting of laser matchings in ϕ(T) correspond to parent/child relationships in T. See the right side of Figure 8 for an example of this inverse procedure.

1 5 6 2 3 7 4 8 9 10  ⇔

Figure 8: An example of the bijection between T_{n}^{k} and M_{n,0}^{k−1}(1,1) from the proof of Theorem 3.4. The tree of the left side exhibits our depth-first edge ordering, whereas the dotted red lines on the right side correspond to the “lasers” used in defining the inverse map.

The bijection of Theorem 3.4 directly prompts a combinatorial interpretation for any sequence of (α⃗, β⃗)-colored Motzkin numbers where the vectors α⃗ and β⃗ are composed entirely of zeroes and ones:

Corollary 3.12. Fix k ≥ 2, and let S be an subset of {0, 1, …, k − 1}. Then define T_{n}^{k,S} ⊆ T_{n}^{k} to be the collection of all k-ary trees where every vertex must have either k children or precisely i children for some i ∈ S. Then |T_{n}^{k,S}| = M_{n,0}^{k−1}(α⃗_{S}, α⃗_{S}), where α⃗_{S} = (α_{0}, …, α_{k−1}) is the (k − 1)- tuple such that α_{i} = 1 if i ∈ S and α_{i} = 0 otherwise.

4 Acknowledgments

The authors would like to thank the Department of Mathematics and Statistics at Valparaiso University, whose Valparaiso Experience in Research by Undergraduate Mathematicians (VERUM) program provided the framework within which much of this research took place. By extension, the authors would also like to thank the National Science Foundation for funding that program, under NSF Grant DMS-1559912.

References

[1] M. Aigner, Motzkin numbers, Europ. J. Combin. 19 (1998), 663–675.

[2] M. Aigner, Enumeration via ballot numbers, Discrete Math. 308 (2008), 2544–2563.

[3] C. Banderier and P. Flajolet, Basic analytic combinatorics of directed lattice paths, Theoret. Comput. Sci. 281 (2002), 37–80.

[4] E. Barrucci, A. Del Lungo, E. Pergola and R. Pinzani, A construction for enumerating kcoloured Motzkin paths, Proc. of the First Annual International Conference on Computing and Combinatorics, Springer, 1995, pp. 254–263.

[5] F. R. Bernhart, Catalan, Motzkin, and Riordan numbers, Discrete Math. 204 (1999), 73–112.

[6] D. Callan, Bijections for Dyck paths with all peak heights of the same parity, preprint, 2017.

Available at http://arxiv.org/abs/1702.06150v1.

[7] G.-S. Cheon, H. Kim and L. W. Shapiro, Combinatorics of Riordan arrays with identical A and Z sequences, Discrete Math. 312 (2012), 2040–2049.

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

[9] R. Donaghey and L. W. Shapiro, Motzkin numbers, J. Combin. Theory Ser. A 23 (1977), 291–301.

[10] P. Drube, Generalized Path Pairs & Fuss-Catalan Triangles, preprint, 2020. Available at

http://arxiv.org/abs/2007.01892.

[11] P. Flajolet, Combinatorial aspects of continued fractions, Discrete Math. 32 (1980), 125–161.

[12] T.-X. He and L. W. Shapiro, Fuss-Catalan matrices, their weighted sums, and stabilizer subgroups of the Riordan group, Linear Algebra Appl. 532 (2017), 25–42.

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

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

[15] T. Mansour, M. Schork and Y. Sun, Motzkin numbers of higher rank: generating function and explicit expression, J. Integer Seq. 10 (2007), Article 07.7.4.

[16] D. Merlini, D. G. Rogers, R. Sprugnoli and M. C. Verri, On some alternative characterizations of Riordan arrays, Canad. J. Math. 49(2) (1997), 301–320.

[17] H. Prodinger, On k-Dyck paths with a negative boundary, preprint, 2019. Available at

http://arxiv.org/abs/1912.06930.

[18] D. G. Rogers, Pascal triangles, Catalan numbers, and renewal arrays, Discrete Math. 22 (1978), 301–310.

[19] A. Sapounakis and P. Tsikouras, On k-colored Motzkin words, J. Integer Seq. 4 (2004), Article 04.2.5.

[20] A. Sapounakis and P. Tsikouras, Counting peaks and valleys in k-colored Motzkin words, Electron. J. Comb. 12 (2005), Article 12.

[21] L. W. Shapiro, A Catalan triangle, Discrete Math. 14 (1976), 83–90.

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

[23] W. J. Woan, A recursive relation for weighted Motzkin sequences, J. Integer Seq. 8 (2005), Article 05.1.6.

[24] W. J. Woan, A relation between restricted and unrestricted weighted Motzkin paths, J. Integer Seq. 9 (2006), Article 06.1.7.

[25] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, https://oeis.org (2019).

2010 Mathematics Subject Classification: Primary 05A19; Secondary 05C30. Keywords: Motzkin number, Fine number, lattice path, Riordan array, k-ary tree.

(Concerned with sequences \underline{A000079}, \underline{A000108}, \underline{A000302}, \underline{A000400}, \underline{A000957}, \underline{A000984}, \underline{A001005}, \underline{A001006}, \underline{A001405}, \underline{A001700}, \underline{A001764}, \underline{A002212}, \underline{A002426}, \underline{A005043}, \underline{A005572}, \underline{A005573}, \underline{A005773}, \underline{A006013}, \underline{A007317}, \underline{A023053}, \underline{A026378}, \underline{A026641}, \underline{A033321}, \underline{A033543}, \underline{A036765}, \underline{A047099}, \underline{A049027}, \underline{A049128}, \underline{A054341}, \underline{A059738}, \underline{A064613}, \underline{A071879}, \underline{A076025}, \underline{A076227}, \underline{A081671}, \underline{A089354}, \underline{A098409}, \underline{A098746}, \underline{A104455}, \underline{A117641}, \underline{A121545}, \underline{A122898}, \underline{A126120}, \underline{A126568}, \underline{A126931}, \underline{A126932}, \underline{A126952}, \underline{A127358}, \underline{A127360}, \underline{A141223}, \underline{A159772}, \underline{A182401}, \underline{A185132}, \underline{A227081} and \underline{A303730}.)

A Tables of higher-order colored Motzkin numbers

A Java program was written that used Proposition 2.1 to generate the first seven rows of the (α⃗, β⃗)-colored Motzkin triangle, for order ℓ = 1, 2, 3 and arbitrary choices of α⃗, β⃗. The first columns of those Riordan arrays were then checked against OEIS [25] for pre-existing combinatorial interpretations. The results of our comparisons are shown below for ℓ = 1, 2 and various “easy” choices of α⃗, β⃗. Dashes correspond to sequences that failed to return an entry on OEIS. Java code is available upon request.

β = 0 β = 1  β = 2  β = 3 β = 4 β = 5
α = 0 \underline{A126120} \underline{A005043} \underline{A000957} \underline{A117641} \underline{A185132}  -
α = 1 \underline{A001405} \underline{A001006} \underline{A000108} \underline{A033321}  -  -
α = 2 \underline{A054341} \underline{A005773} \underline{A000108}* \underline{A007317} \underline{A033543}  -
α = 3 \underline{A126931} \underline{A059738} \underline{A001700} \underline{A002212} \underline{A064613}  -
α = 4  -  -  \underline{A049027} \underline{A026378} \underline{A005572} \underline{A104455}
α = 5  -  -  \underline{A076025}  -  \underline{A005573} \underline{A182401}

Table 4: An expansion of Table 1, showing integer sequences corresponding to the (α, β)-colored Motzkin numbers M_{n,0}^{1}(α, β) of order ℓ = 1, for various choices of (α, β).

β = 0 β = 1 β = 2 β = 3 β = 4 β = 5
α = 0 \underline{A001405} \underline{A002426} \underline{A026641} \underline{A126952}  -  -
α = 1 \underline{A000079} \underline{A005773} \underline{A000984} \underline{A126568} \underline{A227081}  -
α = 2 \underline{A127358} \underline{A000244} \underline{A001700} \underline{A026375} \underline{A133158}  -
α = 3 \underline{A127359} \underline{A126932} \underline{A000302} \underline{A026378} \underline{A081671}  -
α = 4 \underline{A127360}  -  \underline{A141223}  -  \underline{A005573} \underline{A098409}
α = 5  -  -  -  -  \underline{A000400} \underline{A122898}

Table 5: Integer sequences (r_{n}(α, β))_{n≥0} corresponding to row sums r_{n} = ∑_{i=0}^{n} M_{n,m}^{1}(α, β) of the (α, β)-Motzkin triangle of order ℓ = 1, for various choices of (α, β). By Theorem 2.5, the (i, i) entries of this table equal the (i + 1, i) entries of Table 4.

\begin{aligned}& β⃗ = (0, 0) & β⃗ = (1, 0) & β⃗ = (2, 0) \\ α⃗ = (0, 0) & - & - & - \\ α⃗ = (1, 0) & \underline{A076227} & \underline{A071879} & - \\ α⃗ = (2, 0) & - & - & - \end{aligned} \begin{aligned}& β⃗ = (0, 1) & β⃗ = (1, 1) & β⃗ = (2, 1) \\ α⃗ = (0, 1) & \underline{A001005} & - & \underline{A303730} \\ α⃗ = (1, 1) & - & \underline{A036765} & \underline{A049128} \\ α⃗ = (2, 1) & - & \underline{A159772} & - \end{aligned}

Table 6: Integer sequences corresponding to the (α⃗, β⃗)-colored Motzkin numbers M_{n,0}^{2}(α⃗, β⃗) of order ℓ = 2, for various choices of α⃗ = (α_{0}, α_{1}), β⃗ = (β_{0}, β_{1}) with α_{0} = β_{0} = 0 (left) and α_{1} = β_{1} = 1 (right).

α_{1} = 0 α_{1} = 1 α_{1} = 2 α_{1} = 3 α_{1} = 4
α_{0} = 0  -  \underline{A089354} \underline{A023053}  -  -
α_{0} = 1  -  -  \underline{A001764} \underline{A121545}  -
α_{0} = 2  -  -  \underline{A098746} \underline{A006013}  -
α_{0} = 3  -  -  -  \underline{A001764}*  -
α_{0} = 4  -  -  -  \underline{A047099}  -

Table 7: Integer sequences corresponding to the (α⃗, β⃗)-colored Motzkin numbers M_{n,0}^{2}(α⃗, β⃗) of order ℓ = 2, for various choices of α⃗ = (α_{0}, α_{1}) when β⃗ = (3, 3). When ℓ = 2, observe that these cover all choices of (α⃗, β⃗) relevant to Subsections 3.1 and 3.2.