328
7 Arbres digitaux
Finalement nous avons établi, pour n → +∞,
E n [h] = 2 log 2 n + O(log 2 log n),
ce qui implique le résultat énoncé dans la proposition.
Méthode analytique avancée (point col) Avec (beaucoup) plus de
soin, des résultats plus précis que celui de la proposition 7.41 sur la hauteur
moyenne du trie avec source binaire sans mémoire non biaisée peuvent
être obtenus. L’équation (7.16) donne aussi une expression de la probabilité
q n,k := P n (h ≤ k) qu’un trie soit de hauteur inférieure ou égale à k comme le
coefficient en z n d’une série génératrice :
q n,k =
n!
2 nk [z
n
] (1 + z)
2 k
.
Cette expression se prête naturellement à un traitement par méthode de col du
fait qu’il apparaît une puissance d’une fonction analytique. Le point de départ
est la formule de Cauchy pour l’extraction de coefficients
[z
n
]f (z) =
1
2iπ
f (z)
dz
z n+1 ,
(7.39)
où est un chemin simple direct entourant l’origine, que nous écrivons sous
la forme
[z
n
]f (z) =
1
2iπ
e
h(z) dz.
L’heuristique de la méthode de col consiste à choisir pour un chemin qui
passe par un point col de h(z), i.e., un point ξ tel que h (ξ ) = 0.
Pour une intégrale du type de (7.39) avec f une série entière dépendant
d’un paramètre k et un cercle centré sur l’origine et passant par le point col
de plus petit module, la contribution principale à l’intégrale provient d’une
petite partie du contour dans un voisinage du point col. Un développement
local de la fonction permet alors d’approximer l’intégrale. Nous renvoyons à
Flajolet et Sedgewick [94, Ch. VIII] pour plus de détails et d’intuitions.
Finalement, après des calculs qui seraient longs à détailler ici, une
approximation de q n,k obtenue par la méthode du col permet d’obtenir le
théorème suivant (voir Flajolet et Steyaert [96] ou Flajolet [79]).
(tsvp)