{"ID":3084705,"CreatedAt":"2026-06-05T06:46:15.197025399Z","UpdatedAt":"2026-06-06T21:45:49.600566077Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.05470","arxiv_id":"2606.05470","title":"Generating 2-Gray codes for grand Motzkin paths and grand Dyck paths with air pockets in constant amortized time","abstract":"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.","short_abstract":"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 {gran...","url_abs":"https://arxiv.org/abs/2606.05470","url_pdf":"https://arxiv.org/pdf/2606.05470v1","authors":"[\"Lei Dong\",\"Bowie Liu\",\"Dennis Wong\",\"Lin Chen\",\"Chan-Tong Lam\",\"Sio-Kei Im\"]","published":"2026-06-03T21:49:08Z","proceeding":"math.CO","tasks":"[\"math.CO\",\"cs.DS\"]","methods":"[]","has_code":false}