7.1 Analyses exactes
289
Un exemple d’un tel paramètre serait par exemple la taille du sous-trie gauche en
prenant b(ω) = S(ω).
Un cas particulier important est celui des paramètres additifs de trie qui font
intervenir une fonction de péage et pour lequel nous avons le lemme suivant.
Lemme 7.4 (Paramètres additifs – cas fini équiprobable) Considérons un
paramètre additif s’exprimant sous la forme
v(ω) = γ (ω) + v(ω \ 0) + v(ω \ 1),
où γ est lui-même un paramètre de l’arbre appelée fonction de péage. 3 Alors les
séries génératrices des paramètres v et γ satisfont l’équation fonctionnelle pour
d ≥ 1
v
(d) (z) = γ
(d) (z) + 2 (1 + z)
2 d−1
v
(d−1) (z).
(7.8)
Nous avons v (0) (z) = γ (0) (z) et pour d ≥ 1
v
(d) (z) = 2
d (1 + z)
2 d
d
j =0
γ (j ) (z)
2 j (1 + z) 2 j .
Preuve Par itération, nous déduisons de (7.8) l’expression
v
(d) (z) =
d
j =0
γ
(j ) (z)
d−1
k=j
2(1 + z)
2 k
,
à partir de laquelle nous obtenons la formule voulue après quelques simplifications.
Remarque 7.5 Le paramètre v comme la fonction de péage γ , s’ils correspondent
à des paramètres de trie, doivent être nuls pour tout ensemble de cardinal inférieur
strictement à deux (par définition du trie).
Remarque 7.6 Nous énonçons ci-après un lemme plus général sur les séries
génératrices. Sa preuve repose sur une manipulation élémentaire des suites.
Lemme 7.7 (Itération – cas fini équiprobable) Soit une série génératrice
cumulée v (d) (z) définie par
v
(d) (z) = α d (z)v
(d−1) (z) + β d (z) (d ≥ 1),
3 Pour les tries, dans les analyses usuelles de la longueur de cheminement externe et de la taille,
cette fonction dépend seulement du cardinal |ω|.