%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\magnification=1200
\overfullrule=0pt


%%%%%%%%%%%%%%%
%\catcode`@=11


%---> FOURTEENPOINT
%\newfam\gothfam
%\newfam\gothbfam
%\newfam\bbfam
%\newskip\ttglue
%\def\twelvepoint{\def\rm{\fam0\twelverm}%
%\textfont0=\fourteenrm    \scriptfont0=\twelverm    \scriptscriptfont0=\ninerm
%\textfont1=\fourteeni    \scriptfont1=\twelvei    \scriptscriptfont1=\ninei
%\textfont2=\fourteensy    \scriptfont2=\twelvesy    \scriptscriptfont2=\ninesy
%\textfont3=\tenex    \scriptfont3=\tenex    \scriptscriptfont3=\tenex
%\textfont\itfam=\fourteenit    \def\it{\fam\itfam\fourteenit}%
%\textfont\slfam=\fourteensl    \def\sl{\fam\slfam\fourteensl}%
%\textfont\ttfam=\fourteentt    \def\tt{\fam\ttfam\fourteentt}%
%\textfont\bffam=\fourteenbf    \scriptfont\bffam=\twelvebf    \scriptscriptfont\bffam=\ninebf
%    \def\bf{\fam\bffam\fourteenbf}%
%\textfont\gothfam=\fourteeneufm    \scriptfont\gothfam=\twelveeufm    \scriptscriptfont\gothfam=\nineeufm
%    \def\goth{\fam\gothfam\fourteeneufm}%
%\textfont\gothbfam=\fourteeneufb    \scriptfont\gothbfam=\twelveeufb    \scriptscriptfont\gothbfam=\nineeufb
%    \def\gthb{\fam\gothbfam\fourteeneufb}%
%\textfont\bbfam=\fourteenbb    \scriptfont\bbfam=\twelvebb    \scriptscriptfont\bbfam=\ninebb
%    \def\bb{\fam\bbfam\fourteenbb}%
%\tt\ttglue=0.8em plus .5em minus .3em
%\normalbaselineskip=18pt
%\setbox\strutbox=\hbox{\vrule height15pt depth6pt width0pt}%
%\font\sc=cmcsc10 scaled\magstep2
%\normalbaselines\rm}%\fourteenpoint
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


% MACRO

% \font\eighttt=cmtt8             
% \font\eightsl=cmsl8             
% \font\eightex=cmex10 at 8pt

%%%%%%%%%%%%%%%%
%%  FONT CMR  %%
%%%%%%%%%%%%%%%%

% \font\fiverm=cmr5
% \font\sixrm=cmr6
\font\seventeenrm=cmr17
\font\fourteenrm=cmr12 at 14pt
\font\twelverm=cmr12
\font\ninerm=cmr10 at 9pt
\font\eightrm=cmr8
\font\sixrm=cmr10 at 6pt
%
\textfont0=\tenrm
\scriptfont0=\sevenrm
\scriptscriptfont0=\fiverm
\def\rm{\fam0\tenrm}


%%%%%%%%%%%%%%%%
%%  FONT CMM  %%
%%%%%%%%%%%%%%%%
%
% \font\sixi=cmmi6
% \font\eighti=cmmi8
% \font\ninei=cmmi9
% \font\twelvei=cmmi12
% \font\fourteeni=cmmi10 at 14pt
%
\font\teni=cmmi10
\font\seveni=cmmi7
\font\fivei=cmmi5
\textfont1=\teni
\scriptfont1=\seveni
\scriptscriptfont1=\fivei
\def\mit{\fam1}
\def\oldstyle{\fam1\teni}

%%%%%%%%%%%%%%%%%
%%  FONT CMSY  %%
%%%%%%%%%%%%%%%%%
%
\font\fivesy=cmsy6 at 5pt
\font\sixsy=cmsy6
\font\sevensy=cmsy7
\font\eightsy=cmsy8
\font\ninesy=cmsy9
\font\tensy=cmsy10
\font\twelvesy=cmsy10 at 12pt
\font\fourteensy=cmsy10 at 14pt

%%%%%%%%%%%%%%%%%
%%  FONT CMTI  %%
%%%%%%%%%%%%%%%%%
%
\font\nineit=cmti10 at 9pt
\font\eightit=cmti8 
\font\sevenit=cmti7

%%%%%%%%%%%%%%%%%%%
%%  FONT CMBFTI  %%
%%%%%%%%%%%%%%%%%%%
%
\font\eightbfti=cmbxti10 at 8pt
\font\bfti=cmbxti10
\font\twelvebfti=cmbxti10 at 12pt
\font\fourteenbfti=cmbxti10 at 14pt

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  FONT CMCSC (Petites capitales) %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\font\sc=cmcsc10

%%%%%%%%%%%%%%%%%
%%  FONT MSBM  %%
%%%%%%%%%%%%%%%%%

\font\sixbboard=msbm7 at 6pt

% \font\ninebb=msbm9  % msbm10 at 9pt
% \font\eightbb=msbm8 % msbm10 at 8pt
% \font\sixbb=msbm6   % msbm10 at 6pt
% \font\sixbboard=msbm7 at 6pt
%
\font\tenbb=msbm10
\font\sevenbb=msbm7
\font\fivebb=msbm5
\newfam\bbfam
\textfont\bbfam=\tenbb
\scriptfont\bbfam=\sevenbb
\scriptscriptfont\bbfam=\fivebb
\def\bb{\fam\bbfam\tenbb}
\let\oldbb=\bb
\def\bb #1{{\oldbb #1}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  FONT EUFM  (Gothique)  %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
\font\sixgoth=eufm5 at 6pt  
\font\eightgoth=eufm7 at 8pt
%
\font\tengoth=eufm10
\font\sevengoth=eufm7
\font\fivegoth=eufm5
\newfam\gothfam
\textfont\gothfam=\tengoth
\scriptfont\gothfam=\sevengoth
\scriptscriptfont\gothfam=\fivegoth
\def\goth{\fam\gothfam\tengoth}
%

%%%%%%%%%%%%%%%%%
%%  FONT CMBX  %%
%%%%%%%%%%%%%%%%%
%              
% \font\eightbf=cmbx10 at 8pt
\font\twelvebf=cmbx12
\font\fourteenbf=cmbx10 at 14pt
%

\font\ninebf=cmbx9
\font\eightbf=cmbx8
% \font\sevenbf=cmbx10 at 7pt
\font\sixbf=cmbx5 at 6pt 
% \font\sixbf=cmbx5
% \font\fivebf=cmbx10 at 5pt

\font\tenbf=cmbx10
\font\sevenbf=cmbx7
\font\fivebf=cmbx5
\newfam\bffam
\textfont\bffam=\tenbf
\scriptfont\bffam=\sevenbf
\scriptscriptfont\bffam=\fivebf
\def\bf{\fam\bffam\tenbf}
%
%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  HAUT-DE-PAGE (EX. : AUTEUR COURANT ET TITRE COURANT)  %%
%%  BAS-DE-BAGE                                           %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newif\ifpagetitre           \pagetitretrue
\newtoks\hautpagetitre       \hautpagetitre={\hfil}
\newtoks\baspagetitre        \baspagetitre={\hfil}

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

\newtoks\hautpagegauche
         \hautpagegauche={\hfil\the\auteurcourant\hfil}
\newtoks\hautpagedroite
         \hautpagedroite={\hfil\the\titrecourant\hfil}

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

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

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

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


           %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
           %%  UN SEMBLANT DES GUILLEMETS FRANCAIS  %%
           %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\og{\leavevmode\raise.3ex
     \hbox{$\scriptscriptstyle\langle\!\langle$~}}
\def\fg{\leavevmode\raise.3ex
     \hbox{~$\!\scriptscriptstyle\,\rangle\!\rangle$}}
     
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      %%  TRUC AVEC MACHIN AU-DESSUS ET BIDULE AU-DESSOUS %%
      %%                (MODE MATHEMATIQUE)               %%
      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\build #1_#2^#3{\mathrel{\mathop{\kern 0pt #1}
     \limits_{#2}^{#3}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\scs{\scriptstyle}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
         %% FLECHES HORIZONTALES ET VERTICALES AVEC TRUC  %%
         %%   AU-DESSUS ET MACHIN AU-DESSOUS (MODE MATH)  %%
         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\def\hfl[#1][#2][#3]#4#5{\kern -#1
 \sumdim=#2 \advance\sumdim by #1 \advance\sumdim by #3
  \smash{\mathop{\hbox to \sumdim {\rightarrowfill}}
   \limits^{\scriptstyle#4}_{\scriptstyle#5}}
    \kern-#3}

\def\vfl[#1][#2][#3]#4#5%
 {\sumdim=#1 \advance\sumdim by #2 \advance\sumdim by #3
  \setbox1=\hbox{$\left\downarrow\vbox to .5\sumdim {}\right.$}
   \setbox1=\hbox{\llap{$\scriptstyle #4$}\box1
    \rlap{$\scriptstyle #5$}}
     \vcenter{\kern -#1\box1\kern -#3}}

\def\Hfl #1#2{\hfl[0mm][12mm][0mm]{#1}{#2}}
\def\Vfl #1#2{\vfl[0mm][12mm][0mm]{#1}{#2}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

                   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
                   %% DIAGRAMMES COMMUTATIFS  %%
                   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newdimen\sumdim
\def\diagram#1\enddiagram
    {\vcenter{\offinterlineskip
      \def\tvi{\vrule height 10pt depth 10pt width 0pt}
       \halign{&\tvi\kern 5pt\hfil$\displaystyle##$\hfil\kern 5pt
        \crcr #1\crcr}}}

%% SYNTAXE

%%  $$
%%  \diagram
%%   ... & & ... & \cr
%%   ... & & ... & \cr
%%   .................
%%   ... & & ... & \cr
%%  \enddiagram
%%  $$        


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\def\Doteq{\build{=}_{\scriptscriptstyle\bullet}^{\scriptscriptstyle\bullet}}
\def\Doteq{\build{=}_{\hbox{\bf .}}^{\hbox{\bf .}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

               %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
               %% ESPACE VERTICAL EN MODE MATH  %%
               %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

                      %%%%%%%%%%%%%%%%%%%
                      %%  ENCADREMENT  %%
                      %%%%%%%%%%%%%%%%%%%

\def\boxit [#1]#2{\vbox{\hrule\hbox{\vrule
     \vbox spread #1{\vss\hbox spread #1{\hss #2\hss}\vss}%
      \vrule}\hrule}}

\def\carre{\boxit[5pt]{}} %% INDIQUE LA FIN D'UNE PREUVE

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\catcode`\@=11
\def\Eqalign #1{\null\,\vcenter{\openup\jot\m@th\ialign{
\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
&&\quad\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$
\hfil\crcr #1\crcr}}\,}
\catcode`\@=12

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\font\tengoth=eufm10            \font\tenbboard=msbm10
%\font\eightrm=cmr8              \font\eighti=cmmi8 
%\font\eightsy=cmsy8             \font\eightbf=cmbx8 
% \font\eighttt=cmtt8             \font\eightit=cmti8
% \font\eightsl=cmsl8             \font\eightgoth=eufm7
% \font\eightbboard=msbm7         \font\eightex=cmex10 at 8pt

%\font\eightgoth=eufm7           \font\sevenbboard=msbm7

% \font\sixrm=cmr6                \font\sixi=cmmi6
%\font\sixsy=cmsy6               \font\sixbf=cmbx6
% \font\sixgoth=eufm5 at 6pt      \font\sixbboard=msbm7 at 6pt

%\font\fivegoth=eufm5            \font\fivebboard=msbm5



\vsize= 18.5cm
\hsize= 12.5cm
\hoffset=3mm
\voffset=3mm


%%%%%%%%%%%%%%%%%
%% DEFINITIONS %%
%%%%%%%%%%%%%%%%%

\def\qed{\quad\raise -2pt\hbox{\vrule\vbox to 10pt{\hrule width 4pt 
\vfill\hrule}\vrule}} 

\def\qeda{\quad\raise -2pt\hbox{\vrule\vbox to 10pt{\hrule 
width 4pt height9pt 
\vfill\hrule}\vrule}} 


\def\arti#1#2{\setbox50=\null\ht50=#1\dp50=#2\box50}
\def\tend_#1^#2{\mathrel{
	\mathop{\kern 0pt\hbox to 1cm{\rightarrowfill}}
	\limits_{#1}^{#2}}}
\def\tendps{\tend_{n\to\infty}^{\hbox{p.s.}}}


\def\lfq{\leavevmode\raise.3ex\hbox{$\scriptscriptstyle
\langle\!\langle$}\thinspace}
\def\rfq{\leavevmode\thinspace\raise.3ex\hbox{$\scriptscriptstyle
\rangle\!\rangle$}}


\font\msamten=msam10
\font\msamseven=msam7
\newfam\msamfam

\textfont\msamfam=\msamten
\scriptfont\msamfam=\msamseven
 
\def\ams {\fam\msamfam\msamten}

\def\hexnumber #1%
{\ifcase #1 0\or 1\or 2\or 3\or 4\or 5
   \or 6\or 7\or 8\or 9\or A\or B\or C\or D\or E\or F
    \fi}

\mathchardef\leadsto="3\hexnumber\msamfam 20

\def\frac #1#2{{#1\over #2}}

%%%%%%%%%%%%%%%%%%%%%%%%
%% END OF DEFINITIONS %%
%%%%%%%%%%%%%%%%%%%%%%%%

% le fichier grille

\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\picbox(#1,#2,#3)#4{\setbox\tbox=\hbox{#4}%
%     \ht\tbox=#1 \wd\tbox=#2 \dp\tbox=#3 \box\tbox}

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

% sytaxe: \image(hauteur totale reservee, distance
%    verticale de l'origine par rapport au bas de
%    la place reservee){materiel a inserer}
% L'origine est toujours centre horizontalement
%
\def\image(#1,#2)#3{\vbox to #1{\offinterlineskip
    \vss #3 \vskip #2}}

% \leftput place le materiel avec son point de reference
%    en #1,#2 unites \unitlength
% De meme pour \centerput et \rightput

\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}}
% fin du fichier grille --------------------








%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  AUTHOR ON EVEN PAGES  %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\auteurcourant{\eightbf BODO LASS \hfill}

%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  TITLE ON ODD PAGES  %%
%%%%%%%%%%%%%%%%%%%%%%%%%%

\titrecourant{\hfill\eightbf $\bf E + \overline{E} = XY$}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\vskip 1.5cm

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%
%%  TITEL  %%
%%%%%%%%%%%%%

\centerline
{\twelvebf
Variations sur le th\`eme E+$\overline{\hbox{E}}$ = XY
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  Subject Classification               %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\parindent=-1mm\footnote{}{
{\it Key words:} graph, rook polynomial, complementary graph, Hamiltonian circuit, Hamiltonian path, cover polynomial,
                 tournament, R\'edei's theorem, self-complementary graph, symmetric functions
}

\bigskip

%%%%%%%%%%%
%%  NAME %%
%%%%%%%%%%%  

\centerline{\tenrm Bodo LASS}

\medskip

\centerline{\eightit D\'epartement de math\'ematique, Universit\'e Louis Pasteur, 7, rue Ren\'e-Descartes}
\centerline{\eightit F-67084 Strasbourg, France}
\centerline{\eightrm Courriel: lass@math.u-strasbg.fr} 


\bigskip


%%%%%%%%%%%%%%%%
%%  ABSTRACT  %%
%%%%%%%%%%%%%%%%

{\parindent=3mm \narrower


{\eightrm Soit $\scs G = (X,Y;E)$ un graphe biparti et $\scs \overline{G} = (X,Y;\overline{E})$ le graphe biparti compl\'ementaire. 
Notons $\scs p(G,r)$ le nombre des $\scs r$-couplages de~$\scs G$.
Il est classique que le vecteur $\scs [p(\overline{G},r)]_{r=1,2,\dots}$ est d\'etermin\'e par $\scs [p(G,r)]_{r=1,2,\dots}$. 
Nous explicitons ce fait en d\'emontrant des th\'eor\`emes de dualit\'e nouveaux, g\'en\'eralisant et globalisant notamment
les r\'esultats de Chow, Foata, Gessel, Joni, Rota et Zeilberger. 
Pour des graphes orient\'es on obtient ainsi une preuve rapide de l'identit\'e fondamentale de Berge entre des chemins et 
des circuits hamiltoniens.
Exprim\'ee dans le langage des fonctions d'ensembles, celle-ci implique imm\'ediatement la conjecture de Chung et Graham 
(\'etablie d'abord par Chow et Gessel) ainsi que les th\'eor\`emes de parit\'e de R\'edei sur les tournois, de Lov\'asz sur
les graphes non-orient\'es et de Camion et Rao sur les graphes auto-compl\'ementaires.
Finalement, nous \'etudions les relations entre les fonctions d'ensembles et les fonctions sym\'etriques. 
Le th\'eor\`eme principal de la th\`ese de Chow devient ainsi une cons\'equence directe de l'identit\'e de Berge.


Let $\scs G = (X,Y;E)$ be a bipartite graph with bipartite complement $\scs \overline{G} = (X,Y;\overline{E})$. 
The number of $\scs r$-matchings of~$\scs G$ is denoted by $\scs p(G,r)$.
It is classical that the vector $\scs [p(\overline{G},r)]_{r=1,2,\dots}$ is determined by $\scs [p(G,r)]_{r=1,2,\dots}$. 
We make this statement more explicit by proving new duality theorems, generalizing and globalizing the results of Chow, 
Foata, Gessel, Joni, Rota and Zeilberger, in particular. 
For oriented graphs this provides a short proof of Berge's fundamental identity between Hamiltonian paths and circuits.
Expressed in terms of set functions, the identity immediately implies the Chung-Graham conjecture (first derived by 
Chow and Gessel) as well as R\'edei's, Lov\'asz', and Camion's and Rao's parity results for tournaments, non-oriented 
and self-complementary graphs, respectively.
Finally, we study the relations between set functions and symmetric functions and show that the main theorem in Chow's 
Ph.D.~Thesis becomes a direct consequence of Berge's identity.}

}


\vskip1.5pt



\parindent=3mm
\vskip 5mm


%%%%%%%%%%%%
%%  TEXT  %%
%%%%%%%%%%%%


\centerline{\bf 1. Introduction}

\medskip

Soient $X$ et $Y$ deux ensembles disjoints de cardinalit\'e $n$ et $m$, respectivement. Un graphe biparti $G = (X,Y;E)$ est dit 
simple si et seulement si l'ensemble de ses ar\^etes $E$ est un sous-ensemble de $X \times Y$. Pour de tels graphes on d\'efinit le 
{\it graphe biparti compl\'ementaire} par $\overline{G} := (X,Y;\overline{E})$ avec $\overline{E} := (X \times Y) \backslash E$.
On appelle $r$-{\it couplage} de~$G$ un ensemble de $r$ ar\^etes tel que deux quelconques des ar\^etes du couplage sont 
non-adjacentes. Notons $p(G,r)$ le nombre des $r$-couplages de~$G$ et posons $p(G,0) := 1$. 
Traditionellement, on interpr\`ete $X$ (resp.~$Y$) comme un ensemble de lignes (resp.~colonnes) d'un \'echiquier rectangulaire de 
sorte qu'un couplage devient un ensemble de tours non-attaquantes. C'est pourquoi on appelle 
$$
\rho(G,x) \; := \; \sum_{r=0}^{\min(n,m)} (-1)^r p(G,r) \cdot x^{n-r}
$$
le {\it polyn\^ome des tours}. Il est classique (voir le livre~[28] de Riordan, chapitre 7.7) que $\rho(\overline{G},x)$ est 
compl\`etement d\'etermin\'e par $\rho(G,x)$. Toutefois, aucune relation simple reliant $\rho(\overline{G},x)$ et $\rho(G,x)$
n'a \'et\'e imagin\'ee jusqu'\`a pr\'esent. D'autre part, inspir\'es par la d\'efinition visionnaire du polyn\^ome de recouvrement
de Chung et Graham~[12], Chow (et Gessel)~[9] ont introduit le polyn\^ome {\it factoriel} des tours comme \'etant
$$
\rho!(G,z) \; := \; \sum_{r=0}^{\min(n,m)} p(G,r) \cdot z^{\underline{m-r}},
$$
o\`u $z^{\underline{k}} := z(z-1)\cdots(z-k+1)$. Nous l'appellerons, ci-apr\`es, {\it polyn\^ome de Chow}. Il a d\'ej\`a 
fait ses preuves dans l'\'etude des diagrammes de Ferrers (voir~[15]), parce qu'il se factorise naturellement (voir~[19] et [31], 
th\'eor\`eme 2.4.1). De plus, il satisfait une relation de dualit\'e tout \`a fait remarquable
$$
\rho!(\overline{G},z) \; = \; (-1)^m \rho!(G,m-n-1-z),
$$
imagin\'ee par Chow (et Gessel)~[9] dans le cas $n = m$. Outre cette g\'en\'eralisation, nous \'etablissons la nouvelle formule 
$$
\rho!(\overline{G},z) \; = \; {1 \over \Gamma(z+1+n-m)} \int_{0}^{\infty} x^z \cdot e^{-x}\rho(G,x) \cdot dx,
$$
dont la sp\'ecialisation $n = m$ et $z = 0$ fut trouv\'ee par Joni, Rota et Zeilberger~[21], puisque $\rho!(\overline{G},0)$ 
compte le nombre des couplages parfaits de $\overline{G}$ lorsque $n = m$. Ce r\'esultat permet notamment d'interpr\'eter 
des int\'egrales de produits de polyn\^omes de Laguerre g\'en\'eralis\'es comme nombre de d\'erangements
(voir [3], [4], [5], [14], [16], [18], [20], [29], [34]). 

Suivant Godsil ([17], page 157), on peut, en effet, d\'efinir les polyn\^omes de Laguerre comme des polyn\^omes des tours des 
graphes bipartis complets $K_{n,m} := (X,Y;X \times Y)$ avec $|X| = n$ et $|Y| = m$. Autrement dit, pour tout $a \in {\bb N}$, 
nous posons 
$$
Le_n^{(a)}(x) \; := \; \rho(K_{n,n+a},x).
$$
Comme $\rho(K_{n,n+a} \uplus K_{m+a,m},x) = x^a \cdot Le_n^{(a)}(x) \cdot Le_m^{(a)}(x)$, l'identit\'e de Joni, Rota et Zeilberger
implique alors 
$$
\rho!(\overline{K_{n,n+a} \uplus K_{m+a,m}},0) \; 
= \; \int_{0}^{\infty} Le_n^{(a)}(x) \cdot Le_m^{(a)}(x) \cdot x^a e^{-x} dx
$$
(voir~[18]), ce qui fournit notamment l'orthogonalit\'e de nos polyn\^omes $Le_n^{(a)}(x)$ par rapport \`a $x^a e^{-x} dx$. 
Voil\`a pourquoi notre d\'efinition des polyn\^omes de Laguerre $Le_n^{(a)}(x)$ correspond bien \`a la d\'efinition classique.
Notre normalisation, cependant, est choisie de fa\c con que le premier coefficient, i.~e.~le coefficient de $x^n$, vaille $1$.

Il nous semble \'egalement utile d'introduire les {\it polyn\^omes des tours sym\'etriques} (par rapport \`a la bipartition)
en deux variables
$$\openup2pt\eqalign{
\rho(G,x,y) \; &:= \; \sum_{r=0}^{\min(n,m)} (-1)^r p(G,r) \cdot x^{n-r} y^{m-r} \; = \; y^{m-n} \cdot \rho(G,xy), \cr
\overline{\rho}(G,x,y) \; &:= \; \sum_{r=0}^{\min(n,m)} p(G,r) \cdot x^{n-r} y^{m-r} \; = \; (-1)^n y^{m-n} \cdot \rho(G,-xy), \cr
}$$
si $G = (X,Y;E)$ est biparti avec $|X| = n$ et $|Y| = m$. Pour ces polyn\^omes, nous d\'emontrons plusieurs th\'eor\`emes
de dualit\'e qui font intervenir des op\'erateurs diff\'erentiels. En particulier, nos identit\'es nouvelles
$$\openup2pt\eqalign{
\rho(\overline{G},x,y) \; 
&= \; e^{xy} \cdot \overline{\rho}(G,-{\textstyle {d \over dy}},-{\textstyle {d \over dx}}) \cdot e^{-xy} \cr
&= \; (x/y)^{n-m} \cdot \rho(\overline{G},y,x) \cr
&= \; (x/y)^{n-m} \cdot e^{xy} \cdot \overline{\rho}(G,-{\textstyle {d \over dx}},-{\textstyle {d \over dy}}) \cdot e^{-xy} \cr
}$$
impliquent
$$\openup2pt\eqalign{
Le_n^{(m-n)}(x) 
\; &= \; \rho(K_{n,m},x,1) 
\;  = \; \bigl[e^{xy} \cdot (-{\textstyle {d \over dx}})^m (-{\textstyle {d \over dy}})^n \cdot e^{-xy}\bigr]_{y=1} \cr
\; &= \; e^{x} \cdot (-{\textstyle {d \over dx}})^m \bigl[ x^n e^{-x} \bigr] \cr
\; &= \; x^{n-m} \cdot e^{x} \cdot (-{\textstyle {d \over dx}})^n \bigl[ x^m e^{-x} \bigr], \cr
}$$
o\`u la toute derni\`ere identit\'e est la formule de Rodrigues pour les polyn\^omes de Laguerre g\'en\'eralis\'es.
Dans le cas $n = m$, nous \'etablissons \'egalement le th\'eor\`eme de dualit\'e suivant pour le polyn\^ome des tours lui-m\^eme~:
$$\openup2pt\eqalign{
\rho(\overline{G},-x) \; &= \; (-1)^n \cdot \exp \bigl[{ \textstyle {d \over dx}} x {\textstyle {d \over dx}}\bigr] \rho(G, x), \cr
\rho(\overline{G}, x) \; &= \; (-1)^n \cdot \exp \bigl[{-\textstyle {d \over dx}} x {\textstyle {d \over dx}}\bigr] \rho(G,-x). \cr
}$$

\medskip

Nous d\'emontrons tous nos r\'esultats \`a l'aide des fonctions g\'en\'eratrices pour les fonctions d'ensembles. 
Cette m\'ethode alg\'ebrique permet, par excellence, d'auto\-matiser l'utilisation de plusieurs m\'ethodes classiques 
de la combinatoire \'enum\'era\-tive et alg\'ebrique, et notamment l'utilisation du principe d'inclusion-exclusion et 
de l'inversion de M\"obius sur l'ensemble partiellement ordonn\'e des partitions d'un ensemble. 
L'alg\`ebre des fonctions d'ensembles est introduite dans le paragraphe~2. 
Dans le paragraphe~3, elle est appliqu\'ee pour le traitement du polyn\^ome des tours et de sa parent\'e. 
Ceci fournit des d\'emonstrations particuli\`erement courtes et explicatives et permet m\^eme de prolonger
tous nos r\'esultats \`a l'\'etude des permanents des matrices quelconques. 

Pour des matrices carr\'ees on obtient ainsi une preuve rapide d'une g\'en\'eralisation pond\'er\'ee d'une identit\'e fondamentale 
de Berge entre les chemins et les circuits hamiltoniens d'un graphe orient\'e simple $G = (V,E)$, $E \subseteq V \times V$, et ceux 
de son compl\'ement $\overline{G} = (V,\overline{E})$, $\overline{E} = (V \times V) \backslash E$. 
Appelons {\it bi-chemin hamiltonien} une partition de $V$ en deux chemins hamiltoniens non-vides. 
Si $\hbox{cyc}(G)$ d\'esigne le nombre de circuits hamiltoniens de~$G$, $\hbox{lin}(G)$ le nombre de chemins hamiltoniens et
$\hbox{bilin}(G)$ le nombre de bi-chemins hamiltoniens, alors Berge a imagin\'e le th\'eor\`eme de dualit\'e suivant~:
$$
\hbox{lin}(\overline{G}) \; \equiv \; \hbox{lin}(G) \pmod 2, \qquad
\hbox{bilin}(\overline{G}) \; \equiv \; \hbox{bilin}(G) \pmod 2,
$$
$$
\hbox{lin}(\overline{G}) + \hbox{bilin}(\overline{G}) 
\; \equiv \; \hbox{lin}(G) + \hbox{bilin}(G) 
\; \equiv \; \hbox{cyc}(\overline{G}) + \hbox{cyc}(G) \pmod 2
$$
(voir~[7] ainsi que~[6], chapitre~10, th\'eor\`eme~1 et exercice~9). La d\'emonstration de Berge, cependant, contient un r\'esultat 
nettement plus puissant que nous appelons {\it identit\'e de Berge}. Exprim\'ee dans le langage des fonctions d'ensembles, cette 
identit\'e fondamentale prend toute sa force et implique imm\'ediatement tous les r\'esultats des paragraphes~4 et 5, et 
notamment la conjecture de Chung et Graham (\'etablie d'abord par Chow et Gessel), l'identit\'e de Foata et Zeilberger 
sur les polyn\^omes de Laguerre, les th\'eor\`emes de parit\'e de R\'edei sur les tournois, de Lov\'asz sur les 
graphes non-orient\'es et de Camion et Rao sur les graphes auto-compl\'ementaires. Les d\'emonstrations de ces 
r\'esultats donn\'ees par Berge, Camion, Chow, Foata, Gessel, Lov\'asz, Moon, Rao, Szele et Zeilberger 
s'\'etendent parfois sur plusieurs pages (voir [8], [10], [16], [27], [33], [24], 5.19-20, [26], p.~21-23). 

Dans le paragraphe~6, nous \'etudions les relations les plus importantes entre les fonctions d'ensembles et les fonctions 
sym\'etriques. Nous g\'en\'eralisons plusieurs th\'eor\`emes de Stanley~[30] et simplifions ses d\'emonstrations. Finalement,
nous montrons que le th\'eor\`eme principal de la th\`ese de Chow~[11] est une cons\'equence directe de l'identit\'e de Berge.


\bigskip
\bigskip



%%%%%%%%%%%%%%%%%%%%%%%%%%
%
                       %
%  Outils alg\'ebriques
 %
%
                       % 
%%%%%%%%%%%%%%%%%%%%%%%%%%


\centerline{\bf 2. Outils alg\'ebriques}

\bigskip

\noindent
Soit $V$ un ensemble fini et 
$$\openup2pt\eqalign{
f: 2^V & \to A \cr
V' \subseteq V & \mapsto f(V') \in A \cr
}$$
une {\it fonction d'ensembles}, o\`u $A$ est un {\it anneau commutatif} (avec $1$). 
Consid\'erons la fonction g\'en\'eratrice
$$
F_f(\nu) \; := \; \sum_{V' \subseteq V} f(V') \cdot \nu^{V'}, \qquad \nu^{\emptyset} \; := \; 1,
$$
\`a joindre aux r\`egles de calcul suivantes ($V',V'' \subseteq V$)~:
$$
\nu^{V'} \cdot \nu^{V''} \; := \; \nu^{V'+V''}, \quad \hbox{o\`u}
$$
$$
V'+V'' \; := \;
\openup 2pt\left\{\eqalign{
            V' \cup V'',    \quad   & \hbox{si} \quad V' \cap V'' = \emptyset, \cr
            \dag, \; \; \quad \quad & \hbox{si} \quad V' \cap V'' \ne \emptyset, \quad \hbox{o\`u} \cr
}\right. 
$$            
$$
\dag + V' \; := \; \dag, \quad \dag + \dag \; := \; \dag, \qquad \hbox{et} \qquad \nu^{\dag} \; := \; 0.
$$
L'alg\`ebre $A[V]$ de ces fonctions g\'en\'eratrices n'est pas une inconnue. En effet, on a l'isomorphisme
$$
A[V] \; \simeq \; A[v_1,\dots,v_n]/ \langle v_1^2,\dots,v_n^2 \rangle,
$$
si $V$ contient $n$ \'el\'ements.

\bigskip

\noindent
{\sc Exemple 2.1.} Le produit $fg$ de deux fonctions d'ensembles $f,g$ est d\'efini, pour tout $V' \subseteq V$, par
$$
(fg)(V') \; := \; \sum_{V' = V'' \uplus V'''} f(V'') \cdot g(V''').
$$
Il en r\'esulte
$$
F_{fg} (\nu) \; = \; F_f (\nu) \cdot F_g (\nu).
$$

\bigskip

Pour $|V| = \infty$, soit $F(V)$ l'ensemble partiellement ordonn\'e des sous-ensembles finis de $V$. 
On a des projections canoniques
$p_{V',V''}: A[V'] \to A[V'']$ ($V',V'' \in F(V), V' \supseteq V''$) et l'on pose
$$
A[V] \; := \; \lim_{\longleftarrow} A[V'], \quad V' \in F(V)
$$
pour travailler avec des fonctions g\'en\'eratrices de la forme 
$$
F_f (\nu) \; = \; \sum_{V' \in F(V)} f(V') \cdot \nu^{V'}.
$$
Soit
$$
V \; := \; \sum_{v \in V} \nu^{\{v\}}
$$
la fonction indicatrice des sous-ensembles de $V$ de cardinalit\'e $1$ (l'usage double de $V$ pour l'ensemble 
et pour un \'el\'ement de $A[V]$ ne pourra pas \^etre \`a l'origine de confusions). En multipliant la fonction 
g\'en\'eratrice $V$ plusieurs fois par elle-m\^eme, on voit que $V^n/n!$ repr\'esente la fonction indicatrice 
des sous-ensembles de l'ensemble $V$ de cardinalit\'e $n$. L'identit\'e 
$$
\sum_{n=0}^{\infty} f(n) \cdot V^n/n! \; = \sum_{V' \in F(V)} f(|V'|) \cdot \nu^{V'}, 
   \quad f: {\bb N} \to A,
$$   
fournit un plongement de l'anneau $A![[V]]$ des fonctions g\'en\'eratrices de type exponentiel dans l'anneau
$A[V]$. Ce plongement est \`a l'origine de (presque?) toutes les applications de $A![[V]]$ en combinatoire, 
mais il n\'ecessite l'existence d'un mod\`ele combinatoire infini (qui ne fait intervenir que les cardinalit\'es). 
Par cons\'equent, $A[V]$ donne plus de flexibilit\'e et permet un traitement alg\'ebrique, qui refl\`ete parfaitement
les op\'erations classiques de la combinatoire. Outre cela, $A[V]$ est appropri\'e, par excellence, aux calculs par ordinateur.

\medskip

\noindent
{\sc Remarque 2.1.} L'anneau ${\bb Z}![[V]]$ n'est pas noeth\'erien, mais il contient des fonctions importantes comme
$\exp(V)$ et $\log(1+V)$.

\medskip

\noindent
{\sc Exemple 2.2.} Si $char \; A = 2$, on a 
$$\openup2pt\eqalign{
(1+V)^{-1} \; & = \; \sum_{n=0}^{\infty} (-1)^n n! \cdot V^n/n! \cr
              & \equiv \; 1+V \quad \hbox{et} \cr
\log(1+V) \;  & = \; \sum_{n=1}^{\infty} (-1)^{n-1} (n-1)! \cdot V^n/n! \cr
              & \equiv \; V+V^2/2 \cr
}$$
dans l'anneau $A![[V]]$. Ces identit\'es sont \`a l'origine de maints r\'esultats de parit\'e en combinatoire.

\bigskip

\noindent
Pour tout $t \in A$ posons $(t \cdot \nu)^{V'} \; := \; t^{|V'|} \cdot \nu^{V'}$, $\; V' \subseteq V$, et, par cons\'equent,
$$
F_f(t\nu) \; = \; \sum_{\emptyset \subseteq V' \subseteq V} f(V') \; t^{|V'|} \; \nu^{V'}.
$$
Il est \'evident que cette d\'efinition est compatible avec l'addition et la multiplication. Les cas particuliers les plus
importants sont $t = -1$ et $t = 0$: $F_f(0) = F_f(0 \cdot \nu) = f(\emptyset)$. 

Si $F_f (0) = 0$, alors $F_f(\nu)^n/n!$ est d\'efini pour n'importe quel anneau $A$, parce qu'une partition en $n$ sous-ensembles 
non-vides  peut \^etre ordonn\'ee de $n!$ mani\`eres diff\'erentes. Voil\`a pourquoi $A![[V]]$ op\`ere sur $A[V]$ par la 
substitution $G(F_f (\nu))$ d\'efinie pour tout $G \in A![[V]]$.

\bigskip

\noindent
Finalement, on utilise les d\'eriv\'ees $\partial^v$ pour tout $v \in V$ d\'efinies par
$$
\partial^v \nu^{V'} \; := \;
\openup 2pt\left\{\eqalign{
            \nu^{V'}, \quad & \hbox{si} \quad v \in V', \cr
            0, \; \;  \quad & \hbox{sinon.} \cr
}\right. 
$$            
La formule de d\'erivation d'un produit
$$
\partial^v [F_f (\nu) \cdot F_g (\nu)] \; = \; (\partial^v F_f (\nu)) \cdot F_g (\nu) + F_f (\nu) \cdot (\partial^v F_g (\nu))
$$
est l'analogue alg\'ebrique du fait ensembliste le plus fondamental:
$$
v \in V' \uplus V'' \qquad \Leftrightarrow \qquad  v \in V' \quad \hbox{ou} \quad v \in V''.
$$
La formule
$$
\partial^v [G(F_f (\nu))] \; = \; G'(F_f (\nu)) \cdot \partial^v F_f (\nu), \quad G \in A![[V]],
$$
en d\'ecoule imm\'ediatement.

\bigskip

\noindent
{\sc Remarque 2.2.} L'isomorphisme $A[V] \simeq A[v_1,\dots,v_n]/ \langle v_1^2,\dots,v_n^2 \rangle$ ne fait pas correspondre
$\partial^v$ \`a $\partial / \partial v_i$, mais \`a $v_i \partial / \partial v_i$. 
La d\'eriv\'ee partielle $\partial / \partial v_i$
n'a point d'analogue dans $A[V]$.

\bigskip

\noindent
{\sc Exemple 2.3.} 

\smallskip

{\baselineskip=12pt\tenrm
\item{a)} \'Etant donn\'ees $f,g: 2^V \to A$, alors l'\'equivalence suivante n'est rien d'autre que le principe 
          d'inclusion-exclusion~:
$$ 
F_g (\nu) \; = \; \exp [V] \cdot F_f (\nu) \quad \Leftrightarrow \quad
F_f (\nu) \; = \; \exp [-V] \cdot F_g (\nu). 
$$
\smallskip

\item{b)} \'Etant donn\'ees $f,g: 2^V \to A$ avec $f(\emptyset) = g(\emptyset) = 0$, l'\'equivalence 
$$
1+F_g (\nu) \; = \; \exp [F_f (\nu)] \quad \Leftrightarrow \quad
  F_f (\nu) \; = \; \log [1+F_g (\nu)]
$$ 
s'\'ecrit sous la forme
$$\openup2pt\eqalign{
g(V') \; &= \; \sum_{V' = B_1 \uplus \dots \uplus B_k} f(B_1) \cdots f(B_k)  
\quad \forall \; V' \subseteq V \qquad \Leftrightarrow \cr
f(V') \; &= \; \sum_{V' = B_1 \uplus \dots \uplus B_k} (-1)^{k-1} (k-1)! \cdot g(B_1) \cdots g(B_k) 
\quad \forall \; V' \subseteq V \cr
}$$
et n'est rien d'autre que l'inversion de M\"obius pour des fonctions multiplicatives g\'en\'eralis\'ees sur l'ensemble 
partiellement ordonn\'e des partitions de $V$ (voir~[1], chapitre V.1.C ou [13], chapitre 5.2).
Par ailleurs, on peut se servir de $\partial^v$ pour obtenir le r\'esultat d\'eriv\'e
$$
[1+F_g (\nu)] \cdot \partial^v F_f (\nu) \; = \; \partial^v F_g (\nu), 
$$
qui, par suite de la profusion de m\'ethodes inductives ou r\'ecursives, est souvent beaucoup plus connu que le r\'esultat 
{\lfq pur\rfq}. En outre, ce r\'esultat d\'eriv\'e a l'avantage de n'utiliser qu'un seul produit, permettant des calculs
par ordinateur particuli\`erement rapides. 
\smallskip
}
                              
\eject

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
                                                  %     
%  Le polyn\^ome des tours et sa parent\'e          %
%
                                                  %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\centerline{\bf 3. Le polyn\^ome des tours et sa parent\'e}

\bigskip

Soit $G = (X,Y;E)$ un graphe biparti simple et soit $\overline{G} = (X,Y;\overline{E})$ son compl\'e\-ment biparti. Posons
$V := X \uplus Y$ et d\'efinissons $X,Y,E,\overline{E} \in A[V]$ par
$$
X \; := \; \sum_{x \in X} \nu^{\{x\}}, \quad
Y \; := \; \sum_{y \in Y} \nu^{\{y\}}, \quad
E \; := \; \sum_{e \in E} \nu^e, \quad
\overline{E} \; := \; \sum_{e \in \overline{E}} \nu^e,
$$
o\`u chaque ar\^ete $e \in E$ (resp.~$e \in \overline{E}$) est consid\'er\'ee comme un sous-ensemble de~$V$ de cardinalit\'e~deux. La 
d\'efinition du compl\'ement biparti implique alors l'identit\'e suivante, qui est \`a l'origine de tous les r\'esultats de cet
article.

\bigskip

\noindent
{\sc Lemme fondamental.} {\it Dans l'alg\`ebre $A[V] = A[X \uplus Y]$, on a} 
$$\bf 
E + \overline{E} \; = \; XY.\qeda
$$

\bigskip

Pour $\emptyset \subseteq X' \subseteq X$ et $\emptyset \subseteq Y' \subseteq Y$, notons $G[X',Y']$ le sous-graphe de~$G$ 
engendr\'e par $X' \cup Y'$ (c'est le graphe dont les sommets sont les \'el\'ements de \hbox{$X' \cup Y'$} et dont les ar\^etes 
sont les ar\^etes de~$G$ ayant leurs deux extr\'emit\'es dans \hbox{$X' \cup Y'$}). Alors $\exp[E]$ compte, pour chaque 
$X' \subseteq X$ et $Y' \subseteq Y$, le nombre des cou\-plages parfaits de $G[X',Y']$. Voil\`a pourquoi la proposition 
suivante est une cons\'equence imm\'ediate des d\'efinitions du polyn\^ome des tours et de sa parent\'e 
(voir l'introduction).

\medskip

\noindent
{\sc Proposition 3.1.} {\it On a}
$$\openup-2pt\eqalign{
\sum_{X' \subseteq X} \; \sum_{Y' \subseteq Y} \rho!(G[X',Y'],z) \cdot \nu^{X' \cup Y'} 
\; &= \; \exp[E] \cdot \sum_{i=0}^\infty \sum_{j=0}^\infty {X^i \over i!} \cdot {Y^j \over j!} \cdot z^{\underline{j}} \cr
\; &= \; \exp[E] \cdot \exp[X] \cdot (1+Y)^z \quad \hbox{\it et} \cr
\; \cr
\sum_{X' \subseteq X} \; \sum_{Y' \subseteq Y} \rho(G[X',Y'],x) \cdot \nu^{X' \cup Y'} 
\; &= \; \exp[-E] \cdot \exp[xX] \cdot \exp[Y], \cr
\sum_{X' \subseteq X} \; \sum_{Y' \subseteq Y} \rho(G[X',Y'],x,y) \cdot \nu^{X' \cup Y'} 
\; &= \; \exp[-E] \cdot \exp[xX] \cdot \exp[yY], \cr
\sum_{X' \subseteq X} \; \sum_{Y' \subseteq Y} \overline{\rho}(G[X',Y'],x,y) \cdot \nu^{X' \cup Y'} 
\; &= \; \exp[E] \cdot \exp[xX] \cdot \exp[yY].\qeda \cr
}$$

\bigskip

Il est classique que $\rho(\overline{G},x)$ est compl\`etement d\'etermin\'e par $\rho(G,x)$, un r\'esultat que Riordan~[28],
chapitre~7.7, d\'emontra \`a l'aide de la proposition suivante. 

\medskip

\noindent
{\sc Proposition 3.2.} {\it Soit $G = (X,Y;E)$ un graphe biparti simple avec $|X| = n$ et $|Y| = m$. Alors on a pour le
polyn\^ome des tours du graphe biparti compl\'ementaire $\overline{G} = (X,Y;\overline{E})$ l'identit\'e}
$$
\rho(\overline{G},x) \; = \; \sum_{r=0}^{\min(n,m)} p(G,r) \cdot \rho(K_{n-r,m-r},x).
$$

\medskip

{\it D\'emonstration.} En utilisant l'alg\`ebre $A[V] = A[X \uplus Y]$, on a
$$
\sum_{i=0}^\infty \sum_{j=0}^\infty \rho(K_{i,j},x) \cdot {X^i \over i!} \cdot {Y^j \over j!}
\; = \; \exp[xX + Y - XY].
$$
Par cons\'equent, l'identit\'e suivante implique bien notre proposition~:
$$
\exp[xX + Y -\overline{E}]  
\; = \; \exp[xX + Y - XY + E]
\; = \; \exp[E] \cdot \exp[xX + Y - XY].\qeda
$$

\bigskip

Pour les polyn\^omes des tours sym\'etriques, nous pouvons \'etablir des th\'eor\`emes de dualit\'e apparemment nouveaux.

\medskip

\noindent
{\sc Th\'eor\`eme 3.1.} {\it Pour tout graphe biparti simple $G = (X,Y;E)$, on a}
$$\openup2pt\eqalign{
\overline{\rho}(\overline{G},x,y) \; 
&= \; e^{-xy} \cdot \rho(G,{\textstyle {d \over dy}},{\textstyle {d \over dx}}) \cdot e^{xy}, \cr
\rho(\overline{G},x,y) \; 
&= \; e^{xy} \cdot \overline{\rho}(G,-{\textstyle {d \over dy}},-{\textstyle {d \over dx}}) \cdot e^{-xy}. \cr
}$$

\medskip

{\it D\'emonstration.} D'apr\`es le th\'eor\`eme de Taylor formel on a 
$$
f(x+a,y+b) \; = \; \exp \bigl[ {\textstyle {d \over dx}}a + {\textstyle {d \over dy}}b \bigr] \cdot f(x,y)
$$
pour des variables $x$, $y$, $a$, $b$ et une s\'erie formelle $f$. Il s'ensuit
$$\openup2pt\eqalign{
&\exp[-xy] \cdot \exp[{\textstyle {d \over dy}}X + {\textstyle {d \over dx}}Y - E] \cdot \exp[xy] \cr
&= \; \exp[-xy] \cdot \exp[-E] \cdot \exp[{\textstyle {d \over dx}}Y + {\textstyle {d \over dy}}X] \cdot \exp[xy] \cr
&= \; \exp[-xy] \cdot \exp[-E] \cdot \exp[(x+Y)(y+X)] \cr
&= \; \exp[xX + yY + \overline{E}].
}$$
La deuxi\`eme \'egalit\'e est d\'emontr\'ee de la m\^eme fa\c con.\qeda

\bigskip

Comme $\bigl[ ({d \over dx}{d \over dy})^i (xy)^j \bigr]_{y=1} = ({d \over dx}x{d \over dx})^i x^j$ pour tout $i,j \in {\bb N}$,
nous obtenons le corollaire suivant pour le polyn\^ome des tours lui-m\^eme.

\medskip

\noindent
{\sc Corollaire 3.1.} {\it Soit $G = (X,Y;E)$ un graphe biparti simple tel que $|X| = |Y| = n$. Alors on a pour le
polyn\^ome des tours de $\overline{G} = (X,Y;\overline{E})$ les identit\'es}
$$\openup2pt\eqalign{
\rho(\overline{G},-x) \; &= \; 
(-1)^n \cdot e^{-x} \rho(G,{\textstyle {d \over dx}}x{\textstyle {d \over dx}}) e^{x}, \cr
\rho(\overline{G},x) \; &= \; 
(-1)^n \cdot e^{x} \rho(G,-{\textstyle {d \over dx}}x{\textstyle {d \over dx}}) e^{-x}.\qeda \cr
}$$

\bigskip 

Au lieu de reproduire des g\'en\'eralisations du corollaire pr\'ec\'edent au cas $|X| \ne |Y|$ (qui sont moins belles),
nous pr\'ef\'erons donner une autre forme des th\'eor\`emes de dualit\'e faisant intervenir des op\'erateurs diff\'erentiels.

\medskip

\noindent
{\sc Th\'eor\`eme 3.2.} {\it Pour tout graphe biparti simple $G = (X,Y;E)$, on a}
$$\openup2pt\eqalign{
\overline{\rho}(\overline{G},x,y) \; 
&= \; \exp \bigl[  {\textstyle {d \over dx}}{\textstyle {d \over dy}} \bigr] \cdot \rho(G,x,y), \cr
\rho(\overline{G},x,y) \; 
&= \; \exp \bigl[ -{\textstyle {d \over dx}}{\textstyle {d \over dy}} \bigr] \cdot \overline{\rho}(G,x,y). \cr
}$$

\medskip

{\it D\'emonstration.} Puisque ${\textstyle {d \over dx}}{\textstyle {d \over dy}} \exp[xX+yY-E] = XY \cdot \exp[xX+yY-E]$, 
nous avons
$$\openup2pt\eqalign{
\exp[xX+yY+\overline{E}] \; &= \; \exp[XY] \cdot \exp[xX+yY-E] \cr
                            &= \; \exp \bigl[  {\textstyle {d \over dx}}{\textstyle {d \over dy}} \bigr] \cdot \exp[xX+yY-E]. \cr
}$$
L'op\'erateur diff\'erentiel $\exp \bigl[ -{\textstyle {d \over dx}}{\textstyle {d \over dy}} \bigr]$ est l'inverse de
$\exp \bigl[ {\textstyle {d \over dx}}{\textstyle {d \over dy}} \bigr]$.\qeda

\bigskip

Le corollaire~3.2 se d\'eduit du th\'eor\`eme~3.2 de la m\^eme fa\c con que le corollaire~3.1 se d\'eduit du th\'eor\`eme~3.1.

\medskip

\noindent
{\sc Corollaire 3.2.} {\it Soit $G = (X,Y;E)$ un graphe biparti simple tel que $|X| = |Y| = n$. Alors on a pour le
polyn\^ome des tours de $\overline{G} = (X,Y;\overline{E})$ les identit\'es}
$$\openup2pt\eqalign{
\rho(\overline{G},-x) \; &= \; 
(-1)^n \cdot \exp \bigl[{ \textstyle {d \over dx}} x {\textstyle {d \over dx}}\bigr] \rho(G, x), \cr
\rho(\overline{G}, x) \; &= \; 
(-1)^n \cdot \exp \bigl[{-\textstyle {d \over dx}} x {\textstyle {d \over dx}}\bigr] \rho(G,-x).\qeda \cr
}$$

\bigskip

Terminons ce paragraphe avec le th\'eor\`eme de dualit\'e pour le polyn\^ome de Chow dont nous avons mentionn\'e les
sp\'ecialisations classiques dans l'introduction.

\medskip

\noindent
{\sc Th\'eor\`eme 3.3.} {\it Soit $G = (X,Y;E)$ un graphe biparti simple avec $|X| = n$ et $|Y| = m$. Alors on a}
$$\openup2pt\eqalign{
\rho!(\overline{G},z) \; 
&= \; (-1)^m \rho!(G,m-n-1-z) \cr
&= \; {1 \over \Gamma(z+1+n-m)} \int_{0}^{\infty} x^z \cdot e^{-x}\rho(G,x) \cdot dx. \cr
}$$

\medskip

{\it D\'emonstration.} La proposition 3.1 permet d'exprimer la premi\`ere identit\'e dans le langage des fonctions d'ensembles.
En fait, pour repr\'esenter le facteur $(-1)^m$, il suffit de multiplier chaque \'el\'ement de~$Y$ (et de~$E$) par $-1$.
Autrement dit, il faut d\'emontrer
$$\openup2pt\eqalign{
\exp[\overline{E}] \sum_{i=0}^\infty \sum_{j=0}^\infty {X^i \over i!} {Y^j \over j!} z^{\underline{j}} 
\; &= \; \exp[-E]  \sum_{i=0}^\infty \sum_{j=0}^\infty {X^i \over i!} {(-Y)^j \over j!} (j-i-1-z)^{\underline{j}} \cr
\Leftrightarrow \quad
\exp[\overline{E}] \sum_{i=0}^\infty \sum_{j=0}^\infty {X^i \over i!} Y^j {z \choose j} 
\; &= \; \exp[-E]  \sum_{i=0}^\infty \sum_{j=0}^\infty {X^i \over i!} Y^j {i+z \choose j} \cr
\Leftrightarrow \quad
\exp[\overline{E}] \sum_{i=0}^\infty {X^i \over i!} (1+Y)^z 
\; &= \; \exp[-E]  \sum_{i=0}^\infty {X^i \over i!} (1+Y)^{i+z} \cr
\Leftrightarrow \quad
\exp[E+\overline{E}] \exp[X]  
\; &= \; \exp[X(1+Y)]. \cr
}$$
Pour \'etablir l'identit\'e 
$$
(-1)^m \rho!(G,m-n-1-z) \; = \; {1 \over \Gamma(z+1+n-m)} \int_{0}^{\infty} e^{-x} \cdot x^z\rho(G,x) \cdot dx,
$$
il suffit de constater que le coefficient de $p(G,r)$ (voir l'introduction) dans le membre de gauche et dans le membre de droite 
vaut
$$\openup2pt\eqalign{
(-1)^m (m-n-1-z)^{\underline{m-r}} 
\; &= \; (-1)^r (z+n-r)^{\underline{m-r}} 
\;  = \; (-1)^r {\Gamma(z+1+n-r) \over \Gamma(z+1+n-m)} \cr
\; &= \; {1 \over \Gamma(z+1+n-m)} \int_{0}^{\infty} e^{-x} \cdot x^z (-1)^r x^{n-r} \cdot dx.\qeda \cr
}$$

\bigskip

\noindent
{\sc Remarque 3.1.} Dans le sens de Gessel et Stanley, il faudrait \'egalement \'etudier les fonctions g\'en\'eratrices des suites
de nombres $\rho!(G,z)$, $z \in {\bb Z}$, une \'etude que nous ne reproduisons pas ici. 

\medskip

\noindent
{\sc Remarque 3.2.} Pour plusieurs applications (voir [3], [4], [5] et [16], par exemple), 
il est indispensable de prolonger nos r\'esultats aux graphes bipartis {\it pond\'er\'es} $G_w = (X,Y;E,w)$, o\`u 
\hbox{$w: X \uplus Y \to A$} (resp.~\hbox{$E: X \times Y \to A$}) est une fonction attachant un poids \`a chaque 
sommet (resp.~ar\^ete) du graphe. Par d\'efinition, $\{x,y\}$ est une ar\^ete de $G_w$ si et seulement si 
$E(\{x,y\}) \ne 0$, de sorte qu'un graphe biparti simple est un graphe biparti pond\'er\'e tel que 
$w(x) = w(y) = 1$ et $E(\{x,y\}) \in \{0,1\}$ pour tout $x \in X$ et $y \in Y$. 

Le {\it compl\'ement pond\'er\'e} $\overline{G_w} = (X,Y;\overline{E},w)$ du graphe $G_w = (X,Y;E,w)$ est d\'efini par 
$$
E(\{x,y\}) + \overline{E}(\{x,y\}) \; = \; w(x) \cdot w(y)
$$
pour tout $x \in X$ et $y \in Y$. En posant 
$$\openup2pt\eqalign{
X \; := \; \sum_{x \in X} w(x) \cdot \nu^{\{x\}},& \quad
Y \; := \; \sum_{y \in Y} w(y) \cdot \nu^{\{y\}}, \quad \cr
E \; := \; \sum_{x \in X} \sum_{y \in Y} E(\{x,y\}) \cdot \nu^{\{x,y\}},& \quad
\overline{E} \; := \; \sum_{x \in X} \sum_{y \in Y} \overline{E}(\{x,y\}) \cdot \nu^{\{x,y\}}, \cr
}$$ 
notre lemme fondamental 
$$
E + \overline{E} \; = \; XY
$$
reste alors valable. 

Un $r$-{\it couplage} de~$G_w$, finalement, est un recouvrement de tous les $n$ sommets de~$X$ et 
de tous les $m$ sommets de~$Y$ par $r$ ar\^etes non-adjacentes, $n-r$ sommets de~$X$ et $m-r$ sommets de~$Y$. 
Le poids du $r$-couplage est \'egal au produit des poids de ses $r$ ar\^etes, ses $n-r$ sommets de~$X$ 
et ses $m-r$ sommets de~$Y$. 

Notons $p(G_w,r)$ la somme des poids de tous les $r$-couplages de~$G_w$, 
$p(G_w,0) = [\prod_{x \in X} w(x)] \cdot [\prod_{y \in Y} w(y)]$.
De cette mani\`ere, la proposition~3.1 ainsi que tous les autres r\'esultats de ce paragraphe restent effectivement 
valables pour les graphes bipartis pond\'er\'es. 
Autrement dit, {\it nous avons \'etabli des th\'eor\`emes de dualit\'e pour les permanents des matrices de dimensions} $n \times m$.

\bigskip
\bigskip

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
                                          %     
%  Chemins et circuits hamiltoniens         %
%
                                          %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\centerline{\bf 4. Chemins et circuits hamiltoniens}

\bigskip

Supposons dor\'enavant que $|X| = |Y| = n$ et fixons une bijection entre $X$ et $Y$. Ceci nous permet d'identifier le graphe
biparti simple $G = (X,Y;E)$, $E \subseteq X \times Y$, \`a un graphe orient\'e simple $G = (V,E)$ avec $|V| = n$ et
$E \subseteq V \times V$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\midinsert
\newbox\boxquatre

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

\setbox\boxquatre=\vbox{\vskip
12mm\offinterlineskip
%
\centerput(-46,-4){graphe orient\'e~:}
\centerput(-28,-4){$\bullet$}
\centerput(-7,-4){$\bullet$}
\centerput(14,-4){$\bullet$}
\centerput(35,-4){$\bullet$}
\centerput(56,-4){$\bullet$}
%
\fleche(-28,-3)\dir(1,0)\long{10.5}
\segment(-17.5,-3)\dir(1,0)\long{10.5}
\fleche(-7,-3)\dir(1,0)\long{10.5}
\segment(3.5,-3)\dir(1,0)\long{10.5}
\fleche(56,-3)\dir(-1,0)\long{10.5}
\segment(45.5,-3)\dir(-1,0)\long{10.5}
\segment(-28,-3)\dir(0,-1)\long{3}
\segment(14,-3)\dir(0,-1)\long{3}
\fleche(14,-6)\dir(-1,0)\long{21}
\segment(-7,-6)\dir(-1,0)\long{21}
%
\centerput(-46,8){graphe biparti~:}
\centerput(-28,4){$\bullet$}
\centerput(-7,4){$\bullet$}
\centerput(14,4){$\bullet$}
\centerput(35,4){$\bullet$}
\centerput(56,4){$\bullet$}
%
\centerput(-28,11){$\bullet$}
\centerput(-7,11){$\bullet$}
\centerput(14,11){$\bullet$}
\centerput(35,11){$\bullet$}
\centerput(56,11){$\bullet$}
%
\segment(-28,5)\dir(3,1)\long{21}
\segment(-7,5)\dir(3,1)\long{21}
\segment(14,5)\dir(-6,1)\long{42}
\segment(56,5)\dir(-3,1)\long{21}
}

$$
\box\boxquatre
$$

\endinsert

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bigskip


Notons que $V$ n'est plus \'egal \`a $X \uplus Y$ \`a partir de ce paragraphe. 
La d\'efinition du graphe biparti compl\'ementaire fournit une d\'efinition naturelle du graphe orien\-t\'e compl\'ementaire,
\`a savoir $\overline{G} = (V,\overline{E})$, o\`u $\overline{E} = (V \times V) \backslash E$. En particulier, $G$ contient
une boucle autour de $v \in V$ si et seulement si $\overline{G}$ n'a pas de boucle autour de $v$. 
{\it Un $r$-couplage du graphe biparti, finalement, n'est rien d'autre qu'une partition de~$V$ en plusieurs 
circuits hamiltoniens et $n-r$ chemins hamiltoniens du graphe orient\'e,} de sorte que tous les r\'esultats du paragraphe
pr\'ec\'edent peuvent \^etre interpr\'et\'es dans le langage des graphes orient\'es.

Pour tout $\emptyset \subset V' \subseteq V$, notons $G[V']$ le sous-graphe du graphe orient\'e \hbox{$G = (V,E)$} qui est engendr\'e 
par~$V'$ (c'est le graphe dont les sommets sont les \'el\'ements de~$V'$ et dont les arcs sont les arcs de~$G$ ayant leurs deux 
extr\'emit\'es dans $V'$). Soit cyc$(G[V'])$ le nombre de circuits hamiltoniens de~$G[V']$ et soit lin$(G[V'])$ le nombre de 
chemins hamiltoniens de~$G[V']$, o\`u un seul sommet $v \in V$ est un chemin hamiltonien de~$G[\{v\}]$ dont $v$ est \`a la 
fois le sommet initial et le sommet terminal, alors qu'une boucle autour de~$v$ est bien un circuit hamiltonien 
de~$G[\{v\}]$. Les deux \'el\'ements
$$
\hbox{cyc}_G(\nu) \; := \; \sum_{\emptyset \subset V' \subseteq V} \hbox{cyc}(G[V']) \cdot \nu^{V'}, \qquad
\hbox{lin}_G(\nu) \; := \; \sum_{\emptyset \subset V' \subseteq V} \hbox{lin}(G[V']) \cdot \nu^{V'}
$$
de l'alg\`ebre $A[V]$, $|V| = n$, sont au centre du reste de cet article. En fait, si l'on pose $n = m$ et $z = 0$ dans la 
premi\`ere identit\'e du th\'eor\`eme~3.3, alors le membre de gauche de cette identit\'e est \'egal au coefficient de $\nu^V$ 
dans \hbox{$\exp[\hbox{cyc}_{\overline{G}}(\nu)]$}, tandis que le membre de droite est \'egal au coefficient de $\nu^V$ de la 
fonction d'ensembles \hbox{$\exp[\hbox{cyc}_G(-\nu)] \cdot [1+\hbox{lin}_G(-\nu)]^{-1}$}. Autrement dit, notre th\'eor\`eme~3.3
implique la relation
$$
\exp[\hbox{cyc}_{\overline{G}}(\nu)] \; = \; \exp[\hbox{cyc}_G(-\nu)] \cdot [1+\hbox{lin}_G(-\nu)]^{-1},
$$
imagin\'ee par Berge~[7] sans utiliser les fonctions d'ensembles. En intervertissant les r\^oles de~$G$ et~$\overline{G}$, 
nous obtenons le th\'eor\`eme suivant, qui est \`a l'origine de tous les r\'esultats des paragraphes 4 et 5.

\medskip

\noindent
{\sc Th\'eor\`eme 4.1.} (Identit\'e de Berge) {\it Soit $G = (V,E)$ un graphe orient\'e simple. Alors on a}
$$
1+\hbox{lin}_{\overline{G}}(\nu) \, = \, [1+\hbox{lin}_G(-\nu)]^{-1} \, = \,
\exp[\hbox{cyc}_{\overline{G}}(\nu) - \hbox{cyc}_G(-\nu)],
$$
$$
\log[1+\hbox{lin}_{\overline{G}}(\nu)] \, = \, -\log[1+\hbox{lin}_G(-\nu)] \, = \,
\hbox{cyc}_{\overline{G}}(\nu) - \hbox{cyc}_G(-\nu) \quad \hbox{\it et}
$$
$$
[1+\hbox{lin}_G(-\nu)] \cdot \partial^v \hbox{lin}_{\overline{G}}(\nu)
\, = \, - [1+\hbox{lin}_{\overline{G}}(\nu)] \cdot \partial^v \hbox{lin}_G(-\nu)
\, = \, \partial^v [ \hbox{cyc}_{\overline{G}}(\nu) - \hbox{cyc}_G(-\nu) ]
$$
\smallskip
\noindent
{\it pour chaque sommet $v \in V$.}\qeda

\bigskip

\noindent
{\sc Remarque 4.1.} Pour des applications futures, il est indispensable de prolonger nos r\'esultats aux graphes orient\'es 
{\it pond\'er\'es} $G_{it} = (V,E,i,t)$, o\`u \hbox{$i,t: V \to A$}  et \hbox{$E: V \times V \to A$} sont des fonctions 
attachant des poids \`a chaque sommet et arc, respectivement. Par d\'efinition, $(u,v)$ est un arc de $G_{it}$ si et 
seulement si $E((u,v)) \ne 0$, de sorte qu'un graphe orient\'e simple est un graphe orient\'e pond\'er\'e tel que 
$i(v) = t(v) = 1$ et $E((u,v)) \in \{0,1\}$ pour tout $u,v \in V$. 
Le {\it compl\'ement pond\'er\'e} $\overline{G_{it}} = (V,\overline{E},i,t)$ du graphe $G_{it} = (V,E,i,t)$ est d\'efini par 
$$
E((u,v)) + \overline{E}((u,v)) \; = \; i(u) \cdot t(v)
$$
pour tout $u,v \in V$. 
Finalement, le poids d'un circuit hamiltonien est \'egal au produit des poids de ses arcs, tandis que le poids d'un chemin
hamiltonien est \'egal au produit des poids de ses arcs multipli\'e par $t(u) \cdot i(v)$ si $u$ (resp.~$v$) est le sommet
initial (resp.~terminal) du chemin. 

Pour tout $\emptyset \subset V' \subseteq V$, notons cyc$(G_{it}[V'])$ (resp.~lin$(G_{it}[V'])$) la somme des poids de tous 
les circuits (resp.~chemins) hamiltoniens de~$G_{it}[V']$. 
Avec ces d\'efinitions, notre remarque 3.2 permet de conclure que le th\'eor\`eme~4.1 reste valable pour les graphes orient\'es
pond\'er\'es. Autrement dit, nous avons \'etabli un th\'eor\`eme de dualit\'e pour les matrices carr\'ees de dimension~$n \times n$.
En fait, la diagonale principale d'une matrice carr\'ee fournit une bijection canonique entre l'ensemble des lignes et l'ensemble 
des colonnes (voir le d\'ebut de ce paragraphe). Remarquons finalement que les autres r\'esultats des paragraphes 4 et 5 peuvent 
\'egalement \^etre prolong\'es au cas pond\'er\'e. Nous laissons au lecteur le soin d'expliciter ceci. 

\bigskip

Gr\^ace \`a notre exemple~2.2, on peut simplifier le th\'eor\`eme~4.1 sensiblement en le consid\'erant modulo~2~:
$$\openup2pt\eqalign{
1+\hbox{lin}_{\overline{G}}(\nu) \; &\equiv \; 1+\hbox{lin}_G(\nu) \pmod 2, \cr
\hbox{lin}_{\overline{G}}(\nu) + \hbox{lin}_{\overline{G}}(\nu)^2/2 \; &\equiv \;
\hbox{lin}_G(\nu) + \hbox{lin}_G(\nu)^2/2 \; \equiv \;
\hbox{cyc}_{\overline{G}}(\nu) + \hbox{cyc}_G(\nu) \pmod 2.
}$$
Puisque le coefficient de $\nu^V$ dans $\hbox{lin}_G(\nu)^2/2$ compte le nombre de bi-chemins hamiltoniens de $G = (V,E)$ 
(voir l'introduction), nous avons \'etabli le r\'esultat principal de l'article~[7] de Berge (voir~[6], chapitre 10, 
th\'eor\`eme~1 et exercice~9).
 
\medskip
 
\noindent
{\sc Corollaire 4.1.} (Berge) {\it Pour tout graphe orient\'e simple $G = (V,E)$, on a}
$$
\hbox{lin}(\overline{G}) \; \equiv \; \hbox{lin}(G) \pmod 2, \qquad
\hbox{bilin}(\overline{G}) \; \equiv \; \hbox{bilin}(G) \pmod 2,
$$
$$
\hbox{lin}(\overline{G}) + \hbox{bilin}(\overline{G}) 
\; \equiv \; \hbox{lin}(G) + \hbox{bilin}(G) 
\; \equiv \; \hbox{cyc}(\overline{G}) + \hbox{cyc}(G) \pmod 2.\qeda
$$

\bigskip

Soit $G = (V,E)$ un graphe orient\'e simple. Chung et Graham~[12] (resp.~D'An\-to\-na et Munarini~[2]) ont introduit et \'etudi\'e le 
polyn\^ome $C!(G,x,y)$ (resp.~$C(G,x,z)$) appel\'e {\it polyn\^ome de recouvrement} (resp.~{\it polyn\^ome de recouvrement 
g\'eom\'etrique}). \`A l'aide des fonctions d'ensembles, on peut d\'efinir ces polyn\^omes comme suit~:
$$\openup2pt\eqalign{
1 + \sum_{\emptyset \subset V' \subseteq V} C!(G[V'],x,y) \cdot \nu^{V'} 
\; &:= \; \exp[x \cdot \hbox{cyc}_G(\nu)] \cdot [1+\hbox{lin}_G(\nu)]^y, \cr
1 + \sum_{\emptyset \subset V' \subseteq V} C(G[V'],x,z) \cdot \nu^{V'} 
\; &:= \; \exp[x \cdot \hbox{cyc}_G(\nu)] \cdot \exp[z \cdot \hbox{lin}_G(\nu)]. \cr
}$$ 
Il est \'evident que nos d\'efinitions sont \'equivalentes \`a celles propos\'ees par Chung et Graham~[12], D'Antona et Munarini~[2]
et Chow~[10]. 
Chung et Graham ont pos\'e la question de savoir si $C!(\overline{G},x,y)$ est d\'etermin\'e par $C!(G,x,y)$. 
Une r\'eponse affirmative fut trouv\'ee par Chow (et Gessel)~[10], qui ont \'etabli une belle relation entre les 
deux polyn\^omes, soulignant davantage le caract\`ere visionnaire de la d\'efinition de Chung et Graham. 
Nous montrons que la relation imagin\'ee par Chow (et Gessel) ainsi que notre relation entre $C!(\overline{G},x,y)$ et $C(G,x,z)$
sont des corollaires directs de l'identit\'e de Berge. 
Les diff\'erentes d\'emonstrations de Chow et Gessel~[10] sont toutes plus longues.  

\medskip

\noindent
{\sc Th\'eor\`eme 4.2.} {\it Soit $G = (V,E)$ un graphe orient\'e simple avec $|V| = n$. Alors on a}
$$\openup2pt\eqalign{
C!(\overline{G},x,y) \; 
&= \; (-1)^n C!(G,x,-x-y) \cr
&= \; {(-1)^n \over \Gamma(x+y)} \int_0^\infty e^{-z} \cdot C(G,x,-z) \cdot z^{x+y} \cdot 
                                               \textstyle{{\textstyle dz} \over {\textstyle z}}. \cr
}$$

\medskip

{\it D\'emonstration.} Dans le langage des fonctions d'ensembles, la premi\`ere identit\'e du corollaire s'ex\-prime comme suit~:
$$\openup2pt\eqalign{
\exp[x \cdot \hbox{cyc}_{\overline G}(\nu)] \cdot [1+\hbox{lin}_{\overline G}(\nu)]^y
\; &= \; \exp[x \cdot \hbox{cyc}_G(-\nu)] \cdot [1+\hbox{lin}_G(-\nu)]^{-x-y} \cr
\Leftrightarrow \quad
\bigl( \exp[\hbox{cyc}_{\overline G}(\nu) - \hbox{cyc}_G(-\nu)] \bigr)^x
\; &= \; [1+\hbox{lin}_G(-\nu)]^{-x}.
}$$
La seconde identit\'e se v\'erifie de la fa\c con suivante~:
$$\openup2pt\eqalign{
&{1 \over \Gamma(x+y)} \int_0^\infty 
e^{-z} \cdot \exp[x \cdot \hbox{cyc}_G(-\nu)] \cdot \exp[-z \cdot \hbox{lin}_G(-\nu)] \cdot z^{x+y-1} \cdot dz \cr
&= \; \exp[x \cdot \hbox{cyc}_G(-\nu)] \cdot {1 \over \Gamma(x+y)} \int_0^\infty 
\exp \bigl( -z [1+\hbox{lin}_G(-\nu)] \bigr) \cdot z^{x+y-1} \cdot dz \cr
&= \; \exp[x \cdot \hbox{cyc}_G(-\nu)] \cdot {1 \over \Gamma(x+y)} \int_0^\infty 
e^{-t} \cdot \biggl( {t \over  1+\hbox{lin}_G(-\nu)} \biggr)^{x+y-1} \cdot {dt \over 1+\hbox{lin}_G(-\nu)} \cr
&= \; \exp[x \cdot \hbox{cyc}_G(-\nu)] \cdot [1+\hbox{lin}_G(-\nu)]^{-x-y} \cdot {1 \over \Gamma(x+y)} \int_0^\infty 
e^{-t} \cdot t^{x+y-1} \cdot dt \cr
&= \; \exp[x \cdot \hbox{cyc}_G(-\nu)] \cdot [1+\hbox{lin}_G(-\nu)]^{-x-y}.\qeda
}$$

\bigskip

\noindent
{\sc Remarque 4.2.} \'Evidemment, le th\'eor\`eme 4.1 est aussi une cons\'equence imm\'e\-diate du th\'eor\`eme 4.2. 
Le th\'eor\`eme 4.1, cependant, est bien le cha\^\i non essentiel entre l'alg\`ebre et la combinatoire. 

\bigskip

Pour tout $n \in {\bb N}$, $n \ge 1$, soit $K_n$ le {\it graphe orient\'e complet} avec $n$ sommets. \'Evidemment, son compl\'ement 
ne contient aucun arc, et l'on a cyc$(K_n) = (n-1)!$ et lin$(K_n) = n!$. D\'efinissons le graphe infini complet $K_\infty$ dans le 
sens du para\-graphe~2 pour obtenir les identit\'es
$$\openup2pt\eqalign{
\hbox{cyc}_{K_\infty}(\nu) \; &= \; \sum_{n=1}^{\infty}    \hbox{cyc} (K_n) \cdot V^n/n!  \; = \; - \log (1-V), \cr
\hbox{lin}_{K_\infty}(\nu) \; &= \; \sum_{n=1}^{\infty} \; \hbox{lin} (K_n) \cdot V^n/n!  \; = \; {V \over 1-V}. \cr
}$$
Les polyn\^omes de Laguerre g\'en\'eralis\'es $Le_n^{(\alpha)}(z)$ furent introduits dans l'intro\-duction pour $\alpha \in {\bb N}$.
La proposition suivante est facile \`a \'etablir pour eux (voir notre relation entre graphes bipartis et graphes orient\'es). 
De plus, elle nous servira de d\'efinition des polyn\^omes de Laguerre pour $\alpha \notin {\bb N}$.
L'orthogonalit\'e par rapport \`a $z^\alpha e^{-z} dz$ des polyn\^omes $Le_n^{(\alpha)}(z)$ ainsi d\'efinis sera une cons\'equence
imm\'ediate de notre corollaire~4.2.

\medskip

\noindent
{\sc Proposition 4.1.} {\it On a}
$$\openup2pt\eqalign{
1 + \sum_{n=1}^\infty Le_n^{(\alpha)}(z) \cdot V^n/n! \; 
&= \; (1+V)^{-\alpha - 1} \cdot \exp \biggl[ {z \cdot V \over 1+V} \biggr] \cr
&= \; \exp \bigl[ (\alpha + 1) \cdot \hbox{cyc}_{K_\infty}(-\nu) \bigr] \cdot \exp \bigl[ -z \cdot \hbox{lin}_{K_\infty}(-\nu) \bigr].
}$$
{\it Autrement dit,}
$ \quad
Le_n^{(\alpha)}(z) \; = \; (-1)^n \cdot C(K_n, \alpha + 1, -z).\qeda
$

\bigskip

Soit $K_{n_1} \uplus \dots \uplus K_{n_k}$ l'union disjointe des graphes complets $K_{n_1},\dots,K_{n_k}$ de sorte que l'on a
l'identit\'e \'evidente
$$
Le_{n_1}^{(\alpha)}(z) \cdots Le_{n_k}^{(\alpha)}(z) \; = \; 
(-1)^{n_1 + \dots + n_k} \cdot C(K_{n_1} \uplus \dots \uplus K_{n_k}, \alpha + 1, -z).
$$
Le th\'eor\`eme 4.2 implique donc le corollaire suivant.

\medskip

\noindent
{\sc Corollaire 4.2.} {\it On a}
$$\openup2pt\eqalign{
&C!(\overline{K_{n_1} \uplus \dots \uplus K_{n_k}},\alpha+1,\beta) \cr
&= \; {1 \over \Gamma(\alpha + \beta + 1)} \int_0^\infty 
      e^{-z} \cdot \Bigl( \prod_{h=1}^k Le_{n_h}^{(\alpha)}(z) \Bigr) \cdot z^{\alpha + \beta} \cdot dz.\qeda \cr
}$$

\bigskip

Le cas le plus important du corollaire pr\'ec\'edent, \`a savoir $\beta = 0$, fut imagin\'e par Foata et Zeilberger 
[16, th\'eor\`eme 1]. 
Si, de plus, on pose $k = 2$, alors on obtient l'orthogonalit\'e par rapport \`a $z^\alpha e^{-z} dz$ pour nos polyn\^omes 
$Le_n^{(\alpha)}(z)$ d\'efinis \`a l'aide de la proposition 4.1. Ceci montre qu'ils s'agit bien des polyn\^omes de Laguerre
(g\'en\'eralis\'es) classiques.

\medskip

\noindent
{\sc Remarque 4.3.} Dans le sens de la remarque 4.1, choisissons des poids $\lambda_1, \dots, \lambda_k$ et d\'efinissons le graphe 
orient\'e pond\'er\'e $(K_{n_1} \uplus \dots \uplus K_{n_k})_{it}$ en posant $i(v) := \lambda_h$ si et seulement si $v$ est un sommet 
de $K_{n_h}$, alors que tous les autres poids sont conserv\'es, i.~e.~$t(v) = 1$ pour chaque sommet, par exemple. De cette mani\`ere,
on~a
$$
Le_{n_1}^{(\alpha)}(\lambda_1 z) \cdots Le_{n_k}^{(\alpha)}(\lambda_k z) \; = \; 
(-1)^{n_1 + \dots + n_k} \cdot C((K_{n_1} \uplus \dots \uplus K_{n_k})_{it}, \alpha + 1, -z)
$$
et le cas $\beta = 0$ de l'identit\'e
$$\openup2pt\eqalign{
&C!(\overline{(K_{n_1} \uplus \dots \uplus K_{n_k})_{it}},\alpha+1,\beta) \cr
&= \; {1 \over \Gamma(\alpha + \beta + 1)} \int_0^\infty 
        e^{-z} \cdot \Bigl( \prod_{h=1}^k Le_{n_h}^{(\alpha)}(\lambda_h z) \Bigr) \cdot z^{\alpha + \beta} \cdot dz
}$$
n'est rien d'autre que le th\'eor\`eme~2 de~[16], c'est-\`a-dire le th\'eor\`eme principal de cet article de Foata et Zeilberger. 


\bigskip
\bigskip

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
                                        %     
%  Tournois et graphes non-orient\'es     %
%
                                        %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\centerline{\bf 5. Tournois et graphes non-orient\'es}

\bigskip

Un {\it tournoi} $G = (V,E)$ est un graphe orient\'e simple sans boucles et tel que pour deux sommets distincts $u,v \in V$ on ait 
toujours exactement l'une des relations $(u,v) \in E$ ou bien $(v,u) \in E$.
Si $G = (V,E)$ est un tournoi, alors chaque sommet de~$\overline{G}$ contient une boucle et l'on a
\hbox{$\hbox{lin}_{\overline{G}}(\nu) = \hbox{lin}_G(\nu)$} ainsi que 
\hbox{$\hbox{cyc}_{\overline{G}}(\nu) = V + \hbox{cyc}_G(\nu)$}.
Voil\`a pourquoi le th\'eor\`eme~4.1 implique le r\'esultat sui\-vant.

\medskip

\noindent
{\sc Th\'eor\`eme 5.1.} {\it Pour chaque tournoi $G = (V,E)$, on a} 
$$
1+\hbox{lin}_G(\nu) \; = \; [1+\hbox{lin}_G(-\nu)]^{-1} \; = \;
\exp[V] \cdot \exp[\hbox{cyc}_G(\nu) - \hbox{cyc}_G(-\nu)] \quad \hbox{\it et}
$$
$$
\log[1+\hbox{lin}_G(\nu)] \; = \; -\log[1+\hbox{lin}_G(-\nu)] \; = \;
V + \hbox{cyc}_G(\nu) - \hbox{cyc}_G(-\nu).\qeda
$$

\bigskip

Gr\^ace \`a notre exemple~2.2, on peut simplifier le th\'eor\`eme pr\'ec\'edent sensiblement en le consid\'erant modulo~2~:
$$
1+\hbox{lin}_G(\nu) \; \equiv \; \exp[V] \pmod 2, \qquad \; 
\hbox{lin}_G(\nu) + \hbox{lin}_G(\nu)^2/2 \; \equiv \; V \pmod 2.
$$
On n'obtient ainsi rien d'autre que les th\'eor\`emes classiques de R\'edei et de Berge, formul\'es dans le langage des 
fonctions d'ensembles (voir~[6], chapitre 10, th\'eor\`eme~6 et exercice~9). La d\'emonstration du th\'eor\`eme de R\'edei
imagin\'ee par Berge est plus longue, bien qu'elle simplifie d\'ej\`a consid\'erablement les preuves classiques
(voir [33], [26], p.~21-23).

\medskip

\noindent
{\sc Corollaire 5.1.} (R\'edei, Berge) {\it Pour chaque tournoi $G = (V,E)$ tel que $|V| > 1$, on a}
$\;\; \hbox{lin}(G) \, \equiv \, \hbox{bilin}(G) \, \equiv \, 1 \pmod 2$.\qeda

\bigskip

Finalement, soit $E \uplus \overline{E} = {V \choose 2}$ une partition de la famille des sous-ensembles de cardinalit\'e~2 de
l'ensemble~$V$, et soient $G = (V,E)$ et $\overline{G} = (V,\overline{E})$ deux graphes simples non-orient\'es qui sont
compl\'ementaires. 
Pour tout $\emptyset \subset V' \subseteq V$, notons $G[V']$ le sous-graphe de~$G$ engendr\'e par~$V'$ (c'est le graphe dont 
les sommets sont les \'el\'ements de~$V'$ et dont les ar\^etes sont les ar\^etes de~$G$ ayant leurs deux extr\'emit\'es dans $V'$). 
Soit hc$(G[V'])$ (resp.~hp$(G[V'])$) le nombre de circuits (resp.~chemins) hamiltoniens de~$G[V']$, o\`u hc$(G[V']) := 0$ 
(resp.~hp$(G[V']) := 0$) si $|V'| < 3$ (resp.~$|V'| < 2$). Posons 
$$
\hbox{HC}_G(\nu) \; := \; \sum_{\emptyset \subset V' \subseteq V} \hbox{hc}(G[V']) \cdot \nu^{V'}, \qquad
\hbox{HP}_G(\nu) \; := \; \sum_{\emptyset \subset V' \subseteq V} \hbox{hp}(G[V']) \cdot \nu^{V'}
$$
ainsi que $E := \sum_{e \in E} \nu^e$ et $\overline{E} := \sum_{e \in \overline{E}} \nu^e$ de sorte que $E + \overline{E} = V^2/2$ 
dans l'alg\`ebre $A[V]$.

Suivant la suggestion de Berge (voir~[6], pr\'eface), rempla\c cons chaque ar\^ete de~$G$ et de~$\overline{G}$ par deux arcs 
d'orientations oppos\'ees et munissons chaque sommet de~$\overline{G}$ d'une boucle pour obtenir deux graphes simples orient\'es
qui sont compl\'ementaires. Tout circuit (resp.~chemin) hamiltonien non-orient\'e conduit \`a deux circuits (resp. chemins)
hamiltoniens orient\'es. De plus, une ar\^ete non-orient\'e (resp.~un sommet) conduit \`a un circuit (resp.~chemin) 
hamiltonien orient\'e. Par cons\'equent, le th\'eor\`eme~4.1 fournit le r\'esultat suivant. 

\medskip

\noindent
{\sc Th\'eor\`eme 5.2.} {\it Soient $G = (V,E)$ et $\overline{G} = (V,\overline{E})$ deux graphes simples non-orient\'es qui
sont compl\'ementaires. Alors on a} 
$$\openup2pt\eqalign{
&1 + V + 2\hbox{HP}_{\overline{G}}(\nu) \; = \; \bigl[ 1 - V + 2\hbox{HP}_G(-\nu) \bigr]^{-1} \cr
&= \; \exp \bigl[ V + \overline{E} + 2\hbox{HC}_{\overline{G}}(\nu) - E -2\hbox{HC}_G(-\nu) \bigr], \cr
&\log \bigl[ 1 + V + 2\hbox{HP}_{\overline{G}}(\nu) \bigr] \; = \; - \log \bigl[ 1 - V + 2\hbox{HP}_G(-\nu) \bigr] \cr
&= \; V + \overline{E} - E + 2 \bigl[ \hbox{HC}_{\overline{G}}(\nu) - \hbox{HC}_G(-\nu) \bigr].\qeda \cr
}$$

\bigskip

Pour obtenir des relations plus simples modulo 2, commen\c cons par d\'evelopper la fonction exponentielle dans le th\'eor\`eme 
pr\'ec\'edent modulo 4~:
$$\openup2pt\eqalign{
&\exp \bigl[ V + \overline{E} + 2\hbox{HC}_{\overline{G}}(\nu) - E -2\hbox{HC}_G(-\nu) \bigr] \cr
&\equiv \; \exp \bigl[ \log(1+V) + 
                       2 \bigl( \overline{E} + \hbox{HC}_{\overline{G}}(\nu) + \hbox{HC}_G(\nu) + V^3/3! + V^4/4! \bigr) \bigr] \cr
&\equiv \; \bigl[ 1+V \bigr] 
           \bigl[ 1 + 2\bigl( \overline{E} + \hbox{HC}_{\overline{G}}(\nu) + \hbox{HC}_G(\nu) + V^3/3! + V^4/4! \bigr) \bigr] \pmod 4.
}$$
On en tire le corollaire suivant.

\medskip

\noindent
{\sc Corollaire 5.2.} {\it Pour tout graphe simple non-orient\'e $G = (V,E)$, on a}
$$\openup2pt\eqalign{
&\hbox{HP}_{\overline{G}}(\nu) + \overline{E} (1+V) \; \equiv \; \hbox{HP}_G(\nu) + E (1+V) \cr
&\equiv \; \bigl[ \hbox{HC}_{\overline{G}}(\nu) + \hbox{HC}_G(\nu) \bigr] \bigl[ 1+V \bigr] 
           + V^3/3! + V^4/4! + V^5/5! \pmod 2.\qeda \cr
}$$

\bigskip

Un chemin (resp.~circuit) de~$G = (V,E)$ ($|V| = n$) est dit {\it \'el\'ementaire} s'il ne rencontre pas deux fois le m\^eme 
sommet. Notons hp$_k(G)$ (resp.~hc$_k(G)$) le nombre de chemins (resp.~circuits) \'el\'ementaires de $k$ {\it sommets}, $k \ge 3$. 
En particulier, $\hbox{hp}_n(G) = \hbox{hp}(G)$ (resp.~$\hbox{hc}_n(G) = \hbox{hc}(G)$) d\'enombre les chemins (resp.~circuits) 
hamiltoniens de~$G$, et l'on a
$$
\hbox{hp}_k(G) \; = \; \sum_{V' \in {V \choose k}} \hbox{hp}(G[V']), \qquad 
\hbox{hc}_k(G) \; = \; \sum_{V' \in {V \choose k}} \hbox{hc}(G[V']),
$$
si $V \choose k$ d\'esigne l'ensemble des sous-ensembles de~$V$ de cardinalit\'e~$k$. Multiplions l'identit\'e du corollaire~5.2
par $V^h/h!$, $h \in {\bb N}$~:
$$\openup2pt\eqalign{
&\hbox{HP}_{\overline{G}}(\nu) {V^h \over h!} + \overline{E} (1+V) {V^h \over h!} \; \equiv \; 
 \hbox{HP}_G(\nu) {V^h \over h!} + E (1+V) {V^h \over h!} \cr
&\equiv \;  \bigl[ \hbox{HC}_{\overline{G}}(\nu) + \hbox{HC}_G(\nu) \bigr] 
            \biggl[ {V^h \over h!} + (h+1){V^{h+1} \over (h+1)!} \biggr] \cr
&\quad\;\;\, +
{h+3 \choose 3}{V^{h+3} \over (h+3)!} + {h+4 \choose 4} {V^{h+4} \over (h+4)!} + {h+5 \choose 5} {V^{h+5} \over (h+5)!}\pmod 2. \cr
}$$
En regardant le coefficient de $\nu^V$ nous d\'eduisons le corollaire suivant, puisque $(h+1)$ et $h+5 \choose 5$ sont pairs
si $h$ est un nombre impair. 

\medskip

\noindent
{\sc Corollaire 5.3.} {\it Soient $G = (V,E)$ et $\overline{G} = (V,\overline{E})$ deux graphes simples non-orient\'es qui
sont compl\'ementaires, et soient $k$ et $h$ deux entiers avec $k \ge 5$, $h \ge 1$ et $k+h = n = |V|$.  
Si $h$ est impair, alors on a modulo 2~:}
$$\openup2pt\eqalign{
&\hbox{hp}_k(\overline{G}) \; \equiv \; \hbox{hp}_k(G) \; \equiv \; 
 \hbox{hc}_k(\overline{G}) + \hbox{hc}_k(G), \cr
&\hbox{hp}_{k+1}(\overline{G}) \; \equiv \; \hbox{hp}_{k+1}(G) \; \equiv \; 
 \hbox{hc}_k(\overline{G}) + \hbox{hc}_k(G) + \hbox{hc}_{k+1}(\overline{G}) + \hbox{hc}_{k+1}(G), \cr
&\hbox{hp}_k(\overline{G}) + \hbox{hp}_{k+1}(\overline{G}) \; \equiv \; \hbox{hp}_k(G) + \hbox{hp}_{k+1}(G)  \; \equiv \; 
 \hbox{hc}_{k+1}(\overline{G}) + \hbox{hc}_{k+1}(G).\qeda \cr 
}$$

\bigskip

L'identit\'e $\; \hbox{hp}_{k+1}(\overline{G}) \, \equiv \, \hbox{hp}_{k+1}(G) \!\! \pmod 2 \;$ fut imagin\'ee par Lov\'asz 
[24, 5.19] dans le cas particulier $k+1 = n$.

Un graphe simple non-orient\'e $G = (V,E)$ est appel\'e {\it auto-compl\'ementaire} si et seulement si $G$ et $\overline{G}$
sont isomorphes. Pour de tels graphes, notre corollaire~5.3 fournit le th\'eor\`eme principal de l'article~[27] de Rao,
que ce dernier a d\'emontr\'e sur plusieurs pages. 

\medskip

\noindent
{\sc Corollaire 5.4.} (Rao) {\it Soit $G = (V,E)$ un graphe auto-compl\'ementaire avec $|V| = n$. 
Alors} hp$_k(G)$ {\it est pair pour tout} $5 < k \le n$.\qeda

\bigskip

Le cas le plus important du th\'eor\`eme pr\'ec\'edent, \`a savoir $k = n$, fut imagin\'e par Camion~[8].



\bigskip
\bigskip


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
                                                     %     
%  Fonctions sym\'etriques et fonctions d'ensembles    %
%
                                                     %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\centerline{\bf 6. Fonctions sym\'etriques et fonctions d'ensembles}

\bigskip

Dans l'introduction de sa th\`ese~[11], Chow a sugg\'er\'e une direction prometteuse pour \'etendre son \'etude des fonctions 
sym\'etriques et saisir ainsi davantage de probl\`emes en combinatoire. Il nous semble que les fonctions d'ensembles permettent,
par excellence, de r\'ealiser cette id\'ee de Chow. 

Soient donc $f,g: 2^V \to A$ deux fonctions d'ensembles telles que \hbox{$f(\emptyset) = g(\emptyset) = 0$}. 
Nous d\'efinissons, pour chaque $\emptyset \subset V' \subseteq V$, la {\it fonction sym\'etrique de Stanley} 
$ST_{f,V'}(x_1,x_2,x_3,\dots)$ et la {\it fonction sym\'etrique de Chow} $CH_{g,V'}(x_1,x_2,x_3,\dots)$ par
$$\openup2pt\eqalign{
1 + \sum_{\emptyset \subset V' \subseteq V} ST_{f,V'}(x_1,x_2,x_3,\dots) \cdot \nu^{V'} \; 
&:= \; \prod_{i=1}^\infty \Bigl[ 1 + F_f (x_i \cdot \nu) \Bigr], \cr
1 + \sum_{\emptyset \subset V' \subseteq V} CH_{g,V'}(x_1,x_2,x_3,\dots) \cdot \nu^{V'} \; 
&:= \; \exp \Bigl[ \sum_{i=1}^\infty F_g (x_i \cdot \nu) \Bigr], \cr
}$$
respectivement (voir le d\'ebut du paragraphe~2). La relation fondamentale entre la fonction sym\'etrique de Chow et celle de Stanley 
est donn\'ee par le th\'eor\`eme suivant.

\medskip

\noindent
{\sc Th\'eor\`eme 6.1.} {\it Si $\log [1 + F_f (\nu)] = F_g (\nu)$ ou bien $1 + F_f (\nu) = \exp [F_g (\nu)]$, alors on a pour tout 
$\emptyset \subset V' \subseteq V$}
$$
ST_{f,V'}(x_1,x_2,x_3,\dots) \; = \; CH_{g,V'}(x_1,x_2,x_3,\dots).
$$

\medskip

{\it D\'emonstration.} On a en effet
$$\openup2pt\eqalign{
1 + \sum_{\emptyset \subset V' \subseteq V} ST_{f,V'}(x_1,x_2,\dots) \cdot \nu^{V'} \;
&= \; \exp \Bigl[ \sum_{i=1}^\infty \log \bigl[ 1 + F_f (x_i \cdot \nu) \bigr]  \Bigr] \cr
&= \; 1 + \sum_{\emptyset \subset V' \subseteq V} CH_{g,V'}(x_1,x_2,\dots) \cdot \nu^{V'}.\qeda \cr
}$$

\bigskip

\noindent
{\sc Exemple 6.1.} Les fonctions sym\'etriques de Stanley les plus fondamentales (voir [22], [32, chapitre 7], [25, chapitre 1.2]) 
sont la fonction sym\'etrique \'el\'emen\-taire $e_n = \Lambda^n(x_1,x_2,x_3,\dots)$ et la fonction sym\'etrique 
compl\`ete $h_n = S^n(x_1,x_2,x_3,\dots)$, \hbox{$n \in {\bb N}$}~:
$$\openup2pt\eqalign{
1 + V      \; = \; 1 + F_f (\nu) \qquad &\Rightarrow \qquad ST_{f,V'}(x_1,x_2,x_3,\dots) \; = \; |V'|! \cdot e_{|V'|}, \cr
(1-V)^{-1} \; = \; 1 + F_f (\nu) \qquad &\Rightarrow \qquad ST_{f,V'}(x_1,x_2,x_3,\dots) \; = \; |V'|! \cdot h_{|V'|}. \cr
}$$

\bigskip

Les fonctions sym\'etriques les plus simples, cependant, sont bien les sommes des puissances 
$p_n = \psi_n(x_1,x_2,x_3,\dots) = \sum_{i=1}^\infty x_i^n$. \`A l'aide de cette base de l'espace 
des fonctions sym\'etriques, on d\'efinit l'involution $\omega$ par $\omega(p_n) := (-1)^{n-1} p_n$.
Gr\^ace \`a l'exemple pr\'ec\'edent, le th\'eor\`eme suivant devient une g\'en\'eralisation directe
des identit\'es classiques $\omega(e_n) = h_n$ et $\omega(h_n) = e_n$.

\medskip

\noindent
{\sc Th\'eor\`eme 6.2.} {\it Pour des fonctions d'ensembles $f,g: 2^V \to A$ telles que $f(\emptyset) = g(\emptyset) = 0$, on a}
$$\openup2pt\eqalign{
1 + \sum_{\emptyset \subset V' \subseteq V} \omega \bigl( ST_{f,V'}(x_1,x_2,x_3,\dots) \bigr) \cdot \nu^{V'} \; 
&= \; \prod_{i=1}^\infty \Bigl[ 1 + F_f (- x_i \cdot \nu) \Bigr]^{-1}, \cr
1 + \sum_{\emptyset \subset V' \subseteq V} \omega \bigl( CH_{g,V'}(x_1,x_2,x_3,\dots) \bigr) \cdot \nu^{V'} \; 
&= \; \exp \Bigl[ - \sum_{i=1}^\infty F_g (- x_i \cdot \nu) \Bigr]. \cr
}$$

\medskip

{\it D\'emonstration.} Supposons, sans restreindre la g\'en\'eralit\'e, que $1 + F_f (\nu) = \exp [F_g (\nu)]$. Il s'ensuit~:
$$\openup2pt\eqalign{
&\omega \Biggl( \prod_{i=1}^\infty \Bigl[ 1 + F_f (x_i \cdot \nu) \Bigr] \Biggr) \;
 = \; \omega \Biggl( \exp \Bigl[ \sum_{i=1}^\infty F_g (x_i \cdot \nu) \Bigr] \Biggr) \cr
&= \; \exp \Biggl[ \omega \Bigl( \sum_{i=1}^\infty F_g (x_i \cdot \nu) \Bigr) \Biggr] \;
 = \; \exp \Biggl[ - \sum_{i=1}^\infty F_g (- x_i \cdot \nu) \Biggr] \cr
&= \; \prod_{i=1}^\infty \Bigl[ 1 + F_f (- x_i \cdot \nu) \Bigr]^{-1}.\qeda \cr
}$$

\bigskip

Dans l'article~[23], nous avons introduit, pour chaque graphe simple non-orient\'e $G = (V,E)$, la fonction indicatrice des
ensembles de sommets ind\'ependants $I_G(\nu)$ ainsi que la fonction d'ensembles $A_G(\nu)$ (resp.~$A_G^*(\nu)$) d\'enombrant 
les orientations acycliques (resp.~avec une seule source fix\'ee) pour tous les sous-graphes engendr\'es de~$G$. Nous avons
\'etabli les identit\'es 
$$
[1+I_G(-\nu)]^{-1} \; = \; 1+A_G(\nu), \quad -\log[1+I_G(-\nu)] \; = \; \log[1+A_G(\nu)] \; = \; A_G^*(\nu). 
$$
Stanley~[30] a introduit et \'etudi\'e la fonction chromatique $X_G = X_G(x_1,x_2,x_3,\dots)$, qui est, par excellence, une fonction
sym\'etrique {\lfq de Stanley\rfq}~:
$$
1 + \sum_{\emptyset \subset V' \subseteq V} X_{G[V']} \cdot \nu^{V'} \; 
:= \; \prod_{i=1}^\infty \Bigl[ 1 + I_G(x_i \cdot \nu) \Bigr].
$$
Le corollaire suivant formule plusieurs th\'eor\`emes principaux de l'article~[30] de Stanley dans le langage des fonctions d'ensembles. 

\medskip

\noindent
{\sc Corollaire 6.1.} (Stanley) {\it On a}
$$\openup2pt\eqalign{
1 + \sum_{\emptyset \subset V' \subseteq V} X_{G[V']} \cdot \nu^{V'} \; 
&= \; \prod_{i=1}^\infty \Bigl[ 1 + I_G(x_i \cdot \nu) \Bigr] \;
 = \; \exp \Bigl[ - \sum_{i=1}^\infty A_G^*(-x_i \cdot \nu) \Bigr], \cr
1 + \sum_{\emptyset \subset V' \subseteq V} \omega \bigl( X_{G[V']} \bigr) \cdot \nu^{V'} \; 
&= \; \prod_{i=1}^\infty \Bigl[ 1 + A_G(x_i \cdot \nu) \Bigr] \;
 = \; \exp \Bigl[ \sum_{i=1}^\infty A_G^*(x_i \cdot \nu) \Bigr].\qeda \cr
}$$

\bigskip

Selon Stanley~[30], une s\'erie formelle $p = p(x,y)$ en deux ensembles de variables $x = (x_1,x_2,x_3,\dots)$ et 
$y = (y_1,y_2,y_3,\dots)$ est appel\'ee {\it fonction supersym\'etrique} si et seulement si $p$ est sym\'etrique 
par rapport aux variables $x_i$ et $y_j$ et 
$$
p(x,y)\bigr|_{y_1 = -x_1} \; = \; p(x,y)\bigr|_{y_1 = x_1 = 0}.
$$
Notons $\omega_y$ l'involution $\omega$ n'agissant que sur les variables $y$ en supposant que $x_1,x_2,x_3,\dots$ sont des
constants. Si $p(x)$ est une fonction sym\'etrique, d\'efinissons la {\it superfication} $p(x/y)$ de~$p$ par
$$
p(x/y) \; := \; \omega_y \bigl( p(x,y) \bigr),
$$
c'est-\`a-dire en rempla\c cant les variables $x_1,x_2,\dots$ par $x_1,x_2,\dots,y_1,y_2,\dots$ (c'est une soi-disante {\it addition 
des deux alphabets}) et en utilisant $\omega_y$ ensuite. 
Pour les fonctions sym\'etriques de Stanley et de Chow, notre th\'eor\`eme 6.2 donne le r\'esultat suivant.

\medskip

\noindent
{\sc Th\'eor\`eme 6.3.} {\it Soient $f,g: 2^V \to A$ telles que $f(\emptyset) = g(\emptyset) = 0$, alors on a}
$$\openup2pt\eqalign{
1 + \sum_{\emptyset \subset V' \subseteq V} ST_{f,V'}(x/y) \cdot \nu^{V'} \; 
&= \; \prod_{i=1}^\infty {1 + F_f (x_i \cdot \nu) \over 1 + F_f (- y_i \cdot \nu) }, \cr
1 + \sum_{\emptyset \subset V' \subseteq V} CH_{g,V'}(x/y) \cdot \nu^{V'} \; 
&= \; \exp \Bigl[ \sum_{i=1}^\infty \Bigl( F_g (x_i \cdot \nu) - F_g (- y_i \cdot \nu) \Bigr) \Bigr].\qeda \cr
}$$

\bigskip

Le th\'eor\`eme pr\'ec\'edent implique imm\'ediatement le corollaire suivant, qui exprime le th\'eor\`eme~4.3 de~[30] dans le 
langage des fonctions d'ensembles. La d\'emonstration propos\'ee par Stanley est la plus longue de tout l'article~[30]
et utilise les fonctions de Schur.

\medskip

\noindent
{\sc Corollaire 6.2.} (Stanley) {\it On a}
$$
1 + \sum_{\emptyset \subset V' \subseteq V} X_{G[V']}(x/y) \cdot \nu^{V'} \; = \; 
\Bigl( \prod_{i=1}^\infty \bigl[ 1 + I_G(x_i \cdot \nu) \bigr] \Bigr) \cdot
\Bigl( \prod_{i=1}^\infty \bigl[ 1 + A_G(y_i \cdot \nu) \bigr] \Bigr).\qeda
$$

\bigskip

\'Etudions finalement la th\`ese de Chow~[11] ou bien son article~[10]. Il est utile de noter nos alphabets $(x) = (x_1,x_2,\dots)$ et 
$(y) = (y_1,y_2,\dots)$ de sorte que $(-x) = (-x_1,-x_2,\dots)$ et $(-y) = (-y_1,-y_2,\dots)$. L'addition des alphabets $(x)+(y)$ 
d\'ej\`a introduite peut \^etre g\'en\'eralis\'ee en consid\'erant des combinaisons lin\'eaires quelconques $\lambda(x)+\mu(y)$,
$\lambda,\mu \in A$, o\`u il faut faire attention que $-(-x) \ne (x)$, puisque $(-x)$ est une multiplication des variables par 
$-1$ tandis que $-(x)$ est une soustraction de l'alphabet $(x)$ (voir~[22]). Le th\'eor\`eme suivant est \'evident ou bien une 
d\'efinition.

\bigskip

\noindent
{\sc Th\'eor\`eme 6.4.} {\it Soient $f,g: 2^V \to A$ telles que $f(\emptyset) = g(\emptyset) = 0$, alors on a pour tout 
$\lambda,\mu \in A$~:}
$$\openup2pt\eqalign{
1 + \sum_{\emptyset \subset V' \subseteq V} ST_{f,V'}\bigl[\lambda(x)+\mu(y)\bigr] \cdot \nu^{V'} \; 
&= \; \prod_{i=1}^\infty \Bigl[ \Bigl( 1 + F_f (x_i \nu) \Bigr)^\lambda \Bigl( 1 + F_f (y_i \nu) \Bigr)^\mu \Bigr], \cr
1 + \sum_{\emptyset \subset V' \subseteq V} CH_{g,V'}\bigl[\lambda(x)+\mu(y)\bigr] \cdot \nu^{V'} \; 
&= \; \exp \Bigl[ \sum_{i=1}^\infty \Bigl( \lambda \cdot F_g (x_i \nu) + \mu \cdot F_g (y_i \nu) \Bigr) \Bigr]. \cr
}$$
{\it En particulier,}
$$\openup2pt\eqalign{
\omega_y \Bigl( ST_{f,V'}\bigl[\lambda(x)+\mu(y)\bigr] \Bigr) \; &= \; ST_{f,V'}\bigl[\lambda(x)-\mu(-y)\bigr], \cr
ST_{f,V'}\bigl[(x)/(y)\bigr] \; &= \; ST_{f,V'}\bigl[(x)-(-y)\bigr], \cr
\omega \Bigl( ST_{f,V'}\bigl[(x)\bigr] \Bigr) \; &= \; ST_{f,V'}\bigl[-(-x)\bigr].\qeda \cr
}$$

\bigskip

Soient $\hbox{cyc}_G(\nu)$, $\hbox{lin}_G(\nu)$, $\hbox{cyc}_{\overline{G}}(\nu)$ et $\hbox{lin}_{\overline{G}}(\nu)$ quatre 
fonctions d'ensembles quelconques qui satisfont \`a l'identit\'e de Berge, c'est-\`a-dire au th\'eor\`eme~4.1. 
Nous d\'efinissons, pour chaque $\emptyset \subset V' \subseteq V$, la {\it fonction sym\'etrique de 
Chow-Stanley} $CS_{G[V']}\bigl[(x);(y)\bigr]$ par
$$
1 + \sum_{\emptyset \subset V' \subseteq V} CS_{G[V']}\bigl[(x);(y)\bigr] \cdot \nu^{V'} 
\; := \; \exp \Bigl[ \sum_{i=1}^\infty \hbox{cyc}_G(x_i \nu) \Bigr] \cdot
         \prod_{j=1}^\infty \Bigl[ 1 + \hbox{lin}_G(y_j \nu) \Bigr].
$$
Maintenant nous sommes en mesure de formuler notre g\'en\'eralisation du th\'eor\`eme principal de la th\`ese de Chow~[11].

\bigskip

\noindent
{\sc Th\'eor\`eme 6.5.} (Th\'eor\`eme de dualit\'e pour la fonction de Chow-Stanley) 

\smallskip
 
\noindent
{\it Pour tous $\lambda_c,\lambda_l,\mu_c,\mu_l \in A$, on a}
$$\openup2pt\eqalign{
&CS_{\overline{G}}\bigl[\lambda_c(x)+\mu_c(y);\lambda_l(x)+\mu_l(y)\bigr] \cr 
&= \; CS_G\bigl[\lambda_c(-x)+\mu_c(-y);-(\lambda_c+\lambda_l)(-x)-(\mu_c+\mu_l)(-y)\bigr]. \cr
}$$

\medskip

{\it D\'emonstration.} Dans le langage des fonctions d'ensembles, il s'agit de d\'emontrer l'identit\'e suivante, que nous 
\'etablissons \`a l'aide de l'identit\'e de Berge~:
$$\openup2pt\eqalign{
&\exp \Bigl[ \lambda_c \sum_{i=1}^\infty \hbox{cyc}_{\overline{G}}(x_i \nu) \Bigr] \cdot
 \exp \Bigl[ \mu_c     \sum_{j=1}^\infty \hbox{cyc}_{\overline{G}}(y_j \nu) \Bigr] \cdot \cr
&\Bigl( \prod_{i=1}^\infty \Bigl[ 1 + \hbox{lin}_{\overline{G}}(x_i \nu) \Bigr] \Bigr)^{\lambda_l} \cdot
 \Bigl( \prod_{j=1}^\infty \Bigl[ 1 + \hbox{lin}_{\overline{G}}(y_j \nu) \Bigr] \Bigr)^{\mu_l} \cr
= \; 
&\exp \Bigl[ \lambda_c \sum_{i=1}^\infty \hbox{cyc}_G(-x_i \nu) \Bigr] \cdot
 \exp \Bigl[ \mu_c     \sum_{j=1}^\infty \hbox{cyc}_G(-y_j \nu) \Bigr] \cdot \cr
&\Bigl( \prod_{i=1}^\infty \Bigl[ 1 + \hbox{lin}_G(-x_i \nu) \Bigr] \Bigr)^{-\lambda_c-\lambda_l} \cdot
 \Bigl( \prod_{j=1}^\infty \Bigl[ 1 + \hbox{lin}_G(-y_j \nu) \Bigr] \Bigr)^{-\mu_c-\mu_l} \cr
& \cr
\Leftrightarrow \qquad
&\Bigl( \exp \Bigl[ \sum_{i=1}^\infty 
        \bigl( \hbox{cyc}_{\overline{G}}(x_i \nu) - \hbox{cyc}_G(-x_i \nu) \bigr) \Bigr] \Bigr)^{\lambda_c} \cdot \cr
&\Bigl( \exp \Bigl[ \sum_{j=1}^\infty 
        \bigl( \hbox{cyc}_{\overline{G}}(y_j \nu) - \hbox{cyc}_G(-y_j \nu) \bigr) \Bigr] \Bigr)^{\mu_c} \cr
= \; 
&\Bigl( \prod_{i=1}^\infty \Bigl[ 1 + \hbox{lin}_G(-x_i \nu) \Bigr] \Bigr)^{-\lambda_c} \cdot
 \Bigl( \prod_{j=1}^\infty \Bigl[ 1 + \hbox{lin}_G(-y_j \nu) \Bigr] \Bigr)^{-\mu_c}.\qeda \cr
}$$

\bigskip

Posons $\lambda_c = \mu_l = 1$ et $\lambda_l = \mu_c = 0$ pour obtenir le th\'eor\`eme principal de la th\`ese de Chow~[11] et de
l'article~[10].

\medskip

\noindent
{\sc Corollaire 6.3.} (Chow) {\it On a}
$$\openup2pt\eqalign{
CS_{\overline{G}}\bigl[(x);(y)\bigr] \; 
&= \; CS_G\bigl[(-x);-(-x)-(-y)\bigr] \cr
&= \; \Bigl[ \omega_y \bigl( CS_G\bigl[(-x);(y)\bigr] \bigr) \Bigr]_{y \to (x,y)}.\qeda \cr
}$$

\bigskip

Chow a \'egalement trouv\'e un deuxi\`eme cas particulier du th\'eor\`eme 6.5, \`a savoir $\lambda_c = -2$, $\mu_c = 0$ et 
$\lambda_l = \mu_l = 1$. 

\medskip

\noindent
{\sc Corollaire 6.4.} (Chow) {\it On a}
$$\openup2pt\eqalign{
CS_{\overline{G}}\bigl[-2(x);(x)+(y)\bigr] \;
&= \; CS_G\bigl[-2(-x);(-x)-(-y)\bigr] \cr
&= \; \omega_y \bigl( CS_G\bigl[-2(-x);(-x)+(y)\bigr] \bigr).\qeda \cr
}$$

\bigskip

Tous les autres cas du th\'eor\`eme 6.5 sont nouveaux. De notre point de vue, cependant, le th\'eor\`eme 6.5 et l'identit\'e de 
Berge sont aussi des corollaires imm\'ediats des r\'esultats de Chow. Par ailleurs, Chow~[10, paragraphe~6] a pos\'e la question 
de mieux comprendre le r\^ole des inversions qu'il a consid\'er\'ees. Il nous semble, que l'addition des alphabets r\'epond 
parfaitement \`a cette question. Au moins, il devient \'evident qu'il s'agit bien d'inversions, un fait que Chow a d\^u 
d\'emontrer. 

Remarquons finalement, que Gessel a aussi imagin\'e une d\'emonstration de l'iden\-tit\'e 
$$
CS_{\overline{G}}\bigl[0;(y)\bigr] \; = \; \omega_y \bigl( CS_G\bigl[0;(y)\bigr] \bigr),
$$
qui se trouve dans l'intersection des deux r\'esultats de Chow. Cette preuve de Gessel reproduite dans~[10], cependant, 
s'\'etend, elle aussi, sur plus d'une page tout en utilisant les fonctions de Schur.


\bigskip
\bigskip
\bigskip


{\it Remerciements.} En tout premier lieu, je tiens \`a remercier D.~Foata de toute son aide et assistance et notamment de ses 
explications stimulantes en ce qui concerne l'article~[16]. 
Mes remerciements vont aussi \`a A.~Lascoux, qui m'a recommand\'e, lors du magnifique S\'eminaire Lotharingien de Combinatoire~44
au Domaine Saint-Jacques, son article~[22] \lfq sur l'importance de l'addition dans l'\oe uvre math\'ematique de Gian-Carlo Rota\rfq.
C'est ainsi que je me suis rendu compte de l'importance de la soustraction (des alphabets) dans les \oe uvres de T.~Chow et de 
R.~Stanley.



\bigskip
\bigskip
\bigskip


%%%%%%%%%%%%%%%%%%%%%%%
%%   BIBLIOGRAPHIE   %%
%%%%%%%%%%%%%%%%%%%%%%%

\centerline{\bf R\'ef\'erences bibliographiques}

\medskip

{\baselineskip=9pt\tenrm
\item{[1]} M.~Aigner, \lfq Combinatorial Theory\rfq, Springer-Verlag, Heidelberg, 1979.
\smallskip

\item{[2]} O.~M.~D'Antona et E.~Munarini, The cycle-path indicator polynomial of a digraph,
           {\it Advances in Appl.~Math.}~{\bf 25} (2000), 41-56. 
\smallskip

\item{[3]} R.~Askey et G.~Gasper, Convolution structures for Laguerre polynomials, 
           {\it J. Analyse Math.}~{\bf 31} (1977), 48--68. 
\smallskip

\item{[4]} R.~Askey et M.~Ismail, Permutation problems and special functions, 
           {\it Canad.~J. Math.}~{\bf 28} (1976), 853-874. 
\smallskip

\item{[5]} R.~Askey, M.~Ismail et T.~Koornwinder, Weighted permutation problems and Laguerre Polynomials, 
           {\it J.~Combin.~Theory Ser.~A}~{\bf 25} (1978), 277-287. 
\smallskip

\item{[6]} C.~Berge, \lfq Graphes\rfq, Bordas, Paris, 1983.
\smallskip

\item{[7]} C.~Berge, Chemins hamiltoniens, ICC Research Report n$^o$ 67/2, 1967.
\smallskip

\item{[8]} P.~Camion, Hamiltonian chains in self-complementary graphs, 
           {\it Cahiers Centre \'Etudes Recherche Op\'er.}~{\bf 17} (1975), 173-183. 
\smallskip

\item{[9]} T.~Chow, A short proof of the rook reciprocity theorem, 
           {\it Electronic J.~Combin.}~{\bf 3} (1996), R10. 
\smallskip

\item{[10]} T.~Chow, The path-cycle symmetric function of a digraph,
           {\it Advances in Math.} {\bf 118} (1996), 71-98. 
\smallskip

\item{[11]} T.~Chow, \lfq Symmetric Function Generalizations of Graph Polynomials\rfq,  
           Ph.D. Thesis, MIT, 1995. 
\smallskip

\item{[12]} F.~R.~K.~Chung et R.~L.~Graham, On the cover polynomial of a digraph, 
           {\it J.~Combin.~Theory Ser.~B}~{\bf 65} (1995), 273-290.
\smallskip

\item{[13]} P.~Doubilet, G.-C.~Rota, R.~Stanley, On the foundations of combinatorial theory (VI), dans~: 
           Proceedings of the Sixth Berkely Symposium on Mathematical Statistics and Probability, v.~II, 
           University of California Press, Berkeley (1972), 267-318.            
\smallskip

\item{[14]} S.~Even et J.~Gillis, Derangements and Laguerre polynomials, 
           {\it Math.~Proc.~Camb. Phil.~Soc.}~{\bf 79} (1976), 135-143. 
\smallskip

\item{[15]} D.~Foata et M.-P.~Sch\"utzenberger, On the rook polynomials of Ferrers relations, 
           dans~: Combinatorial Theory and its Applications, vol.~2 (P.~Erd\"os, A.~Renyi et V.~T.~S\'os, eds.),
           {\it Colloq.~Math.~Soc.~J\'anos Bolyai}~{\bf 4} (1970), North-Holland, Amsterdam, 431-436. 
\smallskip

\item{[16]} D.~Foata et D.~Zeilberger, Laguerre polynomials, weighted derangements and positivity,
           {\it SIAM J.~Disc.~Math.}~{\bf 1} (1988), 425-433.
\smallskip

\item{[17]} C.~D.~Godsil, \lfq Algebraic Combinatorics\rfq, Chapman \& Hall, New York, 1993. 
\smallskip 

\item{[18]} C.~D.~Godsil, Hermite polynomials and a duality relation for matchings polynomials, 
           {\it Combinatorica}~{\bf 1} (1981), 257-262. 
\smallskip

\item{[19]} J.~R.~Goldman, J.~T.~Joichi, D.~E.~White, Rook theory I, Rook equivalence of Ferrers boards,
           {\it Proc.~Amer.~Math.~Soc.}~{\bf 52} (1975), 485-492. 
\smallskip

\item{[20]} D.~M.~Jackson, Laguerre polynomials and derangements, 
           {\it Math.~Proc.~Camb. Phil.~Soc.}~{\bf 80} (1976), 213-214. 
\smallskip

\item{[21]} S.~A.~Joni et G.-C.~Rota, A vector space analog of permutations with restricted position, 
           {\it J.~Combinatorial Theory, Series A}~{\bf 29} (1980), 59-73. 
\smallskip

\item{[22]} A.~Lascoux, Couper les alphabets en quatre, http://phalanstere.univ-mlv.fr/~al/;
            version anglaise~: Alphabet splitting, dans~: Algebraic Combinatorics and Computer Science, A Tribute to
            Gian-Carlo Rota (H.~Crapo et D.~Senato, eds.), Springer-Verlag, Milano (2001), 431-444.
\smallskip

\item{[23]} B.~Lass, Orientations acycliques et le polyn\^ome chromatique, 
           {\it Europ.~J.~Combinatorics}~{\bf 22} (2001), 1101-1123. 
\smallskip 

\item{[24]} L.~Lov\'asz, \lfq Combinatorial Problems and Exercises\rfq, Akad\'emiai Kiad\'o, Budapest, 1993.
\smallskip

\item{[25]} I.~G.~Macdonald, \lfq Symmetric Functions and Hall Polynomials\rfq, Clarendon Press, Oxford, 1979.
\smallskip

\item{[26]} J.~W.~Moon, \lfq Topics on tournaments\rfq, Holt, Rinehart and Winston, New York-Montreal, 1968.
\smallskip

\item{[27]} S.~B.~Rao, The number of open chains of length three and the parity of the number of open chains of length~$k$
           in self-complementary graphs,
           {\it Discrete Math.}~{\bf 28} (1979), 291-301.
\smallskip 

\item{[28]} J.~Riordan, \lfq An Introduction to Combinatorial Analysis\rfq, Wiley, New York, 1958.
\smallskip

\item{[29]} M.~de Sainte-Catherine et G.~Viennot, Combinatorial interpretation of integrals of products of Hermite, Laguerre
           and Tchebycheff polynomials, dans~: Polyn\^omes orthogonaux et applications (C.~Brezinski, et al., eds.), Bar-le-Duc,
           1984, {\it Lecture Notes in Mathematics}~{\bf 1175} (1985), Springer-Verlag, Berlin, 120-128.
\smallskip           

\item{[30]} R.~P.~Stanley, A symmetric function generalization of the chromatic polynomial of a graph, 
           {\it Advances in Math.}~{\bf 111} (1995), 166-194.
\smallskip 

\item{[31]} R.~P.~Stanley, \lfq Enumerative Combinatorics\rfq, Volume 1, Cambridge University Press, Cambridge, 1997.
\smallskip 

\item{[32]} R.~P.~Stanley, \lfq Enumerative Combinatorics\rfq, Volume 2, Cambridge University Press, Cambridge, 1999.
\smallskip 

\item{[33]} T.~Szele, Kombinatorische Untersuchungen \"uber gerichtete vollst\"andige Gra\-phen, 
           {\it Publ.~Math.~Debrecen}~{\bf 13} (1966), 145-168.
\smallskip 

\item{[34]} G.~Viennot, \lfq Une th\'eorie combinatoire des polyn\^omes orthogonaux g\'en\'eraux\rfq, 
           Notes de con\-f\'erences donn\'ees \`a l'Universit\'e du Qu\'ebec \`a Montr\'eal, 1983. 
\smallskip 
}
\end
