LogoGDRIM_100px.png

Journées Nationales 2018
du GDR Informatique Mathématique

Du 3 au 6 avril 2018
École polytechnique, Palaiseau, France

Bijections par automates pour quelques modèles de marches combinatoires sur le réseau carré
Frédéric Chyzack  1  
1 : INRIA, équipe Specfun
-

Remplace un exposé initialement annoncé par Assia Mahboubi.

Dans le réseau Z^2, on s'intéresse aux marches de longueur n partant de l'origine et qui empruntent les pas Nord, Ouest et Sud-Est. On considère d'une part les marches confinées au plan des ordonnées positives et terminant sur l'axe des abscisses, et d'autre part les marches confinées aux quart de plan des abscisses et ordonnées positives. Pour tout n, il y a autant de marches de chaque nature. Il y a plusieurs façons d'établir ce résultat : une première approche consiste à expliciter le cardinal, identique,
de ces deux classes ; une deuxième à identifier leur série génératrice, identique ; enfin, on exhibe classiquement une bijection tout à fait explicite entre les deux classes de marches. Dans cet exposé, on met en place un nouveau calcul de la bijection par le biais d'un automate réalisant une transduction. Le résultat se généralise dans diverses directions qui intéressent la combinatoire :
la bijection obtenue se raffine en préservant des paramètres sur la position finale des marches ; une bijection analogue existe entre des modèles à 6 pas ; une autre bijection permet de considérer des modèles à pas plus longs.

(Exposé sur la base de travaux en cours avec A.~Bostan, A.~Mahboubi et K.~Yeats.)


Personnes connectées : 1