Décomposition arborescente de Mario Ouellette pour les espèces de structures

Pierre Bouchard* et Mario Ouellette

Yeong-Nan Yeh proved the semiring (with respect to sum and product) of (isomorphism classes of) species to be factorial, more precisely isomorphic to the semi-ring of formal power series ℕ[[M]] where M is the monoid (for ·) of isomorphism classes of molecular species ([Yeh]). This amounts to saying that each species is uniquely a sum of products of atomic species. Studying also the behavior of the composition of species, Mario Ouellette ([Oue]) showed that each species has a unique decomposition as a composition of a primitive species and a molecular species: this leads to a unique “arborescent” decomposition for species. In this talk, we give a detailed demonstration of the lemma which is at the heart of his proof and a sketch his proof.

1. Rappels sur les espèces de structures.

Définition 1.1 Une espèce de structures est une règle qui, à chaque ensemble fini U associe un autre ensemble fini G[U] et à chaque bijection β: U → V associe une autre bijection G[β]: G[U] → G[V] (appelée transport des structures le long de β) et ce, de façon cohérente, c’est-à-dire:

\begin{aligned}G[1_{U}] & = 1_{G[U]} \\ G[α ∘ β] & = G[α] ∘ G[β]. \end{aligned}

En d’autres mots, G est un foncteur de la catégorie Ensf des ensembles finis et bijections dans la catégorie des ensembles finis. Les éléments de G[U] sont appelés structures d’espèce G sur U.

Définition 1.2 Soit G une espèce de structures et s, t deux structures d’espèce G sur U (c-à-d. deux eléments de G[U]). Allors, s e t sont dites isomorphes s’il esiste une bijection α: U → U (c-à-d. une permutation de U) telle que

G[α](s) = t,

le type de s est la classe d’isomorphie de s dans G[U].

Exemple. Si U a quatre éléments, et si A est l’espèce ^{≪}arbres^{≫}, alors il y a 16 structures d’arbre sur U mais seulement deux types d’arbre.

* qui a présenté le résultat au séminaire lotharingien … et est seul responsable du titre.

Définition 1.3 Soient G et H deux espèces. Un isomorphisme de G sur H est une famille η = (η_{U})_{U∈|Ensf |} de bijections

η_{U}: G[U] → H[U]

qui satisfont la règle de cohérence suivante: pour chaque bijection f: U → V , on a

H[f] ∘ η_{U} = η_{V} ∘ G[f],

c-à-d., le diagramme

G[U] ⟶^{η_{U}} H[U]
↓^{G[f]}  ↓^{H[f]}
G[V] ⟶^{η_{V}} H[V]

est commutatif. En d’autres mots, η: G → H est un isomorphisme de foncteurs.

À l’avenir, par “G = H ” (quand G, et H dénotent des espèces), on signifiera G est isomorphe à H.

Définition 1.4 La somme des espèces G et H est l’espèce définie sur les ensembles finis par

(G + H)[U] = G[U] + H[U]

où “+” à droite veut dire réunion disjointe, et, sur les bijections f: U → V par

