%%%%%%%%%%%%%%%%%%%%%
%% TeX plain file for the paper entitled
%% Le renouveau des mathematiques combinatoires
%% by Dominique Foata%%%%%%%%%%%%%%%%%%%%%
%% An output of 17  pages
%%%%%%%%%%%%%%%%%%%%%


\catcode'32=9
\magnification=1200

\voffset=1cm
\hoffset=0cm
\font\tenpc=cmcsc10

% Charge des fontes de 8 et 6 points :
\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

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

% Chargement des fontes AMS

\font\tengoth=eufm10
\font\tenbboard=msbm10
\font\eightgoth=eufm10 at 8pt
\font\eightbboard=msbm7 at 8pt
\font\sevengoth=eufm7
\font\sevenbboard=msbm7
\font\sixgoth=eufm7 at 6pt
\font\fivegoth=eufm7 at 5pt

\newfam\gothfam
\newfam\bboardfam

\catcode`\@=11

\def\raggedbottom{\topskip 10pt plus 36pt
\r@ggedbottomtrue}
\def\pc#1#2|{{\bigf@ntpc #1\penalty
\@MM\hskip\z@skip\smallf@ntpc #2}}

\def\tenpoint{%
  \textfont0=\tenrm \scriptfont0=\sevenrm \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\tenrm}%
  \textfont1=\teni \scriptfont1=\seveni \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\teni}%
  \textfont2=\tensy \scriptfont2=\sevensy \scriptscriptfont2=\fivesy
  \textfont\gothfam=\tengoth \scriptfont\gothfam=\sevengoth
  \scriptscriptfont\gothfam=\fivegoth
  \def\goth{\fam\gothfam\tengoth}%
  \textfont\bboardfam=\tenbboard \scriptfont\bboardfam=\sevenbboard
  \scriptscriptfont\bboardfam=\sevenbboard
  \def\bboard{\fam\bboardfam}%
  \textfont\itfam=\tenit
  \def\it{\fam\itfam\tenit}%
  \textfont\slfam=\tensl
  \def\sl{\fam\slfam\tensl}%
  \textfont\bffam=\tenbf \scriptfont\bffam=\sevenbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\tenbf}%
  \textfont\ttfam=\tentt
  \def\tt{\fam\ttfam\tentt}%
  \abovedisplayskip=12pt plus 3pt minus 9pt
  \abovedisplayshortskip=0pt plus 3pt
  \belowdisplayskip=12pt plus 3pt minus 9pt
  \belowdisplayshortskip=7pt plus 3pt minus 4pt
  \smallskipamount=3pt plus 1pt minus 1pt
  \medskipamount=6pt plus 2pt minus 2pt
  \bigskipamount=12pt plus 4pt minus 4pt
  \normalbaselineskip=12pt
  \setbox\strutbox=\hbox{\vrule height8.5pt depth3.5pt width0pt}%
  \let\bigf@ntpc=\tenrm \let\smallf@ntpc=\sevenrm
  \let\petcap=\tenpc
  \normalbaselines\rm}
\def\eightpoint{%
  \textfont0=\eightrm \scriptfont0=\sixrm \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\eightrm}%
  \textfont1=\eighti \scriptfont1=\sixi \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\eighti}%
  \textfont2=\eightsy \scriptfont2=\sixsy \scriptscriptfont2=\fivesy
  \textfont\gothfam=\eightgoth \scriptfont\gothfam=\sixgoth
  \scriptscriptfont\gothfam=\fivegoth
  \def\goth{\fam\gothfam\eightgoth}%
  \textfont\bboardfam=\eightbboard \scriptfont\bboardfam=\sevenbboard
  \scriptscriptfont\bboardfam=\sevenbboard
  \def\bboard{\fam\bboardfam}%
  \textfont\itfam=\eightit
  \def\it{\fam\itfam\eightit}%
  \textfont\slfam=\eightsl
  \def\sl{\fam\slfam\eightsl}%
  \textfont\bffam=\eightbf \scriptfont\bffam=\sixbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\eightbf}%
  \textfont\ttfam=\eighttt
  \def\tt{\fam\ttfam\eighttt}%
  \abovedisplayskip=9pt plus 2pt minus 6pt
  \abovedisplayshortskip=0pt plus 2pt
  \belowdisplayskip=9pt plus 2pt minus 6pt
  \belowdisplayshortskip=5pt plus 2pt minus 3pt
  \smallskipamount=2pt plus 1pt minus 1pt
  \medskipamount=4pt plus 2pt minus 1pt
  \bigskipamount=9pt plus 3pt minus 3pt
  \normalbaselineskip=9pt
  \setbox\strutbox=\hbox{\vrule height7pt depth2pt width0pt}%
  \let\bigf@ntpc=\eightrm \let\smallf@ntpc=\sixrm
  \normalbaselines\rm}

\let\bb=\bboard

\tenpoint

% dactylographie fran\c caise

\catcode`\;=\active
\def;{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font\kern -1.2 \fontdimen3 \font\fi\string;}

\catcode`\:=\active
\def:{\relax\ifhmode\ifdim\lastskip>\z@\unskip\fi\penalty\@M\ \fi\string:}

\catcode`\!=\active
\def!{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font \kern -1.1 \fontdimen3 \font\fi\string!}

\catcode`\?=\active
\def?{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font \kern -1.1 \fontdimen3 \font\fi\string?}

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

\frenchspacing

% format de sortie


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

\def\appeln@te{}
\def\vfootnote#1{\def\@parameter{#1}\insert\footins\bgroup\eightpoint
  \interlinepenalty\interfootnotelinepenalty
  \splittopskip\ht\strutbox % top baseline for broken footnotes
  \splitmaxdepth\dp\strutbox \floatingpenalty\@MM
  \leftskip\z@skip \rightskip\z@skip
  \ifx\appeln@te\@parameter\indent \else{\noindent #1\ }\fi
  \footstrut\futurelet\next\fo@t}

\pretolerance=500 \tolerance=1000 \brokenpenalty=5000
\newdimen\hmargehaute \hmargehaute=0cm
\newdimen\lpage \lpage=13.3cm
\newdimen\hpage \hpage=20cm
\newdimen\lmargeext \lmargeext=1cm
\hsize=11.25cm
\vsize=18cm
\parskip 0pt
\parindent=12pt

\def\margehaute{\vbox to \hmargehaute{\vss}}%
\def\margebasse{\vss}

\output{\shipout\vbox to \hpage{\margehaute\nointerlineskip
  \corpsdepage\margebasse}
  \advancepageno \global\pagetitrefalse
  \ifnum\outputpenalty>-20000 \else\dosupereject\fi}

\def\corpsdepage{\hbox to \lpage{\hss\pagetexte\hskip\lmargeext}}
\def\pagetexte{\vbox{\makeheadline\pagebody\makefootline}}
\headline={\ifpagetitre\titleheadline \else
  \ifodd\pageno\rightheadline \else\leftheadline\fi\fi}
\def\leftheadline{\eightpoint\hfil\the\auteurcourant\hfil}
\def\rightheadline{\eightpoint\hfil\the\titrecourant\hfil}
\def\titleheadline{\hfill}
\pagetitretrue

\def\footnoterule{\kern-6\p@
  \hrule width 2truein \kern 5.6\p@} % the \hrule is .4pt high



\let\rmpc=\sevenrm
\def\pd#1#2 {\pc#1#2| }

\def\pointir{\discretionary{.}{}{.\kern.35em---\kern.7em}\nobreak
\hskip 0em plus .3em minus .4em }

\def\resume#1{\vbox{\eightpoint \pc R\'ESUM\'E|\pointir #1}}
\def\abstract#1{\vbox{\eightpoint \pc ABSTRACT|\pointir #1}}

\def\titre#1|{\message{#1}
              \par\vskip 30pt plus 24pt minus 3pt\penalty -1000
              \vskip 0pt plus -24pt minus 3pt\penalty -1000
              \centerline{\bf #1}
              \vskip 5pt
              \penalty 10000 }

\def\section#1|{\par\vskip .3cm
                {\bf #1}\pointir}

\def\ssection#1|{\par\vskip .2cm
                {\it #1}\pointir}

\long\def\th#1|#2\finth{\par\medskip
              {\petcap #1\pointir}{\it #2}\par\smallskip}

\long\def\tha#1|#2\fintha{\par\medskip
                    {\petcap #1.}\par\nobreak{\it #2}\par\smallskip}
\def\cf{{\it cf}}

\def\rem#1|{\par\medskip
            {{\it #1}\pointir}}

\def\rema#1|{\par\medskip
             {{\it #1.}\par\nobreak }}

%
\def\ieme{\raise 1ex\hbox{\pc{}i\`eme|}}
\def\omini{\raise 1ex\hbox{\pc{}o|}}
\def\emini{\raise 1ex\hbox{\pc{}e|}}
\def\ermini{\raise 1ex\hbox{\pc{}er|}}
\def\remini{\raise 1ex\hbox{\pc{}re|}}

%reference pour un article :

\def\article#1|#2|#3|#4|#5|#6|#7|
    {{\leftskip=7mm\noindent
     \hangindent=2mm\hangafter=1
     \llap{[#1]\hskip.35em}{#2}\pointir
     #3, {\sl #4}, vol.\nobreak\ {\bf #5}, {\oldstyle #6},
     p.\nobreak\ #7.\par}}
%reference pour un livre :
\def\livre#1|#2|#3|#4|
    {{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
    \llap{[#1]\hskip.35em}{#2}\pointir
    {\sl #3}\pointir #4.\par}}
%reference complementaire :
\def\divers#1|#2|#3|
    {{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
     \llap{[#1]\hskip.35em}{#2}\pointir
     #3.\par}}
%
\mathchardef\conj="0365
\def\dem{\par{\it D\'emonstration}\pointir}
\def\qed{\quad\raise -2pt\hbox{\vrule\vbox to 10pt{\hrule width 4pt
\vfill\hrule}\vrule}}

\def\virg{\raise 2pt\hbox{,}}   % virgule apr\`es une fraction

\def\cqfd{\penalty 500 \hbox{\qed}\par\smallskip}

\long\def\entourer#1{\hbox{\vrule\vbox{\hrule\hbox{\kern15pt\vbox{\kern5pt
{#1}\kern5pt}\kern15pt}\hrule}\vrule}}
\def\\S {\vskip 5pt\hskip .5cm plus .1cm minus .1cm\relax}

%les differents retraits, voir aussi \item
\def\enonce#1|#2\finenonce{{\par\leftskip=36pt
\noindent\hbox to 0pt{\kern-\leftskip#1\hfill}{#2}\par}}

\def\senonce#1|#2\finsenonce{{\par\leftskip=36pt
\noindent\hbox to 0pt{\kern-24pt #1\hfill}{#2}\par}}

\def\ssenonce#1|#2\finssenonce{{\par\leftskip=48pt
\noindent\hbox to 0pt{\kern-24pt #1\hfill}{#2}\par}}

\def\decale#1|{\par\noindent\hskip 28pt\llap{#1}\kern 5pt}
\def\decaledecale#1|{\par\noindent\hskip 34pt\llap{#1}\kern 5pt}
% pour les titres en deux lignes et les sections sans point-tiret :
\def\titrea#1|#2|{\message{#1 #2}
  \par\vskip.5cm plus .1cm minus .1cm\penalty -1000
  \centerline{\bf #1}
  \centerline{\bf #2}
  \vskip 5pt
  \penalty 10000 }
\def\sectiona#1|{\par\vskip .3cm
  {\bf #1.}
  \par\nobreak\vskip 3pt }
\def\ssectiona#1|{\par\vskip .2cm
  {\it #1.}
  \par\nobreak\vskip 2pt }

\def\rest#1{\ifinner\setbox1=\hbox{$\textstyle{#1}$}
            \else\setbox1=\hbox{$\displaystyle{#1}$}\fi
            \dimen1=\ht1
            \advance\dimen1 by\dp1
            \divide\dimen1 by 2
            \box1\lower 2pt\hbox{$\left|\vbox to\dimen1{}\right.$}}


\def\matrice#1{\null \,\vcenter {\normalbaselines \m@th
\ialign {\hfil $##$\hfil &&\  \hfil $##$\hfil\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip } #1\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip }}}\,}

\def\petitematrice#1{\null \,\vcenter {\normalbaselines \m@th
\ialign {\hfil $##$\hfil &&\thinspace  \hfil $##$\hfil\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip } #1\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip }}}\,}


\catcode`\@=12

