8.1 Arbres m-aires de recherche
343
de sorte que par récurrence sur j , nous avons
G j (x) =
n≥0
E (Y n (Y n − 1) . . . (Y n − j + 1)) x
n .
Remarquons que
F (x, 1) =
n,k≥0
P(Y n = k)x
n
=
n≥0
x
n
=
1
1 − x
.
(8.4)
La méthode consiste ensuite à dériver en y l’équation (8.3), intervertir les ordres de
dérivation et spécialiser en y = 1 pour obtenir une équation différentielle sur G j .
Faisons-le pour G 1 (x), ce qui nous fournira l’asymptotique de E(Y n ).
G 1 (x) =
n≥0
E (Y n ) x
n
et
∂
∂y
∂ m−1 F (x, y)
∂x m−1
= (m − 1)!
cy
c−1 F
m (x, y) + y
c m
∂
∂y
F (x, y)F
m−1 (x, y)
.
Nous intervertissons les dérivations en y et en x, spécialisons en y = 1 et tenons
compte de (8.4) :
∂ m−1
∂x m−1 G 1 (x) −
m!
(1 − x) m−1 G 1 (x) =
c(m − 1)!
(1 − x) m .
C’est une équation différentielle de type Euler, linéaire en G 1 . Commençons par
résoudre l’équation homogène :
∂ m−1
∂x m−1 G 1 (x) −
m!
(1 − x) m−1 G 1 (x) = 0
qui admet comme base de solutions les (m − 1) fonctions (1 − x) −1−λ i , où
λ 1 , . . . , λ m−1 sont les (m − 1) solutions de l’équation caractéristique
m! = (λ + 1)(λ + 2) . . . (λ + m − 1).
(8.5)
Il est clair que λ = 1 est une solution, et on peut prouver (voir Hennequin [129])
que les autres racines sont simples, conjuguées deux à deux et réparties sur une
courbe dans le plan complexe, qui peut être tracée pour chaque valeur de m. La
figure 8.3 permet de voir les racines pour m = 22.