7.1 Analyses exactes
291
Longueur de cheminement externe des tries D’après l’équation (7.3) pour le
paramètre (ω), le péage γ (ω) associé à ω est maintenant égal au cardinal de ω
s’il est supérieur ou égal à 2 et à zéro si ω est vide ou réduit à un singleton :
γ (ω) = |ω| 1 {|ω|≥2} = |ω| − 1 {|ω|=1} .
Nous obtenons donc
γ
(d) (z) = 2
d z(1 + z)
2 d −1
− 2
d z = 2
d z
(1 + z)
2 d −1
− 1
,
et le lemme 7.4 fournit la série génératrice pour le paramètre défini en (7.3) de la
longueur de cheminement externe
(d) (z) = 2
d (1 + z)
2 d
d
j =0
z
(1 + z) 2 j −1 − 1
(1 + z) 2 j
= 2
d (1 + z)
2 d
d
j =0
z
1
1 + z
−
1
(1 + z) 2 j
.
Nous obtenons à nouveau des valeurs exactes pour d fixé (cf. l’exercice 7.1).
Remarque 7.8 Nous pouvons extraire les coefficients et nous obtenons
E
(3)
n [] =
1
2 d
n
2
d
d
j =0
2 d −1
n−1
−
2 d −2 d−j
n−1
= n
d
j =0
1 −
(2 d (1 − 2 −j ))!((2 d − 1) − (n − 1))!
(2 d − 1)!(2 d (1 − 2 −j ) − (n − 1))!
.
Nous remarquons que pour n et j fixés, nous pouvons calculer la limite de chaque
terme lorsque d → ∞
lim
d→∞
2 d (1 − 2 −j )
!
(2 d − 1) − (n − 1)
!
(2 d − 1)!
2 d (1 − 2 −j ) − (n − 1)
!
=
1 − 2
−j
n−1
,
ce qui est, nous le verrons dans la section suivante, la quantité intervenant
dans (7.15) pour l’espérance dans le modèle i.i.d. uniforme (avec des clés infinies).
Notons qu’un calcul similaire est possible pour l’espérance de la taille, et que là
encore la « limite » de l’expression de l’espérance de la taille dans le modèle fini
équiprobable pour n mots de longueur d tend vers celle du modèle i.i.d. uniforme
lorsque que d tend vers +∞ pour n fixé.