342
8 Arbres m-aires et quadrants
Considérons maintenant une suite (Y n ) de variables aléatoires qui sont des
paramètres additifs au sens de la définition 1.48, par exemple la taille, la longueur
de cheminement, ou le nombre de nœuds de type donné. Dans la suite, examinons
le cas simple où le péage est une constante c, de sorte que
Y n = Y |T (1) | + · · · + Y |T (m) | + c.
La proposition 8.6 fournit une relation de récurrence sur les quantités P(Y n =
k), k ≥ 0, toujours avec un péage c.
P(Y n = k) =
i 1 +···+i m =n−m+1
k 1 +···+k m =k−c
(m − 1)!(n − m + 1)!
n!
P(Y i 1 = k 1 ) . . . P(Y i m = k m ).
(8.1)
Cette relation de récurrence conduit à des équations différentielles en introduisant
la fonction génératrice bivariée :
F (x, y) =
n,k≥0
P(Y n = k)x
n y
k .
En dérivant (m−1) fois par rapport à x, et en utilisant la relation de récurrence (8.1),
nous obtenons
∂ m−1 F
∂x m−1 =
(8.2)
(m − 1)!y c
n≥m−1
k≥c
⎛
⎜
⎜
⎝
i 1 +···+i m =n−m+1
k 1 +···+k m =k−c
P(Y i 1 = k 1 ) . . . P(Y i m = k m )y k 1 x i 1 . . . y k m x i m
⎞
⎟
⎟
⎠ ,
et donc
∂ m−1 F (x, y)
∂x m−1
= (m − 1)!y
c F
m (x, y),
(8.3)
qui est une équation différentielle non linéaire, sans solution explicite dès que m ≥
3. Nous allons en utiliser des sous-produits, notamment en différentiant par rapport
à la variable y, afin de calculer l’espérance et la variance de Y n ou plus généralement
la fonction génératrice des moments (ou des cumulants) de Y n .
Calcul des moments
Pour j ≥ 1, posons
G j (x) :=
∂ j F (x, y)
∂y j
y=1