%%  This article has been submitted and accepted for publication in
%%  THE FOATA FESTSCHRIFT, 
%%  a special issue of THE ELECTRONIC JOURNAL OF COMBINATORICS
%%  dedicated to DOMINIQUE FOATA at the occasion of his 60th birthday.
%%
%%  Author(s):		DOMINIQUE DUMONT AND ARMAND RAMAMONJISOA
%%  Title:		GRAMMAIRE DE RAMANUJAN ET ARBRES DE CAYLEY
%%  Date of submission:	February 25, 1995
%%  TeX version:	plain TeX
%%  File size (approx):	62 kB
%%  Number of pages:	16
%%  Author's email:	not available
%%
%%
\magnification=1200

\hsize=11.25cm    
\vsize=18cm       
\parindent=12pt   \parskip=0pt     
\pageno=1 


\hoffset=7 mm   
\voffset=8 mm  

\catcode`\@=11

\font\eightrm=cmr8         \font\eighti=cmmi8
\font\eightsy=cmsy8        \font\eightbf=cmbx8
\font\eighttt=cmtt8        \font\eightit=cmti8
\font\eightsl=cmsl8        \font\sixrm=cmr6
\font\sixi=cmmi6           \font\sixsy=cmsy6
\font\sixbf=cmbx6

% Fontes AMS

\font\tengoth=eufm10       \font\tenbboard=msbm10
\font\eightgoth=eufm7 at 8pt      \font\eightbboard=msbm8
\font\sevengoth=eufm7      \font\sevenbboard=msbm7
\font\sixgoth=eufm6        \font\fivegoth=eufm5

\skewchar\eighti='177 \skewchar\sixi='177
\skewchar\eightsy='60 \skewchar\sixsy='60

\newfam\gothfam           \newfam\bboardfam

\def\tenpoint{%
  \textfont0=\tenrm \scriptfont0=\sevenrm \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\tenrm\let\bigf@nt=\tenrm\let\smallf@nt=\sevenrm}%
  \textfont1=\teni  \scriptfont1=\seveni  \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\teni}\let\old=\oldstyle
  \textfont2=\tensy \scriptfont2=\sevensy \scriptscriptfont2=\fivesy
  \def\calfont{\fam2 \tensy}%
  \textfont\gothfam=\tengoth \scriptfont\gothfam=\sevengoth
  \scriptscriptfont\gothfam=\fivegoth
  \def\gothfont{\fam\gothfam\tengoth}%
  \textfont\bboardfam=\tenbboard \scriptfont\bboardfam=\sevenbboard
  \scriptscriptfont\bboardfam=\sevenbboard
  \def\bbfont{\fam\bboardfam\tenbboard}%
  \textfont\itfam=\tenit
  \def\it{\fam\itfam\tenit\let\bigf@nt=\tenit \let\smallf@nt=\eightit}%
  \textfont\slfam=\tensl
  \def\sl{\fam\slfam\tensl}%
  \textfont\bffam=\tenbf \scriptfont\bffam=\sevenbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\tenbf\let\bigf@nt=\tenbf \let\smallf@nt=\sevenbf}%
  \textfont\ttfam=\tentt
  \def\tt{\fam\ttfam\tentt}%
  \abovedisplayskip=13pt plus 3pt minus 9pt
   \belowdisplayskip=11pt plus 3pt minus 9pt
    \abovedisplayshortskip=6pt plus 3pt
     \belowdisplayshortskip=11pt plus 3pt minus 9pt
  \smallskipamount=3pt plus 1pt minus 1pt
  \medskipamount=6pt plus 2pt minus 2pt
  \bigskipamount=12pt plus 4pt minus 4pt
  \normalbaselineskip=13pt
  \setbox\strutbox=\hbox{\vrule height8.5pt depth3.5pt width0pt}%
  \normalbaselines\rm}

\def\eightpoint{%
  \textfont0=\eightrm \scriptfont0=\sixrm \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\eightrm\let\bigf@nt=\eightrm\let\smallf@nt=\sixrm}%
  \textfont1=\eighti  \scriptfont1=\sixi  \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\eighti}\let\old=\oldstyle
  \textfont2=\eightsy \scriptfont2=\sixsy \scriptscriptfont2=\fivesy
  \def\calfont{\fam2 \eightsy}%
  \textfont\gothfam=\eightgoth \scriptfont\gothfam=\sixgoth
  \scriptscriptfont\gothfam=\fivegoth
  \def\gothfont{\fam\gothfam\eightgoth}%
  \textfont\bboardfam=\eightbboard \scriptfont\bboardfam=\sevenbboard
  \scriptscriptfont\bboardfam=\sevenbboard
  \def\bbfont{\fam\bboardfam\eightbboard}%
  \textfont\itfam=\eightit
  \def\it{\fam\itfam\eightit\let\bigf@nt=\eightit\let\smallf@nt=\eightit}%
  \textfont\slfam=\eightsl
  \def\sl{\fam\slfam\eightsl}%
  \textfont\bffam=\eightbf \scriptfont\bffam=\sixbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\eightbf\let\bigf@nt=\eightbf\let\smallf@nt=\sixbf}%
  \textfont\ttfam=\eighttt
  \def\tt{\fam\ttfam\eighttt}%
  \abovedisplayskip=9pt plus 3pt minus 6pt
   \belowdisplayskip=\abovedisplayskip
    \abovedisplayshortskip=4pt plus 3pt
     \belowdisplayshortskip=9pt plus 3pt minus 6pt
  \smallskipamount=2pt plus 1pt minus 1pt
  \medskipamount=4pt plus 2pt minus 1pt
  \bigskipamount=9pt plus 3pt minus 3pt
  \normalbaselineskip=10pt
  \setbox\strutbox=\hbox{\vrule height7pt depth2pt width0pt}%
  \normalbaselines\rm}

\tenpoint

\def\cal#1{{\calfont#1}}
\def\bb#1{{\bbfont#1}}
\def\goth#1{{\gothfont#1}}

\def\pc{\pcprep}
\def\pcprep{\bgroup\def\'##1{\expandafter\accent 19 ##1}\dosmallcap}
\def\dosmallcap #1#2|%
    {\edef\firstletter{#1}% 
      \edef\otherletters{#2}%         
       \bigf@nt\expandafter\uppercase\expandafter{\firstletter}%
        \smallf@nt\expandafter\uppercase\expandafter{\otherletters}\egroup}


\def\pd#1 {\pc#1| }

{\catcode`\;=\active
  \catcode`\:=\active
   \catcode`\!=\active
    \catcode`\?=\active
\gdef\frenchdactylography{\frenchspacing
      \catcode`\;=\active
       \catcode`\:=\active
        \catcode`\!=\active
         \catcode`\?=\active
\def;{\relax\ifhmode\ifdim\lastskip>\z@
       \unskip\fi\kern\fontdimen2 \font\kern -1.2 \fontdimen3 \font\fi\string;}%
\def:{\relax\ifhmode\ifdim\lastskip>\z@\unskip\fi\penalty\@M\ \fi\string:}%
\def!{\relax\ifhmode\ifdim\lastskip>\z@
       \unskip\fi\kern\fontdimen2 \font \kern -1.1 \fontdimen3 \font\fi\string!}%
\def?{\relax\ifhmode\ifdim\lastskip>\z@
       \unskip\fi\kern\fontdimen2 \font \kern -1.1 \fontdimen3 \font\fi\string?}%
}}

\frenchdactylography

\def\^#1{\if#1i{\accent"5E\i}\else{\accent"5E #1}\fi}
\def\"#1{\if#1i{\accent"7F\i}\else{\accent"7F #1}\fi}

\newtoks\auteurcourant      \auteurcourant={\hfil}
\newtoks\titrecourant       \titrecourant={\hfil}

\newtoks\hautpagetitre      \hautpagetitre={\hfil}
\newtoks\baspagetitre       \baspagetitre={\hfil}

\newtoks\hautpagegauche   \newtoks\hautpagedroite 
  
\hautpagegauche={\tenrm\rlap{\folio}\tenit\hfil\the\auteurcourant\hfil}
\hautpagedroite={\tenit\hfil\the\titrecourant\hfil\tenrm\llap{\folio}}

\newtoks\baspagegauche      \baspagegauche={\hfil} 
\newtoks\baspagedroite      \baspagedroite={\hfil}

\newif\ifpagetitre          \pagetitretrue  


\def\nopagenumbers{\def\folio{\hfil}}  

\headline={\ifpagetitre\the\hautpagetitre
            \else\ifodd\pageno\the\hautpagedroite
             \else\the\hautpagegauche
              \fi\fi}

\footline={\ifpagetitre\the\baspagetitre\else
            \ifodd\pageno\the\baspagedroite
             \else\the\baspagegauche
              \fi\fi
               \global\pagetitrefalse}

\def\raggedbottom{\topskip 10pt plus 36pt\r@ggedbottomtrue}

\def\pointir{\unskip . --- \ignorespaces}

\def\centermode 
    {\parindent=0pt
      \leftskip=0pt plus 1fill
       \rightskip=\leftskip
        \parfillskip=0pt
         }

\def\ctitre 
    {\vglue 24 pt plus 3pt minus 3pt
      \begingroup
       \centermode
        \baselineskip=17pt
         \parskip=0pt
          \obeylines\bf
           }

\def\endctitre 
    {\par\endgroup
      \nobreak\bigskip
       }

\def\bigbreak{\par
               \ifdim\lastskip<\bigskipamount
                \removelastskip\penalty-100\bigskip
                 \fi
                  }

\def\medbreak{\par
               \ifdim\lastskip<\medskipamount
                \removelastskip\penalty-50\medskip
                 \fi
                  }

\def\smallbreak{\par
                 \ifdim\lastskip<\smallskipamount
                  \removelastskip\penalty-25\smallskip
                   \fi
                    }

\long\def\section#1\endsection 
      {\global\subsectiontitlefalse
        \bigbreak{\bf#1\unskip}\pointir}

\long\def\sectiona#1\endsection 
     {\global\subsectiontitlefalse
       \bigbreak\vbox{\bf#1\unskip}\par\nobreak}

\long\def\subsection#1\endsubsection 
     {\global\subsectiontitletrue
       \medbreak{\it#1\unskip}\pointir}

\long\def\subsectiona#1\endsubsection 
     {\global\subsectiontitletrue
       \medbreak\vbox{\it#1\unskip}\par\nobreak}

\def\newparwithcolon#1\endnewparwithcolon 
    {\global\subsectiontitletrue\medbreak
      {#1\unskip:}  
       }

\def\newparwithpointir#1\endnewparwithpointir 
    {\global\subsectiontitletrue\medbreak
      {#1\unskip}\pointir
       }

\def\newpara#1\endnewpar 
    {\global\subsectiontitletrue\medbreak
      {#1\unskip}\par\nobreak\smallskip
       }

\def\resume{\bgroup\eightpoint\noindent R\'esum\'e\pointir} 
 \def\endresume{\par\egroup}     

\def\ddeux@points{\relax
     \ifhmode
      \ifdim\lastskip>\z@\unskip\fi
       \penalty\@M\space{\rm \string:}%
        \else\ifmmode
         \mathrel{\string:}%
          \fi\fi}

\def\virg@le{\relax
     \ifmmode\string,
      \else{\rm\string,}
       \fi}

\def\point@virgule{\relax
     \ifhmode
      \ifdim\lastskip>\z@\unskip\fi
       \kern\fontdimen2 \font\kern -1.2 \fontdimen3 \font
        {\rm\string;}%
         \else\ifmmode
          \mathpunct{\string;}%
           \fi\fi}

{\catcode`\(=\active 
  \catcode`\)=\active 
   \catcode`\,=\active 
    \catcode`\;=\active 
     \catcode`\:=\active 
\gdef\specialit{%
      \catcode`\(=\active  \gdef({\ifmmode\string(\else{\rm\string(}\fi}%
       \catcode`\)=\active  \gdef){\ifmmode\string)\else{\rm\string)}\fi}%
        \catcode`\,=\active  \gdef,{\virg@le}%
         \catcode`\;=\active  \gdef;{\point@virgule}%
          \catcode`\:=\active  \gdef:{\ddeux@points}%
           \it}}

\def\th#1 #2\enonce{\medbreak
              \pc#1| {#2\unskip}\pointir
               \bgroup\specialit}

\def\endth{\ifdim\lastskip<4pt\vskip-\lastskip\medskip\fi\egroup
            \frenchdactylography}
%-----------------------------
\def\tha#1 #2\enonce{\medbreak
              \pc#1| {#2\unskip}\nobreak\par
               \bgroup\specialit}

\def\Th#1 #2 #3\enonce{\medbreak
       #1 \pc#2| {#3\unskip}\pointir
               \bgroup\specialit}

\long\def\Tha#1 #2 #3\enonce{\medbreak
       #1 {\pd#2 } #3\nobreak\par
               \bgroup\specialit}

\def\decale#1{\smallbreak
               \noindent\hskip 28pt\llap{\rm #1}\
                \ignorespaces}

\def\decaledecale#1{\smallbreak
                     \noindent\hskip 34pt\llap{\rm #1}\ 
                            \ignorespaces}

\def\puce{\par
           \noindent\hskip 6pt$\scriptstyle\bullet$\enspace\ignorespaces}

\def\cutdisplay{\hfill\cr\hfill{}}

\def\up#1{\raise 0.85ex\hbox{\smallf@nt#1}}

\def\cf{{\it cf}} \def\etc{{\it etc}} \def\ie{{\it i.e}}
\def\qed{\lower 2pt\hbox{\vrule\vbox to 10pt{\hrule width 4pt
                                             \vfill
                                             \hrule}\vrule}}

\def\cqfd{\unskip\penalty 500\kern 10pt\qed}


\def\smashtop#1{\setbox0=\hbox{#1}\ht0=0pt\box0}
\def\smashbot#1{\setbox0=\hbox{#1}\dp0=0pt\box0}

\def\tvi{\vrule height 12pt depth 5pt width 0pt}
\def\tv{\tvi\vrule}

\catcode`\@=12


