296
7 Arbres digitaux
Notant γ n = n![z n ] γ (z), nous obtenons l’expression
v n (1 −
2
2 n ) = γ n +
2
2 n
n−1
k=0
n
k
v k ,
ou encore
v n =
2
2 n
1 −
2
2 n
γ n +
n−1
k=0
n
k
v k
.
(7.13)
Malheureusement, ce procédé n’est véritablement pas efficace car le calcul de la
valeur de deux termes successifs v n et v n+1 demande de considérer un nombre
linéaire de termes. Calculer les n premiers termes demande donc un temps
quadratique en n. Cependant ce calcul permet de calculer les valeurs exactes de
v n pour n « pas trop grand ».
Le lemme d’itération 7.7 s’adapte au cas infini.
Lemme 7.12 (Itération – modèle infini i.i.d. uniforme) Soient α(z) et β(z) deux
séries entières avec α(0) = c pour une certaine constante c > 0 et β(z) = O(z r )
pour un certain entier r ≥ 2 quand z → 0, et telles que les séries α et β satisfont
une « condition de contraction » c2 −r < 1. Considérons l’équation fonctionnelle
v(z) = α(z) v(z/2) + β(z),
(7.14)
où v est une fonction inconnue supposée satisfaire les conditions initiales
v(0) =
d v
dz
(0) = · · · =
d r−1 v
dz r−1 (0) = 0.
Alors l’équation (7.14) admet une unique solution sous la forme
v(z) =
j ≥0
⎛
⎝ β(z/2
j )
j −1
k=0
α(z/2
k )
⎞
⎠ .
La preuve est omise et se trouve dans Flajolet et al. [97].
Dans le cas particulier d’un paramètre additif, nous obtenons le lemme suivant.
Lemme 7.13 (Itération paramètre additif– modèle infini i.i.d. uniforme) Soit
un paramètre additif v de trie s’exprimant à l’aide d’une fonction de péage γ . Soit
γ (z) la série génératrice associée à γ . Alors la série génératrice du paramètre v(z)
7 Arbres digitaux
Notant γ n = n![z n ] γ (z), nous obtenons l’expression
v n (1 −
2
2 n ) = γ n +
2
2 n
n−1
k=0
n
k
v k ,
ou encore
v n =
2
2 n
1 −
2
2 n
γ n +
n−1
k=0
n
k
v k
.
(7.13)
Malheureusement, ce procédé n’est véritablement pas efficace car le calcul de la
valeur de deux termes successifs v n et v n+1 demande de considérer un nombre
linéaire de termes. Calculer les n premiers termes demande donc un temps
quadratique en n. Cependant ce calcul permet de calculer les valeurs exactes de
v n pour n « pas trop grand ».
Le lemme d’itération 7.7 s’adapte au cas infini.
Lemme 7.12 (Itération – modèle infini i.i.d. uniforme) Soient α(z) et β(z) deux
séries entières avec α(0) = c pour une certaine constante c > 0 et β(z) = O(z r )
pour un certain entier r ≥ 2 quand z → 0, et telles que les séries α et β satisfont
une « condition de contraction » c2 −r < 1. Considérons l’équation fonctionnelle
v(z) = α(z) v(z/2) + β(z),
(7.14)
où v est une fonction inconnue supposée satisfaire les conditions initiales
v(0) =
d v
dz
(0) = · · · =
d r−1 v
dz r−1 (0) = 0.
Alors l’équation (7.14) admet une unique solution sous la forme
v(z) =
j ≥0
⎛
⎝ β(z/2
j )
j −1
k=0
α(z/2
k )
⎞
⎠ .
La preuve est omise et se trouve dans Flajolet et al. [97].
Dans le cas particulier d’un paramètre additif, nous obtenons le lemme suivant.
Lemme 7.13 (Itération paramètre additif– modèle infini i.i.d. uniforme) Soit
un paramètre additif v de trie s’exprimant à l’aide d’une fonction de péage γ . Soit
γ (z) la série génératrice associée à γ . Alors la série génératrice du paramètre v(z)