174
4 Approche combinatoire
et G(z, Cay(z)) = 0, que nous pouvons aussi écrire sous la forme
G(φ(z), Cay(φ(z))) = 0.
Puisque G(φ(z), w) vérifie les conditions du théorème des fonctions implicites (cf.
le théorème B.6) et que Pó(0) = Cay(0) = 0, nous pouvons identifier Pó(z) dans
son disque de convergence :
Pó(z) = Cay(φ(z)).
L’étape suivante est d’obtenir un développement de Pó(z) autour de sa singularité ρ. Or le fait que Pó(z) = Cay(φ(z)) ait pour singularité ρ implique que φ(ρ)
est égal à la singularité
1
e de Cay(z) ; développer cette fonction autour de
1
e donnera
le comportement asymptotique de p n par un lemme de transfert. Nous renvoyons au
problème 4.24 pour plus de détails.
Nous résumons les résultats obtenus dans le théorème suivant, en renvoyant à
Flajolet et Sedgewick [94, p. 477] pour des indications sur l’évaluation numérique
du rayon de convergence et de la constante mutiplicative.
Théorème 4.31 La fonction génératrice des arbres de Pólya Pó(z) =
n≥1 p n z n
satisfait l’équation fonctionnelle
Pó(z) = z exp
Pó(z) +
1
2
Pó(z
2 ) +
1
3
Pó(z
3 ) + . . .
= z
n≥1
1
(1 − z n ) p n
.
Son rayon de convergence a pour valeur approchée ρ = 0,33832 . . .
Le nombre d’arbres de Pólya de taille n vaut asymptotiquement
p n ∼ 1,55949 . . .
ρ −n
2n
√
n
.
4.6 Exercices et problèmes
4.1. Calculer la moyenne et la variance du nombre de nœuds de différents types (doubles,
simples, feuilles) dans un arbre binaire de taille n.
4.2. Retrouver les nombres de Catalan en considérant l’équation (4.3) comme une équation
implicite, et en lui appliquant la formule de Lagrange.
4.3. Vérifier l’égalité des deux expressions (4.15) et (4.19) obtenues pour le nombre f n
d’expressions arithmétiques construites sur x, exp, + et ∗.
4.4. En utilisant la définition 1.8, calculer le nombre d’arbres planaires à n nœuds. Retrouver
la bijection avec les arbres binaires à n + 1 nœuds.
4.5. Calculer le nombre d’arbres planaires de taille n dont les nœuds ont pour seules arités
possibles 0 (feuilles) ou p, et étudier le comportement asymptotique du nombre de nœuds d’arité p.
4 Approche combinatoire
et G(z, Cay(z)) = 0, que nous pouvons aussi écrire sous la forme
G(φ(z), Cay(φ(z))) = 0.
Puisque G(φ(z), w) vérifie les conditions du théorème des fonctions implicites (cf.
le théorème B.6) et que Pó(0) = Cay(0) = 0, nous pouvons identifier Pó(z) dans
son disque de convergence :
Pó(z) = Cay(φ(z)).
L’étape suivante est d’obtenir un développement de Pó(z) autour de sa singularité ρ. Or le fait que Pó(z) = Cay(φ(z)) ait pour singularité ρ implique que φ(ρ)
est égal à la singularité
1
e de Cay(z) ; développer cette fonction autour de
1
e donnera
le comportement asymptotique de p n par un lemme de transfert. Nous renvoyons au
problème 4.24 pour plus de détails.
Nous résumons les résultats obtenus dans le théorème suivant, en renvoyant à
Flajolet et Sedgewick [94, p. 477] pour des indications sur l’évaluation numérique
du rayon de convergence et de la constante mutiplicative.
Théorème 4.31 La fonction génératrice des arbres de Pólya Pó(z) =
n≥1 p n z n
satisfait l’équation fonctionnelle
Pó(z) = z exp
Pó(z) +
1
2
Pó(z
2 ) +
1
3
Pó(z
3 ) + . . .
= z
n≥1
1
(1 − z n ) p n
.
Son rayon de convergence a pour valeur approchée ρ = 0,33832 . . .
Le nombre d’arbres de Pólya de taille n vaut asymptotiquement
p n ∼ 1,55949 . . .
ρ −n
2n
√
n
.
4.6 Exercices et problèmes
4.1. Calculer la moyenne et la variance du nombre de nœuds de différents types (doubles,
simples, feuilles) dans un arbre binaire de taille n.
4.2. Retrouver les nombres de Catalan en considérant l’équation (4.3) comme une équation
implicite, et en lui appliquant la formule de Lagrange.
4.3. Vérifier l’égalité des deux expressions (4.15) et (4.19) obtenues pour le nombre f n
d’expressions arithmétiques construites sur x, exp, + et ∗.
4.4. En utilisant la définition 1.8, calculer le nombre d’arbres planaires à n nœuds. Retrouver
la bijection avec les arbres binaires à n + 1 nœuds.
4.5. Calculer le nombre d’arbres planaires de taille n dont les nœuds ont pour seules arités
possibles 0 (feuilles) ou p, et étudier le comportement asymptotique du nombre de nœuds d’arité p.