1.1 Arbres non marqués
13
l’ensemble des arbres planaires de taille n vers l’ensemble des arbres binaires de
taille n − 1. Nous laissons à la lectrice ou au lecteur la construction de la bijection
réciproque, associant un arbre planaire de taille n + 1 à un arbre binaire de taille n.
1.1.4 Arbres non planaires, ou de Pólya.
Ces arbres ont notamment été étudiés par Pólya [211], d’où notre utilisation du
terme « arbres de Pólya » pour les désigner. Nous donnons ci-dessous deux manières
équivalentes de les définir : comme classe combinatoire, et comme ensemble
quotient.
Définition 1.13 Une classe combinatoire Pó est une classe d’arbres de Pólya
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 « feuille »,
telles que Pó vérifie l’équation récursive
Pó = + (• × MSET(Pó)),
où la construction combinatoire MSET correspond au multi-ensemble, i.e., au choix
d’un ensemble non vide d’arbres, avec répétitions possibles.
En d’autres termes, un nœud a, non pas une suite ordonnée, mais un ensemble (fini)
d’enfants (figure 1.11).
Définition 1.14 Soit R la relation d’équivalence sur l’ensemble P des arbres
planaires engendrée par la relation binaire suivante : deux arbres planaires τ et τ
sont en relation si l’on peut passer de l’un à l’autre en permutant les sous-arbres
d’un même nœud. L’ensemble Pó des arbres de Pólya est l’ensemble des classes
d’équivalence de P pour la relation R.
En toute rigueur, ces deux définitions ne sont pas équivalentes (une classe
d’équivalence n’est pas une classe combinatoire). Cependant, si nous nous limitons
dans la définition 1.14 à des arbres finis, elles définissent des ensembles isomorphes,
puisque l’ensemble des classes d’équivalence de la définition 1.14 est bien la classe
combinatoire des arbres de Pólya au sens de la définition 1.13.
Fig. 1.11 Deux représentations planaires d’un même arbre de Pólya
13
l’ensemble des arbres planaires de taille n vers l’ensemble des arbres binaires de
taille n − 1. Nous laissons à la lectrice ou au lecteur la construction de la bijection
réciproque, associant un arbre planaire de taille n + 1 à un arbre binaire de taille n.
1.1.4 Arbres non planaires, ou de Pólya.
Ces arbres ont notamment été étudiés par Pólya [211], d’où notre utilisation du
terme « arbres de Pólya » pour les désigner. Nous donnons ci-dessous deux manières
équivalentes de les définir : comme classe combinatoire, et comme ensemble
quotient.
Définition 1.13 Une classe combinatoire Pó est une classe d’arbres de Pólya
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 « feuille »,
telles que Pó vérifie l’équation récursive
Pó = + (• × MSET(Pó)),
où la construction combinatoire MSET correspond au multi-ensemble, i.e., au choix
d’un ensemble non vide d’arbres, avec répétitions possibles.
En d’autres termes, un nœud a, non pas une suite ordonnée, mais un ensemble (fini)
d’enfants (figure 1.11).
Définition 1.14 Soit R la relation d’équivalence sur l’ensemble P des arbres
planaires engendrée par la relation binaire suivante : deux arbres planaires τ et τ
sont en relation si l’on peut passer de l’un à l’autre en permutant les sous-arbres
d’un même nœud. L’ensemble Pó des arbres de Pólya est l’ensemble des classes
d’équivalence de P pour la relation R.
En toute rigueur, ces deux définitions ne sont pas équivalentes (une classe
d’équivalence n’est pas une classe combinatoire). Cependant, si nous nous limitons
dans la définition 1.14 à des arbres finis, elles définissent des ensembles isomorphes,
puisque l’ensemble des classes d’équivalence de la définition 1.14 est bien la classe
combinatoire des arbres de Pólya au sens de la définition 1.13.
Fig. 1.11 Deux représentations planaires d’un même arbre de Pólya