\def\Grille{\setbox13=\vbox to 5mm{\hrule width 110mm\vfill}
\setbox13=\vbox{\offinterlineskip
   \copy13\copy13\copy13\copy13\copy13\copy13\copy13\copy13
   \copy13\copy13\copy13\copy13\box13\hrule width 110mm}
\setbox14=\hbox to 5mm{\vrule height 65mm\hfill}
\setbox14=\hbox{\copy14\copy14\copy14\copy14\copy14\copy14
   \copy14\copy14\copy14\copy14\copy14\copy14\copy14\copy14
   \copy14\copy14\copy14\copy14\copy14\copy14\copy14\copy14\box14}
\ht14=0pt\dp14=0pt\wd14=0pt
\setbox13=\vbox to 0pt{\vss\box13\offinterlineskip\box14}
\wd13=0pt\box13}

\def\grille{\noalign{\nointerlineskip\Grille\nointerlineskip}}

%������������������������������������������������������������������

\def\fleche(#1,#2)\dir(#3,#4)\long#5{%
\noalign{\nointerlineskip\leftput(#1,#2){\vector(#3,#4){#5}}\nointerlineskip}}

%������������������������������������������������������������������

\def\diagram#1{\def\normalbaselines{\baselineskip=0pt\lineskip=5pt}
\matrix{#1}}

\def\hfl#1#2#3{\smash{\mathop{\hbox to#3{\rightarrowfill}}\limits
^{\scriptstyle#1}_{\scriptstyle#2}}}

\def\gfl#1#2#3{\smash{\mathop{\hbox to#3{\leftarrowfill}}\limits
^{\scriptstyle#1}_{\scriptstyle#2}}}

\def\vfl#1#2#3{\llap{$\scriptstyle #1$}
\left\downarrow\vbox to#3{}\right.\rlap{$\scriptstyle #2$}}

%������������������������������������������������������������������


 \message{`lline' & `vector' macros from LaTeX}
 \catcode`@=11
\def\{{\relax\ifmmode\lbrace\else$\lbrace$\fi}
\def\}{\relax\ifmmode\rbrace\else$\rbrace$\fi}
\def\newcount{\alloc@0\count\countdef\insc@unt}
\def\newdimen{\alloc@1\dimen\dimendef\insc@unt}
\def\newwrite{\alloc@7\write\chardef\sixt@@n}

\newwrite\@unused
\newcount\@tempcnta
\newcount\@tempcntb
\newdimen\@tempdima
\newdimen\@tempdimb
\newbox\@tempboxa

\def\@spaces{\space\space\space\space}
\def\@whilenoop#1{}
\def\@whiledim#1\do #2{\ifdim #1\relax#2\@iwhiledim{#1\relax#2}\fi}
\def\@iwhiledim#1{\ifdim #1\let\@nextwhile=\@iwhiledim
        \else\let\@nextwhile=\@whilenoop\fi\@nextwhile{#1}}
\def\@badlinearg{\@latexerr{Bad \string\line\space or \string\vector
   \space argument}}
\def\@latexerr#1#2{\begingroup
\edef\@tempc{#2}\expandafter\errhelp\expandafter{\@tempc}%
%% error help message pieces.
\def\@eha{Your command was ignored.
^^JType \space I <command> <return> \space to replace it
  with another command,^^Jor \space <return> \space to continue without it.}
\def\@ehb{You've lost some text. \space \@ehc}
\def\@ehc{Try typing \space <return>
  \space to proceed.^^JIf that doesn't work, type \space X <return> \space to
  quit.}
\def\@ehd{You're in trouble here.  \space\@ehc}

\typeout{LaTeX error. \space See LaTeX manual for explanation.^^J
 \space\@spaces\@spaces\@spaces Type \space H <return> \space for
 immediate help.}\errmessage{#1}\endgroup}
\def\typeout#1{{\let\protect\string\immediate\write\@unused{#1}}}

% line & circle fonts
\font\tenln    = line10
\font\tenlnw   = linew10
%\font\tencirc  = circle10
%\font\tencircw = circlew10


\newdimen\@wholewidth
\newdimen\@halfwidth
\newdimen\unitlength 

\unitlength =1pt

%\newbox\@picbox
%\newdimen\@picht

\def\thinlines{\let\@linefnt\tenln \let\@circlefnt\tencirc
  \@wholewidth\fontdimen8\tenln \@halfwidth .5\@wholewidth}
\def\thicklines{\let\@linefnt\tenlnw \let\@circlefnt\tencircw
  \@wholewidth\fontdimen8\tenlnw \@halfwidth .5\@wholewidth}

\def\linethickness#1{\@wholewidth #1\relax \@halfwidth .5\@wholewidth}



\newif\if@negarg

\def\lline(#1,#2)#3{\@xarg #1\relax \@yarg #2\relax
\@linelen=#3\unitlength
\ifnum\@xarg =0 \@vline
  \else \ifnum\@yarg =0 \@hline \else \@sline\fi
\fi}

\def\@sline{\ifnum\@xarg< 0 \@negargtrue \@xarg -\@xarg \@yyarg -\@yarg
  \else \@negargfalse \@yyarg \@yarg \fi
\ifnum \@yyarg >0 \@tempcnta\@yyarg \else \@tempcnta -\@yyarg \fi
\ifnum\@tempcnta>6 \@badlinearg\@tempcnta0 \fi
\setbox\@linechar\hbox{\@linefnt\@getlinechar(\@xarg,\@yyarg)}%
\ifnum \@yarg >0 \let\@upordown\raise \@clnht\z@
   \else\let\@upordown\lower \@clnht \ht\@linechar\fi
\@clnwd=\wd\@linechar
\if@negarg \hskip -\wd\@linechar \def\@tempa{\hskip -2\wd\@linechar}\else
     \let\@tempa\relax \fi
\@whiledim \@clnwd <\@linelen \do
  {\@upordown\@clnht\copy\@linechar
   \@tempa
   \advance\@clnht \ht\@linechar
   \advance\@clnwd \wd\@linechar}%
\advance\@clnht -\ht\@linechar
\advance\@clnwd -\wd\@linechar
\@tempdima\@linelen\advance\@tempdima -\@clnwd
\@tempdimb\@tempdima\advance\@tempdimb -\wd\@linechar
\if@negarg \hskip -\@tempdimb \else \hskip \@tempdimb \fi
\multiply\@tempdima \@m
\@tempcnta \@tempdima \@tempdima \wd\@linechar \divide\@tempcnta \@tempdima
\@tempdima \ht\@linechar \multiply\@tempdima \@tempcnta
\divide\@tempdima \@m
\advance\@clnht \@tempdima
\ifdim \@linelen <\wd\@linechar
   \hskip \wd\@linechar
  \else\@upordown\@clnht\copy\@linechar\fi}

%\def\@hline{\ifnum \@xarg <0 \hskip -\@linelen \fi
%\vrule \@height \@halfwidth \@depth \@halfwidth \@width
%\@linelen \ifnum \@xarg <0 \hskip -\@linelen \fi}


\def\@hline{\ifnum \@xarg <0 \hskip -\@linelen \fi
\vrule height \@halfwidth depth \@halfwidth width \@linelen
\ifnum \@xarg <0 \hskip -\@linelen \fi}

\def\@getlinechar(#1,#2){\@tempcnta#1\relax\multiply\@tempcnta 8
\advance\@tempcnta -9 \ifnum #2>0 \advance\@tempcnta #2\relax\else
\advance\@tempcnta -#2\relax\advance\@tempcnta 64 \fi
\char\@tempcnta}

\def\vector(#1,#2)#3{\@xarg #1\relax \@yarg #2\relax
\@linelen=#3\unitlength
\ifnum\@xarg =0 \@vvector
  \else \ifnum\@yarg =0 \@hvector \else \@svector\fi
\fi}

\def\@hvector{\@hline\hbox to 0pt{\@linefnt
\ifnum \@xarg <0 \@getlarrow(1,0)\hss\else
    \hss\@getrarrow(1,0)\fi}}

\def\@vvector{\ifnum \@yarg <0 \@downvector \else \@upvector \fi}

\def\@svector{\@sline
\@tempcnta\@yarg \ifnum\@tempcnta <0 \@tempcnta=-\@tempcnta\fi
\ifnum\@tempcnta <5
  \hskip -\wd\@linechar
  \@upordown\@clnht \hbox{\@linefnt  \if@negarg
  \@getlarrow(\@xarg,\@yyarg) \else \@getrarrow(\@xarg,\@yyarg) \fi}%
\else\@badlinearg\fi}

\def\@getlarrow(#1,#2){\ifnum #2 =\z@ \@tempcnta='33\else
\@tempcnta=#1\relax\multiply\@tempcnta \sixt@@n \advance\@tempcnta
-9 \@tempcntb=#2\relax\multiply\@tempcntb \tw@
\ifnum \@tempcntb >0 \advance\@tempcnta \@tempcntb\relax
\else\advance\@tempcnta -\@tempcntb\advance\@tempcnta 64
\fi\fi\char\@tempcnta}

\def\@getrarrow(#1,#2){\@tempcntb=#2\relax
\ifnum\@tempcntb < 0 \@tempcntb=-\@tempcntb\relax\fi
\ifcase \@tempcntb\relax \@tempcnta='55 \or
\ifnum #1<3 \@tempcnta=#1\relax\multiply\@tempcnta
24 \advance\@tempcnta -6 \else \ifnum #1=3 \@tempcnta=49
\else\@tempcnta=58 \fi\fi\or
\ifnum #1<3 \@tempcnta=#1\relax\multiply\@tempcnta
24 \advance\@tempcnta -3 \else \@tempcnta=51\fi\or
\@tempcnta=#1\relax\multiply\@tempcnta
\sixt@@n \advance\@tempcnta -\tw@ \else
\@tempcnta=#1\relax\multiply\@tempcnta
\sixt@@n \advance\@tempcnta 7 \fi\ifnum #2<0 \advance\@tempcnta 64 \fi
\char\@tempcnta}



\def\@vline{\ifnum \@yarg <0 \@downline \else \@upline\fi}


\def\@upline{\hbox to \z@{\hskip -\@halfwidth \vrule
  width \@wholewidth height \@linelen depth \z@\hss}}

\def\@downline{\hbox to \z@{\hskip -\@halfwidth \vrule
  width \@wholewidth height \z@ depth \@linelen \hss}}

\def\@upvector{\@upline\setbox\@tempboxa\hbox{\@linefnt\char'66}\raise
     \@linelen \hbox to\z@{\lower \ht\@tempboxa\box\@tempboxa\hss}}

\def\@downvector{\@downline\lower \@linelen
      \hbox to \z@{\@linefnt\char'77\hss}}

%INITIALIZATION
\thinlines

\newcount\@xarg
\newcount\@yarg
\newcount\@yyarg
\newcount\@multicnt
\newdimen\@xdim
\newdimen\@ydim
\newbox\@linechar
\newdimen\@linelen
\newdimen\@clnwd
\newdimen\@clnht
\newdimen\@dashdim
\newbox\@dashbox
\newcount\@dashcnt
 \catcode`@=12


% macros supplementaires (J.D.)

\newbox\tbox
\newbox\tboxa

\def\leftzer#1{\setbox\tbox=\hbox to 0pt{#1\hss}%
     \ht\tbox=0pt \dp\tbox=0pt \box\tbox}

\def\rightzer#1{\setbox\tbox=\hbox to 0pt{\hss #1}%
     \ht\tbox=0pt \dp\tbox=0pt \box\tbox}

\def\centerzer#1{\setbox\tbox=\hbox to 0pt{\hss #1\hss}%
     \ht\tbox=0pt \dp\tbox=0pt \box\tbox}

\def\leftput(#1,#2)#3{\setbox\tboxa=\hbox{%
    \kern #1\unitlength
    \raise #2\unitlength\hbox{\leftzer{#3}}}%
    \ht\tboxa=0pt \wd\tboxa=0pt \dp\tboxa=0pt\box\tboxa}

\def\rightput(#1,#2)#3{\setbox\tboxa=\hbox{%
    \kern #1\unitlength
    \raise #2\unitlength\hbox{\rightzer{#3}}}%
    \ht\tboxa=0pt \wd\tboxa=0pt \dp\tboxa=0pt\box\tboxa}

\def\centerput(#1,#2)#3{\setbox\tboxa=\hbox{%
    \kern #1\unitlength
    \raise #2\unitlength\hbox{\centerzer{#3}}}%
    \ht\tboxa=0pt \wd\tboxa=0pt \dp\tboxa=0pt\box\tboxa}

\unitlength=1mm

\let\cput=\centerput

\def\put(#1,#2)#3{\noalign{\nointerlineskip
                               \centerput(#1,#2){$#3$}
                                \nointerlineskip}}
\auteurcourant={DOMINIQUE FOATA}
\titrecourant={M\'ETHODE COMBINATOIRE POUR LES FONCTIONS SP\'ECIALES}

\raggedbottom
\noindent
{\eightrm JOURN\'EES
SUR LES M\'ETHODES
EN MATH\'EMATIQUES}

\noindent
Institut Henri Poincar\'e, Paris

\noindent
2--3 avril 2003




\bigskip\bigskip\bigskip
\centerline{\sl UNE M\'ETHODE COMBINATOIRE POUR}
\smallskip
\centerline{\sl L'\'ETUDE DES FONCTIONS SP\'ECIALES}

\bigskip
  
\centerline{Dominique FOATA\footnote{}{\kern-11pt 1980 {\it Mathematics
Subject Classification}, Primary 05A15; Secondary 33A65.\hfil\break
{\it Key words and phrases}. Compos\'e partitionnel, exponential formula,
Hermite polynomials, Mehler formula, involutionary graphs.\hfil\break
{\it Mots cl\'es}. Compos\'e partitionnel, formule exponentielle,
polyn\^omes d'Hermite, formule de Mehler, graphes involutionnaires.}}
\centerline{(Strasbourg)}

\bigskip\bigskip
{\narrower
\resume{La m\'ethode du compos\'e partitionnel, introduite en
math\'ema\-tiques combinatoires dans les ann\'ees soixante-dix, a permis
d'\'etablir de nombreuses identit\'es classiques sur les fonctions
sp\'eciales. On d\'ecrit ici  cette m\'ethode et l'on montre comment elle
s'est \'ecart\'ee radicalement des m\'ethodes utilis\'ees jusque l\`a en
analyse.}

\bigskip
\abstract{The  ``compos\'e partitionnel" method that was introduced in
Combinatorial Mathematics in the seventies was used to derive
several classical identities on Special Functions. It is shown how the
method, which is further described below, has moved away altogether
from the other methods traditionally used in analysis.}

}
\bigskip


Au cours des ces journ\'ees, Michel Serfati nous a aimablement demand\'e 
de mettre en lumi\`ere les m\'ethodes qui nous paraissent essentielles
dans le d\'eveloppement pr\'esent de notre propre sp\'ecialit\'e math\'ematique.
Vaste programme pour la Combinatoire ! Donner, en effet, un aper\c cu de toutes
les m\'ethodes mises au point dans cette discipline aujourd'hui serait une
t\^ache impossible, tant formidable a \'et\'e son essor dans la seconde moiti\'e
du vingti\`eme  si\`ecle. 

Pour mesurer cette explosion, je me suis tourn\'e vers le serveur
{\sl Math\-Science} de la Soci\'et\'e Am\'ericaine de Math\'ematique et retenu les
noms des revues mentionnant le nom ``Combinatorics" ou celui de ``Discrete". Les
premi\`eres revues sp\'ecialis\'ees dans ce domaine (comme dans les autres
domaines des math\'ematiques) sont apparues au milieu des ann\'ees
\hbox{soixante.} Auparavant, les math\'ematiciens publiaient dans des revues,
dites g\'en\'eralistes, essentiellement \'edit\'ees par les soci\'et\'es
math\'ematiques des diff\'erents pays.

Le tableau de la Fig.~1 reproduit, pour chaque ann\'ee, le nombre
de revues sp\'ecialis\'ees en combinatoire. La courbe montrant cette
explosion est encore plus parlante. On constate que le ph\'enom\`ene
explosif est encore dans sa phase ascendante. On devrait tout de
m\^eme atteindre prochainement le point d'inflexion, les ph\'enom\`enes
humains, souvent exponentiels \`a leurs d\'ebuts,  suivent \`a leur
maturit\'e une courbe logistique. L'\'edition des revues sp\'ecialis\'ees n'y
\'echappera pas.

Notons que les deux premi\`eres revues de combinatoire qui sont apparues, \`a
savoir en 1966, sont  le {\it Journal of Combinatorial Theory. Series A 
et Series B}, lorsque la soci\'et\'e {\it Academic Press} a \'edit\'e les revues
aujourd'hui bien connues, comme le {\it Journal of Algebra}, le {\it Journal of
Number Theory},~\dots 

\midinsert

$$
\vbox{\halign{\vrule\ \hfil$#$\hfil\ \vrule&&\strut\ \hfil$#$\hfil
\ \vrule\cr
\noalign{\hrule}
\hbox{ann\'ee}&1966&1976&1986&1996&2002\cr
\noalign{\hrule}
\hbox{No. revues Combin.}&2&5&15&27&41\cr
\noalign{\hrule}
\cr
}}     
 $$

\centerline{Nombre de revues de Combinatoire publi\'ees}

\bigskip\bigskip

\def\fleche(#1,#2)\dir(#3,#4)\long#5{%
{\leftput(#1,#2){\vector(#3,#4){#5}}}}

\def\segment(#1,#2)\dir(#3,#4)\long#5{%
\leftput(#1,#2){\lline(#3,#4){#5}}}

\vglue 4cm

{\eightpoint

\centerline{\vbox{\vbox{\vskip 28mm
\offinterlineskip
\fleche(0,0)\dir(1,0)\long{80}
\centerput(10,-3){\sevenrm 1970}
\centerput(20,-3){\sevenrm 1975}
\centerput(30,-3){\sevenrm 1980}
\centerput(40,-3){\sevenrm 1985}
\centerput(50,-3){\sevenrm 1990}
\centerput(60,-3){\sevenrm 1995}
\centerput(70,-3){\sevenrm 2000}
\centerput(10,0){\vrule height1pt depth 1pt width .5pt}
\centerput(20,0){\vrule height 1pt depth 1pt width .5pt}
\centerput(30,0){\vrule height 1pt depth 1pt width .5pt}
\centerput(40,0){\vrule height 1pt depth 1pt width .5pt}
\centerput(50,0){\vrule height 1pt depth 1pt width .5pt}
\centerput(60,0){\vrule height 1pt depth 1pt width .5pt}
\centerput(70,0){\vrule height 1pt depth 1pt width .5pt}
\centerput(0,15){\vrule height.5pt depth 0pt width 2pt}
\centerput(0,30){\vrule height.5pt depth 0pt width 2pt}
\centerput(0,45){\vrule height.5pt depth 0pt width 2pt}
\centerput(0,60){\vrule height.5pt depth 0pt width 2pt}
\centerput(-3,15){\sevenrm 10}
\centerput(-3,30){\sevenrm 20}
\centerput(-3,45){\sevenrm 30}
\centerput(-3,60){\sevenrm 40}
\fleche(0,0)\dir(0,1)\long{70}
\segment(2,3)\dir(4,1)\long{20}
\segment(22,8)\dir(4,3)\long{20}
\segment(42,23)\dir(6,5)\long{20}
\segment(62,39.7)\dir(1,2)\long{12}
}}\hskip8cm}

}
\vskip.5cm
\centerline{Fig. 1}

\endinsert

Dresser donc le catalogue des m\'ethodes est une t\^ache impossible. On peut,
\`a la rigueur, comme l'avait fait magistralement le regrett\'e Gian-Carlo Rota
[Ro96], faire le point sur l'\'etat actuel de la discipline. Pour s'en tenir aux
m\'ethodes, qu'il faut bien d\'ecrire avec quelques d\'etails, on est amen\'e \`a
faire un choix, forc\'ement r\'educteur et partial. C'est ce que je me
propose de faire. Je vais ainsi parler d'une technique combinatoire,
popularis\'ee dans les ann\'ees 70-80, qui a r\'evolutionn\'e la mani\`ere
d'\'etablir de nombreuses identit\'es sur les fonctions sp\'eciales et
montrer comment cette approche s'\'ecarte fondamentalement des m\'ethodes {\it
classiques} utilis\'ees en analyse.

Les polyn\^omes orthogonaux hyperg\'eom\'etriques (Hermite, Laguerre, Jacobi,
Meixner, \dots\thinspace), tout particuli\`erement, satisfont des identit\'es dites
remarquables, qui sont indispensables \`a l'analyste.  Pour d\'emontrer ces
identit\'es, on utilise les techniques classiques de l'analyse
complexe, repr\'e\-sentation int\'egrale, manipulation des s\'eries, \dots~, en
faisant appel \`a des formules closes d'int\'egrales ou de sommation des s\'eries.
Le fait d'obtenir au bout d'un calcul, m\^eme \'el\'egant, une expression
close,  tient souvent du miracle. Anticipons sur ce qui va suivre et invitons le
lecteur \`a regarder l'identit\'e (1.5), dite de Mehler, qui donne une expression
``close" pour la s\'erie exponentielle des produits de deux polyn\^omes
d'Hermite. Si l'on prend le produit de trois polyn\^omes, plus aucune formule
manipulable ne peut \^etre obtenue, mais si l'on prend un produit bien
particulier (voir (1.6)), la sommation est possible, comme nous allons l'expliquer.

L'approche combinatoire se veut justement de donner une explication \`a ce
miracle. En effet, les fonctionnelles de ces
polyn\^omes classiques sont tr\`es particuli\`eres, ou ``sp\'eciales" et les
polyn\^omes ont des coefficients rationnels, souvent m\^eme {\it entiers} et
mieux encore {\it entiers positifs}. Si on fait appara\^\i tre ces
coefficients comme des {\it compteurs} ou des valeurs prises par des
statistiques d\'efinies sur des {\it structures discr\`etes}, ayant de bonnes
propri\'et\'es g\'eom\'etriques, il s'agit d'utiliser cette g\'eom\'etrie pour
montrer que les deux membres de l'identit\'e sont simplement deux comptages
obtenus par deux voies diff\'erentes. L'identit\'e est alors une banale
cons\'equence de cette \'etude g\'eom\'etrique.

Si le mod\`ele trouv\'e pour ces structures discr\`etes est
suffisamment riche, il fournit aussi des {\it extensions}, que les ana\-lystes
\`a leur tour sont susceptibles d'utiliser. Mon but est d'illustrer cette
d\'emarche avec l'\'etude des polyn\^omes d'Hermite et de certaines identit\'es
les concernant. 

Dans le prochain paragraphe, on trouve les \'el\'ements de base sur les
polyn\^omes d'Hermite, ainsi que les deux identit\'es qui sont \'etudi\'ees plus
particuli\`erement, celle de Mehler et son extension multilin\'eaire. Au
paragraphe~2, est donn\'e un aper\c cu sur les m\'ethodes utilis\'ees en {\it
analyse} pour \'etablir l'identit\'e de Mehler. 

Avec les paragraphes suivants, on entre dans l'\'etude combinatoire. On v\'erifie,
tout d'abord, que les polyn\^omes d'Hermite sont les fonctions g\'en\'eratrices
des involutions des intervalles $[\,n\,]=\{1,2,\ldots, n\}$ par un certain poids.
On constate, ensuite, que la formule de Mehler et son extension multilin\'eaire
sont de la forme $a=\exp b$, o\`u~$a$ et~$b$ sont des s\'eries.  Il s'agit
alors, lorsque~$b$ est interpr\'et\'ee comme la fonction g\'en\'eratrice de
certaines structures, de montrer que~$a$ est la fonction g\'en\'eratrice
d'autres structures li\'ees aux pr\'ec\'edentes. Une \'etude combinatoire de
l'identit\'e exponentielle $a=\exp b$ est ainsi n\'ecessaire ; elle est faite au
paragraphe~4. On donne ensuite la d\'emonstration combinatoire de la formule
de Mehler. Cette approche combinatoire sugg\`ere une extension multilin\'eaire
naturelle trait\'ee au paragraphe~6. Nous terminons par quelques remarques et
r\'ef\'erences.

L'esquisse des d\'emonstrations analytiques donn\'ees au paragraphe~2 peut
laisser croire que celles-ci sont concises. C'est vrai, pour la plupart. N'oublions
pas, cependant, qu'elles reposent sur tout un savoir-faire ant\'erieur, qui fait
partie de la culture du math\'ematicien. Si cette culture englobait aussi les
aspects combinatoires sur les comptages de permutations et sur l'identit\'e
exponentielle, la d\'emonstration de la formule de Mehler (1.5) donn\'ee ici 
serait absorb\'ee par tout auditoire \`a l'aide de deux transparents superpos\'es !
Force est donc de donner des \'el\'ements de base, comme fait dans les
paragraphes~3 et~4, mais ceux-ci prennent de la place !

\bigskip 
\centerline {\bf 1. Les polyn\^omes d'Hermite}

\medskip
Ces polyn\^omes, not\'es $(H_n(x))$ $(n\ge 0)$, qui sont orthogonaux par
rapport \`a la fonctionnelle $e^{-x^2/2}$ sur $]-\infty,+\infty[$, peuvent
\^etre d\'efinis \`a l'aide de leur fonction g\'en\'eratrice exponentielle
$$
\sum_{n\ge 0} {u^n\over n!}H_n(x)=\exp\Bigl(ux-{u^2\over 2}\Bigr).\leqno(1.1)
$$
Notons que l'autre normalisation prise pour les polyn\^omes d'Hermite consiste
\`a prendre le d\'eveloppement de $\exp(2xu-u^2)$ ; voir, par exemple [Er53,
p.~194, Le72, p.~60, Ra60, p.~187, Sz39, p.~105]. La pr\'esente normalisation,
popularis\'ee par Jackson [Ja41], se pr\^ete plus commod\'ement \`a un
traitement combinatoire.

D\'eveloppons l'exponentielle du membre de droite de (1.1) et cherchons le
coefficient de $u^n/n!$ dans les deux membres. On obtient alors l'expression
sui\-vante pour les polyn\^omes d'Hermite :
$$
H_n(x)=\sum_{0\le 2k\le n}
(-1)^k\,x^{n-2k} {n!\over 1^{n-2k}\,(n-2k)!\,2^k\,k!}.\leqno(1.2)
$$
Les premi\`eres valeurs sont ainsi : $H_0(x)=1$ ;\  $H_1(x)=x$ ;\ 
$H_2(x)=x^2-1$ ;\quad $H_3(x)=x^3-3x$ ;\quad
$H_4(x)=x^4-6x+3$ ;\quad $H_5(x)=x^5-10x^3+15x$.

Notons encore, voir par exemple, [Le72, p.~60 et 63], que l'on peut d\'eduire de
(1.1) la formule dite de Rodrigues
$$
H_n(x)=(-1)^n e^{x^2/2} {d^n\over dx^n}\,e^{-x^2/2},\leqno(1.3)
$$
d'ailleurs prise souvent comme d\'efinition des polyn\^omes d'Hermite. Enfin, par
d\'erivations successives de l'int\'egrale
$$
\int_0^{+\infty}e^{-u^2/2}\cos ux\,du=\sqrt{\pi\over 2}e^{-x^2/2},
$$
on obtient la {\it forme int\'egrale} des polyn\^omes d'Hermite
$$
H_n(x)={(-i)^n e^{x^2/2}\over \sqrt{2\pi}}
\int_{-\infty}^{+\infty} e^{-(u^2/2)+i\,ux}u^n\,du,\leqno(1.4)
$$
utile, comme pour beaucoup de fonctions sp\'eciales, dans de nombreux calculs
analytiques. Nous en verrons un exemple plus loin.

La formule bilin\'eaire de Mehler
$$
\sum_{n\ge 0}{u^n\over n!}\,H_n(x)\,H_n(y)
=(1-u^2)^{-1/2}\,
\exp\Bigl({2uxy-u^2(x^2+y^2)\over 2(1-u^2)}\Bigr),\leqno(1.5)
$$
dont la d\'emonstration fera l'objet d'une comparaison entre analyse et
combinatoire, a servi \`a \'etablir que l'analogue du noyau de Poisson (\cf.
[As70]) des polyn\^omes d'Hermite est positif, c'est-\`a-dire
$$
\sum_{n\ge 0}{u^n\over n!}\,H_n(x)\,H_n(y)\ge 0,
$$
quelles que soient les valeurs de $u$, $x$, $y$. 

Cette comparaison s'\'etendra aussi \`a 
l'{\it extension multilin\'eaire} 
$$
\displaylines{
(1.6)\quad
\sum_{(\nu_{i,j})}{\prod\limits_{i<j}\rho_{i,j}^{\nu_{i,j}}
\over \prod\limits_{i<j}\nu_{i,j}!}
H_{s_1}(x_1)\cdots H_{s_m}(x_m)\hfill\cr
\noalign{\vskip-12pt}
\hfill{}=
(\det \rho)^{-1/2}\,
\exp\Bigl(-{1\over 2}\sum_{i,j}
\bigl(\rho^-_{i,j}-\delta_{i,j}\bigr)x_ix_j\Bigr),\quad\cr}
$$
dont les ingr\'edients sont les suivants : d'abord, $m\ge 2$ est un entier
fix\'e, puis $x_1$, $x_2$, \dots~, $x_m$ sont $m$ variables
commutatives et $\rho=(\rho_{i,j})$ $(1\le i,j\le m)$ est une matrice
{\it sym\'etrique} de variables commutatives telle que $\rho_{i,i}=1$
$(1\le i\le m)$ ; soit  $\rho^{-1}=(\rho^-_{i,j})$ la matrice inverse
de~$\rho$. La sommation est alors sur toutes les matrices sym\'etriques
$(\nu_{i,j})\ (1\le i,j\le m,\,i\not=j)$, \`a coefficients entiers positifs et enfin 
$s_j:=\sum\limits_{1\le i\le m,\,i\not=j}\nu_{i,j}$ $(1\le j\le m)$.

\goodbreak
\bigskip
\centerline{\bf 2. Les d\'emonstrations analytiques}

\medskip
Pour la formule de Mehler (1.5), il y a d'abord les d\'emonstrations, di\-sons
\'elementaires, o\`u l'on d\'eveloppe les deux membres de l'identit\'e en s\'erie
et o\`u on utilise les formules classiques de sommation des s\'eries, comme
l'identit\'e de Pfaff-Saalsch\"utz. [On doit \`a Askey [As75a] d'avoir
signal\'e que cette identit\'e se trouve d\'ej\`a d\'emontr\'ee dans un
m\'emoire de Pfaff [Pf97], ant\'erieur de 93 ans \`a l'article de Saalsch\"utz
[Sa90] auquel on se r\'ef\`ere habituellement.] C'est l'une des d\'emonstrations
propos\'ees par Watson [Wa33]. Une d\'emonstration encore plus
\'el\'ementaire est obtenue par Rainville [Ra60, p. 196--198], qui n'utilise
effectivement que les formules (1.1) et (1.2), en faisant des sommations
appropri\'ees. 

Mentionnons aussi le principe de sp\'ecialisation, qui consiste \`a prendre une
formule bilin\'eaire sur les polyn\^omes de Laguerre, appel\'ee {\it
identit\'e de Hille-Hardy} (voir [Er53], formule~(20), p.~189) et \`a la
particulariser pour les polyn\^omes d'Hermite, ceux-ci \'etant des
sp\'ecialisations des pr\'ec\'edents. C'est la premi\`ere d\'emonstration de
Watson [Wa33] et celle conseill\'ee par Szeg\"o (voir [Sz39], Ex.~23,
p.~380).

Les autres d\'emonstrations, en dehors de l'approche originale d'Erd\'elyi
[Er39], utilisent la forme int\'egrale~(1.4). Cette m\'ethode est d\'ej\`a
implicite chez Mehler [Me66, p. 173--174]. On la trouve dans [Wa33] et
[Le72, p.~63--64].
On part du membre de gauche de (1.5) et on exprime les polyn\^omes d'Hermite
\`a l'aide de (1.4), soit
$$\displaylines{\quad
\sum_{n\ge 0}{t^n\over n!}\,H_n(x)\,H_n(y)\hfill\cr
\hfill{}
={e^{x^2/2+y^2/2}\over 2\pi}\sum_{n\ge 0}{(-1)^n\over n!}t^n
\int_{-\infty}^{+\infty}\!\!\int_{-\infty}^{+\infty}
e^{u^2/2-v^2/2+iux+ivy}\,(uv)^n\,du\,dv.\cr}
$$
Tout en justifiant la permutation des signes de sommation et d'int\'egrale, le
membre de droite devient :
$$
{e^{x^2/2+y^2/2}\over 2\pi}
\int_{-\infty}^{+\infty}\!\!\int_{-\infty}^{+\infty}
e^{u^2/2-v^2/2+iux+ivy-uvt}\,du\,dv.
$$
On calcule l'int\'egrale par it\'eration, en utilisant la formule (close!)
$$
\int_{-\infty}^{+\infty}e^{-a^2u^2/2-bu}\,du={\sqrt{2\pi}\over a}
e^{b^2/(2a^2)}
$$
et l'on obtient le membre de droite de (1.4).

\bigskip
\centerline{\bf 3. Involutions}

\nobreak
\medskip
Comme il est bien connu ou rapidement v\'erifi\'e
(voir, par exemple, [Ri58, p.~67]), le nombre de permutations de l'intervalle
$[\,n\,]=\{1,2,\ldots, n\}$ ayant exactement $k_1$ cycles de longueur~1 (dits
{\it points fixes}),
$k_2$ cycles de longueur~2 (dits {\it transpositions}), $k_3$ cycles de
longueur~3,
\dots~, $k_n$ cycles de longueur~$n$, les entiers~$k_i$ satisfaisant $1\cdot
k_1+2\cdot k_2+3\cdot k_3+\cdots +n\cdot k_n=n$, est \'egal \`a
$$
C(k_1,k_2,k_3,\cdots,k_n)={n!\over 1^{k_1}k_1!\,2^{k_2}k_2!\,3^{k_3}k_3!\,
\ldots\, n^{k_n}k_n!}.
$$
On reconna\^\i t, dans la fraction apparaissant dans le membre de droite de
l'identit\'e~(1.2) le coefficient $C(n-2k,k,0,\ldots,0)$ ($0\le 2k\le n$),
c'est-\`a-dire, le nombre d'{\it involutions} de l'intervalle
$[\,n\,]=\{1,2,\ldots, n\}$ ayant exactement~$k$
{\it transpositions} et $(n-2k)$ {\it points fixes} (et donc aucun cycle d'ordre
sup\'erieur).

\def\Inv{\mathop{\rm Inv}\nolimits}
\def\Invc{\mathop{\rm Invc}\nolimits}
\def\trans{\mathop{\rm trans}\nolimits}
\def\fix{\mathop{\rm fix}\nolimits}

Soit alors $\Inv_n$ l'ensemble de toutes les involutions de $[\,n\,]$. Pour tout
$\sigma\in \Inv_n$, notons $\trans(\sigma)$ et $\fix(\sigma)$ le
nombre des transpositions et des points fixes de~$\sigma$, respectivement
et posons
$$\leqalignno{
\mu(\sigma)&:=(-1)^{\trans (\sigma)}\,x^{\fix(\sigma)}.&(3.1)\cr
\noalign{\hbox{La formule~(1.2) peut encore s'\'ecrire :}}
H_n(x)&=\mu\{\Inv_n\}:=\sum_{\sigma\in\Inv_n} \mu(\sigma).&(3.2)\cr
\noalign{\vskip-10pt}}
$$
En d'autres termes, le polyn\^ome d'Hermite $H_n(x)$ peut \^etre vu comme la
{\it fonction g\'en\'eratrice} de l'ensemble $\Inv_n$ suivant le nombre de
points fixes et de transpositions, c'est-\`a-dire la fonction g\'en\'eratrice des
involutions~$\sigma$ de $[\,n\,]$ par le {\it poids} 
$\mu(\sigma)=(-1)^{\trans\sigma}\,x^{\fix\sigma}$. 

Identifions chaque involution $\sigma$ de l'intervalle $[\,n\,]$ \`a son graphe,
ayant~$n$ sommets \'etiquet\'es $1,2,\ldots,n$. Les seules {\it composantes
connexes} du graphe sont les boucles, de poids~$x$, ou les cycles de longueur~2,
de poids ${}-1$, comme montr\'e dans la Fig.~2.

\midinsert
\def\fleche(#1,#2)\dir(#3,#4)\long#5{%
{\leftput(#1,#2){\vector(#3,#4){#5}}}}

\def\segment(#1,#2)\dir(#3,#4)\long#5{%
\leftput(#1,#2){\lline(#3,#4){#5}}}

\def\boucleagauched{%
\centerline{\vbox{\vbox{\vskip 5mm
\offinterlineskip
\segment(0,3)\dir(-1,0)\long{3}
\segment(0,0)\dir(-1,0)\long{3}
\segment(-3,0)\dir(0,1)\long{3}
\fleche(0,0)\dir(0,1)\long{2.5}
}}}}

$$
\centerput(3,-1){\boucleagauched}
\centerput(4,3){$i$}
\centerput(3.5,1){$\bullet$}
\hskip 2cm
\fleche(2,1)\dir(1,0)\long{4}
\fleche(6,0)\dir(-1,0)\long{4}
\centerput(1,-0.5){$\bullet$}
\centerput(7,-0.5){$\bullet$}
\centerput(1,3){$j$}
\centerput(7,3){$k$}\hskip1cm
$$

\centerline{Fig. 2}
\endinsert

\def\fleche(#1,#2)\dir(#3,#4)\long#5{%
{\leftput(#1,#2){\vector(#3,#4){#5}}}}

\def\segment(#1,#2)\dir(#3,#4)\long#5{%
\leftput(#1,#2){\lline(#3,#4){#5}}}

\def\boucleagauched{%
\centerline{\vbox{\vbox{\vskip 5mm
\offinterlineskip
\segment(0,3)\dir(-1,0)\long{3}
\segment(0,0)\dir(-1,0)\long{3}
\segment(-3,0)\dir(0,1)\long{3}
\fleche(0,0)\dir(0,1)\long{2.5}
}}}}

L'identit\'e (1.1) peut donc se r\'ecrire :
$$
\sum_{n\ge 0} \mu\{\Inv_n\}{u^n\over n!}
=\exp\biggl(\mu(\,\centerput(3,-1){\boucleagauched}
\centerput(3.5,1){$\bullet$}
\centerput(5,1){$1$}\kern17pt )
+{1\over 2}\,\mu(\centerput(1,-0.5){$\bullet$}
\fleche(2,1)\dir(1,0)\long{4}
\fleche(6,0)\dir(-1,0)\long{4}
\centerput(7,-0.5){$\bullet$}
\centerput(1,2){$1$}
\centerput(7,2){$2$}\kern23pt)\biggr).\leqno(3.3)
$$
Pour $n\ge 1$, notons $\Invc_n$ l'ensemble des involutions de $[\,n\,]$, dont le
graphe est {\it connexe} [en abr\'eg\'e : les involutions connexes]. On a
\'evidemment :
$$
\Invc_1=\{\centerput(3,-1){\boucleagauched}
\centerput(3.5,1){$\bullet$}
\centerput(5,1){$1$}\kern17pt \},\qquad
\Invc_2=\{\centerput(1,-0.5){$\bullet$}
\fleche(2,1)\dir(1,0)\long{4}
\fleche(6,0)\dir(-1,0)\long{4}
\centerput(7,-0.5){$\bullet$}
\centerput(1,2){$1$}
\centerput(7,2){$2$}\hskip .8cm\},\qquad \Invc_n=\emptyset\ (n\ge 3),
$$
de sorte que (1.1) peut encore se r\'ecrire
$$
\sum_{n\ge 0} \mu\{\Inv_n\}{u^n\over n!}
=\exp\Bigl(\sum_{n\ge 1}\mu\{\Invc_n\}{u^n\over n!}\Bigr).\leqno(3.4)
$$
Cette derni\`ere identit\'e s'interpr\`ete en disant que {\sl la fonction
g\'en\'eratrice exponentielle des polyn\^omes g\'en\'erateurs des involutions
sur les intervalles $[\,n\,]$ est \'egale \`a l'exponentielle de la fonction
g\'en\'eratrice exponentielle des polyn\^omes g\'en\'erateurs des involutions
connexes sur les m\^emes intervalles.}

Les formules (1.5) et (1.6) se pr\'esentent aussi sous la forme
$a=\exp b$, o\`u~$a$ et~$b$ sont des s\'eries. Si donc~$b$ est la fonction
g\'en\'eratrice de structures finies, disons~$Y_n$ $(n\ge 1)$ (comme les
$\Invc_n$ pr\'ec\'edemment),  il importe de donner des conditions suffisantes
pour que~$a$ apparaisse comme la fonction g\'en\'eratrice
d'autres structures li\'ees aux~$Y_n$. Ceci fait l'objet du prochain paragraphe.

\bigskip
\centerline{\bf 4. L'identit\'e exponentielle}

\medskip
La formule (3.4) appara\^\i t comme une variation de l'{\it identit\'e
exponentielle} :
$$
\sum_{n\ge 0}\mu\{Y^{(+)}_n\}{u^n\over n!}
=\exp\Bigl(\sum_{n\ge 1}\mu\{Y_n\}{u\over n!}\Bigr).\leqno(4.1)
$$
Dans cette identit\'e, la suite $Y=(Y_n)$ $(n\ge 1)$ est une suite d'ensembles
finis ; \`a chaque entier $n\ge 1$, chaque $y\in Y_n$ et chaque
sous-ensemble~$I$ de ${\bboard N}\setminus\{0\}$, de cardinal~$n$, est
associ\'ee une variable not\'ee $(y,I)$. On suppose que les variables $(y,I)$
commutent. Pour chaque entier $n\ge 1$,  le  {\it compos\'e partitionnel}
de~$Y$, {\it de degr\'e~$n$} est d\'efini comme \'etant l'ensemble,
not\'e~$Y_n^{(+)}$, de tous les mon\^omes $(y_1,I_1)(y_2,I_2)\ldots
(y_r,I_r)$, ayant la propri\'et\'e que l'ensemble $\{I_1,I_2,\ldots, I_r\}$ est
une {\it partition} de l'intervalle
$[\,n\,]$. La suite $Y^{(+)}=(Y_n^{(+)})$ $(n\ge 1)$ est appel\'e le
{\it compos\'e partitionnel} de~$Y$.

Soit $\mu$ une application envoyant les mon\^omes en les variables $(y,I)$
dans une alg\`ebre $\Omega$ de polyn\^omes. On dit qu'elle est {\it
multiplicative} si les deux conditions suivantes sont satisfaites :

\itemitem{(i)} pour toute paire de mon\^omes $w$, $w'$, on a : 
$\mu(ww')=\mu(w)\mu(w')$ ;

\itemitem{(ii)}pour toute variable $(y,I)$, tel que $y\in Y_n$ (et donc tel
que $I$ est de cardinal~$n$), on a
$\mu(y,I)=\mu(y,[\,n\,]\,)$.

\noindent
Si maintenant $y$ appartient \`a~$Y_n$, on d\'efinit : $\mu(y):=\mu(y,[\,n\,])$, de
sorte que si $w=(y_1,I_1)(y_2,I_2)\ldots (y_r,I_r)$ appartient \`a~$Y_n^{(+)}$,
on a la propri\'et\'e {\it multiplicative} :
$$
\mu(w)=\mu(y_1)\mu(y_2)\ldots \mu(y_r).
$$

\proclaim Th\'eor\`eme 4.1. Soient $Y^{(+)}$ le compos\'e partitionnel de la
suite~$Y$ et
$\mu$ une fonction multiplicative. Alors la formule exponentielle $(4.1)$ est
v\'erifi\'ee.

La d\'emonstration de ce th\'eor\`eme peut \^etre trouv\'ee dans [Fo74], mais
on peut aussi bien l'\'etablir directement en d\'eveloppant l'exponentielle et en
interpr\'etant les calculs \`a la lumi\`ere des pr\'ec\'edentes d\'efinitions sur le
compos\'e partitionnel.

\bigskip
\centerline{\bf 5. La formule de Mehler ; l'approche combinatoire}

\medskip
Comme on a vu pr\'ec\'edemment, toute
involution de $[\,n\,]$ est compos\'ee de points fixes et de transpositions.
Par exemple, l'involution $\sigma=(2)(5)(7)(1,3)(4,6)$ peut se r\'ecrire :
$$
\sigma=(1,\{2\})\,(1,\{5\})\,(1,\{7\})\,((1,2),\{1,3\})\,((1,2),\{4,6\}).
$$
Cet exemple montre que la suite des involutions de $[\,n\,]$
$(n=0,1,\ldots\,)$ n'est autre que le compos\'e partitionnel de la suite
$$
\Invc_1=\{(1)\},\quad \Invc_2=\{(1,2)\},\quad \Invc_n=\emptyset\ (n\ge 3).
$$
Par ailleurs, la fonction $\mu$, d\'efinie en (3.1) est bien multiplicative. On a
donc imm\'ediatement l'identit\'e (3.4). Ainsi, l'identit\'e (1.1) qui d\'efinissait
les polyn\^omes d'Hermite n'est autre que l'identit\'e exponentielle pour le
compos\'e partitionnel de la suite des involutions connexes.

Voyons maintenant comment on peut faire rentrer la formule de Mehler dans ce
cadre exponentiel. Pour chaque couple d'involutions $(\sigma,\tau)\in
\Inv_n\times\Inv_n$, posons cette fois
$$
\mu(\sigma,\tau):=(-1)^{\trans \sigma}x^{\fix\sigma}\,
(-1)^{\trans \tau}y^{\fix\tau},\leqno(5.1)
$$
de sorte que le produit de deux polyn\^omes d'Hermite peut se r\'ecrire
$$\displaylines{
H_n(x)H_n(y)
=\sum\mu(\sigma,\tau)\qquad ((\sigma,\tau)\in \Inv_n\times\Inv_n),\cr
\noalign{\hbox{que l'on exprime pour simplifier comme}}
H_n(x)H_n(y)=\mu\{\Inv_n\times\Inv_n\}\cr
\noalign{\hbox{et le membre gauche de (1.5) comme}}
\sum_{n\ge 0}\mu\{\Inv_n\times\Inv_n\}{u^n\over n!}.\cr}
$$

\goodbreak\noindent
Le facteur $(1-u^2)^{-1/2}$ du membre de droite pouvant aussi s'exprimer \`a
l'aide d'une exponentielle, on peut r\'ecrire la formule de Mehler :
$$\displaylines{\quad
\sum_{n\ge 0}\mu\{\Inv_n\times\Inv_n\}{u^n\over n!}\hfill\cr
\noalign{\vskip-6pt}
\kern2cm{}
=\exp\Bigl(\sum_{n\ge 1}{u^{2n}\over 2n}+\Bigl(
\sum_{n\ge 0}xyu^{2n+1}-{x^2+y^2\over 2}u^{2n+2}\Bigr)\Bigr).\hfill\cr
\rlap{(5.2)}\kern2cm{}
=\exp\Bigl(\sum_{n\ {\rm impair}} xy\,n!\,{u^n\over n!}
+\sum_{n\ge2\ {\rm pair}}
\Bigl((n-1)!-{x^2+y^2\over 2}\,n!\,\Bigr){u^n\over n!}\Bigr).\hfill\cr
}
$$
On retrouve bien l'identit\'e exponentielle, mais pour {\it d\'emontrer} la
formule de Mehler, il faut trouver des ensembles finis~$Y_n$ tels que 
$Y_n^{(+)}=\Inv_n\times\Inv_n$ et une
fonction~$\mu$ qui redonne (5.1), lorsqu'un couple
d'invo\-lu\-tions $(\sigma,\tau)$ s'exprime comme un mon\^ome en les
variables $(y,I)$. 

Or, consid\'erons deux graphes d'involutions d'un m\^eme ensemble de~$n$
\'el\'ements, mat\'erialis\'es par des gros points ``$\bullet$." On n'a pas \'ecrit
les \'etiquettes des points pour ne pas surcharger la figure. Les points fixes
sont repr\'esent\'es par des {\it boucles} et les transpositions simplement par
des {\it ar\^etes} joignant deux points. La premi\`ere a les boucles et les
ar\^etes en trait {\it continu} (\cf. Fig.~3), la seconde les a en trait {\it
pointill\'e} (\cf. Fig.~4).

\def\boucleagauche{\vbox{\vbox{\vskip 5mm
\offinterlineskip
\segment(0,3)\dir(-1,0)\long{3}
\segment(0,0)\dir(-1,0)\long{3}
\segment(-3,0)\dir(0,1)\long{3}
\fleche(0,0)\dir(0,1)\long{2.5}
}}}

\def\boucleagauchep{\vbox{\vbox{\vskip 5mm
\offinterlineskip
\segment(0,3)\dir(-1,0)\long{1}
\segment(-2,3)\dir(-1,0)\long{1}
\segment(0,0)\dir(-1,0)\long{1}
\segment(-2,0)\dir(-1,0)\long{1}
\segment(-3,0)\dir(0,1)\long{1}
\segment(-3,2)\dir(0,1)\long{1}
\fleche(0,0)\dir(0,1)\long{2.5}
}}}

\def\boucleadroite{\vbox{\vbox{\vskip 5mm
\offinterlineskip
\segment(0,0)\dir(1,0)\long{3}
\segment(3,0)\dir(0,1)\long{3}
\segment(0,3)\dir(1,0)\long{3}
\fleche(0,0)\dir(0,1)\long{2.5}
}}}

\def\boucleadroitep{\vbox{\vbox{\vskip 5mm
\offinterlineskip
\segment(0,0)\dir(1,0)\long{1}
\segment(2,0)\dir(1,0)\long{1}
\segment(3,0)\dir(0,1)\long{1}
\segment(3,2)\dir(0,1)\long{1}
\segment(0,3)\dir(1,0)\long{1}
\segment(2,3)\dir(1,0)\long{1}
\fleche(0,0)\dir(0,1)\long{2.5}
}}}

\def\pointille{\hbox to .82cm{\thinspace-\thinspace
-\thinspace -\thinspace-\hfil}}

\def\trait{\raise 2pt\hbox to .82cm{\thinspace
\hrulefill\thinspace}}

\def\traitvert{\vrule height .4cm depth .2cm width .4pt}

\def\traitvertp{\vbox{\offinterlineskip\vskip-4pt
\hbox{\vrule
height 2pt  depth 0pt width .4pt}\vskip2pt
\hbox{\vrule height 2pt 
depth 0pt width .4pt}\vskip2pt
\hbox{\vrule height 2pt 
depth 0pt width .4pt}\vskip2pt
\hbox{\vrule height 2pt 
depth 0pt width .4pt}
\vskip2pt
\hbox{\vrule height 2pt 
depth 0pt width .4pt}
\vskip2pt
}}

\midinsert 
$$
\vbox{\offinterlineskip
\halign{&#\cr
\lower4pt\boucleagauche$\bullet$&\hskip.82cm
$\bullet$&\trait$\bullet$&\hskip.82cm
$\bullet$&\hskip-.5pt\lower4pt\boucleadroite
\hskip24pt \lower4pt\boucleagauche$\bullet$&\hskip.82cm
$\bullet$&\trait$\bullet$\cr
&&&&&&&\vrule height.3cm depth .3cm width0pt\cr
$\bullet$&\trait$\bullet$&\hskip.82cm$\bullet$&\trait
$\bullet$&\hskip.82cm$\bullet$&&\hskip-5pt
$\bullet$&\hskip-5pt$\bullet$\cr
\noalign{\vskip1pt}
\hskip2pt&&&&&\hskip-3pt\traitvert
&\hskip-3pt
\traitvert\hskip2pt
&\hskip-3pt\traitvert\cr
%\noalign{\vskip-2pt}
$\bullet$&\trait$\bullet$&\hskip.82cm$\bullet$&\trait
$\bullet$&\hskip.82cm$\bullet$&&\hskip-5pt
$\bullet$&\hskip-5pt$\bullet$\cr
\vrule depth0.4cm height 4pt width 0pt&\cr
$\bullet$&\trait
$\bullet$&\hskip.82cm$\bullet$&\trait
$\bullet$&\hskip.82cm$\bullet$&\trait
$\bullet$&\hskip-.5pt
\hskip25pt \lower6pt\boucleagauche
$\bullet$&\hskip-.5pt\cr
}}
$$

\centerline{Fig. 3}

\medskip
$$
\vbox{\offinterlineskip
\halign{&#\cr
$\bullet$&\pointille
$\bullet$&\hskip.82cm$\bullet$&\pointille
$\bullet$&\hskip-.5pt
\hskip24pt $\bullet$&\pointille
$\bullet$&\hskip.82cm$\bullet$\cr
\noalign{\vskip4pt}
&&&&&&&\hskip-3pt\traitvertp\cr
$\bullet$&\hskip.82cm$\bullet$&\pointille$\bullet$&\hskip.82cm
$\bullet$&\pointille$\bullet$&&\hskip-5pt
$\bullet$&\hskip-5pt$\bullet$\cr
\noalign{\vskip2pt}
\hskip2pt$\vcenter{\vskip3pt\traitvertp}$&&&&&\hskip-3pt
&\hskip-4pt
\hskip1pt$\vcenter{\vskip3pt\traitvertp}$
&\hskip-3pt\cr
\noalign{\vskip-4pt}
$\bullet$&\hskip.82cm$\bullet$&\pointille$\bullet$&\hskip.82cm
$\bullet$&\pointille$\bullet$&&\hskip-5pt
$\bullet$&\hskip-5pt$\bullet$\lower6pt\boucleadroitep\cr
\vrule depth0.4cm height 0pt width 0pt&\cr
\lower6pt\boucleagauchep$\bullet$&\hskip.82cm
$\bullet$&\pointille$\bullet$&\hskip.82cm
$\bullet$&\pointille$\bullet$&\hskip.82cm
$\bullet$&\hskip-.5pt\lower6pt\boucleadroitep
\hskip25pt 
$\bullet$&\hskip-.5pt\lower6pt\boucleadroitep\cr
}}
$$

\centerline{Fig. 4}

\endinsert

Superposons ces deux graphes l'un sur l'autre, en faisant co\"\i ncider les gros
points, par exemple \`a l'aide de deux transparents o\`u les traits continus et
pointill\'es sont remplac\'es par des traits de diff\'erente couleur. On obtient un
nouveau graphe, o\`u chaque point est de valence~2 et naturellement incident \`a
deux ar\^etes ou boucles de trait continu et pointill\'e. Voir Fig.~5.

\midinsert 

$$
\vbox{\offinterlineskip
\halign{&#\cr%\vrule depth0.7cm height 0pt width 0pt\cr
\lower4pt\boucleagauche$\bullet$&\pointille
$\bullet$&\trait$\bullet$&\pointille
$\bullet$&\hskip-.5pt\lower4pt\boucleadroite
\hskip24pt \lower4pt\boucleagauche$\bullet$&\pointille
$\bullet$&\trait$\bullet$\cr
&&&&&&&\hskip-3pt\traitvertp\cr
$\bullet$&\trait$\bullet$&\pointille$\bullet$&\trait
$\bullet$&\pointille$\bullet$&&\hskip-5pt
$\bullet$&\hskip-5pt$\bullet$\cr
\noalign{\vskip1pt}
\hskip2pt$\vcenter{\vskip3pt\traitvertp}$&&&&&\hskip-3pt\traitvert
&\hskip-4pt
\traitvert\hskip2pt$\vcenter{\vskip3pt\traitvertp}$
&\hskip-3pt\traitvert\cr
\noalign{\vskip-2pt}
$\bullet$&\trait$\bullet$&\pointille$\bullet$&\trait
$\bullet$&\pointille$\bullet$&&\hskip-5pt
$\bullet$&\hskip-5pt$\bullet$\lower6pt\boucleadroitep\cr
\vrule depth0.4cm height 0pt width 0pt&\cr
\lower6pt\boucleagauchep$\bullet$&\trait
$\bullet$&\pointille$\bullet$&\trait
$\bullet$&\pointille$\bullet$&\trait
$\bullet$&\hskip-.5pt\lower6pt\boucleadroitep
\hskip25pt \lower6pt\boucleagauche
$\bullet$&\hskip-.5pt\lower6pt\boucleadroitep\cr
}}
$$

\centerline{Fig. 5}

\endinsert

\medskip
On observe, de plus, que le graphe obtenu est compos\'e de quatre types de
sous-graphes {\it connexes}. Il y a d'abord les {\it cycles}, forc\'ement de
longueur {\it paire}, o\`u les couleurs (trait continu ou trait pointill\'e) des
ar\^etes {\it alternent}. Il y en a deux dans le graphe de la Fig.~5, l'un \`a
deux sommets, l'autre \`a dix sommets (\cf. Fig.~6). Soit
$A_n$ l'ensemble de ces cycles ayant $n$ sommets (et forc\'ement $n$ ar\^etes)
num\'erot\'es $1,2,\ldots,n$.


\midinsert

$$
\vbox{\offinterlineskip
\halign{&#\cr
$\bullet$&\trait$\bullet$&\pointille$\bullet$&\trait
$\bullet$&\pointille$\bullet$\cr
\hskip2pt$\vcenter{\vskip3pt\traitvertp}$&&&&&\hskip-3pt\traitvert\cr
$\bullet$&\trait$\bullet$&\pointille$\bullet$&\trait
$\bullet$&\pointille$\bullet$\cr
}}
$$

\centerline{Fig. 6}

\endinsert

Il y a ensuite les cha\^\i nes dont les deux extr\'emit\'es ont des boucles de
m\^eme couleur. Ces cha\^\i nes ont forc\'ement un nombre {\it pair} de
sommets. D'abord, celles qui finissent par des boucles en trait continu. Il y en a
une seule dans le graphe de la Fig.~5, \`a savoir
$$
\vbox{\offinterlineskip
\halign{&#\cr
\lower4pt\boucleagauche$\bullet$&\pointille
$\bullet$&\trait$\bullet$&\pointille
$\bullet$&\hskip-.5pt\lower4pt\boucleadroite
\cr
}}
$$

\centerline{Fig. 7}

\medskip
Il y a aussi les cha\^\i nes finissant par des boucles en trait pointill\'e. Il y en a
une seule dans le graphe de la Fig.~5, \`a savoir

$$
\vbox{\offinterlineskip
\halign{&#\cr
\lower6pt\boucleagauchep$\bullet$&\trait
$\bullet$&\pointille$\bullet$&\trait
$\bullet$&\pointille$\bullet$&\trait
$\bullet$&\hskip-.5pt\lower6pt\boucleadroitep\cr
}}
$$

\centerline{Fig. 8}

\medskip
Il y a enfin les cha\^\i nes finissant par une boucle en trait continu et une
boucle en trait pointill\'e. Celles-ci ont forc\'ement un nombre {\it impair} de
points. Il y en a deux dans le graphe de la Fig.~5, une \`a un seul sommet et
une \`a cinq sommets, \`a savoir

$$
\vbox{\offinterlineskip
\halign{&#\cr
\lower4pt\boucleagauche$\bullet$&\pointille
$\bullet$&\trait$\bullet$\cr
&&&&\hskip-3pt\traitvertp\cr
&&&&&&&\hskip-5pt$\bullet$\cr
\noalign{\vskip1pt}
&&&&&&&\hskip-3pt\traitvert\cr
\noalign{\vskip-2pt}
&&&&&&&\hskip-5pt$\bullet$\lower6pt\boucleadroitep\cr
}}
$$

\centerline{Fig. 9}

\medskip
Soit $B_n$ (resp. $C_n$) l'ensemble des cha\^\i nes de $n$ sommets, num\'erot\'es
$1,2,\ldots,n$, dont les deux boucles terminales sont en trait {\it continu} 
(resp. en trait {\it pointill\'e\/}). Soit, enfin, $D_n$ l'ensemble des cha\^\i nes de
$n$ sommets, toujours num\'erot\'es $1,2,\ldots,n$, dont les boucles terminales
sont, l'une en trait continu, l'autre en trait pointill\'e.  

Lorsque l'on identifie $\Inv_n\times\Inv_n$ avec l'ensemble des graphes obtenus
par superposition de deux graphes d'involutions de $[\,n\,]$ (appelons-les
{\it graphes bi-involutionnaires}), un instant de r\'eflexion permet de
se convain\-cre que les {\it seuls} sous-graphes {\it connexes} de ce 
graphe bi-involutionnaire sont les cycles du type pr\'ec\'edent et les cha\^\i nes de
l'un des trois types pr\'ec\'edents. Posons $Y_n=A_n+B_n+C_n+D_n$ (union
disjointe).  Un second instant de r\'eflexion permet alors de se persuader que

{\sl l'ensemble de ces graphes bi-involutionnaires est
le compos\'e partitionnel de la suite $Y=(Y_n)$ $(n\ge 1)$.}

Soit maintenant $w$ un graphe bi-involutionnaire de $n$ sommets, donc un
\'el\'ement de $Y_n^{(+)}$, ayant $k$ ar\^etes en trait continu, $l$ ar\^etes en trait
pointill\'e, $k'$ boucles en trait continu et $l'$ boucles en trait pointill\'e. Pour
un tel graphe, posons :
$$\mu(w):=(-1)^k x^{k'} (-1)^l y^{l'}.
$$
Il est facile de voir que cette fonction $\mu$ ainsi d\'efinie est multiplicative et
que, d'autre part, $\mu$ est constante sur chacun des sous-ensembles $A_n$,
$B_n$, $C_n$, $D_n$. Par exemple, en notant $|A|$ le cardinal d'un ensemble
fini~$A$,
$$\mu\{A_n\}=\mu(y)\cdot |A_n|,
$$
o\`u $y$ est l'un quelconque des \'el\'ements de~$A_n$. Il suffit donc d'\'evaluer les
cardinaux de ces ensembles pour d\'eterminer les quantit\'es
$\mu\{A_n\}$, $\mu\{B_n\}$, $\mu\{C_n\}$, $\mu\{D_n\}$.
On obtient le tableau suivant de la Fig.~10.

\midinsert

$$
\vbox{\halign{\vrule\ \hfil#\hfil\ \vrule&&\vrule height 12pt depth 6pt 
width 0pt\ \hfil#\hfil\ \vrule\cr
\noalign{\hrule}
Type&$n$&$\mu(y)$&Cardinal&$\mu\{\cdot\}$\cr
\noalign{\hrule}
$A_n$&pair&$(-1)^n$&$(n-1)!$&$(n-1)!$\cr
\noalign{\hrule}
$A_n=\emptyset$&impair&&$0$&$0$\cr
\noalign{\hrule}
$B_n$&pair&$(-1)^{n-1}x^2$&$n!/2$&$-x^2n!/2$\cr
\noalign{\hrule}
$B_n=\emptyset$&impair&&$0$&$0$\cr
\noalign{\hrule}
$C_n$&pair&$(-1)^{n-1}y^2$&$n!/2$&$-y^2n!/2$\cr
\noalign{\hrule}
$C_n=\emptyset$&impair&&$0$&$0$\cr
\noalign{\hrule}
$D_n=\emptyset$&pair&&$0$&$0$\cr
\noalign{\hrule}
$D_n$&impair&$(-1)^{n-1}xy$&$n!/2$&$xyn!$\cr
\noalign{\hrule}
}}     
 $$

\centerline{Fig. 10}
\endinsert

On en tire 
$$
\sum_{n\ge 1}\mu\{Y_n\}{u^n\over n!}
=\sum_{n\ {\rm impair}} xy\,n!\,{u^n\over n!}
+\sum_{n\ge2\ {\rm pair}}
\Bigl((n-1)!-{x^2+y^2\over 2}\,n!\,\Bigr){u^n\over n!},
$$
qui est bien l'argument de l'exponentielle qui appara\^\i t dans (5.2).
La formule de Mehler est donc d\'emontr\'ee.

\bigskip
\centerline{\bf 6. Comment exploiter ce nouveau mod\`ele combinatoire ?}

\medskip
Consid\'erons encore un graphe bi-involutionnaire~$G$, de $n$
sommets, num\'erot\'es $1,2,\ldots, n$, mais convenons qu'au lieu d'avoir deux
couleurs (les traits continus et les traits pointill\'es) pour colorier ar\^etes et
boucles, on en ait $m\ge 2$, tout en supposant que les ar\^etes ou boucles
incidents \`a un m\^eme sommet sont de couleurs {\it diff\'erentes}. Appelons
$m$-{\it involutionnaire} un tel graphe. Pour $1\le i<j\le m$ soit $N_{i,j}$ le
sous-ensemble de tous les sommets incidents \`a une ar\^ete ou boucle de
couleur~$i$ et \`a une ar\^ete ou boucle de couleur~$j$. Pour $i<j$, posons
$N_{j,i}=N_{i,j}$ et $S_j=\sum\limits_{i,\,i\not=j}N_{i,j}$. Par cons\'equent,
$S_j$ est l'ensemble des sommets qui sont incidents \`a une ar\^ete ou boucle de
couleur~$j$.

L'ensemble $\{N_{i,j}:1\le i<j\le m\}$ est une partition de $[\,n\,]$ ; appe\-lons
{\it blocs} du graphe ces sous-ensembles $N_{i,j}$ ; de plus, pour chaque
$i=1,2,\ldots,m$, le sous-graphe~$G_i$, dont l'ensemble des sommets est~$S_i$
et dont les ar\^etes et boucles sont de couleur~$i$, est le
graphe~$G_i$ d'une {\it involution} de l'ensemble~$S_i$.

R\'eciproquement, pour se donner un graphe $m$-involutionnaire de~$n$
sommets, il suffit d'avoir une suite $(S_i)$ $(1\le i\le m)$ de sous-ensembles
de ces sommets, tel que tout sommet appartient exactement \`a deux
sous-ensembles $S_i$, $S_j$ ($i\not=j)$ et tel que le
sous-graphe~$G_i$ restreint \`a chaque~$S_i$ soit le graphe d'une involution.
Les blocs sont alors d\'efinis par
$N_{i,j}:=S_i\cap S_j$ ($i\not=j$).

Si donc on se fixe une suite $(S_i)$ ayant les propri\'et\'e pr\'ec\'edentes et si l'on
pose $\mu(G_i)= (-1)^{\trans G_i}\,x_i^{\fix G_i}$, la sommation
$\sum_{G_i}\mu(G_i)$ sur tous les graphes d'involutions $G_i$ de
l'ensemble~$S_i$ est pr\'ecis\'ement le polyn\^ome d'Hermite
$H_{|S_i|}(x_i)$, d'apr\`es (3.2).

En plus des variables $x_i$ $(1\le i\le m)$, consid\'erons un ensemble de
variables commutatives $\rho_{i,j}$ $(1\le i<j\le m)$, puis d\'efinissons le 
{\it poids} d'un graphe $m$-involutionnaire~$G$ de~$m$ sommets comme \'etant
$$\displaylines{\rlap{(6.1)}\hfill
\overline\mu(G):=\prod_{i<j}
\rho_{i,j}^{|N_{i,j}|}\prod_i \mu(G_i),\hfill\cr
\noalign{\hbox{enfin,
formons la s\'erie}}
\rlap{(6.2)}\hfill\sum_{n\ge 0}{1\over n!}\sum_G\overline \mu(G),\hfill\cr}
$$
o\`u la seconde somme porte sur tous les graphes $m$-involutionnaires
de~$n$ sommets. 

Dans cette seconde sommation, on peut d'abord se fixer une suite d'entiers
$(\nu_{i,j})\ (1\le i,j\le m,\,i\not=j)$ telle que $\sum_{i<j}\nu_{i,j}=n$,
d\'efinir $\nu_{j,i}:=\nu_{i,j}$, $s_i:=\sum\limits_{1\le i\le n,\,i\not=j}\nu_{i,j}$
pour
$1\le i\le m$, puis faire la sommation sur toutes les partitions
$\{N_{i,j}:1\le i<j\le m\}$ de $[\,n\,]$ telles que
$|N_{i,j}|=\nu_{i,j}$ pour $i<j$, enfin faire la sommation sur tous les
graphes~$G$, $m$-involutionnaires de~$n$ sommets dont les
blocs sont pr\'ecis\'ement les ensembles
$N_{i,j}$ pour $i<j$. La s\'erie (6.2) devient :
$$
\sum_{n\ge 0}{1\over n!}\sum_{(\nu_{i,j})}\prod_{i<j}
\rho_{i,j}^{\nu_{i,j}}\sum_{(N_{i,j})}\sum_{G}
\prod_i \mu(G_i).\leqno(6.3)
$$
Comme
$\sum\limits_{ G}
\prod\limits_i \mu(G_i)=\prod\limits_i H_{s_i}(x_i)$, on obtient 
$$
\sum_{n\ge 0}{1\over n!}\sum_G\overline \mu(G)
=
\sum_{n\ge 0}{1\over n!}\sum_{(\nu_{i,j})}{n!\over \prod\limits_{i<j}\nu_{i,j}!}
\prod_{i<j}
\rho_{i,j}^{\nu_{i,j}}\prod_i H_{s_i}(x_i).\leqno(6.4)
$$
Autrement dit, {\sl la fonction g\'en\'eratrice exponentielle des graphes
$m$-involutionnaires par le poids~$\overline\mu$ est donn\'ee par
$$
\sum_{n\ge 0}{1\over n!}\sum_G\overline\mu(G)
=\sum_{(\nu_{i,j})}{\prod\limits_{i<j}\rho_{i,j}^{\nu_{i,j}}
\over \prod\limits_{i<j}\nu_{i,j}!}
H_{s_1}(x_1)\cdots H_{s_m}(x_m),\leqno(6.5)
$$
o\`u la somme est sur toutes les matrices sym\'etriques
$$(\nu_{i,j})\ 
(1\le i,j\le m,\,i\not=j),$$ \`a coefficients entiers positifs et o\`u l'on a
pos\'e $s_j=\sum\limits_{1\le i\le m,\,i\not=j}\nu_{i,j}$.}

On a ainsi interpr\'et\'e combinatoirement le membre de gauche de l'identit\'e
multilin\'eaire (1.6). La question qui se pose alors est la sui\-vante : peut-on
faire un comptage des graphes $m$-involutionnaires \`a l'aide de ses parties
{\it connexes}, en s'inspirant du principe d\'evelopp\'e dans le paragraphe
pr\'ec\'edent, et obtenir le membre de droite de (1.6) et du coup {\it
d\'emontrer} l'identit\'e (1.6) ?  La r\'eponse est oui. 

Comme on peut l'imaginer, on peut v\'erifier que l'expression $(\det
\rho)^{-1/2}$ est  l'{\it exponentielle} de la s\'erie g\'en\'eratrice de tous les
graphes $m$-involution\-naires, qui sont des {\it cycles}. On montre, ensuite,
que la forme quadratique
$-{1\over 2}\sum_{i,j} \bigl(\rho^-_{i,j}-\delta_{i,j}\bigr)x_ix_j$ est la
s\'erie g\'en\'eratrice de toutes les {\it cha\^\i nes}, les variables $x_i$,
$x_j$ \'etant les poids des deux boucles aux extr\'emit\'es. Les d\'etails de
cette d\'emonstration combinatoire peuvent \^etre trouv\'es dans [FoGa79].

\bigskip
\centerline{\bf 5. Conclusion}


\medskip
Le mod\`ele des graphes involutionnaires ayant \'et\'e imagin\'e, on aurait pu
croire que ce seraient les sp\'ecialistes de Combinatoire qui auraient obtenu les
premiers l'extension multilin\'eaire (1.6). En fait, cette identit\'e a \'et\'e
imagin\'ee et prouv\'ee tout d'abord par Kibble [Ki45], dans la th\`ese de
doctorat qu'il a termin\'ee en 1945, avant de faire une carri\`ere comme\dots\
missionnaire. En fait, c'est sa familiarit\'e avec les distributions statistiques
et tout particuli\`erement la loi normale \`a plusieurs variables, qui lui a
permis de trouver que la bonne extension du membre {\it de droite} de (1.5)
\'etait le membre de droite de~(1.6). Il a ensuite su exprimer cette extension
en termes de produits de polyn\^omes d'Hermite.

L'identit\'e (1.6) a ensuite \'et\'e red\'ecouverte par Slepian [Sl72] en 1972. La
d\'emonstration combinatoire esquiss\'ee dans le paragraphe~6 a \'et\'e obtenue
en 1979. Enfin, en 1981, Louck [Lo81] l'a reprouv\'ee par des m\'ethodes
reposant sur les op\'erateurs de boson utilis\'es en physique. Contrairement \`a
ce que dit le titre de l'article, Louck d\'emontre, en fait, une identit\'e qui est
simplement \'equivalente \`a cette extension multilin\'eaire.

On trouve dans l'\'etude des polyn\^omes orthogonaux, \`a l'int\'erieur de la
classification donn\'ee par Askey [As75] et qui regroupe plusieurs polyn\^omes
usuels (Hermite, Laguerre, Jacobi, \dots) des identit\'es de type exponentiel, qui
ont \'et\'e prouv\'ees par la technique ci-dessus. On peut dire enfin que c'est la
d\'emonstration combinatoire de la formule de Mehler [Fo78] qui a servi de
d\'eclic \`a Joyal [Jo81], pour mettre au point sa th\'eorie des esp\`eces,
popularis\'ee par  l'\'ecole montr\'ealaise (voir [Be98]) et qui constitue un cadre
\'el\'egant pour la manipulation des s\'eries formelles. Notons, enfin, que cette
m\'ethode combinatoire a \'et\'e judicieusement utilis\'ee et exploit\'ee par
Zeng, d'abord dans sa th\`ese de doctorat [Ze88] et dans plusieurs travaux
ult\'erieurs, notamment dans [Ze92] et [Ze01]

\rem Remerciements|Merci \`a Raymond Seroul, qui a
relu, de fa\c con tr\`es critique, une premi\`ere version de cet article.

\bigskip\bigskip\bigskip\bigskip

{\eightpoint

\centerline{\bf BIBLIORAPHIE}

\bigskip

\divers As70|Richard Askey|Orthogonal polynomials and positivity,  ``Studies
in Appl. Math.," {\bf 6}, in ``Wave Propagation and Special Functions" (D. Ludwig
and F. W. J. Olver, eds.), SIAM, Philadelphia, {\oldstyle 1970}|

\livre As75|Richard Askey|Orthogonal polynomials and Special
Functions|``Regional Conference Series in Appl. Math., {\bf 21}, SIAM,
Philadelphia, {\oldstyle 1970}|

\divers As75a|Richard Askey|MRC Technical Report, 1532, Madison, Wisconsin,
{\oldstyle 1975}|

\livre Be98|Fran\c cois Bergeron, Gilbert Labelle, Pierre Leroux|Combinatorial
species and tree-like structures|Encyclopedia of Math. and its Appl.,
{\bf 67}, Cambridge Univ. Press, Cambridge, {\oldstyle 1998}|

\article Er39|Arthur Erd\'elyi|\"Uber eine erzeugende Funktion von Produkten
Hermitescher Polynome|Math. Zeitschrift|44|1939|201--211|


\livre Er53|Arthur Erd\'elyi, Wilhelm Magnus, Fritz Oberhettinger, Francesco G.
Tricomi|Higher Transcendental Functions, Bateman Manuscript Project, {\rm
Vol.~II}|New York, McGraw-Hill, {\oldstyle 1953}|

\livre Fo74|Dominique Foata|La s\'erie g\'en\'eratrice exponentielle dans les
probl\`emes d'\'enum\'eration|Presses de l'Universit\'e de Montr\'eal, Montr\'eal, 
{\oldstyle 1974}|

\article Fo78|Dominique Foata|A combinatorial proof of the Mehler formula|J.
Combinatorial Theory, Ser.~A|24|1978|250--259|

\divers FoGa79|Dominique Foata, Adriano Garsia|A combinatorial approach to
the Mehler formulas for Hermite polynomials, in ``Relations between
combinatorics and other parts of mathematics" (Proc. Sympos. Pure Math., Ohio
State Univ., Columbus, Ohio, {\oldstyle 1978}), Proc. Sympos. Pure Math.,
XXXIV, Amer. Math. Soc., Providence, R.I., {\oldstyle 1979}, p.~163-179|

\livre Ja41|D. Jackson|Fourier Series and Orthogonal Polynomials|Carus Math.
Monograph {\bf 6}, Math. Assoc. Amer., State Univ. New York, Buffalo, New York,
{\oldstyle 1941}|

\article Jo81|Andr\'e Joyal|Une th\'eorie combinatoire des s\'eries formelles|Adv. in
Math.|42|1981|1--82|

\article Ki45|W. F. Kibble|An extension of a the theorem of Mehler on Hermite
polynomials|Proc. Cambridge Philos. Soc.|41|1945|12--15|

\livre Le72|N. N. Lebedev|Special Functions and their Applications|Dover Publ.,
New York, {\oldstyle 1972}|

\article Lo81|J. D. Louck|Extension of the Kibble-Slepian formula for Hermite
polynomials using boson operator methods|Adv. in Appl. Math.|2|1981|239--249|

\article Me66|F. G. Mehler|\"Uber die Entwicklung einer Function von
beliebig vielen Variablen nach Laplaceschen Functionen h\"oherer
Ordnung|J. f\"ur die reine und angewandte Mathematik|66|1866|161--176|

\article Pf97|J. F. Pfaff|Observationes analyticae ad L Euleri institutiones
calculi integralis, vol.~IV. Supplem. II et IV|Nova Acta Academiae Scientiarum
Imperialis Petropolitanae|11|1797|37--57|

\livre Ra60|Earl D. Rainville|Special Functions|Chelsea Publ. Co., New York,
{\oldstyle 1960}|

\livre Ri58|John Riordan|An Introduction to Combinatorial Analysis|J. Wiley
\& Sons, New York, {\oldstyle 1958}|

\article Ro96|Gian-Carlo Rota|Report on the present state of combinatorics
(Inaugural address delivered at the 5th Formal Power Series and Algebraic
Combinatorics Conference, Florence, 21 juin {\oldstyle 1993})|Discrete
Math.|153|1996|289--303|

\article Sa90|L. Saalsch\"utz|Eine Summationsformel|Z. f\"ur Math. u.
Phys.|35|1890|186--188|

\article Sl72|David Slepian|On the symmetrized Kronecker power of a matrix and
extensions of Mehler's formula for Hermite polynomials|SIAM J. Math.
Anal.|3|1972|606--616|

\livre Sz39|Gabor Szeg\"o|Orthogonal Polynomials|Amer. Mat. Soc. Colloq.
Publ., {\bf 23}, Amer. Math. Soc., Providence, R.I. {\oldstyle 1939}, fourth ed.
{\oldstyle 1978}|

\article Wa33|G. N. Watson|Notes on generating functions. II. Hermite
polynomials|J. London Math. Soc.|8|1933|194--199|

\divers Ze88|Jiang Zeng|Calcul Saalsch\"utzien (th\`ese doctorat), Publ. IRMA
Strasbourg, vol.~{360/TS-05}, {\oldstyle 1988}|


\article Ze92|Jiang Zeng|Weighted derangements and the linearization
coefficients of orthogonal Sheffer polynomials|Proc. London Math.
Soc.|65|1992|1-22| 

\article Ze01|Jiang Zeng, D.S. Kim|A combinatorial formula for the
linearization coefficients of general Sheffer polynomials|Europ. J.
Combin.|22|2001|313--332|

}

\bigskip\bigskip
\rightline{\vtop{\halign{#\hfil\cr
Dominique Foata \cr
Institut Lothaire\cr
1, rue Murner\cr
F-67000 Strasbourg, France\cr
\noalign{\smallskip}
{\tt foata@math.u-strasbg.fr}\cr
{\tt http\hskip-6pt://www-irma.u-strasbg.fr/$\sim$foata}\cr
}}\qquad}


\bye

  

