1.1 Arbres non marqués
7
Définition 1.6 Une forêt est une union d’arbres.
Ainsi l’ensemble des sous-arbres issus des enfants d’un nœud d’un arbre planaire
est une forêt.
Remarque 1.7 Il suffit, pour définir un arbre τ , de se donner une suite d’entiers
M u , u ∈ U (où M u sera le nombre d’enfants du nœud u et aussi l’arité du nœud u),
assortie des conditions de la définition 1.1. Un tel arbre est fini ou infini. Quand le
nœud concerné est la racine de l’arbre, nous notons M plutôt que M ε :
M := nombre d’enfants de l’ancêtre = arité de la racine.
Par ailleurs, il est facile de vérifier que la condition (iii) dans la définition 1.1
peut être remplacée par (iii’) : {uk ∈ τ et k > 1} ⇒ {u(k − 1) ∈ τ } . Avec (iii’),
le nombre d’enfants du nœud u, M u (τ ) := max{k ≥ 1, uk ∈ τ }, doit être défini par
la suite.
B. Classes combinatoires Nous définissons ci-dessous la classe combinatoire
des arbres planaires. Nous utilisons la notion de classe combinatoire atomique
(cf. section B.1) et la construction Suite non vide de (cf. section B.2), que nous
notons SEQ >0 (figure 1.3).
Définition 1.8 (récursive) Une classe combinatoire P est une classe d’arbres
planaires lorsqu’il existe deux classes combinatoires atomiques contenant chacune
un objet de taille 1, respectivement notés • et et appelés « nœud interne » et
« nœud externe », telles que P vérifie l’équation récursive 2
P = + (• × SEQ >0 (P)).
(1.1)
Remarque 1.9 Les deux définitions 1.1 et 1.8 ne sont pas strictement équivalentes,
puisqu’elles ne fournissent pas le même ensemble d’arbres : la définition récursive
produit des arbres finis, puisqu’une classe combinatoire se compose d’objets de
taille finie ; alors qu’un arbre avec la première définition peut être fini ou infini. Par
Fig. 1.3 Cet arbre planaire à deux nœuds internes et quatre feuilles est une représentation dans
le plan de l’objet combinatoire (•, ( , (•, ( )))). Sa taille est égale à 6, le nombre total de
nœuds
2 Dans toutes les définitions de classes combinatoires, nous notons les classes atomiques et • au
lieu de { et {•}, ceci afin d’alléger les notations.
7
Définition 1.6 Une forêt est une union d’arbres.
Ainsi l’ensemble des sous-arbres issus des enfants d’un nœud d’un arbre planaire
est une forêt.
Remarque 1.7 Il suffit, pour définir un arbre τ , de se donner une suite d’entiers
M u , u ∈ U (où M u sera le nombre d’enfants du nœud u et aussi l’arité du nœud u),
assortie des conditions de la définition 1.1. Un tel arbre est fini ou infini. Quand le
nœud concerné est la racine de l’arbre, nous notons M plutôt que M ε :
M := nombre d’enfants de l’ancêtre = arité de la racine.
Par ailleurs, il est facile de vérifier que la condition (iii) dans la définition 1.1
peut être remplacée par (iii’) : {uk ∈ τ et k > 1} ⇒ {u(k − 1) ∈ τ } . Avec (iii’),
le nombre d’enfants du nœud u, M u (τ ) := max{k ≥ 1, uk ∈ τ }, doit être défini par
la suite.
B. Classes combinatoires Nous définissons ci-dessous la classe combinatoire
des arbres planaires. Nous utilisons la notion de classe combinatoire atomique
(cf. section B.1) et la construction Suite non vide de (cf. section B.2), que nous
notons SEQ >0 (figure 1.3).
Définition 1.8 (récursive) Une classe combinatoire P est une classe d’arbres
planaires lorsqu’il existe deux classes combinatoires atomiques contenant chacune
un objet de taille 1, respectivement notés • et et appelés « nœud interne » et
« nœud externe », telles que P vérifie l’équation récursive 2
P = + (• × SEQ >0 (P)).
(1.1)
Remarque 1.9 Les deux définitions 1.1 et 1.8 ne sont pas strictement équivalentes,
puisqu’elles ne fournissent pas le même ensemble d’arbres : la définition récursive
produit des arbres finis, puisqu’une classe combinatoire se compose d’objets de
taille finie ; alors qu’un arbre avec la première définition peut être fini ou infini. Par
Fig. 1.3 Cet arbre planaire à deux nœuds internes et quatre feuilles est une représentation dans
le plan de l’objet combinatoire (•, ( , (•, ( )))). Sa taille est égale à 6, le nombre total de
nœuds
2 Dans toutes les définitions de classes combinatoires, nous notons les classes atomiques et • au
lieu de { et {•}, ceci afin d’alléger les notations.