366
8 Arbres m-aires et quadrants
Fonction génératrice bivariée Nous introduisons ici la fonction génératrice bivariée
W (z, t) =
n≥0
E[W τ n (z)]t
n .
(8.16)
Avec la récurrence (8.15) sur les E[W τ n (z)], nous établissons que
W (z, t) = 1 + 2
d z
n−1
p=0
π n,p E[W τ p (z)]t
n .
Ici, il faudrait une expression des probabilités de partage π n,p pour continuer
l’analyse. Nous renvoyons à l’article de Flajolet et Lafforgue [86] pour le cas général
dont l’étude dépasse le cadre de ce livre (cf. aussi le problème 8.13) et détaillons
maintenant le cas d = 2.
Etude pour d = 2 Supposons dans cette partie que d = 2. Nous
montrons alors, en utilisant la relation π n,p = (1/n)(H n − H p ) (cf. la
proposition 8.13), que W (z, t) vérifie cette équation fonctionnelle :
W (z, t) = 1 + 4z
t
o
1
(1 − x) x
x
0
W (z, v)
dv
1 − v
dx.
Considérons z comme un paramètre réel positif, de sorte que l’équation
ci-dessus devient une équation intégrale sur y(t) := W (z, t), qui fournit
immédiatement, en éliminant les intégrales par dérivation, une équation
différentielle sur y(t) :
t (1 − t)
2 y
+ (1 − t)(1 − 2t)y
− 4zy = 0.
Remarquons tout d’abord que les singularités ne peuvent être qu’en t = 0 (ce
qu’on exclut bien vite, en voyant que W (z, 0) = 1, ∂W/∂t (z, 0) = 4z, etc.)
et en t = 1. Nous cherchons donc, dans un premier temps, des solutions de
la forme y(t) = 1/(1 − t) α , ce qui nous amène à demander que α(α + 1)t +
(1 − 2t)α − 4z = 0, y compris pour t = 1. Posons donc α 2 = 4z, et cherchons
maintenant des solutions de la forme
y(t) =
Y (t)
(1 − t) α ,
(tsvp)