4.5 Arbres non planaires
173
= z exp
⎛
⎝ −
n≥1
p n log(1 − z
n )
⎞
⎠
= z exp
⎛
⎝
n≥1
log
1
(1 − z n ) p n
⎞
⎠
= z
n≥1
1
(1 − z n ) p n
.
Nous pouvons ainsi calculer de proche en proche les premiers coefficients :
Pó(z) = z+z
2
+2z
3
+4z
4
+9z
5
+20z
6
+48 z
7
+115 z
8
+286 z
9
+719 z
10
+O(z
11 ).
Revenons maintenant à l’étude des coefficients de Pó(z) : leur comportement
asymptotique est déterminé par celui de Pó(z) au voisinage de ses singularités, qu’il
nous faut d’abord déterminer.
Lemme 4.30 Le rayon de convergence ρ de Pó(z) satisfait
1
4 ≤ ρ ≤
1
e .
Preuve Remarquons, en revenant aux définitions, que Cay n ≤ n! p n ; l’existence
de répétitions éventuelles dans les sous-arbres non marqués entraîne même que
l’inégalité est stricte. Ainsi, le rayon de convergence de Pó(z) est majoré par celui
de Cay(z), d’où la borne supérieure.
Pour la borne inférieure, il suffit de voir que p n ≤ C n−1 : en effet, chaque arbre
de Pólya de taille n correspond à plusieurs arbres planaires de même taille, et nous
avons vu plus haut (corollaire 4.2) que ces arbres sont comptés par les nombres de
Catalan.
Comme dans le cas des arbres de Pólya binaires, nous allons maintenant
considérer l’équation fonctionnelle (4.31) comme une équation en Pó(z) avec une
perturbation :
Pó(z) = e
Pó(z) φ(z) avec φ(z) = z e
p≥2
1
p Pó(z p ) .
(4.32)
La fonction φ(z) a pour rayon de convergence
√
ρ, qui est supérieur à ρ puisque
ρ < 1 (cf. le problème 4.24 de la section 4.6 pour les détails). Posons maintenant
G(z, w) = ze
w
− w.
D’après les équations (4.32) et (4.27) respectivement,
G(φ(z), Pó(z)) = 0