128
4 Approche combinatoire
et il suffit de remplacer |τ (g) | par k dans la première somme puis de voir qu’il y a
C k arbres τ (g) de taille k, et de remplacer
|τ (g) |=k lc(τ (g) ) par l k dans la deuxième,
pour obtenir la relation de récurrence, valide pour n ≥ 1 :
l n = 2
n−1
k=0
(k C k + l k ) C n−k−1 .
Pour résoudre cette équation, nous utilisons comme plus haut une fonction génératrice 2 : L(z) :=
n≥0 l n z n =
τ ∈C lc(τ )z |τ | . Cette fonction satisfait l’équation
linéaire (nous laissons les calculs en exercice)
L(z) = 2z
2 C(z) C
(z) + 2z L(z) C(z).
(4.8)
Nous obtenons aisément
L(z) =
2z 2 C(z) C (z)
1 − 2zC(z)
.
Puisque C(z) = (1 −
√
1 − 4z)/(2z), il suffit de calculer C (z) pour obtenir
L(z) =
1
z
+
1
1 − 4z
+
1 −
1
z
1
√
1 − 4z
.
Comme précédemment pour (4.5), extrayons le coefficient de
1
√
1 − 4z
:
[z
n
]
1
√
1 − 4z
=
2n
n
,
(4.9)
ce qui donne la longueur de cheminement l n , cumulée sur tous les arbres de taille n :
l n = 4
n
+
2n
n
−
2n + 2
n + 1
= 4
n
−
3n + 1
n + 1
2n
n
= 4
n
− (3n + 1)C n .
Pour trouver la longueur de cheminement moyenne d’un arbre de taille n sous
le modèle de Catalan, i.e., dans le cas où tous les arbres de cette taille sont
équiprobables, il nous suffit maintenant de diviser cette longueur cumulée l n par
le nombre d’arbres C n , et nous obtenons la valeur (4 n /C n ) − (3n + 1), dont les
premiers termes du développement asymptotique sont n
√
π n − 3n + (9/8)
√
πn −
1+o(n −1/2 ). La profondeur moyenne d’un nœud choisi uniformément dans un arbre
2 Toute personne avisée aura remarqué que, de nouveau, elle peut obtenir directement l’équation
sur la fonction génératrice L(z) à partir de la relation (4.7) reliant la longueur de cheminement
d’un arbre à celles de ses sous-arbres.