448
B Rappels mathématiques : combinatoire
Dans ce livre nous rencontrons uniquement des classes combinatoires qui sont
construites à partir d’opérations ensemblistes élémentaires. La classe neutre et la
classe atomique définies ci-dessous sont la base des objets combinatoires que nous
construisons dans ce livre.
Une classe neutre, souvent notée E, est une classe combinatoire qui consiste en
un seul objet de taille 0. Un tel objet est dit « objet neutre » et il est souvent noté ε.
Une classe atomique, souvent notée Z, est une classe combinatoire qui consiste
en un seul objet de taille 1. Un tel objet est appelé un atome.
Le mot « atome » est souvent utilisé pour désigner aussi un nœud générique dans
un arbre, parce qu’un arbre de taille n peut être considéré comme étant en bijection
avec la réunion de n classes atomiques.
En notant c n = Card(C n ), la série génératrice C(z), dite « ordinaire », associée
à la classe combinatoire C est la série formelle
C(z) =
γ ∈C
z
|γ |
=
n≥0
c n z
n .
(B.1)
La série génératrice d’une classe neutre est E(z) = 1 et celle d’une classe atomique
est Z(z) = z.
Notation Nous utilisons abondamment, pour une série formelle f (z) =
n≥0 f n z n , la notation [z n ]f (z) = f n pour le coefficient de z n .
B.1.2 Classes étiquetées
Il arrive de rencontrer des structures combinatoires qui se présentent naturellement
comme étiquetées (ou encore marquées). Ceci se produit lorsqu’un objet de taille n
est vu comme réunion de n atomes (par exemple un arbre à n nœuds) et lorsque ces
atomes contiennent une étiquette qui les distinguent les uns des autres. Lorsqu’en
outre la collection de toutes les étiquettes des atomes est l’intervalle complet des
entiers [1 . . n], l’objet de taille n est dit « bien étiqueté ». Une classe étiquetée
est une classe combinatoire composée d’objets bien étiquetés. Une classe neutre
étiquetée contient un objet de taille 0, sans étiquette, elle est notée encore E. Une
classe atomique étiquetée contient un objet de taille 1, étiqueté par 1, elle est notée
encore Z.
Le type de série génératrice adaptée aux structures étiquetées est la série
génératrice dite « exponentielle »
C(z) associée à la classe C :
C(z) =
γ ∈C
z |γ |
|γ |!
=
n≥0
c n
n!
z
n .
B Rappels mathématiques : combinatoire
Dans ce livre nous rencontrons uniquement des classes combinatoires qui sont
construites à partir d’opérations ensemblistes élémentaires. La classe neutre et la
classe atomique définies ci-dessous sont la base des objets combinatoires que nous
construisons dans ce livre.
Une classe neutre, souvent notée E, est une classe combinatoire qui consiste en
un seul objet de taille 0. Un tel objet est dit « objet neutre » et il est souvent noté ε.
Une classe atomique, souvent notée Z, est une classe combinatoire qui consiste
en un seul objet de taille 1. Un tel objet est appelé un atome.
Le mot « atome » est souvent utilisé pour désigner aussi un nœud générique dans
un arbre, parce qu’un arbre de taille n peut être considéré comme étant en bijection
avec la réunion de n classes atomiques.
En notant c n = Card(C n ), la série génératrice C(z), dite « ordinaire », associée
à la classe combinatoire C est la série formelle
C(z) =
γ ∈C
z
|γ |
=
n≥0
c n z
n .
(B.1)
La série génératrice d’une classe neutre est E(z) = 1 et celle d’une classe atomique
est Z(z) = z.
Notation Nous utilisons abondamment, pour une série formelle f (z) =
n≥0 f n z n , la notation [z n ]f (z) = f n pour le coefficient de z n .
B.1.2 Classes étiquetées
Il arrive de rencontrer des structures combinatoires qui se présentent naturellement
comme étiquetées (ou encore marquées). Ceci se produit lorsqu’un objet de taille n
est vu comme réunion de n atomes (par exemple un arbre à n nœuds) et lorsque ces
atomes contiennent une étiquette qui les distinguent les uns des autres. Lorsqu’en
outre la collection de toutes les étiquettes des atomes est l’intervalle complet des
entiers [1 . . n], l’objet de taille n est dit « bien étiqueté ». Une classe étiquetée
est une classe combinatoire composée d’objets bien étiquetés. Une classe neutre
étiquetée contient un objet de taille 0, sans étiquette, elle est notée encore E. Une
classe atomique étiquetée contient un objet de taille 1, étiqueté par 1, elle est notée
encore Z.
Le type de série génératrice adaptée aux structures étiquetées est la série
génératrice dite « exponentielle »
C(z) associée à la classe C :
C(z) =
γ ∈C
z |γ |
|γ |!
=
n≥0
c n
n!
z
n .