4.3 Tas
151
4.3.2 Dénombrement asymptotique des tas
D’après la formule d’équerre appliquée aux tas (4.22), nous savons que n!/t n est un
entier. Posons
f n = log(n!/t n ).
A partir de la récurrence multiplicative sur les t n , nous obtenons tout d’abord une
récurrence additive sur les f n , qui prend deux formes différentes suivant que j =
n − 2 L est plus petit, ou au contraire plus grand, que 2 L−1 :
f 2 L +j =
log(2 L + j ) + f 2 L−1 −1 + f 2 L−1 +j (0 ≤ j ≤ 2 L−1 − 1);
log(2 L + j ) + f 2 L −1 + f L
(2 L−1 ≤ j ≤ 2 L − 1).
Remarquons que les termes f 2 L−1 +j et f j (à l’exception de f 2 L −1 lorsque n =
2 L+1 − 1) correspondent à des sous-arbres spéciaux (définis en 4.3.1), et que tous
les autres termes correspondent à des sous-arbres dont la forme est un arbre saturé.
Appliquons maintenant la formule (4.22) à un tas construit sur l’arbre parfait τ
de taille n, et réécrivons-la en
t n =
n!
L
k=1
2 k − 1
ν k .
L−1
p=0 s p
,
où ν k (nombre de sous-arbres saturés de τ de taille 2 k − 1) et s p (tailles, toutes
différentes, des sous-arbres spéciaux de τ ) sont donnés par la proposition 4.11.
Nous la transformons facilement en
f n = log
n!
t n
= S 1 + S 2 ,
avec
S 1 =
L
k=1
log(2
k
− 1) ν k ;
S 2 =
L−1
p=0
log s p .
Nous allons étudier séparément chacune des deux sommes. Dans ce qui suit, {x}
désigne la partie fractionnaire d’un réel x.
(i) La contribution principale viendra de S 1 : nous réécrivons d’abord
ν k =
n
2 k −
n
2 k−1
+
n
2 k
− 1.