176
4 Approche combinatoire
Donnez l’arbre associé au mot suivant :
w = AABAABABABBABBAAAABABBABAABBABB;
Quels types d’arbres obtient-on ? Y a-t-il bien une bijection entre les mots considérés et cette
classe d’arbres ? Ceci permet-il de retrouver la valeur de e n obtenue à la question précédente ?
Problème 4.13. (Arbres planaires et expressions bien parenthésées) On s’intéresse dans ce
problème au nombre de manières de construire une expression bien parenthésée, obtenue à partir
des règles suivantes :
(a) L’expression x est bien parenthésée.
(b) Si σ 1 , σ 2 , . . . , σ k sont des expressions bien parenthésées, avec k ≥ 2, alors (σ 1 )(σ 2 ) . . . (σ k )
est une expression bien parenthésée.
(c) Les seules expressions bien parenthésées sont obtenues par les deux règles ci-dessus.
Par exemple, (x)(x), ((x)(x)(x))(x) et ((x)(x))(x)(((x)(x))(x)) sont des expressions bien
parenthésées, mais non (x) ou ((x)(x)).
On définit la taille d’une expression bien parenthésée comme le nombre d’occurrences de la
variable x qu’elle contient.
1. Proposer une représentation arborescente des expressions bien parenthésées, et donner les
arbres correspondant aux trois expressions données en exemple.
2. Soit s n le nombre d’expressions bien parenthésées de taille n, et soit S(z) :=
n s n z n la
fonction génératrice associée. Montrer que S(z) satisfait une équation algébrique de degré 2, et
résoudre cette équation.
3. Montrer que S(z) vérifie l’équation différentielle linéaire
(1 − 6z + z
2 ) S
(z) + (3 − z) S(z) = 1 − z.
En tirer une relation de récurrence linéaire entre s n , s n+1 et s n+2 .
4. En récrivant l’équation algébrique définissant S(z) sous la forme S(z) = zz(S(z)), pour une
fonction convenable, puis en utilisant la formule de Lagrange, donner une expression des s n
sous forme de somme simple.
5. Quel est le comportement asymptotique des s n lorsque n → +∞ ?
4.14. Étudier la loi de probabilité P W sur les tas de taille n = 4, obtenue en construisant les
tas par insertions successives des clés dans un tas initialement vide selon l’algorithme de Williams
(cf. la section A.6.3).
4.15. Soit u k le nombre de tas de taille 2 k − 1. Montrer que u k+1 =
2 k+1 −2
2 k −1
(u k ) 2 , puis en
tirer une forme close de u k . On pourra considérer log(u k /(2 k − 1)).
4.16. On pose maintenant v k égal au nombre de tas de taille 2 k − 2. Avec les notations de
l’exercice précédent, montrer que v k+1 =
2 k+1 −3
2 k −1
u k v k , puis donner une forme close de v k .
Problème 4.17. (Asymptotique du nombre de tas de taille n) Le but est de démontrer le
théorème 4.14, en reprenant l’évaluation de f n = log(n!/t n ) proposée dans la démonstration de la
4 Approche combinatoire
Donnez l’arbre associé au mot suivant :
w = AABAABABABBABBAAAABABBABAABBABB;
Quels types d’arbres obtient-on ? Y a-t-il bien une bijection entre les mots considérés et cette
classe d’arbres ? Ceci permet-il de retrouver la valeur de e n obtenue à la question précédente ?
Problème 4.13. (Arbres planaires et expressions bien parenthésées) On s’intéresse dans ce
problème au nombre de manières de construire une expression bien parenthésée, obtenue à partir
des règles suivantes :
(a) L’expression x est bien parenthésée.
(b) Si σ 1 , σ 2 , . . . , σ k sont des expressions bien parenthésées, avec k ≥ 2, alors (σ 1 )(σ 2 ) . . . (σ k )
est une expression bien parenthésée.
(c) Les seules expressions bien parenthésées sont obtenues par les deux règles ci-dessus.
Par exemple, (x)(x), ((x)(x)(x))(x) et ((x)(x))(x)(((x)(x))(x)) sont des expressions bien
parenthésées, mais non (x) ou ((x)(x)).
On définit la taille d’une expression bien parenthésée comme le nombre d’occurrences de la
variable x qu’elle contient.
1. Proposer une représentation arborescente des expressions bien parenthésées, et donner les
arbres correspondant aux trois expressions données en exemple.
2. Soit s n le nombre d’expressions bien parenthésées de taille n, et soit S(z) :=
n s n z n la
fonction génératrice associée. Montrer que S(z) satisfait une équation algébrique de degré 2, et
résoudre cette équation.
3. Montrer que S(z) vérifie l’équation différentielle linéaire
(1 − 6z + z
2 ) S
(z) + (3 − z) S(z) = 1 − z.
En tirer une relation de récurrence linéaire entre s n , s n+1 et s n+2 .
4. En récrivant l’équation algébrique définissant S(z) sous la forme S(z) = zz(S(z)), pour une
fonction convenable, puis en utilisant la formule de Lagrange, donner une expression des s n
sous forme de somme simple.
5. Quel est le comportement asymptotique des s n lorsque n → +∞ ?
4.14. Étudier la loi de probabilité P W sur les tas de taille n = 4, obtenue en construisant les
tas par insertions successives des clés dans un tas initialement vide selon l’algorithme de Williams
(cf. la section A.6.3).
4.15. Soit u k le nombre de tas de taille 2 k − 1. Montrer que u k+1 =
2 k+1 −2
2 k −1
(u k ) 2 , puis en
tirer une forme close de u k . On pourra considérer log(u k /(2 k − 1)).
4.16. On pose maintenant v k égal au nombre de tas de taille 2 k − 2. Avec les notations de
l’exercice précédent, montrer que v k+1 =
2 k+1 −3
2 k −1
u k v k , puis donner une forme close de v k .
Problème 4.17. (Asymptotique du nombre de tas de taille n) Le but est de démontrer le
théorème 4.14, en reprenant l’évaluation de f n = log(n!/t n ) proposée dans la démonstration de la