Quelques techniques analytiques pour l’étude asymptotique des paramètres dans les arbres

Helmut Prodinger

Department of Algebra and Discrete Mathematics Technical University of Vienna Wiedner Hauptstraße 8–10 A–1040, Vienna, Austria

Written for the Proceedings of the Summerschool in Ile de Ré 1983 Retyped 1991

1. Introduction

La structure d’arbre est l’une des structures de données les plus répandues en informatique. Les algorithmes de manipulation d’arbres sont ainsi très nombreux. L’analyse de ces algorithmes au sens de Knuth nous conduit souvent à des problèmes combinatoires de dénombrement des configurations; l’étape suivante consiste en l’analyse asymptotique de ces dénombrements. Voir par exemple [4], [15], [16].

L’étude de Flajolet et Odlyzko [7] est paradigme pour un point de vue un peu différent: Au lieu d’éxtraire des coefficients de fonctions génératrices et d’approximer ceux-ci avec des méthodes de l’analyse réelle, on étudie des singularités des series génératrices. Plus précisement on recherche à établir un développement asymptotique de la fonction autour de la singularité la plus proche de l’origine; ensuite des lemmes de traduction permettent de traduire ce développement en un développement asymptotique des coefficients de Taylor de la série génératrice en question. Par exemple, si f(z) = ∑_{n≥0} f_{n}z^{n} a sa singularité la plus proche de l’origine en 1, avec

f(z) ∼ A − B\sqrt{1 − z} + …,

on déduit que

[z^{n}] f(z) := f_{n} ∼ \frac{B}{2\sqrt{π}} n^{−3/2}.

De même, si l’on a

f(z) ∼ −A log(1 − z) + …,

alors

[z^{n}]f(z) ∼ \frac{A}{n}, etc.

Enfin, plus on connait de termes du développement de la série génératrice, plus on a de termes du développement des coefficients de Taylor.

Cette traduction est un processus assez automatique. Le problème principal est de trouver le développement autour de la (des) singularité(s). Dans de nombreux

Typeset by AMS-TEX

cas, on peut se servir de la transformation de Mellin, méthode très populaire dans l’école française d’algorithmes.

Le but de ce travail est d’expliquer cette stratégie générale dans trois cas particuliers: le problème d’allocation de registres et d’évaluation d’expressions arithmétiques; puis la hauteur des feuilles dans les arbres planaires. Enfin, le troisième problème est la recherche de la valeur asymptotique d’une certaine expression (très similaire au cas de registres); cette valeur est intéressante dans l’analyse d’un algorithme de tri (voir [6], [21]).

Avant de s’engager dans des détails techniques, on formule quelques points fondamentaux:

La classe B des arbres binaires est définissable récursivement par l’équation (symbolique) qui traduit qu’un arbre binaire est soit l’arbre formé d’un seul sommet externe (“feuille”), soit l’arbre formé d’une racine et de deux arbres qui sont les sousarbres gauche et droite de la racine. Soit B(z) = ∑_{n≥0} b_{n}z^{n} la série génératrice des arbres binaires où b_{n} est le nombre d’arbres binaires de taille n (la taille d’un arbre binaire est mesurée par le nombre de ses sommets internes); on a immediatement

B(z) = 1 + z (B(z))^{2} ,

d’où

B(z) = \frac{1 − \sqrt{1 − 4z}}{2z} et b_{n} = \frac{1}{n + 1}\binom{2n}{n}.

Les nombres b_{n} sont les nombres de Catalan.

De manière analogue, la famille P des arbres planaires est définie par d’où on tire pour la série génératrice P (z) = ∑_{n≥1} t_{n}z^{n} des arbres planaires

P (z) = \frac{z}{1 − P (z)} et donc P (z) = \frac{1 − \sqrt{1 − 4z}}{2} et t_{n} = \frac{1}{n}\binom{2n − 2}{n − 1}.

Dans les deux cas, la singularité mentionnée est z = \frac{1}{4}, et

B(z) ∼ 2 − 2\sqrt{1 − 4z}, donc b_{n} ∼ \frac{1}{\sqrt{π}} 4^{n}n^{−3/2}

respectivement

P (z) ∼ \frac{1}{2} − \frac{1}{2}\sqrt{1 − 4z}, donc t_{n} ∼ \frac{1}{\sqrt{π}} 4^{n−1}n^{−3/2}.

2. Le nombre moyen de registres pour evaluer un arbre binaire de taille n

Avant de commencer notre traitement, citons les références sur ce sujet: [4], [5], [8], [11], [17], [19]. On s’abstiendra de présenter ici une description de la problématique informatique. A cet effet on renvoie à la thèse de P.Flajolet [4].

La fonction “nombre de registres” reg est donnée recursivement par

reg(□) = 0

