4.6 Exercices et problèmes
181
En déduire que la valeur asymptotique du coefficient [z n ]P (2) (z) est
λ
n
√
n
1
ρ
n
,
avec
λ =
ρ + ρ 2 Q
(ρ 2 )
2π
= 0,3187766259 . . .
Problème 4.24. (Dénombrement des arbres de Pólya) Il s’agit ici d’obtenir l’asymptotique
des arbres de Pólya, sans restriction d’arité. Les notations sont celles de la section 4.5.3.
1. On a vu que la fonction φ(z) =
p≥2
1
p P o(z p ) a un rayon de convergence au plus égal à
√
ρ.
Montrer que
√
ρ est bien le rayon de convergence de φ(z).
2. En partant des deux équations Cay(φ(z)) = φ(z) e Cay(φ(z)) et P o(φ(z)) = φ(z) e P o(φ(z)) ,
montrer que P o(z) = Cay(φ(z)).
3. Utiliser la méthode de la section 4.2.3 pour obtenir le comportement de la fonction Cay(z)
autour de sa singularité
1
e .
4. Soit ρ la singularité de P o(z) ; montrer qu’elle est solution de l’équation φ(z) =
1
e . Évaluer sa
valeur numérique.
5. Utiliser l’analycité de la fonction φ(z) en ρ pour obtenir un développement de Cay(φ(z))
autour de ρ.
6. En supposant qu’un lemme de transfert s’applique, montrer que [z n ]P o(z) ∼ γ
ρ −n
n 3/2 avec γ =
e ρφ
(ρ)
π
. Évaluer numériquement γ .