\magnification=1200
%ญญญญญญญญญญญญญญญญญญญญญ Reglages generaux ญญญญญญญญญญญ 
%ญญญญญญญญญญญญญญญญญญญญญ que vous pouvez modifier ญญญญญญ 
%ญญญญญญญญญญญญญญญญญญญญญญ sans faire de degats ญญญญญญญญ 
%\input tex8bits

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

\ifnum\mag=1000
\hoffset= 0 mm    % offset horizontal en \magnification=1000
\voffset=10 mm    % offset vertical en \magnification=1000
\fi

\ifnum\mag=1200
\hoffset=7 mm   % offset horizontal en \magnification=1200
\voffset=8 mm   % offset vertical en \magnification=1200
\fi

\ifnum\mag=1440
\hoffset=0 mm   % offset horizontal en \magnification=1440
\voffset=-3 mm  % offset vertical en \magnification=1440
\fi 

% ญญญญญญญญญญญญญญญญญญญญญญญญญญญ Reglages ญญญญญญญญญญ 
% ญญญญญญญญญญญ auquels il ne vaut mieux pas toucher ญญญญญญ 

\pretolerance=500 \tolerance=1000  \brokenpenalty=5000


% ญญญญญญญญญญญญญญญญญญญญ Debut des macros privees ญญญญญญ 
\catcode`\@=11
% ญญญญญญญญญญญญญญญญญญญญญ Les fontes ญญญญญญญญญญญญญญญ 

\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

% Pour que les accents se placent correctement en mode math en corps 8 et 6

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

% Nouvelles familles pour les maths

\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}}


% D้finition des petites capitales qui r้agissent au \tenpoint et \eightpoint
% Syntaxe : \pc FERMAT|, \pd ้RASME et \pc G\"ODEL| 
% ou encore \pc fermat|, \pd ้rasme et \pc g\"odel| (pas besoin de capitales)
% ou encore  \pc Fermat|, \pd ้rasme et \pc G\"odel|


% La programmation est tordue 
% pour que \pc Th้or่me| \quad \pc Th\'eor่me| \quad \pc Th้or\`eme|
% donnent tous le m๊me r้sultat

\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| }

%ญญญญญญญญญญญญญญญญญญญญญญ dactylographie francaise ญญญญญญญญญ 
%ญญญญญญญญญญญญ dactylographie fran็aise ญญญญญญญญญญญญญญญญญญญ

{\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?}%
}}
% fin \frenchdactylography

\frenchdactylography
% \frenchspacing

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


% ญญญญญญญญญญญญญญญญ Le format de sortie ญญญญญญญญญญญญญ 
% Haut et bas de page 

\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  

% \nopagenumbers : c'est un peu violent, mais ็a marche. Alors ...

\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}

% Redefinition de \raggedbottom pour avoir plus de mou en bas de page
% (necesssaire quand il y a beaucoup de grumeaux, des grosses
% formules centrees et pas beaucoup de texte entre)

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

%ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
%ญญญญญญญญญญญญญญญญญญญญญญ Macros de mise en page ญญญญญญญญญญญ 
%ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 

% Un point-tiret

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

%ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% Texte centre dans une boite : le resultat est le plus petit 
% rectangle qui contient le texte. Ce resultat est
% place dans une boite centree.
% SYNTAXE : le passage a la ligne definit les lignes
%     \ctexte
%     La petite fille
%     est all\'ee \`a l'\'ecole
%     \endctexte

{\obeylines%
  \gdef\ctexte%
       {\begingroup\obeylines%
         \let^^M=\cr\makectexte}}

\def\makectexte#1\endctexte%
    {\hbox{$\vcenter{\halign{\hfill##\hfill\crcr#1\crcr}}$}%
      \endgroup%
       }

%ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% pour etre en mode centre dans une boite
% Syntaxe {\centermode ... \par}
% ne pas oublier le \par, sinon la derniere ligne
% ne sera pas centree !
% VARIANTE POSSIBLE :
% \leftskip=0pt plus 25pt (au lieu de 1fill)

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

%ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% Titre centre (en gras)

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

\def\endctitre 
    {\par\endgroup
      \nobreak\bigskip
       }
%ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% on redefinit d'abord \bigbreak et \medbreak
% pour attenuer les \penalty

\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
                    }
%ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% Materiel pour la numerotation automatique

\newif\ifsubsectiontitle
\newcount\sectionnumber   \sectionnumber=0
\newcount\subsectionnumber

\def\secsubnumber{\the\sectionnumber.\the\subsectionnumber}

\def\withnum 
    {\ifsubsectiontitle\global\advance\subsectionnumber by 1
      \the\sectionnumber.\the\subsectionnumber.\enspace\ignorespaces
       \else\global\advance\sectionnumber by 1
        \global\subsectionnumber=0
         \the\sectionnumber.\enspace\ignorespaces
          \fi}
%ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% Les sections

\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}

%ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% Les sous-sections

\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}


%ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% Differentes manieres de commencer un nouveau paragraphe

\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
       }

%ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% Exemples d'utilisation des macros precedentes
% 
% \def\remarque{\newparwithcolon
%                \withnum\pc REMARQUE|
%                 \endnewparwithcolon}
% 
% \def\remarques{\newpara
%                 \pc REMARQUES|
%                  \endnewpar}

% \def\exemple{\newparwithcolon
%               \pc EXEMPLE|
%                \endnewparwithcolon}
% 
% \def\exemples{\newpara
%                \pc EXEMPLES|
%                 \endnewpar}
% 
% \def\definition{\newparwithpointir
%                  \pc D\'EFINITION|
%                   \endnewparwithpointir}
% 
% \def\definitions{\newpara
%                   \pc D\'EFINITIONS|
%                    \endnewpar}
% 
% \def\demonstration{\newparwithcolon
%                     \it D\'emonstration
%                      \endnewparwithcolon}


%ญญญญญญญญญญญญ r้sum้ ญญญญญญญญญญญญญญญญญญญญญญ

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

%ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% enonces de theoremes avec numerotation APRES
% #1 = THEOREME, COROLLAIRE, etc.
% #2 = numero (par exemple 3, 3.1, etc.)
% #3 = l'enonce du th proprememnt dit.

%------- pour que les parentheses et la ponctuation
%-------- ne soit pas en italique 

\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}

\def\@deux@points{\relax
     \ifhmode
      \ifdim\lastskip>\z@\unskip\fi
       \penalty\@M\space{\rm \string:}%
        \else\ifmmode
         \mathrel{\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:{\@deux@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}

%ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% enonces de theoremes avec numerotation AVANT
% #1 = numero (par exemple 3, 3.1, etc.)
% #2 = THEOREME, COROLLAIRE, etc.
% #3 = l'enonce du th proprememnt dit.

\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}

%ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% les differents retraits
% on peut aussi utiliser \item et \itemitem)

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

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

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

% ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% ญญญญญญญญญญญญญญ ce que Knuth n'a pas fait ญญญญญญญญญญญญ 
% ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% Math้matiques centr้es
% ญญญญญญญญญญญญญญญญญญญญญญญญญ

%--------- pour couper une formule trop longue 
% DANS un \displaylines
%----- syntaxe (pas besoin de \cr) :
%
%    $$\displaylines{
%    .....
%    \cutdisplay
%    ......
%    \cutdisplay
%    ......
%    }$$

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

%----------------------------------
% un ``small''displaylines analogue เ une matrice ;
% fabrique une boite centree, donc \leqno possible

\def\smalldisplaylines#1{\displ@y\vcenter{\halign{&\strut
$\@lign\hfil\displaystyle##\hfil$\crcr#1\crcr}}}

%----------------------------------
% Un \displaylines qui num้rote เ droite.
% La syntaxe est la meme que celle de \eqalignno

\def\displaylinesno#1{\displ@y\halign{
\hbox to\displaywidth{$\@lign\hfil\displaystyle##\hfil$}&
\llap{$##$}\crcr#1\crcr}}

%----------------------------------
% Un \displaylines qui numerote a gauche.
% La syntaxe est la meme que celle de \leqalignno

\def\ldisplaylinesno#1{\displ@y\halign{ 
\hbox to\displaywidth{$\@lign\hfil\displaystyle##\hfil$}&
\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr#1\crcr}}

%----------------------------------
% Un \eqalign qui accepte plusieurs alignements verticaux
% Motif : \hfil # & # \hfil & \hfil # & # \hfill, etc.

\def\eqalign#1{\null\,\vcenter{\openup\jot\m@th\ialign{\strut
\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
&&\quad\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
\crcr#1\crcr}}\,}

%--------------------------------------------
% Un eqalign avec numerotation a gauche ET a droite
% syntaxe :
% numero gauche & A & = B & numero droit \cr

\def\fulleqalignno#1{\displ@y\tabskip=\z@skip
      \halign to\displaywidth {
       \rlap{$##$}  \tabskip=\centering &
        \hfil $\@lign \displaystyle {##}$ \tabskip \z@skip &
         $\@lign \displaystyle {{}##}$\hfil  \tabskip \centering &
          \llap {$\@lign ##$}  \tabskip \z@skip \crcr 
           #1\crcr}}
%--------------------------------------------
% idem avec \displaylines

\def\fulldisplaylinesno#1{\displ@y \tabskip=\z@skip
     \halign to\displaywidth{%
      \rlap{$##$}\tabskip=\centering &
       $\@lign \hfil \displaystyle ##\hfil $&
        \llap{$##$}\tabskip=\z@skip\crcr 
         #1\crcr}}

%--------------------------------------------
% Systeme d'equations precede d'une accolade.
% Copi\'e sur \eqalign, on s'en sert comme une matrice
% syntaxe : signe & coef & inconnue
% les coef sont justifi\'es \`a droite (\hfil coef)
% et les inconnues \`a gauche (inconnue\hfil)
% attention : un seul & ou deux && avant le signe =
% selon la justification choisie !
% Exemple : $$\system{
%             &2 &x &- &3 & y & = &&  -5 \cr
%            -&  &x &+ &  & y & = &&   6 \cr
%           }$$

\def\system#1{\left\{\null\,\vcenter{\openup1\jot\m@th
\ialign{\strut$##$&\hfil$##$&$##$\hfil&&
        \enskip$##$\enskip&\hfil$##$&$##$\hfil\crcr#1\crcr}}\right.}


% ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% ญญญญญญญญญญญญญญญญญ Divers gadgets ญญญญญญญญญญญญญญ 
% ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 

% Pour se rendre la vie facile : \up{er}, \up{i\`eme}, n\up{0}, etc.
\def\up#1{\raise 0.85ex\hbox{\smallf@nt#1}}
%----------------------------
% Utilisation : \cf. \etc. \ie. (ne pas oublier le point a la fin !
%----------------------------
\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}
%----------------------------
% virgule apres une fraction
\def\virg{\raise .4ex\hbox{,}}   
%----------------------------
\def\pv{\ ;\enspace} % point-virgule de ponctuation en maths

%----------------------------
% Pour obtenir un cadre rectangulaire :
% Entoure #2 (le texte) d'un filet. 
% Le filet est ecarte de #1 du texte
% La ligne de base n'est pas perdue
% Syntaxe : \boxit[5pt]{...}. 

\def\boxit[#1]#2%
    {\setbox1=\hbox{\kern#1{#2}\kern#1}%
      \dimen1=\ht1 \advance\dimen1 by #1 
       \dimen2=\dp1 \advance\dimen2 by #1 
        \setbox1=\hbox{\vrule height\dimen1 depth\dimen2\box1\vrule}%  
         \setbox1=\vbox{\hrule\box1\hrule}%
          \advance\dimen1 by .4pt \ht1=\dimen1 
           \advance\dimen2 by .4pt \dp1=\dimen2  \box1\relax
            }
%-----------------------------
% analogue, mais avec effet d'ombre
% #1 = epaisseur de l'ombre
% #2 = blanc qui separe le filet du texte
% #3 = ce qu'on veut mettre dans la boite ombree
% la ligne de base n'est pas perdue
% Syntaxe : \shadebox[3pt][5pt]{...}

\def\shadebox[#1][#2]#3%
    {\setbox1=\hbox{\kern#2{#3}\kern#2}%
      \dimen1=\ht1 \advance\dimen1 by #2 
       \dimen2=\dp1 \advance\dimen2 by #2 
        \setbox1=\hbox{\vrule height\dimen1 depth\dimen2 width 0.2pt
                        \box1
                         \vrule  width 0.2pt}%  
          \setbox1=\vbox{\hrule height 0.2pt
                          \box1
                           \hrule height 0.2pt}%
             \dimen3=\wd1 \advance\dimen3 by -#1 
              \dimen4=\ht1 \advance\dimen4 by -#1
               \setbox2=\hbox{\vrule height #1 depth 0pt width\dimen3
                               \vrule height\ht1 depth 0pt width #1}%
                 \advance\dimen1 by .2pt 
                  \ht1=\dimen1 
                   \advance\dimen2 by .2pt \advance\dimen2 by #1
                    \dp1=\dimen2  
                     \box1\kern-\dimen3\lower\dimen2\box2\relax
                      }

%ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% quand il faut smasher seulement le dessus ou le dessous d'une formule 
% Ne tient pas compte du style !!!

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

%ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% \date : 15 Novembre 1987
% j'ai abandonne \date qui provoquait des conflits
% avec le token \date que j'utilise dans les bibliographies

\def\today
    {\ignorespaces\space\the\day\space
      \ifcase\month\or janvier\or f\'evrier\or mars\or avril
       \or mai\or juin\or juillet\or ao\^ut\or septembre
        \or octobre\or novembre\or d\'ecembre\fi\space\the\year
         }
%ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% fractions intelligentes (sans parentheses, puis avec parentheses)

\def\frac#1#2{\mkern 1.5mu {#1\over #2}\mkern 1.5mu }

\font\ninerm=cmr9

\def\sfrac#1#2{\mkern 1.5mu
     \ifmmode\ifinner 
       {\textstyle{\raise 0.5pt\hbox{\sevenrm #1}\over
        \lower 0.5pt\hbox{\sevenrm #2}}} 
         \else 
          {{\textstyle{\hbox{\ninerm #1}\over
            \lower 1.5pt\hbox{\ninerm #2}}}}
             \fi\fi\mkern 1.5mu}

\def\demi{\sfrac 12}

\def\pfrac#1#2{
     \bgroup\mathchoice
      {\Bigl({#1\over #2}\Bigr)}  % \displaystyle 
       {({#1\over #2})}           % \textstyle
        {{\textstyle(}{#1\over #2}{\textstyle)}}  % \scriptstyle
         {{\textstyle(}{#1\over #2}{\textstyle)}}  %\scriptscriptstyle
          \egroup}

%ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% crochets de taille que l'on definit soi-meme
% #1 : dimension qui monte ou descend le crochet
% #2 : la taille du crochet

\def\lbk[#1][#2]{\raise #2\hbox{$\left[\vcenter to #1{}\right. $}}
\def\rbk[#1][#2]{\raise #2\hbox{$\left.\vcenter to #1{}\right]$}}

%ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% pour surligner convenablement
% remplace avantageusement \overline si l'on desire
% de bons resultats

\def\lineover#1#2#3{\mkern#1mu\overline{\mkern-#1mu#2\mkern-#3mu}\mkern#3mu}

%ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% regle graduee en cm
% utile pour la mise au point 
% de la largeur de certaines boites
% syntaxe : \reglegraduee

\def\Graduation{\vrule height 5pt depth 0pt width 0.2pt\kern -0.2pt}
 \def\tiret{\Graduation\vrule height 0.2pt depth 0pt width 5mm}
  \def\nombre#1{\kern 10mm\hbox to 0pt{\hss\sevenrm#1\hss}}

\def\reglegraduee
    {\hrule width 12cm
      \vbox{\count10=24
       \hbox to 0pt{\loop\ifnum\count10>0
                     \tiret
                      \advance\count10 by -1
                       \repeat
                        \Graduation\hss}
          \nointerlineskip\smallskip
           \hbox to 0pt{\count10=1
                         \loop\ifnum\count10<13
                          \nombre{\the\count10}%
                           \advance\count10 by 1
                            \repeat
                             \hss}
               }}

%ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% fleche horizontale dirig\'ee vers la droite et intelligente
% si elle n'a pas de decoration (indice ou exposant)
% c'est une \rightarrow
% si l'indice et l'exposant ne sont pas trop longs,
% c'est une longrightarrow
% sinon, elle s'allonge en cons\'equence
% Syntaxe : \arrow{...}{...}
% le premier groupe est l'exposant, le deuxieme l'indice
% ces deux groupes (memes vides) sont obligatoires !!!

\newdimen\lengtharrow
 \newbox\exponant \newbox\indice
  \newbox\arrowbox

%------------------------------------------------------------
% la longueur d'une \longrightarrow est de 16.11...pt
% la longueur de \arrow sera donc celle d'une \longrightarrow
% tant que l'exposant ne d\'epasse pas 8pt de large
% sinon, on rajoute 4pt de part et d'autre.
% Cas particulier : s'il n'y a ni indice, ni exposant,
% on retrouve \rightarrow

\def\dimmax#1#2{\ifdim#1<#2 #2\else #1\fi}

\def\arrow#1#2%
    {\setbox\exponant=\hbox{$\scriptstyle#1$}
      \setbox\indice=\hbox{$\scriptstyle#2$}
       \lengtharrow=\dimmax{\wd\indice}{\wd\exponant}
        \ifdim \lengtharrow=0pt \setbox\arrowbox=\hbox{$\rightarrow$}
         \else \ifdim\lengtharrow<8pt
                \lengtharrow=16pt
                 \else \advance\lengtharrow by 8pt
                  \fi
                   \setbox\arrowbox=\hbox to\lengtharrow{\rightarrowfill}
                    \ht\arrowbox=3.66875pt \dp\arrowbox=0pt 
                     \setbox\arrowbox=\hbox{$\mathop{\box\arrowbox}\limits
                                            _{\box\indice}^{\box\exponant}$}
                       \fi
                \mathrel{\box\arrowbox}}

%ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% generalise le \buildrel de plain
% exemples de syntaxe avec une fleche dirigee a gauche
% \build\longleftarrow_{...}\endbuild
% \build\longleftarrow^{...}\endbuild
% \build\longleftarrow_{...}^{...}\endbuild
% l'indice ou l'exposant sont facultatifs
% ne surtout pas oublier le \endbuild !!!!

\def\build#1{\mathrel\bgroup\mathop{#1\kern 0pt}\limits}
 \let\endbuild=\egroup

%ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% commodites pour la construction de tableaux
% \vmove[5pt]{...} deplace le groupe vers le haut de 5pt
% SANS RIEN DERANGER DANS LE TABLEAU

\def\vmove[#1]#2{\setbox1=\hbox{\raise#1\hbox{#2}}%
                 \ht1=0pt \dp1=0pt\box1}

%---------------------------------------
% \vspace[5pt] ecarte deux lignes d'un tableau
% \vspace[-2mm] rapproche deux lignes d'un tableau
% (ne peut fonctionner qu'apres un \cr)

\def\vspace[#1]{\noalign{\vskip#1}}

%ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% pour ne pas avoir a chosir entre \hat et \widehat,
% \tilde et \widetilde

\def\hat#1{\setbox1=\hbox{$#1$}
               \ifdim\wd1>7pt
                \mathaccent "0362 {#1}
                 \else\mathaccent"705E {#1}
                  \fi
                   }

\def\tilde#1{\setbox1=\hbox{$#1$}
               \ifdim\wd1>7pt
                \mathaccent "0365 {#1}
                 \else\mathaccent"707E {#1}
                  \fi
                   }

% ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% pour qu'il la ferme le plus possible...

\showboxbreadth=-1  \showboxdepth=-1

% ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% pour avoir des messages raisonnables avec les lettres accentu\'ees
% et les petites capitales

\let\@ldmessage=\message

 \def\message#1%
     {\begingroup
       \def\pc##1{\string\pc\space##1}%
        \def\'{\string'}\def\`{\string`}%
         \def\^{\string^}\def\"{\string"}%
          \@ldmessage{#1}%
           \endgroup
            }


