150
4 Approche combinatoire
Il apparaît clairement que cette manière de faire, si elle peut permettre d’obtenir une
expression close pour certaines tailles de termes, par exemple t 2 k+1 ±j pour j fixé
et « petit », ne sera guère généralisable et ne permettra sans doute pas d’obtenir t n
pour n quelconque. Nous allons maintenant, en suivant une approche due à Hwang
et Steyaert [138], reprendre l’expression de t n donnée par la formule (4.22) et en tirer
d’abord une relation de récurrence, ce qui nous permettra dans un second temps (cf.
la section 4.3.2) d’obtenir son comportement asymptotique.
Établissons une récurrence sur la taille d’un tas : il est clair que les tailles de la
forme 2 k −1, qui correspondent à des arbres saturés, jouent un rôle particulier. Nous
écrivons n sous la forme
n = 2
L
+ j
avec
L = =log 2 n
0 ≤ j ≤ 2
L
− 1.
Nous pouvons alors obtenir une récurrence multiplicative sur les t n :
– Si 0 ≤ j ≤ 2 L−1 − 1, le sous-tas de droite est plein et de taille 2 L−1 − 1, celui
de gauche est de taille 2 L−1 + j < 2 L , et
t 2 L +j =
2 L + j − 1
2 L−1 − 1
t 2 L−1 −1 t 2 L−1 +j .
– Si 2 L−1 ≤ j ≤ 2 L − 1, alors c’est le sous-tas de gauche qui est plein, de taille
2 L − 1, et le sous-tas de droite est de taille j , d’où
t 2 L +j =
2 L + j − 1
2 L − 1
t j t 2 L −1 .
Nous avons maintenant un outil pour calculer numériquement, et relativement
facilement, les premières valeurs de t n ; cf. la table de la figure 4.8.
Fig. 4.8 Nombre t n de tas
de taille donnée n ≤ 15