122
4 Approche combinatoire
combinatoire C des arbres binaires vérifie (cf. la définition 1.11) l’équation récursive
C = E + (◦ × C × C).
(4.1)
où ◦ est un nœud de l’arbre et E est la classe neutre qui contient uniquement l’arbre
vide. L’ensemble des arbres binaires de taille n est muni de la loi uniforme, notée
P n , qui est aussi ce que nous appelons « loi du modèle de Catalan ».
La démarche suivie au long de cette section est la suivante : une quantité (nombre
d’arbres de taille n, longueur de cheminement d’un arbre de taille n, etc.) obéit à
une relation de récurrence, de sorte que la fonction génératrice associée est solution
d’une équation. Lorsque l’équation se résout explicitement, le coefficient d’ordre
n de la fonction peut être extrait directement. Sinon, sous des hypothèses souvent
vérifiées, l’asymptotique de ce coefficient est obtenue en utilisant un outil puissant
de combinatoire analytique appelé lemme de transfert (cf. annexe B.3.6).
4.1.1 Dénombrement
La première question qui se pose est de compter le nombre d’arbres binaires de
taille n ; soit C n ce nombre. Nous obtenons facilement les premières valeurs (cf. la
figure 4.1) : C 0 = 1, C 1 = 1, C 2 = 2, C 3 = 5, C 4 = 14, etc.
En décomposant l’ensemble des arbres de taille n ≥ 1 suivant la taille k du sousarbre gauche, qui varie de 0 à n − 1, nous obtenons une relation de récurrence sur la
suite (C n ) n≥0 :
C n =
n−1
k=0
C k C n−k−1 .
(4.2)
Une technique efficace pour résoudre cette relation est de passer par la fonction
C(z) :=
n≥0
C n z
n ,
appelée la fonction génératrice de la suite (C n ). Remarquons que nous pouvons
aussi écrire
C(z) =
τ ∈C
z
|τ | .
Nous verrons, selon les besoins de notre étude, ces objets tantôt comme séries
formelles, tantôt comme fonctions d’une variable complexe. Ainsi, en considérant
C(z) comme une série formelle, prendre son carré et regrouper les termes de même
4 Approche combinatoire
combinatoire C des arbres binaires vérifie (cf. la définition 1.11) l’équation récursive
C = E + (◦ × C × C).
(4.1)
où ◦ est un nœud de l’arbre et E est la classe neutre qui contient uniquement l’arbre
vide. L’ensemble des arbres binaires de taille n est muni de la loi uniforme, notée
P n , qui est aussi ce que nous appelons « loi du modèle de Catalan ».
La démarche suivie au long de cette section est la suivante : une quantité (nombre
d’arbres de taille n, longueur de cheminement d’un arbre de taille n, etc.) obéit à
une relation de récurrence, de sorte que la fonction génératrice associée est solution
d’une équation. Lorsque l’équation se résout explicitement, le coefficient d’ordre
n de la fonction peut être extrait directement. Sinon, sous des hypothèses souvent
vérifiées, l’asymptotique de ce coefficient est obtenue en utilisant un outil puissant
de combinatoire analytique appelé lemme de transfert (cf. annexe B.3.6).
4.1.1 Dénombrement
La première question qui se pose est de compter le nombre d’arbres binaires de
taille n ; soit C n ce nombre. Nous obtenons facilement les premières valeurs (cf. la
figure 4.1) : C 0 = 1, C 1 = 1, C 2 = 2, C 3 = 5, C 4 = 14, etc.
En décomposant l’ensemble des arbres de taille n ≥ 1 suivant la taille k du sousarbre gauche, qui varie de 0 à n − 1, nous obtenons une relation de récurrence sur la
suite (C n ) n≥0 :
C n =
n−1
k=0
C k C n−k−1 .
(4.2)
Une technique efficace pour résoudre cette relation est de passer par la fonction
C(z) :=
n≥0
C n z
n ,
appelée la fonction génératrice de la suite (C n ). Remarquons que nous pouvons
aussi écrire
C(z) =
τ ∈C
z
|τ | .
Nous verrons, selon les besoins de notre étude, ces objets tantôt comme séries
formelles, tantôt comme fonctions d’une variable complexe. Ainsi, en considérant
C(z) comme une série formelle, prendre son carré et regrouper les termes de même