294
7 Arbres digitaux
Fig. 7.3 Pour un alphabet binaire A = {0, 1}, un trie binaire aléatoire dans le modèle infini i.i.d.
pour n = 100 mots (hauteur 16, longueur de cheminement externe 1323, nombre de nœuds internes
222). Nous avons omis les étiquettes sur les branches
symbole 1 et est égale à 1/2 (voir la figure 7.3). Nous allons retrouver l’analogue
des lemmes 7.3, 7.4 et 7.7.
Nous définissons la série génératrice exponentielle
v(z) =
∞
n=0
v n
z n
n!
.
Les séries génératrices pour des cas particuliers importants, correspondant à ceux
déjà vus pour le modèle fini, sont rassemblées dans la troisième colonne de la
table 7.1. Par exemple, pour v n = 1 pour n ≥ 0, la série s’écrit
v(z) =
n≥0
z n
n!
= e
z .
De même que dans le cas fini, nous établissons un lemme de traduction pour des
relations simples sur les paramètres.
Lemme 7.10 (Traduction – modèle infini i.i.d. uniforme) Le dictionnaire suivant donne une traduction, pour b et c des paramètres de trie, en termes de séries
génératrices associées :
Paramètre
Série génératrice
λb(ω), λ ∈ R
λ b(z)
b(ω) + c(ω)
b(z) + c(z)
b(ω \ 0) c(ω \ 1) b(
z
2 ) c(
z
2 )