Espèce (combinatoire)

En mathématiques, et plus précisément en combinatoire, la théorie des espèces est une méthode abstraite et systématique permettant de calculer les séries génératrices de structures discrètes. Elle permet non seulement de dénombrer ces structures, mais aussi de donner des preuves bijectives des résultats obtenus. Parmi les exemples typiques d'espèces figurent les graphes (finis), les permutations, les arbres, etc. À chaque espèce est associée une série génératrice qui compte le nombre de structures de cardinal donné. L'un des objectifs de la théorie des espèces est de pouvoir analyser des structures complexes en les décrivant en termes de transformations et de combinaisons de structures plus simples. À chaque opération sur les espèce correspond une manipulation sur les séries génératrices. C'est pourquoi cette théorie facilite l'étude des séries génératrices des structures complexes. Cette théorie a été introduite, développée et appliquée par des chercheurs canadiens autour d'André Joyal à partir d'un article de 1981^[1].

La puissance de cette théorie est due à son haut niveau d'abstraction. Le « format de description » d'une structure (par exemple, liste d'adjacence ou matrice d'adjacence pour les graphes) ne compte pas car les espèces sont purement algébriques. La théorie des catégories fournit un langage efficace pour introduire la notion d'espèce mais il n'est pas nécessaire de comprendre les catégories pour travailler avec les espèces.

La catégorie des espèces est équivalente à la catégorie des suites symétriques ou S-objets dans les ensembles finis^[2].

Une espèce est constituée de structures combinatoires individuelles construites à partir des éléments d'un ensemble fini. Par exemple, un graphe est une structure d'arêtes reliant certains éléments d'un ensemble donné de sommets, et l'espèce des graphes comprend tous les graphes définis sur tous les ensembles finis. Par ailleurs, l'ensemble sous-jacent d'un membre d'une espèce peut être ré-étiqueté par les éléments de n'importe quel autre ensemble de même cardinal ; par exemple, ré-étiqueter les sommets d'un graphe donne « la même structure de graphe » sur les nouveaux sommets, c'est-à-dire un graphe isomorphe au premier.

Cela conduit à la définition formelle d'une espèce combinatoire. Soit ${\displaystyle {\mathcal {B}}}$ la catégorie dont les objets sont les ensembles finis et les morphismes les bijections entre ces ensembles. Une espèce combinatoire, ou simplement une espèce, est un foncteur^[3]

${\displaystyle F\,:\,{\mathcal {B}}\longrightarrow {\mathcal {B}}.}$

Pour tout ensemble fini A dans ${\displaystyle {\mathcal {B}}}$, l'ensemble fini ${\displaystyle F[A]}$^{[note 1]} est appelé l'ensemble des F-structures sur A, ou l'ensemble des structures d'espèce F sur A. De plus, par définition d'un foncteur, si φ est une bijection entre les ensembles A et B, alors ${\displaystyle F[\varphi ]}$ est une bijection entre les ensembles de F-structures ${\displaystyle F[A]}$ et ${\displaystyle F[B]}$, appelée transport de F-structure le long de φ.

Par exemple, l'espèce de permutations^[4] associe à chaque ensemble fini A l'ensemble ${\displaystyle S[A]}$ de toutes les permutations de A (toutes les manières d'ordonner A dans une liste), et chaque bijection f de A vers un autre ensemble B induit naturellement une bijection (un réétiquetage) qui associe à chaque permutation g de A une permutation correspondante de B, à savoir la bijection ${\displaystyle S[f]:S[A]\to S[B]}$, ${\displaystyle g\mapsto f\circ g\circ f^{-1}}$. De même, on peut définir l'espèce des partitions en associant à chaque ensemble fini l'ensemble de toutes ses partitions, et l'espèce des ensembles de parties en associant à chaque ensemble fini l'ensemble de ses parties. Le diagramme ci-dessus illustre une structure (représentée par un point rouge) construite à partir de cinq éléments distincts (représentés par des points bleus) ; une structure équivalente pourrait être construite à partir de cinq objets quelconques.

Deux ensembles finis sont en bijection lorsqu'ils ont le même cardinal (nombre d'éléments). On voit que par définition, les ensembles correspondants de structures d'un espèce donnée sont également en bijection, de sorte que le cardinal (fini) de ${\displaystyle F[A]}$ ne dépend que du cardinal de A^{[note 2]}. En particulier, on peut introduire la série génératrice exponentielle ${\displaystyle F(x)}$ d'une espèce F^[5] :

