288
7 Arbres digitaux
Table 7.1 Traduction de quelques paramètres fréquemment rencontrés dans les analyses de tries
dans le modèle fini équiprobable pour la longueur d (définition 2.16) et dans le modèle infini i.i.d.
uniforme (définition 2.17)
Paramètre
modèle fini équiprobable
modèle infini i.i.d. uniforme
v(ω)
v (d) (z)
v(z)
1
(1 + z) 2 d
e z
1 {|ω|=p}
2 d
p
z p
z p
p!
|ω|
2 d z(1 + z) 2 d −1
ze z
La dernière colonne résulte de la section 7.1.2
Cette description se traduit directement par la série génératrice
γ
(d) (z) = (1 + z)
2 d −
2 d
0
−
2 d
1
z = (1 + z)
2 d − 1 − 2
d z.
Le lemme ci-après permet de passer d’une description récursive d’un paramètre
à une équation fonctionnelle sur les séries génératrices.
Lemme 7.3 (Traduction – modèle fini équiprobable) Soit b et c deux paramètres
de trie. Dans le modèle fini équiprobable sur B (d) , les opérations sur les paramètres
b et c en termes de séries génératrices cumulées (respectivement notées b (d) (z) et
c (d) (z)) se traduisent grâce au dictionnaire :
Paramètre
Série génératrice
λb(ω), λ ∈ R
λb (d) (z)
b(ω) + c(ω)
b (d) (z) + c (d) (z)
b(ω \ 0) c(ω \ 1) b (d−1) (z) c (d−1) (z) (si d ≥ 1)
La preuve de ce lemme ne présente pas de difficulté et nous la laissons à la
lectrice/au lecteur.
Comme illustration de ce lemme, considérons par exemple deux paramètres a et
b tels que le paramètre a est égal à la valeur de b sur son sous-arbre gauche. Ainsi
nous avons
a(ω) = b(ω \ 0).
Introduisant la fonction 1 qui vaut identiquement 1, nous écrivons
a(ω) = b(ω \ 0) 1(ω \ 1).
L’application du lemme 7.3 donne alors l’expression pour d ≥ 1
a
(d) (z) = b
(d−1) (z) (1 + z)
2 d−1
.