Colored Motzkin Paths of Higher Order
Abstract
Motzkin paths are integer lattice paths that use the steps U = (1,1), L = (1,0), and D = (1,−1) and stay weakly above the line y = 0. We generalize Motzkin paths to allow for down steps with multiple slopes and for various coloring schemes on the edges of the resulting paths. These colored, higher-order Motzkin paths provide a general setting where specific coloring schemes yield sets that are in bijection with many well-studied combinatorial objects. We develop bijections between various classes of colored, higher-order Motzkin paths and certain subclasses of `-ary paths, including a generalization of Fine paths, as well as certain subclasses of `-ary trees. All of this utilizes the language of proper Riordan arrays, and we also include a series of results about the Riordan arrays whose entries enumerate sets of generalized Motzkin paths.
