298
7 Arbres digitaux
Fig. 7.4 Courbes représentant respectivement E n [S]/n à gauche et (E n [S] + 1)/n à droite. Les
oscillations observées sont très petites et pour les mettre en évidence nous devons prendre en
compte, en retranchant −1, le terme constant du développement asymptotique de E n [S]
À nouveau, en itérant puis par extraction de coefficient, nous obtenons les expressions
(z) =
k≥0
z
e
z
− e
z
1−
1
2 k
,
E n [] = n![z
n
] = n
k≥0
1 −
1 −
1
2 k
n−1
.
(7.15)
Là encore ces expressions sont exactes, mais une étude asymptotique est nécessaire
pour avoir une idée du comportement.
Hauteur d’un trie L’expression sous forme de produit de l’équation (7.6) χ k (ω) =
1 {h(ω)≤k} = χ k−1 (ω \ 0)χ k−1 (ω \ 1) conduit à la famille de séries génératrices
χ k (z) =
n≥0
E n [χ k ]
z n
n!
.
Notons que dans cette expression E n [χ k ] est l’espérance d’une fonction caractéristique et donc rien d’autre que la probabilité que le trie soit de hauteur inférieure ou
égale à k. D’après le lemme 7.10, nous calculons
χ k (z) =
χ k−1 (z/2)
2
= · · · =
χ 0 (z/2
k )
2 k = (1 + z/2
k )
2 k
.