100
3 Arbres, algorithmes et données
3241 3214
321
4231
4213 2413
4312 3412 3142
312
1432
1
21
12
4321
2143
231
213
132
1
3
4
2
1
2
4
3
4132
Fig. 3.26 L’arbre de génération pour les permutations évitant le motif 123, tronqué à la quatrième
génération
2
3
2
4
2
3
3
2
5
2
3
4
3
2
4
2
3
4
2
3
3
2
Fig. 3.27 L’arbre de génération de la figure 3.26, dans lequel chaque nœud est marqué par le
nombre de ses enfants
Nous l’avons vu sur l’exemple des permutations excluant le motif 123, et cela
est plus général : l’arbre de génération encode le mécanisme, en fait le système
de réécriture, qui permet de passer d’un objet de taille donnée à un objet de taille
immédiatement supérieure. Une information importante est le nombre d’enfants par
nœud ; si nous marquons chaque nœud par le nombre de ses enfants, nous obtenons
l’arbre de la figure 3.27.
Continuons l’exemple des permutations à motif exclu 123, et regardons le
système de réécriture associé : il indique comment passer d’un niveau à un autre,
en précisant, pour chaque nœud, quels sont les marques de ses enfants. Nous
commençons par un « axiome » noté (2), indiquant que la racine a deux fils. Passant
aux niveaux suivants, si un nœud est marqué k, il est possible de montrer (cf.
West [249]) que ses k fils sont eux-mêmes d’arités respectives (toutes distinctes)
k + 1, 2, 3, . . . , k ; en réordonnant les sous-arbres nous obtenons la règle de
réécriture
(k) → (2) (3) · · · (k − 1) (k) (k + 1).