320
7 Arbres digitaux
Fig. 7.7 Schéma pour la formule de Nörlund-Rice avec σ 0 = 1. Le contour d’intégration
entourant les pôles en les points de {2, 3, . . . , n} est déformé pour se ramener à l’intégrale sur
une droite verticale qui donne la formule de Nörlund-Rice. Enfin le contour est refermé sur la
gauche avec la courbe 2 représentée ici par une droite à l’intérieur du domaine R à gauche de
(s) = σ 0 , afin d’obtenir une formule de résidu et un terme d’erreur
Revenons maintenant à l’étude des paramètres de trie. Pour appliquer la proposition 7.36, nous cherchons d’abord des expressions adaptées à la formule de
Nörlund-Rice pour la taille et la longueur de cheminement externe d’un trie
aléatoire.
– Taille d’un trie. Le péage est γ (k) = 1 {k≥2} et nous avons déjà calculé la série de
Poisson γ (z) = 1 − e −z (1 + z). Nous appliquons facilement (7.33) à cette série
pour obtenir
ϕ(k) = k − 1.
En utilisant la proposition 7.36 nous obtenons
E n [S] =
k≥2
(−1)
k
n
k
(k − 1)
w∈A
∗
p
k
w .
– Longueur de cheminement externe d’un trie. Toujours en utilisant (7.33) et
pour le péage γ (k) = k 1 {k≥2} , nous calculons la série de Poisson γ (z) =
z(1 − e −z ), d’où nous déduisons facilement ϕ(k) = k. Après application de
la proposition 7.36, nous obtenons
E n [] =
k≥2
(−1)
k
n
k
k
w∈A
∗
p
k
w .