124
4 Approche combinatoire
Les constructions + (union disjointe) et (◦ × A × B) (produit de trois termes,
dont le premier est réduit à un atome) sont admissibles et se traduisent directement
sur les fonctions génératrices, respectivement en somme et en produit ; la fonction
génératrice de la classe neutre restreinte à l’arbre vide est la constante 1 ; celle de la
classe atomique restreinte à la racine ◦ est z, et nous obtenons directement
C(z) = 1 + z × C(z) × C(z),
soit l’équation (4.3). Celle-ci se résout aisément (le choix entre les deux racines se
fait en tenant compte de C(0) = C 0 = 1) :
C(z) =
1
2z
(1 −
√
1 − 4z).
(4.4)
Nous avons maintenant, outre la récurrence (4.2), une deuxième façon de calculer
les nombres C n : ce sont les coefficients de la fonction C(z).
Nous utilisons la notation [z n ]C(z) pour désigner le n-ième coefficient de C(z) ;
ainsi C n = [z n ]C(z).
Nous obtenons facilement les premières valeurs des nombres C n , comme
coefficients du développement de Taylor de C(z) autour de l’origine ; nous en
donnons ci-dessous les dix premiers termes :
C(z) = 1 + z + 2 z
2
+ 5 z
3
+ 14 z
4
+ 42 z
5
+ 132 z
6
+ 429 z
7
+1430 z
8
+ 4862 z
9
+ 16796 z
10
+ O
z
11
.
Ainsi sont obtenus les nombres de Catalan, nombres classiques en combinatoire 1 :
à partir de l’expression de C(z) donnée par (4.4), le développement en série entière
de
√
1 − 4z fournit
[z
n
]
−
1
2z
√
1 − 4z
=
(2n)!
n!(n + 1)!
(4.5)
de sorte que
C n =
(2n)!
n!(n + 1)!
=
1
n + 1
2n
n
.
1 Cette dénomination est due, non à une origine au sud des Pyrénées, mais à la mémoire de
C.E. Catalan, qui démontra vers le milieu du 19-ième siècle la formule donnant leur fonction
génératrice ; cf. le livre de Flajolet et Sedgewick [94, p. 20], où l’on trouvera également des
indications sur la « préhistoire » de ces nombres.