134
4 Approche combinatoire
R(z) de r, le péage à la racine. En effet,
V (z) =
τ =(◦,τ (g) ,τ (d) )
r(τ ) + v(τ
(g) ) + v(τ
(d) )
z
|τ |
=
τ ∈C
r(τ )z
|τ |
+ 2
τ (g) ,τ (d) ∈C
v(τ
(g) )z
1+|τ (g) |+|τ (d) |
= R(z) + 2zV (z)C(z),
où C(z) =
τ ∈C z |τ | est, comme précédemment, la fonction génératrice énumérant
les arbres binaires. Nous obtenons alors facilement
V (z) =
R(z)
1 − 2zC(z)
=
R(z)
√
1 − 4z
,
d’où nous tirons la valeur moyenne de v sur les arbres de taille n : c’est simplement
[z n ]V (z)/C n . Ceci conduit à la proposition suivante.
Proposition 4.6 Soit v un paramètre additif associé à la fonction de péage r de
fonction génératrice R(z) =
τ ∈C r(τ )z |τ | . Alors, sous le modèle de Catalan, la
valeur moyenne de v sur les arbres de taille n vaut
E[v(τ n )] =
1
C n
[z
n
]
R(z)
√
1 − 4z
.
Un des exemples les plus simples de paramètre additif sur un arbre binaire, outre
sa taille et sa longueur de cheminement, est le nombre de ses nœuds doubles (définis
section 1.1.2), obtenu en prenant comme péage à la racine, dans l’équation (1.10),
r(τ ) = 1 si les sous-arbres gauche et droit sont non vides, et 0 sinon :
R(z) =
τ (g) ,τ (d) =∅
z
1+|τ (g) |+|τ (d) |
= z(C(z) − 1)
2 .
Nous en tirons d’abord que
V (z) =
1
2z
√
1 − 4z
−
1
2z
+ 1 +
z − 2
√
1 − 4z
,
puis, en utilisant l’extraction du coefficient de z n dans
1
√
1 − 4z
, déjà vue en (4.9),
nous obtenons le nombre moyen de nœuds doubles dans un arbre binaire de
taille n :
[z n ]V (z)
C n
=
(n − 1) (n − 2)
2 (2n − 1)
;
ce nombre est équivalent à n/4 lorsque n tend vers l’infini.