4.3 Tas
149
Nous pouvons maintenant obtenir une expression du nombre de tas de taille n, en
injectant dans la formule d’équerre de la Proposition 1.25, qui s’applique aux arbres
croissants, le nombre de sous-arbres de taille donnée d’un arbre parfait, qui vient de
la Proposition 4.11 ; c’est la proposition suivante.
Proposition 4.12 Le nombre de tas de taille n est, en posant L = =log 2 n
t n =
n!
L
k=1
2 k − 1
n
2 k −
1
2 .
n + 2 k − 2 k
n
2 kp
.
(4.22)
Cette expression, qui permet de calculer explicitement le nombre de tas de taille
donnée, est cependant quelque peu difficile à exploiter numériquement, et ne
permet guère de voir comment ce nombre évolue lorsque la taille croît. Nous
allons repousser son étude asymptotique à la section 4.3.2, et chercher d’abord des
expressions alternatives se prêtant mieux à des calculs numériques ou à l’évaluation
asymptotique, au moins dans des cas particuliers. Prenons d’abord le cas simple
où le tas est de taille n = 2 k+1 − 1 : l’arbre binaire sous-jacent est saturé et les
sous-arbres de la racine sont donc tous deux de taille 2 k − 1. Nous avons
t 2 k+1 −1 =
2 k+1 − 2
2 k − 1
t 2 k −1
2 .
(4.23)
Cette récurrence nous permet tout d’abord de calculer numériquement les premières
valeurs de la suite (t 2 k+1 −1 ) k≥0 : t 1 = 1, t 3 = 2, t 7 = 80, t 15 = 21964800, t 31 =
74836825861835980800000, etc. En résolvant la relation de récurrence (4.23), nous
pouvons montrer (cf. exercice 4.15, section 4.6) que
t 2 k+1 −1 =
(2 k+1 − 1)!
k+1
i=1 (2 i − 1) 2 k+1−i .
Essayons maintenant de calculer t 2 k+1 −2 . Nous établissons de même une relation de
récurrence analogue à (4.23) :
t 2 k+1 −2 =
2 k+1 − 3
2 k − 1
t 2 k −1 t 2 k −2 .
Ceci nous donne d’abord les premières valeurs numériques t 2 = 1, t 6 = 20,
t 14 = 2745600, t 30 = 4677301616364748800000. On obtient ensuite, là aussi,
une expression explicite (cf. exercice 4.16, section 4.6) :
t 2 k+1 −2 =
(2 k − 1) (2 k+1 − 3)!
2 k−1 k
i=1 (2 i − 1) 2 k+1−i .
149
Nous pouvons maintenant obtenir une expression du nombre de tas de taille n, en
injectant dans la formule d’équerre de la Proposition 1.25, qui s’applique aux arbres
croissants, le nombre de sous-arbres de taille donnée d’un arbre parfait, qui vient de
la Proposition 4.11 ; c’est la proposition suivante.
Proposition 4.12 Le nombre de tas de taille n est, en posant L = =log 2 n
t n =
n!
L
k=1
2 k − 1
n
2 k −
1
2 .
n + 2 k − 2 k
n
2 kp
.
(4.22)
Cette expression, qui permet de calculer explicitement le nombre de tas de taille
donnée, est cependant quelque peu difficile à exploiter numériquement, et ne
permet guère de voir comment ce nombre évolue lorsque la taille croît. Nous
allons repousser son étude asymptotique à la section 4.3.2, et chercher d’abord des
expressions alternatives se prêtant mieux à des calculs numériques ou à l’évaluation
asymptotique, au moins dans des cas particuliers. Prenons d’abord le cas simple
où le tas est de taille n = 2 k+1 − 1 : l’arbre binaire sous-jacent est saturé et les
sous-arbres de la racine sont donc tous deux de taille 2 k − 1. Nous avons
t 2 k+1 −1 =
2 k+1 − 2
2 k − 1
t 2 k −1
2 .
(4.23)
Cette récurrence nous permet tout d’abord de calculer numériquement les premières
valeurs de la suite (t 2 k+1 −1 ) k≥0 : t 1 = 1, t 3 = 2, t 7 = 80, t 15 = 21964800, t 31 =
74836825861835980800000, etc. En résolvant la relation de récurrence (4.23), nous
pouvons montrer (cf. exercice 4.15, section 4.6) que
t 2 k+1 −1 =
(2 k+1 − 1)!
k+1
i=1 (2 i − 1) 2 k+1−i .
Essayons maintenant de calculer t 2 k+1 −2 . Nous établissons de même une relation de
récurrence analogue à (4.23) :
t 2 k+1 −2 =
2 k+1 − 3
2 k − 1
t 2 k −1 t 2 k −2 .
Ceci nous donne d’abord les premières valeurs numériques t 2 = 1, t 6 = 20,
t 14 = 2745600, t 30 = 4677301616364748800000. On obtient ensuite, là aussi,
une expression explicite (cf. exercice 4.16, section 4.6) :
t 2 k+1 −2 =
(2 k − 1) (2 k+1 − 3)!
2 k−1 k
i=1 (2 i − 1) 2 k+1−i .