4.2 Familles simples d’arbres
139
– Revenons enfin à l’exemple des expressions définies en section 4.2.1 à partir des
opérateurs +, ∗ et exp ; ici S(u) = 1 + u + 2u 2 , ce qui donne une autre manière
d’écrire le coefficient de z n :
f n =
1
n
[u
n−1
](1 + u + 2u
2 )
n
=
1
n
n−1
2 ≤p≤n−1
n
p
p
n − 1 − p
2
n−1−p .
(4.19)
4.2.3 Dénombrement asymptotique
Lorsqu’il n’est pas possible d’obtenir une formule close pour f n , ou lorsque la
formule close est compliquée comme dans le dernier exemple ci-dessus, l’équation
implicite (4.17) va cependant permettre d’obtenir son équivalent asymptotique ; cf.
par exemple Meir et Moon [185]. Posons
G(y, z) := y − zS(y);
la fonction F (z) est définie comme la solution en y de l’équation G(y, z) = 0.
Le théorème des fonctions implicites version analytique (cf. section B.3.5), qui
s’applique bien puisque S(0) = 0, nous assure de l’existence et de l’unicité de F ,
analytique dans un voisinage de 0 ; le théorème de Pringsheim s’applique car les
coefficients de F sont positifs ou nuls, et donc le rayon de convergence de la série
est une singularité dominante. Cette singularité positive ρ est obtenue lorsqu’il n’est
plus possible de résoudre l’équation en y, G(y, z) = 0, i.e., lorsque la dérivée
∂G/∂y s’annule. Notons ξ = F (ρ), de sorte que ρ et ξ sont solutions du système
ξ = ρS(ξ);
1 = ρS (ξ ).
De ce système, nous déduisons d’abord l’équation en une seule variable
ξS
(ξ ) = S(ξ),
que nous résolvons sur R + et qui nous permet de déterminer la valeur ξ (supposée
unique). La première équation du système nous donne alors la valeur de ρ, égale à
ξ/S(ξ). Nous allons maintenant écrire l’équation (4.17) sous la forme z = y/S(y),
i.e., considérer z comme une fonction de y, que nous développons autour de ξ :
z = ρ + (y − ξ)
d
dy
y
S(y)
y=ξ
+
1
2
(y − ξ)
2 d 2
dy 2
y
S(y)
y=ξ
+ O
(y − ξ)
3
.