18
1 Botanique
Nous pouvons aussi donner une définition récursive, par classes combinatoires,
des arbres de Cayley.
Définition 1.22 La classe Cay des arbres de Cayley vérifie l’équation récursive
Cay = (◦ × SET(Cay)),
où SET désigne la construction combinatoire Ensemble-de. Attention, ici l’opérateur
× désigne le produit étiqueté défini en section B.1.2.
Notons que l’arbre réduit à une feuille est obtenu en prenant un ensemble vide de
sous-arbres.
1.2.4 Arbres croissants, tas, et arbres récursifs
Définition 1.23 Un arbre croissant est un arbre marqué dans lequel les marques
sont prises dans un ensemble totalement ordonné, et telles qu’elles croissent le long
des branches, en partant de la racine.
Par conséquent, la marque de chaque nœud interne d’un arbre croissant est
inférieure ou égale à celles de chacun de ses enfants.
Remarque 1.24 Un arbre croissant peut être planaire ou non ; nous verrons ci-après
deux exemples d’arbres croissants : les tas, qui sont planaires, et les arbres récursifs,
qui ne le sont pas.
Un arbre croissant τ a un arbre des rangs obtenu par marquage canonique, en
renumérotant les marques de 1 à |τ | (ou à un entier inférieur à sa taille s’il y a
des répétitions), cf. la définition 1.16. De plus, lorsque l’arbre est planaire et que les
marques sont toutes distinctes, il est possible de calculer le nombre d’arbres marqués
ayant la même forme d’arbre ; c’est la formule d’équerre donnée ci-dessous.
Proposition 1.25 (Formule d’équerre) Soit τ un arbre planaire non marqué et
soit un ensemble de |τ | marques distinctes ; le nombre λ(τ ) de marquages croissants
de τ , sans répétition de marques, est donné par une formule d’équerre 8 :
λ(τ ) =
|τ |!
σ
|σ |
,
(1.6)
où σ parcourt l’ensemble des sous-arbres de τ .
8 Le nom vient de l’analogie avec la formule d’équerre utilisée dans l’énumération des tableaux de
Young.
1 Botanique
Nous pouvons aussi donner une définition récursive, par classes combinatoires,
des arbres de Cayley.
Définition 1.22 La classe Cay des arbres de Cayley vérifie l’équation récursive
Cay = (◦ × SET(Cay)),
où SET désigne la construction combinatoire Ensemble-de. Attention, ici l’opérateur
× désigne le produit étiqueté défini en section B.1.2.
Notons que l’arbre réduit à une feuille est obtenu en prenant un ensemble vide de
sous-arbres.
1.2.4 Arbres croissants, tas, et arbres récursifs
Définition 1.23 Un arbre croissant est un arbre marqué dans lequel les marques
sont prises dans un ensemble totalement ordonné, et telles qu’elles croissent le long
des branches, en partant de la racine.
Par conséquent, la marque de chaque nœud interne d’un arbre croissant est
inférieure ou égale à celles de chacun de ses enfants.
Remarque 1.24 Un arbre croissant peut être planaire ou non ; nous verrons ci-après
deux exemples d’arbres croissants : les tas, qui sont planaires, et les arbres récursifs,
qui ne le sont pas.
Un arbre croissant τ a un arbre des rangs obtenu par marquage canonique, en
renumérotant les marques de 1 à |τ | (ou à un entier inférieur à sa taille s’il y a
des répétitions), cf. la définition 1.16. De plus, lorsque l’arbre est planaire et que les
marques sont toutes distinctes, il est possible de calculer le nombre d’arbres marqués
ayant la même forme d’arbre ; c’est la formule d’équerre donnée ci-dessous.
Proposition 1.25 (Formule d’équerre) Soit τ un arbre planaire non marqué et
soit un ensemble de |τ | marques distinctes ; le nombre λ(τ ) de marquages croissants
de τ , sans répétition de marques, est donné par une formule d’équerre 8 :
λ(τ ) =
|τ |!
σ
|σ |
,
(1.6)
où σ parcourt l’ensemble des sous-arbres de τ .
8 Le nom vient de l’analogie avec la formule d’équerre utilisée dans l’énumération des tableaux de
Young.