358
8 Arbres m-aires et quadrants
Ceci nous permet d’obtenir une relation de récurrence entre les coefficients (notés
respectivement v ∗
n et r ∗
n ) des fonctions V ∗ (z) et r ∗ (z) :
v
∗
n = r
∗
n − r
∗
n−1 +
1 −
2 d
n 2
v
∗
n−1 .
En sommant, nous obtenons l’expression des v ∗
n en fonction des r ∗
n :
v
∗
n =
n
j =2
(r
∗
j − r
∗
j −1 )
n
k=j +1
1 −
2 d
k 2
,
(n≥ 2).
(8.11)
Les valeurs v ∗
0 = v 0 et v ∗
1 = v 0 − v 1 s’obtiennent en regardant le comportement du
paramètre sur un arbre vide ou contenant une seule clé. Il suffit ensuite d’inverser
l’équation (8.11), par la relation (B.3), pour obtenir v n . Remarquons aussi que
r
∗
n − r
∗
n−1 = [u
n
]r
u
u − 1
.
Exemple : longueur de cheminement Appliquons la méthode précédente au
péage 5 r n = n. Nous obtenons aisément r(z) = z/(1 − z) 2 puis r ∗ (z) = −z :
r ∗
1 = −1 et, pour n > 1, r ∗
n = 0, ce qui donne
f
∗
n =
n
p=3
1 −
2 d
p 2
.
Dans le cas d = 2, l’expression de f ∗
n se simplifie :
f
∗
n =
(n + 1) (n + 2)
6n (n − 1)
(n ≥ 2),
d’où
f n =
n
p=0
(−1)
p
n
p
(p + 1) (p + 2)
6p (p − 1)
.
5 Le péage vu plus haut pour la longueur de cheminement est plutôt r n = n − 1, en considérant que
la racine est à hauteur 0. Les calculs qui suivent pour r n = n induisent une différence de n dans le
développement de la proposition 8.16.
8 Arbres m-aires et quadrants
Ceci nous permet d’obtenir une relation de récurrence entre les coefficients (notés
respectivement v ∗
n et r ∗
n ) des fonctions V ∗ (z) et r ∗ (z) :
v
∗
n = r
∗
n − r
∗
n−1 +
1 −
2 d
n 2
v
∗
n−1 .
En sommant, nous obtenons l’expression des v ∗
n en fonction des r ∗
n :
v
∗
n =
n
j =2
(r
∗
j − r
∗
j −1 )
n
k=j +1
1 −
2 d
k 2
,
(n≥ 2).
(8.11)
Les valeurs v ∗
0 = v 0 et v ∗
1 = v 0 − v 1 s’obtiennent en regardant le comportement du
paramètre sur un arbre vide ou contenant une seule clé. Il suffit ensuite d’inverser
l’équation (8.11), par la relation (B.3), pour obtenir v n . Remarquons aussi que
r
∗
n − r
∗
n−1 = [u
n
]r
u
u − 1
.
Exemple : longueur de cheminement Appliquons la méthode précédente au
péage 5 r n = n. Nous obtenons aisément r(z) = z/(1 − z) 2 puis r ∗ (z) = −z :
r ∗
1 = −1 et, pour n > 1, r ∗
n = 0, ce qui donne
f
∗
n =
n
p=3
1 −
2 d
p 2
.
Dans le cas d = 2, l’expression de f ∗
n se simplifie :
f
∗
n =
(n + 1) (n + 2)
6n (n − 1)
(n ≥ 2),
d’où
f n =
n
p=0
(−1)
p
n
p
(p + 1) (p + 2)
6p (p − 1)
.
5 Le péage vu plus haut pour la longueur de cheminement est plutôt r n = n − 1, en considérant que
la racine est à hauteur 0. Les calculs qui suivent pour r n = n induisent une différence de n dans le
développement de la proposition 8.16.