142
4 Approche combinatoire
L’équation de récurrence (4.21) sur le paramètre v(τ ) se traduit en une équation sur
sa fonction génératrice :
V (z) =
τ ∈F
r(τ )z
|τ |
+
τ ∈F
τ i sous-arbre de la racine
v(τ i )z
|τ |
= R(z) +
k≥0
τ =(◦,τ 1 ,...,τ k )
(v(τ 1 ) + · · · + v(τ k ))z
1+|τ 1 |+···+|τ k |
= R(z) + z
k≥0
k
τ =(◦,τ 1 ,...,τ k )
v(τ 1 )z
|τ 1 |+···+|τ k |
= R(z) + z
k≥0
k σ k V (z)F (z)
k−1
= R(z) + z V (z) S
(F (z)).
Cette dernière équation nous permet d’obtenir
V (z) =
R(z)
1 − zS (F (z))
,
que nous pouvons aussi écrire uniquement avec la fonction F (z) : en dérivant la
relation F (z) = z S(F (z)), nous obtenons
V (z) = R(z)
z F (z)
F (z)
.
Au voisinage de z = ρ, il suffit maintenant de reporter le développement de F (z)
obtenu ci-dessus (cf. l’équation (4.20)) pour obtenir un développement de Taylor
de V (z), qui dépend naturellement du comportement de R(z) en ρ. Nous pouvons
alors obtenir l’équivalent asymptotique de [z n ]V (z) pour n → +∞, et donc du coût
moyen du paramètre v sur un arbre de taille n ; c’est la proposition suivante.
Proposition 4.8 Soit F une famille simple d’arbres définie par un ensemble
de symboles S ayant pour fonction génératrice S(z) et ayant elle-même pour
fonction génératrice F (z). Soit v un paramètre additif sur la famille F , défini par
l’équation (4.21) et de fonction génératrice cumulée V (z) ; soit également R(z) la
fonction génératrice de r, le péage à la racine. Alors, sous le modèle de Catalan sur
les arbres de taille n, la valeur moyenne du paramètre v est
E[v(τ n )] =
[z n ]R(z)
z F (z)
F (z)
[z n ]F (z)
.