372
8 Arbres m-aires et quadrants
Problème
8.13. (Loi limite de la profondeur d’insertion dans un arbre quadrant
(d quelconque))
1. Soient les opérateurs
If (t) =
t
0
f (v)
dv
1 − v
;
Jf (t) =
t
0
f (v)
dv
v(1 − y)
.
En utilisant la forme intégrale
π n,k =
n − 1
p
1
0
t
p (1 − t)
n−p−1 (− log t) d−1
(d − 1)!
dt
et l’équation 8.16. montrer que W (z, t) satisfait une équation intégrale
W (z, t) = 1 + 2
d z J
d−1 I W (z, t).
2. La fonction W (z, t) est maintenant considérée comme une fonction z (t) en t, paramétrée
par z. En dérivant l’équation obtenue à l’étape précédente, établir une équation différentielle
satisfaite par z (t), linéaire d’ordre d et à coefficients polynomiaux en z et t.
3. Montrer que, lorsque z est proche de 1, la fonction z (t) a une singularité en t, elle-même
proche de 1, et qu’elle satisfait le schéma bivarié
W (z, t) =
A(t) + B(z, t)
(1 − z) f (t)
où f (t) est une fonction analytique en t = 1 et f (1) > 0, A(t) est analytique en t = 1 avec
A(1) = 0, et B(z, t) = o(1) uniformément en t lorsque z → 1.
4. En reconnaissant un schéma (1 − t) −f (z) (cf. le livre de Flajolet et Sedgewick [94, IX.7.4]),
montrer la normalité asymptotique.
(Voir l’article de Flajolet et Lafforgue [86].)