Bijections between walks inside a triangular domain and Motzkin paths of bounded amplitude (Q2662347)

Summary: This paper solves an open question of \textit{P. R. G. Mortimer} and \textit{T. Prellberg} [ibid. 22, No. 1, Research Paper P1.64, 15 p. (2015; Zbl 1308.05010)] asking for an explicit bijection between two families of walks. The first family is formed by what we name triangular walks, which are two-dimensional walks moving in six directions (\(0^\circ\), \(60^\circ\), \(120^\circ\), \(180^\circ\), \(240^\circ\), \(300^\circ\)) and confined within a triangle. The other family is comprised of two-colored Motzkin paths with bounded height, in which the horizontal steps may be forbidden at maximal height. We provide several new bijections. The first one is derived from a simple inductive proof, taking advantage of a \(2^n\)-to-one function from generic triangular walks to triangular walks only using directions \(0^\circ\), \(120^\circ\), \(240^\circ\). The second is based on an extension of Mortimer and Prellberg's results to triangular walks starting not only at a corner of the triangle, but at any point inside it. It has a linear-time complexity and is in fact adjustable: by changing some set of parameters called a scaffolding, we obtain a wide range of different bijections. Finally, we extend our results to higher dimensions. In particular, by adapting the previous proofs, we discover an unexpected bijection between three-dimensional walks in a pyramid and two-dimensional simple walks confined in a bounded domain shaped like a waffle.