Chemins tandems et chemins de Łukasiewicz : bijections et variations
Time: 11:00 -- Location: Salle Philippe Flajolet du LIX
Les chemins du quart de plan sur les pas O, N, SE (« chemins tandems ») et celles sur les pas O, NO, N, E, SE, S (« chemins tandems symétrisés ») sont connus pour avoir des séries génératrices algébriques lorsqu'ils sont énumérées par la longueur. Pour les premiers, D. Gouyou-Beauchamps a donné en 1989 une bijection en termes de chemins de Motzkin et de tableaux de Young. Pour les seconds, M. Bousquet-Mélou et M. Mishna ont en 2010 donné un calcul algébrique explicite de la série génératrice, par moyennisation d'une équation fonctionnelle vérifiée par la série. Ces dernières auteures ont de plus fait la remarque que la duplication symétrique des pas pour les chemins tandems symétrisés semble être reflétée d'une manière encore inexpliquée par un facteur 2^n dans leur dénombrement ; elles ont demandé une explication bijective du phénomène. Cet exposé donne des bijections pour approcher ces questions.
Dans un premier temps, nous montrerons comment des travaux de S.-P. Eu et de ses collaborateurs peuvent être revisités pour donner une bijection algorithmique directe du résultat de Gouyou-Beauchamps. Cette bijection et son inverse s'appuient sur des traversées uniques et unidirectionnelles de mots, en ne considérant qu'une information locale, alors que la méthode d'origine d'Eu requiert plusieurs itérations sur les mots, en considérant simultanément plusieurs lettres distantes. Cette présentation plus explicite de la bijection permet de plus de suivre des paramètres de position finale.
Ensuite, nous montrerons comment étendre la bijection précédente dans deux directions. D'une part, en allant au-delà des chemins de Motzkin par l'utilisation de grands pas positifs, nous obtenons une bijection entre les chemins p-Łukasiewicz du demi-plan supérieur, utilisant les pas (1, i) pour -1 <= i <= p, et les chemins p-tandems du quart de plan, utilisant le pas SE = (1, -1) et les pas (-i, p-i) pour 0 <= i <= p. D'autre part, en interférant habilement deux copies de la bijection pour les chemins tandems, nous obtenons une bijection entre chemins tandems symétrisés et une variété bicolorée de chemins de Motzkin.
De manière remarquable, des résultats bijectifs similaires apparaissent dans un travail en cours de M. Bousquet-Mélou, É. Fusy et K. Raschel, où les auteurs utilisent une bijection récente due à R. Kenyon, J. Miller, S. Sheffield et D. Wilson, entre chemins tandems généraux et orientations bipolaires marquées de cartes. Nos bijections sont pourtant différentes de celles à base de cartes, sans que les liens potentiels n'aient a ce jour été étudiés.
(Exposé sur deux travaux en cours avec A. Bostan, A. Mahboubi et K. Yeats.)