180
4 Approche combinatoire
En déduire le comportement asymptotique de n h lorsque h → +∞, puis le nombre moyen de
nœuds dans un tel arbre.
3. Montrer que la longueur de cheminement cumulée λ h satisfait la récurrence
λ h = = 2λ h−1 (v h−1 + v h−2 ) + 2λ h−2 v h−1 + 2v h−1 (n h−1 + n h−2 )
+v
2
h−1 + 2v h−2 (v h−1 + n h−1 ).
Donner le comportement asymptotique de λ h lorsque h → +∞. En divisant par le nombre
d’arbres de hauteur h, évaluer asymptotiquement la profondeur moyenne d’un nœud dans un
arbre de hauteur h.
(Ce problème est inspiré de l’article de Khizder [154].)
Problème 4.22. (Nombre d’arbres 2–3 à n feuilles) Soit e n le nombre d’arbres 2–3 à n
feuilles, et soit E(z) =
n≥0 e n z n sa fonction génératrice. Le but de ce problème est de présenter
une approche élémentaire permettant d’obtenir, sinon l’équivalent asymptotique, du moins le
comportement exponentiel des e n .
1. Montrer que E(z) satisfait la relation E(z) = z + E(z 2 + z 3 ) et en déduire la relation de
récurrence e n =
n
k=0
k
n−2k
e k , avec les valeurs initiales e 0 = 0 et e 1 = 1.
2. Soient σ (z) = z 2 + z 3 , et σ [h] la h-ième itérée de h : σ [0] (z) = z, et σ [h+1] (z) = σ (σ [h] (z)).
Montrer que l’on peut écrire formellement E(z) =
h≥0 σ [h] (z), et en tirer les premières
valeurs de e n :
E(z) = z + z
2 + z
3 + z
4 + 2 z
5 + 2 z
6 + 3 z
7 + 4 z
8 + 5 z
9 + 8 z
10 + O
z
11
.
3. Le théorème de Pringsheim assure que la singularité dominante de E(z) appartient à R + .
Montrer que, sur R + , la transformation σ a pour unique point fixe le nombre d’or φ =
1+
√
5
2 .
4. Montrer que, pour tout x ∈ [0, ρ[, σ [h] (x) → 0 quand h → +∞, et déterminer la rapidité de
convergence. En déduire que E(z) est analytique sur le disque {|z| < ρ}.
5. En établissant que, pour x réel et tendant vers ρ − , E(x) → +∞, montrer que le rayon de
convergence ρ de E(z) est exactement égal à φ. En déduire que e n est d’ordre exponentiel
φ n =
1+
√
5
2
n
.
(Cette approche est tirée du livre de Flajolet et Sedgewick [94, pp. 281–283].)
Problème 4.23. (Dénombrement des arbres de Pólya binaires)
1. Montrer que la fonction génératrice des arbres de Pólya satisfait, pour tout p ≥ 1, l’équation
P (2) (z) = 1 −
−2z +
−2z 2 + · · · +
−2z 2 p−1 +
1 − 2z 2 p − P (2) (z 2 p+1 ).
2. Montrer que le rayon de convergence ρ de la fonction P (2) (z) est solution de l’équation
P (2) (ρ) = 1
et que sa valeur numérique est ρ = 0,4026975037 . . .
3. En posant Q(z) = 1 − 2z − P (2) (z 2 ), montrer que, près de son rayon de convergence ρ,
P (2) (z) = 1 −
(z − ρ)Q
(ρ) + O((z − ρ) 2 ).
4 Approche combinatoire
En déduire le comportement asymptotique de n h lorsque h → +∞, puis le nombre moyen de
nœuds dans un tel arbre.
3. Montrer que la longueur de cheminement cumulée λ h satisfait la récurrence
λ h = = 2λ h−1 (v h−1 + v h−2 ) + 2λ h−2 v h−1 + 2v h−1 (n h−1 + n h−2 )
+v
2
h−1 + 2v h−2 (v h−1 + n h−1 ).
Donner le comportement asymptotique de λ h lorsque h → +∞. En divisant par le nombre
d’arbres de hauteur h, évaluer asymptotiquement la profondeur moyenne d’un nœud dans un
arbre de hauteur h.
(Ce problème est inspiré de l’article de Khizder [154].)
Problème 4.22. (Nombre d’arbres 2–3 à n feuilles) Soit e n le nombre d’arbres 2–3 à n
feuilles, et soit E(z) =
n≥0 e n z n sa fonction génératrice. Le but de ce problème est de présenter
une approche élémentaire permettant d’obtenir, sinon l’équivalent asymptotique, du moins le
comportement exponentiel des e n .
1. Montrer que E(z) satisfait la relation E(z) = z + E(z 2 + z 3 ) et en déduire la relation de
récurrence e n =
n
k=0
k
n−2k
e k , avec les valeurs initiales e 0 = 0 et e 1 = 1.
2. Soient σ (z) = z 2 + z 3 , et σ [h] la h-ième itérée de h : σ [0] (z) = z, et σ [h+1] (z) = σ (σ [h] (z)).
Montrer que l’on peut écrire formellement E(z) =
h≥0 σ [h] (z), et en tirer les premières
valeurs de e n :
E(z) = z + z
2 + z
3 + z
4 + 2 z
5 + 2 z
6 + 3 z
7 + 4 z
8 + 5 z
9 + 8 z
10 + O
z
11
.
3. Le théorème de Pringsheim assure que la singularité dominante de E(z) appartient à R + .
Montrer que, sur R + , la transformation σ a pour unique point fixe le nombre d’or φ =
1+
√
5
2 .
4. Montrer que, pour tout x ∈ [0, ρ[, σ [h] (x) → 0 quand h → +∞, et déterminer la rapidité de
convergence. En déduire que E(z) est analytique sur le disque {|z| < ρ}.
5. En établissant que, pour x réel et tendant vers ρ − , E(x) → +∞, montrer que le rayon de
convergence ρ de E(z) est exactement égal à φ. En déduire que e n est d’ordre exponentiel
φ n =
1+
√
5
2
n
.
(Cette approche est tirée du livre de Flajolet et Sedgewick [94, pp. 281–283].)
Problème 4.23. (Dénombrement des arbres de Pólya binaires)
1. Montrer que la fonction génératrice des arbres de Pólya satisfait, pour tout p ≥ 1, l’équation
P (2) (z) = 1 −
−2z +
−2z 2 + · · · +
−2z 2 p−1 +
1 − 2z 2 p − P (2) (z 2 p+1 ).
2. Montrer que le rayon de convergence ρ de la fonction P (2) (z) est solution de l’équation
P (2) (ρ) = 1
et que sa valeur numérique est ρ = 0,4026975037 . . .
3. En posant Q(z) = 1 − 2z − P (2) (z 2 ), montrer que, près de son rayon de convergence ρ,
P (2) (z) = 1 −
(z − ρ)Q
(ρ) + O((z − ρ) 2 ).