140
4 Approche combinatoire
Le coefficient de (y − ξ) vaut 1/S(ξ ) − ξS (ξ )/S(ξ ) 2 , et est donc nul par définition
de ξ ; et celui de (y − ξ) 2 est égal après simplification à −ρS
(ξ )/S(ξ ), ce qui
donne
z − ρ = −
ρ S
(ξ )
2 S(ξ)
(y − ξ)
2
+ O
(y − ξ)
3
.
Nous inversons alors cette égalité, pour obtenir le développement de y = y(z) en
fonction de z au voisinage de ρ, où nous gardons provisoirement le terme d’erreur
en y(z) − ξ :
(y(z) − ξ)
2
= −
2 S(ξ)
ρ S
(ξ )
(z − ρ) + O
(y(z) − ξ)
3
.
Remarquons que S (ξ ) > 0, car le développement en série de S autour de 0 est
à coefficients positifs ou nuls, et S (ξ ) = 0 entraînerait S fonction linéaire, cas
dégénéré que nous évitons (tous les arbres seraient filiformes). Pour les mêmes
raisons, S(ξ) > 0 : en effet, ξ > 0 et S(z) est à coefficients dans N, non tous
nuls. Ceci implique tout d’abord que y(z) − ξ est d’ordre (z − ρ)
1
2 , et que le terme
d’erreur ci-dessus est O
(z − ρ)
3
2
. En résolvant ensuite l’équation quadratique
en y
(y − ξ)
2
= −
2 S(ξ)
ρ S
(ξ )
(z − ρ) + O
(z − ρ)
3
2
,
et en choisissant la racine adéquate, nous obtenons les premiers coefficients :
y(z) = ξ −
2 S(ξ)
S
(ξ )
1 − z/ρ + O((z − ρ)
3/2 ).
(4.20)
Nous avons mis en évidence ici une singularité de type « racine carrée ». Ce type de
singularité est relativement « universel » pour les structures arborescentes dès lors
que nous avons une relation implicite comme (4.17). Nous rencontrerons la même
situation pour l’étude des arbres de Cayley, qui ne sont pourtant pas planaires, en
section 4.5.1. Il s’agit ensuite extraire le coefficient d’ordre n dans cette équation.
Le lemme de transfert de Flajolet et Odlyzko, que nous avons déjà utilisé plus haut,
permet ici de justifier que le coefficient d’ordre n d’une fonction O
(z − ρ) 3/2
peut s’écrire O
[z n ] (z − ρ) 3/2
. En extrayant le coefficient d’ordre n de
√
1 − z/ρ,
nous obtenons
[z
n
]y(z) =
2 S(ξ)
S
(ξ )
ρ
−n
1
2n
√
πn
+ O([z
n
] (z − ρ)
3/2 ).
Cette étude est résumée dans le théorème suivant.