Colored Motzkin Paths of Higher Order

Abstract

Motzkin paths of order-$\ell$ 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\le \ell$. We further generalize order-$\ell$ Motzkin paths by allowing for various coloring schemes on the edges of our paths. These $(\vec{\alpha },\vec{\beta })$-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 $(\vec{\alpha },\vec{\beta })$-colored Motzkin paths and a variety of well-studied combinatorial objects. Specific coloring schemes $(\vec{\alpha },\vec{\beta })$ allow us to place $(\vec{\alpha },\vec{\beta })$-colored Motzkin paths in bijection with different subclasses 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 $(\vec{\alpha },\vec{\beta })$-colored Motzkin paths and certain subclasses of $k$-ary trees.

References in corpus (2)

• Bijections for Dyck paths with all peak heights of the same parity
• Generalized Path Pairs and Fuss-Catalan Triangles