4.2 Familles simples d’arbres
141
Théorème 4.7 Soit une famille simple d’arbres définie par un ensemble de symboles S ayant pour fonction génératrice S(z). Supposons que S ne soit pas linéaire,
et que sur le disque ouvert de convergence de S, il existe une unique solution positive
de l’équation
ξS
(ξ ) = S(ξ).
Alors, le nombre f n d’arbres de taille n de cette famille vaut asymptotiquement
f n =
S(ξ)
2 π S
(ξ )
ρ
−n n
−3/2 (1 + O(1/n)) ,
où ξ et ρ sont les uniques éléments de R + solutions du système
ρS(ξ) = ξ
ρS (ξ ) = 1.
4.2.4 Paramètres additifs sur les familles simples d’arbres
Les paramètres additifs que nous avons définis en Section 1.3.2 (cf. la définition 1.48) pour des familles générales d’arbres, puis rencontrés sur les arbres
binaires sous le modèle de Catalan en section 4.1.3, sont bien entendu pertinents
pour les familles simples d’arbres. Soit F une telle famille, et soit v un paramètre
additif associé à r, le péage à la racine ; alors pour tout arbre τ ∈ F nous pouvons
écrire
v(τ ) = r(τ ) +
τ i sous-arbre de la racine
v(τ i ).
(4.21)
Nous venons de consacrer les trois sections précédentes à l’analyse de la fonction
de dénombrement F (z) =
τ ∈F z |τ | associée à une famille simple donnée.
Introduisons maintenant la fonction génératrice du paramètre cumulé sur tous les
arbres :
V (z) :=
τ ∈F
v(τ )z
|τ | .
Sous le modèle de Catalan – rappelons que tous les arbres de taille donnée sont alors
équiprobables – le coût moyen de v sur un arbre aléatoire τ n de taille n sera
E[v(τ n )] =
[z n ]V (z)
[z n ]F (z)
.