330
7 Arbres digitaux
Hauteur d’un trie avec une source générale Les techniques pour
obtenir la hauteur asymptotique dans le cas d’une source générale sont
similaires. Posons
k (z) =
w∈A
k
(1 + zp w ) .
Appliquons la formule de Cauchy pour obtenir le coefficient
p n,k = n![z
n
] k (z) =
n!
2iπ
k (z)
dz
z n+1 ,
où est un contour simple direct entourant l’origine. Assez grossièrement,
car l’objectif de ce paragraphe est de montrer de quelle manière le résultat
précédent se généralise mais sans l’établir formellement, l’idée pour évaluer
p n,k est d’appliquer une transformation « exp-log » à k (z) puis de considérer
le développement limité de log(1 + x) = x −
x 2
2 + O(x 3 ) quand x → 0. Ceci
nous donne
k (z) = exp
w∈A
k
log(1 + zp w )
= exp
⎛
⎝ z
w∈A
k
p w −
z 2
2
w∈A
k
p
2
w + O(z
3 p
3
w )
⎞
⎠ .
Nous obtenons l’approximation suivante, lorsque n → +∞ et pour k
logarithmique en n dans une « bonne » fenêtre (du même type que celle de
l’équation (7.41)) autour de la hauteur moyenne :
p n,k ∼
n!
2iπ
exp
⎛
⎝ −
z 2
2
w∈A
k
p
2
w
⎞
⎠
e z dz
z n+1 .
Cette dernière expression peut être envisagée comme une perturbation de
l’intégrale de Cauchy pour e z . La méthode de col s’applique alors pour fournir
(tsvp)