Journal of Integer Sequences, Vol. 24 (2021), Article 21.4.6

Colored Motzkin Paths of Higher Order

Isaac DeJager
LeTourneau University
Longview, TX 75602

Madeleine Naquin
Spring Hill College
Mobile, AL 36608

Frank Seidl
University of Michigan
Ann Arbor, MI 48109

Paul Drube
Valparaiso University
Valparaiso, IN 46383


Motzkin paths of order $\ell$ are a generalization of Motzkin paths that use steps U=(1,1), L=(1,0), and Di=(1,-i) for every positive integer $i \leq \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 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 $(\vec{\alpha},\vec{\beta})$-colored Motzkin paths and certain sub-classes of k-ary trees.

Full version:  pdf,    dvi,    ps,    latex    

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

Received January 4 2021; revised versions received March 4 2021; April 6 2021. Published in Journal of Integer Sequences, April 16 2021.

Return to Journal of Integer Sequences home page