4.6 Exercices et problèmes
175
4.6. Soit la famille d’arbres planaires, telle que l’arité d’un nœud soit bornée par un entier
p ≥ 2. Donner le nombre moyen d’enfants d’un nœud interne dans un arbre de taille n.
4.7. Calculer le nombre d’arbres m-aires de taille n, puis le nombre de nœuds d’arité q, pour
tout q ∈ {0, . . . , p}.
4.8. Appliquer la méthode d’analyse asymptotique présentée en Section 4.2.3 pour dénombrer
les différentes familles simples d’arbres rencontrées en sections 1.2.2 ou 4.2, puis étudier le
comportement asymptotique de leur longueur de cheminement moyenne.
4.9. Pour un paramètre additif v défini sur une famille simple d’arbres, étudier comment la
fonction W (u, z) :=
τ u v(τ ) z |τ | peut servir à étudier la variance de v.
4.10. Reprendre l’analyse de la complexité de la différentiation avec l’ensemble de symboles
S = {x, +, −, ∗, /,
√ }, clos pour la dérivation. Etendre les résultats obtenus à un ensemble
quelconque S de symboles.
Problème 4.11. (Arbres planaires) Soit la famille P des arbres planaires définie en section 1.1.1.
1. Quel est le nombre moyen d’enfants de la racine dans un arbre de P de taille n ? Étudier son
comportement asymptotique pour n → +∞. Attention : il ne s’agit pas ici d’un paramètre
additif.
2. Quel est le nombre moyen de feuilles d’un arbre de P de taille n ?
3. Quel est le nombre moyen, exact et asymptotique, de nœuds simples (d’arité 1) dans un arbre
de P de taille n ?
4. Étendre le résultat précédent pour obtenir le nombre moyen, exact et asymptotique, de nœuds
d’arité p dans un arbre de P de taille n. Quelle est la proportion asymptotique du nombre moyen
de nœuds d’arité p ? Peut-on reconnaître une loi connue ?
Problème 4.12. (Arbres planaires, élections, et résultats partiels) On s’intéresse au dénombrement des possibilités lors d’une élection à deux candidats A et B, lorsque les votes (qui ont lieu
séquentiellement) sont comptabilisés dès qu’ils sont formulés ; tous les résultats intermédiaires
sont donc disponibles.
1. On suppose tout d’abord qu’il y a un nombre pair 2n de votants, et que les votes sont également
répartis sur les deux candidats (il n’y a pas de vainqueur). Soit d n le nombre d’élections
possibles, tels que A aie toujours autant ou plus de voix que B, et soit d(z) =
n≥0 d n z n
la fonction génératrice associée. Donner une formule explicite pour d(z). Pour cela, on pourra
chercher une équation de récurrence en considérant le premier instant, lors de l’élection et après
le premier vote, où les candidats A et B se retrouvent à égalité. En déduire la valeur de d n pour
n quelconque, et son comportement asymptotique.
2. Sous les mêmes hypothèses que la question précédente, on s’intéresse maintenant aux élections
dans lesquelles le candidat A a constamment au moins autant de voix que le candidat B, mais
ne gagne que par une voix. Il y aura n + 1 voix pour A et n voix pour B, soit 2n + 1 votants en
tout. Soit e n le nombre de telles élections sur 2n+1 votants, et soit e(z) =
n≥0 e n z n . Calculer
e(z). On pourra, comme pour le calcul de d(z), obtenir d’abord une équation de récurrence, ici
en regardant la dernière (ou la première) fois où les deux candidats sont à égalité. En déduire la
valeur de e n pour n quelconque.
3. Toujours en supposant un nombre pair de votants, on construit maintenant un arbre à partir
d’une suite de votes, i.e. d’un mot w ∈ {A, B} ∗ , comme suit :
– on part d’une racine, donnée ;
– on va lire le mot de gauche à droite, et construire l’arbre en parallèle ;
– lorsqu’on lit A, on crée un enfant du nœud courant et on va en cet enfant (lorsqu’un nœud a
plusieurs enfants, on considère que ceux-ci sont crées de gauche à droite) ;
– lorsqu’on lit B, on remonte du nœud courant vers son père ;
– on terminera donc la lecture à un niveau en dessous de la racine.
Par exemple, le mot AABAABAABBABBBABAAABBAB donne l’arbre
175
4.6. Soit la famille d’arbres planaires, telle que l’arité d’un nœud soit bornée par un entier
p ≥ 2. Donner le nombre moyen d’enfants d’un nœud interne dans un arbre de taille n.
4.7. Calculer le nombre d’arbres m-aires de taille n, puis le nombre de nœuds d’arité q, pour
tout q ∈ {0, . . . , p}.
4.8. Appliquer la méthode d’analyse asymptotique présentée en Section 4.2.3 pour dénombrer
les différentes familles simples d’arbres rencontrées en sections 1.2.2 ou 4.2, puis étudier le
comportement asymptotique de leur longueur de cheminement moyenne.
4.9. Pour un paramètre additif v défini sur une famille simple d’arbres, étudier comment la
fonction W (u, z) :=
τ u v(τ ) z |τ | peut servir à étudier la variance de v.
4.10. Reprendre l’analyse de la complexité de la différentiation avec l’ensemble de symboles
S = {x, +, −, ∗, /,
√ }, clos pour la dérivation. Etendre les résultats obtenus à un ensemble
quelconque S de symboles.
Problème 4.11. (Arbres planaires) Soit la famille P des arbres planaires définie en section 1.1.1.
1. Quel est le nombre moyen d’enfants de la racine dans un arbre de P de taille n ? Étudier son
comportement asymptotique pour n → +∞. Attention : il ne s’agit pas ici d’un paramètre
additif.
2. Quel est le nombre moyen de feuilles d’un arbre de P de taille n ?
3. Quel est le nombre moyen, exact et asymptotique, de nœuds simples (d’arité 1) dans un arbre
de P de taille n ?
4. Étendre le résultat précédent pour obtenir le nombre moyen, exact et asymptotique, de nœuds
d’arité p dans un arbre de P de taille n. Quelle est la proportion asymptotique du nombre moyen
de nœuds d’arité p ? Peut-on reconnaître une loi connue ?
Problème 4.12. (Arbres planaires, élections, et résultats partiels) On s’intéresse au dénombrement des possibilités lors d’une élection à deux candidats A et B, lorsque les votes (qui ont lieu
séquentiellement) sont comptabilisés dès qu’ils sont formulés ; tous les résultats intermédiaires
sont donc disponibles.
1. On suppose tout d’abord qu’il y a un nombre pair 2n de votants, et que les votes sont également
répartis sur les deux candidats (il n’y a pas de vainqueur). Soit d n le nombre d’élections
possibles, tels que A aie toujours autant ou plus de voix que B, et soit d(z) =
n≥0 d n z n
la fonction génératrice associée. Donner une formule explicite pour d(z). Pour cela, on pourra
chercher une équation de récurrence en considérant le premier instant, lors de l’élection et après
le premier vote, où les candidats A et B se retrouvent à égalité. En déduire la valeur de d n pour
n quelconque, et son comportement asymptotique.
2. Sous les mêmes hypothèses que la question précédente, on s’intéresse maintenant aux élections
dans lesquelles le candidat A a constamment au moins autant de voix que le candidat B, mais
ne gagne que par une voix. Il y aura n + 1 voix pour A et n voix pour B, soit 2n + 1 votants en
tout. Soit e n le nombre de telles élections sur 2n+1 votants, et soit e(z) =
n≥0 e n z n . Calculer
e(z). On pourra, comme pour le calcul de d(z), obtenir d’abord une équation de récurrence, ici
en regardant la dernière (ou la première) fois où les deux candidats sont à égalité. En déduire la
valeur de e n pour n quelconque.
3. Toujours en supposant un nombre pair de votants, on construit maintenant un arbre à partir
d’une suite de votes, i.e. d’un mot w ∈ {A, B} ∗ , comme suit :
– on part d’une racine, donnée ;
– on va lire le mot de gauche à droite, et construire l’arbre en parallèle ;
– lorsqu’on lit A, on crée un enfant du nœud courant et on va en cet enfant (lorsqu’un nœud a
plusieurs enfants, on considère que ceux-ci sont crées de gauche à droite) ;
– lorsqu’on lit B, on remonte du nœud courant vers son père ;
– on terminera donc la lecture à un niveau en dessous de la racine.
Par exemple, le mot AABAABAABBABBBABAAABBAB donne l’arbre