Jean-Baptiste Priez (LRI, Paris-Sud)

La combinatoire énumérative a pour but de compter le nombre de configurations d’une structure combinatoire donnée. Dans cette théorie, l’outil algébrique principal est la notion de série génératrice. Cette méthodologie a été utilisée avec succès par P. Flajolet & al. pour le calcul automatique de complexité de certains algorithmes.

Le principal défaut de cette méthode est que l’information encodée dans l’exposant d’un monôme est très pauvre : c’est un nombre entier qui encode une notion de taille. En conséquence, les séries génératrices usuelles sont adaptées pour manipuler les récurrences sur les entiers mais peu pour manipuler des inductions structurelles.

La théorie des algèbres de Hopf combinatoires cherche à généraliser les séries génératrices pour résoudre le problème plus général des inductions structurelles.

Dans cet exposé, nous présenterons des algèbres de Hopf liées à des monoïdes de types plaxique. In fine, nous nous intéresserons à celles-ci pour l’étude d’algorithme de type Robinson-Schensted. En 2003, Hivert, Novelli et Thibon ont mis en avant un lien entre algèbres de Hopf et algorithmes d’insertion. Ils ont montré que les opérations de l’algèbre des arbres binaires de Loday- Ronco répondent à des questions naturelles sur l’algorithme d’insertion d’un mot dans un arbres binaire de recherche (ABR).

Nous nous intéresserons, dans cet exposé, à une algèbre de Hopf d’arbres binaires à multiplicité (PBTm) et à un algorithme d’insertion analogue à celui des ABR. Nous donnerons une formule des équerres associée à ces objets et à cet algorithme, et enfin nous montrerons cette formule en utilisant l’algèbre de Hopf PBTm.