Bijections between walks inside a triangular domain and Motzkin paths of bounded amplitude - Normandie Université Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2020

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

Bijections entre des marches dans un domaine triangulaire et des chemins de Motzkin d'amplitude bornée

Résumé

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 2^n-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.
Ce papier résout une question ouverte de Mortimer et Prellberg demandant une bijection explicite entre deux familles de marches. La première famille est formée par ce qu'on appelle des marches triangulaires, qui sont des chemins bidimensionnels mouvant selon 6 directions (0°, 60°, 120°, 180°, 240°, 300°) et confinés dans un triangle. L'autre famille est composée de chemins de Motzkin bicoloriés et de hauteur bornée, dans lesquels les pas horizontaux peuvent être interdits à hauteur maximale. Nous fournissons plusieurs bijections. La première provient d'une simple preuve récursive, tirant parti d'une fonction "2^n-to-one" des marches triangulaires génériques à des marches triangulaires n'utilisant que les directions 0°, 120°, 240°. La seconde bijection se base sur une extension d'un résultat de Mortimer et Prellberg sur les marches triangulaires commençant non seulement à partir d'un coin du triangle, mais également à partir de n'importe quel point à son intérieur. Elle a une complexité temporelle linéaire et est en réalité paramétrisable : en changeant un jeu de métadonnées qu'on appelle "échaffaudage", nous obtenons une grande variété de bijections différentes. Enfin, nous étendons nos résultats aux dimensions supérieures. En particulier, en adaptant les preuves précédentes, nous découvrons une bijection inattendue entre les marches tridimensionelles dans une pyramides et les marches bidimensionnelles simples confinés dans un domaine ressemblant à une demi-gaufre.
Fichier principal
Vignette du fichier
Redaction.pdf (1.47 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02901546 , version 1 (17-07-2020)

Identifiants

  • HAL Id : hal-02901546 , version 1

Citer

Julien Courtiel, Andrew Elvey Price, Irène Marcovici. Bijections between walks inside a triangular domain and Motzkin paths of bounded amplitude. 2020. ⟨hal-02901546⟩
116 Consultations
84 Téléchargements

Partager

Gmail Facebook X LinkedIn More