170
4 Approche combinatoire
n’a pas de nœuds simples : le nombre de ses feuilles est donc 1+ le nombre de
ses nœuds internes. En distinguant le cas où les deux sous-arbres sont identiques de
celui où ils sont distincts, nous pouvons exprimer P (2) (z) sous la forme
P (2) (z) = z +
τ ∈P (2)
z
2|τ |
+
τ 1 ,τ 2 ∈P (2) ,τ 1 =τ 2
z
|τ 1 |+|τ 2 | .
Nous reconnaissons P (2) (z 2 ) dans la première somme ; quant à la seconde, elle peut
se réécrire en
τ 1 ,τ 2 ∈P (2) ,τ 1 =τ 2
z
|τ 1 |+|τ 2 |
=
1
2
⎛
⎜
⎝
(τ 1 ,τ 2 )∈P 2
(2)
z
|τ 1 |+|τ 2 |
− P (2) (z
2 )
⎞
⎟
⎠
=
1
2
P (2) (z)
2
− P (2) (z
2 )
,
ce qui donne finalement l’équation fonctionnelle :
P (2) (z) = z +
1
2
P (2) (z
2 ) + P (2) (z)
2
.
(4.29)
Pour résoudre cette équation, nous la considérons comme une équation du second
degré en P (2) (z) avec une perturbation P (2) (z 2 ), et procédons par itérations successives. Nous allons donc d’abord résoudre l’équation
Y = z +
1
2
Y
2
+
1
2
P (2) (z
2 ),
ce qui donne, en choisissant la racine adéquate,
P (2) (z) = 1 −
1 − 2 z − P (2) (z 2 ).
(4.30)
Reportons-y la valeur P (2) (z 2 ) = 1 −
1 − 2 z 2 − P (2) (z 4 ), puis itérons ; nous
obtenons
P (2) (z) = 1 −
−2 z +
1 − 2 z 2 − P (2) (z 4 )
= 1 −
−2 z +
−2 z 2 +
1 − 2 z 4 − P (2) (z 8 )
= 1 −
−2 z +
−2 z 2 +
−2 z 4 +
. . .
1 − 2 z 2 p − P (2) (z 2 p+1 )