%ญญญญญญญญญญญญญญญญญญญญญญญญญญญญ
% Pour les tableaux
%-----------------------
% syntaxe \tableau\preambule...\endtableau
% pour les filets horizontaux
% utiliser \cr\th ou encore
% \th\vspace[2pt]\th
% en cas de traits espaces

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

%-------------------------
\def\tableau
    {\vtop\bgroup
      \def\th{\noalign{\hrule}}
       \offinterlineskip\halign\expandafter\bgroup
        }

\def\endtableau{\egroup\egroup}

%-----------------------
% divers preambules (liste non exhaustive !)
%-----------------------
% justification a droite, pas de filet, mode math

\def\preambuleI[#1]{% 
     \tvi\hfil\kern#1$##$\kern#1&&
      \tvi\hfil\kern#1$##$\kern#1\cr}
%-----------------------
% justification a droite, filets verticaux, mode math

\def\preambuleItv[#1]{%
     \tv\hfil\kern#1$##$\kern#1\tv&&
      \tvi\hfil\kern#1$##$\kern#1\tv\cr}

%-----------------------
% mode centre, pas de filet, mode math

\def\preambuleII[#1]{%
     \tvi\hfil\kern#1$##$\kern#1\hfil&&
      \tvi\hfil\kern#1$##$\hfil\kern#1\cr}

%-----------------------
% mode centre, filets verticaux, mode math

\def\preambuleIItv[#1]{%
     \tv\hfil\kern#1$##$\kern#1\hfil\tv&&
      \tvi\hfil\kern#1$##$\hfil\kern#1\tv\cr}

%ญญญญญญ guillements fran็ais (pis-aller)

\def\og{\leavevmode\raise 1pt\hbox{$\scriptscriptstyle\langle\!\langle\,$}}
\def\fg{\ignorespaces\leavevmode\raise 1pt\hbox{$\,\scriptscriptstyle\rangle\!\rangle$}}




% ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 
% fin des macros privees
% ญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญญ 

\catcode`\@=12
%%%%%%% bibliographie selon AMS style %%%%%%%%%%%
%%%%%%% inspir้ de TUGboat 11 (1990), p. 609 %%%%%%%


\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

\hsize=12.5cm
\def\,{\mkern 3mu}
\def\tg{\mathop{\rm tg}\nolimits}
\def\cos{\mathop{\rm cos}\nolimits}
%\font\bb=msym10
%\font\sp=eufm10
%\font\cm=cmbsy10
%\overfullrule=0mm

\ctitre
 Grammaires de William Chen et d\'erivations dans les arbres
et arborescences
\medskip
Dominique DUMONT
\medskip
D\'epartement de Math\'ematiques
Universit\'e Louis Pasteur,
7 rue Ren\'e Descartes, 67084 Strasbourg 
\endctitre
\sectiona
1.Introduction
\endsection
 Etant donn\'e
un alphabet fini ou infini  $X=\{
x_1,x_2,x_3,\ldots \}$, et 
l'alg\`ebre $C[X]$ des polyn\^omes
commutatifs dans les lettres $x_i$, une
{\it grammaire} est un ensemble de
r\`egles de r\'e\'ecritures des lettres
de l'alphabet {\it (substitution
rules)}, c'est- \`a-dire une
application $G$ de $X$ dans $C[X]$ :
$$
G=\{ x_1\rightarrow G(x_1),\quad
x_2\rightarrow G(x_2),\quad
x_3\rightarrow G(x_3),\quad \ldots
\}
$$  
Notons que le plus souvent les
$G(x_i)$ sont des mon\^omes, mais
nous donnerons des exemples o\`u ce
sont des polyn\^omes. (William Chen [Ch]
se place dans un contexte plus
g\'en\'eral o\`u les $G(x_i)$ sont ce
qu'il appelle des ``formal functions",
qui peuvent \^etre des s\'eries
formelles).\par   A une grammaire $G$
on associe une {\it d\'erivation}
$D_G$, not\'ee plus simplement $D$, qui
co\"\i ncide avec $G$ sur les lettres 
$(D(x_i)=G(x_i))$,
 s'\'etend aux mon\^omes par application de la r\`egle de Leibniz :
$$
D(uv)=D(u)v+uD(v),
$$
puis s'\'etend aux polyn\^omes par
lin\'earit\'e. Il est clair que
l'op\'erateur de d\'erivation 
  $D$ s'identifie \`a la somme (finie ou
infinie) : 
$$D=D(x_1){\partial
\over\partial x_1}+D(x_2){\partial
\over\partial x_2} +D(x_3){\partial
\over\partial x_3}+\cdots 
$$ 
mais nous
utiliserons peu cette notation et
lui pr\'ef\'ererons la pr\'esentation
fl\^ech\'ee de W. Chen, et cela pour deux
raisons : d'une part la notation
utilisant les d\'eriv\'ees partielles
est lourde quand l'alphabet est infini
(et l'apport principal de W. Chen
consiste pr\'ecis\'ement \`a \'etudier
des cas de ce type), d'autre part cette
notation exprime un calcul purement
formel alors que la grammaire introduit
un  calcul {\it combinatoire}. Par
exemple le calcul formel  
$$
yz{\partial \over\partial
x}\,x^3=3x^2yz
$$  ne refl\`ete
qu'imparfaitement le calcul grammatical
$$xxx\rightarrow
(yz)xx+x(yz)x+xx(yz)$$ dans lequel
chacune des trois lettres $x$ est tour
\`a tour r\'e\'ecrite $yz,$ (ce qui
conduit d'ailleurs naturellement \`a
une extension d'un tel calcul au cas
non commutatif, mais ce n'est pas notre
objectif ici).\par 
Etant donn\'ees une
grammaire $G$ et la d\'erivation
associ\'ee $D$, on s'int\'eresse \`a la
suite des polyn\^omes qui sont les d\'eriv\'ees
successives d'une lettre, par exemple :
$$
x_1,\quad D(x_1),\quad  D(D(x_1)),
\cdots \quad D^n(x_1), \cdots
$$ et \`a
la s\'erie g\'en\'eratrice
exponentielle $Gen(x_1,t)$ de cette
suite : 
$$
Gen(x_1,t)=x_1+D(x_1)t+
D^2(x_1){t^2\over 2!}+\cdots  +
D^n(x_1){t^n\over n!} +\cdots 
$$
On fait de m\^eme pour chaque lettre $x_i$.
Une autre mani\`ere d'introduire ces
s\'eries g\'en\'eratrices est de
consid\'erer les fonctions $y_1(t),$
$y_2(t),$  $y_3(t),\cdots$ solutions
du syst\`eme diff\'erentiel 
$$
\eqalign{
y'_1(t)&=D(y_1(t)),\quad\quad
y_1(0)=x_1 \cr 
y'_2(t)&=D(y_2(t)),\quad\quad
y_2(0)=x_2 \cr 
y'_3(t)&=D(y_3(t)),\quad\quad
y_3(0)=x_3 \cr \cdots &=\cdots \cr
}$$ 
dans lequel $D(y_i(t))$ est la
fonction obtenue en rempla\c cant dans
le polyn\^ome $D(x_i)$ chaque lettre
$x_j$ par la fonction $y_j(t)$ (et en
faisant des produits et des sommes de
fonctions). Dans ces conditions on a, 
par la r\`egle de Leibniz, l'identit\'e
suivante pour $n\geq 0 :$
 $$
y_i^{(n)}(t)=D^n(y_i(t)).
$$
Par suite 
$$y_i^{(n)}(0)=D^n(y_i(0))=D^n(x_i),$$
ce qui montre que $y_i(t)$ n'est autre
que $Gen(x_i,t)$. Nous ne faisons
ici que rappeler un r\'esultat
classique qu'on trouve par exemple
 dans [BLL]
(section 5.2)\par 
On peut aussi
introduire, \`a partir d'un polyn\^ome
$p$ dans les lettres $x_i$, les
polyn\^omes d\'eriv\'ees successifs
$D^n(p)$ et leur s\'erie
g\'en\'eratrice $Gen(p,t).$ A ce sujet
nous rappelons (W. Chen [Ch], prop. $3.2$
et $3.4$) que l'application $p\mapsto
Gen(p,t)$ est un homomorphisme de
l'alg\`ebre diff\'erentielle $(C[X],D)$
sur l'alg\`ebre diff\'erentielle $(C[[t]],
{d\over dt}),$ en ce sens que 
$$\eqalign{
Gen(pq,t)&=Gen(p,t)Gen(q,t),\cr
Gen(D(p),t)&={d\over dt}Gen(p,t).\cr}
$$

\medskip 
Notre objectif dans cet article est
de pr\'esenter sous cet angle un certain
nombre d'exemples de suites de
polyn\^omes classiques, qui pr\'esentent
essentiellement deux aspects,
un aspect proprement ``calculatoire", et
un aspect ``combinatoire" en tant
que polyn\^omes \'enum\'erateurs. 

Dans la Combinatoire de nagu\`ere, le lien
entre les deux aspects s'op\'erait le
plus souvent par le biais de relations
de r\'ecurrences sur les suites
d'entiers qui sont les coefficients des
polyn\^omes. Ainsi une m\^eme relation
de r\'ecurrence sur des entiers
s'interpr\`ete \`a la fois comme la
traduction d'un calcul formel sur des
polyn\^omes ou des s\'eries, et comme
la traduction de d\'enombrements
d'ensembles d'objets combinatoires.\par

Cette co\"\i ncidence des deux
traductions apparaissait, et
appara\^\i t encore parfois, comme un
peu myst\'erieuse. Aujourd'hui on 
tend \`a construire des th\'eories
 explicatives. Par exemple quand on
fait le lien entre le calcul de
l'exponentielle d'une s\'erie formelle
et la notion combinatoire de compos\'e
partitionnel [F], on aboutit \`a une
identit\'e telle que 
$$exp(xt+{t^2\over 2!})=\sum_{n\geq
0}(\sum_{\sigma \in I_n}x^{fix(\sigma
)}) {t^n\over n!}$$ o\`u $I_n$
d\'esigne l'ensemble des involutions de
$[n]$. La th\'eorie permet de faire
l'\'economie des coefficients des
polyn\^omes, en fait elle fournit
l'interpr\'etation combinatoire de ces
coefficients  sans qu'il soit besoin de
faire appel ni \`a leur expression
(close ou sommatoire), ni \`a leur
r\'ecurrence, ni m\^eme \`a leur
notation.\par 

Cette approche, qui vise \`a expliciter
des liens ``fondamentaux" entre calcul
et combinatoire, a \'et\'e reprise et
d\'evelopp\'ee par d'autres \'ecoles,
notamment \`a travers la th\'eorie des
esp\`eces de structures de l'\'ecole 
qu\'ebecquoise [BLL]. On y d\'efinit un ensemble
de concepts qui fournissent un cadre
explicatif g\'en\'eral pour
 un grand nombre
de cas particuliers d\'ej\`a connus, et
permet de formuler des th\'eor\`emes
g\'en\'eraux. 

Notre ambition ici se bornera \`a dresser
une liste d'exemples de grammaires.
Chacune de ces grammaires engendre
par d\'erivations successives une suite
de polyn\^omes. Or on constate que
ces polyn\^omes sont
\'enum\'erateurs sur
certains objets combinatoires. Par
exemple ils \'enum\`erent certaines
structures arborescentes selon les
ar\^etes ou les sommets pond\'er\'es par
les lettres de l'alphabet. Le lien avec
la grammaire provient de ce que dans
tout ``prolongement" d'un objet
 de taille $n-1$ en un objet
``d\'eriv\'e" de taille $n,$ l'insertion du
nouveau sommet  \'etiquet\'e $n$ se traduit
sur le polyn\^ome \'enum\'erateur
des sommets ou ar\^etes par une r\`egle
de r\'e\'ecriture d'une certaine lettre. 

En outre cette m\^eme grammaire permet
aussi de rendre compte d'un
certain calcul sur les s\'eries formelles.
Elle constitue de ce fait un point de
jonction entre combinatoire et calcul
qui permet de se passer des
coefficients entiers. Nous nous
situons donc bien ici dans la d\'emarche
de pens\'ee qui se trouve \`a l'origine des
th\'eories sur les fondements de la
Combinatoire \'enum\'erative. Notons \`a ce
propos que le point de vue
``grammatical" des r\`egles de
r\'e\'ecritures litt\'erales, tel qu'il a \'et\'e
pr\'esent\'e par William Chen, est de toute
\'evidence fortement reli\'e aux concepts
d'``arborescence enrichie" et
d'``\'eclosion combinatoire" introduits
par l'\'ecole qu\'ebecquoise (cf. [BLL]).
Cependant nous ne chercherons pas ici
\`a faire le lien avec cette th\'eorie
g\'en\'erale, notre  ambition n'\'etant
que de fournir nombre d'exemples
qui plaident en faveur du ``point de vue
grammatical", exemples souvent peu
connus, et nouveaux pour certains.

Nous distinguerons deux parties dans
notre expos\'e, selon que l'alphabet de
base est fini ou infini.  \par 

 \sectiona
 2. Exemples o\`u l'alphabet $X$ est fini
\endsection  
\section
2.1.  Polyn\^omes eul\'eriens
\endsection
Etant donn\'ee une permutation $\sigma $ de
$[n]$, une ar\^ete de cycle est un
couple $(i,\sigma (i))$. C'est une
mont\'ee de cycle si $i<\sigma (i),$
une descente de cycle si $i>\sigma
(i)$, une boucle si $i=\sigma (i).$\par
Commen\c cons par le polyn\^ome
\'enum\'erateur des permutations
circulaires (pour $n\geq 2$) selon les
mont\'ees et descentes de cycles :
$$A_n(x,y)=\sum_{\sigma \in
C_n}x^{mc(\sigma )}y^{dc(\sigma
)}.$$  Par exemple on a, pour $n=3$,
deux \'el\'ements de $C_3$. A 
 $\sigma =(123)$ correspond le
mon\^ome $x^2y$, et \`a $\sigma
=(132)$ correspond le mon\^ome
$xy^2$, d'o\`u 
$A_3(x,y)=x^2y+xy^2.$ Pour passer de
$A_{n-1}(x,y)$ \`a $A_n(x,y)$, on
observe qu'une insertion de $n$ dans le
cycle d'une permutation circulaire
$\tau$ de $[n-1]$ correspond au choix
 d'une ar\^ete $(i,\tau(i))$ 
(mont\'ee ou descente) de $\tau$, puis
au  remplacement de celle-ci par
une mont\'ee $(i,n)$ et une descente
$(n,d(i))$ pour $\sigma $. 
Sur le polyn\^ome \'enum\'erateur cela
revient \`a r\'e\'ecrire l'une des
lettres $x$ ou $y$ du mon\^ome selon
la grammaire  $$G=\{x\rightarrow
xy,\quad y\rightarrow xy \}.$$ En
consid\'erant toutes les insertions
possibles, on obtient : 
 $$A_n(x,y)=DA_{n-1}(x,y),$$
o\`u $D$ est la d\'erivation associ\'ee
 \`a cette grammaire. 
Voici les premi\`eres valeurs 
des polyn\^omes eul\'eriens 
(donn\'es ici sous
leur forme homog\`ene et sym\'etrique) :
$$\eqalign{ A_1(x,y,z)&=z \cr
A_2(x,y)&=xy \cr
A_3(x,y)&=x^2y+xy^2 \cr
A_4(x,y)&=x^3y+4x^2y^2+xy^3 \cr 
A_5(x,y)&=x^4y+11x^3y^2+11x^2y^3+xy^4 \cr
}$$
Nous avons \'ecrit $A_1(x,y,z)=z$ car
dans le cas $n=1$ on a une boucle, et
en fait la grammaire que nous avons
utilis\'ee est  $$G=\{x\rightarrow
xy,\quad y\rightarrow xy, \quad
z\rightarrow xy \}.$$ 
 \par\medskip
2.2 {\bf Polyn\^omes de Roselle}
\par\medskip
La grammaire pr\'ec\'edente
doit \^etre compl\'et\'ee si
l'on veut obtenir le polyn\^ome
\'enum\'erateur de l'ensemble des
permutations selon les trois
statistiques : mont\'ees, descentes,
boucles. Consid\'erons la grammaire
suivante : 
$$G=\{x\rightarrow xy,\quad
y\rightarrow xy, \quad z\rightarrow xy
,\quad e\rightarrow ez \},
$$
Initialisons en $e$ et en d\'erivons
selon l'op\'erateur $D$ associ\'e \`a cette
grammaire. Les polyn\^omes
$E_n(x,y,z)=D^n(e)$ ont pour
premi\`eres valeurs :
  
$$\eqalign{
E_0(x,y,z)&=e \cr E_1(x,y,z)&=ez \cr
E_2(x,y,z)&=e(xy+z^2) \cr
E_3(x,y,z)&=e(x^2y+xy^2+3xyz+z^3)
\cr
E_4(x,y,z)&=e(x^3y+7x^2y^2+xy^3+4x^2yz+4xy^2z+6xyz^2+z^4)
\cr }$$ 
Il est clair que 
$$E_n(x,y,z)=e\sum_{\sigma \in
S_n}x^{mc(\sigma )}y^{dc(\sigma
)}z^{b(\sigma)} .$$ Dans cette
\'ecriture, la lettre $e$ d\'esigne la
place vide destin\'ee \`a \^etre \`a la
fois occup\'ee par la boucle $(n,n)$ (en
cas d'insertion de ce type) et
reconduite (dans la m\^eme
hypoth\`ese), d'o\`u $e\longrightarrow
ez$. Notons que les polyn\^omes
$E_n(x,y,0)$, qui \'enum\`erent les
d\'erangements selon les mont\'ees et
descentes de cycles, ont \'et\'e
\'etudi\'es par Roselle [Ro]. Par ailleurs
posons : $$E(t)=\sum_{n\geq 0}{1\over
e}E_n(x,y,z){t^n\over n!}\quad {\rm
et} \quad A(t)=\sum_{n\geq
1}A_n(x,y){t^n\over n!}.$$ La th\'eorie
du compos\'e partitionnel fournit
imm\'ediatement l'identit\'e
$$E(t)=exp(A(t)).$$ Mais nous
pouvions \'egalement obtenir ce
r\'esultat en observant que 
$E(t)={1\over e}Gen(e,t)$, d'o\`u 
$$E'(t)={1\over e}Gen(ez,t)={1\over
e}Gen(e,t)Gen(z,t) =E(t)A'(t).$$
\par\medskip
2.3. {\bf Arborescences croissantes de type
$(0,1,2)$ (ou arbres
d'Andr\'e)}\par\medskip 
Soit $f$
une application  de $\{2,3,\ldots n\}$
dans $\{1,2,\ldots n-1\}$ qui satisfait
les deux conditions suivantes : \par
(C1) pour tout $i\in\{2,3,\ldots n\}$,
$f(i)<i$ ; \par
 (C2) pour tout $j\in
\{1,2,\ldots n-1\}$, $0\leq card
(f^{-1}(j))\leq 2$. \par
 On trace une
ar\^ete orient\'ee croissante
$j\rightarrow i$ chaque fois que $i$
est ant\'ec\'edent de $j$ ($f(i)=j$), 
et on obtient ainsi un arbre $E$ qu'on
appelle un {\it arbre d'Andr\'e}, d'apr\`es [FS]. C'est
une arborescence dont les sommets
sont $\{1,2,3,\ldots n\}$, dont les
$n-1$ ar\^etes sont croissantes, et tel
que chaque sommet poss\`ede $0$, $1$
ou $2$ fils. Il est clair que la
donn\'ee de l'arbre d'Andr\'e $E$ est
\'equivalente \`a celle de $f$
v\'erifiant (C1) et (C2). On d\'esigne
par $E_n$ l'ensemble des arbres
d'Andr\'e $E$ de taille $n$, et on
consid\`ere le polyn\^ome
\'enum\'erateur $$E_n(x,y)=\sum_{E \in
E_n}x^{ext(E)}y^{un(E)},$$ o\`u
$ext(E)$ d\'esigne le nombre {\it
d'extr\'emit\'es} de $E$,
c'est-\`a-dire de sommets sans fils, et
$un(E)$ le nombre de sommets {\it
unaires}, c'est-\`a-dire ayant un seul
fils (on ne met pas de lettre $z$ pour
les sommets binaires, sauf si l'on veut
homog\'en\'eiser le polyn\^ome).\par
 Pour passer
d'un arbre $E$ de taille $n-1$ \`a un
arbre $F$ de taille $n$, il faut choisir
une extr\'emit\'e $e$ ou un sommet
unaire $u$ de $E$ et faire
$e\rightarrow n$ ou $u\rightarrow n$.
Dans le premier cas, on remplace une 
lettre $x$ par $xy$, dans le second
cas on remplace une lettre $y$ par $x$
(puisqu'on ne compte pas le sommet
binaire cr\'e\'e, mais seulement
l'extr\'emit\'e cr\'e\'ee). Par suite 
$$E_n(x,y)=DE_{n-1}(x,y),\quad\quad
{\rm avec}\quad
 G=\{x\rightarrow xy,\quad y\rightarrow x\}$$
Voici les premi\`eres valeurs des polyn\^omes d'Andr\'e $E_n(x,y)$ :
$$\eqalign{
E_1(x,y)&=x \cr
E_2(x,y)&=xy \cr
E_3(x,y)&=xy^2+x^2 \cr
E_4(x,y)&=xy^3+4x^2y \cr
E_5(x,y)&=xy^4+11x^2y^2+4x^3 \cr
}$$
Montrons que $E_n(1,1)$ est le
$n-$i\`eme nombre d'Euler (s\'ecant ou
tangent). Posons
  $$Y(t)=Gen(y,t)=y+\sum_{n\geq 1}E_n(x,y){t^n\over n!}.$$
On a, d'apr\`es l'homomorphisme
d'alg\`ebres diff\'erentielles rappel\'e
dans l'intro\-duc\-tion :
  $$\eqalign{
Y'(t)&=Gen(x,t) \cr Y''(t)&=Gen(xy,t)
\cr
     &=Gen(x,t)Gen(y,t)\cr
     &=Y'(t)Y(t), \cr
}$$
d'o\`u $Y''(x,y;t)=Y(x,y;t)Y'(x,y:t)$,
avec $Y(x,y;0)=y$ et $Y'(x,y;0)=x$.
On peut int\'egrer cette \'equation
g\'en\'erale, mais nous nous
int\'eressons plus particuli\`erement
au cas o\`u $x=y=1$, et il est bien
connu qu'alors la solution de cette
\'equation est  $$Y(1,1;t)={1\over \cos
t}+\tg t$$ d'o\`u le r\'esultat
classique [FS].

\section
2.4. Arbres binaires croissants.
\endsection
Un arbre binaire
croissant $A$ de taille $n$ est un
couple $A=(E,\varphi)$, o\`u $E$ est
un arbre d'Andr\'e de taille $n$ et
$\varphi$ une application de l'ensemble
des $n-1$ ar\^etes de l'arbre dans
l'ensemble ``gauche-droite" $\{g,d\}$,
avec pour seule restriction que les
deux ar\^etes issues d'un sommet
binaire sont l'une, gauche, et l'autre,
droite.\par  

L'ar\^ete issue d'un
sommet unaire elle \'etant soit gauche,
soit droite, il existe non pas un, mais
deux prolongements d'une extr\'emit\'e
$e$ en une ar\^ete $e\rightarrow n$,
tandis qu'il existe toujours un seul
prolongement  d'un sommet unaire $u$ en
une ar\^ete $u\rightarrow n$ (cette
nouvelle ar\^ete sera gauche si la
premi\`ere ar\^ete issue de $u$ \'etait
droite, et inversement). Par
cons\'equent, si $$P_n(x,y)=\sum_{A
\in A_n}x^{ext(A)}y^{un(A)}$$ est le
polyn\^ome \'enum\'erateur des arbres
binaires croissants selon les m\^emes
param\`etres, on a 
$$P_n(x,y)=D^n(y),\quad\quad {\rm
avec}\quad G=\{x\rightarrow 2xy,\quad
 y\rightarrow x\},\quad {\rm soit :}$$
$$\eqalign{
P_1(x,y)&=x \cr
P_2(x,y)&=2xy \cr
P_3(x,y)&=4xy^2+2x^2 \cr
P_4(x,y)&=8xy^3+16x^2y \cr
P_5(x,y)&=16xy^4+88x^2y^2+16x^3 \cr
}$$

Notons que si l'on homog\'en\'eise les
polyn\^omes en prenant les $n$ sommets : 
$$\eqalign{
E_n(x,y,z)&=\sum_{E \in
E_n}x^{ext(E)}y^{un(E)}z^{bin(E)},\cr
P_n(x,y,z)&=\sum_{A \in
A_n}x^{ext(A)}y^{un(A)}z^{bin(A)}
}$$
il est clair qu'alors
$P_n(x,y,z)=E_n(x,2y,2z)$. En outre
il existe une bijection classique entre
arbres binaires croissants et
permutations, consistant
intuitivement \`a projeter sur l'axe
horizontal les sommets de l'arbre pour
obtenir un ordre lin\'eaire d\'efinissant
la permutation.  Cette bijection fait
correspondre aux sommets binaires de
l'arbre les {\it creux} du mot de la
permutation $(\sigma (i-1)>\sigma
(i)<\sigma (i+1)$, d'o\`u
l'interpr\'etation combinatoire de
$P_n(1,1,z)$ comme \'enum\'erateurs 
des creux sur les permutations. 

\sectiona
3. Exemples de grammaires o\`u l'alphabet $X$ est infini
\endsection
\section
3.1. Grammaire de Faa di Bruno et polyn\^omes de Bell
\endsection
Ce paragraphe est essentiellement d\^u \`a Chen [Ch].
Sur l'alphabet
$X=\{x_1,x_2,x_3,\ldots, y_0,y_1,y_2,y_3,\ldots \}$ 
on d\'efinit la
grammaire de Faa di Bruno comme 
 $$\displaylines{
G=\{x_1\rightarrow x_2,\quad
x_2\rightarrow x_3,\quad x_3\rightarrow x_4 \ldots\cr
 \hskip 3 cm y_0\rightarrow
y_1x_1,\quad y_1\rightarrow y_2x_1,\quad 
 y_2\rightarrow y_3x_1 \ldots \}
}$$
On consid\`ere la suite $D^n(y_0)$ associ\'ee :
$$\eqalign{
D^0(y_0)&=y_0 \cr
D^1(y_0)&=y_1x_1 \cr
D^2(y_0)&=y_1x_2+y_2x_1^2 \cr
D^3(y_0)&=y_1x_3+y_2(3x_1x_2)+y_3x_1^3 \cr
D^4(y_0)&=y_1x_4+y_2(4x_1x_3+3x_2^2)+y_3(6x_1^2x_2)+y_4x_1^4 \cr
}$$
Ces polyn\^omes ont deux interpr\'etations fondamentales : calculatoire et
combinatoire.\par
Sur le plan du calcul il s'agit de la composition de deux s\'eries
g\'en\'eratrices exponentielles, ou, ce qui revient au m\^eme, du calcul
des d\'eriv\'ees successives d'une fonction de fonction. Soient
$$\eqalign{
x(t)&=x_1t+x_2{t^2\over 2!}+\cdots +x_n{t^n\over n!}+\cdots \cr
y(x)&=y_0+y_1x+y_2{x^2\over 2!}+\cdots +y_n{x^n\over n!}+\cdots 
}$$
deux s\'eries. Comme la premi\`ere est sans terme constant, il est
possible de la substituer \`a la variable de la seconde. On consid\`ere
donc
 $$y(x(t))=y_0+y_1x(t)+y_2{x(t)^2\over 2!}+\cdots +y_n{x(t)^n\over n!}
+\cdots $$ 
et en d\'eveloppant $y(x(t))$ selon les puissances croissantes de
$t$, on obtient pr\'ecis\'ement :
$$\displaylines{
y(x(t))=y_0+y_1x_1t+(y_1x_2+y_2x_1^2){t^2\over 2!}+
(y_1x_3+y_2(3x_1x_2)+y_3x_1^3){t^3\over 3!}\cr
\hskip 2 cm+\cdots +D^n(y_0){t^n\over n!}+\ldots 
}$$
En effet, notons $x^{(k)}(t)$, puis plus simplement $x_k(t)$, la
d\'eriv\'ee $k-$i\`eme de $x(t)$. De m\^eme,
notons $y^{(k)}(x(t))$, puis plus simplement $y_k(t)$, la fonction obtenue
en substituant $x(t)$ \`a $x$ dans $y^{(k)}(x)$. On a alors les d\'eriv\'ees
successives : 
$$\eqalign{
{d\over dt}y(x(t))&=y'(x(t))x'(t) = y_1(t)x_1(t) \cr
{d^2\over dt^2}y(x(t))&=y'(x(t))x''(t)+y''(x(t))x'(t)^2 
  =y_1(t)x_2(t)+y_2(t)x_1^2(t)\cr
{d^3\over dt^3}y(x(t))&
=y_1(t)x_3(t)+y_2(t)(3x_1(t)x_2(t))+y_3(t)x_1^3(t) \cr
}$$
Il est clair que 
$$\eqalign{
{d\over dt}x_k(t)&=x_{k+1}(t),\cr
{d\over dt}y_k(t)&={d\over dt}y^{(k)}(x(t))=y^{(k+1)}(x(t))\cdot x'(t)
=y_{k+1}(t)x_1(t).
}$$
Par suite
$${d^n\over dt^n}y(x(t))=D^n(y_0(t))$$
d'o\`u le r\'esultat en prenant $t=0$.

Pour l'interpr\'etation combinatoire, on introduit l'ensemble $\Pi_n$ des
partitions $\pi$ de $[n]$. Etant donn\'ee une partition $\pi$ de $[n]$, on
note $b_i(\pi)$ le nombre de blocs de $\pi$ de cardinal $i$, et 
$b(\pi)=b_1(\pi)+b_2(\pi)+\cdots +b_n(\pi)$ le nombre total de ses blocs.
Alors on a : 
$$D^n(y_0)=\sum_{\pi\in\Pi_n}y_{b(\pi)}x_1^{b_1(\pi)}x_2^{b_2(\pi)}\cdots
x_n^{b_n(\pi)}.$$
{\it Exemple.---} Voici, pour $n=3$, les cinq partitions $\pi$ suivies de
leurs mon\^omes respectifs $m(\pi)$ entre parenth\`eses :
$$\displaylines{
/123/ (y_1x_3)\quad /1/23/ (y_2x_1x_2) \quad /2/13/ (y_2x_1x_2)\cr
/3/12/ (y_2x_1x_2)\quad /1/2/3/ (y_3x_1^3)
}$$
{\it D\'emonstration.---} Si $\pi$ est une partition de $[n]$ et $\bar\pi$
la partition de $[n-1]$ obtenue en supprimant $n$ de son bloc dans $\pi$,
on dit que $\bar\pi$ est la restriction de $\pi$ et que $\pi$ est un
prolongement de $\bar\pi$. Comparons alors $m(\bar\pi)$ et $m(\pi)$.
Si l'on prolonge $\bar\pi$ en $\pi$ en ins\'erant $n$ dans un bloc de 
cardinal $i$ de $\bar\pi$, alors il suffit de remplacer une lettre $x_i$
de $m(\bar\pi)$ par $x_{i+1}$ pour obtenir $m(\pi)$. Mais si l'on prolonge 
$\bar\pi$ en $\pi$ en cr\'eant un nouveau bloc $\{n\}$ alors, en posant 
$k=b(\bar\pi)$,  il
faut remplacer la lettre $y_k$ de $m(\bar\pi)$ par $y_{k+1}x_1$ pour
obtenir $m(\pi)$. Par suite
$$D(m(\bar\pi))=\sum_\pi m(\pi),$$
o\`u la somme est \'etendue \`a tous les prolongements $\pi$ de $\bar\pi$.
En prenant toutes les $\bar\pi$, chaque
$\pi$ est obtenue une fois, comme prolongement de sa restriction :
 $$D\Bigl(\sum_{\bar\pi\in\Pi_{n-1}}m(\bar\pi)\Bigr) 
=\sum_{\pi\in\Pi_n}m(\pi),$$
d'o\`u le r\'esultat par induction sur $n$.\par
Rappelons pour conclure qu'on note souvent 
$$D^n(y_0)=\sum_{1\leq k \leq n}y_kB_n,k(x_1,x_2,\ldots ,x_n),$$
les $B_{n,k}$ s'appelant les polyn\^omes de Bell. En prenant tous les
$y_k$ \'egaux \`a $1$, on obtient la fonction g\'en\'eratrice bien connue :
$$
exp(x(t))=\sum_{n\geq 0}
 \Bigl(\sum_{1\leq k \leq n}B_n,k(x_1,x_2,\ldots ,x_n) \Bigr)
{t^n\over n!}
$$
\sectiona
3.2. Grammaire de Polya et et polyn\^omes
indicateurs de cycles
\endsection
Appelons 
 {\it grammaire de Polya} la grammaire suivante :
$$\displaylines{
G=\{x_1\rightarrow x_2,\quad x_2\rightarrow 2x_3,\quad x_3\rightarrow
3x_4 \ldots \cr
y_0\rightarrow y_1x_1,\quad y_1\rightarrow y_2x_1,\quad 
y_2\rightarrow y_3x_1 \ldots \}
}$$
On consid\`ere la suite $D^n(y_0)$ associ\'ee :
$$\eqalign{
D^0(y_0)&=y_0 \cr
D^1(y_0)&=y_1x_1 \cr
D^2(y_0)&=y_1x_2+y_2x_1^2 \cr
D^3(y_0)&=y_1(2x_3)+y_2(3x_1x_2)+y_3x_1^3 \cr
D^4(y_0)&=y_1(6x_4)+y_2(8x_1x_3+3x_2^2)+y_3(6x_1^2x_2)+y_4x_1^4 \cr
}$$
Les polyn\^omes obtenus sont les polyn\^omes indicateurs de cycles des
permutations, \'etudi\'es par Polya. Plus pr\'ecis\'ement, soit $\sigma $
une permutation de $[n]$, $c_i(\sigma )$ le nombre de cycles de $\sigma $ de
longueur $i$, et  $c(\sigma )$ le
nombre total de ses cycles. Alors on a : 
$$D^n(y_0)=\sum_{\sigma
\in\S_n}y_{c(\sigma )}x_1^{c_1(\sigma )}x_2^{c_2(\sigma )}\cdots
 x_n^{c_n(\sigma )}.$$
La d\'emonstration est la m\^eme que pour les partitions, \`a cela pr\`es
qu'il y a, non pas une, mais $i$ mani\`eres de prolonger une $\bar\sigma $
en une $\sigma $ en ins\'erant $n$ dans un cycle de longueur $i$ de
$\bar\sigma $, et qu'il faut donc remplacer une lettre $x_i$ de
$m(\bar\sigma )$ par $ix_{i+1}$ pour obtenir la somme de tous les $m(\sigma
)$ correspondant \`a ces prolongements.
\bigskip
{\bf 3.3. --- Equation $y'=f(y)$ et polyn\^ome des degr\'es des
sommets d'une arborescence croissante} \par\medskip
Dans ce paragraphe, on consid\`ere la grammaire suivante :
$$G=\{x_0\rightarrow x_1x_0,\quad x_1\rightarrow x_2x_0,\quad 
x_2\rightarrow x_3x_0,\quad x_3\rightarrow x_4x_0,\quad \ldots \}$$
Les d\'eriv\'ees successives de $x_0$ sont alors :
$$\eqalign{
D^0(x_0)&=x_0 \cr
D^1(x_0)&=x_0x_1 \cr
D^2(x_0)&=x_0x_1^2+x_0^2x_2\cr
D^3(x_0)&=x_0x_1^3+4x_0^2x_1x_2+x_0^3x_3 \cr
D^4(x_0)&=x_0x_1^4+11x_0^2x_1^2x_2+4x_0^3x_2^2+7x_0^3x_1x_3+x_0^4x_4 \cr
}$$
Pour cet exemple aussi nous allons d\'egager une interpr\'etation 
calculatoire et une interpr\'etation combinatoire.\par
Etant donn\'ee la s\'erie exponentielle
$$f(t)=x_0+x_1t+x_2{t^2\over 2!}+\cdots +x_n{t^n\over n!}+\cdots ,$$
on cherche la solution de l'\'equation diff\'erentielle
$$y'=f(y),\quad\quad y(0)=0.$$
$$y'=x_0+x_1y+x_2{y^2\over 2!}+\cdots +x_k{y^k\over k!}+\cdots
,\quad y(0)=0.$$
Alors cette solution est donn\'ee par la s\'erie
$$y=x_0t+x_0x_1{t^2\over 2!}+(x_0x_1^2+x_0^2x_2){t^3\over
3!}+\cdots +D^{n-1}(x_0){t^n\over n!}+ \cdots, $$
o\`u $D$ est la d\'erivation associ\'ee \`a la grammaire ci-dessus.

En effet, d\'erivons l'\'egalit\'e $y'(t)=f(y(t))$.
Notons  $f_k(t)$ la fonction $f^{(k)}(y(t))$, c'est-\`a-dire la
fonction obtenue en substituant $y(t)$ \`a $y$ dans $f^{(k)}(y)$.
On a donc $y'(t)=f(y(t))=f_0(t)$. En outre,
$$f'_k(t)={d\over
dt}f^{(k)}(y(t))=f_{k+1}(t)y'(t)=f_{k+1}(t)f_0(t)\quad\quad (k\geq 0).$$ Or
$y'(t)=f_0(t)$. Par induction sur $n$, on en d\'eduit que 
$y^{(n)}(t)=D^{n-1}(f_0(t))$, d'o\`u le r\'esultat en portant $t=0$, puisque
$f_0(0)=f(y(0))=f(0)=x_0.$
\par \medskip
Nous en venons \`a pr\'esent \`a l'interpr\'etation combinatoire.
A une application $f$ de
$\{1,2,\ldots, n\}$ dans $\{0,1,2,\ldots, n-1\}$ telle que pour tout $i$,
$f(i)<i$ correspond l'arborescence croissante obtenue en 
tra\c cant une ar\^ete orient\'ee croissante $j\rightarrow i$ chaque fois
que $i$ est ant\'ec\'edent de $j$ ($f(i)=j$). Contrairement au cas des
arbres d'Andr\'e, la multiplicit\'e d'un sommet, c'est-\`a-dire le nombre
de ses fils, n'est pas born\'ee (elle est, pour une arborescence de
taille $n$, comprise entre $0$ et $n$).  On
d\'esigne par $m_i(F)$ le nombre de sommets de $F$ de multiplicit\'e
\'egale \`a $i$.   Dans ces conditions, si l'on pose 
 $$E_n(x_0,x_1,\ldots
x_n)=\sum_{F\in F_n}x_0^{m_0(F)}x_1^{m_1(F)}\cdots x_n^{m_n(F)}$$
 alors ce polyn\^ome n'est autre que le polyn\^ome $D^n(x_0)$ ci-dessus. 
 En effet, on prolonge un arbre $G$ de
taille $n-1$ en un arbre $F$ de taille $n$ en cr\'eant une ar\^ete 
$s\rightarrow n$ \`a partir d'un sommet quelconque $s$ de $G$. Si ce sommet
$s$ est de multiplicit\'e $i$ dans $G$, il est repr\'esent\'e
dans le mon\^ome de $G$ par la lettre $x_i$, qu'il faut donc remplacer par
$x_{i+1}x_0$ pour obtenir le mon\^ome de $F$.\par
On trouve une autre d\'emonstration, bas\'ee essentiellement sur un
compos\'e partitionnel, dans [BLL], section 5 : on
 supprime le sommet $0$ et ses ar\^etes, on obtient alors une partition
de $[n]$ en blocs, et un arbre sur chaque bloc. Si $y$ est la s\'erie
\'enum\'eratrice compl\`ete, le coefficient de ${t^n\over n!}$ dans le
d\'eveloppement de $x_k{y^k\over k!}$ est le polyn\^ome \'enum\'erateur des
arbres de taille $n$ dans lesquels le sommet $0$ est de multiplicit\'e $k$. En
sommant sur $k$, on trouve l'\'egalit\'e entre d\'eveloppements de $f(y)$ et de
$y'$.\par \medskip
Remarquons que les exemples consid\'er\'es plus haut en $2.1$ et $2.3$
s'obtiennent comme cas particuliers. D'une part, on retrouve les
polyn\^omes eul\'eriens en faisant $x_1=x_2=x_3=\cdots$ :
$$E_n(x_0,x_1,x_1,x_1,\cdots)=A_n(x_0,x_1),$$ d'autre part on retrouve
les arbres d'Andr\'e en interdisant les multiplicit\'es $\geq 3$ : les
polyn\^omes d'Andr\'e homog\`enes  $$E_n(x_0,x_1,x_2,0,0,
\cdots)=E_n(x_0,x_1,x_2)$$ ont donc pour fonction g\'en\'eratrice la
solution de l'\'equation de Ricatti g\'en\'erale
 $$y'=x_0+x_1y+x_2{y^2\over
2!}\cdotp$$

\sectiona
3.4. Equation $y=f(xy)$, grammaire de Lagrange, polyn\^ome des degr\'es des
sommets d'une arborescence, ou des poids d'une fonction de parking
\endsection
Etant donn\'ee une s\'erie formelle de type exponentiel :
$$f(x)=a_0+a_1x+a_2{x^2/2!}+\cdots +a_n{x^n/n!}+\cdots,$$
on consid\`ere la solution $y$ de l'\'equation $y=f(xy)$ :
$$y=a_0+a_1xy+a_2{(xy)^2/2!}+\cdots +a_n{(xy)^n/n!}+\cdots .\leqno (1)$$
Cette \'equation implicite d\'efinit une s\'erie formelle $y$ unique, comme le
montre l'algorithme naturel suivant :
$$\eqalign{
y&=a_0+\cdots \cr 
y&=a_0+a_1x(a_0+\cdots)=a_0+a_0a_1x+\cdots \cr 
y&=a_0+a_1x(a_0+a_0a_1x+\cdots)+a_2{(x(a_0+\cdots))^2/2!}+\cdots \cr 
y&=a_0+a_0a_1x+(2a_0a_1^2+a_0^2a_2)\,{x^2/2!}+\cdots \cr
\cdots \cr
y&=a_0+a_0a_1x+(2a_0a_1^2+a_0^2a_2)\,{x^2/2!}+\cdots \cr
&\hskip 2 cm +P_n(a_0,a_1,\ldots, a_n)\, {x^n/n!}+\cdots \cr 
}$$
o\`u il appara\^\i t clairement, par r\'ecurrence sur 
$n$, que le coefficient de ${x^n/n!}$ est un
polyn\^ome $P_n$, homog\`ene de degr\'e $n+1$ dans les lettres $a_0$, $a_1$, $\cdots $ $a_n$. 
Nous n'expliciterons pas davantage cet algorithme de type ``recherche du point fixe", car
le calcul des polyn\^omes $P_n$ se complique tr\`es vite.\par
\medskip
Notre objectif est de trouver une grammaire $G$ sur l'alphabet des $a_i$ telle que
$$P_n=D(P_{n-1}),$$
ce qui donnera une r\'ecurrence beaucoup plus simple.

Pour cela, nous allons utiliser l'interpr\'etation combinatoire des polyn\^omes $P_n$, qui est
classique (plus pr\'ecis\'ement, elle d\'erive imm\'ediatement des classiques interpr\'etations
combinatoires de la formule d'inversion de Lagrange, cf. par exemple [BLL]).

 Soit $A$ une arborescence de racine $0$ et de $n$ ar\^etes, construite sur les
$n+1$ sommets $\{0,1,2,\ldots ,n\}$ (c'est-\`a-dire un arbre de Cayley enracin\'e en $0$).  On
note $\cal A_n$ l'ensemble de ces arborescences. \par
Tout sommet $i$ de $A$ ($0\leq i\leq n$) poss\`ede un degr\'e $d_i$ 
(degr\'e sortant), qui est le nombre d'ar\^etes issues de $i$. A
l'arborescence $A$, on associe le mon\^ome $m(A)$ d\'efini par
$$m(A)=a_{d_0}a_{d_1}a_{d_2}\cdots a_{d_n}.$$ 
{\it Exemple.---} Soit $n=9$. Consid\'erons
l'arborescence $A$ suivante :

$$\vbox{\halign{#&#&#&#&#&#&#&#&#\cr 
  &&&& 0 &&&& \cr 
 &&& $\swarrow$ && $\searrow$ &&& \cr 
&& 3 &&&& 9 && \cr 
&& $\downarrow$ &&& $\swarrow$ & $\downarrow$ & $\searrow$ & \cr 
&& 6             && 1  &&            4 && 7 \cr 
& $\swarrow$ && $\searrow$ &&&  && $\downarrow$ \cr 
2 &&&& 5 && && 8 \cr 
}}
$$

Il est clair que $d_0=2$, $d_1=0$, $d_2=0$, $d_3=1$, $\ldots,$ $d_9=3.$ Par suite,
$$m(A)=a_2a_0a_0a_1a_0a_0a_2a_1a_0a_3=a_0^5a_1^2a_2^2a_3.$$
Dans $m(A)$, la puissance de $a_0$ est le nombre de sommets pendants, la puissance de
$a_1$ est le nombre de sommets ayant un fils, etc. On a alors 
 $$P_n=\sum_{A\in \cal A_n}m(A).$$
Rappelons rapidement la d\'emonstration de ce r\'esultat. Posons :
$$y=\sum_{n\geq 0}\sum_{A\in \cal A_n}m(A).$$
On a alors
$$a_k{(xy)^k/k!}=\sum_{n\geq 0}\sum_{A\in \cal A_n;d_0=k}m(A).$$
En effet, une arborescence telle que $d_0=k$ se construit \`a partir d'une
partition de $[n]$ en $k$ blocs et d'une arborescence sur chacun de ces blocs, \`a quoi
l'on ajoute le sommet $0$ et les $k$ ar\^etes reliant $0$ aux racines respectives des $k$
arborescences.

En sommant sur $k$, on en d\'eduit que $y$ satisfait l'\'equation fonctionnelle $y=f(xy).$

A partir de l'interpr\'etation combinatoire, nous allons montrer que $y$ est \'egalement l'unique
solution de l'\'equation 
$$y'=y\, D_+(y),\quad y(0)=a_0, \leqno (2)$$
o\`u $D_+$ est l'op\'erateur diff\'erentiel associ\'e \`a la grammaire {\it d'augmentation}
$$\{a_0\rightarrow a_1,\quad a_1\rightarrow a_2,
\quad\ldots,\quad a_i\rightarrow a_{i+1},\quad \ldots \}.$$

Il est \'equivalent de montrer que la suite $P_n$ satisfait la r\'ecurrence de type
binomial :
$$P_{n+1}=\sum_{k=0}^n {n\choose k}D_+(P_k)\,P_{n-k},\quad\quad P_0=a_0.\leqno
(3)$$ \par
Nous appelons arborescence augment\'ee $(A,p\rightarrow)$ le couple form\'e d'une arborescence
$A$ et d'une ar\^ete pendante $(p\rightarrow)$ issue de l'un de ses sommets $p$ (pendante en
ce sens qu'elle n'aboutit pas \`a un sommet \'etiquet\'e). 
 Par suite, le degr\'e $d_p$ augmente de $1$ quand on passe \`a l'arborescence
augment\'ee. En consid\'erant tous les choix possibles de $p$, puis l'ensemble 
$\cal A_{k,\cdotp\rightarrow}$ 
de toutes les arborescences augment\'ees poss\'edant $(k+1)$ sommets et $(k+1)$ ar\^etes (dont
une pendante), on a :  
$$
D_+(m(A))=\sum_{p} m(A,p\rightarrow), 
\quad\quad\quad\quad D_+(P_k)=\sum_{(A,p\rightarrow)\in 
\cal A_{k,\cdotp\rightarrow}}
m(A,p\rightarrow)
$$

A pr\'esent, on partitionne de mani\`ere unique une arborescence $A$ de $\cal
A_{n+1}$ en deux composantes comme suit : 
on d\'esigne par $p$ le p\`ere du sommet $1,$ par $C$ la
sous-arborescence de $A$ de racine $1,$ et par
$(B,p\rightarrow)$ l'arborescence augment\'ee qui est le 
compl\'ementaire de $C$
dans $A$, de sorte qu'on a  
$$
m(A)=m(B,p\rightarrow)m(C).
$$
R\'eciproquement, on choisit dans l'ensemble $\{2,3,\ldots, n+1\}$ les $n-k$
sommets qui seront les descendants de $1$ , on leur ajoute $1$ et on construit une
arborescence $C$ de racine $1$ et de $n-k$ ar\^etes sur l'ensemble obtenu. Puis sur
l'ensemble compl\'ementaire dans $[0,n+1]$ on construit une arborescence augment\'ee
$(B,p\rightarrow)$ de racine $0$ et de $(k+1)$ ar\^etes (dont une pendante). 
En r\'eunissant
les deux, on obtient une arborescence $A$ de $\cal A_{n+1}$.

En sommant sur $k$, on d\'eduit la r\'ecurrence de type binomial $(3)$. Cette
r\'ecurrence repr\'esente un premier progr\`es dans la simplification des calculs
(par rapport \`a l'algorithme du point fixe). 

Nous allons \`a pr\'esent trouver une grammaire engendrant ces polyn\^omes. A cet effet, nous
d\'efinissons une suite de fonctions $(y_n)$  par la r\'ecurrence 
$$y_0=y,\quad
y_1=D_+(y_0),\quad \cdots \quad y_n=D_+(y_{n-1}).$$ 
L'op\'erateur diff\'erentiel $D_+$ op\'erant sur les variables
$a_i$, il commute avec la d\'erivation ordinaire par rapport \`a $x$, on a donc  
$$y'_0=y_0y_1, \quad y'_1=D_+(y'_0)=D_+(y_0y_1)=y_0y_2+y_1^2, \quad \cdots \quad 
y'_n=D_+(y'_{n-1}).$$ 
On voit que $y'_n$ est un polyn\^ome dans les $y_0$, $y_1$, ...
$y_{n+1},$ plus pr\'ecis\'ement, c'est, d'apr\`es la formule de Leibniz :
$$y'_n=D_+^n(y_0y_1)=\sum_{k=0}^n {n\choose k}y_ky_{p+1-k}.$$

A pr\'esent nous d\'efinissons comme suit la {\it grammaire de Lagrange} sur l'alphabet
des $a_i$ :
 $$\displaylines{
G=\{a_0\rightarrow a_0a_1,\quad a_1\rightarrow D_+(a_0a_1)=a_0a_2+a_1^2,
\ldots \cr
 a_n\rightarrow D_+^n(a_0a_1)=\sum_{k=0}^n {n\choose k}a_ka_{n+1-k},
\ldots\},
}$$
 et notons $D$ l'op\'erateur diff\'erentiel associ\'e \`a cette
grammaire autrement dit
$$D=(a_0a_1){\partial / \partial a_0}+(a_0a_2+a_1^2){\partial / \partial
a_1}+\cdots +\Biggl( \sum_{k=0}^n {n\choose k}a_ka_{n+1-k}\Biggr){\partial / \partial
a_n}+\cdots $$
 Nous allons montrer que $G$ est bien la grammaire que nous
recherchons, en ce sens qu'on a :
 $$P_n=D^n(a_0).$$

Pour cela, faisons op\'erer la grammaire de Lagrange sur les $y_i$ (\`a la
place des $a_i$), et v\'erifions que le calcul des d\'eriv\'ees successives de $y_0$ en fonction
des $y_i$ co\"\i ncide avec le calcul selon la grammaire $G$ des d\'eriv\'ees successives  de
 $y_0$ quand on consid\`ere ces d\'eriv\'ees comme des polyn\^omes dans les $y_i$, autrement dit : 
$$y_0^{(n)}=D(y_0^{(n-1)}),\quad\quad\quad \hbox{\rm d'o\`u}\quad y_0^{(n)}=D^n(y_0).$$

La v\'erification est imm\'ediate : on a bien $y'_0=y_0y_1=D(y_0),$
d'o\`u $y''_0=y_0y'_1+y'_0y_1=y_0D_+(y_0y_1)+(y_0y_1)y_1=D^2(y_0),$ et ainsi de
suite d'apr\`es l'identit\'e $y'_i=D_+^i(y_0y_1)$ montr\'ee ci-dessus.

En portant $x=0$ dans cette identit\'e, et en tenant compte de $y_n(0)=a_n,$ on
d\'eduit
$$
y^{(n)}(0)=P_n=D^n(a_0)\cqfd
$$ 
Les premi\`eres valeurs sont :
$$\eqalign{
P_0&=a_0 \cr 
P_1&=a_0a_1 \cr 
P_2&=(a_0a_1){\partial \over \partial a_0}(a_0a_1)+(a_0a_2+a_1^2){\partial \over
\partial a_1} (a_0a_1) \cr 
&=2a_0a_1^2+a_0^2a_2 \cr 
P_3&=(a_0a_1){\partial \over \partial a_0}(P_2)+
(a_0a_2+a_1^2){\partial \over \partial a_1}(P_2)+
(a_0a_3+3a_1a_2){\partial \over \partial a_2}(P_2)
\cr
&=(a_0a_1)(2a_1^2+2a_0a_2)+(a_0a_2+a_1^2)(4a_0a_1)+(a_0a_3+3a_1a_2)(a_0^2) \cr 
&=6a_0a_1^3+9a_0^2a_1a_2+a_0^3a_3 \cr
}$$
On trouve ensuite :
$$
P_4=24a_0a_1^4+72a_0^2a_1^2a_2+16a_0^3a_1a_3+12a_0^3a_2^2+a_0^4a_4,
\qquad\quad{\rm etc.}
$$ 

Donnons encore une interpr\'etation (ou une preuve) combinatoire du r\'esultat. $P_n$
d\'esigne \`a pr\'esent le polyn\^ome \'enum\'erateur, et nous allons montrer la r\'ecurrence :
$$P_n=D(P_{n-1}),\qquad P_0=a_0.
$$ 
Soit $A$ un \'el\'ement de $\cal A_n$. On d\'efinit sa
restriction $\bar A$, \'el\'ement de $\cal A_{n-1}$, de la mani\`ere suivante (on d\'esigne par $i$
le p\`ere de $n$) :\par 
$\bullet$ si $d_n=0$, le sommet $n$ est pendant, on le supprime ainsi que l'ar\^ete qui
conduit de $i$ \`a $n$. \par
$\bullet$ si $d_n>0,$ on supprime $n$ et ses fils deviennent fils de $i$. Dans l'exemple ci-dessus,
$1$, $4$ et $7$ deviennent fils de $0$, donc $\bar A$ est l'arborescence
$$
\vbox{\halign{#&#&#&#&#&#&#\cr 
  && 1 & $\leftarrow$ & 0 && \cr 
 &&& $\swarrow$ & $\downarrow$ & $\searrow$ & \cr 
&& 3 && 4 && 7  \cr 
&& $\downarrow$ &&& & $\downarrow$  \cr 
&& 6             &&  &&          8 \cr 
& $\swarrow$ && $\searrow$ &&&   \cr 
2 &&&& 5 &&   \cr 
}}
$$
R\'eciproquement, soit $B$ un \'el\'ement de $\cal A_{n-1}$. Pour prolonger $B$
en une arborescence $A$ \'el\'ement de $\cal A_n$ telle que $B=\bar A$, on doit
:\par \noindent
- choisir un sommet $i$ de $B$ qui devient le p\`ere de $n$ dans $A$. \par\noindent
- choisir une partie $K$ (\'eventuellement
vide) de l'ensemble des fils de $i$ dans $B$ qui deviennent les fils de $n$
dans $A$, les autres restant fils de $i$. \par 
Supposons que $i$ poss\`ede $p$ fils, donc il correspond dans $m(B)$ \`a une occurrence
de la lettre $a_p$. Si l'on choisit $K$ de cardinal $k$, ce qui peut se faire de 
${p\choose k}$ mani\`eres, alors dans $A$ le nouveau sommet $n$ poss\`ede $k$ fils et le
sommet $i$ poss\`ede $(p-k+1)$ fils, le mon\^ome $m(A)$ se d\'eduit donc de $m(B)$ en rempla\c cant
une lettre $a_p$ par un produit $a_ka_{p-k+1}$. L'ensemble des prolongements possibles
du sommet $i$ de degr\'e $p$ correspond donc sur la lettre qui le repr\'esente \`a la r\`egle de
substitution de la grammaire $G$ :
$$a_p\rightarrow \sum_{k=0}^n {p\choose k}a_ka_{p+1-k}.$$
 En consid\'erant l'ensemble des sommets $i$ possibles dans $B$, on en d\'eduit que $D(m(B))$
est la somme des mon\^omes $m(A)$, pour $A$ prolongeant $B$. En sommant sur toutes les
arborescences on obtient la r\'ecurrence caract\'erisant les polyn\^omes $P_n,$ la condition
initiale $P_0=a_0$ se v\'erifiant imm\'ediatement sur l'arborescence r\'eduite au sommet $0$, et
aussi $P_1=a_0a_1$ sur l'arbre $0\rightarrow 1.$
\medskip
{\it Exemple.---} L'arborescence $\bar A$ ci-dessus a pour mon\^ome $m(\bar
A)=a_0^5a_1^2a_2a_4$. Pour retrouver l'arborescence $A$ il faut choisir le sommet $0$, pour
lequel $p=4$, puis la partie $K=\{1,4,7\}$ de cardinal $k=3,$ ce qui revient \`a substituer \`a
$a_4$ le produit $a_3a_2,$ ce qui redonne bien $m(A).$ \par 
\medskip

Signalons encore une autre interpr\'etation combinatoire des polyn\^omes $P_n$, en termes de
fonctions de parking.
Rappelons [FR] [Fr] qu'une application $\varphi$ de $[n]$
dans $[n]$ est appel\'ee {\it fonction de parking} s'il existe une
permutation $\sigma$ de $S_n$ la majorant : 
$$\forall i\in [n], \quad\quad \varphi(i)\leq \sigma(i).$$ \par\noindent
On consid\`ere $\varphi$ comme un mot de
longueur $n$ sur l'alphabet $\{0,1,2,\ldots, n\}$ : 
$$ 
\varphi=\varphi(1)\varphi(2)\cdots \varphi(n).
$$
 Soit $0\leq j\leq n.$ On note $d_j$ la multiplicit\'e de $j$ dans $\varphi$,
c'est-\`a-dire le nombre d'occurrences de l'entier $j$  dans le mot $\varphi$, et
on fait correspondre \`a
$\varphi$ le mon\^ome dans les $a_i$ obtenu comme suit :
$$w(\varphi)=a_{d_0}a_{d_1}a_{d_2}\cdots a_{d_n}.
$$
Dans $w(\varphi)$, la puissance de $a_0$ est le nombre d'entiers de
$\{0,1,2,\ldots, n\}$ qui n'apparaissent pas dans $\varphi$, la puissance de
$a_1$ est le nombre d'entiers qui apparaissent une fois, etc. 
Comme la $0-$i\`eme ligne du graphe cart\'esien de $\varphi$ est toujours vide,
$d_0=0$, et $w(\varphi)$ contient toujours la lettre $a_0.$
\medskip 
{\it Exemple.---} $n=8$, $\varphi=14114218,$ 
$w(\varphi)=a_0a_4a_1a_0a_2a_0a_0a_0a_1=a_0^5a_1^2a_2a_4.$
\medskip
Dans ces conditions, on d\'esigne par $\Phi_n$ l'ensemble des 
fonctions de parking de longueur
$n$, et on a :  
$$
P_n=\sum_{\varphi\in \Phi_n}w(\varphi).
$$
  
Une preuve repose sur la bijection suivante (qui est l'une de celles existantes
[Fr]) entre ${\cal A}_n$  et
 $\Phi_n$. Soit $A$ un \'el\'ement de $\cal A_n$. Les fils de chaque sommet
sont rang\'es de gauche \`a droite dans l'ordre croissant. En outre, on d\'efinit
les {\it positions} des sommets de $1$ \`a $n+1$ quand on  d\'ecrit l'arbre dans
l'ordre pr\'efixe ({\it depth first}) en partant de la racine : $0$ est en
position $1$, puis le plus petit fils de $0$ est en position $2$, etc., le
dernier sommet atteint est un sommet pendant en position $n+1.$ La fonction
$pos$ est donc une bijection de $\{0,1,2,\ldots ,n\}$ sur $[n+1]$.\par On
d\'efinit alors $\varphi(i)$ comme {\it la position du p\`ere de $i$} (pour
$1\leq i\leq n$) :
$$\varphi(i)=pos \hbox{\it (p\`ere(i)).}
$$
Il est clair que $\varphi$ est une fonction de parking, car pour trouver la
permutation majorante il suffit de poser  $\sigma(i)=pos(i)-1,$ et on a bien
$\varphi(i)\leq \sigma(i)$. On montre
\'egalement que cette transformation $A\mapsto \varphi$ est une bijection. En
outre, il est clair qu'on a l'\'egalit\'e $m(A)=w(\varphi),$ d'o\`u le
r\'esultat.\par\noindent {\it Exemple.---} Soit $n=9$. Si $A$ est l'arbre pris
en exemple dans le paragraphe $2$, alors  $\varphi=631632681$ lui correspond par
cette bijection, et $\sigma=631742895$. On a
$w(\varphi)=m(A)=a_0^5a_1^2a_2^2a_3$. 

{\it Remarque.---} Lorsqu'on consid\`ere l'\'equation fonctionnelle 
$y=f(xy)$ dans le cas o\`u
$f$ est une s\'erie g\'en\'eratrice {\it ordinaire} (et non exponentielle), 
la solution est le
langage de Lukasiewicz (cf. par exemple [Co]).
 Les interpr\'etations combinatoires sont
analogues, on peut consid\'erer les arborescences ordonn\'ees 
d'une part (ou ``de Catalan",
dans lesquelles on impose par exemple que les fils de chaque sommet sont rang\'es dans
l'ordre croissant quand on tourne dans le sens trigonom\'etrique), les fonctions de parking
croissantes d'autre part (c'est-\`a-dire les fonctions sous-exc\'edantes croissantes), et
reprendre les m\^emes statistiques.

Le langage de Lukasiewicz est \'evidemment li\'e aux polyn\^omes $P_n$. Mais ses propri\'et\'es
 rel\`event essentiellement de la combinatoire alg\'ebrique du mono\"\i de libre (factorisations
de mots), il ne semble pas directement d\'efinissable par une grammaire et un op\'erateur
diff\'erentiel, sauf \`a faire le d\'etour par nos polyn\^omes $P_n.$

\bigskip
\ctitre
 Bibliographie
\endctitre

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

\ref         Ca
\auteur   Carlitz L.
\titre    A note on the Lagrange expansion formula
\nomrevue  Buletinul Institutului Politehnic din Ia\c si, Sec\c tia 1, Matematic\v a
\tome  17
\date   1971
\pages  39-44
\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         Co
\auteur   Cori R. (Lothaire)
\titre   Words and Trees in  ``Encyclopedia of Mathematics" 
\editeur  Addison Wesley   
\date   1983
\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         FR
\auteur   Foata D, Riordan J
\titre    Mappings of Acyclic and Parking Functions
\nomrevue  Aequationes mathematicae
\tome  10
\date   1974
\pages 10-22
\endref

\ref         FS
\auteur   Foata D, Sch\" utzenberger M.-P
\titre    Nombres d'Euler et permutations alternantes in ``A Survey
of Combinatorial Theory" (chapter 16) 
\editeur  J.N. Srivastava et als, eds  
\date   1973
\endref

\ref         Fr
\auteur   {Francon} J
\titre    Acyclic and Parking Functions
\nomrevue  J. of Combinatorial Theory
\tome  18
\date   1975
\pages 27-35
\endref

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

\ref         Ro
\auteur   Roselle
\titre    Permutations by number of rises and successions
\nomrevue Proc. Amer. Math. Soc. 
\tome  19
\date  1968 
\pages 8-16
\endref

\ref         W
\auteur  Wilf H.S
\titre     Generatingfunctionology
\editeur  Acad. Press
\date   1990
\endref 

 \bye