100, rue des maths 38610 Gières / GPS : 45.193055, 5.772076 / Directeur : Thierry Gallay

Les séries rationnelles et algébriques en combinatoire énumérative

Jeudi, 6 Mars, 2008 - 17:30
Prénom de l'orateur: 
Mireille
Nom de l'orateur: 
BOUSQUET-MÉLOU
Résumé: 
Soit $A$ une classe d'objets munis d'une taille entière, telle que pour tout $n$ le nombre $a(n)$ d'objets de taille $n$ est fini. On s'intéresse aux cas où la série génératrice associée, $A(t) = \sum_n a(n) t^n$, est rationnelle, ou plus généralement algébrique. Ces propriétés présentent un intérêt pratique, car on sait alors dire beaucoup de choses sur les nombres $a(n)$ mais aussi un intérêt plus spécifiquement combinatoire : la nature rationnelle ou algébrique de la série suggère que les objets possèdent une structure (peut-être bien cachée) semblable, en gros, à la structure linéaire des mots dans le cas rationnel, et à la structure branchante des arbres dans le cas algébrique. On expliquera et discutera cette intuition combinatoire, en l'illustrant par des exemples. L'impression finale devrait être que, si cette intuition paraît satisfaisante dans le cas rationnel, elle est probablement incomplète dans le cas algébrique. Au travers de l'exposé, on apportera quelques réponses à la question (essentielle) suivante : et au fait, comment prouve-t-on qu'une série génératrice est rationnelle, ou algébrique?
Institution: 
LaBRI (Bordeaux)
Salle: 
04
logo uga logo cnrs