450
B Rappels mathématiques : combinatoire
Table B.1 Les principales constructions combinatoires : union, produit, séquence, ensemble,
multi-ensemble, cycle, pointage et substitution, pour les classes combinatoires (non étiquetées),
avec leur traduction en termes de séries génératrices ordinaires
Construction
séries génératrices ordinaires
Union disjointe
A = B + C
A(z) = B(z) + C(z)
Produit cartésien
A = B × C
A(z) = B(z) · C(z)
Séquence
A = SEQ(B)
A(z) =
1
1 − B(z)
Ensemble
A = SET(B)
A(z) = exp
B(z) −
1
2
B(z
2 ) + · · ·
Multiensemble
A = MSET(B)
A(z) = exp
B(z) +
1
2
B(z
2 ) + · · ·
Cycle
A = CYC(B)
A(z) = log
1
1 − B(z)
+
1
2
log
1
1 − B(z 2 )
+ · · ·
Pointage
A =
A(z) = z
d
dz B(z)
Substitution
A = B ◦ C
A(z) = B(C(z))
En particulier, pour une séquence de cardinalité k fixée, un ensemble, un multi-ensemble et un
cycle de cardinalité k = 2 ou 3 fixée :
SEQ k (B) : B(z) k
SET 2 (B) :
B(z) 2
2 −
B(z 2 )
2
MSET 2 (B) :
B(z) 2
2 +
B(z 2 )
2
CYC 2 (B) :
B(z) 2
2 +
B(z 2 )
2
SET 3 (B) :
B(z) 3
6 −
B(z)B(z 2 )
2
+
B(z 3 )
3
MSET 3 (B) :
B(z) 3
6 +
B(z)B(z 2 )
2
+
B(z 3 )
3
CYC 3 (B) :
B(z) 3
3 +
2B(z 3 )
3
B.2.2 Constructions sur les classes étiquetées
Le produit cartésien de deux classes B et C s’étend par le produit étiqueté de deux
classes étiquetées. C’est la réunion sur tous les couples (β, γ ) des produits étiquetés
de deux objets β et γ , défini comme suit. Le produit étiqueté de deux objets β et γ ,
bien étiquetés respectivement par [1 . . m] et [1 . . n], est noté β βγ ; c’est l’ensemble
des couples (β , γ ) où β et γ sont obtenus en effaçant les étiquettes de β et γ , et
où on étiquette (β , γ ) de toutes les façons possibles par l’ensemble [1 . . m + n] en
respectant les règles suivantes :
– l’ensemble des étiquettes des atomes de β est disjoint de l’ensemble des
étiquettes des atomes de γ ,et leur réunion est l’ensemble [1 . . m + n] ;
– l’étiquetage des atomes de β, respectivement de γ , est une fonction strictement
croissante de [1 . . m] (l’étiquetage initial de β), respectivement de [1 . . n]
(l’étiquetage initial de γ ).