B Rappels mathématiques : combinatoire
449
La série génératrice exponentielle d’une classe neutre étiquetée est E(z) = 1 et celle
d’une classe atomique étiquetée est Z(z) = z.
B.2 Méthode symbolique
Des dictionnaires mettent en relation constructions combinatoires et opérations sur
les séries génératrices. C’est un des grands intérêts de la méthode symbolique. Une
fois la structure combinatoire bien comprise, il est assez facile de calculer les séries
génératrices correspondantes.
B.2.1 Constructions sur les classes non étiquetées
Nous commençons par le principe de la méthode symbolique pour le cas des classes
combinatoires « non étiquetées ».
Les classes décomposables non étiquetées sont définies à partir de classes
combinatoires de base et d’opérations sur ces classes :
– La classe neutre, qui est constituée d’un élément de taille 0 et notée E.
– La classe atomique, qui est constituée d’un objet de taille 1 et notée Z.
– L’union disjointe C = A ⊕ B de deux classes A et B.
– Le produit cartésien C = A × B = {(α, β); (α, β) ∈ A × B} de deux classes A
et B. La taille du couple (α, β) est la somme des tailles : |(α, β)| = |α| + |β|.
– L’opérateur SEQ, étendant le produit cartésien à un nombre fini d’ensembles,
qui permet de construire la classe des séquences finies d’objets d’une classe.
L’opérateur Suite non vide de, noté SEQ >0 , permet de construire la classe des
suites finies non vides d’objets d’une classe.
Il existe d’autres constructions comme par exemple les opérateurs SET, CYC ou
encore MSET correspondant respectivement aux classes obtenues en considérant un
ensemble d’éléments (par rapport à la séquence, on oublie l’ordre et on interdit les
doublons), un cycle d’éléments (une séquence « circulaire ») et un multi-ensemble
d’éléments (les répétitions sont permises). On peut aussi substituer aux atomes
d’une classe des objets d’une autre classe, ou encore construire une classe où un
atome sera distingué (ou encore pointé).
L’intérêt de ces constructions est qu’elles se traduisent directement sur les séries
génératrices ordinaires correspondantes. Dans la table B.1, nous avons rassemblé
les principales constructions combinatoires avec leur traduction en termes de séries
génératrices ordinaires.
449
La série génératrice exponentielle d’une classe neutre étiquetée est E(z) = 1 et celle
d’une classe atomique étiquetée est Z(z) = z.
B.2 Méthode symbolique
Des dictionnaires mettent en relation constructions combinatoires et opérations sur
les séries génératrices. C’est un des grands intérêts de la méthode symbolique. Une
fois la structure combinatoire bien comprise, il est assez facile de calculer les séries
génératrices correspondantes.
B.2.1 Constructions sur les classes non étiquetées
Nous commençons par le principe de la méthode symbolique pour le cas des classes
combinatoires « non étiquetées ».
Les classes décomposables non étiquetées sont définies à partir de classes
combinatoires de base et d’opérations sur ces classes :
– La classe neutre, qui est constituée d’un élément de taille 0 et notée E.
– La classe atomique, qui est constituée d’un objet de taille 1 et notée Z.
– L’union disjointe C = A ⊕ B de deux classes A et B.
– Le produit cartésien C = A × B = {(α, β); (α, β) ∈ A × B} de deux classes A
et B. La taille du couple (α, β) est la somme des tailles : |(α, β)| = |α| + |β|.
– L’opérateur SEQ, étendant le produit cartésien à un nombre fini d’ensembles,
qui permet de construire la classe des séquences finies d’objets d’une classe.
L’opérateur Suite non vide de, noté SEQ >0 , permet de construire la classe des
suites finies non vides d’objets d’une classe.
Il existe d’autres constructions comme par exemple les opérateurs SET, CYC ou
encore MSET correspondant respectivement aux classes obtenues en considérant un
ensemble d’éléments (par rapport à la séquence, on oublie l’ordre et on interdit les
doublons), un cycle d’éléments (une séquence « circulaire ») et un multi-ensemble
d’éléments (les répétitions sont permises). On peut aussi substituer aux atomes
d’une classe des objets d’une autre classe, ou encore construire une classe où un
atome sera distingué (ou encore pointé).
L’intérêt de ces constructions est qu’elles se traduisent directement sur les séries
génératrices ordinaires correspondantes. Dans la table B.1, nous avons rassemblé
les principales constructions combinatoires avec leur traduction en termes de séries
génératrices ordinaires.