172
4 Approche combinatoire
Son rayon de convergence ρ est la solution dans R + de P (2) (z) = 1, et a pour valeur
approchée ρ = 0.4026975037 . . .
Le nombre d’arbres de Pólya binaires de taille n vaut asymptotiquement
0,3187766259 . . .
ρ −n
n
√
n
.
4.5.3 Dénombrement des arbres de Pólya
Nous rappelons (cf. section 1.1.4) que Pó est l’ensemble des arbres non planaires
d’arité quelconque. Il vérifie l’équation récursive (1.13), que nous rappelons cidessous :
Pó = + (• × MSET(Pó)) .
Cette équation se traduit sur la fonction génératrice 11 Pó(z) =
n≥1 p n z n (cf.
Section B.2) en
Pó(z) = z exp
Pó(z) +
1
2
Pó(z
2 ) +
1
3
Pó(z
3 ) + . . .
.
(4.31)
Pas plus que dans le cas des arbres de Pólya binaires, une telle équation fonctionnelle
ne peut être résolue explicitement ; elle donnera cependant, comme dans le cas
binaire, le comportement asymptotique des coefficients. Nous commençons par en
tirer une forme non récursive de Pó(z) :
Pó(z) = z exp
⎛
⎝
q≥1
1
q
Pó(z
q )
⎞
⎠
= z exp
⎛
⎝
q≥1
1
q
n≥1
p n z
nq
⎞
⎠
= z exp
⎛
⎝
n≥1
p n
q≥1
1
q
z
nq
⎞
⎠
11 Ici, nous travaillons, comme le plus souvent, sur la fonction génératrice du nombre total de nœuds
de l’arbre.