7.2 Analyses asymptotiques
327
La probabilité q n,k 1 est donc exponentiellement petite en n, ce qui établit pour
n → +∞,
S 1 = H (n) + O(log 2 log n).
(ii) Comme nous ne cherchons que le terme dominant pour la hauteur, nous
obtenons trivialement
S 2 = O(Card(I 2 )) = O(log 2 log n).
(iii) Enfin, pour k ∈ I 3 , posons m = k − H (n) − −log 2 log n ≥ 0. Nous allons
établir d’abord que, pour n → +∞,
1 − q n,k = O
2 −m
log n
.
En effet, nous avons bien
n
2 k = O
1
log n
pour k ∈ I 3 . Le développement
limité de log(1 − x) = −x + O(x 2 ) pour x → 0, donne pour n, k → +∞,
log q n,k = −
n−1
j =1
j
2 k + O
n 3
2 2k
= −
n(n − 1)
2 k
(1 + o(1)).
En substituant 2 log 2 n + +log 2 log n + m à k, nous avons
n 2
2 k = O(
1
2 m log n ).
En conclusion nous obtenons pour k ∈ I 3
q n,k = exp
O
1
2 m log n
et 1 − q n,k = O
1
2 m log n
.
Nous en déduisons que
S 3 =
k∈I 3
1 − q n,k
=
K
log n
m≥0
1
2 m =
2K
log n
,
pour une certaine constante K.