290
7 Arbres digitaux
où les fonctions α d et β d sont connues, et v (0) (z) = β 0 (z). La série a alors pour
expression
v
(d) (z) =
d
j =0
⎛
⎝ β j (z)
d
k=j +1
α j (z)
⎞
⎠ .
Taille d’un trie Pour appliquer le lemme 7.4, nous considérons la fonction de
péage obtenue à partir de (7.2)
γ (ω) = 1 − 1 {|ω|=0} − 1 {|ω|=1} .
Nous calculons donc pour d ≥ 0
γ
(d) (z) = (1 + z)
2 d − 1 − 2
d z,
ce qui donne d’après le lemme d’itération 7.4
S
(d) (z) = 2
d (1 + z)
2 d
d
j =0
(1 + z) 2 j − 1 − 2 j z
2 j (1 + z) 2 j
= 2
d (1 + z)
2 d
d
j =0
1
2 j
1 −
1 + 2 j z
(1 + z) 2 j
.
L’expression est un peu compliquée mais reste finie et calculable automatiquement
à l’aide d’un logiciel de calcul formel pour d fixé. Par exemple pour d = 3 nous
obtenons
S
(3) (z) = 7 z
8
+ 48 z
7
+ 144 z
6
+ 240 z
5
+ 236 z
4
+ 136 z
3
+ 44 z
2 .
Avec du courage, nous pouvons vérifier ces valeurs numériques en examinant un à
un les arbres de la figure 7.2 : il y a bien 7 tries de taille 8, 48 tries de taille 7, etc.
Ce polynôme permet de calculer la valeur moyenne de la taille d’un trie à n clés,
E
(3)
n [S] =
[z n ]S (3) (z)
(
8
n )
, pour les premières valeurs de n :
n
2
3
4
5
6
7 8
E
(3)
n [S]
11
7
17
7
118
35
30
7
36
7
6 7
≈ 1,571 ≈ 2,428 ≈ 3,371 ≈ 4,285 ≈ 5,143