\newbox\auteurbox
\newbox\titrebox    
\newbox\editeurbox
\newbox\datebox
\newbox\nomrevuebox
\newbox\tomebox
\newbox\pagesbox
\newbox\textebox
\newbox\diversbox
\newbox\refbox

%--------------------------------------------
\def\makebox#1#2{\par\egroup
                     \setbox#1=\vbox\bgroup
                      \leftskip=0pt   
                       \hsize=\maxdimen \noindent#2}
%--------------------------------------------
\def\ref{\par\vskip 3pt plus 30pt
           \setbox0=\vbox\bgroup\makebox\refbox\bf}
%--------------------------------------------
\def\auteur{\makebox\auteurbox\pd}
 \def\titre{\makebox\titrebox\sl}
  \def\editeur{\makebox\editeurbox\rm}
   \def\nomrevue{\makebox\nomrevuebox\rm}
    \def\tome{\makebox\tomebox\bf}
%--------------------------------------------
{\catcode`\-=\active
           \gdef\date{\makebox\datebox
            \catcode`\-=\active
             \def-{\hbox{\rm \string-\string-}}%
              \oldstyle}}
%--------------------------------------------
{\catcode`\-=\active
           \gdef\pages{\makebox\pagesbox
            \catcode`\-=\active
             \def-{\hbox{\rm\string-\string-}}%
              \rm}}
%--------------------------------------------
{\catcode`\-=\active
           \gdef\divers{\makebox\diversbox
            \catcode`\-=\active
             \def-{\hbox{\rm\string-\string-}}%
              \rm}}
%--------------------------------------------
\def\addref#1{\setbox0=\vbox{\unvbox#1%
                \global\setbox1=\lastbox}%
                 \unhbox1 \unskip\unskip\unpenalty}
%--------------------------------------------
\newif\iffirstitem        
\def\separateur{\iffirstitem\pointir\global\firstitemfalse
                   \else, \ignorespaces\fi}
%--------------------------------------------
\def\voidallboxes
{\setbox0=\box\auteurbox
  \setbox0=\box\titrebox 
   \setbox0=\box\editeurbox
    \setbox0=\box\datebox
     \setbox0=\box\nomrevuebox
      \setbox0=\box\tomebox
       \setbox0=\box\pagesbox
        \setbox0=\box\textebox
         \setbox0=\box\diversbox
          \setbox0=\box\refbox
           \setbox0=\null}
%--------------------------------------------
\def\makelivre 
    {\ifdim\ht\auteurbox>0pt   \addref\auteurbox\fi 
      \ifdim\ht\titrebox>0pt     \separateur\addref\titrebox\fi
       \ifdim\ht\editeurbox>0pt   \pointir\global\firstitemfalse
                                      \addref\editeurbox\fi
         \ifdim\ht\datebox>0pt      \separateur\addref\datebox\fi}
%--------------------------------------------
\def\makearticle 
   {\ifdim\ht\auteurbox>0pt     \addref\auteurbox\fi 
     \ifdim\ht\titrebox>0pt      \separateur\addref\titrebox\fi
      \ifdim\ht\nomrevuebox>0pt  \separateur\addref\nomrevuebox\fi
       \ifdim\ht\tomebox>0pt      \separateur t.~\addref\tomebox\fi
        \ifdim\ht\datebox>0pt      \separateur\addref\datebox\fi
         \ifdim\ht\pagesbox>0pt     \separateur p.~\addref\pagesbox\fi}
%--------------------------------------------
\def\makedivers
   {\ifdim\ht\auteurbox>0pt     \addref\auteurbox\fi 
     \ifdim\ht\diversbox>0pt      \separateur\addref\diversbox\fi}
%--------------------------------------------
\def\endref
{\egroup\global\firstitemtrue
  \vskip 3pt plus 2pt minus 1pt
   \putref
    \ifdim\ht\nomrevuebox>0pt \makearticle
     \else\ifdim\ht\editeurbox>0pt \makelivre
      \else\ifdim\ht\diversbox>0pt \makedivers
       \fi\fi\fi
       .\voidallboxes}
%--------------------------------------------
\spaceskip=3pt plus 3pt minus 1pt 
\xspaceskip=3pt plus 3pt minus 1pt
\frenchspacing

%--------------------------------------------
\def\putrefI{\noindent[\addref\refbox]\quad}
\def\putrefII{\noindent\llap{[\addref\refbox]\enspace}}
\def\putrefIII{\noindent}
\def\putrefIV{\leftskip=15pt\noindent\hskip-\leftskip}

\def\styleI{\let\putref=\putrefI}
\def\styleII{\let\putref=\putrefII}
\def\styleIII{\let\putref=\putrefIII}
\def\styleIV{\let\putref=\putrefIV}

\styleI
\def\Log{\mathop{\rm Log}\nolimits}
\def\exp{\mathop{\rm exp}\nolimits}
\def\som{\mathop{\rm som}\nolimits}
\def\arc{\mathop{\rm arc}\nolimits}
\def\k{\kern .3em} 
\def\,{\mkern 3mu}
\def\e{\mkern 5mu}

\auteurcourant={\vtop{\hfill\eightit D. Dumont, A.
Ramamonjisoa 
    \smallskip 
    \hrule
    }} \titrecourant={\vtop{\eightit \noindent
Grammaire de Ramanujan et arbres de Cayley \hfill 
    \smallskip 
    \hrule
    }} 

\def\ej{\eject\vskip 1cm} 

\vsize=190mm \hsize=135mm \hoffset=-2mm
\overfullrule=0mm \font\bb=msbm10

%%% End of format %%%%




\ctitre Grammaire de Ramanujan et Arbres de Cayley
\endctitre
\centerline{Dominique DUMONT et Armand
RAMAMONJISOA} 
\centerline{E.E.S. Sciences, B.P.
$906$,} 
\centerline{Antananarivo-$101$, Madagascar}

\vskip 15mm
{\eightpoint\eightit Dedicace d'un Dominique a l'autre :
"Le rapporteur a qualifi\'e le pr\'esent article de "foatesque". C'est, me semble-t-il, non seulement la reconnaissance d'une \'evidente parent\'e 
d'esprit entre les \'el\`eves de Dominique Foata, y compris chez ceux de deuxieme g\'en\'eration comme Armand Ramamonjisoa qui n'ont pas la chance 
de le conna\^{\i}tre directement, c'est cette constatation mais c'est aussi, 
et surtout, le meilleur compliment que ce rapporteur pouvait faire."

Antananarivo, le 17 Ao\^ut 1995,
Dominique DUMONT.\par}
\vskip 12pt
\centerline{\eightrm Submitted: February 25, 1995; Accepted: July 25, 1995}

\vskip 15mm

{\eightpoint\noindent Abstract \pointir We study
three sequences of polynomials defined as successive
derivatives with respect to a differential operator
associated with a grammar (one of these sequences
was originally introduced by Ramanujan).
Combinatorial interpretations for these polynomials
are found in terms of rooted trees and graphs of
mappings from $[n]$ to $[n]$.\par}    

