Séminaire du 7 avril 03, Mireille Bousquet-Mélou

Sur quelques arbres de génération à deux étiquettes

Les arbres de génération à deux étiquettes décrivent la croissance de structures combinatoires dont le nombre de descendants dépend de deux paramètres.

Plutôt que cette définition obscure, on peut proposer un certain nombre d'exemples : marches dans un quart de plan (les deux paramètres étant les coordonnées des points d'arrivée), permutations évitant certains motifs, tableaux de Young de hauteur bornée, etc.

Les séries génératrices de ces structures sont régies par des équations fonctionnelles linéaires où deux variables, dites catalytiques, font l'objet de substitutions par des constantes. Les équations linéaires à une variable catalytique sont résolubles par la méthode du noyau. Leur solution est toujours algébrique.

On présentera quelques exemples récents de solutions d'équations linéaires ˆ deux variables catalytiques. Les solutions apparaissent en général comme diagonales de séries algébriques (et donc comme des séries holonomes).