4.2 Familles simples d’arbres
145
Nous simplifions ceci, en tenant compte de
f z |f | = F (z) et
f |f |z |f | =
z F
(z). Remarquons aussi la symétrie sur f et g dans les sommes doubles, de sorte
que
D = z + 2zF + z
2 F
+ zD + 4zF
2
+ 4zF D + 2z
2 F F
.
Résolvons pour obtenir
D(z) = z
1 + 2F (z) + zF (z) + 4F (z) 2 + 2zF (z)F
(z)
1 − z − 4zF (z)
.
Compte tenu des relations tirées de l’équation F = z(1 + F + 2F 2 ) (c’est
l’équation (4.14)), nous avons
F
(z) =
F (z)
z(1 − z − 4zF (z))
et
F
2 (z) =
(1 − z)F (z) − z
2z
,
ce qui nous permet d’abord d’obtenir
D =
2F 2 − z 2
F (1 − z − 4zF )
=
(1 − z)F − z − z 3
zF (1 − z − 4zF )
,
et nous donne après quelques calculs
D(z) =
√
1 − 2z − 7z 2
4z
+
3z
4
√
1 − 2z − 7z 2
−
1 − 3z − 10z 2
4z(1 − 2z − 7z 2 )
.
Au voisinage de la singularité dominante ρ 0 , qui est la racine de plus petit module
de l’équation 1 − 2 z − 7 z 2 = 0 et vaut
2
√
2−1
7 , nous avons le développement
D(z) =
1 +
√
2
8(1 − z/ρ 0 )
+ O
(1 − z/ρ 0 )
−1/2
,
ce qui donne, en appliquant à nouveau le lemme de transfert :
[z
n
]D(z) ∼
1 +
√
2
8
ρ
−n
0 (1 + o(1)).
D’où, en divisant par le nombre d’expressions de taille n, dont la valeur asymptotique est
1+
1
2
√
2
2n
√
πn
ρ
−n
0 (cf. l’équation (4.16)), la proposition suivante.