130
4 Approche combinatoire
Étudions donc la fonction (u, z) ; nous allons d’abord montrer qu’elle vérifie
une équation fonctionnelle, que nous ne pourrons pas résoudre explicitement mais
dont nous tirerons cependant les informations nécessaires à notre propos. En
écrivant un arbre non vide sous la forme τ = (◦, τ (g) , τ (d) ) et en remplaçant, dans la
définition de z), |τ | par 1+|τ (g) |+|τ (d) | (la taille d’un arbre non vide est égale
à 1 + les tailles de ses sous-arbres) et lc(τ ) par |τ (g) | + |τ (d) | + lc(τ (g) ) + lc(τ (d) )
(c’est la relation (4.7)), nous obtenons successivement
z) =
τ ∈C
u
lc(τ ) z
|τ |
= 1 +
τ =(◦,τ (g) ,τ (d) )
u
|τ (g) |+|τ (d) |+lc(τ (g) )+lc(τ (d) ) z
1+|τ (g) |+|τ (d) |
= 1 + z
τ =(◦,τ (g) ,τ (d) )
u
lc(τ (g) )+lc(τ (d) ) (uz)
|τ (g) |+|τ (d) |
= 1 + z
τ =(◦,τ (g) ,τ (d) )
u
lc(τ (g) ) (uz)
|τ (g) |
u
lc(τ (d) ) (uz)
|τ (d) |
= 1 + z
⎛
⎝
τ (g)
u
lc(τ (g) ) (uz)
|τ (g) |
⎞
⎠
⎛
⎝
τ (d)
u
lc(τ (d) ) (uz)
|τ (d) |
⎞
⎠ .
Nous reconnaissons (u, uz) dans chacune de ces dernières sommes, d’où
z) = 1 + z z(u, uz)
2 .
(4.10)
Remarque 4.4 En prenant u = 1, nous retrouvons l’équation définissant C(z) la
fonction génératrice des nombres de Catalan, comme l’on pouvait s’y attendre.
En dérivant l’équation (4.10) par rapport à u puis en substituant 1 à u, nous
obtenons
∂∂
∂u
(1, z) = 2zz(1, z)
∂∂
∂u
(1, z) + z
∂∂
∂z
(1, z)
,
qui n’est autre, compte tenu de
∂∂
∂z (1, z) = C (z), que l’équation (4.8) satisfaite par
la fonction L(z) =
∂∂
∂u (1, z).
Revenons à la variance : comme nous l’avons vu plus haut, elle s’obtient à partir
des coefficients de z n dans les dérivées ∂∂/∂u et ∂ 2 2 , prises en u = 1. Avec
[z n ] z) = C n et [z n ]∂∂/∂u(1, z) = l n , nous avons en fait
σ
2 (lc(τ n )) =
[z n ]
∂ 2
∂u 2 (1, z)
C n
+
l n
C n
−
l n
C n
2
,
(4.11)