(G + H)[f](s) = \{ \begin{matrix}G[f](s), & si s ∈ G[U] \\ H[f](s), & si s ∈ H[U]. \end{matrix}

La somme admet un neutre: l’espèce 0 définie par

0[U] = ∅

Remarque. On définit de façon semblable la somme d’une suite (possiblement infinie) d’espèces. Par exemple, toute espèce G est somme infinie G = G_{0} + G_{1} + ⋯ où

G_{n}[U] = \{ \begin{matrix}G[U], & si Card(U) = n \\ ∅ & sinon. \end{matrix}

Définition 1.5 Le produit des espèces G e H est l’espèce définie par

(G · H)[U] = { (V, W, s, t) : V ⊆ U, W = U \ V, s ∈ G[V], t ∈ H[W] }

et, pour f: U → V e (V, W, s, t) ∈ (G · H)[U], par

(G · H)[f](V, W, s, t) = (f(V), f(W), G[f](s), G[f](t)).

Le produit admet un neutre, l’espèce 1 définie par

1[U] = \{ \begin{matrix}\{∅\} & si U = ∅ \\ ∅ & sinon \end{matrix}

Définition 1.6 La composition des espèces F et G où F [∅] = ∅ est l’espèce définie par

(F ∘ G)[U] = { (P, α, (β_{ν})_{ν∈P}) : P est partition de U, α ∈ F [P], (∀ν ∈ P, β_{ν} ∈ G[ν]) }

et, pour f: U → V et (P, α, (β_{ν})_{ν∈P}) ∈ (F ∘ G)[U], par

(F ∘ G)[f] = (\{ f(ν) : ν ∈ P \}, F [ \underline{f} ](α), ( β′_{μ})_{μ∈P′})

où

P′ = { f(ν) : ν ∈ P },
\underline{f}: P → P′: ν ↦ f(ν),
β′_{μ} = G[f_{f^{−1}(μ)}](β_{f^{−1}(μ)}),
f_{ν}: ν → f(ν): u ↦ f(u).

La composition admet un neutre, l’espèce X définie par

X[U] = \{ \begin{matrix}\{U\} & si Card(U) = 1 \\ ∅ & sinon. \end{matrix}

Proposition 1.7. La somme et le produit d’espèces sont des opérations commutatives et associatives, la composition est associative, les espèces 0, 1 et X sont respectivement neutre pour la somme, le produit et la composition.

Remarque. Le produit d’espèces étant commutatif et associatif, on peut, étant donnée une famille (B_{i})_{i∈I}, en définir le produit par

(∏_{i∈I} B_{i})[U] = { (U_{i}, s_{i})_{i∈I} : Les U_{i} sont disjoints de réunion U , (∀i ∈ I)(s_{i} ∈ B_{i}[U_{i}]) }

(∏_{i∈I} B_{i})[f]((U_{i}, s_{i})_{i∈I}) = (f(U_{i}), B_{i}[f_{U_{i}}](s_{i}))_{i∈I}

où f_{U_{i}}: U_{i} → f(U_{i}): u ↦ f(u).

On dira qu’une espèce G ≠ 0 vit sur une seule cardinalité s’il existe un n ∈ ℕ tel que Card(U) ≠ n ⟺ G[U] = ∅. L’entier n sera appelé le degré de l’espèce G et noté |G|.

Définition 1.9 Une espèce M est moléculaire si

\begin{matrix}M & ≠ 0 \\ (M = A + B) & ⇒ (A = 0 ou B = 0). \end{matrix}

Une espèce moléculaire vit donc sur une seule cardinalité n. En fait dire que M est moléculaire de degré n revient à dire que l’action de 𝔖_{n} sur M[\underline{n}]: (σ, s) ↦ M[σ](s) est transitive.

Définition 1.10 Une espèce A est atomique si

A est moléculaire
A ≠ 1
A = B · C ⇒ (B = 1 ou C = 1).

Définition 1.11 Une espèce P est primitive si

P est atomique
P ≠ X
P = B ∘ C ⇒ (B = X ou C = X).

Notations. Soit U un ensemble fini. On notera U! l’ensemble des permutations de U. Pour un sous-groupe H de U!, on notera

\frac{U!}{H}

l’espèce définie sur un ensemble fini V par

\frac{U!}{H}[V] = \{ fH : f ∈ Bij(U, V) \}

où Bij(U, V) = { f : f: U → V est une bijection. } et fH = { f ∘ h : h ∈ H }, et définie sur une bijection g: V → W par

\frac{U!}{H}[g] : fH ↦ (g ∘ f)H.

Lorsque U = [\underline{n}] = \{ 1 … n \}, on écrit aussi X^{n}/H pour désigner U!/H.

Étant donnée une espèce M, un ensemble fini U et une structure s d’espèce M sur U, on notera aut(s) l’ensemble { f ∈ U! : M[f](s) = s }. C’est l’ensemble des automorphismes de s.

Si U ⊇ W et f: U → U est une bijection telle que f(W) = W, on notera f_{W} la bijection de W → W: w ↦ f(w). Par contre, si g: W → W est une bijection, la notation g_{U} désignera la bijection

g_{U}: U → U: u ↦ \{ \begin{matrix}g(u), & si u ∈ W \\ u & sinon. \end{matrix}

Définition 1.12 Si H et K sont des sous-groupes de U! et V! respectivement, on dira que H et K sont conjugués s’il existe une bijection f: U → V telle que K = f ∘ H ∘ f^{−1} = { fhf^{−1} : h ∈ H }.

Proposition 1.13. Soient U et V des ensembles finis de même cardinalité et H et K des sous-groupes de U! et V! respectivement. Les espèces U!/H et V!/K sont isomorphes si et seulement si H et K sont conjugués. De façon précise, si

θ: \frac{U!}{H} → \frac{V!}{K}

est un isomorphisme d’espèces et f est tel que θ_{V}^{−1}(K) = fH, alors K = f ∘ H ∘ f^{−1} . Réciproquement, si K = f ∘ H ∘ f^{−1} , alors la famille des θ_{W} définie par θ_{W} (gH) = g ∘ f^{−1}H est un isomorphisme d’espèces

θ = (θ_{W})_{W ∈|Ensf|}: \frac{U!}{H} → \frac{V!}{K}.

.

Proposition 1.14. Caractérisation des espèces moléculaires. Soit U un ensemble fini et H un sous-groupe de U! L’espèce U!/H est moléculaire. Réciproquement, toute espèce moléculaire M de degré n est isomorphe à l’espèce U!/H si U est de cardinalité n et s’il existe une structure s ∈ M[U] telle que H = aut(s).

Proposition 1.15. Le produit d’une famille finie d’espèces moléculaires est moléculaire. La famille θ = (θ_{V})_{V ∈|Ensf|} définie par

\begin{matrix}∏_{i∈I} \frac{U_{i}!}{H_{i}}[V] & ⟶^{θ_{V}} \frac{U!}{H}[V] \\ (V_{i}, f_{i}H_{i}) & ⟶ fH, \end{matrix}

où f prolonge les f_{i},

H = ◯_{i∈I} H_{i} = { ◯_{i∈I} h_{i} : ∀i ∈ I, h_{i} ∈ H_{i} },

(la composition ne dépendant pas de l’ordre des termes, les h_{i} ayant des supports disjoints) et les U_{i} sont disjoints de réunion U, est un isomorphisme d’espèces.

Proposition 1.16. Soit M une espèce moléculaire, I un ensemble fini et A_{i} des espèces telles que M = ∏_{i∈I} A_{i}. Soit U un ensemble fini et s = (U_{i}, s_{i})_{i∈I} ∈ M[U]. Alors

∀f ∈ aut(s), ∀i ∈ I, f(U_{i}) = U_{i} et (f_{U_{i}})_{U} ∈ aut(s)
∀i ∈ I, aut(s_{i}) = { f_{U_{i}} : f ∈ aut(s) }.

En particulier, un facteur A_{i} est caractérisé, à isomorphisme près, par la donnée de aut(s) et de U_{i} (car A_{i} ≃ U_{i}!/aut(s_{i})).

Proposition 1.17. La composition de deux espèces moléculaires est moléculaire. De plus, si A et B sont moléculaires, U est un ensemble fini et s ∈ (A ∘ B)[U].

s = (Π, α, (β_{π})_{π∈Π})

Alors,

∀f ∈ aut(s), ∀π ∈ Π, f(π) ∈ Π

et si, pour f ∈ aut(s) on note \overline{f} la permutation de Π induite par f, alors

∀f ∈ aut(s), \overline{f} ∈ aut(α)
∀f ∈ aut(s), ∀π ∈ Π, f(π) = π ⇒ (f_{π} ∈ aut(β_{π}) et (f_{π})_{U} ∈ aut(s))
aut(α) = \{ \overline{f} : f ∈ aut(s) \}
∀π ∈ Π, aut(β_{π}) = { f_{π} : f ∈ aut(s) et f(π) = π }.

En particulier, A est déterminée à isomorphisme près par la donnée de aut(s) et de Π et B est déterminée à isomorphisme près par la donnée de aut(s) et d’un élḿent π de Π.

Théorème 1.18. Critère de Yeh. Soit M une espèce moléculaire. Si s ∈ M[U] et V ⊆ U sont tels que

∀f ∈ aut(s), f(V) = V
∀f ∈ aut(s), (f_{V})_{U} ∈ aut(s),

alors, on a un isomorphisme d’espèces

M ⟶^{∼} \frac{V!}{H} · \frac{(U \ V)!}{K}

avec

H = aut(s)_{V} = { f_{V} : f ∈ aut(s) }
K = aut(s)_{U\V} = { f_{U\V} : f ∈ aut(s) }

θ_{W} (t) = ( f(V), f(U \ V), f_{V} H, f_{U\V} K), où f: U → W est telle que M[f](s) = t.

Théorème 1.19. Théorème de Yeh. Les classes d’isomorphie d’espèces forment un semi-anneau isomorphe à ℕ[[M]] ≃ ℕ[[X_{a}]]_{a∈A} où M est le monoïde (pour ·) des classes d’isomorphie d’espèces moléculaires et A est l’ensemble des classes d’isomorphie d’espèces atomiques.

2. Le lemme fondamental. Dans cette section, nous allons énoncer, illustrer et enfin démontrer le lemme que Ouellette utilise par la suite pour démontrer les lois de simplification pour les espèces moléculaires.

Ces lois de simplification permettent ensuite de voir que si J est une espèce atomique, J ≠ X, alors il existe une espèce P et une espèce M, uniques à isomorphisme près, telles que

J ≃ P ∘ M

P est primitive

M est moléculaire.

En décomposant à son tour M en produit d’espèces atomiques (Th. 1.18) et en appliquant de nouveau le procédé à celles qui ne sont pas isomorphes à X, on obtient ainsi la ^{≪}décomposition arborescente^{≫} mentionnée en titre.

Voyons tout de suite l’énoncé du lemme fondamental suivi d’un exemple.

Lemme 2.1. Soient A, B, C, D des espèces moléculaires et θ un isomorphisme

A ∘ B ⟶^{∼} C ∘ D,

et soient

B = ∏_{i∈I} B_{i}

D = ∏_{k∈K} D_{k}

les décompositions de B et D en espèces atomiques. Soit U un esnsemble fini tel que (A ∘ B)[U] ≠ ∅ ≠ (C ∘ D)[U]. Soit s ∈ (A ∘ B)[U]. Posons

s = (Π, α, ((π_{i}, β_{π_{i}})_{i∈I})_{π∈Π})
θ_{U}(s) = (Π′, γ, ((π′_{k}, δ_{π′_{k}})_{k∈K})_{π′∈Π′}) .

Posons de plus, pour chaque choix de π ∈ Π et i ∈ I:

Π′_{π_{i}} = { π′ ∩ π_{i} : π′ ∈ Π′ et π′ ∩ π_{i} ≠ ∅ }

et pour chaque choix de π′ ∈ Π′ et k ∈ K:

Π_{π′_{k}} = { π ∩ π′_{k} : π ∈ Π et π ∩ π′_{k} ≠ ∅ }.

Supposons enfin qu’il existe au moins un choix de (i, π, k, π′) ∈ I × Π × K × Π′ tel que π_{i} ∩ π′_{k} ≠ ∅ et π_{i} ≠ π′_{k}.

Alors une et une seule des propriétés suivantes est vérifiée a. Pour tout choix de (i, π, k, π′) ∈ I × Π × K × Π′ tel que π_{i} ∩ π′_{k} ≠ ∅ et π_{i} ≠ π′_{k},

on a

Π′_{π_{i}} ⊂ Π′ et Card (Π′_{π_{i}}) ≥ 2.

En d’autres mots, chaque π_{i} est réunion d’au moins deux éléments de Π′. b. Pour tout choix de (i, π, k, π′) ∈ I × Π × K × Π′ tel que π_{i} ∩ π′_{k} ≠ ∅ et π_{i} ≠ π′_{k},

on a

Π_{π′_{k}} ⊂ Π et Card (Π_{π′_{k}}) ≥ 2.

En d’autres mots, chaque π′_{k} est réunion d’au moins deux éléments de Π.

Un exemple. Soient X l’espèce Singleton

E_{2} ≃ \frac{X^{2}}{𝔖_{2}} l’espèce Ensemble à deux éléments et

C_{3} ≃ \frac{X^{3}}{A_{3}} l’espèce Cycle de longueur 3.

La figure A∘B représente une des 26987494074303548957539873849344000000000 A∘B structures s sur l’ensemble U des 40 points noirs. La partition Π est formée des deux colonnes, sur l’ensemble desquelles il y a la structure d’ensemble à deux éléments et sur l’ensemble des points de chacune desquelles il y a une B structure. Pour chaque colonne π ∈ Π, il y a trois ^{≪}π_{i}^{≫} (Card(I) = 3). Pour fixer les idées, posons Π = { π_{g}, π_{d} } (pour gauche, droite) et I = { h, m, b } (pour haut, milieu, bas).

La figure C ∘ D représente la C ∘ D structure θ_{U}(s) sur U. La partition Π′ est formée des huit colonnes sur l’ensemble desquelles il y a une structure d’espèce E_{2} ∘ (X · C_{3}) et sur les points de chacune desquelles il y a une C_{3} · E_{2} structure. Pour chaque colonne π′ ∈ Π′, il y a deux ^{≪}π′_{k}^{≫} (Card(K) = 2). Comme ci-dessus, posons Π′ = { π′_{1}, …, π′_{8} } (les colonnes de gauche à droite) et K = { h, b } (haut, bas).

Conformément au lemme (cas a.), on voit que chaque ^{≪}π_{i}^{≫} qui n’est pas égal à un ^{≪}π′_{k}^{≫} (en l’occurence (π_{g})_{b} et (π_{d})_{b}) est réunion d’au moins deux (ici exactement trois) éléments de Π′. Ainsi (π_{g})_{b} = π′_{2} ∪ π′_{3} ∪ π′_{4} . Un coup d’oeil à la figure nous montre l’isomorphisme naturel θ.

preuve du Lemme 2.1. Si ^{≪}a.^{≫} est vérifiée, alors

|B| ≥ |B_{i}| ≥ 2 · |D| > |D|.

De même, si ^{≪}b.^{≫} est vérifiée, on a |D| > |B| ce qui montre que les deux conditions ne peuvent être vérifiées en même temps.

Supposons les deux conditions fausses. Soient (i, π, k, π′) ∈ I × Π × K × Π′ tel que π_{i} ∩ π′_{k} ≠ ∅ et π_{i} ≠ π′_{k}.

La négation de ^{≪}a.^{≫} entraîne

(∃x)(∃ν′)(x ∈ ν′ ∈ Π′ et x ∉ π_{i} et π_{i} ∩ ν′ ≠ ∅) ou π′ = π_{i}  (1).

En effet distinguons deux cas.

Dans le cas π′ ⊈ π_{i}, on a (∃x)(x ∈ π′ et x ∉ π_{i}) et on conclut (1) en posant ν′ = π′.

Dans le cas π′ ⊆ π_{i}, si π′ = π_{i} il est clair qu’on a (1). Sinon π′ ≠ π_{i}, donc

Card (Π′_{π_{i}}) ≥ 2.

et comme ^{≪}a.^{≫} n’est pas vérifiée, on doit donc avoir

Π′_{π_{i}} ⊈ Π′.

Il y a donc un ν′ ∈ Π′ tel que ν′ ∩ π_{i} ≠ ∅ et ν′ ∩ π_{i} ∉ Π′. Il ne reste plus qu’à prendre x ∈ ν′ \ ν′ ∩ π_{i}.

De façon semblable, la négation de ^{≪}b.^{≫} entraîne

(∃y)(∃ν)(y ∈ ν ∈ Π et y ∉ π′_{k} et π′_{k} ∩ ν ≠ ∅) ou π = π′_{k}  (2)

.

Le cas π′ = π_{i} ne peut se produire car alors D = B_{i} (prop. 1.16, 1.17 et fait que aut(s) = aut(θ_{U}(s)) est atomique et donc D = D_{k} et π′ = π′_{k} = π_{i} contredisant l’hypothèse. De même, le cas π = π′_{k} ne peut se produire.

Par (1) on a donc

(∃x)(∃ν′)(x ∈ ν′ ∈ Π′ et x ∉ π_{i} et π_{i} ∩ ν′ ≠ ∅).

Choisissons un l ∈ K tel que π_{i} ∩ ν′_{l} ≠ ∅. Soit ω = π_{i} ∩ ν′_{l}.

Soit g ∈ aut(β_{π_{i}}). Alors

g_{U} ∈ aut(s)
g_{U}(x) = x  car x ∈ π_{i} et g_{U} est l’identité hors de π_{i}
g_{U}(ν′) = ν′  car g_{U} préserve Π′ et x ∈ g_{U}(ν′) ∩ ν′
g_{U}(ν′_{l}) = ν′_{l}  prop. 1;16
g_{U}(π_{i}) = π_{i}  car (g_{U})_{π_{i}} = g
g_{U}(ω) = g_{U}(π_{i} ∩ ν′_{l}) = ω
(g_{U})_{ν′_{l}} ∈ aut(ν′_{l})  vu que g_{U}(ν′) = ν′
((g_{U})_{ν′_{l}})_{U} ∈ aut(s)  prop. 1.16 et 1.17
(((g_{U})_{ν′_{l}})_{U})_{π_{i}} = (g_{ω})_{π_{i}} ∈ aut(β_{π_{i}}) prop. 1.16 et 1.17

Par le critère de Yeh, l’atomicité de B_{i} est contredite si ω ≠ π_{i}. Donc ω = π_{i} ⊆ ν′_{l}. Comme π_{i} ∩ π′_{k} ≠ ∅, on a ν′_{l} = π′_{k} et π_{i} ⊆ π′_{k}.

En raisonnant de façon analogue à partir de l’équation (2), on arrive à π′_{k} ⊆ π_{i} ce qui donne finalement π_{i} = π′_{k}, une contradiction à l’hypothèse π_{i} ≠ π′_{k}.

3. Lois de simplification et décomposition arborescente. Dans cette section, nous ferons un exposé sommaire des résultats conduisant à la décomposition arborescente.

Proposition 3.1. Si A est une espèce atomique et H et N sont des espèces telles que A = H ∘ N, alors H est atomique et N est moléculaire.

La démonstration est immédiate.

Prosposition 3.2. Loi de simplification à gauche. Si A, B et C sont des espèces moléculaires telles que A ∘ B ≃ A ∘ C, alors B ≃ C.

On décompose B et C en produits d’espèces atomiques. L’observation des cardinalités nous conduit à montrer que, avec les notations du lemme fondamental, chaque ≪π_{i}^{≫} est un ^{≪}π′_{k}^{≫} et que chaque ^{≪}B_{i}^{≫} est un ^{≪}C_{k}^{≫} en vertu des prop. 1.16 et 1.17.

Proposition 3.3. Loi de simplification à droite. Si A, B et C sont des espèces moléculaires telles que A ∘ C ≃ B ∘ C, alors A ≃ B.

Cette fois-ci, on montre d’abord le cas C = X^{n} et on montre ensuite, par récurrence sur le degré n de C que ce cas implique le cas général.

Pour le cas C = X^{n}, avec les notations du lemme fondamental, ^{≪}les π_{i} et les π′_{k} sont de cardinalité 1^{≫}. On prend s ∈ (A ∘ X^{n})[U] et on étudie une relation d’équivalence sur l’ensemble O des orbites de l’action de aut(s) sur U, deux orbites étant équivalentes s’il existe un élément t du centralisateur de aut(s) dans U! qui les transpose et laisse fixes les autres orbites. On est ainsi amené à construire deux sousgroupes conjugués H et K de U!, tels que A ≃ U!/H et B ≃ U!/K et on applique la proposition 1.13.

Proposition 3.4. Décomposition arborescente. Si J est une espèce atomique, J ≠ X, alors il existe une espèce P et une espèce M, uniques à isomorphisme près, telles que

J ≃ P ∘ M

P est primitive

M est moléculaire.

En décomposant à son tour M en produit d’espèces atomiques (Th. 1.18) et en appliquant de nouveau le procédé à celles qui ne sont pas isomorphes à X, on obtient ainsi une ^{≪}décomposition arborescente^{≫} de J.

Il est facile de voir par récurrence l’existence de P et M. Quant à l’unicité, elle se démonstre en utilisant la récurence et les lois de simplification.

Les espèces E_{2} et C_{3} sont primitives. Dans l’exemple de la section précédente, il est alors facile de voir la décomposition arborescente, c’est

E_{2} ∘ (C_{3} · E_{2} · (C_{3} ∘ (C_{3} · E_{2}))) .

4. Conclusion Les preuves fournies ou esquissées dans cet exposé sont des adaptations de celles que Mario Ouellette a fournies dans son mémoire de maîtrise.

Mentionnons toutefois qu’il existe une autre démonstration indépendente des lois de simplification pour les espèces moléculaires due à André Longtin ([Lon]) et faisant intervenir la théorie des groupes. On remarquera que Ouellette aussi, dans sa preuve de la simplification à droite utilise des techniques de groupes.

5. Bibliographie.

[Joy] André Joyal, Une théorie combinatoire des séries formelles, Adv. in Math. 42 (1981), 1–82.

[LaJ1] Jacques Labelle, Applications diverses de la théorie combinatoire des espèces de structures, Ann. Sc. Math. Québec 7 (1983) 59–94.

[LaJ2] Jacques Labelle, Quelques espèces sur les ensembles de petite cardinalité, Ann. Sc. Math. Québec. 9 (1985) 31–58.

[Lon] André Longtin, Lois de simplification pour les espèces moléculaires. Communication au colloque des Sciences mathématiques du Québec, Montréal (Automne 1987).

[Oue] Mario Ouellette, Décomposition des espèces moléculaires en forêts d’arborescences d’espèces primitives, Mémoire de maîtrise, Université du Québec à Montréal. (1987)

[Yeh] Yeong-Nan Yeh, On the Combinatorial Species of Joyal, Ph.D. Thesis, State University of New York at Buffalo. (1985)