166
4 Approche combinatoire
qui a entre 1 et 2m clés. Pour une hauteur h ≥ 1, le nombre de clés de la racine
détermine son nombre d’enfants, qui varie entre 2 et 2m + 1 ; les racines de ces
enfants ont un nombre de clés compris entre m et 2m et chacun des sous-arbres peut
prendre c h−1 valeurs distinctes, d’où
b h = c
2
h−1 + · · · + c
2m+1
h−1 = c
2m+1
h−1
1 +
1
c h−1
+ · · · +
1
c
2m−1
h−1
.
Quant à la suite c h , il est aisé de voir par le même raisonnement que c 0 = m + 1 et
qu’elle vérifie la relation de récurrence
c h+1 = c
m+1
h
+ · · · + c
2m+1
h
= c
2m+1
h
1 +
1
c h
+ · · · +
1
c m
h
.
(4.25)
De manière similaire à ce que nous avons fait pour les arbres 2–3, nous établissons
d’abord une minoration pour c h . Définissons x 0 = m + 1 et, pour h ≥ 1, x h+1 =
x
2m+1
h
; pour chaque h, x 0 ≤ c h et x h = (m + 1) (2m+19 h , d’où la relation
c h ≥ (m + 1)
(2m+1) h
.
(4.26)
Nous posons ensuite v h = c
1
(2m+1) h
h
; donc ν 0 = c 0 = m + 1. La relation (4.25) peut
se récrire en
c h+1 = ν
(2m+1) h+1
h+1
= ν
(2m+1) h+1
h
1 +
1
c h
+ · · · +
1
c
m
h
,
ce qui donne
v h+1
v h
=
1 +
1
c h
+ · · · +
1
c
m
h
1
(2m+1) h+1
.
Comme la série
1
(2m + 1) log
1 +
1
c
+ · · · +
1
c m
est de même nature que la série
1
(2m + 1)
1
c