4.1 Les arbres binaires
129
τ n de taille n est lc(τ n )/n ; ainsi, dans un arbre choisi selon le modèle de Catalan,
elle est asymptotiquement égale à
√
πn.
Regardons maintenant la variance de la longueur de cheminement, et pour cela
utilisons la fonction génératrice bivariée
(u, z) :=
τ ∈C
u
lc(τ ) z
|τ | ,
où les variables z et u « marquent » respectivement la taille de l’arbre et sa longueur
de cheminement.
En fait, la fonction (u, z) encode toute l’information concernant la loi de
probabilité de la longueur de cheminement lc(τ ) d’un arbre aléatoire τ sous le
modèle de Catalan (cf. la section C.1).
– Remarquons tout d’abord que z) =
τ ∈C z |τ | n’est autre que C(z).
– Le nombre d’arbres de taille n ayant une longueur de cheminement égale à k
vaut [u k z n ](u, z) ; en le divisant par le nombre C n d’arbres de taille n, que
nous pouvons aussi écrire [z n ] z), nous obtenons la probabilité qu’un arbre
de taille n ait une longueur de cheminement égale à k : c’est
P(lc(τ ) = k | |τ | = n) =
[u k z n ](u, z)
[z n ] z)
.
– La fonction génératrice de probabilité de la longueur de cheminement, conditionnée par la taille n, est
G n (u) =
[z n ] z)
[z n ] z)
.
– La fonction génératrice de la longueur de cheminement cumulée, que nous avons
déjà rencontrée plus haut, est
L(z) =
∂∂
∂u
(1, z).
– La moyenne de la longueur de cheminement sur les arbres de taille n est G
n (1),
soit
E[lc(τ n )] =
[z n ]
∂∂
∂u (1, z)
[z n ] z)
.
– La variance de la longueur de cheminement sur les arbres de taille n est G
n (1) +
G
n (1) − G
n (1) 2 , soit
σ
2
[lc(τ n )] =
[z n ]
∂ 2
∂u 2 (1, z)
[z n ] z)
+
[z n ]
∂∂
∂u (1, z)
[z n ] z)
−
[z n ]
∂∂
∂u (1, z)
[z n ] z)
2
.