8.2 Arbres quadrants de recherche
367
avec Y (t) une série entière en t. Nous trouvons après quelques calculs que
Y (t) =
i≥0
α
i
α − 1
i
t
i ,
ce qui donne
y(t) =
1
(1 − t) α
i≥0
α
i
α − 1
i
t
i
;
α = 2
√
z.
Après encore quelques calculs, nous obtenons
E[W τ n (z
2 )] =
p+q=n
2z + q − 1
q
2z
p
2z − 1
p
.
Remarquons que
2z−1
p
est un polynôme en z, ce qui donne finalement
la fonction génératrice δ n (z), en utilisant son expression en fonction des
E[W τ n (z)].
Fonction hypergéométrique et loi limite Nous avons ici utilisé
des moyens élémentaires pour résoudre l’équation différentielle satisfaite par
y(t). En fait, la fonction auxiliaire Y (t) appartient à la classe des fonctions
hypergéométriques : si
F [a, b; c; z] = 1 +
a b
c
z
1!
+
a(a + 1) b(b + 1)
c(c + 1)
z 2
2!
+ . . . ,
alors Y (t) = F [−α, −α + 1; 1; t].
Considérons maintenant W (z 2 , t) : sa singularité dominante en z est
obtenue pour z = 1, et dans son voisinage nous obtenons une expression
qui fait intervenir la fonction hypergéométrique F mentionnée ci-dessus :
W (z 2 , t) =
)(2z + 1)
1
(1 − t) 2z F [−2z, 1 − 2z; 1 − 4z; 1 − t] (8.17)
+
)(−2z + 1)
(1 − t) 2z F [2z, 1 + 2z; 1 + 4z; 1 − t].
La singularité de W (z 2 , t) vient du facteur
1
(1−t) 2z , ce qui correspond à un
schéma de loi limite normale (cf. le livre de Flajolet et Sedgewick [94,
IX.7.4]) ; en tenant compte des résultats déjà obtenus sur la moyenne et la
variance de la profondeur d’insertion, cela fournit directement la normalité
asymptotique de la profondeur d’insertion pour d = 2.