\input amstex
\documentstyle{amsppt}









\def\erfc{\operatorname{erfc}}
\define\reg{\operatorname{reg}}
\define\coeff#1{\left[z^{#1}\right]}
\define\coeffu#1{\left[u^{#1}\right]}
\define\GG{\Gamma}
\redefine\ll{\lambda}

\font\super=cmbx10 scaled \magstep 2

\document
{\super 
\centerline{Quelques techniques analytiques}
\medskip
\centerline{pour l'\'etude asymptotique}
\medskip
\centerline{des param\`etres}
\medskip
\centerline{dans les arbres}}

\bigskip
\centerline{{\smc Helmut Prodinger}}
\bigskip
\font\klein=cmr8
\klein
\centerline{Department of Algebra and Discrete Mathematics}
\centerline{Technical University of Vienna}
\centerline{Wiedner Hauptstra\ss e 8--10}
\centerline{A--1040, Vienna, Austria}
\bigskip
\rm
\rightline{{\sl Written for the Proceedings of the Summerschool
 in Ile de R\'e 1983}}
\rightline{{\sl Retyped 1991}}





\heading
1. Introduction
\endheading

La structure d'arbre est l'une des structures de donn\'ees les
plus r\'epan\-dues en informatique. Les algorithmes de manipulation 
d'arbres sont ainsi tr\`es nombreux. L'analyse de ces algorithmes au sens
de Knuth nous conduit souvent \`a des probl\`emes combinatoires de
d\'enombrement des configurations; l'\'etape suivante consiste en
l'analyse asymptotique de ces d\'enombrements. Voir par exemple
\cite 4, \cite{15}, \cite{16}.

L'\'etude de Flajolet et Odlyzko \cite 7 est paradigme pour un point
de vue un peu diff\'erent: Au lieu d'\'extraire des coefficients
de fonctions g\'en\'eratrices et d'approxi\-mer ceux-ci avec des m\'ethodes
de l'analyse r\'eelle, on \'etudie des singularit\'es des series 
g\'en\'eratrices. Plus pr\'ecisement on recherche \`a \'etablir un
d\'eveloppement asymptotique de la fonction autour de la
singularit\'e la plus proche de l'origine; ensuite des lemmes
de traduction permettent de traduire ce d\'eveloppement en un
d\'eveloppe\-ment asymptotique des coefficients de Taylor de la s\'erie
g\'en\'eratrice en question. Par exemple, si
$f(z)=\sum_{n\ge 0}f_nz^n$ a sa singularit\'e la plus proche de l'origine
en 1, avec
$$
f(z)\sim A-B\sqrt{1-z}+\dots ,
$$
on  d\'eduit que
$$
\coeff n f(z):=f_n\sim\frac{B}{2\sqrt \pi}n^{-3/2}.
$$
De m\^eme, si l'on a
$$
f(z)\sim -A\log(1-z)+\dots,
$$
alors
$$
[z^n]f(z)\sim\frac{A}{n},\quad\text{etc}.
$$
Enfin, plus on connait de termes du d\'eveloppement de la s\'erie
g\'en\'eratrice, plus on a de termes du d\'eveloppement des coefficients
de Taylor.

Cette traduction est un processus assez automatique. Le probl\`eme
principal est de trouver le d\'eveloppement autour de la (des)
 singularit\'e(s).
Dans de nombreux cas, on peut se servir de la transformation de Mellin,
m\'ethode tr\`es populaire dans l'\'ecole fran\c caise d'algorithmes.

Le but de ce travail est d'expliquer cette strat\'egie g\'en\'erale
dans trois cas parti\-culiers: le probl\`eme d'allocation de registres et
d'\'evaluation d'expressions arithm\'eti\-ques; puis la hauteur des feuilles dans les
arbres planaires. Enfin, le troisi\`eme probl\`eme est la recherche
de la valeur asymptotique d'une certaine expression
(tr\`es similaire au cas de registres); cette valeur est int\'eressante
dans l'analyse d'un algorithme de tri (voir \cite 6, \cite{21}).

Avant de s'engager dans des d\'etails techniques, on formule quelques
points fondamentaux:

La classe $\Cal B$ des arbres binaires est d\'efinissable
r\'ecursivement par l'\'equation (symbolique)
%$$ \includegraphic{binaer} $$
qui traduit qu'un arbre binaire est soit l'arbre form\'e d'un
seul sommet externe (``feuille''), soit l'arbre form\'e d'une racine et de deux
arbres qui sont les sous-arbres gauche et droite de la racine. Soit
$B(z)=\sum_{n\ge 0}b_nz^n$ la s\'erie g\'en\'eratrice des arbres binaires
o\`u $b_n$ est le nombre
d'arbres binaires de taille $n$ (la taille d'un arbre binaire est mesur\'ee
par le nombre de ses sommets internes); on a immediatement
$$
B(z)=1+z\left(B(z)\right)^2,
$$
d'o\`u
$$
B(z)=\frac{1-\sqrt{1-4z}}{2z}\quad \text{et} \quad 
b_n=\frac{1}{n+1}\binom{2n}n.
$$
Les nombres $b_n$ sont les nombres de {\sl Catalan}.

De mani\`ere analogue, la famille $\Cal P$ des arbres planaires est
d\'efinie par
%\vskip 2 cm
%$$ \includegraphic{planted} $$
d'o\`u on tire pour la s\'erie g\'en\'eratrice $P(z)=\sum_{n\ge 1}
t_nz^n$ des arbres planaires
$$
P(z)=\frac{z}{1-P(z)}
\ \text{ et donc } \ 
P(z)=\frac{1-\sqrt{1-4z}}{2}\ \text{  et  }\ 
 t_n=\frac{1}{n}\binom{2n-2}{n-1}
.$$
Dans les deux cas, la singularit\'e mentionn\'ee est $z=\frac 14$, et
$$
B(z)\sim 2 -2\sqrt{1-4z},\ \text{ donc }\ 
b_n\sim\frac{1}{\sqrt \pi}4^nn^{-3/2}
$$
respectivement
$$
P(z)\sim \frac 12 -\frac 12\sqrt{1-4z},\ \text{ donc }\ 
t_n\sim\frac{1}{\sqrt \pi}4^{n-1}n^{-3/2}.
$$
\pagebreak
\heading
2. Le nombre moyen de registres pour evaluer un arbre binaire de
taille $n$
\endheading

Avant de commencer notre traitement, citons les r\'ef\'erences sur ce
sujet: \cite 4, \cite 5, \cite8, \cite{11}, \cite{17}, \cite{19}.
On s'abstiendra de pr\'esenter ici une description de la probl\'ematique
informatique. A cet effet on renvoie \`a la th\`ese de P.Flajolet
\cite 4.

La fonction ``nombre de registres'' {\it reg} est donn\'ee recursivement par
$$
\reg(\square)=0
$$
$$
\reg\bigg(\quad
%\hbox{
\kern-.3cm\raise-.38cm\hbox{%\includegraphic{baum1}
}
%}
\bigg)=
\cases
\max\{\reg(t_1), \reg(t_2)\} \quad&\text{si } \reg(t_1)\ne \reg(t_2)\\
1+\reg(t_1) \quad&\text{sinon }.
\endcases
$$
Le probl\`eme est l'\'etude de $R_n$, la valeur moyenne de la fonction
{\it reg}, relativement \`a l'ensemble des arbres binaires de taille $n$.
On a
$$
R_n=\frac{1}{b_n}\cdot [z^n]E(z),
$$
avec
$$
E(z)=\sum_{n\ge 0}z^n\sum_{t \text{ de taille }n}\reg(t).
$$

Soit $\Cal R_p$ la famille des arbres $t$ avec $\reg(t)=p$. 
De la d\'efinition de {\it reg} on
d\'eduit facilement :
$$
%\includegraphic{reg1}
$$
Soit $\Cal S_p$ la famille des arbres $t$ avec $\reg(t)\ge p$,
c'est \`a dire
$$
\Cal S_p=\Cal R_p+\Cal R_{p+1}+\dots\ .
$$
On peut \'ecrire
$$
\sum_{j<p-1}\Cal R_j=\Cal B \diagdown \Cal S_{p-1}.
$$
On obtient une r\'ecurrence pour les familles $\Cal S_{p}$ d'une mani\`ere
tout \`a fait semblable:
$$
%\includegraphic{reg2}
 $$
Les fonctions $S_p(z)$ sont d\'efinies par
$$
S_p(z):=\sum_{n\ge 0}z^n\sum_{t \text{ de taille }n,\  \reg(t)\ge p}1.
$$
Il est clair que
$$
E(z)=\sum_{p\ge 1}S_p(z).
$$
Les fonctions $S_p(z)$ sont d\'ecrites par les r\'ecurrences
imm\'ediates
$$
S_0=B; \quad
S_p=zS_{p-1}^2+2zS_p\left(B-S_{p-1}\right).
$$
Il est commode de d\'efinir $\varepsilon:=\sqrt{1-4z}$ et $z=u/(1+u)^2$.
D'o\`u
$$
S_p=\frac{zS_{p-1}^2}{1-2zB+2zS_{p-1}},
$$
c'est \`a dire
$$
\frac{1}{S_p}=\frac{\varepsilon}{zS_{p-1}^2}+\frac{2}{S_{p-1}}.
$$
Ce qui conne finalement
$$
\aligned
1+\frac{\varepsilon}{z}\frac{1}{S_p}&=
1+\frac{\varepsilon^2}{z^2S_{p-1}^2}+\frac{2\varepsilon}{z}\frac{1}{S_{p-1}}
=\left(1+\frac{\varepsilon}{z}\cdot\frac{1}{S_{p-1}}\right)^2\\
&=\dots=\left(1+\frac{\varepsilon}{z}\cdot\frac{1}{S_0}\right)^{2^p}.
\endaligned
$$
On en d\'eduit l'\'equation
$$
S_p=\frac{\varepsilon}{z}\left(\left(1+\frac{\varepsilon}{zB}\right)
^{2^p}-1
\right)^{-1}.
$$
On voit tout de suite que
$$
\frac{\varepsilon}{z}=\frac{1-u^2}{u},\quad\text{et}\quad
1+\frac{\varepsilon}{zB}=\frac 1u,
$$
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
$$
\aligned
E(z)&=\frac{1-u^2}{u}\sum_{p\ge 1}\frac{u^{2^p}}{1-u^{2^p}}\\
&=\frac{1-u^2}{u}\sum_{p\ge 1}
\sum_{\lambda \ge 1}u^{\lambda 2^p}\\
&=\frac{1-u^2}{u}\sum_{n\ge 2}v_2(n)u^n,
\endaligned
$$
o\`u $v_2(n)$ est l'exposant de 2 dans la d\'ecomposition de $n$
en facteurs premiers:
$$
v_2(n)=\sum_{n=\lambda 2^p,\ \lambda, p\ge 1}1.
$$
Si on \'ecrit, d'une mani\`ere unique, $n=2^m(1+2i)$, ($m\ge1$, 
$i\ge 0$), on a
$$
v_2(n)=\sum_{p=1}^m1=m.
$$
On appelle souvent la quantit\'e $v_2(n)$ ``valuation dy\-adi\-que'',
pour des raisons \'eviden\-tes.
Comme il \'etait annonc\'e dans l'introduction, on va
d\'emontrer ult\'erieurement que l'on a dans un voisinage de
$z=\frac 14$ (c'est \`a dire $u=1$):
$$
E(z)\sim 2\varepsilon\log_2\varepsilon+A\varepsilon+
4\sum_{k\ne 0}c_k\varepsilon^{1-\chi_k}+\dots,
$$
avec
$$
A=3-2\log_22\pi+\frac{2\gamma}{\log 2},\quad (\gamma 
\text{ est la constante d'Euler})
$$
et
$$
\chi_k=\frac{2k\pi i}{\log 2}\quad\text{et}\quad
c_k=\frac{1}{\log 2}\Gamma(\chi_k)\zeta(\chi_k)
$$
($\Gamma$ est la fonction gamma d'Euler, $\zeta$ est la fonction
zeta de Riemann).

Mentionnons le d\'eveloppement suivant (\cite{10})
$$
\coeff n\log(1-z)(1-z)^\alpha\sim \frac{-n^{-\alpha-1}\log n}{\GG(-\alpha)}
+n^{-\alpha-1}\frac{\GG(-\alpha)}{(\GG(-\alpha))^2},
$$
ce qui nous donne en particulier
$$
\coeff n\varepsilon\log\varepsilon\sim
\frac 124^nn^{-3/2}\left(
\frac{\log n}{2\sqrt\pi}+\frac{\gamma+2\log2-2}{2\sqrt\pi}\right).
$$
On utilise \'egalement le r\'esultat
$$
\coeff n\varepsilon^{1-\chi_k}\sim4^nn^{(\chi_k-3)/2}\Big/\GG
\left(\frac{\chi_k-1}{2}\right).
$$
Observons alors qu'on peut simplifier l'expression
$$
c_k\Big/\GG
\left(\frac{\chi_k-1}{2}\right)=
\frac{\zeta(\chi_k)\GG\big(\frac{\chi_k}{2}\big)(\chi_k-1)}{4\sqrt\pi\log2};
$$
pour cela on utilise la formule de duplication de Legendre-Gauss
(voir p.e. \cite2)
$$
\GG\left(\frac{z}{2}\right)\GG\left(\frac{z+1}{2}\right)=
\sqrt\pi2^{1-z}\GG(z).
$$
Enfin, si l'on collecte tous les ingr\'edients, on trouve
$$
\align
\coeff nE(z)&\sim
\frac{4^nn^{-3/2}}{2\sqrt\pi\log2}\left(\log n+\gamma+2\log2-2\right)\\
&-A\frac{4^n}{2\sqrt\pi}n^{-3/2}+
\sum_{k\ne0}
\frac{4^nn^{(\chi_k-3)/2}\zeta(\chi_k)\GG(\chi_k/2)(\chi_k-1)}{\sqrt\pi
\log2}.
\endalign
$$
Si on prend en consid\'eration que
$$
b_n\sim\frac{4^n}{\sqrt\pi}n^{-3/2}\qquad\text{et}
\qquad
n^{\chi_k/2}=\varepsilon^{\log_4n\cdot2k\pi i}, 
$$
on obtient

\proclaim{Theor\`eme 1}
Le nombre moyen $R_n$ 
de registres n\'ecessaires \`a l'\'evaluation d'un arbre de taille
$n$ verifie
$$
R_n=\log_4n+D(\log_4n)+o(1),
$$
o\`u $D(x)$
est une fonction continue p\'eriodique de p\'eriode 1; cette fonction
peut \^etre d\'evelopp\'ee en s\'erie de Fourier
$$
D(x)=\sum_{k\in\Bbb Z}d_ke^{2k\pi ix},
$$
avec
$$
d_0=\frac 12-\frac{\gamma}{2\log2}
-\frac{1}{\log 2}+\log_2\pi
$$
et
$$
d_k=\frac{1}{\log2}\zeta(\chi_k)\GG(\frac{\chi_k}{2})(\chi_k-1),
\quad k\ne 0, \quad \chi_k=\frac{2k\pi i}{\log2}.
$$
\endproclaim

Le reste de ce chapitre est consacr\'e \`a la d\'ecouverte du d\'eveloppement
de la fonction $E(z)$.

Pour \'etudier $E(z)$ pour $z\to \frac 14$, i.e. pour $u\to 1$, on pose
$u=e^{-t}$ et on consid\`ere $E(z)$ pour $t\to 0$. On obtient facilement
que
$$
\frac{1-u^2}{u }\sim2t+\dots \ .
$$
Passons au deuxi\`eme facteur de $E(z)$, d\'enot\'e par $V(t)$; la
transformation de Mellin de $V(t)$ est not\'ee $V^*(s)$:
$$
V(t)=\sum_{k\ge 1}v_2(k)e^{-kt}; \qquad
V^*(s)=\int_0^\infty x^{s-1}V(x)dx
$$
$$
\align
V^*(s)&=\int_0^\infty x^{s-1}\sum_{k\ge 1}v_2(k)e^{-kx}dx\\
&=\sum_{k\ge 1}v_2(k)k^{-s}\int_0^\infty x^{s-1}e^{-x}dx
\endalign
$$
On a
$$
\sum_{k\ge 1}v_2(k)k^{-s}=2^{-s}\sum_{k\ge 1}v_2(2k)k^{-s}
=2^{-s}\sum_{k\ge 1}\big[1+v_2(k)\big]k^{-s},
$$
donc
$$
V^*(s)=\frac{\GG(s)\zeta(s)}{2^s-1}.
$$
La formule d'inversion de Mellin nous donne
$$
V(t)=\frac{1}{2\pi i}\int\limits_{2-i\infty}^{2+i\infty}V^*(s)t^{-s}ds.
$$

On peut d\'eplacer le chemin d'int\'egration vers la gauche, en prenant
en compte les r\'esidues de l'int\'egrande $V^*(s)t^{-s}$. Il y a des
p\^oles en $s=1$ (provenant de la fonction $\zeta$ de Riemann)
, en $s=0, -1, -2,\dots$ (provenant de la fonction $\GG$)  et en
$s=\chi_k$, $k\in\Bbb Z$ (de $(2^s-1)^{-1}$). On utilise des d\'eveloppements
classiques et on trouve
$$
\align
V(t)&\sim \frac 1t +\frac 12\log_2t-\frac 12\log_22\pi +\frac 14
+\frac{\gamma}{2\log 2}\\
&+\frac{1}{\log 2}\sum_{k\ne 0}\GG(\chi_k)\zeta(\chi_k)t^{-\chi_k}+\dots
\endalign
$$
ce qui donne la formule annonc\'ee pour $E(z)$, apr\`es avoir multipli\'e 
les deux derniers d\'eveloppements et en notant que
$$
t\sim 2\varepsilon+\dots \ .
$$
\bigskip

\head 3. Un probleme similaire: La fusion paire-impaire \endhead

Dans l'analyse d'un algorithme de tri (fusion paire-impaire) on doit
consid\'erer la quantit\'e
$$
B_n=\sum_{k\ge 1}\frac{\binom{2n}{n-k}}{\binom{2n}n}\Big(2F(k)+k\Big),
$$
repr\'esentant le nombre d'\'echanges dans la fusion paire-impaire de
$2n$ \'el\'ements. Dans cette \'egalit\'e,
$$
F(k)=\sum_{0\le j<k}f(j)
$$
et $f(j)$ est le nombre des chiffres ``1'' dans la repr\'esentation
de $j$ en code de Gray (voir \cite6, \cite{21}). On trouve ci-dessous
les premiers nombres dans cette repr\'esentation:
\vskip 1 cm

\hfil
\vbox{
\settabs 
\+ \hskip 2 cm&\hskip 1 cm&\hskip 3 cm&\hskip 1 cm&\cr
\+ \hfill 0 & \hfill 0 & \hfill 1100 &\hfill 8 &\cr
\+ \hfill 1 & \hfill 1 & \hfill 1101 &\hfill 9 &\cr
\+ \hfill 11 & \hfill 2 & \hfill 1111 &\hfill 10 &\cr
\+ \hfill 10 & \hfill 3 & \hfill 1110 &\hfill 11 &\cr
\+ \hfill 110 & \hfill 4 & \hfill 1010 &\hfill 12 &\cr
\+ \hfill 111 & \hfill 5 & \hfill 1011 &\hfill 13 &\cr
\+ \hfill 101 & \hfill 6 & \hfill 1001 &\hfill 14 &\cr
\+ \hfill 100 & \hfill 7 & \hfill 1000 &\hfill 15 &\cr
\+ &  & \hfill 11000 &\hfill 16 &\cr}
\hfil
\vskip 1 cm
   
Les nombres $$\vartheta(j):=f(j)-f(j-1)$$
sont \`egaux \`a $\pm1$: si $k$ est de la forme $k=2^m(4i+1)$, $\vartheta
(k)=1$; si $k$ est de la forme $k=2^m(4i+3)$, $\vartheta(k)=-1$.
On peut constater une grande similarit\'e entre $\vartheta(k)$ et $v_2(k)$
du chapitre 2. La s\'erie g\'en\'eratrice de Dirichlet de la suite
$\vartheta(k)$ est
$$
\align
\sum_{k\ge 1}\vartheta(k)k^{-s}
&=\sum_{m\ge 0}\sum_{i\ge 0}2^{-ms}(4i+1)^{-s}
-\sum_{m\ge 0}\sum_{i\ge 0}2^{-ms}(4i+3)^{-s}\\
&=\frac{1}{1-2^{-s}}
\cdot\frac{1}{4^s}
\left(\zeta\big(s,\frac 14\big)-\zeta\big(s,\frac 34\big)
\right),
\endalign
$$
o\`u la fonction $\zeta(s,a)$ de Hurwitz est d\'efinie par
$$
\zeta(s,a)=\sum_{n\ge 0}(n+a)^{-s}\qquad\text{pour}\ \ \Re (s)>1.
$$
On peut \'ecrire
$$
B_n=\frac n2 +\frac{2}{\binom{2n}n}C_n,
$$
avec 
$$
C_n=\sum_{k\ge 1}F(k)\binom{2n}{n-k}.
$$
On veut trouver une fonction analogue \`a $E(z)$ (chapitre 2). Donc
on \'ecrit 
$$
\align
C_n&=\sum_{k\ge 1}F(k)\coeffu{n-k}(1+u)^{2n}\\
&=\coeffu n \sum_{k\ge 1}F(k)u^k(1+u)^{2n}\\
&=\coeffu n \sum_{k\ge 1}\sum_{0\le j<k}f(j) \ u^k(1+u)^{2n}\\
&=\coeffu n \sum_{j\ge 0}f(j)  u^j\frac{u}{1-u}(1+u)^{2n}\\
&=\coeffu n \sum_{j\ge 0}\sum_{0\le i\le j} \vartheta(i)
 u^j\frac{u}{1-u}(1+u)^{2n}\\
&=\coeffu n \sum_{i\ge 0} \vartheta(i)
 u^i\frac{u}{(1-u)^2}(1+u)^{2n}.
\endalign
$$
En g\'en\'eral, si on a une s\'erie $\Psi(z)$, et si on pose $z=u/(1+u)^2$,
on a d'apr\`es le theor\`eme de Cauchy
$$\align
\coeff n \Psi(z)&=
\frac{1}{2\pi i}\oint\frac{dz}{z^{n+1}}\Psi(z)\\
&=\frac{1}{2\pi i}\oint \frac{du(1-u)}{(1+u)^3}\frac{(1+u)^{2n+2}}{u^{n+1}}
\Psi\Big(\frac{u}{(1+u)^2}\Big)\\
&=\coeffu n (1-u)(1+u)^{2n-1}\Psi\Big(\frac{u}{(1+u)^2}\Big).
\endalign
$$
C'est pourquoi on peut \'ecrire
$$
C_n=\coeffu n \frac{u(1+u)}{(1-u)^3}
\sum_{i\ge 1}\vartheta(i)u^i.
$$
La fonction dans le membre droit de cette \'egalit\'e est l'analogue de
$E(z)$ du chapitre 2. On trouve facilement, que
$$
\frac{u(1+u)}{(1-u)^3}\sim\frac{2}{t^3}+\dots\ .
$$
Soit
$$
V(t)=\sum_{k\ge 1}\vartheta(k)e^{-kt},
$$
d'o\`u
$$
V^*(s)=\GG(s)\cdot \frac{1}{2^s}\cdot\frac{1}{2^s-1}
\left(\zeta\big(s,\frac 14\big)-\zeta\big(s,\frac 34\big)
\right).
$$
Par cons\'equant 
$$
V(t)=\frac{1}{2\pi i}\int\limits_{2-i\infty}^{2+i\infty}
\GG(s)\cdot \frac{1}{2^s}\cdot\frac{1}{2^s-1}
\left(\zeta\big(s,\frac 14\big)-\zeta\big(s,\frac 34\big)
\right)t^{-s}dt.
$$
La diff\'erence des fonctions de Hurwitz est une fonction enti\`ere;
l'int\'egrande a des p\^oles en $s=\chi_k$ et $s=0, -1, -2,\dots$ .
On a (voir \cite {22})
$$
\zeta\big(s,\frac 14\big)-\zeta\big(s,\frac 34\big)
\sim \frac 12 +s\left(2\log\GG\big(\frac 14\big)-\frac 12\log2-\log\pi
\right)+\dots
$$
pour $s\to0$. De m\^eme,
$$
\gather
\GG(s)\sim \frac 1s -\gamma+\dots\\
\frac{1}{2^s-1}\sim \frac{1}{\log2}\cdot \frac 1s -\frac 12 +\dots\\
(2t)^{-s}\sim 1-s\cdot \log(2t)+\dots
\endgather
$$
ce qui nous donne le r\'esidu en $s=0$
$$
-\frac 54 -\frac{\gamma}{2\log2}+2\log_2\GG(\frac 14)-\log_2\pi
-\frac 12\log_2t.
$$
Le  r\'esidu en $s=\chi_k$ pour $k\ne 0$ est simplement
$$
\frac{1}{\log2}\GG(\chi_k)
\left(\zeta\big(\chi_k,\frac 14\big)-\zeta\big(\chi_k,\frac 34\big)
\right)t^{-\chi_k}.
$$
On peut simplifier, puisque
$$
\zeta\big(\chi_k,\frac 34\big)=-\zeta\big(\chi_k,\frac 14\big).
$$
Donc, on obtient 
$$\align
C_n\sim\coeff n \frac{2}{t^3}\bigg(&-\frac 12\log_2t-\frac 54
-\frac{\gamma}{2\log2}
+2\log_2\GG\big(\frac14\big)-\log_2\pi\\
&+\frac{2}{\log2}\sum_{k\ne 0}\GG(\chi_k)\zeta\big(\chi_k,\frac14\big)
t^{-\chi_k}\bigg),
\endalign
$$
o\`u, avec $t\sim 2\varepsilon$
$$\align
C_n\sim\coeff n \bigg(&-\frac 18\varepsilon^{-3}\log_2\varepsilon
-\varepsilon^3\Big(
\frac{7}{16}+\frac{\gamma}{8\log2}
-\frac12\log_2\GG\big(\frac14\big)+\frac14\log_2\pi\Big)\\
&+\frac{1}{2\log2}\sum_{k\ne 0}\GG(\chi_k)\zeta\big(\chi_k,\frac14\big)
\varepsilon^{-3-\chi_k}\bigg).
\endalign
$$
On trouve, comme au chapitre 2, 
$$\gather
\coeff n\varepsilon^3\log\varepsilon\sim
\frac{4^n\sqrt n}{\sqrt\pi}\Big(-\log n+(2-\gamma-2\log2)\Big),\\
\coeff n\varepsilon^{-3}\sim \frac{2\cdot4^n\sqrt n}{\sqrt\pi},\\
\coeff n\varepsilon^{-3-\chi_k}\sim4^n\frac{n^{(1+\chi_k)/2}}
{\GG\left(\frac{3+\chi_k}{2}\right)}.
\endgather
$$
En regroupant les r\'esultats pr\'ec\'edents, on obtient
$$\align
C_n&\sim\frac{4^n\sqrt n}{\sqrt\pi}\log n\cdot\frac{1}{8\log2}\\
&+\frac{4^n\sqrt n}{\sqrt\pi}
\left(-\frac{1}{4\log2}-\frac{\gamma}{8\log2}-\frac 58+
\log_2\GG\big(\frac14\big)-\frac 12\log_2\pi
\right)\\
&+\frac124^n\sqrt n \frac{1}{\log 2}
\sum_{k\ne 0}\GG(\chi_k)\zeta\big(\chi_k,\frac14\big)
\frac{n^{\chi_k/2}}
{\GG\left(\frac{3+\chi_k}{2}\right)}.
\endalign
$$
On a par la formule de duplication
$$
\GG(\chi_k)\Big/ \GG\left(\frac{3+\chi_k}{2}\right)=
\frac{1}{1+\chi_k}
\frac{1}{\sqrt\pi}\GG\left(\frac{\chi_k}{2}\right).
$$
Avec
$$
\binom{2n}n\sim\frac{4^nn^{-1/2}}{\sqrt\pi},
$$
on obtient


$$
\align
\frac{D_n}{\binom{2n}n}\cdot\frac{1}{n}&\sim\frac 18\log_2n\\
&-\frac{1}{4\log2}-\frac{\gamma}{8\log2}-\frac 58+\log_2\Gamma\big(\frac14
\big)-\frac12\log_2\pi\\
&+\frac{1}{2\log2}\sum_{k\ne0}\zeta\big(\chi_k,\frac 14\big)\frac
{\Gamma(\chi_k/2)}{1+\chi_k}n^{\chi_k/2}.
\endalign
$$
Finalement on a trouv\'e le

\proclaim{Theor\`eme 2} Le nombre moyen d'\'echanges dans la fusion
paire-impaire de $2n$ \'el\'ements v\'erifie
$$
B_n\sim\frac 14n\log_2n+nB\big(\log_4n\big),
$$
ou $B(x)$ est une fonction continue p\'eriodique de p\'eriode 1; cette
fonction peut \^etre d\'evelopp\'ee en s\'erie de Fourier
$$
B(x)=\sum_{k\in \Bbb Z}b_ke^{2k\pi ix},
$$ 
avec
$$
b_0=-\frac{1}{2\log 2}
-\frac{\gamma}{4\log 2}-\frac 34+2\log_2\Gamma\big(\frac14
\big)-\log_2\pi
$$
et pour $k\ne 0$
$$
b_k=\frac{1}{\log 2}\zeta\big(\chi_k,\frac 14\big)\frac
{\Gamma(\chi_k/2)}{1+\chi_k}.
$$
\endproclaim

\newpage

\head 4. La hauteur des feuilles dans les arbres planaires \endhead

On peut comprendre la probl\'ematique de ce chapitre tr\`es simplement
en consid\'erant l'example d'un arbre planaire:

$$
%\includegraphic{baum2}
$$

Cet arbre a 4 feuilles de hauteur (de gauche \`a droite) $3, 3, 4, 2$. 
Nous remarquons que la hauteur de l'arbre est donn\'ee par la hauteur de la
feuille la plus haute. Nous imaginons maintenant que les feuilles sont
ordonn\'ees par ordre d\'ecroissant 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\^eme hauteur.
Pour faciliter les calculs, nous compl\'etons cette
suite par une infinit\'e de z\'eros. 
Ainsi, nous pouvons parler de la $d$-i\`eme
feuille pour n'importe quel $d$, m\^eme si l'arbre a moins de $d$ feuilles.

On consid\`ere maintenant $h_n^{(d)}$, la hauteur de la $d$-i\`eme 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\'ej\`a dans divers articles, voir
\cite{1}, \cite{12}, \cite{13}, \cite{14}, \cite{20}.

\proclaim{Lemme 1} Soit $F(z,y)$ la s\'erie g\'en\'eratrice telle que
$\left[z^ny^m\right]F$ soit le nombre d'arbres de taille $n$ avec $m$
feuilles (l'arbre $\circ$ a z\'ero feuilles); on a alors pour tout
$p\ge 0$
$$
F^p(z,y)=z^p+p\sum_{0\le\lambda<n}
z^ny^{n-\lambda}\frac 1n \binom n\lambda\binom{n-p-1}{\lambda-p}.
$$
\endproclaim
\demo{Id\'ee de la demonstration} (Voir \cite{12}) On introduit
$G(z,y)$, la quantit\'e analogue, o\`u on consid\`ere que
$\circ$ a une feuille; en traduisant l'\'equation symbolique pour
les arbres planaires, on obtient
$$
G(z,y)=z\bigg(y+\sum_{r\ge 1}G^r(z,y)\bigg)=
\big(1-z(1-y)\big)P\left(\frac{zy}{\big(1-z(1-y)\big)^2}\right).
$$
On utilise le d\'eveloppement classique
$$
P^m(z)=\sum_{k\ge 0}\left[\binom{2k+m-1}{k}-\binom{2k+m-1}{k-1}\right]
z^{k+m}.
$$
Apr\`es avoir utilis\'e deux fois le th\'eor\`eme binomial, on se sert de l'
identit\'e
$$
\sum_{k\ge 0}\binom rk\binom{s+k}p(-1)^k=(-1)^r\binom s{p-r}
$$
pour obtenir
$$
G^p(z,y)=z^py^p+p\sum_{p\le\lambda\le n}
z^ny^\lambda\frac 1n \binom n\lambda\binom{n-p-1}{\lambda-p}.
$$
Enfin, on peut constater que
$$
F(z,y)=G(z,y)-zy+z=G(zy,y^{-1}),
$$
d'o\`u la formule annonc\'ee.
\enddemo

\proclaim{Lemme 2} Soit $A_k(z)$ la s\'erie g\'en\'eratrice des
arbres de hauteur $\le k$ et, comme pr\'ec\'edemment, $z=u/(1+u)^2$.
On a
$$
A_k(z)=\frac{u}{1+u}\cdot\frac{1-u^k}{1-u^{k+1}}.
$$
\endproclaim
\demo{D\'emonstration} En traduisant l'\'equation symbolique pour la famille
$\Cal P$, on obtient
$$
A_k=\frac{z}{1-A_{k-1}}
,\qquad k\ge 1, \quad A_0=0;
$$
on peut donc d\'emontrer la formule tr\`es facilement par
r\'ecurrence. \qed
\enddemo

\proclaim{Lemme 3} Soit $Q_k(z,y)$ la s\'erie g\'en\'eratrice,
o\`u $[z^ny^m]Q_k$ est le nombre d'arbres de taille $n$ avec $m$
n\oe uds au niveau $k$, qui est le niveau maximal. (C'est \`a dire,
si $m\ge 1$, la hauteur d'arbre est exactement $k$.) On a pour $k\ge 1$
et $d\ge 1$
$$
[y^d]Q_k(z,y)=A_{k-1}^{d+1}(z)-A_{k-1}^{d}(z)+zA_{k-1}^{d-1}(z).
$$
\endproclaim
\demo{D\'emonstration} En traduisant comme d'habitude, on obtient
$$
Q_1=zy\qquad\text{et}\qquad Q_k=\frac{z}{1-Q_{k-1}}\quad
\text{pour $k\ge 2$.}
$$
Comme on a
$$
[y^0]Q_k(z,y)=A_{k-1}(z),
$$
il suffit de d\'emontrer que
$$
\align
Q_k(z,y)&=A_{k-1}(z)+\sum_{d\ge 1}y^d\Big(
A_{k-1}^{d+1}(z)-A_{k-1}^{d}(z)+zA_{k-1}^{d-1}(z)\Big)\\
&=\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}};
\endalign
$$
ce qui est un simple exercice, en utilisant la r\'ecurrence des
$A_k$.
\enddemo

Soit $B_{d,k}(z)$ la s\'erie g\'en\'eratrice,
o\`u $[z^n]B_{d,k}$ est le nombre d'arbres de taille $n$ o\`u
$d$ feuilles sont \`a hauteur $>k$ et toutes les autres sont \`a
hauteur $\le k$. On peut constater que $B_{0,k}+B_{1,k}+\dots+
B_{d-1,k}$ est la s\'erie g\'en\'eratrice d'arbres o\`u la $d$-i\`eme
feuille (au sens d\'efini dessus) est \`a hauteur $\le k$.
Donc la quantit\'e $h_n{(d)}$
est donn\'ee par
$$
h_n^{(d)}=\frac{\coeff n \sum_{k\ge 0}\Big(P(z)-B_{0,k}(z)-B_{1,k}(z)-\dots-
B_{d-1,k}(z)\Big)
}{\coeff n P(z)}.
$$
\proclaim{Lemme 4} La hauteur moyenne d'un arbre planaire de taille
$n$ v\'erifie
$$
\frac{\coeff n \sum_{k\ge 0}\Big(P(z)-B_{0,k}(z)\Big)
}{\coeff n P(z)}\sim\sqrt{\pi n}-\frac 12+\dots\ .
$$
\endproclaim
\demo{Id\'ee de la demonstration} On trouve que
$$
\align
\sum_{k\ge 0}\Big(P(z)-B_{0,k}(z)\Big)
&=\sum_{k\ge 0}\Big(P(z)-A_{k}(z)\Big)\\
&=\frac{1-u}{1+u}\sum_{k\ge1}\frac{u^k}{1-u^k}
=\frac{1-u}{1+u}\sum_{k\ge1}d(k)u^k
\endalign
$$
o\`u $d(k)$ est le nombre de diviseurs de $k$. On constate que
$$
\sum_{k\ge1}d(k)k^{-s}=\zeta^2(s),
$$
et on peut utiliser la transformation de Mellin comme au chapitre 2.
\enddemo

Comme dans les chapitres 2 et 3 on va d\'emontrer aue
$$
\sum_{k\ge 0}B_{s+1,k}(z)\sim A_s-B_st+\dots,
$$
o\`u $A_s$ et $B_s$ sont des constantes et $u=e^{-t}$. Comme
$$
P(z)=\frac{u}{1+u}\sim\frac 12-\frac 14t+\dots,
$$
on peut conclure que
$$
\coeff n \sum_{k\ge 0}B_{s+1,k}(z)\bigg/t_n\sim4B_s.
$$
\proclaim{Lemme 5} On a pour $s\ge 0$
$$
\sum_{n\ge p}z^n\binom ns\binom{n-p}s=
\sum_{j=0}^s\frac{z^{s+p+j}}{(1-z)^{s+1+j}}
\frac{(p+s)!(s+j)!}{j!(s-j)!(p+j)!s!}.
$$
\endproclaim
\demo{D\'emonstration} Avec $D=d/dz$ et $(n)_d=n(n-1)\dots(n-d+1)$ on a
$$\align
\sum_{n\ge p}z^n\binom ns\binom{n-p}s&=
\frac{1}{(s!)^2}
\sum_{n\ge 0}(n)_sz^sD^sz^{n+p}\\
&=\frac{1}{(s!)^2}
z^sD^sz^{p+s}\sum_{n\ge 0}z^n\\
&=\frac{1}{s!}z^sD^s\frac{z^{p+s}}{(1-z)^{s+1}}\\
&=\frac{1}{s!}z^s\sum_{j=0}^s\binom sj\big[D^{s-j}z^{p+s}\big]
\big[D^{j}(1-z)^{-s-1}\big].\qed
\endalign
$$
\enddemo
\proclaim{Lemme 6} On a pour $s\ge 0$ et $k\ge 1$
$$\align
B_{s+1,k}(z)&=\sum_{j=0}^s
\frac{(s+j)!}{j!(s-j)!(s+1)!}\left(\frac{u}{1+u+u^2}\right)^{s+1+j}\\
&\times\frac{(1-u)^2}{1+u}
\frac{u^{k-1}}{(1-u^{k-1})(1-u^k)}
\sum_{p\ge 1}\frac{p(p+s)!}{(p+j)!}A_{k-1}^p.
\endalign
$$
\endproclaim

\demo{D\'emonstration}
On remplace chaque feuille au niveau maximal $k$ (marqu\'ee par $y$ en
$Q_k(z,y)$) par un arbre arbitraire dont les feuilles sont marqu\'ees par
$y$. Alors
$$\align
B_{s+1,k}&=\left[y^{s+1}\right]Q_k\Big(z,\frac 1zF(z,y)\Big)\\
&=\left[y^{s+1}\right]
\sum_{p\ge1}\Big[\frac 1zF(z,y)\Big]^p
\Big[A_{k-1}^{p+1}-A_{k-1}^{p}+zA_{k-1}^{p-1}\Big]\\
&=\sum_{p\ge1}z^{-p}p\sum_{n\ge 1}z^n
\frac 1n\binom{n}{s+1}\binom{n-p-1}{s}A_{k-1}^p
\big[A_{k-1}-1+zA_{k-1}^{-1}\big].
\endalign
$$
La formule annonc\'ee est obtenue en remarquant que
$$
\gather
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}
\endgather
$$
et en utilisant le Lemme 5.
\enddemo

\proclaim{Lemme 7} La s\'erie g\'en\'eratrice $B_{s+1,k}(z)$ est donn\'ee
par
$$
\align
B_{s+1,k}(z)&=\sum_{j=0}^s\sum_{i=0}^{s-j}
\frac{(s+j)!(i+1)}{j!(s-j-i)!(j+i+1)!}\times\\&\times
\left(\frac{u}{1+u+u^2}\right)^{s+1+j}
(1-u)^2u^{i+1}u^{k-1}\frac{(1-u^{k-1})^i}{(1-u^{k+1})^{i+2}}.
\endalign
$$
\endproclaim
\demo{D\'emonstration} On utilise la formule
(d\'eduite de la formule de {\sl Vandermonde})
$$
\frac{p(p+s)!}{(s-j)!(s+1)!(p+j)!}=
\sum_{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
$$
\sum_{p\ge1}\binom{p}{i+1}A_{k-1}^p=
\frac{A_{k-1}^{i+1}}{\big(1-A_{k-1}\big)^{i+2}}
$$
Nous sommes pr\^ets \`a  attaquer  la d\'etermination
des d\'eveloppements locaux en
$\sum_{k\ge0}B_{s+1,k}$. On constate facilement que
$$
\frac{u}{1+u+u^2}\sim\frac 13;\qquad
(1-u)^2\sim t^2(1-t);\qquad u^{i+1}\sim 1-(i+1)t.
$$
\enddemo

\proclaim{Lemme 8} On a le d\'eveloppement local
$$\align
&\sum_{k\ge 0}u^{k-1}\frac{(1-u^{k-1})^i}{(1-u^{k+1})^{i+2}}\\
&\sim
t^{-2}(1+2t)\bigg(
\sum_{l=0}^i\binom il (-2)^l(1+lt)\Big(
\zeta(l+2)-\frac l2\zeta(l+1)t
\Big)-\frac 12t
\bigg).
\endalign
$$
\endproclaim
\demo{D\'emonstration}
On peut \'ecrire
$$
\align
\sum_{k\ge 0}u^{k-1}\frac{(1-u^{k-1})^i}{(1-u^{k+1})^{i+2}}
&=u^{-2}\sum_{k\ge1}\frac{u^k}{(1-u^k)^2}\bigg(1+
\frac{(1-u^{-2})u^k}{1-u^k}\bigg)^i\\
&=u^{-2}\sum_{l=0}^i\binom il \big(1-u^{-2}\big)^l\sum_{k\ge1}
\frac{u^{k(l+1)}}{(1-u^k)^{l+2}}.
\endalign
$$
On voit imm\'ediatement que
$$
u^{-2}\sim1+2t\qquad\text{et}\qquad(1-u^{-2})^l\sim(-2)^lt^l(1+lt).
$$
On applique encore la transformation de Mellin:
$$
\align
\Cal M \sum_{k\ge1}\frac{e^{-tk(l+1)}}{(1-e^{tk})^{l+2}}
&= \sum_{k\ge1}k^{-s}\Cal M\frac{e^{-t(l+1)}}{(1-e^{t})^{l+2}}\\
&=\zeta(s)\GG(s)\sum_{\ll\ge0}\binom{\ll}{l+1}\ll^{-s}\\
&=\zeta(s)\GG(s)\sum_{\ll\ge0}\frac{1}{(l+1)!}
\sum_{i=0}^{l+1}s_{l+1,i}\ll^i\ll^{-s}\\
\intertext{
(o\`u les $s_{l+1,j}$ sont les nombres {\sl Stirling} de premi\`ere
esp\`ece)}
&=\frac{1}{(l+1)!}\zeta(s)\GG(s)\sum_{i=0}^{l+1}s_{l+1,i}\zeta(s-i).
\endalign
$$
Comme au chapitre 2 on utilise la formule d'inversion de Mellin;
on change le chemin d'int\'egration en prenant en compte les
r\'esidues. Dans notre probl\`eme, il suffit de consid\'erer
les termes o\`u $i=s+1$ et $i=s$. On peut constater que
$$
s_{l+1,l+1}=1\qquad\text{et}\qquad s_{l+1,l}=-\binom{l+1}2.
$$
\enddemo

\proclaim{Lemme 9} La somme des $B_{s+1,k}(z)$ v\'erifie
 le d\'eveloppement local
$$
\sum_{k\ge0}B_{s+1,k}(z)\sim\text{const}-
\frac 12t\sum_{j=0}^s\sum_{i=0}^{s-j}
\frac{(s+j)!(i+1)}{j!(s-j-i)!(j+i+1)!}3^{-s-1-j}.
$$
\endproclaim
\demo{Id\'ee de la D\'emonstration}
$$
\align
\sum_{k\ge0}B_{s+1,k}(z)&\sim\sum_{j=0}^s\sum_{i=0}^{s-j}
\frac{(s+j)!(i+1)}{j!(s-j-i)!(j+i+1)!}3^{-s-1-j}
t^2(1-t)\big(1-(i+1)t\big)\times\\
&\times t^{-2}(1+2t)\bigg(
\sum_{l=0}^i\binom il (-2)^l(1+lt)\Big(
\zeta(l+2)-\frac l2\zeta(l+1)t
\Big)-\frac 12t
\bigg)
\endalign
$$
On veut obtenir le coefficient de $t$ dans cette expression. C'est une 
chose tr\`es simple; apr\`es quelques manipulations de nombreuses
simplifications apparaissent. \qed
\enddemo

A partir des \'egalit\'es pr\'ec\'edentes, on tire
$$
\coeff n B_{s+1,k}(z)\Big/ t_n
\sim 
4\cdot \frac 12\sum_{j=0}^s\sum_{i=0}^{s-j}
\frac{(s+j)!(i+1)}{j!(s-j-i)!(j+i+1)!}3^{-s-1-j}.
$$
Pour la quantit\'e $h_n^{(d)}$ on doit sommer:
$$
\sum_{s=0}^{d-2}2\sum_{j=0}^s\sum_{i=0}^{s-j}
\frac{(s+j)!(i+1)}{j!(s-j-i)!(j+i+1)!}3^{-s-1-j}.
$$
On peut \'ecrire pour cette quantit\'e
$$
\sum_{s=0}^{d-2}\frac{2}{(s+1)3^{s+1}}
\left[x^s\right]
\frac{1}{(1-x)^2}
\left(\frac{1+x}{1-\frac x3}\right)^{s+1}.
$$
Donc nous avons le

\proclaim{Theor\`eme 3} La hauteur moyenne de la {$d$-i\`eme} feuille  
d'un arbre planaire de taille $n$, a le d\'eveloppement
asymptotique (pour $d$ fixe et $n
\to\infty$)
$$
h_n^{(d)}=\sqrt{\pi n}-\frac 12-
\sum_{s=0}^{d-2}\frac{2}{(s+1)3^{s+1}}
\left[x^s\right]
\frac{1}{(1-x)^2}
\left(\frac{1+x}{1-\frac x3}\right)^{s+1}
+\ o(1).
$$
\endproclaim

\head 5. Quelques remarques sur la technique d'extraction de coefficients
\endhead

Si on suit la strat\'egie mentionn\'ee dans le titre, les probl\`emes
de d\'enombrement d'arbres demandent souvent d'\'evaluer des sommes
du type
$$
\sum_{k\ge1}\omega(k)
\frac{\binom{2n}{n+k+1}-2\binom{2n}{n+k}+\binom{2n}{n+k-1}}{\binom{2n}{n}}
.
$$
o\`u $\omega(k)$ peut \^etre, par exemple, $v_2(k)$ ou $\vartheta(k)$
ou $d(k)$ comme dans les chapitres 2, 3 et 4.

On a besoin d'approximations de certains coefficients 
binomiaux dans une r\'egion
centrale (p.e. $|k|\le \sqrt n\log n$). On obtient, par exemple par la
formule de {\sl Stirling}
$$
\frac{\binom{2n}{n+k}}{\binom{2n}{n}}\sim
e^{-k^2/n}\cdot\left(
1+\frac{k^2}{2n^2}-\frac{k^4}{6n^3}+\dots\right)
$$
(voir \cite 9 pour une formule g\'en\'erale). On voit souvent
apparaitre les diff\'erences {$r$-i\`emes} de coefficients binomiaux
$$
\xi=\coeffu n
u^k(1-u)^r(1+u)^{2n}\bigg/\binom{2n}n
=\sum_{\ll=0}^r
(-1)^\ll\binom r\ll \binom{2n}{n+k+r}\bigg/\binom{2n}n.
$$
On rappelle l'op\'erateur des diff\'erences $\Delta$:
$$
\Delta^r \binom{2n}{n+k}=\sum_{\ll=0}^r
\binom r\ll(-1)^{r-\ll} \binom{2n}{n+k+\ll}
$$
Nous consid\'erons $\Delta^re^{-k^2/n}$. Pour cela, on a besoin des polynomes
d'{\sl Hermite}. Voici les propri\'et\'ees 
necessaires \cite 3:
$$
\gather
e^{2zt-t^2}=\sum_{n\ge0}H_n(z)\frac{t^n}{n!}\\
H_0=1,\quad H_1=2z,\quad H_{n+1}=2zH_n-2nH_{n-1}\\
H_n(z)=\sum_{k\ge0}\frac{n!}{k!(n-2k)!}(-1)^k(2z)^{n-2k}\\
H_n(-z)=(-1)^nH_n(z)
\endgather
$$
Donc
$$
\align
\Delta^re^{-k^2/n}&=\sum_{\ll=0}^r(-1)^{r-\ll}
\binom r\ll e^{-(k+\ll)^2/n}\\
&=e^{-k^2/n}\sum_{\ll=0}^r(-1)^{r-\ll}
\binom r\ll e^{-\frac{2k\ll}{n}-\frac{\ll^2}{n}}\\
&=e^{-k^2/n}\sum_{\ll=0}^r(-1)^{r-\ll}
\binom r\ll 
\sum_{m\ge0}H_m\left(-\frac{k}{\sqrt n}\right)\left(\frac{\ll}{\sqrt n}
\right)^m\frac{1}{m!}.
\endalign
$$
On sait (avec les nombres de {\sl Stirling\/} de second esp\`ece) que
$$
\sum_{\ll=0}^r(-1)^{r-\ll}
\binom r\ll \ll^m=r!S_{m,r}.
$$
Donc
$$
(-1)^r\Delta^re^{-k^2/n}\sim
e^{-k^2/n}\left[
H_{r}\left(\frac{k}{\sqrt n}\right)\frac{1}{n^{r/2}}-
H_{r+1}\left(\frac{k}{\sqrt n}\right)\frac{1}{n^{(r+1)/2}}\frac r2+\dots
\right].
$$
On trouve donc
$$
\xi\sim e^{-k^2/n}H_{r}\left(\frac{k}{\sqrt n}\right)\frac{1}{n^{r/2}},
$$
r\'esultat annonc\'ee en \cite 5.
\medskip

Pour obtenir plusieurs termes, on  doit consid\'erer $\displaystyle{
\Delta^rk^te^{-k^2/n}}$.

On peut utiliser la formule g\'en\'erale (de type {\sl Leibniz}):
$$
\Delta^rf(k)g(k)  =\sum_{\ll=0}^r\binom r\ll \Big(\Delta^{r-\ll}f(k+\ll)
\Big) \Big(\Delta^{\ll}g(k)\Big)
$$
avec $f(k)=k^t$ et $g(k)=e^{-k^2/n}$.
\medskip

Si on a (pour un certain polynome $p$)
$$
\coeffu n u^kp(u)(1+u)^{2n},
$$
on peut d\'evelopper $p(u)$ en puissances de $1-u$ et utiliser la
machinerie comme nous l'avons indiqu\'e.
\medskip

Dans de nombreux autres cas, on rencontre les quantit\'es
$$
\coeffu n u^k\frac{1}{1-u} (1+u)^{2n};
$$
c'est \`a dire qu'on doit consid\'erer
$$
\sum_{j\ge k}e^{-j^2/n}\sim\sqrt n \erfc\Big(\frac{k}{\sqrt n}\Big)
+\frac 12 e^{-k^2/n}+\dots,
$$ avec la formule de sommation d'{\sl Euler\/} et la fonction
d'erreur
$$
\erfc(z):=\int_z^\infty e^{-t^2}dt.
$$
\medskip

Pour obtenir plusieurs termes, on doit consid\'erer
$$
I_m(z)=\int_z^\infty t^m e^{-t^2}dt;
$$
on peut \'evaluer cette int\'egrale avec une int\'egration par parties:
$$
\gather
I_m(z)=\frac{m-1}{2}I_{m-2}(z)+\frac 12z^{m-1}e^{-z^2},\\
I_1(z)=\frac 12e^{-z^2},\qquad I_0(z)=\erfc(z).
\endgather
$$
Enfin un probl\`eme plus g\'en\'eral de m\^eme nature apparait dans
l'evaluation des sommes du type
$$
\coeffu n u^k\frac{1}{(1-u)^a} (1+u)^{2n}
$$
o\`u $a$ est un nombre entier $\ge1$.










\Refs\nofrills{Bibliographie}

\ref \no 1\by de Bruijn, Knuth, Rice\jour \yr 1972\pages 15--22
        \vol \paper The average height of planted plane trees
        \inbook Graph Theory and Computing \eds R.C. Read
        \publ Academic Press \publaddr New York\endref

\ref \no 2\by Dieudonn\'e \yr 1968\book Calcul Infinitesimal
         \publ Hermann \publaddr Paris\endref

\ref \no 3\by Erd\'elyi, Magnus, Oberhettinger,
        Tricomi \yr 1955\book Higher Transcendental Functions
        \publ Mc-Graw-Hill \endref

\ref \no 4\by Flajolet\jour Cahiers du BURO\yr 1981
        \pages 1--209\vol 34--35\paper Analyse d'algorithmes
        d'arbres et de fichiers\endref

\ref \no 5\by Flajolet, Raoult, Vuillemin
        \jour Theor. Comput. Sci. \yr 1979\pages 99--125\vol 9
        \paper The number of registers required for evauluating
        arithmetic expressions\endref

\ref \no 6\by Flajolet, Ramshaw\jour SIAM J. on Computing
        \yr 1980\pages 142--158\vol 9\paper A note on Gray Code and
        odd-even merge\endref

\ref \no 7\by Flajolet, Odlyzko\jour J. Comput. Syst. Sci.
        \yr 1982\pages 171--213\vol 25\paper The average height of binary
        trees and other simple trees\endref

\ref \no 8\by Flajolet, Prodinger\jour SIAM J. on Computing
        \yr 1986\pages 629--640\vol 15\paper Register Allocation
        for unary-binary Trees\endref

\ref \no 9\by Greene, Knuth\book Mathematics for the 
        Analysis of Algorithms \yr 1981 \publ Birkh\"auser \endref

\ref \no 10\by Jungen\jour Commentarii Math. Helvetici
        \yr 1931\pages 266--306\vol 3\paper Sur les s\'eries de Taylor
        n'ayant que des singularit\'es alg\'ebro-logarithmiques sur
        leur cercle de convergence\endref

\ref \no 11\by Kemp\jour Acta. Inf.\yr 1979\pages 363--372\vol 11
        \paper The average number of registers to evaluate a binary tree
        optimally\endref

\ref \no 12\by Kemp\jour Combinatorica\yr 1982\pages 157--176\vol 2
        \paper On the average oscillation of a stack\endref

\ref \no 13\by Kemp\jour Journal of Combinatorial Theory Ser. B\yr 1983
        \pages 191--208\vol B 34\paper The average height of planted
        plane trees with $m$ leaves\endref

\ref \no 14\by Kemp\jour Discrete Mathematics\yr 1990\pages 247--258
        \vol 81\paper 
        On the number of deepest nodes in ordered trees\endref

\ref \no 15\by Knuth\book The Art of Computer Programming,Vol.1 
        \publ Addison-Wesley\yr 1968\endref

\ref \no 16\by Knuth\book The Art of Computer Programming,Vol.3 
        \publ Addison-Wesley\yr 1968\endref

\ref \no 17\by Meir, Moon and Pounder\jour SIAM J. on Alg. Disc. Meth.
        \yr 1980\pages 25--33\vol 1\paper On the order of random channel
        networks\endref

\ref \no 18\by Prodinger\jour Europ. J. on Combinatorics
        \yr 1984\pages 351--357\vol 5\paper The average height of 
        the second highest leaf of a
        planted plane trees\endref

\ref\no 19
        \paper Die Bestimmung gewisser Parameter von 
        bin\"aren  B\"aumen mit Hilfe analytischer Methoden
        \jour Lecture Notes in Mathematics  (E.Hlawka, Ed.)
        \vol 1114 \yr 1985\pages 118--133\by Prodinger
        \endref

\ref \no 20  
        \paper The Average Height of the d-th Highest Leaf of a 
        Planted Plane Tree
        \jour Networks \vol 16 \yr 1985\pages  67--75 \by Prodinger
        \endref

\ref \no 21\by Sedgewick\jour SIAM J. on Computing\yr 1978\pages 239--272
        \vol 7\paper Data movement in odd-even merge\endref

\ref \no 22\by Whittaker, Watson\book A course in modern analyis \yr 1930
        \publ Cambridge University Press \endref


\endRefs











\enddocument