reg ( ) = \{ \begin{matrix}max\{reg(t_{1}), reg(t_{2})\} & si reg(t_{1}) ≠ reg(t_{2}) \\ 1 + reg(t_{1}) & sinon . \end{matrix}

Le problème est l’étude de R_{n}, la valeur moyenne de la fonction reg, relativement à l’ensemble des arbres binaires de taille n. On a

R_{n} = \frac{1}{b_{n}} · [z^{n}]E(z),

avec

E(z) = ∑_{n≥0} z^{n} ∑_{t de taille n} reg(t).

Soit R_{p} la famille des arbres t avec reg(t) = p. De la définition de reg on déduit facilement :

Soit S_{p} la famille des arbres t avec reg(t) ≥ p, c’est à dire

S_{p} = R_{p} + R_{p+1} + ….

On peut écrire

∑_{j<p−1} R_{j} = B⧹S_{p−1}.

On obtient une récurrence pour les familles S_{p} d’une manière tout à fait semblable:

Les fonctions S_{p}(z) sont définies par

S_{p}(z) := ∑_{n≥0} z^{n} ∑_{t de taille n, reg(t)≥p} 1.

Il est clair que

E(z) = ∑_{p≥1} S_{p}(z).

Les fonctions S_{p}(z) sont décrites par les récurrences immédiates

S_{0} = B; S_{p} = zS_{p−1}^{2} + 2zS_{p} (B − S_{p−1}) .

Il est commode de définir ε := \sqrt{1 − 4z} et z = u/(1 + u)^{2}. D’où

S_{p} = \frac{zS_{p−1}^{2}}{1 − 2zB + 2zS_{p−1}} ,

c’est à dire

\frac{1}{S_{p}} = \frac{ε}{zS_{p−1}^{2}} + \frac{2}{S_{p−1}} .

Ce qui conne finalement

\begin{aligned}1 + \frac{ε}{z} \frac{1}{S_{p}} & = 1 + \frac{ε^{2}}{z^{2}S_{p−1}^{2}} + \frac{2ε}{z} \frac{1}{S_{p−1}} = (1 + \frac{ε}{z} · \frac{1}{S_{p−1}} )^{2} \\ & = ⋯ = (1 + \frac{ε}{z} · \frac{1}{S_{0}} )^{2^{p}} . \end{aligned}

On en déduit l’équation

S_{p} = \frac{ε}{z} ((1 + \frac{ε}{zB} )^{2^{p}} − 1)^{−1} .

On voit tout de suite que

\frac{ε}{z} = \frac{1 − u^{2}}{u} , et 1 + \frac{ε}{zB} = \frac{1}{u},

donc

S_{p} = \frac{1 − u^{2}}{u} \frac{1}{u^{−2^{p}} − 1} = \frac{1 − u^{2}}{u} \frac{u^{2^{p}}}{1 − u^{2^{p}}} .

La fonction E(z) a donc pour expression

E(z) = \frac{1 − u^{2}}{u} ∑_{p≥1} \frac{u^{2^{p}}}{1 − u^{2^{p}}}

= \frac{1 − u^{2}}{u} ∑_{p≥1} ∑_{λ≥1} u^{λ2^{p}}

= \frac{1 − u^{2}}{u} ∑_{n≥2} v_{2}(n)u^{n},

où v_{2}(n) est l’exposant de 2 dans la décomposition de n en facteurs premiers:

v_{2}(n) = ∑_{n=λ2^{p}, λ,p≥1} 1.

Si on écrit, d’une manière unique, n = 2^{m}(1 + 2i), (m ≥ 1, i ≥ 0), on a

v_{2}(n) = ∑_{p=1}^{m} 1 = m.

On appelle souvent la quantité v_{2}(n) “valuation dyadique”, pour des raisons évidentes. Comme il était annoncé dans l’introduction, on va démontrer ultérieurement que l’on a dans un voisinage de z = \frac{1}{4} (c’est à dire u = 1):

E(z) ∼ 2ε log_{2} ε + Aε + 4 ∑_{k≠0} c_{k}ε^{1−χ_{k}} + …,

avec

A = 3 − 2 log_{2} 2π + \frac{2γ}{log 2}, (γ est la constante d’Euler)

et

χ_{k} = \frac{2kπi}{log 2} et c_{k} = \frac{1}{log 2}Γ(χ_{k})ζ(χ_{k})

(Γ est la fonction gamma d’Euler, ζ est la fonction zeta de Riemann).

Mentionnons le développement suivant ([10])

[z^{n}] log(1 − z)(1 − z)^{α} ∼ \frac{−n^{−α−1} log n}{Γ(−α)} + n^{−α−1} \frac{Γ(−α)}{(Γ(−α))^{2}} ,

ce qui nous donne en particulier

[z^{n}] ε log ε ∼ \frac{1}{2}4^{n}n^{−3/2} (\frac{log n}{2\sqrt{π}} + \frac{γ + 2 log 2 − 2}{2\sqrt{π}}) .

On utilise également le résultat

[z^{n}] ε^{1−χ_{k}} ∼ 4^{n}n^{(χ_{k}−3)/2}/Γ (\frac{χ_{k} − 1}{2}) .

Observons alors qu’on peut simplifier l’expression

c_{k}/Γ (\frac{χ_{k} − 1}{2}) = \frac{ζ(χ_{k})Γ(\frac{χ_{k}}{2} )(χ_{k} − 1)}{4\sqrt{π} log 2};

pour cela on utilise la formule de duplication de Legendre-Gauss (voir p.e. [2])

Γ (\frac{z}{2}) Γ (\frac{z + 1}{2}) = \sqrt{π}2^{1−z}Γ(z).

Enfin, si l’on collecte tous les ingrédients, on trouve

[z^{n}] E(z) ∼ \frac{4^{n}n^{−3/2}}{2\sqrt{π} log 2} (log n + γ + 2 log 2 − 2)

− A\frac{4^{n}}{2\sqrt{π}} n^{−3/2} + ∑_{k≠0} \frac{4^{n}n^{(χ_{k}−3)/2}ζ(χ_{k})Γ(χ_{k}/2)(χ_{k} − 1)}{\sqrt{π} log 2}.

Si on prend en considération que

b_{n} ∼ \frac{4^{n}}{\sqrt{π}} n^{−3/2}  et  n^{χ_{k}/2} = ε^{log_{4} n·2kπi},

on obtient Theorème 1. Le nombre moyen R_{n} de registres nécessaires à l’évaluation d’un arbre de taille n verifie

R_{n} = log_{4} n + D(log_{4} n) + o(1),

où D(x) est une fonction continue périodique de période 1; cette fonction peut être développée en série de Fourier

D(x) = ∑_{k∈ℤ} d_{k}e^{2kπix},

avec

d_{0} = \frac{1}{2} − \frac{γ}{2 log 2} − \frac{1}{log 2} + log_{2} π

et

d_{k} = \frac{1}{log 2}ζ(χ_{k})Γ(\frac{χ_{k}}{2} )(χ_{k} − 1), k ≠ 0, χ_{k} = \frac{2kπi}{log 2}.

Le reste de ce chapitre est consacré à la découverte du développement de la fonction E(z).

Pour étudier E(z) pour z → \frac{1}{4}, i.e. pour u → 1, on pose u = e^{−t} et on considère E(z) pour t → 0. On obtient facilement que

\frac{1 − u^{2}}{u} ∼ 2t + ….

Passons au deuxième facteur de E(z), dénoté par V (t); la transformation de Mellin de V (t) est notée V^{∗}(s):

V (t) = ∑_{k≥1} v_{2}(k)e^{−kt}; V^{∗}(s) = ∫_{0}^{∞} x^{s−1}V (x)dx

V^{∗}(s) = ∫_{0}^{∞} x^{s−1} ∑_{k≥1} v_{2}(k)e^{−kx}dx

= ∑_{k≥1} v_{2}(k)k^{−s} ∫_{0}^{∞} x^{s−1}e^{−x}dx

On a

∑_{k≥1} v_{2}(k)k^{−s} = 2^{−s} ∑_{k≥1} v_{2}(2k)k^{−s} = 2^{−s} ∑_{k≥1} [1 + v_{2}(k)]k^{−s},

donc

V^{∗}(s) = \frac{Γ(s)ζ(s)}{2^{s} − 1}.

La formule d’inversion de Mellin nous donne

V (t) = \frac{1}{2πi} ∫_{2−i∞}^{2+i∞}V^{∗}(s)t^{−s}ds.

On peut déplacer le chemin d’intégration vers la gauche, en prenant en compte les résidues de l’intégrande V^{∗}(s)t^{−s}. Il y a des pôles en s = 1 (provenant de la fonction ζ de Riemann) , en s = 0, −1, −2, … (provenant de la fonction Γ) et en s = χ_{k}, k ∈ ℤ (de (2^{s} − 1)^{−1}). On utilise des développements classiques et on trouve

V (t) ∼ \frac{1}{t} + \frac{1}{2} log_{2} t − \frac{1}{2} log_{2} 2π + \frac{1}{4} + \frac{γ}{2 log 2}

+ \frac{1}{log 2} ∑_{k≠0} Γ(χ_{k})ζ(χ_{k})t^{−χ_{k}} + …

ce qui donne la formule annoncée pour E(z), après avoir multiplié les deux derniers développements et en notant que

t ∼ 2ε + ….

3. Un probleme similaire: La fusion paire-impaire

Dans l’analyse d’un algorithme de tri (fusion paire-impaire) on doit considérer la quantité

B_{n} = ∑_{k≥1} \begin{matrix}( & {2n \atop n−k} & ) \\ ( & {2n \atop n} & ) \end{matrix}(2F (k) + k),

représentant le nombre d’échanges dans la fusion paire-impaire de 2n éléments. Dans cette égalité,

F (k) = ∑_{0≤j<k} f(j)

et f(j) est le nombre des chiffres “1” dans la représentation de j en code de Gray (voir [6], [21]). On trouve ci-dessous les premiers nombres dans cette représentation:

0  0  1100  8
1  1  1101  9
11  2  1111 10
10  3  1110 11
110  4  1010 12
111  5  1011 13
101  6  1001 14
100  7  1000 15
11000 16

Les nombres

ϑ(j) := f(j) − f(j − 1)

sont ègaux à ±1: si k est de la forme k = 2^{m}(4i + 1), ϑ(k) = 1; si k est de la forme k = 2^{m}(4i + 3), ϑ(k) = −1. On peut constater une grande similarité entre ϑ(k) et v_{2}(k) du chapitre 2. La série génératrice de Dirichlet de la suite ϑ(k) est

∑_{k≥1} ϑ(k)k^{−s} = ∑_{m≥0} ∑_{i≥0} 2^{−ms}(4i + 1)^{−s} − ∑_{m≥0} ∑_{i≥0} 2^{−ms}(4i + 3)^{−s}

= \frac{1}{1 − 2^{−s}} · \frac{1}{4^{s}} (ζ(s, \frac{1}{4}) − ζ(s, \frac{3}{4})) ,

où la fonction ζ(s, a) de Hurwitz est définie par

ζ(s, a) = ∑_{n≥0}(n + a)^{−s} pour ℜ(s) > 1.

On peut écrire

B_{n} = \frac{n}{2} + \frac{2}{\binom{2n}{n}}C_{n},

avec

C_{n} = ∑_{k≥1} F (k)\binom{2n}{n − k}.

On veut trouver une fonction analogue à E(z) (chapitre 2). Donc on écrit

C_{n} = ∑_{k≥1} F (k) [u^{n−k}] (1 + u)^{2n}

= [u^{n}] ∑_{k≥1} F (k)u^{k}(1 + u)^{2n}

= [u^{n}] ∑_{k≥1} ∑_{0≤j<k} f(j) u^{k}(1 + u)^{2n}

= [u^{n}] ∑_{j≥0} f(j)u^{j} \frac{u}{1 − u}(1 + u)^{2n}

= [u^{n}] ∑_{j≥0} ∑_{0≤i≤j} ϑ(i)u^{j} \frac{u}{1 − u}(1 + u)^{2n}

= [u^{n}] ∑_{i≥0} ϑ(i)u^{i} \frac{u}{(1 − u)^{2}} (1 + u)^{2n}.

En général, si on a une série Ψ(z), et si on pose z = u/(1 + u)^{2}, on a d’après le theorème de Cauchy

[z^{n}] Ψ(z) = \frac{1}{2πi} ∮ \frac{dz}{z^{n+1}} Ψ(z)

= \frac{1}{2πi} ∮ \frac{du(1 − u)}{(1 + u)^{3}} \frac{(1 + u)^{2n+2}}{u^{n+1}} Ψ(\frac{u}{(1 + u)^{2}} )

= [u^{n}] (1 − u)(1 + u)^{2n−1}Ψ(\frac{u}{(1 + u)^{2}} ).

C’est pourquoi on peut écrire

C_{n} = [u^{n}] \frac{u(1 + u)}{(1 − u)^{3}} ∑_{i≥1} ϑ(i)u^{i}.

La fonction dans le membre droit de cette égalité est l’analogue de E(z) du chapitre 2. On trouve facilement, que

\frac{u(1 + u)}{(1 − u)^{3}} ∼ \frac{2}{t^{3}} + ….

Soit

V (t) = ∑_{k≥1} ϑ(k)e^{−kt},

d’où

V^{∗}(s) = Γ(s) · \frac{1}{2^{s}} · \frac{1}{2^{s} − 1} (ζ(s, \frac{1}{4}) − ζ(s, \frac{3}{4})) .

Par conséquant

V (t) = \frac{1}{2πi} ∫_{2−i∞}^{2+i∞}Γ(s) · \frac{1}{2^{s}} · \frac{1}{2^{s} − 1} (ζ(s, \frac{1}{4}) − ζ(s, \frac{3}{4})) t^{−s}dt.

La différence des fonctions de Hurwitz est une fonction entière; l’intégrande a des pôles en s = χ_{k} et s = 0, −1, −2, …. On a (voir [22])

ζ(s, \frac{1}{4}) − ζ(s, \frac{3}{4}) ∼ \frac{1}{2} + s (2 log Γ(\frac{1}{4}) − \frac{1}{2} log 2 − log π) + …

pour s → 0. De même,

Γ(s) ∼ \frac{1}{s} − γ + …

\frac{1}{2^{s} − 1} ∼ \frac{1}{log 2} · \frac{1}{s} − \frac{1}{2} + …

(2t)^{−s} ∼ 1 − s · log(2t) + …

ce qui nous donne le résidu en s = 0

−\frac{5}{4} − \frac{γ}{2 log 2} + 2 log_{2} Γ(\frac{1}{4}) − log_{2} π − \frac{1}{2} log_{2} t.

Le résidu en s = χ_{k} pour k ≠ 0 est simplement

\frac{1}{log 2}Γ(χ_{k}) (ζ(χ_{k}, \frac{1}{4}) − ζ(χ_{k}, \frac{3}{4})) t^{−χ_{k}}.

On peut simplifier, puisque

ζ(χ_{k}, \frac{3}{4}) = −ζ(χ_{k}, \frac{1}{4}).

Donc, on obtient

C_{n} ∼ [z^{n}] \frac{2}{t^{3}} ( − \frac{1}{2} log_{2} t − \frac{5}{4} − \frac{γ}{2 log 2} + 2 log_{2} Γ(\frac{1}{4}) − log_{2} π

+ \frac{2}{log 2} ∑_{k≠0} Γ(χ_{k})ζ(χ_{k}, \frac{1}{4})t^{−χ_{k}}),

où, avec t ∼ 2ε

C_{n} ∼ [z^{n}] ( − \frac{1}{8}ε^{−3} log_{2} ε − ε^{3}(\frac{7}{16} + \frac{γ}{8 log 2} − \frac{1}{2} log_{2} Γ(\frac{1}{4}) + \frac{1}{4} log_{2} π)

+ \frac{1}{2 log 2} ∑_{k≠0} Γ(χ_{k})ζ(χ_{k}, \frac{1}{4})ε^{−3−χ_{k}}).

On trouve, comme au chapitre 2,

[z^{n}] ε^{3} log ε ∼ \frac{4^{n}\sqrt{n}}{\sqrt{π}}( − log n + (2 − γ − 2 log 2)),

[z^{n}] ε^{−3} ∼ \frac{2 · 4^{n}\sqrt{n}}{\sqrt{π}},

[z^{n}] ε^{−3−χ_{k}} ∼ 4^{n} \frac{n^{(1+χ_{k})/2}}{Γ (\frac{3+χ_{k}}{2} )} .

En regroupant les résultats précédents, on obtient

C_{n} ∼ \frac{4^{n}\sqrt{n}}{\sqrt{π}} log n · \frac{1}{8 log 2}

+ \frac{4^{n}\sqrt{n}}{\sqrt{π}} (−\frac{1}{4 log 2} − \frac{γ}{8 log 2} − \frac{5}{8} + log_{2} Γ(\frac{1}{4}) − \frac{1}{2} log_{2} π)

+ \frac{1}{2}4^{n}\sqrt{n}\frac{1}{log 2} ∑_{k≠0} Γ(χ_{k})ζ(χ_{k}, \frac{1}{4})\frac{n^{χ_{k}/2}}{Γ (\frac{3+χ_{k}}{2} )}.

On a par la formule de duplication

Γ(χ_{k})/Γ (\frac{3 + χ_{k}}{2} ) = \frac{1}{1 + χ_{k}} \frac{1}{\sqrt{π}} Γ (\frac{χ_{k}}{2} ) .

Avec

\binom{2n}{n} ∼ \frac{4^{n}n^{−1/2}}{\sqrt{π}} ,

on obtient

\frac{D_{n}}{\binom{2n}{n}} · \frac{1}{n} ∼ \frac{1}{8} log_{2} n

− \frac{1}{4 log 2} − \frac{γ}{8 log 2} − \frac{5}{8} + log_{2} Γ(\frac{1}{4}) − \frac{1}{2} log_{2} π

+ \frac{1}{2 log 2} ∑_{k≠0} ζ(χ_{k}, \frac{1}{4})\frac{Γ(χ_{k}/2)}{1 + χ_{k}}n^{χ_{k}/2}.

Finalement on a trouvé le

Theorème 2. Le nombre moyen d’échanges dans la fusion paire-impaire de 2n éléments vérifie

B_{n} ∼ \frac{1}{4}n log_{2} n + nB( log_{4} n),

ou B(x) est une fonction continue périodique de période 1; cette fonction peut être développée en série de Fourier

B(x) = ∑_{k∈ℤ} b_{k}e^{2kπix},

avec

b_{0} = −\frac{1}{2 log 2} − \frac{γ}{4 log 2} − \frac{3}{4} + 2 log_{2} Γ(\frac{1}{4}) − log_{2} π

et pour k ≠ 0

b_{k} = \frac{1}{log 2}ζ(χ_{k}, \frac{1}{4})\frac{Γ(χ_{k}/2)}{1 + χ_{k}}.

4. La hauteur des feuilles dans les arbres planaires

On peut comprendre la problématique de ce chapitre très simplement en considérant l’example d’un arbre planaire:

Cet arbre a 4 feuilles de hauteur (de gauche à droite) 3, 3, 4, 2. Nous remarquons que la hauteur de l’arbre est donnée par la hauteur de la feuille la plus haute. Nous imaginons maintenant que les feuilles sont ordonnées par ordre décroissant de leurs hauteurs. Dans notre exemple, la suite des hauteurs de feuilles est ainsi 4, 3, 3, 2. Remarquons qu’il peut y avoir plusieurs feuilles de même hauteur. Pour faciliter les calculs, nous complétons cette suite par une infinité de zéros. Ainsi, nous pouvons parler de la d-ième feuille pour n’importe quel d, même si l’arbre a moins de d feuilles.

On considère maintenant h_{n}^{(d)}, la hauteur de la d-ième feuille en remarquant encore une fois que h_{n}^{(1)} est simplement la hauteur moyenne d’un arbre de taille n.

Quelques lemmes techniques apparaissent déjà dans divers articles, voir [1], [12], [13], [14], [20].

Lemme 1. Soit F (z, y) la série génératrice telle que [z^{n}y^{m}] F soit le nombre d’arbres de taille n avec m feuilles (l’arbre ∘ a zéro feuilles); on a alors pour tout p ≥ 0

F^{p}(z, y) = z^{p} + p ∑_{0≤λ<n} z^{n}y^{n−λ} \frac{1}{n}\binom{n}{λ}\binom{n − p − 1}{λ − p}.

Idée de la demonstration. (Voir [12]) On introduit G(z, y), la quantité analogue, où on considère que ∘ a une feuille; en traduisant l’équation symbolique pour les arbres planaires, on obtient

G(z, y) = z(y + ∑_{r≥1} G^{r}(z, y)) = (1 − z(1 − y))P (\frac{zy}{(1 − z(1 − y))^{2}} ) .

On utilise le développement classique

P^{m}(z) = ∑_{k≥0} [\binom{2k + m − 1}{k} − \binom{2k + m − 1}{k − 1}] z^{k+m}.

Après avoir utilisé deux fois le théorème binomial, on se sert de l’ identité

∑_{k≥0} \binom{r}{k}\binom{s + k}{p}(−1)^{k} = (−1)^{r}\binom{s}{p − r}

pour obtenir

G^{p}(z, y) = z^{p}y^{p} + p ∑_{p≤λ≤n} z^{n}y^{λ} \frac{1}{n}\binom{n}{λ}\binom{n − p − 1}{λ − p}.

Enfin, on peut constater que

F (z, y) = G(z, y) − zy + z = G(zy, y^{−1}),

d’où la formule annoncée.

Lemme 2. Soit A_{k}(z) la série génératrice des arbres de hauteur ≤ k et, comme précédemment, z = u/(1 + u)^{2}. On a

A_{k}(z) = \frac{u}{1 + u} · \frac{1 − u^{k}}{1 − u^{k+1}} .

Démonstration. En traduisant l’équation symbolique pour la famille P, on obtient

A_{k} = \frac{z}{1 − A_{k−1}} , k ≥ 1, A_{0} = 0;

on peut donc démontrer la formule très facilement par récurrence. □

Lemme 3. Soit Q_{k}(z, y) la série génératrice, où [z^{n}y^{m}]Q_{k} est le nombre d’arbres de taille n avec m nœuds au niveau k, qui est le niveau maximal. (C’est à dire, si m ≥ 1, la hauteur d’arbre est exactement k.) On a pour k ≥ 1 et d ≥ 1

[y^{d}]Q_{k}(z, y) = A_{k−1}^{d+1}(z) − A_{k−1}^{d}(z) + zA_{k−1}^{d−1}(z).

Démonstration. En traduisant comme d’habitude, on obtient

Q_{1} = zy  et  Q_{k} = \frac{z}{1 − Q_{k−1}} pour k ≥ 2.

Comme on a

[y^{0}]Q_{k}(z, y) = A_{k−1}(z),

il suffit de démontrer que

Q_{k}(z, y) = A_{k−1}(z) + ∑_{d≥1} y^{d}(A_{k−1}^{d+1}(z) − A_{k−1}^{d}(z) + zA_{k−1}^{d−1}(z))

= \frac{A_{k−1}}{1 − yA_{k−1}} − \frac{yA_{k−1}}{1 − yA_{k−1}} + \frac{zy}{1 − yA_{k−1}}

= \frac{(1 − y)A_{k−1} + zy}{1 − yA_{k−1}} ;

ce qui est un simple exercice, en utilisant la récurrence des A_{k}.

Soit B_{d,k}(z) la série génératrice, où [z^{n}]B_{d,k} est le nombre d’arbres de taille n où d feuilles sont à hauteur > k et toutes les autres sont à hauteur ≤ k. On peut constater que B_{0,k} +B_{1,k} +⋯+B_{d−1,k} est la série génératrice d’arbres où la d-ième feuille (au sens défini dessus) est à hauteur ≤ k. Donc la quantité h_{n}(d) est donnée par

h_{n}^{(d)} = \frac{[z^{n}] ∑_{k≥0} (P (z) − B_{0,k}(z) − B_{1,k}(z) − ⋯ − B_{d−1,k}(z))}{[z^{n}] P (z)}.

Lemme 4. La hauteur moyenne d’un arbre planaire de taille n vérifie

\frac{[z^{n}] ∑_{k≥0} (P (z) − B_{0,k}(z))}{[z^{n}] P (z)} ∼ \sqrt{πn} − \frac{1}{2} + ….

Idée de la demonstration. On trouve que

∑_{k≥0} (P (z) − B_{0,k}(z)) = ∑_{k≥0} (P (z) − A_{k}(z))

= \frac{1 − u}{1 + u} ∑_{k≥1} \frac{u^{k}}{1 − u^{k}} = \frac{1 − u}{1 + u} ∑_{k≥1} d(k)u^{k}

où d(k) est le nombre de diviseurs de k. On constate que

∑_{k≥1} d(k)k^{−s} = ζ^{2}(s),

et on peut utiliser la transformation de Mellin comme au chapitre 2.

Comme dans les chapitres 2 et 3 on va démontrer aue

∑_{k≥0} B_{s+1,k}(z) ∼ A_{s} − B_{s}t + …,

où A_{s} et B_{s} sont des constantes et u = e^{−t}. Comme

P (z) = \frac{u}{1 + u} ∼ \frac{1}{2} − \frac{1}{4}t + …,

on peut conclure que

[z^{n}] ∑_{k≥0} B_{s+1,k}(z)/t_{n} ∼ 4B_{s}.

Lemme 5. On a pour s ≥ 0

∑_{n≥p} z^{n}\binom{n}{s}\binom{n − p}{s} = ∑_{j=0}^{s} \frac{z^{s+p+j}}{(1 − z)^{s+1+j}} \frac{(p + s)!(s + j)!}{j!(s − j)!(p + j)!s!}.

Démonstration. Avec D = d/dz et (n)_{d} = n(n − 1) … (n − d + 1) on a

∑_{n≥p} z^{n}\binom{n}{s}\binom{n − p}{s} = \frac{1}{(s!)^{2}} ∑_{n≥0}(n)_{s}z^{s}D^{s}z^{n+p}

= \frac{1}{(s!)^{2}} z^{s}D^{s}z^{p+s} ∑_{n≥0} z^{n}

= \frac{1}{s!}z^{s}D^{s} \frac{z^{p+s}}{(1 − z)^{s+1}}

= \frac{1}{s!}z^{s} ∑_{j=0}^{s} \binom{s}{j}[D^{s−j}z^{p+s}][D^{j}(1 − z)^{−s−1}]. □

Lemme 6. On a pour s ≥ 0 et k ≥ 1

B_{s+1,k}(z) = ∑_{j=0}^{s} \frac{(s + j)!}{j!(s − j)!(s + 1)!} (\frac{u}{1 + u + u^{2}} )^{s+1+j}

× \frac{(1 − u)^{2}}{1 + u} \frac{u^{k−1}}{(1 − u^{k−1})(1 − u^{k})} ∑_{p≥1} \frac{p(p + s)!}{(p + j)!}A_{k−1}^{p}.

Démonstration. On remplace chaque feuille au niveau maximal k (marquée par y en Q_{k}(z, y)) par un arbre arbitraire dont les feuilles sont marquées par y. Alors

B_{s+1,k} = [y^{s+1}] Q_{k}(z, \frac{1}{z}F (z, y))

= [y^{s+1}] ∑_{p≥1} [\frac{1}{z}F (z, y)]^{p}[A_{k−1}^{p+1} − A_{k−1}^{p} + zA_{k−1}^{p−1}]

= ∑_{p≥1} z^{−p}p ∑_{n≥1} z^{n} \frac{1}{n}\binom{n}{s + 1}\binom{n − p − 1}{s}A_{k−1}^{p}[A_{k−1} − 1 + zA_{k−1}^{−1}].

La formule annoncée est obtenue en remarquant que

A_{k−1} − 1 + zA_{k−1}^{−1} = \frac{u^{k−1}}{(1 − u^{k−1})(1 − u^{k})} \frac{(1 − u)^{2}}{1 + u} ,

\frac{z}{1 − z} = \frac{u}{1 + u + u^{2}}

et en utilisant le Lemme 5.

Lemme 7. La série génératrice B_{s+1,k}(z) est donnée par

B_{s+1,k}(z) = ∑_{j=0}^{s} ∑_{i=0}^{s−j} \frac{(s + j)!(i + 1)}{j!(s − j − i)!(j + i + 1)!}×

× (\frac{u}{1 + u + u^{2}} )^{s+1+j} (1 − u)^{2}u^{i+1}u^{k−1} \frac{(1 − u^{k−1})^{i}}{(1 − u^{k+1})^{i+2}} .

Démonstration. On utilise la formule (déduite de la formule de Vandermonde)

\frac{p(p + s)!}{(s − j)!(s + 1)!(p + j)!} = ∑_{i=0}^{s−j}(i + 1)\binom{p}{i + 1}\frac{1}{(s − j − i)!(j + i + 1)!}

et aussi les formules

\frac{A_{k}}{z} = \frac{1}{1 − A_{k−1}}

et

∑_{p≥1} \binom{p}{i + 1}A_{k−1}^{p} = \frac{A_{k−1}^{i+1}}{(1 − A_{k−1})^{i+2}}

Nous sommes prêts à attaquer la détermination des développements locaux en ∑_{k≥0} B_{s+1,k}. On constate facilement que

\frac{u}{1 + u + u^{2}} ∼ \frac{1}{3};  (1 − u)^{2} ∼ t^{2}(1 − t);  u^{i+1} ∼ 1 − (i + 1)t.

Lemme 8. On a le développement local

∑_{k≥0} u^{k−1} \frac{(1 − u^{k−1})^{i}}{(1 − u^{k+1})^{i+2}}

∼ t^{−2}(1 + 2t)( ∑_{l=0}^{i} \binom{i}{l}(−2)^{l}(1 + lt)(ζ(l + 2) − \frac{l}{2}ζ(l + 1)t) − \frac{1}{2}t).

Démonstration. On peut écrire

∑_{k≥0} u^{k−1} \frac{(1 − u^{k−1})^{i}}{(1 − u^{k+1})^{i+2}} = u^{−2} ∑_{k≥1} \frac{u^{k}}{(1 − u^{k})^{2}} (1 + \frac{(1 − u^{−2})u^{k}}{1 − u^{k}} )^{i}

= u^{−2} ∑_{l=0}^{i} \binom{i}{l}(1 − u^{−2})^{l} ∑_{k≥1} \frac{u^{k(l+1)}}{(1 − u^{k})^{l+2}} .

On voit immédiatement que

u^{−2} ∼ 1 + 2t  et  (1 − u^{−2})^{l} ∼ (−2)^{l}t^{l}(1 + lt).

On applique encore la transformation de Mellin:

M ∑_{k≥1} \frac{e^{−tk(l+1)}}{(1 − e^{tk})^{l+2}} = ∑_{k≥1} k^{−s}M\frac{e^{−t(l+1)}}{(1 − e^{t})^{l+2}}

= ζ(s)Γ(s) ∑_{λ≥0} \binom{λ}{l + 1}λ^{−s}

= ζ(s)Γ(s) ∑_{λ≥0} \frac{1}{(l + 1)!} ∑_{i=0}^{l+1} s_{l+1,i}λ^{i}λ^{−s}

(où les s_{l+1,j} sont les nombres Stirling de première espèce)

= \frac{1}{(l + 1)!}ζ(s)Γ(s) ∑_{i=0}^{l+1} s_{l+1,i}ζ(s − i).

Comme au chapitre 2 on utilise la formule d’inversion de Mellin; on change le chemin d’intégration en prenant en compte les résidues. Dans notre problème, il suffit de considérer les termes où i = s + 1 et i = s. On peut constater que

s_{l+1,l+1} = 1  et  s_{l+1,l} = −\binom{l + 1}{2}.

Lemme 9. La somme des B_{s+1,k}(z) vérifie le développement local

∑_{k≥0} B_{s+1,k}(z) ∼ const − \frac{1}{2}t ∑_{j=0}^{s} ∑_{i=0}^{s−j} \frac{(s + j)!(i + 1)}{j!(s − j − i)!(j + i + 1)!}3^{−s−1−j}.

Idée de la Démonstration.

∑_{k≥0} B_{s+1,k}(z) ∼ ∑_{j=0}^{s} ∑_{i=0}^{s−j} \frac{(s + j)!(i + 1)}{j!(s − j − i)!(j + i + 1)!}3^{−s−1−j}t^{2}(1 − t)(1 − (i + 1)t)×

× t^{−2}(1 + 2t)( ∑_{l=0}^{i} \binom{i}{l}(−2)^{l}(1 + lt)(ζ(l + 2) − \frac{l}{2}ζ(l + 1)t) − \frac{1}{2}t)

On veut obtenir le coefficient de t dans cette expression. C’est une chose très simple; après quelques manipulations de nombreuses simplifications apparaissent. □

A partir des égalités précédentes, on tire

[z^{n}] B_{s+1,k}(z)/t_{n} ∼ 4 · \frac{1}{2} ∑_{j=0}^{s} ∑_{i=0}^{s−j} \frac{(s + j)!(i + 1)}{j!(s − j − i)!(j + i + 1)!}3^{−s−1−j}.

Pour la quantité h_{n}^{(d)} on doit sommer:

∑_{s=0}^{d−2} 2 ∑_{j=0}^{s} ∑_{i=0}^{s−j} \frac{(s + j)!(i + 1)}{j!(s − j − i)!(j + i + 1)!}3^{−s−1−j}.

On peut écrire pour cette quantité

∑_{s=0}^{d−2} \frac{2}{(s + 1)3^{s+1}} [x^{s}] \frac{1}{(1 − x)^{2}} (\frac{1 + x}{1 − \frac{x}{3}} )^{s+1} .

Donc nous avons le

Theorème 3. La hauteur moyenne de la d-ième feuille d’un arbre planaire de taille n, a le développement asymptotique (pour d fixe et n → ∞)

h_{n}^{(d)} = \sqrt{πn} − \frac{1}{2} − ∑_{s=0}^{d−2} \frac{2}{(s + 1)3^{s+1}} [x^{s}] \frac{1}{(1 − x)^{2}} (\frac{1 + x}{1 − \frac{x}{3}} )^{s+1} + o(1).

5. Quelques remarques sur la technique d’extraction de coefficients

Si on suit la stratégie mentionnée dans le titre, les problèmes de dénombrement d’arbres demandent souvent d’évaluer des sommes du type

∑_{k≥1} ω(k)\frac{\binom{2n}{n+k+1} − 2\binom{2n}{n+k} + \binom{2n}{n+k−1}}{\binom{2n}{n}}.

où ω(k) peut être, par exemple, v_{2}(k) ou ϑ(k) ou d(k) comme dans les chapitres 2, 3 et 4.

On a besoin d’approximations de certains coefficients binomiaux dans une région centrale (p.e. |k| ≤ \sqrt{n} log n). On obtient, par exemple par la formule de Stirling

\begin{matrix}( & {2n \atop n+k} & ) \\ ( & {2n \atop n} & ) \end{matrix} ∼ e^{−k^{2}/n} · (1 + \frac{k^{2}}{2n^{2}} − \frac{k^{4}}{6n^{3}} + …)

(voir [9] pour une formule générale). On voit souvent apparaitre les différences r-ièmes de coefficients binomiaux

ξ = [u^{n}] u^{k}(1 − u)^{r}(1 + u)^{2n}/\binom{2n}{n} = ∑_{λ=0}^{r}(−1)^{λ}\binom{r}{λ}\binom{2n}{n + k + r}/\binom{2n}{n}.

On rappelle l’opérateur des différences Δ:

Δ^{r}\binom{2n}{n + k} = ∑_{λ=0}^{r} \binom{r}{λ}(−1)^{r−λ}\binom{2n}{n + k + λ}

Nous considérons Δ^{r}e^{−k^{2}/n}. Pour cela, on a besoin des polynomes d’Hermite. Voici les propriétées necessaires [3]:

e^{2zt−t^{2}} = ∑_{n≥0} H_{n}(z)\frac{t^{n}}{n!}

H_{0} = 1, H_{1} = 2z, H_{n+1} = 2zH_{n} − 2nH_{n−1}

H_{n}(z) = ∑_{k≥0} \frac{n!}{k!(n − 2k)!}(−1)^{k}(2z)^{n−2k}

H_{n}(−z) = (−1)^{n}H_{n}(z)

Donc

Δ^{r}e^{−k^{2}/n} = ∑_{λ=0}^{r}(−1)^{r−λ}\binom{r}{λ}e^{−(k+λ)^{2}/n}

= e^{−k^{2}/n} ∑_{λ=0}^{r}(−1)^{r−λ}\binom{r}{λ}e^{− \frac{2kλ}{n} − \frac{λ^{2}}{n}}

= e^{−k^{2}/n} ∑_{λ=0}^{r}(−1)^{r−λ}\binom{r}{λ} ∑_{m≥0} H_{m} (−\frac{k}{\sqrt{n}}) (\frac{λ}{\sqrt{n}})^{m} \frac{1}{m!}.

On sait (avec les nombres de Stirling de second espèce) que

∑_{λ=0}^{r}(−1)^{r−λ}\binom{r}{λ}λ^{m} = r!S_{m,r}.

Donc

(−1)^{r}Δ^{r}e^{−k^{2}/n} ∼ e^{−k^{2}/n} [H_{r} (\frac{k}{\sqrt{n}}) \frac{1}{n^{r/2}} − H_{r+1} (\frac{k}{\sqrt{n}}) \frac{1}{n^{(r+1)/2}} \frac{r}{2} + …] .

On trouve donc

ξ ∼ e^{−k^{2}/n}H_{r} (\frac{k}{\sqrt{n}}) \frac{1}{n^{r/2}} ,

résultat annoncée en [5].

Pour obtenir plusieurs termes, on doit considérer Δ^{r}k^{t}e^{−k^{2}/n}.

On peut utiliser la formule générale (de type Leibniz):

Δ^{r}f(k)g(k) = ∑_{λ=0}^{r} \binom{r}{λ}(Δ^{r−λ}f(k + λ))(Δ^{λ}g(k))

avec f(k) = k^{t} et g(k) = e^{−k^{2}/n}.

Si on a (pour un certain polynome p)

[u^{n}] u^{k}p(u)(1 + u)^{2n},

on peut développer p(u) en puissances de 1 − u et utiliser la machinerie comme nous l’avons indiqué.

Dans de nombreux autres cas, on rencontre les quantités

[u^{n}] u^{k} \frac{1}{1 − u}(1 + u)^{2n};

c’est à dire qu’on doit considérer

∑_{j≥k} e^{−j^{2}/n} ∼ \sqrt{n} erfc (\frac{k}{\sqrt{n}}) + \frac{1}{2}e^{−k^{2}/n} + …,

avec la formule de sommation d’Euler et la fonction d’erreur

erfc(z) := ∫_{z}^{∞} e^{−t^{2}}dt.

Pour obtenir plusieurs termes, on doit considérer

I_{m}(z) = ∫_{z}^{∞} t^{m}e^{−t^{2}}dt;

on peut évaluer cette intégrale avec une intégration par parties:

I_{m}(z) = \frac{m − 1}{2}I_{m−2}(z) + \frac{1}{2}z^{m−1}e^{−z^{2}},

I_{1}(z) = \frac{1}{2}e^{−z^{2}}, I_{0}(z) = erfc(z).

Enfin un problème plus général de même nature apparait dans l’evaluation des sommes du type

[u^{n}] u^{k} \frac{1}{(1 − u)^{a}} (1 + u)^{2n}

où a est un nombre entier ≥ 1.

Bibliographie

1. de Bruijn, Knuth, Rice, The average height of planted plane trees, Graph Theory and Computing (R.C. Read, eds.), Academic Press, New York, 1972, pp. 15–22.

2. Dieudonné, Calcul Infinitesimal, Hermann, Paris, 1968.

3. Erdélyi, Magnus, Oberhettinger, Tricomi, Higher Transcendental Functions, Mc-Graw-Hill, 1955.

4. Flajolet, Analyse d’algorithmes d’arbres et de fichiers, Cahiers du BURO 34–35 (1981), 1– 209.

5. Flajolet, Raoult, Vuillemin, The number of registers required for evauluating arithmetic expressions, Theor. Comput. Sci. 9 (1979), 99–125.

6. Flajolet, Ramshaw, A note on Gray Code and odd-even merge, SIAM J. on Computing 9 (1980), 142–158.

7. Flajolet, Odlyzko, The average height of binary trees and other simple trees, J. Comput. Syst. Sci. 25 (1982), 171–213.

8. Flajolet, Prodinger, Register Allocation for unary-binary Trees, SIAM J. on Computing 15 (1986), 629–640.

9. Greene, Knuth, Mathematics for the Analysis of Algorithms, Birkhäuser, 1981.

10. Jungen, Sur les séries de Taylor n’ayant que des singularités algébro-logarithmiques sur leur cercle de convergence, Commentarii Math. Helvetici 3 (1931), 266–306.

11. Kemp, The average number of registers to evaluate a binary tree optimally, Acta. Inf. 11 (1979), 363–372.

12. Kemp, On the average oscillation of a stack, Combinatorica 2 (1982), 157–176.

13. Kemp, The average height of planted plane trees with m leaves, Journal of Combinatorial Theory Ser. B B 34 (1983), 191–208.

14. Kemp, On the number of deepest nodes in ordered trees, Discrete Mathematics 81 (1990), 247–258.

15. Knuth, The Art of Computer Programming,Vol.1, Addison-Wesley, 1968.

16. Knuth, The Art of Computer Programming,Vol.3, Addison-Wesley, 1968.

17. Meir, Moon and Pounder, On the order of random channel networks, SIAM J. on Alg. Disc. Meth. 1 (1980), 25–33.

18. Prodinger, The average height of the second highest leaf of a planted plane trees, Europ. J. on Combinatorics 5 (1984), 351–357.

19. Prodinger, Die Bestimmung gewisser Parameter von binären Bäumen mit Hilfe analytischer Methoden, Lecture Notes in Mathematics (E.Hlawka, Ed.) 1114 (1985), 118–133.

20. Prodinger, The Average Height of the d-th Highest Leaf of a Planted Plane Tree, Networks 16 (1985), 67–75.

21. Sedgewick, Data movement in odd-even merge, SIAM J. on Computing 7 (1978), 239–272.

22. Whittaker, Watson, A course in modern analyis, Cambridge University Press, 1930.