Espèces combinatoires

Ce n’est qu’à la suite d’un long processus que la notion moderne de fonction s’est dégagée. Cette définition, apparemment due à Dirichlet (1837), rend indépendante cette notion de toute méthode de description. Cette définition a, entre autres, ouvert la porte à l’introduction d’algèbres de fonctions et d’opérateurs.  C’est un processus tout à fait semblable qui a amené André Joyal (1981) à introduire en combinatoire la notion d’espèces, pour ainsi libérer la description de structures combinatoires d’un format spécifique. Cette théorie (voir ce texte pour une introduction en français) permet d’expliquer, de façon élégante, l’utilisation de calcul de séries génératrices pour l’énumération de structures. Cependant, ce qui en fait la véritable originalité est qu’elle permet de tenir compte de façon naturelle de l’action de groupes de permutations sur les structures considérées.

Au cours de dernières décennies, un progrès considérable a été fait dans le processus de clarifier et de renforcer les fondements de la combinatoire. Plusieurs théories ont émergé, permettant d’expliquer l’utilisation de techniques algébriques en combinatoire. Entre autres, on peut mentionner le travail de Rota sur l’inversion de Möbius et le calcul ombral, la théorie des ensembles ordonnés binomiaux de Stanley, ou encore les multiples applications combinatoires des algèbres de Hopf. Plusieurs auteurs, comme Goulden et Jackson, ou encore Wilf, ont clarifié l’importance de développer de bonnes méthodes générales pour résoudre des problèmes d’énumération. En particulier, Flajolet, Knuth et Schützenberger ont mis de l’avant des liens importants pour les fondements de l’informatique théorique. De plus, au cours de la même période, la combinatoire s’est enrichie de multiples interactions avec l’algèbre et la physique théorique.

La théorie des espèces de structures combinatoires se situe dans ce grand courant. D’une manière unifiée, elle permet autant de comprendre l’utilisation de séries génératrices pour l’énumération de structures étiquetées ou non, que l’élaboration d’outils d’analyse et de spécification de ces structures. Ainsi, elle transforme en équations fonctionnelles (ou différentielles) la spécification récursive de structures arborescentes. Englobant la description de structures avec la description de l’action de groupes de permutations sur ces structures, la théorie des espèces unifie le calcul de fonctions génératrices avec la théorie de Pólya. Formellement, tout ceci résulte du fait qu’une espèce est simplement un endofoncteur de la catégorie des ensembles finis avec bijections, et de ce qu’on a une structure algébrique sur ces foncteurs. Cependant, l’utilisation de notion catégorique est assez légère.

endo
Une preuve par l’image, dans le contexte des espèces

Explicitement, une espèce de structure $F$ consiste en la donnée de deux règles: une première qui associe à chaque ensemble fini $U$, un ensemble fini $F[U]$; et une seconde qui associe à chaque biijection $\sigma:U\rightarrow V$, une bijection $F[\sigma]:F[U]\rightarrow F{V}$. Les éléments de l’ensemble $F[U]$ sont les $F$-structures sur l’ensemble sous-jacent $U$. La condition de fonctorialité assure que $\sigma\mapsto F[\sigma]$ est compatible avec la composition de bijections. Ainsi, on insiste autant sur la description des structures que sur l’effet de permutations sur celles-ci.

Des opérations combinatoires naturelles permettent de construire de nouvelles espèces à partir d’espèces connues. En particulier, on a les opérations d’addition, de multiplication, de substitution, de dérivation, etc., qui reflètent les calculs avec des séries formelles. En fait, divers types de séries formelles peuvent être associées à chaque espèce selon le genre de problème d’énumération considéré (étiqueté, non-étiqueté, pondérées, etc.). La clé de l’utilisation de ces outils réside dans la « compatibilité » entre opérations sur les espèces et opérations sur les séries. Ainsi, chaque identité (algébrique, fonctionnelle or différentielle) entre espèces entraîne automatiquement des identités entre les séries associées. C’est là l’esprit de la méthode d’Euler. On n’apprécie vraiment la puissance de la théorie des espèces que lorsqu’on constate qu’un simple argument combinatoire montre une identité entre espèces, duquel découle alors automatiquement non seulement des identités combinatoires, mais aussi des formules à la Pólya (incluant des identités entre fonctions symétriques).

Pour en savoir plus, voir le livre