% plain tex format
% please mask the next line by adding %
% \input Ottfont


\magnification =1200
\parindent     =0pt
\hsize         =11.25cm
\vsize         =18cm
\hoffset       =1cm

\line{\hfil le 12 Novembre 1996}
\bigskip

\centerline{\bf D\'emonstration Combinatoire des Formules }
\centerline{\bf de Prodinger Concernant les Arbres Binaires}
\medskip
\centerline{Guo-Niu HAN}

\bigskip
{\bf 1. Introduction}.---
Nous consid\'erons les arbres binaires d'ordre~$n$.  Il est bien connu que le
nombre de ces arbres est \'egal au nombre de Catalan
$c_n={1\over n+1}{2n\choose{n}}$. Pour $m=0, 1$ ou~2, on d\'efinit
{\it $m$-noeuds} comme \'etant les noeuds ayant $m$ fils. En particulier, les
0-noeuds ne sont d'autre que les feuilles.

\medskip
Dans [M], Mahmoud a trouv\'e trois formules qui donnent le nombre des arbres
binaires ayant j feuilles, j 1-noeuds et j 2-noeuds respectivement. D'apr\`es
ces r\'esultat, Prodinger a trouv\'e trois formules closes pour ces m\^emes
nombres [P], en utilisant le logiciel Ekhad, d\'evelopp\'e par Zeilberger~[Z].

\medskip
Dans cette note, on trouvera une d\'emonstration combinatoire pour ces formules.

\bigskip
{\bf 2. Formule de Prodinger}.---
Dans un arbre binaire, il est facile \`a v\'erifier que le nombre des feuilles
est \'egal au nombre des 2-noeuds plus 1. Les formules de Prodinger se
r\'eduisent donc \`a une seule formule [P] :

\medskip
{\bf Th\'eo\`eme} [Prodinger].---{\it Le nombre des arbres binaires
d'ordre~$n$ ayant
$j$ feuilles est \'egal \`a}
$$ A_n^j = {2^{n+1-2j} (n-1)!\over j!(j-1)!(n+1-2*j)! }.$$

\bigskip
{\bf 3. D\'emonstration Combinatoire}.---
Consid\'erons les mots finis engendr\'es par l'alpha\-bet $\{U, D, R, L\}$ (Up,
Down, Right, Left). Un tel mot $w$ est dit de {\it Grand-Motzkin} si $|w|_D
= |w|_U$.
Il est \'evident que le nombre des mots de Grand-Motzkin d'ordre~$n$ ayant $j$
$Down$ est \'egal \`a
$$B_n^j = {n \choose j, j, n-2*j} 2^{n-2*j}.$$

\medskip
Un mot $w=x_1 x_2 \cdots x_{n-1}D$
est dit de {\it Motzkin}, si $x_1 x_2 \cdots x_{n-1}$ est de Grand-Motzkin et si
$|x_1 x_2 \cdots x_i|_D \le |x_1 x_2 \cdots x_i|_U$ pour tout $1\le i\le n-1$.
Soit $w$ un mot de Motzkin d'ordre~$n$ ayant~$j$ $Down$, il existe $j$
fa\c cons de factoriser ce mot sous la forme
$w=uDv$.
C'est clair que la concatenation $vu$ est un mot de Grand-Motzkin, et que le
nombre des mots de Motzkin d'ordre~$n$ ayant~$j$
$Down$ est $jB^{j-1}_{n-1} =  A^j_n$.

\medskip
Enfin, la formule de Prodinger est assur\'ee par une simple bijection
entre les arbres binaires et les mots de Motzkin, qui envoie les feuilles en
$Down$, les 2-noeuds en $Up$, et les 1-noeuds ayant un fils droit en $Right$,
les 1-noeuds ayant un fils gauche en $Left$.

\medskip
Exercice.--- Tracer l'arbre binaire correspondant au mot de Motzkin $w=$
$ULDRUULDRDRD$.

\vskip 2cm

\centerline{BIBLIOGRAPHIE}

\bigskip

\medskip
[M] H. M. Mahmoud. The joint distribution of the three types of nodes in
uniform binary
trees. {\it Algorithmica}, 13:313-323, 1995.

\medskip
[P] H. Prodinger. A note on the distribution of the three types of nodes in
uniform binary
trees. {\it S\'eminaire Lotharingien de Combinatoire}, B38b, 5pp, 1996.
{\tt http://cartan.u-strasbg.fr/\~{}slc/}

\medskip
[Z] M. Petkovsek, H. Wilf, and D. Zeilberger. $A=B$. A.K. Peters, Ltd., 1996.

\vskip 1cm

\hfill\hbox{\vbox{\hrule width 4cm}}

\medskip

\line{\hfill IRMA, Universit\'e Louis Pasteur \& CNRS}
\line{\hfill 7, rue Ren\'e-Descartes}
\line{\hfill 67084 Strasbourg Cedex, France}
\line{\hfill \tt email: guoniu@math.u-strasbg.fr}


\vfil

\end