\vskip .5cm
{\bf Introduction}
\font\smcp=cmcsc8 
\headline={\ifnum\pageno>1 {\smcp the electronic journal of combinatorics 3 (2) (1996), \#R17\hfill\folio} \fi} 

\medskip
Dans [Ra], [B], Ramanujan (et B. Berndt \`a sa suite) a introduit
une suite-double d'entiers $a(n,k)$ donn\'es par une
r\'ecurrence simple, qui raffinent la suite $(n^n).$  Dans cet
article nous donnons d'abord de nouvelles d\'efinitions
calculatoires pour ces entiers et pour des raffinements
analogues des suites $(n^{n-1})$ et $(n^{n-2})$ (\S\kern 2pt 1,
\S\kern 2pt 2).  Puis dans une deuxi\`eme partie nous en
proposons des interpr\'etations combinatoires, en introduisant
sur les arbres les notions de {\it cadet, ar\^ete simple, ar\^ete
double} et le param\`etre statistique ``arc" (\S\kern 2pt 3).
L'\'enonc\'e fondamental (dont les autres se d\'eduisent
ais\'ement) est constitu\'e par la proposition $5$ (\S\kern 2pt
4), dont nous donnons deux d\'emonstrations : une
d\'emonstration d\'etaill\'ee et \'el\'ementaire (\S\kern 2pt 5),
qui pr\'esente l'avantage d'interpr\'eter du m\^eme coup la {\it
grammaire de Ramanujan} introduite au \S\kern 2pt 2 et les
r\'ecurrences de type triangle de Pascal sur les coefficients ;
puis une d\'emonstration plus exp\'editive et plus savante
(\S\kern 2pt 7), qui nous a \'et\'e sugg\'er\'ee par J. Zeng, 
combinant des compos\'es partitionnels ab\'elien et non
ab\'elien.


\vskip .5cm 
{\bf 1. Inversions de s\'eries}

\medskip
 Rappelons
la proposition suivante, qu'on d\'emontre classiquement
\`a l'aide de la formule d'inversion de Lagrange, ou par
des m\'ethodes combinatoires ([BLL], [B], [F], [Ri], [W]) :

\th Proposition 1 
\enonce Soit $y$ une s\'erie formelle
en $x$ sans terme constant. Alors on a l'\'equivalence 
$$
x=y\,e^{-y} \enspace\Longleftrightarrow\enspace
y=x+2^1{x^2\over 2!}+3^2{x^3\over 3!}+\cdots
+n^{n-1}{x^n\over n!} +\cdots \leqno (1)
$$
\endth

On en d\'eduit une autre inversion de s\'erie, sous la
forme de la proposition $2$ suivante.

\th Proposition 2 
\enonce 
Soit $z$ une s\'erie formelle
en $x$ sans terme constant. Alors on a \'equivalence 
entre les deux relations suivantes : 
$$\leqalignno{
x&=-(1-z)\,\Log(1-z)=z-{z^2\over 2}-{z^3\over 6}
-{z^4\over 12}-\cdots
-{z^n\over n\,(n-1)}-\cdots &(2)\cr
 z&=x+{x^2\over 2!}+2^2{x^3\over 3!}+3^3{x^4\over 4!}
+\cdots +n^n{x^{n+1}\over (n+1)!}+\cdots &(2')\cr }
$$ 
\endth

En effet, posons $z=1-e^{-y}$, $y$ \'etant la solution
de $x=y\,e^{-y}$. On a donc $x=-(1-z)\,\Log(1-z).$
D'autre part, en diff\'erentiant la relation
$y=x\,e^y,$ on obtient $y'=e^y+x\,e^yy'$. Par
suite, $$z'=(1-e^{-y})'=e^{-y}y'=1+xy'=\sum_{n\geq
0}n^n{x^n\over n!},$$ d'o\`u le r\'esultat apr\`es int\'egration.

\smallskip 
Cette proposition $2$ est li\'ee \`a un
probl\`eme de d\'eveloppement asymptotique pour une
fonction implicite, \'etudi\'e par Ramanujan [Ra] [B] [H],
que nous \'enon\c cons ainsi :

\smallskip\noindent  
{\sl Si\quad $x\,\Log x=x_0\Log x_0+h$\quad\quad ($h$\enspace
 petit), \enspace d\'evelopper $x$ au voisinage de
$x_0$.}

\smallskip 
Ramanujan trouve le d\'eveloppement suivant, avec
$y_0=1/(1+\Log x_0)$ :
$$
x=x_0+y_0h-(y_0^3){1\over x_0}{h^2\over
2!}+(y_0^4+3y_0^5){1\over x_0^2}{h^3\over 3!}
-(2y_0^5+10y_0^6+15y_0^7){1\over x_0^3}{h^4\over
4!}+\cdots ,
$$  
o\`u la suite de polyn\^omes en $y_0$ est
donn\'ee par une r\'ecurrence simple (cf $(4)$ ci-dessous).
Apr\`es une l\'eg\`ere transformation, on peut reformuler le
r\'esultat de Ramanujan de la mani\`ere suivante, o\`u il
appara\^\i t comme une extension de la proposition $2$ :  
 
\th Proposition 3 \enonce On a \'equivalence 
entre les deux relations suivantes : 
$$\leqalignno{
x&={z\over a}-z-(1-z)\,\Log(1-z)
={z\over a}-{z^2\over 2}-{z^3\over 6}-{z^4\over 12}
-\cdots-{z^n\over n(n-1)}-\cdots &(3)\cr
z&=ax+a^3{x^2\over 2!}+(a^4+3a^5){x^3\over 3!}
+(2a^5+10a^6+15a^7){x^4\over 4!}+\cdots\hfill &(3')\cr 
&\quad\quad+\big(a(n,1)a^{n+2}+a(n,2)a^{n+3}+\ldots
+a(n,n)a^{2n+1}\big){x^{n+1}\over (n+1)!}+\cdots \cr
}
$$ 
o\`u les nombres de Ramanujan $a(n,k)$ sont
d\'efinis par la r\'ecurrence 
$$
a(n,k)=(n-1)\,a(n-1,k)+(n+k-1)\,a(n-1,k-1),\quad\quad
a(1,1)=1,\leqno (4)
$$ 
et sont tels que :
$$
\sum_{1\leq k\leq n}a(n,k)=n^n. \leqno (5)
$$
\endth

Nous donnerons au \S\kern 2pt 2 une d\'emonstration de la
proposition $3$ (dans [B], le lecteur trouvera une
autre preuve d'un \'enonc\'e \'equivalent). 

Toujours \`a l'aide du changement de fonction
$y=-\Log(1-z)$, nous serons conduits \`a d\'emontrer
l'extension suivante de l'\'equivalence $(1)$.

\th Proposition 4 
\enonce 
Soit $y$ une s\'erie
formelle en $x$ sans terme constant. Alors on a
\'equivalence  entre les deux relations suivantes :
$$
\leqalignno{ \quad
x&=y\,e^{-y}+{a-1\over a}(e^{-y}-1)
={1\over a}\big[y-(a+1){y^2\over 2!}+(2a+1){y^3\over 3!}-
(3a+1){y^4\over 4!}+\cdots \big] &(6) \cr
y&=ax+(a^2+a^3){x^2\over 2!}+(2a^3
+4a^4+3a^5){x^3\over 3!}+\cdots &(6')\cr  
&\quad\quad+\big(b(n,0)a^{n}+b(n,1)a^{n+1}+\ldots
+b(n,n-1)a^{2n-1}\big){x^n\over n!}+\cdots \cr }
$$
o\`u les nombres  $b(n,k)$ sont donn\'es par la r\'ecurrence 
$$
b(n,k)=(n-1)\,b(n-1,k)+(n+k-2)\,b(n-1,k-1),\quad\quad
b(1,0)=1,\leqno (7)
$$
et sont tels que la somme de leur $n-$i\`eme ligne vaut
$n^{n-1}$ :
 $$\sum_{0\leq k\leq n-1}b(n,k)=n^{n-1}.
\leqno (8)$$
\endth

\vskip .3cm
{\bf \S\kern 2pt 2. Grammaire de Ramanujan}

\medskip
Dans tout ce qui suit, $y$ d\'esigne donc la s\'erie
formelle solution de
$$
x=y\,e^{-y}+{a-1\over a}(e^{-y}-1), \leqno(6)
$$
et on consid\`ere aussi la fonction auxiliaire
$z=1-e^{-y}$.
En diff\'erentiant par rapport \`a $x$
l'\'equation $(6)$, on obtient :
$1=-y\,e^{-y}y'+{1\over a}e^{-y}y'$,
soit
$$
y'=\Big({a\over 1-ay}\Big)e^y,\leqno(9)
$$
\'equation diff\'erentielle qui, avec la condition
initiale $y(0)=0$, suffit \`a caract\'eriser $y$, et
surtout conduit \`a un algorithme de calcul de ses
coefficients, comme nous allons le voir.\par Notons
que $(9)$ implique que $z'=\displaystyle{a\over 1-ay}.$
Introduisons deux nouvelles fonctions auxiliaires
que, pour des raisons qui appara\^\i tront plus loin,
nous notons par les deux lettres capitales $A$ et
$S$ : 
$$
\leqalignno{ A&=z'={a\over 1-ay} &(10)\cr
S&={1\over 1-z}=e^y &(11)\cr }
$$ 
Calculons les d\'eriv\'ees de ces deux fonctions :
$$\displaylines{
A'=\Big({a\over 1-ay}\Big)'=\Big({a\over 1-ay}\Big)^2y'
=\Big({a\over 1-ay}\Big)^3e^y=A^3S,\cr
S'=(e^y)'=e^yy'=AS^2. \cr
\noalign{\hbox{En r\'esum\'e, on obtient
le syst\`eme diff\'erentiel :}}
\rlap{(12)}\hfill
\left\{\matrix{ y'&=&AS &&
&y(0)=0 \cr z'&=&A  && &z(0)=0      \cr A'&=&A^3S &&
&A(0)=a     \cr S'&=&AS^2 && &S(0)=1     \cr }\right.
\hfill\cr}
$$ 

Soit $D$ l'op\'erateur diff\'erentiel
$$D=A^3S {\partial \over  \partial A}+AS^2{\partial \over 
\partial S}\cdotp$$ 
Dans le formalisme de W. Chen
[Ch], $D$ n'est autre que l'op\'erateur diff\'erentiel
associ\'e \`a la grammaire 
$G=\{A\rightarrow
A^3S,\enspace S\rightarrow AS^2\}$,
d\'efinie sur
l'alphabet $\{A,S\}$, et ce sont ces deux r\`egles de
r\'e\'ecriture que nous appelons {\it grammaire de
Ramanujan}.\par On a, par r\'ecurrence sur $n$,
$$
\left\{\matrix{ y^{(n+1)}&=&D^n(AS) \cr
z^{(n+1)}&=&D^n(A)  \cr
 A^{(n)}&=&D^n(A)   \cr
 S^{(n)}&=&D^n(S)   \cr }\right. \leqno (13) 
$$ 
Les membres de droite sont des polyn\^omes en $A$ et $S$.
Voici d'abord les premi\`eres valeurs des polyn\^omes
d\'eriv\'es successifs de $A$ : 
$$\eqalign{ &D^0(A)=A \cr
&D^1(A)=(A^3)S \cr  &D^2(A)=(A^4+3A^5)S^2 \cr 
&D^3(A)=(2A^5+10A^6+15A^7)S^3 \cr  &\cdots \cr 
&D^n(A)=(a(n,1)A^{n+2}+\cdots +a(n,k)A^{n+k+1}
+\cdots +a(n,n)A^{2n+1})S^n \cr  }$$
 Le terme
$a(n,k)A^{n+k+1}S^n$ se d\'eduit de deux termes de la
ligne pr\'ec\'edente :
$$\displaylines{
AS^2{\partial \over  \partial
S}\Big[a(n-1,k)A^{n+k}S^{n-1}\Big]+ A^3S{\partial \over 
\partial A}\Big[a(n-1,k-1)A^{n+k-1}S^{n-1}\Big],\cr
\noalign{\hbox{ce qui donne la r\'ecurrence $(4)$ annonc\'ee
plus haut :}}
a(n,k)=(n-1)\,a(n-1,k)+(n+k-1)\,a(n-1,k-1).\cr}
$$

Voici \`a pr\'esent les premi\`eres valeurs des polyn\^omes
d\'eriv\'es successifs de $AS$ : 
$$\eqalign{ &D^0(AS)=AS
\cr &D^1(AS)=(A^2+A^3)S^2 \cr 
&D^2(AS)=(2A^3+4A^4+3A^5)S^3 \cr  &\cdots \cr 
&D^{n-1}(AS)=(b(n,0)A^n+\cdots +b(n,k)A^{n+k}
+\cdots +b(n,n-1)A^{2n-1})S^n \cr  }$$ 
Le terme
$b(n,k)A^{n+k}S^n$ se d\'eduit de deux termes de la
ligne pr\'ec\'edente : 
$$\displaylines{
AS^2{\partial \over  \partial
S}\Big[b(n-1,k)A^{n+k-1}S^{n-1}\Big]+ A^3S{\partial
\over  \partial A}\Big[b(n-1,k-1)A^{n+k-2}S^{n-1}\Big],\cr
\noalign{\hbox{ce qui donne la r\'ecurrence $(10)$ annonc\'ee
plus haut :}} 
b(n,k)=(n-1)\,b(n-1,k)+(n+k-2)\,b(n-1,k-1).\cr}$$

Voici enfin les premi\`eres valeurs des polyn\^omes
d\'eriv\'es successifs de $S$ : 
$$\eqalign{ &D^0(S)=S \cr
&D^1(S)=(A)S^2 \cr  &D^2(S)=(2A^2+A^3)S^3 \cr 
&D^3(S)=(6A^3+7A^4+3A^5)S^4 \cr  &\cdots \cr 
&D^{n-1}(S)=(c(n,0)A^{n-1}+\cdots +c(n,k)A^{n+k-1}
+\cdots +c(n,n-2)A^{2n-3})S^n \cr  }$$
 Le terme
$c(n,k)A^{n+k-1}S^n$ se d\'eduit de deux termes de la
ligne pr\'ec\'edente : 
$$
\displaylines{AS^2{\partial \over  \partial
S}\Big[c(n-1,k)A^{n+k-2}S^{n-1}\Big]+ A^3S{\partial
\over  \partial A}\Big[c(n-1,k-1)A^{n+k-3}S^{n-1}\Big],\cr
\noalign{\hbox{ce qui donne la r\'ecurrence $(14)$ suivante :}}
\rlap{(14)}\hfill
c(n,k)=(n-1)\,c(n-1,k)+(n+k-3)\,c(n-1,k-1).\hfill\cr}
$$ 
Pour obtenir les s\'eries $y$ (primitive de
$AS$), $A=z'$, et $S$, il suffit d'apr\`es la formule de
Taylor formelle, de porter $x=0$ dans les identit\'es
$(13)$, ce qui, avec les conditions initiales $(12)$,
donne les trois d\'eveloppements suivants, dont les
deux premiers \'etaient annonc\'es plus haut : 
$$\leqalignno {
y&=ax+(a^2+a^3){x^2\over 2!}+(2a^3+4a^4+3a^5)
{x^3\over 3!}+\cdots &(6) \cr 
z'={a\over 1-ay}&=a+a^3x+(a^4+3a^5){x^2\over 2!}
+(2a^5+10a^6+15a^7){x^3\over 3!}+\cdots&(3) \cr 
e^y&=1+ax+(2a^2+a^3){x^2\over 2!}+(6a^3+7a^4+3a^5)
{x^3\over 3!}+\cdots & (15) }$$ 
Les coefficients des d\'eveloppements sont respectivement les
entiers $b(n,k)$, $a(n,k)$ (ces derniers introduits par
Ramanujan, cf. [Ra] [B] [H]) et $c(n,k)$. Ainsi
s'ach\`eve la d\'emonstration des proposition $3$ et $4$
ci-dessus.

\vskip .5cm 
{\bf \S\kern 2pt 3. Descendants et cadets dans les
arbres de Cayley. Param\`etre ``arc"}

\medskip  
Soit $(A,r)$ un arbre de Cayley enracin\'e de taille
$n$, c'est-\`a-dire le couple form\'e d'un arbre de
Cayley $A$ de sommets $\{1,2,\ldots ,n\}$ et d'un
sommet distingu\'e $r$ de $A$ qu'on appelle {\it
racine} de l'arbre. On oriente les ar\^etes de l'arbre \`a
partir de la racine (on aurait pu convenir de
l'orientation contraire, l'arbre est alors le graphe
sagittal d'une {\it fonction acyclique}, au sens de
[F]). Pour distinguer la racine de
l'arbre, on convient d'ajouter  une ar\^ete 
$(\longrightarrow r)$. 

 On note $\cal A_n(\rightarrow r)$ l'ensemble des
arbres $A$ de taille $n$ enracin\'es en $r$ et  $\cal
A_n(\rightarrow .)=\bigcup_{r\in [n]}\cal
A_n(\rightarrow r)$ la r\'eunion de ces ensembles, de
cardinal $n^{n-1}$ (cf. [BLL], [F], [W]). \par
 Soit $A$ un \'el\'ement de $\cal A_n(\rightarrow
.)$, de racine $r$.  On convient que l'ar\^ete 
$(\longrightarrow r)$
fait partie des ar\^etes de l'arbre. De ce fait, l'arbre
enracin\'e poss\`ede $n$ sommets et $n$ ar\^etes.  \par  
 Soit $j$ un sommet fix\'e dans l'arbre $A$. Si un
sommet $k$ est tel que le chemin joignant $r$ \`a $k$
passe par $j$, on dit qu'il appartient \`a la  {\it
descendance} du sommet $j$. Cette descendance est un
sous-arbre enracin\'e en $j$ et on la note $A(j)$. En
particulier, si $j$ est pendant, $A(j)$ se r\'eduit \`a
$j$ lui-m\^eme. En revanche, $A(r)$ n'est autre que $A$
tout entier (``en revanche" suppose ici qu'on se
trouve dans un cas o\`u $n>1$).

Le plus petit sommet de $A(j)$, not\'e $c(j),$
s'appelle le {\it cadet} de la descendance du sommet
$j$. 

Par ailleurs le sommet $j$ poss\`ede un p\`ere
et un seul, c'est le sommet $i$ qui est l'origine de
l'unique ar\^ete  dont $j$ est une extr\'emit\'e (Si
$j=r$, on convient que ce p\`ere est $0$). On distingue deux cas :
 
\puce  Si $c(j)>i$, on dit que l'ar\^ete de $i$ \`a $j$ est
{\it simple}, on la note dor\'enavant 
$(i\longrightarrow j)$ et on dessine {\it un arc}
allant de $i$ vers $j$.
 
\puce  Si $c(j)<i$, on dit que l'ar\^ete de $i$ \`a $j$
est {\it double}, on la note dor\'enavant 
$(i\Longrightarrow j)$ et on dessine {\it deux arcs}
allant de $i$ vers $j$. 

\medskip
{\it Remarques.---} Si
une ar\^ete de $i$ \`a $j$ est d\'ecroissante (telle que
$i>j$), alors elle est double.  Si elle est croissante
et si $j$ est un sommet pendant, alors elle est
simple. Mais si $j$ n'est pas pendant, il peut se
produire qu'une ar\^ete croissante soit double, il
suffit qu'un descendant de $j$ soit $<i$. 
Notons que l'ar\^ete $(\longrightarrow r)$ est toujours simple. 

Si $A$ est un arbre enracin\'e, on note $\som(A)$ le nombre
de ses sommets. Si $A\in\cal A_n(\rightarrow .)$,
$\som(A)=n$). On note  $s(A)$ le nombre des ar\^etes
simples et $d(A)$ le nombre des ar\^etes doubles, et 
$\arc(A)$ le nombre des arcs de $A$. On a donc,
pour un arbre de Cayley enracin\'e : 
$$
\eqalign{
&s(A)+d(A)=n, \cr  &s(A)+2d(A)=\arc(A). \cr  }
$$
On consid\`ere aussi l'ensemble $\cal A_n$ des arbres
de Cayley proprement dits (non enracin\'es), de
cardinal $n^{n-2}$. Un arbre de Cayley $A$ poss\`ede
$n$ sommets et $n-1$ ar\^etes. Pour que les notions
introduites ici (descendances, cadets) gardent un
sens, nous orientons les ar\^etes de l'arbre \`a partir
de la racine $1$, mais nous supprimons l'ar\^ete
$(\longrightarrow 1),$ parce qu'elle est invariable
quand $A$ d\'ecrit $\cal A_n$,  tandis que l'ar\^ete 
$(\longrightarrow r)$ varie quand $A$ d\'ecrit $\cal
A_n(\rightarrow .)$. Les autres d\'efinitions sont
inchang\'ees. Pour un arbre de Cayley $A$, on a donc
$$\eqalign{ &s(A)+d(A)=n-1, \cr 
&s(A)+2d(A)=\arc(A). \cr  }$$  

 \vskip .3cm 
{\bf \S\kern 2pt 4. Enonc\'es combinatoires}
\medskip

Ces pr\'eliminaires \'etant pos\'es, nous pouvons
commencer par interpr\'eter les relations de r\'ecurrence
d\'efinissant deux des trois triangles de nombres
d\'efinis plus haut. 

\th Proposition $5$
\enonce 
Les s\'eries $y$ et $e^y$
\'enum\`erent les arbres de Cayley enracin\'es (resp. les
arbres de Cayley) selon le param\`etre $\arc$ (nombre
des arcs) :
$$ 
\leqalignno{ y&=ax+(a^2+a^3){x^2\over 2!}+\cdots
+\Big(\sum_{A\in\cal A_n(\rightarrow
.)}a^{\arc(A)}\Big){x^n\over n!}+\cdots &(16) \cr 
e^y&=1+ax+(2a^2+a^3){x^2\over 2!}+\cdots
+\Big(\sum_{A\in\cal A_{n+1}
}a^{\arc(A)}\Big){x^n\over n!}+\cdots
&(17) \cr }
$$
 \endth 

\th Corollaire  
\enonce
Le coefficient
$c(n,k)$ est le nombre d'arbres de Cayley de taille
$n+1$ poss\'edant $k$ ar\^etes doubles et $b(n,k)$ est le
nombre d'arbres de Cayley enracin\'es de taille $n$
poss\'edant $k$ ar\^etes doubles. 
\endth

\vskip .3cm 
{\bf \S\kern 2pt 5. Interpr\'etation combinatoire de la
grammaire de Ramanujan et des r\'ecurrences $(7)$ et
$(14)$.} 
\medskip

 {\it Convention.---} Soit $A$ un arbre enracin\'e de
taille $n$, et soit un sommet fix\'e $i$. Soit $k=p+q$
son degr\'e, c'est-\`a-dire le nombre des ar\^etes issues
de $i$, comprenant $p$ ar\^etes doubles et $q$ ar\^etes
simples. On d\'efinit un ordre sur ces $k$ ar\^etes qui
est l'ordre croissant des cadets des fils de $i$ (non
l'ordre croissant des fils eux-m\^emes). On dessine
donc en tournant dans le sens trigonom\'etrique,
d'abord les $p$ ar\^etes doubles $(i\Longrightarrow
j_1)$, $(i\Longrightarrow j_2)$,  $\ldots$,
 $(i\Longrightarrow j_p)$, puis les $q$ ar\^etes
simples $(i\longrightarrow j_{p+1})$,  $\ldots$,
$(i\longrightarrow j_k)$, de telle sorte que   
$$c(j_1)<c(j_2)<\ldots <c(j_p)<i<c(j_{p+1})<\ldots
<c(j_k).$$ 

 Notons que si toutes les ar\^etes sont
simples ($p=0$), alors $c(i)=i.$ Si au contraire 
$p>1$, alors $c(i)=c(j_1)$.
 A pr\'esent, nous allons d\'efinir la {\it restriction}
$\bar A$ d'un arbre enracin\'e $A$ de taille $n$ comme
un arbre enracin\'e $\bar A$ de taille $n-1$, et
inversement les  divers {\it prolongements} d'un
arbre enracin\'e $B$ de taille $n-1$, c'est-\`a-dire la
construction de ses ant\'ec\'edents par l'application
{\it restriction}. 

 \smallskip {\it Restrictions.}
On distingue trois cas, selon le degr\'e $k$ du sommet
$n$ (notons qu'avec les conventions ci-dessus, on a
toujours $p=k$ et $q=0$, car $n$ est le sommet
maximum). On d\'esigne par $i$ le p\`ere de $n$ : 
  
a) On suppose que le sommet $n$ est pendant ($k=0$).
Alors $\bar A$ s'obtient \`a partir de $A$ en
supprimant simplement le sommet $n$ et l'ar\^ete
$(i\longrightarrow n)$ qui conduit \`a $n$. Le reste
est inchang\'e.

   b) On suppose que $k=1$, le
sommet $n$ a un fils unique $j$. Alors pour obtenir
$\bar A$ 
 \`a partir de $A$, on supprime $n$ et
$(n\Longrightarrow j)$.  Il est clair que
$c(n)=c(j)$. Si $c(n)>i,$ on remplace
$(i\longrightarrow n)$ par $(i\longrightarrow j)$ 
(si $n$ est racine, on remplace 
$(\longrightarrow n)$ par $(\longrightarrow j)$, et
$j$ devient racine). Si $c(n)<i,$  on remplace 
$(i\Longrightarrow n)$ par $(i\Longrightarrow j)$. Le
reste est inchang\'e. 

     c) On suppose que $k\geq 2$,
 et on pose $d=k-1$. Soient $j_1, j_2, \ldots
, j_d, j_k$ les fils de $n$, rang\'es de telle sorte que
les cadets respectifs aillent en croissant : 
$$c(j_1)<c(j_2)<\ldots <c(j_d)<c(j_k)<n.$$
Sommairement, la r\`egle de construction de $\bar A$
est la suivante : on remplace $n$ par son fils $j_k$
(celui dans la descendance duquel se trouve le plus
grand cadet). Plus pr\'ecis\'ement : 

\noindent  \puce  on
supprime le sommet $n$ ; 

\noindent  \puce  Si
$c(n)>i$,  on remplace $(i\longrightarrow n)$ par
$(i\longrightarrow j_k)$  (si $n$ est racine,
on remplace  $(\longrightarrow n)$ par
$(\longrightarrow j_k)$, et $j_k$ devient racine).
Si $c(n)<i$, on remplace  $(i\Longrightarrow n)$ par
$(i\Longrightarrow j_k)$ ; 

\noindent  \puce  On
supprime la derni\`ere ar\^ete issue de $n$, \`a savoir
$(n\Longrightarrow j_k)$, et on remplace $n$ par son
fils $j_k$ dans les autres ar\^etes issues de $n$, qui
deviennent donc $(j_k\Longrightarrow j_1)$,
$(j_k\Longrightarrow j_2)$, $\ldots$,
$(j_k\Longrightarrow j_d)$. Ces ar\^etes sont doubles
car les $d$ premiers cadets sont inf\'erieurs \`a
$c(j_k)$, lequel est $\leq j_k$. Le reste est
inchang\'e.

   Rappelons que  $c(j_k)=j_k$
 dans le cas o\`u toutes les ar\^etes issues de $j_k$
sont simples (en particulier dans le cas o\`u $j_k$ est
pendant).  Dans le cas contraire, il existe $m$
ar\^etes doubles issues de $j_k$, avec $m\geq 1$, que
nous notons $(j_k\Longrightarrow k_1)$, $\ldots$,
$(j_k\Longrightarrow k_m)$, et on a
$c(j_k)=c(k_1)<j_k$. Ces ar\^etes doubles se rangent,
dans l'arbre $\bar A$, {\it apr\`es} les $d$ premi\`eres
ar\^etes r\'ecup\'er\'ees du sommet $n$, car on a :
 $$c( j_1)<c(j_2)<\cdots
<c(j_{d})<c(j_k)=c(k_1)<c(k_2)<\cdots $$ 
 
\smallskip 
{\it Exemple.---} Dans la figure
ci-dessous, l'arbre de gauche est obtenu par
restriction de type (c) \`a partir de l'arbre de droite : 
$$\vbox{\halign{#&#&#&#&#&#&#&#&#&#&#&#&#\cr &&5
&&& &&& &&6 &$\Longrightarrow$ 5 &   \cr  &&
$\Uparrow$ &&& &&& && $\Uparrow$ && \cr 
$\longrightarrow$ &3 $\Longrightarrow$ & 6
&$\Longrightarrow$ 4 & $\Longrightarrow$ 2 
&\quad&\quad&\quad& $\longrightarrow$ &3
$\Longrightarrow$ &8 &$\Longrightarrow$ 4 &
$\Longrightarrow$ 2   \cr  && $\Downarrow$ &&& &&& &&
$\Downarrow$ && \cr  && 7 &&& &&& && 7 && \cr  &&
$\Downarrow$ &&& &&& && $\Downarrow$ && \cr  && 1 &&&
&&& && 1 && \cr  }} $$ 

\smallskip {\it Prolongements.} On
distingue de m\^eme trois types de prolongements d'un
arbre enracin\'e $B$ de taille $n-1$ vers un arbre
enracin\'e de taille $n$ :

 a) Prolongement par
{\it d\'erivation d'un sommet} de $B$. On choisit un
sommet quelconque $i$ de $B$, on ajoute le sommet
$n$ et l'ar\^ete $(i\longrightarrow n)$. Il est clair
que sur l'arbre $A$ ainsi obtenu le sommet $n$ est
pendant, et que $A$ redonne $B$ par restriction de
type a). Notons que dans le d\'ecompte des sommets et
ar\^etes, l'arbre $A$ poss\`ede un sommet de plus et une
ar\^ete simple de plus que l'arbre $B$.

  b)
Prolongement par {\it d\'erivation simple d'une ar\^ete}
de $B$. On choisit une ar\^ete quelconque de $B$,
simple ou double, \`a savoir $(i\longrightarrow j)$, ou
$(\longrightarrow r)$, ou $(i\Longrightarrow j).$ On
la remplace par $(i\longrightarrow n)$
 dans le premier cas, par $(\longrightarrow n)$ 
dans le deuxi\`eme cas, par $(i\Longrightarrow n)$
dans le troisi\`eme cas. On ajoute $(n\Longrightarrow
j)$. Il est clair que sur l'arbre $A$ ainsi obtenu, le
sommet $n$ est de degr\'e $1$, et que $A$ redonne $B$
par restriction de type b). Notons que dans le
d\'ecompte des sommets et ar\^etes, l'arbre $A$ poss\`ede
un sommet de plus et une ar\^ete double de plus que
l'arbre $B$.
 
c) Prolongement par {\it d\'erivation compos\'ee d'une
ar\^ete double} de $B$. On choisit une ar\^ete double
quelconque de $B$, \`a savoir $(i\Longrightarrow
j_d).$  L'indice $d$ signifie qu'elle est la $d-$i\`eme
ar\^ete issue de $i$, avec $d\geq 1$. On
 remplace ces $d$ premi\`eres ar\^etes $(i\Longrightarrow
j_1)$, $(i\Longrightarrow j_2)$, $\ldots$,
$(i\Longrightarrow j_d)$
 par $(n\Longrightarrow j_1)$, $(n\Longrightarrow
j_2)$, $\ldots$, $(n\Longrightarrow j_d)$, puis on
ajoute une ar\^ete  $(n\Longrightarrow i)$. Le reste
est inchang\'e, en particulier les ar\^etes suivantes
issues de $i$ sont inchang\'ees. On obtient ainsi un
arbre $A$ dont le degr\'e du sommet $n$ est $d+1$,
donc est $\geq 2.$ En outre, le cadet $c(i)$ de $i$
dans $A$ est sup\'erieur \`a $c(j_d)$, donc parmi les
fils de $n$, $i$ est celui qui a le plus grand cadet.
Donc  $A$ redonne $B$ par restriction de type c).
Notons que dans le d\'ecompte des sommets et ar\^etes,
l'arbre $A$ poss\`ede un sommet de plus et une ar\^ete
double de plus que l'arbre $B$.

\medskip
{\it Exemple.---} 
Dans la figure ci-dessus, l'arbre de
droite est obtenu \`a partir de l'arbre de droite en
proc\'edant \`a une d\'erivation compos\'ee de l'ar\^ete 
$(6\Longrightarrow 4)$. 

\medskip  
{\it D\'emonstration de la proposition $5$.---} 
Elle est vraie pour $n=1$, car
l'unique arbre enracin\'e de taille $1$ est $A=(\longrightarrow
1)$, pour lequel $\som(A)=1$ et $\arc(A)=1$ (on compte l'ar\^ete simple
$(\longrightarrow 1$)), et qui correspond donc au
mon\^ome $as.$ 

  A pr\'esent, supposons la
proposition vraie pour $n-1$. Le prolongement d'un
arbre $B$ consiste :

\noindent \puce  soit \`a choisir un
sommet et \`a le d\'eriver, ce qui revient \`a remplacer ce
sommet $i$ par un ensemble comportant le sommet $i$
lui-m\^eme, un nouveau sommet $n$, et une nouvelle
ar\^ete $(i\longrightarrow n)$, donc pour le mon\^ome \`a
remplacer une occurrence de la lettre $s$ par
$as^2.$

  \puce  soit \`a choisir un arc et \`a d\'eriver
l'ar\^ete qui lui correspond. Ainsi chaque ar\^ete simple
est choisie une fois, pour un prolongement de type
$b)$, et chaque ar\^ete double deux fois, pour un
prolongement de type $b)$ et un de type $c)$. Or dans
les  prolongements de type b) et c),  la d\'erivation
d'une ar\^ete revient dans le d\'ecompte \`a cr\'eer un
nouveau sommet $n$ et une nouvelle ar\^ete double,
donc deux nouveaux arcs. L'ar\^ete d\'eriv\'ee, simple ou
double, est remplac\'ee.  Pour le mon\^ome, cela
correspond au remplacement d'un arc par un ensemble
comprenant cet arc m\^eme, un nouveau sommet et deux
nouveaux arcs, donc par le remplacement d'une
occurrence de la lettre $a$ par $a^3s.$ 

En r\'esum\'e, la d\'erivation d'un arc se traduit par
$D(a)=a^3s$ et la d\'erivation d'un sommet par $D(s)=as^2$,
ce qui explique le choix des lettres $A$ et $S$ dans les
d\'efinitions $(10)$ et $(11)$. En outre, on a,
par r\'ecurrence sur $n$ :

$$D^{n-1} (as) = \sum_{A\in\cal A_n(\rightarrow.)}
a^{\arc(A)}s^{\som(A)}.$$
Les coefficients du polyn\^ome \'enum\'erateur membre de droite
siont donc les entiers $b(n,k)$, ce qui d\'emontre la premi\`ere
identit\'e de la proposition 5.

 La d\'emonstration de la deuxi\`eme identit\'e est identique,
\`a la diff\'erence pr\`es qu'il faut supprimer l'ar\^ete
$(\longrightarrow 1)$. Le mon\^ome associ\'e \`a l'arbre
$(1)$ est donc $s$, le mon\^ome associ\'e \`a l'arbre de
taille $2$, \`a savoir $(1\longrightarrow 2),$ est donc
$D(s)=as^2$, et ainsi de suite.

On peut donner du corollaire une d\'emonstration
directe consistant \`a interpr\'eter la r\'ecurrence $(7)$.
Pour construire les arbres de Cayley $A$ enracin\'es de
taille $n$ poss\'edant $k$ ar\^etes doubles on doit :

\puce  soit partir d'un arbre $B$ de taille $n-1$ poss\'edant
$k$ ar\^etes doubles et d\'eriver l'un de ses $n-1$
sommets. On obtient ainsi les $(n-1)\,b(n-1,k)$
arbres de Cayley $A$ enracin\'es de taille $n$
poss\'edant $k$ ar\^etes doubles dans lesquels le sommet
$n$ est pendant.

 \puce  soit partir d'un arbre $B$ de
taille $n-1$ poss\'edant $k-1$ ar\^etes doubles et faire
la d\'erivation simple de l'une de ses $n-1$ ar\^etes. On
obtient ainsi les $(n-1)\,b(n-1,k-1)$ arbres de
Cayley $A$ enracin\'es de taille $n$ poss\'edant $k$
ar\^etes doubles dans lesquels le sommet $n$ est  de
degr\'e $1$.

 \puce  soit partir d'un arbre $B$ de taille
$n-1$ poss\'edant $k-1$ ar\^etes doubles et faire la
d\'erivation compos\'ee de l'une de ses $k-1$ ar\^etes
doubles. On obtient ainsi les $(k-1)\,b(n-1,k-1)$
arbres de Cayley $A$ enracin\'es de taille $n$
poss\'edant $k$ ar\^etes doubles dans lesquels le sommet
$n$ est  de degr\'e $>1$.

 En rassemblant les trois
cas, on aboutit \`a la r\'ecurrence. La preuve est
analogue pour les arbres non enracin\'es. 

\vskip .5cm 
{\bf \S\kern 2pt 6. Applications de $[n]$ dans $[n]$ et
interpr\'etation des entiers $a(n,k)$} 
\medskip

{\it Rappels} (sur lesquels le
lecteur peut se r\'ef\'erer \`a [F]).---
Soit $\cal F_n$ l'ensemble des applications $f$ de
l'ensemble $[n]=\{1,2,\ldots, n\}$ dans lui-m\^eme, qui
est de cardinal $n^n.$  On repr\'esente $f$ par  (et on l'identifie \`a)
son graphe sagittal $G_f$, o\`u une ar\^ete orient\'ee
joint $i$ \`a $j$ si et seulement si $j=f(i)$. A chaque
sommet $i$ on associe la {\it trajectoire} $T(i)$ des
it\'er\'es  de $i$ par $f$, ou {\it descendants,} soit 
$$T(i)=\{i, f(i), f^2(i)=f(f(i)),
f^3(i)=f(f(f(i))),\ldots \}.$$ 
 
 S'il existe $k\geq 1$ tel que $f^k(i)=i$, alors le
sommet $i$ est dit {\it r\'ecurrent}. On note $ R_f$
l'ensemble des sommets r\'ecurrents de $f$ et  
$T_f=[n]\setminus R_f$ l'ensemble des sommets {\it
transitoires} pour $f$. On montre que $f$, restreinte
\`a $R_f$, est une permutation $\sigma _f$ de $R_f$ sur
lui-m\^eme, les trajectoires des sommets r\'ecurrents
\'etant les cycles de cette permutation. 

   Si $i$ est transitoire, on montre  qu'en d\'ecrivant $T(i)$ on
trouve n\'ecessairement des sommets r\'ecurrents (car la
trajectoire ne peut \^etre infinie, l'ensemble $[n]$
\'etant fini). Soit $r=f^k(i)$ le {\it premier sommet
r\'ecurrent} dans $T(i)$, en ce sens que l'entier
$k\geq 1$ est le plus petit entier tel que $f^k(i)$
soit r\'ecurrent. Notons que les sommets suivants de
$T(i)$ ($f(r)$, etc.) sont alors tous r\'ecurrents et
forment le cycle $T(r)$ auquel appartient $r$. 

Soit $\varphi $ l'application $i\mapsto \varphi (i)=r,$ o\`u $r$ est
le premier sommet r\'ecurrent de $T(i)$. Cette
application $\varphi $ est d\'efinie sur $[n]$ tout entier et
\`a valeurs dans $R_f$. En particulier si $r$ est
r\'ecurrent, il est clair que $\varphi (r)=r.$ Etant donn\'e un
sommet r\'ecurrent $r$, on note $A(\rightarrow r)$ le
sous-graphe de $G_f$ dont l'ensemble des sommets
est  $\varphi ^{-1}(r)$. On montre que $A(\rightarrow r)$
est un arbre de Cayley enracin\'e en $r$, avec la
convention qu'on oriente les ar\^etes {\it vers la
racine} (et non plus \`a partir de la racine comme dans notre \S\kern 2pt 3). 

On note $\pi _f$ l'ensemble des arbres $A(\rightarrow
r)$, $r$ d\'ecrivant $R_f$, autrement dit $\pi _f$
correspond \`a la donn\'ee de la partition de $[n]$
associ\'ee \`a l'application $\varphi $ et d'un arbre enracin\'e
sur chaque bloc de cette partition. On montre que le
triplet $(R_f, \sigma _f, \pi _f)$ caract\'erise l'application
$f$ (le triplet permet de construire toutes les ar\^etes
du graphe $G_f$). 

\medskip
{\it D\'efinitions.---} Soit $f$ une application de
$[n]$ dans $[n]$. Etant donn\'e un sommet $i$, on note
$A(i)$ {\it l'ascendance} de $i$, c'est-\`a-dire
l'ensemble des sommets $k$ tels que $i$ soit \'el\'ement
de $T(k)$.

 Dans le cas o\`u $i$ est un sommet transitoire, cette
notion correspond exactement, \`a l'orientation pr\`es, \`a
la d\'efinition de $A(i)$ dans le paragraphe pr\'ec\'edent
: si $\varphi (i)=r$, alors $i$ est un sommet de
$A(\rightarrow r)$, et $A(i)$ est un sous-arbre de
Cayley de $A(\rightarrow r)$ enracin\'e en $i$. 

Dans le cas o\`u $i=r$ est r\'ecurrent, $A(r)$ se
compose du cycle $T(r)$ et de tous les arbres de
Cayley enracin\'es sur les sommets de ce cycle (parmi
lesquels figure $A(\rightarrow r)$), autrement dit
$A(r)$ n'est autre qu'une composante connexe toute
enti\`ere du graphe $G_f$.

 Le plus petit sommet de $A(i)$, not\'e $c(i),$
s'appelle le {\it cadet} de $i$. 

  Soit $(i,j)$
une ar\^ete du graphe $G_f$ (autrement dit $f(i)=j$).

  \puce  Si $c(i)>j$, on dit que l'ar\^ete $(i,j)$ est
{\it simple}, on la note dor\'enavant 
$(i\longrightarrow j)$ et on dessine un arc allant de
$i$ vers $j$.
 
  \puce  Si $c(i)\leq j$, on dit que l'ar\^ete $(i,j)$
est {\it double}, on la note dor\'enavant 
$(i\Longrightarrow j)$ et on dessine deux arcs allant
de $i$ vers $j$.  

\medskip
{\it Remarques.---}
Toute ar\^ete r\'ecurrente, c'est-\`a-dire toute ar\^ete d'un
cycle $T(r)$, est double, car $r\in A(r)$, donc
$c(r)\leq r$. 

Pour une ar\^ete transitoire,
c'est-\`a-dire une ar\^ete d'un arbre $A(\rightarrow r)$,
la d\'efinition se confond avec celle du paragraphe
pr\'ec\'edent. La diff\'erence est que l'arbre
$A(\rightarrow r)$ ne comporte plus l'ar\^ete simple 
$(\longrightarrow r)$, le rep\'erage de la racine $r$
s'op\'erant dor\'enavant \`a l'aide du branchement sur le
cycle de $\sigma _f.$ De ce fait, il se peut que toutes les
ar\^etes de $A(\rightarrow r)$ soient doubles (par
exemple si elles sont toutes croissantes). 

 On d\'esigne par $d(f)$ le nombre des ar\^etes
doubles  du graphe $G_f$ et par $\arc(f)$ le nombre
de ses arcs  lorsqu'on remplace chaque ar\^ete simple
par un arc et chaque ar\^ete double par deux arcs. Par
suite, $\arc(f)=n+d(f).$

\medskip
 {\it Exemple.--- } Pour l'application suivante 
$f:[14]\rightarrow [14]$, on a $d(f)=10$
 et $\arc(f)=24$  :
$$\vbox{\halign{#&#&#&#&#&#&#&#&#&#&#&#\cr &&& 14 &&
3 &&&&&& $\e 9$   \cr  &&& $\e\downarrow$ &&
$\Downarrow$ &&&&&& $\e\Downarrow$ \cr 
$4\Longrightarrow$ &10 &$\longrightarrow$ &$\e 1$
&$\Longrightarrow$ &7 & $\longleftarrow$ 13
&\quad&\quad & $\e 6$  &\raise
-2mm\vbox{\hbox{$\Longrightarrow$}
 \hbox{$\Longleftarrow$}}
 & 12 \cr  & $\e\Uparrow$ && $\e \Uparrow$ &&
$\Downarrow$ &&&& $\e\uparrow$ && \cr  & $\e 5$ 
&&$\e 2$ & $\Longleftarrow$ & 8 &&&& 11 && \cr  }} $$
Lorsqu'on d\'enombre les applications selon ce
param\`etre, on obtient le r\'esultat suivant, dont nous
donnerons deux \'enonc\'es \'equivalents :   

\goodbreak
\th  Proposition 6 
\enonce
$1)$ La lettre $y$ d\'esignant
toujours la s\'erie formelle introduite dans les
propositions $4$ et $5$, on a 
$${1\over 1-ay}=1+a^2x+(a^3+3a^4){x^2\over 2!}+(2a^4+10a^5+15a^6){x^3\over 3!}+\cdots
+ \Big(\sum_{f\in \cal F_n}a^{\arc(f)}\Big){x^n\over n!}
+\cdots $$
      
$2)$ Le nombre de Ramanujan $a(n,k)$
est, pour $1\leq k\leq n$, le cardinal de l'ensemble
des applications $f:[n]\mapsto [n]$ poss\'edant $k$
ar\^etes doubles, autrement dit des applications $f$
pour lesquelles il existe $k$ sommets $i$ tels que le
plus petit ascendant de $i$ soit $\leq f(i)$. 
\endth

D'apr\`es la
proposition $3$ et la d\'efinition ci-dessus de
$\arc(f)$,  les deux \'enonc\'es sont clairement
\'equivalents. Le lecteur pourra sans peine mettre au
point une d\'emonstration du second \'enonc\'e analogue 
\`a celles du \S\kern 2pt 4, et trouvera une d\'emonstration du premier
\'enonc\'e dans le paragraphe
suivant.
 
\vskip .5cm 
{\bf \S\kern 2pt 7. D\'emonstration directe des
propositions $5$ et $6$ par compos\'es partitionnels}
\medskip

Une partie de ce paragraphe, plus pr\'ecis\'ement
l'interpr\'etation combinatoire de l'\'equation
diff\'erentielle $(9)$ qui conduit \`a une d\'emonstration
directe de la proposition $5$, nous a \'et\'e sugg\'er\'ee
par Jiang Zeng.

Nous modifions l\'eg\`erement les notations :

\puce $\cal A_{n+1}$ d\'esigne ici
 l'ensemble  des arbres de taille
$n+1$ ayant pour sommets les \'el\'ements de $[0,n]$, les ar\^etes \'etant orient\'ees
\`a partir de $0$.

\puce $\cal A_n(\rightarrow .)$ d\'esigne comme pr\'ec\'edemment
l'ensemble des arbres enracin\'es de taille $n$, c'est-\`a-dire
des couples $(A,r)$ form\'es d'un arbre $A$ sur $[1,n]$
et d'un sommet distingu\'e $r\in [1,n]$ rep\'er\'e par une
ar\^ete $(\longrightarrow r)$.

\puce convenons en outre de noter $\cal A_{n+1}^0(\rightarrow
.)$ l'ensemble des arbres enracin\'es de taille $n+1$, ayant pour
sommets les \'el\'ements de $[0,n]$, et dont le sommet $0$ est
une feuille (i.e. de degr\'e  sortant nul). 

Si $n=0$, l'ensemble $\cal A_1^0(\rightarrow .)$
se r\'eduit \`a l'arbre  $(\longrightarrow 0)$. 

Si $n\geq 1$, la racine $r$ est
distincte de $0$, le sommet $0$ a un p\`ere appel\'e {\it
sortie}, not\'e $s$. Un \'el\'ement de $\cal A_{n+1}^0(\rightarrow .)$
correspond donc \`a la donn\'ee d'un triplet
$(A,r,s)$, o\`u $A$ est un arbre sur $[n]$, et o\`u $r$ et $s$ deux sommets
distingu\'es (non n\'ecessairement distincts) de $A$, $r$ \'etant la racine, 
rep\'er\'ee par une ar\^ete $(\longrightarrow r)$,  et $s$ la
sortie, prolong\'ee par une ar\^ete $(s\Longrightarrow 0)$. 
(C'est un {\sl vert\'ebr\'e} dans la terminologie (due \`a
A. Joyal) de la th\'eorie de esp\`eces, voir [BLL], [L]). Par suite :  
$$card[\cal A_{n+1}^0(\rightarrow .)]=n^n.$$

Nous d\'efinissons \`a pr\'esent les s\'eries \'enum\'eratrices
$Y(x,a))$, $S(x,a)$ et $A(x,a)$ suivantes (par abus de notation, dans ces
sommations les arbres sont toujours not\'es $A$, et non $(A,r)$ ou
$(A,r,s)$) :
 $$ \eqalign{
 Y(x,a)&=\sum_{n\geq 1}\Big(\sum_{A\in\cal A_n(\rightarrow .)}
a^{\arc(A)}\Big){x^n\over n!} \cr 
  S(x,a)&= \sum_{n\geq 0}\Big(\sum_{A\in\cal A_{n+1}}
a^{\arc(A)}\Big){x^n\over n!} \cr  
A(x,a)&=\sum_{n\geq 0}
\Big(\sum_{A\in\cal A_{n+1}^0(\rightarrow .)}
a^{\arc(A)}\Big){x^n\over n!} \cr 
 } 
$$  

Dans ces conditions, on a le r\'esultat suivant :
\medskip
 \th 
Proposition 7 \enonce Les s\'eries $Y$, $S$ et $A$
ainsi d\'efinies satisfont les identit\'es suivantes :
\medskip
(i) $S(x,a)=\exp(Y(x,a))$ 
\medskip
 (ii) $A(x,a)=\displaystyle{a\over 1-aY(x,a)}$
\medskip
 (iii) $\displaystyle {d\over dx}Y(x,a)=A(x,a)S(x,a).$

\medskip
\noindent
Par suite, $Y(x,a)$ s'identifie avec la s\'erie formelle
$y$ introduite dans la proposition $4$ et solution de
l'\'equation diff\'erentielle $(9)$.  
\endth 

{\it D\'emonstration.---} Pour d\'emontrer (i),
Consid\'erons un \'el\'ement $A$ de  $\cal A_{n+1}$. En
supprimant le sommet $0$, on obtient une partition
$\pi $ de $[n]$ en $k$ blocs, et un arbre enracin\'e
$A_j$ sur chaque bloc $B_j$ de cette partition
$(1\leq j\leq k)$.

\medskip
{\it Exemple.---} Dans l'exemple du vert\'ebr\'e ci-dessous,
de racine $r=8$ et de sortie $s=6$, on obtient la partition
$\pi = 1,4,5,10,14/2/3,7,13/6,11/8/9,12$,
six arbres de racines respectives
$1$, $2$, $7$, $6$, $8$, $12$, et l'ordre
lin\'eaire $\enspace 8,2,1,7,12,6\enspace$ sur ces racines.
\medskip

$$\vbox{\halign{#&#& #&#& #&#& #&#& #&#& # \cr
&& &&   14        && \k 5 && && \cr
&& && \k $\uparrow$ && \k $\Uparrow$ && && \cr
$\longrightarrow$ 8 & $\Longrightarrow$ & 2
& $\Longrightarrow$ & \k 1 & $\longrightarrow$ & 10
& $\Longrightarrow$ & \k 4 && \cr
&& && \k $\Downarrow$ && && && \cr
&& 3 & $\Longleftarrow$ & \k 7 & $\Longrightarrow$ & 12
 & $\Longrightarrow$ & \k 6 & $\Longrightarrow$ & 0 \cr
&& && \k $\downarrow$ && \k $\Downarrow$ && \k $\downarrow$ && \cr
&& && 13 && \k 9 && 11 && \cr
}}$$

$$\vbox{\halign{#&#& #&#& #&#& #&#& #&#& #&#& #&# \cr
& 14 & & \k 5 & && && && & 3 && \cr
&\k $\uparrow$ & & \k $\Uparrow$ & && && && & $\Uparrow$ && \cr
$\longrightarrow$ & \k 1 & $\longrightarrow$ & 10 &
$\Longrightarrow$ & 4 &\quad \quad \quad & $\longrightarrow$ & 2 &
\quad \quad \quad & $\longrightarrow$ & 7 & $\longrightarrow$ & 13 \cr
&&&   &&&&& &&&&& \cr
$\longrightarrow$ & \k 6 & $\longrightarrow$ & 11 & 
 & &\quad \quad \quad & $\longrightarrow$ & 8 & \quad \quad \quad
 & $\longrightarrow$ & 12 & $\Longrightarrow$ & 9 \cr
 }}$$


En outre, on a :
$$ 
\som(A)-1=n=\sum_{j=1}^k \som(A_j)\,; \qquad 
\arc(A)=\sum_{j=1}^k \arc(A_j).
$$
On en d\'eduit
l'identit\'e (i) par compos\'e partitionnel {\it 
ab\'elien} [F].

Pour d\'emontrer (ii), \'etant donn\'e un \'el\'ement $A$ de
$\cal A_{n+1}^0(\rightarrow .)$, avec $n\geq 1$,  consid\'erons le
chemin reliant la racine $r$ au sommet $0$, soit
$r_1=r,$ $r_2$, $\ldots$,  $r_l=s$, $r_{l+1}=0$,
chemin de longueur $l\geq 1$, dont toutes les ar\^etes
sont doubles puisque $0$ est dans la descendance de
chaque sommet de ce chemin. On supprime le sommet
$0$, l'ar\^ete $(s\Longrightarrow 0)$, et on remplace
chaque ar\^ete double $r_j\Longrightarrow r_{j+1}$ (o\`u
$1\leq j\leq l-1$) par une ar\^ete  simple rep\'erante
(sans origine) $\longrightarrow r_{j+1}$. On obtient
ainsi une partition $\pi $ en $l$ blocs, $l$ arbres
enracin\'es $A_1$, $A_2$, $\ldots$, $A_l$ de racines
$r_1$, $r_2$, $\ldots$, $r_l$, et un {\it ordre total} sur
ces racines (i.e. une permutation, comme mot lin\'eaire).

\medskip
{\it Exemple.---} Dans l'exemple ci-apr\`es, on obtient
la partition $\pi =1236/4/57$, trois arbres de racines
respectives $3$, $4$, $5$, et l'ordre $4,5,3$ sur ces
racines. 
$$\vbox{\halign{# &#&#&# &#&#&# &#&#&# &#&#&# &#&#\cr 
&&&& 6 &&&& 6 &&&& && \cr 
&&&& $\uparrow$ &&&& $\uparrow$ && &&  && \cr 
$\longrightarrow$ 4 & $\Longrightarrow$ & 5
& $\Longrightarrow$ & 3 & $\Longrightarrow$ 0
&\quad\quad\quad\quad 
&$\longrightarrow$ & 3 & &\quad\quad 
& $\longrightarrow$ 4 &\quad\quad
&$\longrightarrow$ & 5  \cr 
&& $\downarrow$ && $\Downarrow$ &&&&
 $\Downarrow$ &&& &&& $\downarrow$  \cr 
&& 7 && 1 & $\longrightarrow$ 2 
&&& 1 & $\longrightarrow$ 2 && &&& 7    \cr
}}$$ 
En outre, on a : 
$$
\som(A)-1=n=\sum_{j=1}^l \som(A_j)\,;\qquad 
\arc(A)=(l+1)+\sum_{j=1}^l \arc(A_j).
$$
On en d\'eduit
l'identit\'e (ii) par compos\'e partitionnel {\it non
ab\'elien} [F].  Plus pr\'ecis\'ement, le terme
$a^{l+1}(Y(x,a))^l$ est la s\'erie \'enum\'eratrice restreinte
aux \'el\'ements de $\cal A_{n+1}^0(\rightarrow .)$ pour
lesquels la distance de la racine \`a $0$ est \'egale \`a
$l$.

\medskip
 {\it Remarque.---} Si au lieu de prendre un
ordre lin\'eaire sur les racines $r_1$, $r_2$,
$\ldots$, $r_l$, on d\'efinit une permutation de ces
racines d\'ecompos\'ee en cycles, on obtient alors un
\'el\'ement $f$ de $\cal F_n$ et on red\'emontre la
proposition $6$ (Notons que $f$ poss\`ede un arc de
moins que l'arbre enracin\'e $A$ obtenu par l'ordre
lin\'eaire). Dans l'exemple ci-dessus, si l'on prend
la permutation $\sigma = (8,2,1,7)(12,6)$, qui correspond
\`a l'ordre lin\'eaire $8,2,1,7,12,6$ par la transformation
fondamentale, on retrouve l'endo-function qui nous a servi
d'exemple plus haut (le sens des fl\^eches est simplement 
invers\'e \`a partir des racines).

Pour d\'emontrer (iii), consid\'erons un arbre $A$
enracin\'e de taille $n+1$, de sommets $[0,n]$, dont
$r$ est la racine (notons qu'on peut avoir $r=0$).
 Nous
partitionnons le graphe $A$ en deux sous-graphes :
l'ascendance large de $0$, not\'ee $Asc$, et la descendance
stricte de $0$, not\'ee $Desc$ : le sous-graphe $Desc$
(\'eventuellement vide) est $A(0)\setminus \{0\}$, \`a
savoir la descendance de $0$ moins $0$ lui-m\^eme, c'est
donc un compos\'e partitionnel ab\'elien d'arbres
enracin\'es.
$Asc$ est le sous-graphe compl\'ementaire de $Desc$ dans
$A$, c'est donc un arbre enracin\'e dans lequel le sommet
$0$ est pendant. 

\medskip
{\it Exemple.---} Voici un arbre enracin\'e sur $[0,9]$, et les
sous-graphes $Asc$ et $Desc$ correspondants :
$$\vbox{\halign{#
&#&#&# &#&#&# &#&#&# &#&#&# &#&#&# \cr 
& 6 &&& 3 & $\longrightarrow$ 8 & $\Longrightarrow$ 4
&\quad\quad\quad\quad & & 6 &&& \quad\quad 
& $\longrightarrow$ 3 & $\longrightarrow$ 8 & $\Longrightarrow$ 4
\cr 
& $\uparrow$ &&& $\uparrow$ &&
&& & $\uparrow$ &&& & & &
\cr  
$\longrightarrow$ & 5 & $\Longrightarrow$ 9 & $\Longrightarrow$ & 0
& $\longrightarrow$ 4 & $\Longrightarrow$ 2 & & $\longrightarrow$
& 5 & $\Longrightarrow$ 9 & $\Longrightarrow$ 0 & &
$\longrightarrow$ 4 & $\Longrightarrow$ 2 &
\cr
&&&& $\downarrow$ &&&& &&&& &&& \cr 
&&&& 1             &&&& &&&& & $\longrightarrow$ 1 && \cr 
}}$$ 
On en d\'eduit l'identit\'e (iii) par convolution binomiale des
s\'eries $A(x,a)$ et $S(x,a)$. 

\bigskip
\noindent
{\it Table des coefficients}.
$$\vbox{\cleartabs \offinterlineskip \+ $k$ &\quad
\tv \quad &1\quad \quad &2\quad \quad \enspace
&3\quad \quad \enspace &4\quad\quad\enspace
&5\quad\quad\enspace &6\quad\quad &\quad \tv \quad
& \cr  \hrule \+ $n$ &\quad \tv \quad &   &       
&    &       &       &      &\quad \tv \quad & $n^n$
\cr  \+ 1 &\quad \tv \quad &1     &        &    &      
&       &      &\quad \tv \quad & 1 \cr  \+ 2 &\quad
\tv \quad &1    &3       &     &       &      &       
&\quad \tv \quad & 4 \cr  \+ 3 &\quad \tv \quad &2   
&10     &15    &       &      &        &\quad \tv \quad
& 27 \cr  \+ 4 &\quad \tv \quad &6    &40     &105  
&105   &       &        &\quad \tv \quad & 256 \cr  \+
5 &\quad \tv \quad &24   &196    &700   &1260  &945  
&         &\quad \tv \quad & 3125 \cr   \+ 6 &\quad
\tv \quad &120  &1148   &5068  &12600 &17325  &10395 
&\quad \tv \quad & 46656 \cr   } $$

\nobreak
\centerline{table des nombres $a(n,k)$} 
\smallskip
\centerline{$a(n,k)=(n-1)\,a(n-1,k)+(n+k-1)\,a(n-1,k-1)$}

\goodbreak
\bigskip
$$\vbox{\cleartabs \offinterlineskip \+ $k$ &\quad
\tv \quad &0\quad \quad &1\quad \quad &2\quad \quad
\enspace &3\quad\quad\enspace &4\quad\quad\enspace
&5\quad\quad &\quad \tv \quad & \cr  \hrule \+ $n$
&\quad \tv \quad &     &        &       &       &    & 
&\quad \tv \quad & $n^{n-1}$ \cr  \+ 1 &\quad \tv
\quad &1       &        &       &       &    &  &\quad
\tv \quad & 1 \cr  \+ 2 &\quad \tv \quad &1      
&1       &       &       &    &  &\quad \tv \quad & 2
\cr  \+ 3 &\quad \tv \quad &2       &4       &3    
&       &    &  &\quad \tv \quad & 9 \cr  \+ 4 &\quad
\tv \quad &6       &18      &25    &15     &    & 
&\quad \tv \quad & 64 \cr  \+ 5 &\quad \tv \quad
&24      &96     &190    &210   &105 &  &\quad \tv
\quad & 625 \cr   \+ 6 &\quad \tv \quad &120    
&600   &1526  &2380  &2205 &945 &\quad \tv \quad
&7776 \cr   
} $$

\centerline{table des nombres $b(n,k)$}
\smallskip
\centerline{$b(n,k)=(n-1)\,b(n-1,k)+(n+k-2)\,b(n-1,k-1)$}
\bigskip

$$\vbox{\cleartabs \offinterlineskip \+ $k$ &\quad
\tv \quad &0\quad \quad &1\quad \quad \enspace
&2\quad \quad \enspace &3\quad\quad\enspace
&4\quad\quad\enspace &5\quad\quad &\quad \tv \quad
& \cr  \hrule \+ $n$ &\quad \tv \quad &  &     &    
&    &       &     &\quad \tv \quad & $n^{n-2}$ \cr 
\+ 1 &\quad \tv \quad &1    &     &     &    &      
&     &\quad \tv \quad & 1 \cr  \+ 2 &\quad \tv \quad
&1    &     &     &    &       &     &\quad \tv \quad & 1
\cr  \+ 3 &\quad \tv \quad &2   &1    &     &   
&        &     &\quad \tv \quad & 3 \cr  \+ 4 &\quad
\tv \quad &6   &7    &3    &    &        &     &\quad
\tv \quad & 16 \cr  \+ 5 &\quad \tv \quad &24  &46  
&40   &15  &       &      &\quad \tv \quad & 125 \cr  
\+ 6 &\quad \tv \quad &120 &326  &430  &315 &105   
&      &\quad \tv \quad &1296 \cr \+ 7 &\quad \tv
\quad &720 &2556 &4536 &4900 &3150 &945     &\quad
\tv \quad &16807 \cr
} $$

\centerline{table des nombres $c(n,k)$}
\smallskip
\centerline{$c(n,k)=(n-1)\,c(n-1,k)+(n+k-3)\,c(n-1,k-1)$}

\vfill \ej

\vglue 44pt
 \centerline{\bf Bibliographie} \medskip

\ref         BLL \auteur Bergeron F. , Labelle G. et Leroux P
\titre Th\'eorie der esp\`eces et combinatoire des structures
arborescentes \editeur Publications du LACIM,
Montr\'eal \date 1994 \endref


\ref         B \auteur  Berndt B.C \titre   
Ramanujan's Notebooks, Part I, chap. 3 :
Combinatorial Analysis and Series Inversions, p. 80-84
  \editeur  Springer Verlag \date   1985 \endref

\ref         Ch \auteur   Chen W.Y.C \titre   
Context-free Grammars, Differential Operators and
Formal Power Series \nomrevue  Actes Coll. S\'eries
Formelles et Combinatoire Alg\'ebrique, LABRI,
Bordeaux \tome   \date   1991 \pages  144-159 \endref


\ref         F \auteur  Foata D \titre    La s\'erie
g\'en\'eratrice exponentielle dans les probl\`emes
d'\'enum\'eration \editeur  Presses Universitaires de
Montr\'eal    \date   1974 \endref

\ref         H \auteur   Howard F.T \titre    Explicit
formulas for numbers of Ramanujan \nomrevue 
Fibonacci Quarterly \tome  24 \date   1986 \pages 
168-175 \endref

\ref        L \auteur  Labelle J \titre  Applications diverses
de la th\'eorie combinatoire des esp\`eces de structures
\nomrevue Ann. Sci. Math. Qu\'ebec \tome 7 \date 1983
\pages 59-94 \endref 

\ref         Ra \auteur  Ramanujan S \titre    
Notebooks, vol. 1, chap. II,  p. 35-36 \editeur  Tata
Institute of Fundamental Research, Bombay \date   1957
\endref

\ref         Ri \auteur  Riordan J \titre    
Combinatorial Identities, chap. 3 \editeur  Robert E.
Krieger Publishing Company, New York \date   1979
\endref

\ref         W \auteur  Wilf H \titre    
Generatingfunctionology \editeur  Academic Press \date   1990
\endref

\bye











.