4.1 Les arbres binaires
125
Puis la formule de Stirling (rappelée dans la section B.5.1) donne le comportement
asymptotique de n! et permet d’obtenir le comportement asymptotique de C n
lorsque n → +∞. Nous résumons les résultats obtenus dans le théorème suivant :
Théorème 4.1 Les arbres binaires ont pour fonction génératrice
C(z) =
1
2z
1 −
√
1 − 4z
.
Le nombre d’arbres binaires de taille n est égal au nombre de Catalan C n :
C n =
1
n + 1
2n
n
.
Asymptotiquement lorsque n → +∞, C n ∼
4 n
n
√
πn
.
Nous avons vu en section 1.1.3 que les arbres binaires de taille n sont en bijection
avec les arbres planaires de taille n+1. Le théorème 4.1 donne alors immédiatement
le
Corollaire 4.2 Le nombre d’arbres planaires de taille n (n ≥ 1) est égal à C n−1 .
Mentionnons pour terminer un outil bien utile pour identifier une suite de
nombres entiers dont les premiers termes sont connus : l’encyclopédie en ligne des
suites entières (Online Encyclopaedia of Integer Sequences) [200]. En entrant les
premiers termes d’une suite, ici (1, 1, 2, 5, 14, 42, 132) dans le moteur de recherche
de ce site, celui-ci identifie la suite et donne les principaux résultats mathématiques
à son sujet : les termes suivants de la suite, les diverses significations combinatoires
connues avec des références à la littérature, la fonction génératrice, explicite ou
par l’intermédiaire d’une équation, la formule exacte si elle est accessible, diverses
formules satisfaites par les termes de la suite, des procédures pour calculer les
premiers termes en différents langages (en général MAPLE ou MATHEMATICA),
etc. La suite des nombres de Catalan porte le numéro A 000108, et le site donne
littéralement des dizaines de références, significations, et formules pour cette suite.
4.1.2 Longueur de cheminement
La longueur de cheminement lc(τ ) d’un arbre binaire τ a été définie dans la
section 1.3 comme la somme des profondeurs des différents nœuds de τ .
Un autre paramètre, la hauteur, fait lui aussi intervenir les profondeurs des nœuds
de l’arbre, mais en prenant leur maximum, non leur somme. Regardons d’abord un
encadrement rapide de cette hauteur. Rappelons que la profondeur de la racine d’un
arbre est égale à 0. Il est facile de donner un encadrement de la hauteur d’un arbre
125
Puis la formule de Stirling (rappelée dans la section B.5.1) donne le comportement
asymptotique de n! et permet d’obtenir le comportement asymptotique de C n
lorsque n → +∞. Nous résumons les résultats obtenus dans le théorème suivant :
Théorème 4.1 Les arbres binaires ont pour fonction génératrice
C(z) =
1
2z
1 −
√
1 − 4z
.
Le nombre d’arbres binaires de taille n est égal au nombre de Catalan C n :
C n =
1
n + 1
2n
n
.
Asymptotiquement lorsque n → +∞, C n ∼
4 n
n
√
πn
.
Nous avons vu en section 1.1.3 que les arbres binaires de taille n sont en bijection
avec les arbres planaires de taille n+1. Le théorème 4.1 donne alors immédiatement
le
Corollaire 4.2 Le nombre d’arbres planaires de taille n (n ≥ 1) est égal à C n−1 .
Mentionnons pour terminer un outil bien utile pour identifier une suite de
nombres entiers dont les premiers termes sont connus : l’encyclopédie en ligne des
suites entières (Online Encyclopaedia of Integer Sequences) [200]. En entrant les
premiers termes d’une suite, ici (1, 1, 2, 5, 14, 42, 132) dans le moteur de recherche
de ce site, celui-ci identifie la suite et donne les principaux résultats mathématiques
à son sujet : les termes suivants de la suite, les diverses significations combinatoires
connues avec des références à la littérature, la fonction génératrice, explicite ou
par l’intermédiaire d’une équation, la formule exacte si elle est accessible, diverses
formules satisfaites par les termes de la suite, des procédures pour calculer les
premiers termes en différents langages (en général MAPLE ou MATHEMATICA),
etc. La suite des nombres de Catalan porte le numéro A 000108, et le site donne
littéralement des dizaines de références, significations, et formules pour cette suite.
4.1.2 Longueur de cheminement
La longueur de cheminement lc(τ ) d’un arbre binaire τ a été définie dans la
section 1.3 comme la somme des profondeurs des différents nœuds de τ .
Un autre paramètre, la hauteur, fait lui aussi intervenir les profondeurs des nœuds
de l’arbre, mais en prenant leur maximum, non leur somme. Regardons d’abord un
encadrement rapide de cette hauteur. Rappelons que la profondeur de la racine d’un
arbre est égale à 0. Il est facile de donner un encadrement de la hauteur d’un arbre