10h30: Énumération de chemins dans le quart de plan, Mireille Bousquet-Mélou, LaBRI, Bordeaux.

Travail en commun avec Marni Mishna, Simon Fraser University, Vancouver. Soit S un sous-ensemble de {-1,0,1}^2 ne contenant pas (0,0). On s'intéresse au comptage des chemins du plan à pas dans S, issus de l'origine et confinés au premier quadrant. En particulier, on voudrait connaître la nature de la série génératrice associée : est-elle rationnelle, algébrique, différentiellement finie ? A priori, on a 2^8 problèmes de ce type à étudier. Cependant, certains sont triviaux ; d'autres sont équivalents à un problème de chemin dans un demi-plan et peuvent donc être résolus par la « méthode du noyau », qui conduit systématiquement à des séries génératrices algébriques. On se concentre sur les cas restants, et montrons qu'il y a 79 problèmes inhéremment différents à étudier. Suivant les préceptes du petit livre jaune de Fayolle et al., on associe à chacun d'eux un groupe de transformations birationnelles, et montrons que celui-ci est fini (d'ordre au plus 8) dans 23 cas, infini sinon. On présente une façon unifiée de résoudre 22 des 23 problèmes associés à un groupe fini. Dans chaque cas, la série trouvée est D-finie. Bostan et al. ont récemment prouvé que la série associée au 23 ème problème, connu comme « les chemins de Gessel », est algébrique (donc D-finie). On conjecture que les séries associés à des groupes infinis ne sont pas D-finies. Notre approche retrouve des résultats connus, en raffine certains, et apporte aussi des résultats neufs. Par exemple, nous montrons que les chemins à pas N, E, W, S, SW et NE ont une série génératrice algébrique.