Vertically constrained Motzkin-like paths inspired by bobbin lace

Veronika Irvine¹ ; Stephen Melczer² ; Frank Ruskey³

¹Cheriton School of Computer Science University of Waterloo
²Department of Mathematics University of Pennsylvania
³Department of Computer Science University of Victoria

The electronic journal of combinatorics, Tome 26 (2019) no. 2

Résumé

Inspired by a new mathematical model for bobbin lace, this paper considers finite lattice paths formed from the set of step vectors $\mathfrak{A}=$$\{\rightarrow,$ $\nearrow,$ $\searrow,$ $\uparrow,$ $\downarrow\}$ with the restriction that vertical steps $(\uparrow, \downarrow)$ cannot be consecutive. The set $\mathfrak{A}$ is the union of the well known Motzkin step vectors $\mathfrak{M}=$$\{\rightarrow,$ $\nearrow,$ $\searrow\}$ with the vertical steps $\{\uparrow, \downarrow\}$. An explicit bijection $\phi$ between the exhaustive set of vertically constrained paths formed from $\mathfrak{A}$ and a bisection of the paths generated by $\mathfrak{M}S$ is presented. In a similar manner, paths with the step vectors $\mathfrak{B}=$$\{\nearrow,$ $\searrow,$ $\uparrow,$ $\downarrow\}$, the union of Dyck step vectors and constrained vertical steps, are examined. We show, using the same $\phi$ mapping, that there is a bijection between vertically constrained $\mathfrak{B}$ paths and the subset of Motzkin paths avoiding horizontal steps at even indices. Generating functions are derived to enumerate these vertically constrained, partially directed paths when restricted to the half and quarter-plane. Finally, we extend Schröder and Delannoy step sets in a similar manner and find a bijection between these paths and a subset of Schröder paths that are smooth (do not change direction) at a regular horizontal interval.

Détail

DOI : 10.37236/7799

Classification : 05C38, 05C30