Motzkin Paths with Vertical Edges


Veronika Irvine and Frank Ruskey. Motzkin Paths with Vertical Edges. GasCOM 2014: Generation Aleatoire des Structures COMbinatoires.


This paper considers finite lattice paths formed from the set of step vectors {→, ↗, ↘, ↑ and ↓} with the restriction that vertical steps (↑, ↓) can not be consecutive. We provide a recurrence relation for enumerating paths that terminate a horizontal distance n and vertical distance m from the starting point and apply the relation to paths which are restricted to the first quadrant and paths which are not. We provide an explicit algorithmic bijection between these paths and a bisection of the Motzkin triangle paths. Finally, we extend Dyck paths in a similar manner and show that using the same mapping there is a bijection to a subset of Motzkin paths.


PDF Preprint (564KB)