136
4 Approche combinatoire
d’où nous tirons
F (z) =
1 − z −
1 − (2z + 7z 2 )
4z
= 2z + 2z
2
+ z
3
+ 14z
4
+ 42z
5
+ 122z
6
+ 382z
7
+ 1206z
8
+3922z
9
+ 12914z
10
+ O
z
11
,
quand z tend vers 0. Le nombre d’expressions de taille n est f n = [z n ]F (z) ; ce
nombre satisfait aussi l’équation de récurrence
⎧
⎨
⎩
f 0 = 0;
f 1 = 1;
f n = f n−1 + 2
n−1
k=0 f k f n−k−1
(n ≥ 2).
S’il n’en existe pas de forme close analogue aux nombres de Catalan, nous pouvons
cependant écrire f n comme somme pondérée de coefficients binomiaux, à partir du
développement de Taylor de
1 − (2z + 7z 2 ) autour de 0 (cf. section B.3.3) ; nous
obtenons
f n =
1
2 n+2
n+1
2 ≤m≤n+1
C m−1
m
n + 1 − m
7
n+1−m .
(4.15)
Cette formule, ou la formule de récurrence donnée plus haut, sont une alternative
à la formule de Taylor pour calculer les premières valeurs de la suite (f n ). S’il
est facile de calculer un nombre important de valeurs de f n , il l’est moins d’avoir
une idée de leur comportement asymptotique lorsque n tend vers l’infini à partir de
ces valeurs numériques : à la différence des calculs que nous avons faits dans les
sections précédentes pour énumérer les arbres binaires et obtenir la moyenne ou la
variance de leur longueur de cheminement, nous ne pouvons pas obtenir pour f n
une forme comportant un nombre fixe de termes. Cependant, ce qui nous intéresse
ici est essentiellement, plus que le nombre exact d’arbres f n , son comportement
asymptotique, et un outil de choix pour cela est le lemme de transfert de Flajolet
et Odlyzko, que nous rappelons dans l’annexe B.3.6 (l’on pourra aussi se reporter
à l’article original de Flajolet et Odlyzko [90] ou aux pages 338 à 392 du livre de
Flajolet et Sedgewick [94]).
L’idée fondamentale de ce résultat est de relier le comportement asymptotique
des coefficients d’une fonction, supposée analytique dans un voisinage de l’origine,
à son comportement autour de ses singularités. Ici, nous sommes dans le cas d’une
fonction génératrice de dénombrement, à coefficients tous positifs, et le théorème
de Pringsheim (son énoncé est rappelé en section B.3.1) s’applique, de sorte que le
rayon de convergence de la série est une singularité principale, dite aussi dominante,
qui va contribuer au coefficient de z n dans F .
4 Approche combinatoire
d’où nous tirons
F (z) =
1 − z −
1 − (2z + 7z 2 )
4z
= 2z + 2z
2
+ z
3
+ 14z
4
+ 42z
5
+ 122z
6
+ 382z
7
+ 1206z
8
+3922z
9
+ 12914z
10
+ O
z
11
,
quand z tend vers 0. Le nombre d’expressions de taille n est f n = [z n ]F (z) ; ce
nombre satisfait aussi l’équation de récurrence
⎧
⎨
⎩
f 0 = 0;
f 1 = 1;
f n = f n−1 + 2
n−1
k=0 f k f n−k−1
(n ≥ 2).
S’il n’en existe pas de forme close analogue aux nombres de Catalan, nous pouvons
cependant écrire f n comme somme pondérée de coefficients binomiaux, à partir du
développement de Taylor de
1 − (2z + 7z 2 ) autour de 0 (cf. section B.3.3) ; nous
obtenons
f n =
1
2 n+2
n+1
2 ≤m≤n+1
C m−1
m
n + 1 − m
7
n+1−m .
(4.15)
Cette formule, ou la formule de récurrence donnée plus haut, sont une alternative
à la formule de Taylor pour calculer les premières valeurs de la suite (f n ). S’il
est facile de calculer un nombre important de valeurs de f n , il l’est moins d’avoir
une idée de leur comportement asymptotique lorsque n tend vers l’infini à partir de
ces valeurs numériques : à la différence des calculs que nous avons faits dans les
sections précédentes pour énumérer les arbres binaires et obtenir la moyenne ou la
variance de leur longueur de cheminement, nous ne pouvons pas obtenir pour f n
une forme comportant un nombre fixe de termes. Cependant, ce qui nous intéresse
ici est essentiellement, plus que le nombre exact d’arbres f n , son comportement
asymptotique, et un outil de choix pour cela est le lemme de transfert de Flajolet
et Odlyzko, que nous rappelons dans l’annexe B.3.6 (l’on pourra aussi se reporter
à l’article original de Flajolet et Odlyzko [90] ou aux pages 338 à 392 du livre de
Flajolet et Sedgewick [94]).
L’idée fondamentale de ce résultat est de relier le comportement asymptotique
des coefficients d’une fonction, supposée analytique dans un voisinage de l’origine,
à son comportement autour de ses singularités. Ici, nous sommes dans le cas d’une
fonction génératrice de dénombrement, à coefficients tous positifs, et le théorème
de Pringsheim (son énoncé est rappelé en section B.3.1) s’applique, de sorte que le
rayon de convergence de la série est une singularité principale, dite aussi dominante,
qui va contribuer au coefficient de z n dans F .