4.1 Les arbres binaires
123
Fig. 4.1 Les arbres binaires de taille comprise entre 1 et 4
degré en z conduit à
C
2 (z) = C
2
0 + (C 0 C 1 + C 1 C 0 )z + (C 0 C 2 + C
2
1 + C 2 C 0 )z
2
+(C 0 C 3 + C 1 C 2 + C 2 C 1 + C 3 C 0 )z
3
+ . . .
et l’équation (4.2) permet de reconnaître que
C
2 (z) =
n≥0
C n+1 z
n
=
n≥1
C n z
n−1
=
1
z
n≥1
C n z
n
=
1
z
(C(z) − 1).
Nous avons donc obtenu une équation quadratique satisfaite par la fonction C(z),
que nous pouvons écrire sous la forme :
C(z) = 1 + zC
2 (z).
(4.3)
Il est bien sûr possible d’obtenir directement l’équation (4.3) par la méthode
symbolique (cf. l’annexe B.2), à partir de l’équation (4.1), que nous rappelons :
C = E + (◦ × C × C).