${\displaystyle F(x)=\sum _{n\geq 0}\operatorname {card} F[n]{\frac {x^{n}}{n!}}}$,

où ${\displaystyle \operatorname {card} F[n]}$ est le cardinal de ${\displaystyle F[A]}$ pour n'importe quel ensemble A à n, par exemple, ${\displaystyle A=\{1,2,\dots ,n\}}$.

Quelques exemples – on note dans chaque cas ${\displaystyle f_{n}=\operatorname {card} F[n]}$ :

• l'espèce des ensembles, traditionnellement notée E est le foncteur qui à A associe ${\displaystyle \{A\}}$ ; on a ${\displaystyle f_{n}=1}$ pour tout n donc ${\displaystyle E(x)=e^{x}}$ ;
• l'espèce S de permutations, décrite ci-dessus ; on a ${\displaystyle f_{n}=n!}$ pour tout n donc ${\displaystyle S(x)=1/(1-x)}$ ;
• l'espèce T₂ des couples est le foncteur qui à un ensemble A associe l'ensemble A² ; on a ${\displaystyle f_{n}=n^{2}}$ pour tout n et ${\displaystyle T_{2}(x)=x(x+1)e^{x}}$.

Les opérations algébriques sur les fonctions génératrices correspondent à certaines opérations « naturelles » sur les espèces. Les opérations de base sont l'addition, la multiplication, la composition et la différentiation. Il est également nécessaire de définir l'égalité sur les espèces. En théorie des catégories, on dispose déjà d'un moyen de décrire l'équivalence de deux foncteurs : la notion d'isomorphisme naturel. Dans ce contexte, cela signifie simplement que pour chaque A, il existe une bijection entre les F-structures sur A et les G-structures sur A, qui « se comporte bien » vis à vis du transport. Il existe des espèces qui ont la même fonction génératrice exponentielle (on dit qu'elles sont équipotentes) mais qui ne sont pas isomorphes (par exemple, l'espèce S des permutations et l'espèce L des ordres linéaires). En revanche, deux espèces isomorphes ont toujours la même fonction génératrice.

La somme de deux espèces est définie par la réunion disjointe des ensembles et correspond à un choix entre structures^[6]. Étant donné deux espèces F et G, on définit ${\displaystyle (F+G)[A]}$ comme la réunion disjointe (également notée « + ») de ${\displaystyle F[A]}$ et ${\displaystyle G[A]}$. On en déduit immédiatement que ${\displaystyle (F+G)(x)=F(x)+G(x)}$. À titre d'exemple, soit ${\displaystyle E^{+}}$ l'espèce des ensembles non vides (${\displaystyle E[A]=\{A\}}$ si A n'est pas vide, ${\displaystyle E[\emptyset ]=\emptyset }$), dont la fonction génératrice est ${\displaystyle E(x)=\exp(x)-1}$, et soit 1 l'espèce de l'ensemble vide (${\displaystyle E[\emptyset ]=\{\emptyset \}}$ et ${\displaystyle E[A]=\emptyset }$ si A n'est pas vide), dont la fonction génératrice est ${\displaystyle \mathbf {1} (x)=1}$. La somme de ces deux espèces est l'espèce des ensembles ${\displaystyle E=\mathbf {1} +E^{+}}$. Cela traduit le fait qu'un ensemble (fini) est soit vide, soit non vide. Des égalités de ce type peuvent être interprétées comme se référant à une structure donnée, ou bien à la collection de toutes les structures.

Le produit de deux espèces est légèrement plus compliqué. On pourrait se contenter de le définir comme le produit cartésien des ensembles mais l'interprétation combinatoire qui en découle n'est pas pertinente. (Ce type de produit apparaîtra néanmoins plus bas.) Plutôt que de combiner deux structures indépendantes sur un même ensemble, le produit utilise part de l'idée de scinder l'ensemble en deux parties et de mettre une F-structure sur l'une et une G-structure sur l'autre^[7]. Cela donne, pour tout ensemble fini A,

${\displaystyle (F\cdot G)[A]=\sum _{A=B+C}F[B]\times G[C].}$

