4.2 Familles simples d’arbres
137
La fonction F (z) = (1 − z −
√
1 − 2z − 7z 2 )/(4z) est bien une fonction
analytique en z, et ses deux singularités sont les racines du polynôme 1 − 2z − 7z 2 ,
soit ρ 0 = (2
√
2 − 1)/7 et ρ 1 = −(2
√
2 + 1)/7 ; de plus ρ 0 est la singularité de plus
petit module, donc dominante. Sans rentrer dans les détails, tout se passe « comme
si », au voisinage de cette singularité principale ρ 0 , nous pouvions remplacer F (z),
que nous pouvons aussi écrire sous la forme
F (z) =
1 − z −
√
(1 − z/ρ 0 )(1 − z/ρ 1 )
4z
par
F 1 (z) =
1 − ρ 0 −
√
(1 − z/ρ 0 )(1 − ρ 0 /ρ 1 )
4ρ 0
,
c’est-à-dire son développement au voisinage de ρ 0 dans l’échelle
1 −
z
ρ 0
α
:
F (z) = −
1 +
1
2
√
2
1 −
z
ρ 0
+ O
1 −
z
ρ 0
,
lorsque z tend vers ρ 0 . Le terme principal dans le développement asymptotique du
coefficient de z n dans F vient du terme
√
1 − z/ρ 0 , et celui qui vient du terme
d’erreur O
1 −
z
ρ 0
donne un terme d’erreur, ce qui n’est en rien évident, mais est
rendu rigoureux grâce au lemme de transfert ; nous obtenons alors, pour n → +∞
f n ∼
1 +
1
2
√
2
2n
√
πn
ρ
−n
0 .
(4.16)
Remarquons ici que nous aurions déjà pu utiliser le lemme de transfert pour obtenir
le comportement asymptotique du nombre d’arbres binaires, ou de leur longueur
moyenne de cheminement, si nous n’avions pas été intéressés par les valeurs
exactes.
4.2.2 Dénombrement exact
Le dénombrement que nous avons effectué sur l’exemple précédent ne dépend
pas d’une propriété particulière de cette famille d’expressions, mais repose sur la
définition des familles simples d’arbres, et est donc généralisable à toute famille
simple d’arbres. Soit F une telle famille associée à un ensemble S de symboles.
Soit σ p le nombre de symboles de S d’arité p, et soient S(u) :=
p σ p u p et
F (z) :=
n f n z n les fonctions génératrices de dénombrement respectives de S
137
La fonction F (z) = (1 − z −
√
1 − 2z − 7z 2 )/(4z) est bien une fonction
analytique en z, et ses deux singularités sont les racines du polynôme 1 − 2z − 7z 2 ,
soit ρ 0 = (2
√
2 − 1)/7 et ρ 1 = −(2
√
2 + 1)/7 ; de plus ρ 0 est la singularité de plus
petit module, donc dominante. Sans rentrer dans les détails, tout se passe « comme
si », au voisinage de cette singularité principale ρ 0 , nous pouvions remplacer F (z),
que nous pouvons aussi écrire sous la forme
F (z) =
1 − z −
√
(1 − z/ρ 0 )(1 − z/ρ 1 )
4z
par
F 1 (z) =
1 − ρ 0 −
√
(1 − z/ρ 0 )(1 − ρ 0 /ρ 1 )
4ρ 0
,
c’est-à-dire son développement au voisinage de ρ 0 dans l’échelle
1 −
z
ρ 0
α
:
F (z) = −
1 +
1
2
√
2
1 −
z
ρ 0
+ O
1 −
z
ρ 0
,
lorsque z tend vers ρ 0 . Le terme principal dans le développement asymptotique du
coefficient de z n dans F vient du terme
√
1 − z/ρ 0 , et celui qui vient du terme
d’erreur O
1 −
z
ρ 0
donne un terme d’erreur, ce qui n’est en rien évident, mais est
rendu rigoureux grâce au lemme de transfert ; nous obtenons alors, pour n → +∞
f n ∼
1 +
1
2
√
2
2n
√
πn
ρ
−n
0 .
(4.16)
Remarquons ici que nous aurions déjà pu utiliser le lemme de transfert pour obtenir
le comportement asymptotique du nombre d’arbres binaires, ou de leur longueur
moyenne de cheminement, si nous n’avions pas été intéressés par les valeurs
exactes.
4.2.2 Dénombrement exact
Le dénombrement que nous avons effectué sur l’exemple précédent ne dépend
pas d’une propriété particulière de cette famille d’expressions, mais repose sur la
définition des familles simples d’arbres, et est donc généralisable à toute famille
simple d’arbres. Soit F une telle famille associée à un ensemble S de symboles.
Soit σ p le nombre de symboles de S d’arité p, et soient S(u) :=
p σ p u p et
F (z) :=
n f n z n les fonctions génératrices de dénombrement respectives de S