%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \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 \space to replace it with another command,^^Jor \space \space to continue without it.} \def\@ehb{You've lost some text. \space \@ehc} \def\@ehc{Try typing \space \space to proceed.^^JIf that doesn't work, type \space X \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 \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