Il s'agit d'une réunion disjointe sur toutes les partitions possibles de A en deux parts. Il est facile de montrer que le produit est associatif et commutatif (à isomorphisme près) et qu'il est distributif par rapport à la somme. Quant à la série génératrice, ${\displaystyle (F\cdot G)(x)=F(x)G(x)}$.

Le diagramme ci-dessous illustre une ${\displaystyle (F\cdot G)}$structure possible sur un ensemble A à cinq éléments. La F-structure (en rouge) prend trois éléments de l'ensemble de base et la G-structure (en bleu clair) prend les deux autres. D'autres ${\displaystyle (F\cdot G)}$-structures appliquent F et G à d'autre partitions de A. L'ensemble ${\displaystyle (F\cdot G)[A]}$ est la réunion disjointe de toutes ces structures.

La somme et le produit des espèces sont la plus vaste interprétation des principe de dénombrement dits « de somme » et « de produit »^{[réf. nécessaire]}.

La composition, aussi appelée substitution, est encore plus complexe. L'idée de base est de remplacer les composants de F par des G-structures pour former ${\displaystyle (F\circ G)}$^[8]. Comme pour le produit, on commence par faire une partition de l'ensemble A ; on applique G à chaque part de la partition puis on applique F aux images des parts pour construire la F-structure reliant les G-structures. Pour que la composition ait un sens, il faut supposer que l'image par G de l'ensemble vide est l'ensemble vide^{[note 3]}. La définition formelle est :

${\displaystyle (F\circ G)[A]=\sum _{\pi \in P[A]}(F[\pi ]\times \prod _{B\in \pi }G[B]).}$

Ici, P désigne l'espèce des partitions, c'est-à-dire que ${\displaystyle P[A]}$ est l'ensemble de toutes les partitions de A. Cette définition indique qu'un élément de ${\displaystyle (F\circ G)[A]}$ est constitué d'une F-structure sur une partition de A et d'une G-structure sur chaque part de la partition. La série génératrice s'obtient par substitution : ${\displaystyle (F\circ G)(x)=F(G(x))}$.

Un exemple de l'une de ces structures est illustré ci-dessous. Trois G-structures (bleu clair) se partagent l'ensemble de base à cinq éléments ; puis, une F-structure (rouge) est construite pour relier les G-structures.

Le produit et la composition peuvent être illustrées par l'exemple des arbres. Au préalable, on définit X comme l'espèce « singleton », qui envoie un ensemble A sur A si c'est un singleton et ${\displaystyle X[A]=\emptyset }$ sinon ; sa série génératrice est ${\displaystyle X(x)=x}$. Alors, l'espèce ${\displaystyle \operatorname {Ar} }$ des arbres enracinés est définie récursivement par l'égalité ${\displaystyle \operatorname {Ar} =X\cdot (E\circ \operatorname {Ar} )}$. Cette équation exprime qu'un arbre enraciné est composé d'une racine (unique) à laquelle sont rattachés un ensemble de (sous-)arbres. La récursion ne nécessite pas d'initialisation explicite : elle n'engendre des arbres que lorsqu'elle est appliquée à un ensemble fini. On peut se représenter cela comme l'application itérative du foncteur ${\displaystyle \operatorname {Ar} }$ à une « réserve » d'éléments de cet ensemble : à chaque itération, un élément est pris par X et les autres sont distribués par E entre les sous-arbres de ${\displaystyle \operatorname {Ar} }$, jusqu'à ce qu'il n'y ait plus d'éléments à fournir à E. Ceci montre que les descriptions algébriques des espèces diffèrent sensiblement des spécifications de types dans les langages de programmation comme Haskell.

