4.3 Tas
153
Proposition 4.13 Lorsque n → +∞, le nombre f n = log(n!/t n ), où t n est le
nombre de tas de taille n, est tel que
f n = c n + O(log
2 n),
avec c =
k≥1
log(2 k −1)
2 k
= 0,9457553022 . . .
Cette proposition, couplée à la formule de Stirling pour n!, entraîne lorsque n →
+∞ que
log t n = n log n − (c + 1)n + O(log
2 n),
ce qui ne fournit cependant pas un équivalent asymptotique de t n : le terme d’erreur
est d’ordre n log n . Il faut donc affiner l’approche ci-dessus pour obtenir le résultat
suivant (cf. [138]).
Théorème 4.14 Le nombre de tas de taille n vaut asymptotiquement, pour n →
+∞,
t n = λ P (log 2 n) R(n) n
n+3/2 e
−μn
1 + O
1
n
,
où les constantes λ et μ valent respectivement
λ = 2
√
2π
j ≥1
(1 − 2
−j ) = 1,447768809 . . .
μ = 1 + 2 log 2 +
j ≥1
2
−j log(1 − 2
−j ) = 1,945755302 . . .
et où, {r} désignant la partie fractionnaire du réel r :
P (r) = 2
2 {r} −{r}
0≤j ≤r
2 {2 r−j }
1 + {2 r−j }
;
R(n) =
L
j =1
1 − 2 −j −1
1 − 2 −j
{n/2 j }
.
La démonstration de ce théorème, bien que ne faisant appel qu’à des notions
mathématiques relativement élémentaires, est techniquement compliquée, et nous
renvoyons au problème 4.17 de la Section 4.6, pour quelques indications.