4.5 Arbres non planaires
171
Nous avons ici une approximation de P (2) (z) qui coïncide sur les 2 p premiers termes
de son développement de Taylor à l’origine ; en adaptant la valeur de p cela donne
les coefficients de P (2) (z), et donc le nombre d’arbres de Pólya de taille donnée,
aussi loin que souhaité :
P (2) (z) = z + z
2
+ z
3
+ 2 z
4
+ 3 z
5
+ 6 z
6
+ 11 z
7
+ 23 z
8
+ 46 z
9
+ 98 z
10
+ O(z
11 ).
Voyons maintenant le passage à la limite. Pour tout z réel positif dans l’intervalle
]0, 1/2[, appelons
a 0 (z) =
√
−2z + 1 ; a 1 (z) =
−2z +
1 − 2z 2 . . .
a n (z) =
−2z +
−2z 2 + · · · +
1 − 2z 2 n ,
n ≥ 1
Il est facile de voir que la suite (a n (z)) est décroissante. Comme elle est positive,
elle admet une limite (z). En outre, pour f n (z) = 1 − a n (z), un calcul élémentaire
montre que
f n+1 (z) = z +
1
2
f
2
n+1 (z) + f n (z
2 )
,
de sorte que f (z) = 1 − (z), limite de f n (z) quand n tend vers l’infini, est solution
de l’équation fonctionnelle (4.29).
Revenons à l’équation (4.30), qui va servir à déterminer le comportement
asymptotique des coefficients de P (2) (z). Sa singularité dominante ρ, qui est aussi
son rayon de convergence, vient de l’annulation du discriminant 1 − 2z − P (2) (z 2 ),
i.e., P (2) (ρ 2 ) = 1 − 2 ρ. En reportant ceci dans l’équation (4.29), nous voyons que
ρ satisfait l’équation P (2) (z) 2 − 2P (2) (z) + 1 = 0, soit simplement
P (2) (ρ) = 1.
Numériquement nous avons ρ = 0,4026975037 . . . Nous pouvons alors, grâce au
lemme de transfert de Flajolet et Odlyzko, calculer un équivalent asymptotique
du coefficient [z n ]P (2) (z) ; des indications sur ces calculs sont données dans le
problème 4.23 de la section 4.6. Nous retrouvons ainsi un résultat, dont la première
version est due à Pólya [211], relatif à la fonction génératrice des arbres binaires
non planaires et au dénombrement asymptotique de ces arbres ; voir aussi le livre
de Flajolet et Sedgewick [94, p. 72].
Théorème 4.29 La fonction génératrice des arbres de Pólya binaires, énumérés
suivant le nombre de leurs feuilles, satisfait l’équation fonctionnelle
P (2) (z) = z +
1
2
P (2) (z
2 ) + P (2) (z)
2
.
171
Nous avons ici une approximation de P (2) (z) qui coïncide sur les 2 p premiers termes
de son développement de Taylor à l’origine ; en adaptant la valeur de p cela donne
les coefficients de P (2) (z), et donc le nombre d’arbres de Pólya de taille donnée,
aussi loin que souhaité :
P (2) (z) = z + z
2
+ z
3
+ 2 z
4
+ 3 z
5
+ 6 z
6
+ 11 z
7
+ 23 z
8
+ 46 z
9
+ 98 z
10
+ O(z
11 ).
Voyons maintenant le passage à la limite. Pour tout z réel positif dans l’intervalle
]0, 1/2[, appelons
a 0 (z) =
√
−2z + 1 ; a 1 (z) =
−2z +
1 − 2z 2 . . .
a n (z) =
−2z +
−2z 2 + · · · +
1 − 2z 2 n ,
n ≥ 1
Il est facile de voir que la suite (a n (z)) est décroissante. Comme elle est positive,
elle admet une limite (z). En outre, pour f n (z) = 1 − a n (z), un calcul élémentaire
montre que
f n+1 (z) = z +
1
2
f
2
n+1 (z) + f n (z
2 )
,
de sorte que f (z) = 1 − (z), limite de f n (z) quand n tend vers l’infini, est solution
de l’équation fonctionnelle (4.29).
Revenons à l’équation (4.30), qui va servir à déterminer le comportement
asymptotique des coefficients de P (2) (z). Sa singularité dominante ρ, qui est aussi
son rayon de convergence, vient de l’annulation du discriminant 1 − 2z − P (2) (z 2 ),
i.e., P (2) (ρ 2 ) = 1 − 2 ρ. En reportant ceci dans l’équation (4.29), nous voyons que
ρ satisfait l’équation P (2) (z) 2 − 2P (2) (z) + 1 = 0, soit simplement
P (2) (ρ) = 1.
Numériquement nous avons ρ = 0,4026975037 . . . Nous pouvons alors, grâce au
lemme de transfert de Flajolet et Odlyzko, calculer un équivalent asymptotique
du coefficient [z n ]P (2) (z) ; des indications sur ces calculs sont données dans le
problème 4.23 de la section 4.6. Nous retrouvons ainsi un résultat, dont la première
version est due à Pólya [211], relatif à la fonction génératrice des arbres binaires
non planaires et au dénombrement asymptotique de ces arbres ; voir aussi le livre
de Flajolet et Sedgewick [94, p. 72].
Théorème 4.29 La fonction génératrice des arbres de Pólya binaires, énumérés
suivant le nombre de leurs feuilles, satisfait l’équation fonctionnelle
P (2) (z) = z +
1
2
P (2) (z
2 ) + P (2) (z)
2
.