7.1 Analyses exactes
295
Preuve Les deux premières lignes se prouvent directement par linéarité et additivité
sur la définition de la série génératrice. Pour la troisième ligne, considérons un
paramètre v(ω) = b(ω \ 0) c(ω \ 1) avec b et c deux paramètres. L’espérance
v n = E n [v] se décompose en considérant les sous-tries issus de la racine (disons
avec k clés ou mots à gauche et n−k clés à droite) à l’aide des espérances b k = E k [b]
et c n−k = E n−k [c]. La probabilité que k mots parmi n commencent par la lettre 0
est exactement
n
k
/2 n . Ainsi nous obtenons
v n =
n
k=0
1
2 n
n
k
b k c n−k =
n
k=0
n!
k!(n − k)!
b k
2 k
c n−k
2 n−k .
Cela conduit à
v(z) =
n≥0
v n
z n
n!
=
n≥0
n
k=0
b k (z/2) k
k!
c n−k (z/2) n−k
(n − k)!
= b(z/2) c(z/2).
Afin d’illustrer ce lemme, examinons le cas particulier important de deux paramètres
de tries a et b qui vérifient a(ω) = b(ω \ 0) (le paramètre a est égal au paramètre b
sur le sous-trie gauche). La série génératrice associée est
a(z) = e
z/2 b(z/2).
Un autre cas particulier important correspond au cas d’un paramètre additif qui
s’écrit
v(ω) = γ (ω) + v(ω \ 0) + v(ω \ 1),
nous obtenons alors
v(z) = γ (z) + 2e
z/2
v(z/2).
(7.12)
Remarque 7.11 L’équation (7.12) permet de calculer exactement, par récurrence
sur n, la valeur numérique de v n , l’espérance du paramètre v pour un nombre n de
mots dans le trie. En effet nous écrivons v n = E n [v] = n![z n ]v(z). Or nous avons
n![z
n
]2e
z/2
v(z/2) =
2
2 n
n
k=0
n
k
v k .