De façon analogue, l'espèce P des partitions peut être caractérisée comme ${\displaystyle P=E\circ E^{+}}$: cette égalité s'interprète en disant qu'une partition est un ensemble d'ensembles non vides deux à deux disjoints (utilisant tous les éléments de l'ensemble de départ). Par composition des séries génératrices exponentielles, on obtient immédiatement que celle de P est ${\displaystyle P(x)=\mathrm {e} ^{\mathrm {e} ^{x}-1}}$, qui est la série génératrice des nombres de Bell.

La différenciation des espèces correspond intuitivement à la construction de « structures avec un trou », illustrée par la figure ci-dessous.

Formellement^[9], la dérivée F' d'une espèce F associe à chaque ensemble fini A :

${\displaystyle (F')[A]=F{\bigl [}A+\{\star \}{\bigr ]}}$,

où ${\displaystyle \star }$ est un nouvel élément distingué qui n'appartient pas à ${\displaystyle A}$ et + désigne la réunion disjointe.

Pour différencier la série exponentielle associée, la suite des coefficients doit être décalée d'un cran vers la gauche (en supprimant le premier terme). C'est ce qui motive la définition précédente.

Quand on avance dans la théorie des espèces, on utilise abondamment la différentiation pour mettre en place et résoudre des équations différentielles sur les espèces et les séries associées. En effet, l'idée d'ajouter (ou de supprimer) un élément ou une partie d'une structure est puissante : elle permet d'établir des relations entre des espèces apparemment sans lien.

Par exemple, considérons l'espèce L des ordres linéaires — les listes des éléments de l'ensemble de base (ordonnées, sans répétition ni omission). Supprimer un élément d'une liste la divise en deux parties (éventuellement vides) ; en symboles, cela s'écrit ${\displaystyle L'=L\cdot L}$. Comme le nombre de listes possibles pour un ensemble de cardinal n est ${\displaystyle n!}$, la série génératrice exponentielle de L est ${\displaystyle L(x)=1/(1-x)}$et on a bien :

${\displaystyle {\frac {\mathrm {d} }{\mathrm {d} x}}{(1-x)}^{-1}={(1-x)}^{-2}}$.

Cette idée et ces formules de différenciation généralisées figurent déjà dans un article de N. G. de Bruijn de 1964.

L'espèce C des permutations cycliques associe à un ensemble A l'ensemble de tous les cycles sur A. En retirant un élément à un cycle, on obtient une liste, ce qui donne ${\displaystyle C'=L}$. On peut intégrer la série génératrice de L pour obtenir celle de C :

${\displaystyle C(x)=1+\int _{0}^{x}{\frac {\mathrm {d} t}{1-t}}=1+\log {\frac {1}{1-x}}}$.

Un joli exemple d'intégration d'une espèce est la complétion d'une droite (munie d'un système de coordonnées paramétré par un corps) par un point à l'infini, pour obtenir une droite projective.

On peut effectuer diverses autres opérations sur les espèces. Elles deviennent nécessaires pour décrire des structures plus complexes, telles que les graphes orientés ou les bigraphes (en).

Le pointage consiste à sélectionner un élément dans une structure^[10]. Étant donné une espèce F, l'espèce pointée correspondante F^• est définie par ${\displaystyle F^{\bullet }[A]=A\times F[A]}$. Ainsi, chaque F^•-structure est une F-structure dont un élément est distingué. Le pointage est lié à différentiation décrite ci-dessus par la relation ${\displaystyle F^{\bullet }=X\cdot F'}$, ce qui entraîne que ${\displaystyle F^{\bullet }(x)=xF'(x)}$. L'espèce E^• des ensembles pointés est particulièrement importante comme brique de base pour de nombreuses constructions plus complexes.

Le produit cartésien ${\displaystyle F\times G}$ de deux espèces F et G permet de construire deux structures en même temps sur le même ensemble. Elle diffère du produit ordinaire ${\displaystyle F\cdot G}$ parce que tous les éléments de l'ensemble de base sont partagés entre les deux structures. Une ${\displaystyle F\times G}$-structure peut être vue comme la superposition d'une F-structure et d'une G-structure.

Par exemple, les bigraphes peuvent être décrits comme la superposition d'un graphe et d'un ensemble d'arbres : chaque nœud du bigraphe appartient à la fois à un graphe et à un arbre qui décrit l'imbrication des nœuds. La fonction génératrice ${\displaystyle (F\times G)(x)}$ est le produit d'Hadamard (ou produit terme à terme) de ${\displaystyle F(x)}$ et ${\displaystyle G(x)}$.

L'espèce ${\displaystyle E^{\bullet }\times E^{\bullet }}$ peut être interprétée comme consistant à faire deux choix indépendants d'un élément de l'ensemble de base. Les deux points peuvent coïncider, alors que dans ${\displaystyle X\cdot X\cdot E}$, ils sont nécessairement différents.

En tant que foncteurs, deux espèces F et G peuvent être combinées par la composition des foncteurs : ${\displaystyle (F\,\Box \,G)[A]=F[G[A]]}$ (on utilise un symbole carré pour éviter le cercle, qui est déjà employé pour la substitution). Ceci construit une F-structure sur l'ensemble de toutes les G-structures sur l'ensemble A. Par exemple, si F est le foncteur qui associe à un ensemble l'ensemble de ses parties, une structure de l'espèce composée est un sous-ensemble des G-structures sur A. Si par exemple G est l'espèce ${\displaystyle E^{\bullet }\times E^{\bullet }}$ définie ci-dessus, on obtient l'espèce des graphes orientés, avec boucles autorisées. (Un graphe orienté est déterminé par un ensemble d'arêtes, et les arêtes sont des couples de sommets : un graphe est donc un sous-ensemble de l'ensemble des couples d'éléments de l'ensemble des sommets A.) D'autres familles de graphes, ainsi que de nombreuses autres structures, peuvent être définies de façon analogue.

Les opérations sur les espèces sont implémentées sur SageMath^[11] et, sous forme d'un paquetage dédié, également sur Haskell^[12],[13].

• Une espèce en k genres est un foncteur ${\displaystyle {\mathcal {B}}^{k}\rightarrow {\mathcal {B}}}$. Ici, les structures produites peuvent comporter des éléments provenant de différentes sources^[14].
• On peut considérer un foncteur vers ${\displaystyle {\mathcal {B}}_{R}}$, la catégorie des ensembles pondérés par un anneau R de séries formelles, ce que l'on appelle une espèce pondérée^[15].

Si l’on remplace la catégorie des ensembles finis munis de bijections par celle des espaces vectoriels de dimension finie munis des automorphismes linéaires, on obtient la notion de foncteur polynomial (en) (si on impose une certaine condition de finitude)^{[réf. nécessaire]}.

• André Joyal, « Une théorie combinatoire des séries formelles », Advances in Mathematics, vol. 42, n^o 1,‎ octobre 1981, p. 1-82 (DOI 10.1016/0001-8708(81)90052-9)
• Nicolaas Govert de Bruijn, « Pólya's theory of counting », dans E. F. Beckenbach (éd.), Applied combinatorical mathematics, John Wiley & Sons, 1964 (lire en ligne), p. 144-184
• Jacques Labelle, « Quelques espèces sur les ensembles de petite cardinalité », Annales des sciences mathématiques du Québec, vol. 9, n^o 1,‎ 1985, p. 31-58 (lire en ligne)
• Jacques Labelle et Y. N. Yeh, « The relation between Burnside rings and combinatorial species », Journal of Combinatorial Theory, a, vol. 50, n^o 2,‎ 1989, p. 269-284 (DOI 10.1016/0097-3165(89)90019-8 )
• Yves Chiricota, « Classification des espèces moléculaires de degré 6 et 7 », Annales des sciences mathématiques du Québec, vol. 17, n^o 1,‎ 1993, p. 11–37
• François Bergeron, Gilbert Labelle et Pierre Leroux, Théorie des espèces et combinatoire des structures arborescentes, Montréal, LaCIM, 1994, vi+394 p. (ISBN 2-89276-135-2). Traduction en anglais : Combinatorial Species and Tree-like Structures (trad. Margaret Readdy), Cambridge University Press, coll. « Encyclopedia of Mathematics and its Applications » (n^o 67), 2013 (1^re éd. 1998) (ISBN 9781107325913, DOI 10.1017/CBO9781107325913, lire en ligne)
• François Bergeron, Gilbert Labelle et Pierre Leroux, Introduction to the Theory of Species of Structures, Université du Québec à Montréal, 25 novembre 2013 (lire en ligne)
• Adalbert Kerber, Applied finite group actions, Berlin, New York, Springer-Verlag, coll. « Algorithms and Combinatorics » (n^o 19), 1999, 2^e éd. (ISBN 978-3-540-65941-9, OCLC 247593131, MR 1716962)

• Formule exponentielle
• Conteneur (théorie des types) (en)

• (en) Eric W. Weisstein, « Species », sur MathWorld
• Combinatorial species sur le nLab

• Portail des mathématiques