Generating 2-Gray codes for grand Motzkin paths and grand Dyck paths with air pockets in constant amortized time

Le résumé fourni par la source

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.

Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.