Generating 2-Gray codes for grand Motzkin paths and grand Dyck paths with air pockets in constant amortized time
This work provides the first Gray code generation for these specific combinatorial objects, addressing a gap in the literature for enumeration and generation of such paths.
The authors present the first known 2-Gray codes for grand Motzkin paths with air pockets and, by setting horizontal steps to zero, for grand Dyck paths with air pockets. Their algorithm generates each path in constant amortized time per string using O(n^2) memory.
A grand Motzkin path with air pockets is a non-empty lattice path in the first and fourth quadrant of $\mathbb{Z}^2$, starting at the origin $(0,0)$, ending on the $x$-axis, and consisting of up-steps $(1, 1)$, horizontal steps $(1, 0)$, down-steps $(1, -k)$ where $k \geq 1$, and with no consecutive down-steps. A {grand Dyck path with air pockets} is a grand Motzkin path with air pockets that uses no horizontal steps. We present the first known 2-Gray codes for grand Motzkin paths with air pockets. Setting the number of horizontal steps to zero in our algorithm yields the first known 2-Gray codes for grand Dyck paths with air pockets. Our three-stage algorithm generates each path in constant amortized time per string, using $O(n^2)$ memory. We also provide enumeration formulae for grand Motzkin paths and grand Dyck paths with air pockets.