4.1 Les arbres binaires
133
Le théorème suivant récapitule les résultats obtenus sur le comportement de la
longueur de cheminement dans un arbre binaire sous le modèle de Catalan.
Théorème 4.5
i) Si τ n est un arbre binaire choisi selon la loi uniforme parmi les arbres de taille n,
sa longueur de cheminement moyenne vaut
E[lc(τ n )] = (4
n /C n ) − (3n + 1)
= n
√
π n − 3n + (9/8)
√
πn − 1 + O
1
√
n
.
ii) Sous ce même modèle, la variance de la longueur de cheminement est
σ
2 (lc(τ n )) =
10
3
n
3
+9 n
2
+
23
3
n+2−
(n + 1) (n + 2)
2
4 n
2n
n
−(n+1)
2
4 n
2n
n
2
.
Elle vaut asymptotiquement
σ
2 (lc(τ n )) =
10 − 3π
3
n
3
+ O
n
2 √
n
= 0,191740649 . . .n
3
+ O
n
2 √
n
.
4.1.3 Paramètres additifs
L’approche que nous avons utilisée pour étudier la longueur de cheminement des
arbres binaires s’étend à d’autres paramètres de ces arbres, à condition qu’ils
satisfassent une relation de récurrence analogue à la relation (4.7), i.e., de la forme
suivante pour une fonction r convenable :
v(τ ) = r(τ ) + v(τ
(g) ) + v(τ
(d) ).
Or une telle équation n’est autre que l’équation (1.10), et caractérise ce nous avons
appelé dans la section 1.3.2 un paramètre additif avec r désignant le péage à la
racine ; cf. la définition 1.48 où nous avons défini ce qu’est un paramètre additif
associé à une fonction de péage.
Dans la présente section, nous nous penchons sur une manière d’obtenir systématiquement la fonction génératrice V (z) =
n≥0 v n z n du paramètre v cumulé
sur tous les arbres de taille n : v n :=
τ ∈C,|τ |=n v(τ ). Cette fonction s’écrit aussi
V (z) =
τ ∈C v(τ )z τ , et s’exprime simplement à partir de la fonction génératrice