Geodesic
Bijections between walks inside a triangular domain and Motzkin paths of bounded amplitude
Julien Courtiel1 ; Andrew Elvey Price2 ; Irène Marcovici3
1Normandie University, UNICAEN, ENSICAEN, CNRS, GREYC
2Université de Tours, IDP
3Universitée de Lorraine, CNRS, Inria, IECL
The electronic journal of combinatorics, Tome 28 (2021) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

This paper solves an open question of Mortimer and Prellberg 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°, 60°, 120°, 180°, 240°, 300°) 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 2n-to-one function from generic triangular walks to triangular walks only using directions 0°, 120°, 240°. 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.
DOI : 10.37236/9724
Classification : 05A15, 05C38, 05E10, 05A19, 60G50
Mots-clés : Mortimer and Prellberg's problem, triangular walks

Julien Courtiel  1   ; Andrew Elvey Price  2   ; Irène Marcovici  3

1 Normandie University, UNICAEN, ENSICAEN, CNRS, GREYC
2 Université de Tours, IDP
3 Universitée de Lorraine, CNRS, Inria, IECL 
@article{10_37236_9724,
     author = {Julien Courtiel and Andrew Elvey Price and Ir\`ene Marcovici},
     title = {Bijections between walks inside a triangular domain and {Motzkin} paths of bounded amplitude},
     journal = {The electronic journal of combinatorics},
     year = {2021},
     volume = {28},
     number = {2},
     doi = {10.37236/9724},
     zbl = {1461.05009},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/9724/}
}
TY  - JOUR
AU  - Julien Courtiel
AU  - Andrew Elvey Price
AU  - Irène Marcovici
TI  - Bijections between walks inside a triangular domain and Motzkin paths of bounded amplitude
JO  - The electronic journal of combinatorics
PY  - 2021
VL  - 28
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/9724/
DO  - 10.37236/9724
ID  - 10_37236_9724
ER  - 
%0 Journal Article
%A Julien Courtiel
%A Andrew Elvey Price
%A Irène Marcovici
%T Bijections between walks inside a triangular domain and Motzkin paths of bounded amplitude
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/9724/
%R 10.37236/9724
%F 10_37236_9724
Julien Courtiel; Andrew Elvey Price; Irène Marcovici. Bijections between walks inside a triangular domain and Motzkin paths of bounded amplitude. The electronic journal of combinatorics, Tome 28 (2021) no. 2. doi: 10.37236/9724

Cité par Sources :