B Rappels mathématiques : combinatoire
451
Fig. B.1 Un exemple de produit étiqueté. En haut deux arbres étiquetés : β de taille 3, et γ de
taille 2. En dessous les 10 =
3+2
2
étiquetages du produit étiqueté β β γ
Table B.2 Principales constructions combinatoires pour les classes étiquetées : union, produit,
séquence, ensemble, cycle, pointage et substitution, avec leur traduction en termes de séries
génératrices exponentielles
Construction
séries génératrices exponentielles
Union disjointe
A = B + C
A(z) = B(z) + C(z)
Produit étiqueté
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))
Cycle
A = CYC(B)
A(z) = log
1
1 − B(z)
Pointage
A =
A(z) = z
d
dz B(z)
Substitution
A = B ◦ C
A(z) = B(C(z))
En particulier, pour une séquence, un ensemble et un cycle de cardinalité k fixée :
SEQ k (B) : B(z) k
SET k (B) :
1
k! B(z) k
CYC k (B) :
1
k B(z)
Notons qu’il y a
m+n
n
bons étiquetages de (β, γ ). Un exemple de produit
étiqueté de deux arbres se trouve en figure B.1.
Ainsi défini, le produit étiqueté se traduit par le produit usuel des séries
génératrices exponentielles, ce qui sera utilisé par la méthode symbolique.
Les constructions combinatoires sur les classes étiquetées sont les mêmes mais
doivent tenir compte du produit étiqueté qui considère tous les étiquetages des
composantes du produit. Dans la table B.2, nous avons rassemblé les principales
constructions combinatoires avec leur traduction en termes de séries génératrices
exponentielles (repris de [94]).