4.5 Arbres non planaires
169
Une fois que nous avons la valeur explicite de [z n ] Cay(z), nous obtenons aisément
l’équivalent asymptotique par la formule de Stirling (cf. section B.5.1) :
Cay n
n!
∼
e n
n
√
2πn
.
Nous pouvons alors en déduire le rayon de convergence de la fonction génératrice
Cay(z) : c’est
1
e = 0,367879 . . .
Ce raisonnement très simple ne nous donne cependant pas le type de la singularité
de la fonction Cay(z), dont nous allons avoir besoin pour étudier les arbres de Pólya
(qui s’obtiennent à partir des arbres de Cayley en effaçant les marques). Cela nous
sera fourni par une approche alternative : bien que les arbres de Cayley ne forment
pas une famille simple d’arbres, l’étude de la solution d’une équation implicite
présentée en section 4.2.3 s’applique sans problème à Cay(z) (qui, rappelons-le,
est la fonction génératrice exponentielle – et non ordinaire – des arbres de Cayley).
Cela permet tout d’abord de retrouver les valeurs du rayon de convergence ρ et de
ξ = Cay(ρ) : elles satisfont le système d’équations
ξ = ρ e ξ
1 = ρ e ξ
ce qui donne d’abord ξ = 1, puis ρ =
1
e . Cela montre ensuite que, toujours comme
dans le cas des familles simples d’arbres de la section 4.2.3,
1
e est une singularité
algébrique de type « racine carrée » avec un comportement de la fonction génératrice
en −
√
1 − ez. Nous résumons ces résultats dans le théorème suivant.
Théorème 4.28 La fonction génératrice exponentielle des arbres de Cayley satisfait l’équation implicite Cay(z) = ze Cay(z) . Elle a pour rayon de convergence
1
e et
a une singularité de type « racine carrée » en ce point.
Le nombre d’arbres de Cayley de taille n est Cay n = n n−1 .
4.5.2 Arbres de Pólya binaires
Soit P (2) l’ensemble des arbres de Pólya binaires ; nous avons vu (cf. la définition 1.4) qu’il vérifie la relation de récurrence
P (2) = + (• × MSET 2 (P (2) )),
(4.28)
où MSET 2 (X) est le multi-ensemble (non ordonné) composé de deux éléments d’un
ensemble X : les répétitions sont autorisées ; cf. section B.1 ou [94, p. 26]. Ceci
donne une équation sur la fonction génératrice P (2) (z) – ici, la taille d’un arbre est
le nombre de ses feuilles, marquées par z. Remarquons qu’un arbre de Pólya binaire
169
Une fois que nous avons la valeur explicite de [z n ] Cay(z), nous obtenons aisément
l’équivalent asymptotique par la formule de Stirling (cf. section B.5.1) :
Cay n
n!
∼
e n
n
√
2πn
.
Nous pouvons alors en déduire le rayon de convergence de la fonction génératrice
Cay(z) : c’est
1
e = 0,367879 . . .
Ce raisonnement très simple ne nous donne cependant pas le type de la singularité
de la fonction Cay(z), dont nous allons avoir besoin pour étudier les arbres de Pólya
(qui s’obtiennent à partir des arbres de Cayley en effaçant les marques). Cela nous
sera fourni par une approche alternative : bien que les arbres de Cayley ne forment
pas une famille simple d’arbres, l’étude de la solution d’une équation implicite
présentée en section 4.2.3 s’applique sans problème à Cay(z) (qui, rappelons-le,
est la fonction génératrice exponentielle – et non ordinaire – des arbres de Cayley).
Cela permet tout d’abord de retrouver les valeurs du rayon de convergence ρ et de
ξ = Cay(ρ) : elles satisfont le système d’équations
ξ = ρ e ξ
1 = ρ e ξ
ce qui donne d’abord ξ = 1, puis ρ =
1
e . Cela montre ensuite que, toujours comme
dans le cas des familles simples d’arbres de la section 4.2.3,
1
e est une singularité
algébrique de type « racine carrée » avec un comportement de la fonction génératrice
en −
√
1 − ez. Nous résumons ces résultats dans le théorème suivant.
Théorème 4.28 La fonction génératrice exponentielle des arbres de Cayley satisfait l’équation implicite Cay(z) = ze Cay(z) . Elle a pour rayon de convergence
1
e et
a une singularité de type « racine carrée » en ce point.
Le nombre d’arbres de Cayley de taille n est Cay n = n n−1 .
4.5.2 Arbres de Pólya binaires
Soit P (2) l’ensemble des arbres de Pólya binaires ; nous avons vu (cf. la définition 1.4) qu’il vérifie la relation de récurrence
P (2) = + (• × MSET 2 (P (2) )),
(4.28)
où MSET 2 (X) est le multi-ensemble (non ordonné) composé de deux éléments d’un
ensemble X : les répétitions sont autorisées ; cf. section B.1 ou [94, p. 26]. Ceci
donne une équation sur la fonction génératrice P (2) (z) – ici, la taille d’un arbre est
le nombre de ses feuilles, marquées par z. Remarquons qu’un arbre de Pólya binaire