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


\magnification=1100
\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= 22.5cm
\hsize= 14.0cm
\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 %%
%%%%%%%%%%%%%%%%%%%%%%%%

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


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

\auteurcourant{\eightbf Bodo Lass \hfill}

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

\titrecourant{\hfill\eightbf Orientations acycliques}


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

{\parindent=0pt\eightbf
Europ.~J.~Combinatorics~22, 1101--1123, 2001 
}


\vskip 1.5cm

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

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

\centerline
{\fourteenbf
Orientations acycliques et le polyn\^ome chromatique
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  Subject Classification               %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\parindent=-1mm\footnote{}{
{\it Mots cl\'es:} graphe, polyn\^ome chromatique, orientation acyclique, source, puits, invariant de Crapo}

\vskip 20pt

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

\centerline{\bf BODO LASS}



\bigskip
\medskip



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

\noindent
{\eightrm On attache \`a tout graphe $\scs G$ son polyn\^ome chromatique $\scs \chi_G(\lambda)$, qui d\'enombre ses colorations 
r\'eguli\`eres avec $\scs \lambda$ couleurs. D'apr\`es Stanley, on sait que $\scs |\chi_G(-1)|$ est \'egal au nombre d'orientations 
acycliques du graphe, un r\'esultat qui fut raffin\'e par Greene et Zaslavsky. Nous nous proposons de l'affiner davantage en 
interpr\'etant, avec l'aide de certaines orientations acycliques, les coefficients de $\scs \chi_G(\lambda)$ d\'evelopp\'e 
en puissances de $\scs \lambda$ et surtout en puissances de $\scs (\lambda-1)$. L'utilisation syst\'ematique des fonctions 
g\'en\'eratrices des fonctions d'ensembles permet d'avoir des d\'emonstrations tr\`es courtes et explicatives. Elles se 
veulent une r\'eponse \`a la suggestion faite par Gebhard et Sagan, qui ont d\'ej\`a trouv\'e des d\'emonstrations 
combinatoires de deux r\'esultats de Greene et Zaslavsky. Les fonctions d'ensembles permettent aussi d'\'etablir  
une s\'erie d'interpr\'etations nouvelles de l'invariant~$\scs \beta_G$ de Crapo. Cet article donne \'egalement
un nouvel \'eclat aux r\'esultats classiques de Cartier, Foata, Viennot, Brenti, Gessel et Stanley.}

\medskip

\noindent
{\eightrm
The chromatic polynomial $\scs \chi_G(\lambda)$, which is associated with each graph $\scs G$, enumerates its regular colorations 
with $\scs \lambda$ colors. Stanley showed that $\scs |\chi_G(-1)|$ is equal to the number of acyclic orientations of the graph, 
a result that was refined by Greene and Zaslavsky. The purpose of the paper is to show that a further refinement can be obtained 
by interpreting each coefficient of $\scs \chi_G(\lambda)$, when the polynomial is developed with respect to powers of 
$\scs \lambda$ and $\scs (\lambda-1)$. A systematic use of the generating functions for set functions enables us to 
have very short and instructive proofs. Gebhard and Sagan, who had already found combinatorial proofs of two 
results by Greene and Zaslavsky, suggested that further proofs were to be found. Finally, the set functions 
algebra allows us to establish a series of new interpretations for Crapo's $\scs \beta_G$ invariant. This 
paper also brings a new light to the classical results due to Cartier, Foata, Viennot, Brenti, Gessel and 
Stanley.}

\vskip1.5pt


\parindent=3mm
\vskip 5mm


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


\centerline{\bf 1. Introduction}

\medskip

Soit $G = (V,E)$ un graphe fini non-orient\'e. Une {\it orientation} de $G$ est un graphe orient\'e obtenu \`a partir de $G$ 
en rempla\c cant chaque ar\^ete $e \in E$ par un des deux arcs (i.~e.~ar\^etes orient\'ees) possibles. L'orientation est
{\it acyclique} si elle ne contient pas de cycles orient\'es. \'Evidemment, le nombre d'orientations acycliques est \'egal \`a
z\'ero si $G$ contient une boucle (et \'egal \`a 1 si $G$ ne contient aucune ar\^ete). De plus, des ar\^etes multiples de $G$ 
doivent toutes \^etre orient\'ees de la m\^eme fa\c con pour que l'orientation devienne acyclique. Voil\`a pourquoi on peut 
supposer, sans restreindre la g\'en\'eralit\'e, que $G$ est simple, c'est-\`a-dire qu'il ne contient ni boucles ni 
ar\^etes multiples, lorsqu'on s'int\'eresse aux orientations acycliques.

On appelle {\it puits} (resp.~{\it source}) d'une orientation de $G$ un sommet qui n'est l'extr\'emit\'e {\it initiale} 
(resp.~{\it terminale}) d'aucun arc.
Apparemment, de quelque fa\c con que l'on choisisse une orientation de $G$, {\it chaque sommet isol\'e de $G$ est
toujours \`a la fois un puits et une source}, un fait qui n\'ecessite une prise en charge particuli\`ere des
sommets isol\'es lorsqu'il faut regarder des puits et des sources en m\^eme temps.

\medskip

Une coloration $c: V \to \{1,2,\dots,\lambda\}$ de $G$ avec $\lambda$ couleurs est dite {\it r\'eguli\`ere} 
si les deux extr\'emit\'es de chaque ar\^ete ont des couleurs diff\'erentes, c'est-\`a-dire 
$\{u,v\} \in E \; \Rightarrow \; c(u) \neq c(v)$. Soit $\chi_G(\lambda)$ le nombre de ces colorations. 
C'est un des faits les plus classiques de la th\'eorie des graphes (d\'ecoulant \`a plusieurs reprises de cet article) 
que $\chi_G(\lambda)$ est un polyn\^ome en $\lambda$ de degr\'e $\bf n := |V|$, appel\'e {\it polyn\^ome chromatique}. 
\'Evidemment, $\chi_G(\lambda) = 0$ si $G$ contient une boucle, et de nouveau on peut se cantonner aux graphes simples 
pour \'etudier le polyn\^ome chromatique.

\medskip

Les similarit\'es constat\'ees entre les orientations acycliques et le polyn\^ome chromatique ne sont pas une co\"\i ncidence.
En fait, si
$$
\chi_G(\lambda) \; = \; \lambda^n - c_{n-1} \cdot \lambda^{n-1} + c_{n-2} \cdot \lambda^{n-2} - \dots + (-1)^{n-1}c_1 \cdot \lambda,
$$
alors il est classique que $c_1$, $c_2$, \dots, $c_{n-1}$ sont des entiers positifs; et gr\^ace \`a Stanley~[21], on sait que
$c_1 + c_2 + \dots + c_{n-1} + 1$ d\'enombre effectivement les orientations acycliques de~$G$. 

\medskip

Ceci soul\`eve imm\'ediatement la question de savoir s'il est possible de partitionner, de fa\c con canonique, l'ensemble des 
orientations acycliques en blocs de cardinalit\'es $c_1$, $c_2$, \dots, $c_{n-1}$, $1$. En effet, si les sommets de $G$ 
sont num\'erot\'es, c'est-\`a-dire $V = \{1,2,\dots,n\}$, alors une telle partition est possible en attachant, \`a 
chaque orientation acyclique, une partition de~$V$ constitu\'ee par $k$~blocs, appel\'es {\it composantes} de 
l'orientation acyclique. 
La m\^eme construction de ces composantes fut imagin\'ee par Greene et Zaslavsky~[12] (dans un contexte g\'eom\'etrique)
et par Viennot~[27] (dans le cadre des empilements de pi\`eces). Un des buts de cet article est de populariser leur 
r\'esultat, qui est rest\'e plut\^ot inconnu sauf pour le cas d'une seule composante~: le fait que $c_1$ d\'enombre 
les orientations acycliques d'une seule composante (ce sont par d\'efinition les orientations acycliques dont le 
sommet $1$ est la seule source) se trouve dans~[4] et dans le livre r\'ecent de Bollob\'as~[1] 
(chapitre~X, th\'eor\`eme~8), par exemple. 

Suivons Sachs ([20], chapitre V.9.2) et appelons $\alpha_G := c_1$ {\it discriminant chromatique} du graphe~$G$.
Les nombres $c_1$, $c_2$, \dots, $c_{n-1}$ sont d\'efinis ind\'ependamment de la num\'erotation choisie et du
fait que l'on s'int\'eresse aux sources ou plut\^ot aux puits des orientations acycliques. Voil\`a pourquoi
$\alpha_G$ compte les orientations acycliques de~$G$ dont un sommet fix\'e est la seule source (ou bien le 
seul puits). 
C'\'etait le leitmotif de l'article~[9] de Gebhard et Sagan de donner trois preuves nouvelles de ce th\'eor\`eme de
Greene et Zaslavsky~[12], que ces derniers avaient d\'emontr\'e en s'appuyant sur les arrangements d'hyperplans.

\medskip

Supposons maintenant que $G$ est connexe de sorte que $\alpha_G$ est strictement positif. Il est classique (voir [26], 
chapitre IX.2) que le polyn\^ome chromatique admet alors le d\'eveloppe\-ment
$$
\chi_G(\lambda) \; = \; \lambda \cdot 
\bigl[(\lambda-1)^{n-1} - b_{n-2} \cdot (\lambda-1)^{n-2} + \dots + (-1)^n b_1 \cdot (\lambda-1)\bigr],
$$
o\`u $b_1$, $b_2$, \dots, $b_{n-2}$ sont des entiers positifs correspondant \`a certains coefficients du polyn\^ome de 
Tutte. Les nombres $b_1$, $b_2$, \dots, $b_{n-2}$ sont probablement les invariants les plus petits (i.~e.~les plus
puissants) que l'on peut associer \`a tout graphe (connexe) \`a partir de son polyn\^ome chromatique. 
Leur positivit\'e implique en particulier une unimodalit\'e partielle des coefficients {\lfq ordinaires\rfq} de $\chi_G(\lambda)$,
\`a savoir $1 \le c_{n-1} \le c_{n-2} \le \dots \le c_{\lceil n/2 \rceil}$ (voir~[1], chapitre~X, th\'eor\`eme~13).
Num\'erotons les sommets du graphe~$G$. Il est \'evident que
$$
b_1 + b_2 + \dots + b_{n-2} + 1 \; = \; \alpha_G
$$
d\'enombre les orientations acycliques de~$G$ dont le sommet~$1$ est le seul puits; et la question se pose si l'on peut,
de nouveau, trouver une partition canonique de l'ensemble de ces orientations en blocs de cardinalit\'es
$b_1$, $b_2$, \dots, $b_{n-2}$, $1$. Une telle partition existe effectivement, et de surcro\^\i t, c'est 
la m\^eme que nous connaissons d\'ej\`a~: $b_k$ compte le nombre d'orientations acycliques de~$G$ de 
$k+1$~composantes, dont le puits unique est \'egal \`a $1$, si (et seulement si) la num\'erotation
des sommets refl\`ete bien la connexit\'e du graphe.
Ce r\'esultat risque d'\^etre absolument inconnu, puisque la positivit\'e des nombres $b_1$, $b_2$, \dots, $b_{n-2}$ constitue 
la premi\`ere moiti\'e du th\'eor\`eme principal de l'article tout r\'ecent~[10] de Gessel, mais pour la d\'emonstration,
le lecteur est renvoy\'e \`a la litt\'erature (i.~e.~au polyn\^ome de Tutte), bien que le sujet dudit article 
soient des relations entre colorations et orientations acycliques~! 

Dans le cas particulier de l'{\it invariant $\beta_G := b_1$ de Crapo}~[6] cependant, on retrouve le th\'eor\`eme classique
de Greene et Zaslavsky~[12] qui, gr\^ace aux arrangements d'hyperplans, ont indentifi\'e $\beta_G$ comme nombre
d'orientations acycliques de $G$ n'ayant qu'une seule source et un seul puits, \`a savoir les deux sommets
adjacents $2$ et $1$, respectivement. 
Gebhard et Sagan ont trouv\'e une preuve par induction de ce fait et ont pens\'e que le r\'esultat m\'eriterait d'autres 
d\'emonstrations (voir~[9]). 
Cet article se veut, entre autres, une r\'eponse \`a leur suggestion. Nous donnons, en effet, une s\'erie 
d'interpr\'etations apparemment nouvelles (incluant celle de Greene et Zaslavsky) de $\beta_G$, et nous les 
d\'emontrons avec l'aide de l'alg\`ebre des fonctions d'ensembles. 

\bigskip

En fait, de notre point de vue, l'int\'er\^et principal de cet article consiste en l'exploration de la m\'ethode des fonctions 
g\'en\'eratrices dans le pr\'esent contexte, m\'ethode qui a d\'ej\`a fait ses preuves dans beaucoup de situations diff\'erentes 
(voir~[14]). Chacun de nos th\'eor\`emes s'obtient effectivement comme sp\'ecialisation d'une identit\'e dans l'alg\`ebre des 
fonctions d'ensembles et le passage entre ces diff\'erentes identit\'es se fait toujours en quelques lignes. 
Ceci permet notamment de trouver des nouvelles d\'emonstrations, tr\`es courtes et explicatives, des deux th\'eor\`emes de Greene 
et Zaslavsky mentionn\'es ci-dessus ainsi que de celui de Stanley sur $|\chi_G(-1)|$.

Il nous semble particuli\`erement surprenant que chacune de nos identit\'es admettant une g\'en\'eralisation {\it non-commutative} 
appara\^\i t d\'ej\`a dans les travaux de Cartier-Foata~[5], Foata~[7] et Gessel~[10]. De plus, c'est Gessel (voir~[27], pages 343-344)
qui a montr\'e (sur toute une page \`a l'\'epoque) comment on peut d\'eduire le r\'esultat de Stanley du th\'eor\`eme de Cartier et 
Foata (voir~[5]) sur l'inversion (de M\"obius) dans le mono\"\i de de commutation. 
En fait, de notre point de vue, ce th\'eor\`eme de Cartier et Foata devient une g\'en\'eralisation non-commutative directe du 
th\'eor\`eme de Stanley~[21] sans aucune d\'emonstration suppl\'ementaire. Ceci montre \`a quel point le livre de Cartier et 
Foata \'etait visionnaire~!

Cependant, pour aller plus loin dans le sens des th\'eor\`emes de Greene et Zaslavsky qui font intervenir des interpr\'etations 
combinatoires du logarithme, il semble falloir se cantonner au cas {\it commutatif}. Cette n\'ecessit\'e fut d'abord
r\'ev\'el\'ee par Viennot (voir~[27], proposition 5.10), qui a, de plus, \'etabli l'\'equivalence du mod\`ele de Cartier et Foata 
avec son mo\-d\`ele des empilements de pi\`eces ainsi que, notamment, avec notre mod\`ele pr\'ef\'er\'e, \`a savoir les 
orientations acycliques d'un graphe (voir [27], page 325, c)). Gr\^ace \`a cette \'equivalence, les th\'eor\`emes~3.2 
et~5.1 de cet article deviennent effectivement des g\'en\'eralisations ou plut\^ot des raffinements de la 
proposition~5.10 de~[27]. 

\medskip

Apr\`es avoir expliqu\'e notre m\'ethode alg\'ebrique dans le paragraphe~2, nous l'appliquons pour le traitement du polyn\^ome 
chromatique et des orientations acycliques dans les paragraphes 3, 4, 5 et 6. 
Trois appendices sont consacr\'es \`a la discussion, dans notre optique, des travaux de Cartier, Foata, Gessel, Viennot et Stanley 
mentionn\'es ci-dessus. En outre, nous consid\'erons bri\`evement les d\'eveloppements du polyn\^ome chromatique obtenus par 
Brenti, les graphes al\'eatoires \'etudi\'es par Welsh~[28] et la fonction (sym\'etrique) chromatique de Stanley (voir~[22]).



\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 fonction d'ensembles, o\`u $A$ est un anneau commutatif (avec $1$). 

\noindent
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'iso\-morphisme
$$
A[V] \; \simeq \; A[v_1,\dots,v_n]/ \langle v_1^2,\dots,v_n^2 \rangle,
$$
si $V$ contient $n$ \'el\'ements.

\medskip

\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'}.
$$

\smallskip

\noindent
{\sc Remarque 2.1.} Dans~[14], les projections canoniques furent utilis\'ees pour d\'emontrer des propositions 
par analogie avec les propositions 3.2 et 4.1 de cet article. Deux de ces r\'esultats sont directement \'equivalents
\`a la proposition~5.3 de~[27] et au lemme~1.2 de~[2]. Cependant, l'interaction des projections avec l'analyse est 
moins int\'eressante. C'est pourquoi elles ne sont plus employ\'ees ici. 

\bigskip

\noindent
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.2.} 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)$. 

\medskip

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.

\medskip

\noindent
{\sc Remarque 2.3.} 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
Pour $\emptyset \subseteq V' \subseteq V$, posons 
$$
\partial^{V'} \; := \; \prod_{v \in V'} \partial^v, \;\; \hbox{i.~e.} \qquad 
\partial^{V'} \nu^{V''} \; = \;
\openup 2pt\left\{\eqalign{
            \nu^{V''}, \quad & \hbox{si} \quad V' \subseteq V'', \cr
            0, \;\;\;  \quad & \hbox{sinon;} \cr
}\right. 
$$            
en particulier, $\partial^{\emptyset}$ est l'identit\'e. Comme $(\partial^v)^2 = \partial^v$ pour tout $v \in V$, on a
$$
\partial^{V'}\partial^{V''} \; = \; \partial^{V' \cup V''}, \quad V',V'' \subseteq V.
$$
Les op\'erateurs diff\'erentiels n'\'etant pas des combinaisons lin\'eaires des d\'erivations d'\'el\'ements $\partial^v$,
$v \in V$, ne satisfont pas aux formules de d\'erivation ordinaires. En s'appuyant sur la d\'efinition 
$\partial^{V'} := \prod_{v \in V'} \partial^v$, cependant, on peut calculer des r\`egles sp\'ecifiques pour eux :

\bigskip

\noindent
{\sc Proposition 2.1.}

\medskip

\noindent
a) {\it Soient $f,g: 2^V \to A$ des fonction d'ensembles, et soit $V' \subseteq V$ fix\'e. Alors}
$$
\partial^{V'} [F_f (\nu) \cdot F_g (\nu) ] \; = \sum_{\emptyset \subseteq V'' \subseteq V'} 
                                                \partial^{V''} F_f (\nu) \cdot \partial^{V' \backslash V''} F_g (\nu).
$$

\smallskip

\noindent
b) {\it Soient $s,p \in V$, et soit $G \in A![[V]]$. Alors}
$$
\partial^{\{s,p\}} [G(F_f (\nu))] \; = \;\;  G''(F_f (\nu)) \cdot \partial^s F_f (\nu) \cdot \partial^p F_f (\nu) \; + \; 
                                             G'(F_f (\nu)) \cdot \partial^{\{s,p\}} F_f (\nu). 
$$

\smallskip

\noindent
c) {\it Soit $t$ une variable (ou $t \in A$) et posons 
   $\displaystyle D(t) \; := \; \sum_{\emptyset \subseteq V' \subseteq V} t^{|V'|}\partial^{V'}$. Alors}
$$\openup2pt\eqalign{
D(t) [F_f (\nu) \cdot F_g (\nu) ] \; &= \; D(t) F_f (\nu) \; \cdot \; D(t) F_g (\nu); \quad puisque \cr
                   D(t) F_f (\nu) \; &= \; F_f ((t+1)\nu).\qeda \cr
}$$


                              
\bigskip
\bigskip

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
                                                       %     
%  Orientations acycliques et ensembles ind\'ependants   %
%
                                                       %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\centerline{\bf 3. Orientations acycliques et ensembles ind\'ependants~:}

\centerline{\bf sources ou puits}

\bigskip

Pour tout $\emptyset \subset V' \subseteq V$, soit $G[V']$ le sous-graphe de $G = (V,E)$ engendr\'e par~$V'$~: 
c'est le graphe dont les sommets sont les points de $V'$, et dont les ar\^etes sont les ar\^etes de $G$ 
ayant leurs deux extr\'emit\'es dans $V'$. Un sous-ensemble $I$ de sommets est dit {\it ind\'ependant}, si
le sous-graphe engendr\'e par $I$ ne contient aucune ar\^ete.

Une coloration $c: V \to \{1,2,\dots,\lambda\}$ de $G$ avec $\lambda$ couleurs est {\it r\'eguli\`ere} (voir l'introduction)
si et seulement si, pour tout $i \in \{1,2,\dots,\lambda\}$, le sous-ensemble $c^{-1}(i)$ est un ensemble de sommets 
ind\'ependant (ou vide). 
{\it Voil\`a pourquoi une coloration r\'eguli\`ere avec $\lambda$ couleurs n'est rien d'autre qu'une partition de $V$ 
en $\lambda$ ensembles ind\'ependants, dont chacun peut \^etre vide.}

\medskip

Soit $I_G(\nu)$, $I_G(0) = 0$, la fonction indicatrice des sous-ensembles ind\'ependants de $G$ (la valeur de cette fonction 
indicatrice sur $V'$, $\emptyset \subset V' \subseteq V$, est \'egal \`a 1, si
$G[V']$ ne contient aucune ar\^ete, et \'egal \`a 0 sinon)~:
$$
{} \;\;\; I_G(\nu) \; := \sum_{\emptyset \subset I \subseteq V, \;\; I \; \hbox{\eightrm ind\'ependant}} \nu^I;
$$
et posons
$$
\chi_{G,\lambda}(\nu) \; := \sum_{\emptyset \subset V' \subseteq V} \chi_{G[V']}(\lambda) \cdot \nu^{V'},
$$
o\`u $\chi_{G[V']}(\lambda)$ d\'esigne le polyn\^ome chromatique (c'est-\`a-dire le nombre de colo\-rations r\'eguli\`e\-res 
avec $\lambda$ couleurs) de $G[V']$. 

\medskip

Rappelons que le coefficient lin\'eaire de $\chi_G(\lambda)$ multipli\'e par $(-1)^{n-1}$, i.~e.~$(-1)^{n-1}\chi'_G(0)$, 
est appel\'e discriminant chromatique et not\'e $\alpha_G$; et g\'en\'eralisons la d\'efinition de l'invariant de Crapo donn\'ee
dans l'introduction en posant $\beta_G := (-1)^{n+i}\chi'_G(1)$, o\`u $i$ d\'esigne le nombre de sommets isol\'es de $G$. 
Le lecteur familier avec $\beta_G$ verra facilement que cette d\'efinition est \'equivalente \`a la sienne, si $G$ contient
au moins une ar\^ete. Si $G$ ne contient aucune ar\^ete, on obtient $\beta_G = n$, une d\'efinition artificielle qui sera
modifi\'ee ci-dessous. 

\'Evidemment, nous utilisons les m\^emes d\'efinitions pour tous les sous-graphes engendr\'es,
notant en particulier $i(G[V'])$ le nombre de sommets isol\'es de $G[V']$.

\medskip

Puisqu'une multiplication dans l'alg\`ebre $A[V]$ avec $\lambda$ facteurs compte des partitions en $\lambda$ ensembles, 
on a l'identit\'e fondamentale (un facteur 1 correspond au fait qu'on peut choisir l'ensemble vide pour la couleur 
correspondante, i.~e.~ne pas utiliser cette couleur pour la coloration), que nous reproduisons dans la proposition 
suivante.

\bigskip

\noindent
{\sc Proposition 3.1.} {\it On a}
$$\openup2pt\eqalign{
                             1+\chi_{G,\lambda}(\nu) \; &= \; [1+I_G(\nu)]^{\lambda}, \cr
\hbox{$\frac{d}{d\lambda}$}[1+\chi_{G,\lambda}(\nu)] \; &= \; [1+I_G(\nu)]^{\lambda} \cdot \log[1+I_G(\nu)]; \cr
}$$
{\it et, en particulier, pour le discriminant chromatique $\alpha_G$ et l'invariant de Crapo $\beta_G$, on a~:}
$$\openup2pt\eqalign{
-\log[1+I_G(-\nu)] \; 
&= \; \sum_{\emptyset \subset V' \subseteq V} \alpha_{G[V']} \cdot \nu^{V'}, \cr
[1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)] \; 
&= \; \sum_{\emptyset \subset V' \subseteq V} (-1)^{i(G[V'])}\beta_{G[V']} \cdot \nu^{V'}.\qeda \cr
}$$

\bigskip

\noindent
{\sc Exemple 3.1.} Selon l'exemple 2.2, $I_G(\nu) + I_G(\nu)^2/2$ compte les discriminants chromatiques modulo 2. 
Par cons\'equent, $\alpha_G$ est impair si et seulement si le graphe $G$ est connexe et biparti (voir [20], chapitre V.9.2).
(Un graphe est biparti, si l'ensemble de ses sommets peut \^etre partitionn\'e en deux classes ind\'ependantes.)

\bigskip
\medskip

Pour tout $\emptyset \subset V' \subseteq V$, soit $a(G[V'])$ le nombre d'orientations acycliques du graphe $G[V']$
(voir l'introduction), et soit $a_S(G[V'])$ le nombre d'orientations acycliques de $G[V']$, dont l'ensemble des sources 
est \'egal \`a $S$, $\emptyset \subseteq S \subseteq V$. 
\'Evidemment, $a_S(G[V']) = 0$, si $S$ n'est pas un sous-ensemble de $V'$. De plus, si $S = \emptyset$, alors on a toujours 
$a_S(G[V']) = 0$, puisque chaque orientation acyclique du graphe $G[V']$ ($|V'| > 0$) a au moins une source. Posons
$$
    A_G(\nu) \; := \sum_{\emptyset \subset V' \subseteq V} a(G[V'])   \cdot \nu^{V'}, \qquad
A_{G,S}(\nu) \; := \sum_{\emptyset \subset V' \subseteq V} a_S(G[V']) \cdot \nu^{V'}.
$$

Le rapport fondamental entre les orientations acycliques et les sous-ensembles ind\'epen\-dants de $G$ repose uniquement 
sur le fait que {\it l'ensemble des sources d'une orientation acyclique est toujours ind\'ependant.}

\medskip

Or, si $S'$, $\emptyset \subseteq S' \subseteq V$, n'est pas ind\'ependant (l'ensemble vide est ind\'ependant),
$S'$ ne peut pas \^etre un sous-ensemble de l'ensemble des sources. Si $S'$ est ind\'ependant, cependant, alors
$[1+A_G(\nu)] \cdot \nu^{S'}$ compte le nombre d'orientations acycliques telles que $S'$ est un sous-ensemble 
de l'ensemble des sources; car ces orientations de $G[V']$, $S' \subseteq V' \subseteq V$, s'obtiennent en
choisissant une orientation acyclique quelconque du graphe $G[V' \backslash S']$ et en orientant toutes les
autres ar\^etes de $S'$ \`a $V' \backslash S'$.
Par cons\'equent, le principe d'inclusion-exclusion fournit le r\'esultat suivant (voir~[7], th\'eor\`eme~3.1, pour une 
g\'en\'eralisation non-commutative ayant la m\^eme d\'emonstration)~:

\eject

\noindent
{\sc Proposition 3.2.} (Foata) {\it Pour tout $\emptyset \subseteq S \subseteq V$ on a}
$$
[1+A_G(\nu)] \cdot (-1)^{|S|}\partial^S [1+I_G(-\nu)] \; = \; \partial^S [1+A_{G,S}(\nu)],
$$
{\it les cas particuliers les plus int\'eressants \'etant $S = \emptyset$ et $S = \{s\}$ ($s \in V$)~:}
$$
        [1+A_G(\nu)] \cdot [1+I_G(-\nu)] \; = \; 1, \qquad
        -[1+A_G(\nu)] \cdot \partial^s I_G(-\nu) \; = \; A_{G,s}(\nu).\qeda 
$$

\bigskip

Alors il d\'ecoule des deux propositions pr\'ec\'edentes (voir [21] ou [17], 9.46, ainsi que [5], th\'eor\`eme 2.4, et
[27], proposition 5.1)~:

\bigskip

\noindent
{\sc Th\'eor\`eme 3.1.} (Stanley, Cartier-Foata, Gessel-Viennot) {\it Pour tout $\emptyset \subset V' \subseteq V$,}
$$
[1+I_G(-\nu)]^{-1} \; = \; 1+A_G(\nu) \; = \; 1+\chi_{G,-1}(-\nu)
$$
{\it d\'enombre les orientations acycliques de $G[V']$. En particulier, on a $a(G) = (-1)^n\chi_G(-1)$,
et ce nombre est toujours strictement positif.\qeda}

\bigskip

\noindent
Soit $s \in V$ fix\'e. Alors le th\'eor\`eme 3.1 et la proposition 3.2 impliquent 
$$
\partial^s -\log[1+I_G(-\nu)] \; = \; -[1+I_G(-\nu)]^{-1} \cdot \partial^s I_G(-\nu) \; = \; A_{G,s}(\nu).
$$
Posons $A_G^*(\nu) \; := \; -\log[1+I_G(-\nu)]$. Il s'ensuit (voir [12] ou [9] ainsi que [27], proposition 5.10)~:

\bigskip

\noindent
{\sc Th\'eor\`eme 3.2.} (Greene-Zaslavsky, Viennot) {\it Pour tout $\emptyset \subset V' \subseteq V$,}
$$
-\log[1+I_G(-\nu)] \; = \; A_G^*(\nu) \; = \; -\hbox{$\frac{d}{d\lambda}$} \chi_{G,0}(-\nu)
$$
{\it d\'enombre les orientations acycliques de $G[V']$ n'ayant qu'une seule source fix\'ee $s\in V'$. 
En particulier, on a $a_s(G) = (-1)^{n-1}\chi'_G(0) = \alpha_G$ pour tout $s\in V$, 
et ce nombre n'est jamais n\'egatif. Plus pr\'ecis\'ement, il est \'egal \`a 0 si $G$ n'est pas connexe,
il est \'egal \`a 1 si $G$ est un arbre, et il est plus grand que 1 dans tous les autres cas.}

\bigskip

{\it D\'emonstration.} Seulement la toute derni\`ere affirmation n'est pas encore \'evidente. Elle se d\'emontre comme suit.
Les plus courts chemins de $s \in V$ \`a n'importe quel autre sommet forment une arborescence avec $s$ comme source unique. 
Une ar\^ete suppl\'ementaire de $G$ doit {\lfq passer de travers\rfq} par rapport \`a cette arborescence et peut \^etre orient\'ee 
de deux mani\`eres diff\'erentes sans qu'il y ait un cycle orient\'e. Enfin, chacune de ces deux orientations acycliques 
peut \^etre prolong\'ee \`a tout $G$.\qeda

\bigskip

Finalement, soit $a_k(G)$ le nombre d'orientations acycliques de $G = (V,E)$ avec (pr\'ecis\'e\-ment) $k$ sources et posons
$$
a_G(t) \; := \; \sum_{k=1}^{n} a_k(G)t^k, \qquad 
A_{G,t}(\nu) \; := \; \sum_{\emptyset \subset V' \subseteq V} a_{G[V']}(t) \cdot \nu^{V'},
$$
($A_{G,1}(\nu) = A_G(\nu)$). Avec l'aide de la proposition 3.2 ainsi que de l'op\'erateur diff\'erentiel $D(t)$ 
de la proposition 2.1, c), on obtient~:

\bigskip

\noindent
{\sc Th\'eor\`eme 3.3.} {\it On a}
$$\openup2pt\eqalign{
1+A_{G,t}(\nu) \; &= \; [1+A_G(\nu)] \cdot D(-t)[1+I_G(-\nu)] \cr
                  &= \; \frac{1+I_G((t-1)\nu)}{1+I_G(-\nu)}.\qeda \cr
}$$
 
\bigskip

\'Evidemment, tout ce qui fut \'enonc\'e pour les sources vaut \'egalement pour les puits. En particulier, 
$a_S(G[V'])$ (pour les sources) ou encore $a_P(G[V'])$ (pour les puits), $\emptyset \subset V' \subseteq V$,
est \'egal \`a z\'ero, si $V' \backslash S$ (ou bien $V' \backslash P$) contient un sommet isol\'e dans le
graphe $G[V']$.
 
                  
\bigskip
\bigskip

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
                                                       %     
%  Orientations acycliques et ensembles ind\'ependants   %
%
                                                       %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\centerline{\bf 4. Orientations acycliques et ensembles ind\'ependants~:}

\centerline{\bf sources et puits}

\bigskip

Les sommets isol\'es posent des probl\`emes lorsqu'on veut regarder les sources et les puits en m\^eme temps;
car ces sommets sont toujours les deux \`a la fois.
Dans cette optique, la d\'efinition suivante se r\'ev\`ele raisonnable.

\medskip

\noindent
{\sc D\'efinition 4.1.}
Pour tout $\emptyset \subset V' \subseteq V$, soit $I(G[V'])$ l'ensemble des sommets isol\'es de~$G[V'] \;$ ($|I(G[V'])| = i(G[V'])$). 
Si $\emptyset \subset S,P \subseteq V$ et $S \cap P = \emptyset$, notons $|a_{S,P}(G[V'])|$ le nombre d'orientations acycliques 
du graphe $G[V']$ telles que l'ensemble des sources est \'egal \`a $S \cup I(G[V'])$ et l'ensemble des puits est \'egal \`a 
$P \cup I(G[V'])$; et posons $a_{S,P}(G[V']) := (-1)^{I(G[V']) \backslash (S \cup P)} |a_{S,P}(G[V'])|$. 
Par d\'efinition, $a_{S,P}(G[V']) := 0$, si $S \cap P \ne \emptyset$.

\medskip

\noindent
Posons
$$
A_{G,S,P}(\nu) \; := \; \sum_{\emptyset \subset V' \subseteq V} a_{S,P}(G[V']) \cdot \nu^{V'}.
$$
Alors la proposition 3.2, ainsi que le principe d'inclusion-exclusion, impliquent (voir Gessel~[10] pour une g\'en\'eralisation
non-commutative et pond\'er\'ee)~:

\bigskip

\noindent
{\sc Proposition 4.1.} (Gessel) {\it Pour $\emptyset \subset S,P \subseteq V$ on a~:}
$$\openup2pt\eqalign{
&[1+A_G(\nu)] \cdot [(-1)^{|S|}\partial^S I_G(-\nu)] \cdot [(-1)^{|P|}\partial^P I_G(-\nu)] \cr
&= \; A_{G,S}(\nu) \cdot [(-1)^{|P|}\partial^P I_G(-\nu)] \; = \; A_{G,P}(\nu) \cdot [(-1)^{|S|}\partial^S I_G(-\nu)] \cr
&= \; A_{G,S,P}(\nu).
}$$

\medskip

{\it D\'emonstration.} Il ne s'agit que d'expliquer l'entr\'ee des nombres n\'egatifs due aux sommets isol\'es.
Soit $i$ un sommet isol\'e de $G$ (pour les sous-graphes engendr\'es $G[V']$, $\emptyset \subset V' \subseteq V$,
on a le m\^eme argument), alors $i \notin S$ implique 
$$
\partial^i A_{G,S}(\nu) \; = \; 0 \qquad \hbox{et} \qquad 
\partial^i (-1)^{|S|}\partial^S I_G(-\nu) \; = \; -\nu^i \cdot (-1)^{|S|}\partial^S I_G(-\nu),
$$
o\`u $S$ peut \^etre remplac\'e par $P$. Par cons\'equent, $i \notin (S \cup P)$ implique
$$
\partial^i A_{G,S,P}(\nu) \; = \; -\nu^i \cdot A_{G,S,P}(\nu).\qeda
$$

\bigskip


Maintenant, pour $s,p \in V$ fix\'es, il d\'ecoule de la proposition pr\'ec\'edente ainsi que du th\'eor\`eme 3.1 
(voir aussi la proposition 2.1) que~:
$$\openup2pt\eqalign{
&\partial^{\{s,p\}} \Bigl( [1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)] \Bigr) \cr
&= \; [1+I_G(-\nu)]^{-1} \cdot \partial^s I_G(-\nu) \cdot \partial^p I_G(-\nu) \; + \; 
      \Bigl( 1+\log[1+I_G(-\nu)] \Bigr) \cdot \partial^{\{s,p\}} I_G(-\nu) \cr
&= \; A_{G,s,p}(\nu) \; + \; \Bigl( 1+\log[1+I_G(-\nu)] \Bigr) \cdot \partial^{\{s,p\}} I_G(-\nu). \cr
}$$
Si $s$ et $p$ sont adjacents, alors $\partial^{\{s,p\}} I_G(-\nu) = 0$, et il s'ensuit
$$
\partial^{\{s,p\}} \Bigl( [1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)] \Bigr) \; = \; A_{G,s,p}(\nu).
$$
Cela implique le th\'eor\`eme suivant (voir [12] ou [9]), que nous repr\'esentons dans~$A[V]$~:

\bigskip

\noindent
{\sc Th\'eor\`eme 4.1.} (Greene-Zaslavsky) {\it La fonction d'ensembles}
$$
[1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)] \; = \; \hbox{$\frac{d}{d\lambda}$} \chi_{G,1}(-\nu)
$$
{\it prend la valeur $(-1)^{|V'|}|V'|$ pour tout $\emptyset \subset V' \subseteq V$, lorsque $V'$ est ind\'ependant 
(car $\exp(-V') \cdot \log[\exp(-V')]$ $= -V' \cdot \exp(-V')$),
et la valeur 
$$
a_{s,p}(G[V']) \; = \; (-1)^{|V'|}\chi'_{G[V']}(1) \; = \; (-1)^{|I|}\beta(G[V']) \; = \;
$$
$$
(-1)^{|I|}a_{s,p}(G[V' \backslash I]) \; = \; (-1)^{|V'|}\chi'_{G[V' \backslash I]}(1) \; = \; (-1)^{|I|}\beta(G[V' \backslash I]),
$$
lorsque $G[V']$ contient une ar\^ete $\{s,p\}$ et $I$ est l'ensemble des sommets isol\'es de $G[V']$.
En particulier, si $G$ ne contient aucun sommet isol\'e et $\{s,p\}$ est une ar\^ete de $G$, alors 
$a_{s,p}(G) = (-1)^n\chi'_G(1) = \beta(G)$ d\'enombre les orientations acycliques de $G$ 
n'ayant qu'une seule source \`a $s$ et qu'un seul puits \`a $p$. 
Ce nombre n'est jamais n\'egatif et strictement positif si $G$ est un bloc, c'est-\`a-dire si $G$ est \hbox{2-connexe} ou 
la seule ar\^ete $\{s,p\}$.}

\medskip

{\it D\'emonstration.} Seulement la toute derni\`ere affirmation n'est pas encore \'evidente. Elle se d\'emontre comme suit.
Selon [13], chapitre 3.2, tout graphe \hbox{2-connexe} admet une {\lfq d\'ecom\-po\-si\-tion en oreilles\rfq} donn\'ee par des chemins
$C_1,\dots,C_k$ tels que $C_1 = \{s,p\}$, $|V(C_i) \cap [V(C_1) \cup \dots \cup V(C_{i-1})]| = 2$ pour tout $2 \le i \le k$ et 
$V = V(C_1) \cup \dots \cup V(C_k)$. Cette d\'ecomposition permet de munir $G$ d'une fonction injective $i: V \to [0,1]$, $i(s) = 0$,
$i(p) = 1$, qui  augmente (ou diminue) le long de tous les chemins $C_1,\dots,C_k$ de fa\c con strictement monotone. Alors il 
ne s'agit que d'orienter chaque ar\^ete de son extr\'emit\'e la plus petite (selon $i$) \`a son extr\'emit\'e la plus grande.\qeda

\bigskip

Nous avons d\'ej\`a interpr\'et\'e $[1+I_G(-\nu)]^{-1}$ (th\'eor\`eme 3.1), $-\log[1+I_G(-\nu)]$ en d\'erivant par rapport \`a un 
\'el\'ement (th\'eor\`eme 3.2) et $[1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)]$ en d\'erivant deux fois (th\'eor\`eme 4.1).
En effet, $-\log[1-V]$ est l'int\'egrale de $[1-V]^{-1}$. Cependant, l'int\'egrale de $-\log[1-V]$ n'est pas $[1-V] \cdot \log[1-V]$,
mais $[1-V] \cdot \log[1-V]-[-V]$. Voil\`a pourquoi le th\'eor\`eme principal de ce paragraphe est consacr\'e \`a l'interpr\'etation
de $[1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)] - I_G(-\nu)$. Si l'on ajoute le terme $-I_G(-\nu)$ au membre de gauche de la derni\`ere
identit\'e de la proposition 3.1, la valeur de $\beta_{G[V']}$ ne change que si $V'$ est ind\'ependant~: dans ce cas $\beta_{G[V']}$ 
n'est plus \'egal \`a $|V'|$ mais \`a $|V'|-1$ (toutes les deux d\'efinitions \'etant artificielles). 
On utilisera donc l'identit\'e 
$$
\sum_{\emptyset \subset V' \subseteq V} (-1)^{i(G[V'])}\beta_{G[V']} \cdot \nu^{V'} 
\; := \; [1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)] - I_G(-\nu). 
$$
Avec cette modification (et la d\'efinition 4.1) on a alors~:

\bigskip

\noindent
{\sc Th\'eor\`eme 4.2.} {\it Soit $V = \{1,\dots,n\}$ et soit $i$ le nombre de sommets isol\'es de $G$. Alors le coefficient
de $\nu^V$ dans 
$
[1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)] - I_G(-\nu),
$
c'est-\`a-dire $(-1)^i \beta_G$, est \'egal \`a}
$$
a_{\{1\},\{2\}}(G) - a_{\{1,2\},\{3\}}(G) + a_{\{1,2,3\},\{4\}}(G) - \dots + (-1)^na_{\{1,2,\dots,n-1\},\{n\}}(G),
$$
{\it o\`u la somme pr\'ec\'edente s'arr\^ete d\`es que l'ensemble des sources $\{1,2,\dots,k\}$ n'est plus ind\'ependant.}

\eject

\noindent
{\it D\'emonstration.} D\'erivons successivement par rapport \`a tous les \'el\'ements~:
$$\openup2pt\eqalign{
&\partial^{\{1\}} \Bigl( [1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)] - I_G(-\nu) \Bigr) \cr
&= \; \log[1+I_G(-\nu)] \cdot \partial^{\{1\}} I_G(-\nu), \cr
&\partial^{\{1,2\}} \Bigl( [1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)] - I_G(-\nu) \Bigr) \cr
&= \; A_{G,\{1\},\{2\}}(\nu) + \log[1+I_G(-\nu)] \cdot \partial^{\{1,2\}} I_G(-\nu), \cr
&\partial^{\{1,2,3\}} \Bigl( [1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)] - I_G(-\nu) \Bigr) \cr
&= \; \partial^{\{3\}} A_{G,\{1\},\{2\}}(\nu) - A_{G,\{1,2\},\{3\}}(\nu) + \log[1+I_G(-\nu)] \cdot \partial^{\{1,2,3\}} I_G(-\nu), \cr
& \qquad \qquad \qquad \qquad \qquad \qquad \qquad \cdots \cr
&\partial^{\{1,2,\dots,k\}} \Bigl( [1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)] - I_G(-\nu) \Bigr) \cr
&= \; \partial^{\{3,\dots,k\}} A_{G,\{1\},\{2\}}(\nu) - \partial^{\{4,\dots,k\}} A_{G,\{1,2\},\{3\}}(\nu) + 
      \partial^{\{5,\dots,k\}} A_{G,\{1,2,3\},\{4\}}(\nu) \cr 
& \quad \;\; - \dots + (-1)^k A_{G,\{1,2,\dots,k-1\},\{k\}}(\nu) + \log[1+I_G(-\nu)] \cdot \partial^{\{1,2,\dots,k\}} I_G(-\nu), \cr
& \qquad \qquad \qquad \qquad \qquad \qquad \qquad \cdots \cr
&\partial^V \Bigl( [1+I_G(-\nu)] \cdot \log[1+I_G(-\nu)] - I_G(-\nu) \Bigr) \cr
&= \; \partial^V A_{G,\{1\},\{2\}}(\nu) - \partial^V A_{G,\{1,2\},\{3\}}(\nu) + \partial^V A_{G,\{1,2,3\},\{4\}}(\nu) \cr
& \quad \;\; - \dots + (-1)^n \partial^V A_{G,\{1,2,\dots,n-1\},\{n\}}(\nu).\qeda \cr
}$$


\bigskip
\medskip

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
                             %     
%  Le polyn\^ome chromatique   %
%
                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\centerline{\bf 5. Le polyn\^ome chromatique~: bases canoniques}

\bigskip

\noindent
Tout d'abord, il d\'ecoule de la proposition 3.1 et du th\'eor\`eme 3.1 que 

\bigskip

\noindent
{\sc Proposition 5.1.} (Stanley~[21], Gessel~[10])
$$
1+\chi_{G,\lambda}(\nu) \; = \; [1+I_G(\nu)]^{\lambda}, \qquad
1+\chi_{G,-\lambda}(-\nu) \; = \; [1+A_G(\nu)]^{\lambda}.\qeda 
$$


\bigskip


Soit $V = \{1,2,\dots,n\}$, et regardons une orientation acyclique des ar\^etes de $G = (V,E)$. Notons $V_1$ l'ensemble
des sommets accessibles (par des chemins orient\'es) \`a partir de $v_1 := 1$. Soit $v_2$ le plus petit sommet de 
$V \backslash V_1$, et soit $V_2$ l'ensemble des sommets de $V \backslash V_1$ accessibles de $v_2$ \dots\ 
Finalement, soit $v_k$ le plus petit sommet de $V \backslash (V_1 \cup \dots \cup V_{k-1})$, et soit $V_k$ 
l'ensemble des sommets de $V \backslash (V_1 \cup \dots \cup V_{k-1})$ accessibles de $v_k$, 
$V = V_1 \uplus V_2 \uplus \dots \uplus V_k$. On appelle $k$ le nombre de {\it composantes} de l'orientation acyclique.
Ainsi une orientation acyclique de $k$ composantes est constitu\'ee par une partition $V = V_1 \uplus \dots \uplus V_k$
en orientations acycliques avec des sources fix\'ees $v_1,\dots,v_k$ (le plus petit sommet $v_i$ de chaque composante $V_i$
est la source unique, et les ar\^etes entre deux composantes $V_i$ et $V_j$ avec $v_i < v_j$ sont toutes orient\'ees de
$V_j$ \`a $V_i$). Or, puisque $A_G^*(\nu)$ compte des orientations acycliques avec une source unique fix\'ee (ou bien
des orientations acycliques d'une seule composante), $A_G^*(0) = 0$, il s'ensuit que $A_G^*(\nu)^k/k!$ compte des
orientations acycliques de $k$ composantes. En particulier, on a 
$$
\exp[A_G^*(\nu)] \; = \; 1+A_G(\nu),
$$
ce qui est la d\'emonstration de Viennot (voir~[27], proposition 5.10) du th\'eor\`eme~3.2, \`a savoir de l'identit\'e 
$$
A_G^*(\nu) \; = \; -\log[1+I_G(-\nu)],
$$
avec l'aide du th\'eor\`eme 3.1, i.~e.~de l'identit\'e $1+A_G(\nu) = [1+I_G(-\nu)]^{-1}$.

\eject

Notons $c(G)$ le nombre de {\it composantes connexes} de $G$, de sorte que chaque orientation acyclique de $G$ a au moins 
$c(G)$ composantes, ce nombre minimal pouvant \^etre atteint selon le th\'eor\`eme 3.2. On en d\'eduit le r\'esultat de
Greene et Zaslavsky (voir [12] ou [26], chapitre IX.2), que nous reformulons dans l'alg\`ebre des fonctions d'ensembles.

\bigskip

\noindent
{\sc Th\'eor\`eme 5.1.} (Greene-Zaslavsky, Viennot) {\it On a}
$$\openup2pt\eqalign{
1+\chi_{G,\lambda}(-\nu) \; &= \; \exp \Bigl( \lambda \cdot \log[1+I_G(-\nu)] \Bigr) 
                         \;  = \; \exp \Bigl( -\lambda \cdot A_G^*(\nu) \Bigr) \cr
                            &= \; \sum_{k=0}^\infty \Bigl( [-A_G^*(\nu)]^k/k! \Bigr) \cdot \lambda^k.                                     
}$$
{\it En particulier,}
$$
\chi_G(\lambda) \; = \; \lambda^n - c_{n-1} \cdot \lambda^{n-1} + c_{n-2} \cdot \lambda^{n-2} - \dots + (-1)^{n-1}c_1 \cdot \lambda,
$$
{\it o\`u $c_k$ d\'esigne le nombre d'orientations acycliques de $G$ de $k$ composantes, $c_{n-1} = |E|$, 
$c_1 = \alpha_G = a_{\{1\}}(G)$, $1+c_{n-1}+c_{n-2}+\dots+c_1 = a(G)$; $c_k = 0$, si $k < c(G)$, et $c_k > 0$, si $k \ge c(G)$.\qeda}

\bigskip

\noindent
{\sc Remarque 5.1.}
Le th\'eor\`eme pr\'ec\'edent montre que l'alternance des signes du polyn\^ome chromatique est une cons\'equence directe
de la positivit\'e des discriminants chromatiques, c'est-\`a-dire de $A_G^*(\nu)$.

\bigskip
\medskip

Un r\'esultat plus puissant que l'alternance des signes du polyn\^ome chromatique d\'evelopp\'e par rapport \`a la base
des puissances $\lambda^k$ est celui de l'alternance des signes par rapport \`a la base des puissances $(\lambda - 1)^k$, ce qui 
correspond au polyn\^ome de Tutte. Pour la d\'emontrer avec l'aide des orientations acycliques, supposons que $G$ est 
connexe et que ses sommets sont num\'erot\'es avec les nombres $1,\dots,n$ de telle fa\c con que le plus petit voisin de chaque 
sommet (sauf $1$) porte un nombre plus petit que celui du sommet m\^eme. (De cette mani\`ere, la num\'erotation refl\`ete bien
la connexit\'e.) 

Dans cette situation, les sommets $v_2,\dots,v_k$ d'une orientation acyclique de $k$ composantes $V = V_1 \uplus \dots \uplus V_k$ 
(de nouveau, pour chaque composante $V_i$, son plus petit sommet $v_i$ est sa source unique) ne peuvent pas \^etre des puits; 
car, pour chacun de ces sommets $v_i$, son plus petit voisin se trouve toujours dans une composante plus petite 
(la {\lfq grandeur\rfq} d'une composante \'etant m\'esur\'ee en fonction de son plus petit \'el\'ement) de sorte 
que l'ar\^ete corres\-pondante a $v_i$ comme extr\'emit\'e initiale et le plus petit voisin comme extr\'emit\'e terminale. 

Si $v_1 = 1$ est un puits (i.~e.~$v_2 = 2$), alors la suppression des puits r\'eduit le nombre de composantes de $1$ (\`a savoir
de la composante $V_1 = \{1\}$). D'autre part, en ajoutant les puits distincts de $v_1 = 1$, on les affecte automatiquement
\`a la composante la plus petite d'o\`u ils sont accessibles (c'est la composante du plus petit voisin ou une composante encore
plus petite).

Par cons\'equent, pour chaque ensemble de sommets ind\'ependant $I$ tel que $1 = v_1 \in I$, le coefficient de $\nu^V$ dans
$[A_G^*(\nu)^k/k!] \cdot \nu^I$ compte le nombre d'orientations acycliques de $k+1$ composantes de $G$ telles que $I$ est
un sous-ensemble des puits. Voil\`a pourquoi le principe d'inclusion-exclusion implique que le coefficient de $\nu^V$ dans
$[A_G^*(\nu)^k/k!] \cdot [-\partial^{\{1\}} I_G(-\nu)]$ compte le nombre d'orientations acycliques de $k+1$ composantes de $G$,
dont le puits unique est \'egal \`a $1$ (pour $k = 1$ il s'agit bien du nombre $a_{\{2\},\{1\}}(G)$).

\medskip

Notons $b(G)$ le nombre de {\it blocs} de $G$ (voir le th\'eor\`eme 4.1), de sorte que chaque orientation acyclique de $G$ telle
que le sommet $1$ est son puits unique a au moins $b(G)+1$ composantes; pour une telle orientation il est n\'ecessaire
et suffisant, que le plus petit sommet de tout bloc soit son puits unique. Selon le th\'eor\`eme 4.1 le nombre minimal de
$b(G)+1$ composantes peut \^etre atteint. Nous avons d\'emontr\'e le th\'eor\`eme principal de ce paragraphe 
(voir [26], chapitre IX.2).

\eject

\noindent
{\sc Th\'eor\`eme 5.2.} {\it On a} 
$$\openup2pt\eqalign{
-\partial^{\{1\}} \chi_{G,\lambda}(-\nu) \; 
&= \; \lambda \cdot [1+I_G(-\nu)]^{\lambda-1} \cdot [-\partial^{\{1\}} I_G(-\nu)] \cr
&= \; \lambda \cdot \exp \Bigl( -(\lambda - 1) \cdot A_G^*(\nu) \Bigr) \cdot [-\partial^{\{1\}} I_G(-\nu)] \cr
&= \; \lambda \cdot \sum_{k=0}^\infty \Bigl( [-A_G^*(\nu)]^k/k! \Bigr) \cdot [-\partial^{\{1\}} I_G(-\nu)] \cdot (\lambda-1)^k.                                     
}$$
\noindent
{\it En particulier,}
$$
\chi_G(\lambda) \; = \; \lambda \cdot [(\lambda-1)^{n-1} - b_{n-2} \cdot (\lambda-1)^{n-2} + \dots + (-1)^n b_1 \cdot (\lambda-1)],
$$
{\it o\`u $b_k$ d\'esigne le nombre d'orientations acycliques de $G$ de $k+1$ composantes, dont le puits unique est \'egal \`a $1$,
$b_{n-2} = |E| - (n-1)$, $b_1 = \beta_G = a_{\{2\},\{1\}}(G)$, $1+b_{n-2}+\dots+b_1 = \alpha_G = a_{\{1\}}(G)$; 
$b_k = 0$, si $k < b(G)$, et $b_k > 0$, si $k \ge b(G)$.\qeda}

\bigskip

\noindent
{\sc Exemple 5.1.} Le graphe donn\'e dans les dessins suivants admet quatre orientations acycliques, dont le puits unique est $1$~: 
une de quatre composantes, deux de trois composantes et une de deux composantes. Voil\`a pourquoi son polyn\^ome chromatique
s'\'ecrit~: $\lambda[(\lambda-1)^3 - 2(\lambda-1)^2 + (\lambda-1)] = \lambda(\lambda-1)(\lambda-2)^2$.

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



% le fichier grille

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

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

%------------------------------------------------------------------

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

%------------------------------------------------------------------

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

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

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

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

%------------------------------------------------------------------


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

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

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

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

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


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

\unitlength =1pt

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

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

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



\newif\if@negarg

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

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

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


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

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

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

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

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

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

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

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



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


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

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

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

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

%INITIALIZATION
\thinlines

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


% macros supplementaires (J.D.)

\newbox\tbox
\newbox\tboxa

%\def\picbox(#1,#2,#3)#4{\setbox\tbox=\hbox{#4}%
%     \ht\tbox=#1 \wd\tbox=#2 \dp\tbox=#3 \box\tbox}

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

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

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

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

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

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

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

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

\unitlength=1mm

\let\cput=\centerput

\def\put(#1,#2)#3{\noalign{\nointerlineskip
                               \centerput(#1,#2){$#3$}
                                \nointerlineskip}}
% fin du fichier grille --------------------


\midinsert
\newbox\boxquatre
\newbox\boxcinq
\newbox\boxsix
\newbox\boxsept

\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
\fleche(0,0)\dir(2,1)\long{6}
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(-2,1)\long{10}
\fleche(0,10)\dir(2,-1)\long{6}
\segment(0,10)\dir(0,-1)\long{10}
\fleche(0,10)\dir(0,-1)\long{6}
\segment(0,0)\dir(-2,1)\long{10}
\fleche(-10,5)\dir(2,-1)\long{6}
\fleche(-10,5)\dir(2,1)\long{6}
\segment(-10,5)\dir(2,1)\long{10}
%
\centerput(12,4){1}
\centerput(-12,4){4}
\centerput(0,-3){2}
\centerput(0,11){3}
%
\centerput(0,-7){composantes~:}
\centerput(0,-11){\{1\},\{2\},\{3\},\{4\}}
}

\setbox\boxcinq=\vbox{\vskip
12mm\offinterlineskip
\fleche(0,0)\dir(2,1)\long{6}
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(-2,1)\long{10}
\fleche(0,10)\dir(2,-1)\long{6}
\segment(0,10)\dir(0,-1)\long{10}
\fleche(0,0)\dir(0,1)\long{6}
\segment(0,0)\dir(-2,1)\long{10}
\fleche(-10,5)\dir(2,-1)\long{6}
\fleche(-10,5)\dir(2,1)\long{6}
\segment(-10,5)\dir(2,1)\long{10}
%
\centerput(12,4){1}
\centerput(-12,4){4}
\centerput(0,-3){2}
\centerput(0,11){3}
%
\centerput(0,-7){composantes~:}
\centerput(0,-11){\{1\},\{2,3\},\{4\}}
}

\setbox\boxsix=\vbox{\vskip
12mm\offinterlineskip
\fleche(0,0)\dir(2,1)\long{6}
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(-2,1)\long{10}
\fleche(0,10)\dir(2,-1)\long{6}
\segment(0,10)\dir(0,-1)\long{10}
\fleche(0,10)\dir(0,-1)\long{6}
\segment(0,0)\dir(-2,1)\long{10}
\fleche(-10,5)\dir(2,-1)\long{6}
\fleche(0,10)\dir(-2,-1)\long{6}
\segment(-10,5)\dir(2,1)\long{10}
%
\centerput(12,4){1}
\centerput(-12,4){4}
\centerput(0,-3){2}
\centerput(0,11){3}
%
\centerput(0,-7){composantes~:}
\centerput(0,-11){\{1\},\{2\},\{3,4\}}
}

\setbox\boxsept=\vbox{\vskip
12mm\offinterlineskip
\fleche(0,0)\dir(2,1)\long{6}
\segment(0,0)\dir(2,1)\long{10}
\segment(10,5)\dir(-2,1)\long{10}
\fleche(0,10)\dir(2,-1)\long{6}
\segment(0,10)\dir(0,-1)\long{10}
\fleche(0,0)\dir(0,1)\long{6}
\segment(0,0)\dir(-2,1)\long{10}
\fleche(0,0)\dir(-2,1)\long{6}
\fleche(-10,5)\dir(2,1)\long{6}
\segment(-10,5)\dir(2,1)\long{10}
%
\centerput(12,4){1}
\centerput(-12,4){4}
\centerput(0,-3){2}
\centerput(0,11){3}
%
\centerput(0,-7){composantes~:}
\centerput(0,-11){\{1\},\{2,3,4\}}
}

$$
\box\boxquatre\hskip3cm\box\boxcinq
\hskip3cm\box\boxsix
\hskip3cm\box\boxsept
$$

\endinsert


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

\bigskip
\bigskip
\bigskip
\bigskip
\bigskip


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
                             %     
%  Le polyn\^ome chromatique   %
%
                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\centerline{\bf 6. Le polyn\^ome chromatique~: bases exotiques}

\bigskip

Notons $\chi(G)$ le nombre chromatique de $G$, i.~e.~le plus petit nombre de couleurs n\'ecessaire pour colorier 
les sommets de $G$ de fa\c con r\'eguli\`ere. 

Gr\^ace \`a la proposition~5.1 et \`a la formule du bin\^ome, on obtient le d\'eveloppe\-ment du polyn\^ome chromatique du graphe 
$G = (V,E)$ dans les deux bases 
$$
\lambda^{\underline{k}} \; := \; k! {\lambda \choose k}, \quad  
\lambda^{\overline{k}} \; := \; k! \biggl({\lambda \choose k}\biggr) 
                        \; = \; k! {\lambda+k-1 \choose k} \; = \; k! (-1)^k{-\lambda \choose k}.
$$                        

\medskip

\noindent
{\sc Proposition 6.1.} (Brenti~[3])
$$\openup2pt\eqalign{
1+\chi_{G,\lambda}(\nu) \; &= \; \sum_{k=0}^\infty I_G(\nu)^k {\lambda \choose k}, \quad
1+\chi_{G,-\lambda}(\nu) \; = \; \sum_{k=0}^\infty [-I_G(\nu)]^k \biggl({\lambda \choose k}\biggr), \cr
1+\chi_{G,-\lambda}(-\nu) \; &= \; \sum_{k=0}^\infty A_G(\nu)^k {\lambda \choose k}, \;\;
1+\chi_{G,\lambda}(-\nu) \; = \; \sum_{k=0}^\infty [-A_G(\nu)]^k \biggl({\lambda \choose k}\biggr). \cr
}$$
{\it Alors, avec $|V| = n$, on a}
$$\openup2pt\eqalign{
\chi_G(\lambda) \; &= \; \lambda^{\underline{n}} + i_{n-1} \cdot \lambda^{\underline{n-1}} + 
                         i_{n-2} \cdot \lambda^{\underline{n-2}} + \dots + i_1 \cdot \lambda \cr
                   &= \; \lambda^{\overline{n}} - a_{n-1} \cdot \lambda^{\overline{n-1}} + 
                         a_{n-2} \cdot \lambda^{\overline{n-2}} - \dots + (-1)^{n-1} a_1 \cdot \lambda, \cr
}$$
{\it o\`u les $i_k$ sont des entiers positifs (d\'enombrant des partitions en ensembles ind\'ependants non-vides) 
et les $a_k$ sont des entiers strictement positifs (d\'enombrant des partitions en orientations acycliques), $1 \le k \le n-1$.
En particulier, $i_{n-1} = {n \choose 2} - |E|$, $a_{n-1} = {n \choose 2} + |E|$, $a_1 = a(G)$ et $i_1$ est \'egal \`a $1$ si 
$|E| = 0$ et \'egal \`a $0$ sinon. 
De plus, on a $i_k = 0$, si $k < \chi(G)$, et $i_k > 0$, si $k \ge \chi(G)$.\qeda}
                
\eject 

Le r\'esultat sur les nombres $a_k$ constitue un des th\'eor\`emes principaux de~[3] (\`a savoir le th\'eor\`eme~5.5 qui est 
directement \'equivalent au th\'eor\`eme~5.3). Remarquons que la d\'emonstration de Brenti (par induction simultan\'ee sur 
le nombre des sommets et des ar\^etes du graphe) est la plus longue de tout l'article~[3], bien que Brenti remercie 
l'arbitre {\lfq for suggesting a simplification in the proof of theorem~5.3\rfq}.

\bigskip
\medskip

\noindent
Brenti~[3] a \'egalement regard\'e
$$
\frac{p_G(x)}{(1-x)^{n+1}} \; := \; \sum_{\lambda = 0}^\infty \chi_G(\lambda) \cdot x^\lambda \quad \Rightarrow \quad
-\frac{p_G(\frac{1}{x})}{(1-\frac{1}{x})^{n+1}} \; = \; \sum_{\lambda = 0}^\infty \chi_G(-\lambda) \cdot x^\lambda,
$$
o\`u l'implication est une cons\'equence de [23], chapitre 4.2. 
Dans cet esprit, nous nous proposons de trouver plusieurs expressions pour
$$
\overline{P}_{G,x}(\nu) \; := \; \sum_{\emptyset \subset V' \subseteq V} \frac{p_{G[V']}(x)}{(1-x)^{|V'|+1}} \cdot \nu^{V'}.
$$

\medskip

\noindent
{\sc Proposition 6.2.} {\it On a}
$$\openup2pt\eqalign{
{\textstyle{1 \over 1-x}} + \overline{P}_{G,x}(\nu) 
\; &= \; \sum_{\lambda = 0}^\infty [1+I_G(\nu)]^\lambda \cdot x^\lambda 
\;  = \; \frac{1}{1-x[1+I_G(\nu)]} \cr
   &= \; \frac{1}{1-x} \cdot \Bigl[1 - \frac{x}{1-x} I_G(\nu)\Bigr]^{-1} 
\;  = \; \frac{1}{1-x} \cdot \sum_{k=0}^\infty \Bigl(\frac{x \cdot I_G(\nu)}{1-x}\Bigr)^k, \cr
{\textstyle{1 \over 1-x}} - \overline{P}_{G,\frac{1}{\scriptstyle x}}(-\nu) 
\; &= \; \sum_{\lambda = 0}^\infty [1+A_G(\nu)]^\lambda \cdot x^\lambda 
\;  = \; \frac{1}{1-x[1+A_G(\nu)]} \cr
   &= \; \frac{1}{1-x} \cdot \Bigl[1 - \frac{x}{1-x} A_G(\nu)\Bigr]^{-1}
\;  = \; \frac{1}{1-x} \cdot \sum_{k=0}^\infty \Bigl(\frac{x \cdot A_G(\nu)}{1-x}\Bigr)^k,  \cr
{\textstyle{1 \over x-1} + \frac{1}{x}} \cdot \overline{P}_{G,\frac{1}{\scriptstyle x}}(\nu) 
\; &= \; \frac{1}{x-[1+I_G(\nu)]} 
\; = \; \frac{1}{x-1} \cdot \sum_{k=0}^\infty \Bigl(\frac{I_G(\nu)}{x-1}\Bigr)^k, \cr
{\textstyle{1 \over x-1} - \frac{1}{x}} \cdot \overline{P}_{G,x}(-\nu) 
\; &= \; \frac{1}{x-[1+A_G(\nu)]} 
\; = \; \frac{1}{x-1} \cdot \sum_{k=0}^\infty \Bigl(\frac{A_G(\nu)}{x-1}\Bigr)^k.\qeda \cr
}$$

\bigskip

\noindent
{\sc Remarque 6.1.} On n'a pas besoin de s'appuyer sur [23], chapitre 4.2, puisque l'identit\'e fondamentale
$$\bf
\frac{1}{1-y} \; = \; 1 - \frac{1}{1-\frac{1}{y}}
$$
implique \'evidemment
$$\openup2pt\eqalign{
&{\textstyle{1 \over 1-x}} + \overline{P}_{G,x}(\nu) \; = \; \frac{1}{1-x[1+I_G(\nu)]} \; = \; 
1 - \frac{1}{1-\frac{1}{x}[1+A_G(-\nu)]}   \quad   \Rightarrow \cr
&\frac{1}{1-x[1+A_G(\nu)]} \; = \; 1-{1 \over 1-{1 \over x}} - \overline{P}_{G,\frac{1}{\scriptstyle x}}(-\nu) \; = \; 
{\textstyle{1 \over 1-x}} - \overline{P}_{G,\frac{1}{\scriptstyle x}}(-\nu). \cr
}$$

\bigskip
\medskip

\noindent
Calculons aussi la fonction g\'en\'eratrice 
$$
P_{G,x}(\nu) \; := \; \sum_{\emptyset \subset V' \subseteq V} p_{G[V']}(x) \cdot \nu^{V'}.
$$

\bigskip

\noindent
{\sc Proposition 6.3.} (Tomescu~[25], Gansner-Vo~[8], Brenti~[3]) {\it On a}
$$\openup2pt\eqalign{
1 + P_{G,x}(\nu)                    \; &= \; \Bigl(1 - \frac{x \cdot I_G[(1-x)\nu]}{1-x}\Bigr)^{-1} 
\; = \; \sum_{k=0}^\infty \Bigl(\frac{x \cdot I_G[(1-x)\nu]}{1-x}\Bigr)^k, \cr
1 + x \cdot P_{G,\frac{1}{\scriptstyle x}}(x\nu) \; &= \; \Bigl(1 - \frac{x \cdot A_G[(1-x)\nu]}{1-x}\Bigr)^{-1} 
\; = \; \sum_{k=0}^\infty \Bigl(\frac{x \cdot A_G[(1-x)\nu]}{1-x}\Bigr)^k, \cr
1 + P_{G,\frac{1}{\scriptstyle x}}(x\nu)         \; &= \; \Bigl(1 - \frac{I_G[(x-1)\nu]}{x-1}\Bigr)^{-1} 
\; = \; \sum_{k=0}^\infty \Bigl(\frac{I_G[(x-1)\nu]}{x-1}\Bigr)^k, \cr
1 + {\textstyle{1 \over x}} \cdot P_{G,x}(\nu)  \; &= \; \Bigl(1 - \frac{A_G[(x-1)\nu]}{x-1}\Bigr)^{-1}  
\; = \; \sum_{k=0}^\infty \Bigl(\frac{A_G[(x-1)\nu]}{x-1}\Bigr)^k. \cr
}$$
{\it Alors, avec les nombres $i_k$ et $a_k$ de la proposition 6.1 on a notamment}
$$\openup2pt\eqalign{
p_G(x) \; &= \; n! \cdot x^n + i_{n-1} \cdot (n-1)! \cdot x^{n-1}(1-x) + i_{n-2} \cdot (n-2)! \cdot x^{n-2}(1-x)^2 + \cr
          & \quad \;\; \dots + i_2 \cdot 2 \cdot x^2(1-x)^{n-2} + i_1 \cdot x(1-x)^{n-1} \cr
       \; &= \; n! \cdot x + a_{n-1} \cdot (n-1)! \cdot x(x-1) + a_{n-2} \cdot (n-2)! \cdot x(x-1)^2 + \cr
          & \quad \;\; \dots + a_2 \cdot 2 \cdot x(x-1)^{n-2} + a_1 \cdot x(x-1)^{n-1}.\qeda \cr
}$$

\bigskip

Supposons que $V = \{1,2,\dots,n\}$. Pour $\emptyset \subset V',V'' \subseteq V$ soit $V' < V''$ si et seulement si
$v' < v''$ pour tout $v' \in V'$ et $v'' \in V''$. De plus, pour des ensembles de sommets non vides, deux \`a deux disjoints
et ind\'ependants $I_1,\dots,I_k$, soit $G[\{I_1,\dots,I_k\}]$ le graphe dont les sommets sont les $k$ ensembles
$I_1,\dots,I_k$ et tel que $\{I_{i_1},\dots,I_{i_j}\}$, $\emptyset \subset \{i_1,\dots,i_j\} \subseteq \{1,\dots,k\}$, 
est un ensemble de $j$ sommets ind\'ependants si et seulement si $I_{i_1} \cup \dots \cup I_{i_j}$ est ind\'ependant 
dans le graphe $G$ et (apr\`es une permutation appropri\'ee de $\{i_1,\dots,i_j\}$) $I_{i_1} < \dots < I_{i_j}$
(voir~[8]). Alors la proposition pr\'ec\'edente ainsi que le th\'eor\`eme 3.1 impliquent~:
$$\openup2pt\eqalign{
&1 + P_{G,x}(\nu) \cr
&= \; \Biggl( 1 - \sum_{\scriptstyle \emptyset \subset I \subseteq V \atop \scriptstyle I \; \hbox{\eightrm ind\'ependant}}
              x(1-x)^{|I|-1} \cdot \nu^I \Biggr)^{-1} \cr
&= \; \Biggl( 1 + \sum_{\scriptstyle \emptyset \subset I \subseteq V \atop \scriptstyle I \; \hbox{\eightrm ind\'ependant}}
              \nu^I \cdot \sum_{j=1}^{|I|} {|I|-1 \choose j-1} \cdot (-x)^j \Biggr)^{-1} \cr
&= \; \Biggl( 1 + \sum_{\scriptstyle \emptyset \subset I \subseteq V \atop \scriptstyle I \; \hbox{\eightrm ind\'ependant}}
              \sum_{\scriptstyle I_1 \uplus \dots \uplus I_j = I \atop \scriptstyle I_1 < \dots < I_j} 
              (-x \nu^{I_1}) \cdot \dots \cdot (-x \nu^{I_j}) \Biggr)^{-1} \cr
&= \; 1 + \sum_{\emptyset \subset V' \subseteq V} 
          \sum_{\scriptstyle I_1 \uplus \dots \uplus I_k = V' \atop \scriptstyle I_1,\dots,I_k \; \hbox{\eightrm ind\'ependants}} 
          a\Bigl(G[\{I_1,\dots,I_k\}]\Bigr) \cdot (x \nu^{I_1}) \cdot \dots \cdot (x \nu^{I_k}). \cr
}$$


\bigskip

\noindent
{\sc Proposition 6.4.} (Linial~[15], Gansner-Vo~[8], Tomescu~[25]) {\it On a}
$$
1 + P_{G,x}(\nu) 
\; = \; 1 + \sum_{\emptyset \subset V' \subseteq V} 
        \sum_{\scriptstyle I_1 \uplus \dots \uplus I_k = V' \atop \scriptstyle I_1,\dots,I_k \; \hbox{\eightrm ind\'ependants}} 
        a\Bigl(G[\{I_1,\dots,I_k\}]\Bigr) \cdot (x \nu^{I_1}) \cdot \dots \cdot (x \nu^{I_k}).
$$
{\it En particulier,}
$$
p_G(x) \; = \; p_n x^n + p_{n-1} x^{n-1} + \dots + p_1 x
$$
{\it o\`u les $p_k$, $1 \le k \le n$, sont des entiers positifs tels que $p_n + p_{n-1} + \dots + p_1 = p_G(1) = n!$.
De plus, $p_n = a_1 = a(G)$ et $p_1$ est \'egal \`a $1$ si $|E| = 0$ et \'egal \`a $0$ sinon. 
Si $\chi(G)$ est le nombre chromatique de $G$, alors $p_k = 0$, si $k < \chi(G)$, et $p_k > 0$, si $k \ge \chi(G)$,
$p_{\chi(G)} = i_{\chi(G)} \cdot \chi(G)!$.\qeda
}

\bigskip
\medskip

Brenti~[3] a aussi introduit et \'etudi\'e beaucoup de polyn\^omes qui ne furent jamais consid\'er\'es auparavant. 
\`A partir du polyn\^ome chromatique, leurs fonctions d'ensembles peuvent \^etre d\'efinies comme suit~:
$$\openup0pt\eqalign{
1+\chi_{G,\lambda}(\nu) \; &= \; [1+I_G(\nu)]^\lambda \; 
                            = \; \sum_{k=0}^\infty {\lambda \choose k} I_G(\nu)^k, \cr
1+\sigma_{G,\lambda}(\nu) \; &= \; \exp[\lambda I_G(\nu)] \; 
                              = \; \sum_{k=0}^\infty \lambda^k I_G(\nu)^k/k!, \cr
1+\overline{\sigma}_{G,\lambda}(\nu) \; &= \; [1-\lambda I_G(\nu)]^{-1} \; 
                                         = \; \sum_{k=0}^\infty \lambda^k I_G(\nu)^k, \cr
1+\chi_{G,\lambda}(\nu) \; &= \; [1+A_G(-\nu)]^{-\lambda} \; 
                            = \; \sum_{k=0}^\infty \biggl({\lambda \choose k}\biggr) [-A_G(-\nu)]^k, \cr
1+\tau_{G,\lambda}(\nu) \; &= \; \exp[\lambda A_G(\nu)] \; 
                            = \; \sum_{k=0}^\infty \lambda^k A_G(\nu)^k/k!, \cr
1+\overline{\tau}_{G,\lambda}(\nu) \; &= \; [1-\lambda A_G(\nu)]^{-1} \; 
                                       = \; \sum_{k=0}^\infty \lambda^k A_G(\nu)^k. \cr
}$$
Finalement, une comparaison avec la proposition~6.2 fournit les identit\'es
$$\openup2pt\eqalign{
1 + (1-x) \cdot \overline{P}_{G,x}(\nu) \; &= \; 1 + \overline{\sigma}_{G,\textstyle{x \over 1-x}}(\nu) \quad \; \hbox{et} \cr
1 + ({\textstyle{ 1 \over x}}-1) \cdot \overline{P}_{G,x}(-\nu) \; &= \; 1 + \overline{\tau}_{G,\textstyle{1 \over x-1}}(\nu),
\quad \hbox{d'o\`u} \cr
}$$

\medskip

\noindent
{\sc Proposition 6.5.} (Brenti~[3]) 
$$\textstyle
\overline{P}_{G,x}(\nu) \; = \; {1 \over 1-x} \cdot \overline{\sigma}_{G,\textstyle{x \over 1-x}}(\nu)
                        \; = \; {x \over 1-x} \cdot \overline{\tau}_{G,\textstyle{1 \over x-1}}(-\nu).\qeda
$$

\bigskip
\bigskip


%%%%%%%%%%%%%%%%%%%
%
                %     
%  Appendice I    %
%
                %
%%%%%%%%%%%%%%%%%%%


\centerline{\bf 7. Appendice~I~: Les travaux de Gessel et Stanley}

\bigskip

\noindent
Une d\'erivation de notre polyn\^ome chromatique par rapport \`a plusieurs \'el\'ements fournit~:
$$\openup2pt\eqalign{
1+\chi_{G,\lambda}(\nu) \; &= \; 
[1+I_G(\nu)]^{\lambda}, \cr
\partial^s \chi_{G,\lambda}(\nu)/\lambda \; &= \; 
[1+I_G(\nu)]^{\lambda-1} \cdot \partial^s I_G(\nu), \cr
\partial^{\{s,p\}} \chi_{G,\lambda}(\nu)/\lambda(\lambda-1) \; &= \; 
[1+I_G(\nu)]^{\lambda-2} \cdot \partial^s I_G(\nu) \partial^p I_G(\nu), \cr
\partial^{\{s,p,q\}} \chi_{G,\lambda}(\nu)/\lambda(\lambda-1)(\lambda-2) \; &= \; 
[1+I_G(\nu)]^{\lambda-3} \cdot \partial^s I_G(\nu)  \partial^p I_G(\nu) \partial^q I_G(\nu), \cr
}$$
si $\{s,p\}$ (resp.~$\{s,p,q\}$) est une ar\^ete (resp.~un triangle) de $G$, des conditions que l'on supposera
toujours satisfaites dans la suite.

\eject

\noindent
\`A l'aide du th\'eor\`eme~3.1 et de la proposition~3.2, on d\'eduit des expressions positives~:
$$\openup2pt\eqalign{
1+\chi_{G,-\lambda}(-\nu) \; &= \; 
[1+A_G(\nu)]^{\lambda}, \cr
\partial^s \chi_{G,-\lambda}(-\nu)/\lambda \; &= \; 
[1+A_G(\nu)]^{\lambda} \cdot A_{G,s}(\nu), \cr
\partial^{\{s,p\}} \chi_{G,-\lambda}(-\nu)/\lambda(\lambda+1) \; &= \; 
[1+A_G(\nu)]^{\lambda} \cdot A_{G,s}(\nu) A_{G,p}(\nu), \cr
\partial^{\{s,p,q\}} \chi_{G,-\lambda}(-\nu)/\lambda(\lambda+1)(\lambda+2) \; &= \; 
[1+A_G(\nu)]^{\lambda} \cdot A_{G,s}(\nu) A_{G,p}(\nu) A_{G,q}(\nu), \cr
}$$
o\`u les trois premi\`eres \'egalit\'es reprennent les th\'eor\`emes~3.2, 3.4 et 3.3 de Gessel~[10], res\-pectivement.
Gr\^ace \`a la proposition~4.1, on peut r\'ecrire la troisi\`eme expression de la fa\c con suivante~:
$$
\partial^{\{s,p\}} \chi_{G,-\lambda}(-\nu)/\lambda(\lambda+1) \; = \; 
[1+A_G(\nu)]^{\lambda+1} \cdot A_{G,s,p}(\nu).
$$
Cependant, cette expression n'est particuli\`erement int\'eressante que si $\lambda = -1$, puisque, en g\'en\'eral, 
$A_{G,s,p}(\nu)$ n'est pas positif, au moins pour certains sous-graphes engendr\'es de $G$. Le cas $\lambda = -1$
fut utilis\'e par Gessel~[10] pour d\'emontrer son th\'eor\`eme~3.1 correspondant au th\'eor\`eme~4.1 de cet article.

\bigskip

\noindent
Dans l'esprit du paragraphe~6, calculons
$$\matrix{
\displaystyle \sum_{\lambda=0}^\infty [1+\chi_{G,\lambda}(\nu)] \cdot x^\lambda \qquad \hfill &
\displaystyle \sum_{\lambda=1}^\infty {\partial^s \chi_{G,\lambda}(\nu) \over \lambda} \cdot x^{\lambda-1} \qquad \hfill &
\displaystyle \sum_{\lambda=2}^\infty {\partial^{\{s,p\}} \chi_{G,\lambda}(\nu) \over \lambda(\lambda-1)} \cdot x^{\lambda-2} \hfill \cr
\displaystyle = \; {1 \over 1 - x[1+I_G(\nu)]}, \qquad \hfill &
\displaystyle = \; {\partial^s I_G(\nu) \over 1 - x[1+I_G(\nu)]}, \qquad \hfill &
\displaystyle = \; {\partial^s I_G(\nu) \partial^p I_G(\nu) \over 1 - x[1+I_G(\nu)]}, \hfill \cr
}$$
et posons
$$\matrix{
\displaystyle \sum_{\lambda=0}^\infty \chi_G(\lambda) \cdot x^\lambda \qquad \quad \hfill &
\displaystyle \sum_{\lambda=1}^\infty {\chi_G(\lambda) \over \lambda} \cdot x^{\lambda-1} \qquad \quad \hfill &
\displaystyle \sum_{\lambda=2}^\infty {\chi_G(\lambda) \over \lambda(\lambda-1)} \cdot x^{\lambda-2} \hfill \cr
\displaystyle =: \; {p_G(x) \over (1-x)^{n+1}}, \qquad \quad \hfill &
\displaystyle =: \; {q_G(x) \over (1-x)^{n  }}, \qquad \quad \hfill &
\displaystyle =: \; {r_G(x) \over (1-x)^{n-1}}. \hfill \cr
}$$
Pour les fonctions d'ensembles $P_{G,x}(\nu)$, $Q_{G,x}(\nu)$ et $R_{G,x}(\nu)$ d\'enombrant les poly\-n\^omes $p$, $q$ et $r$,
respectivement, on obtient alors l'analogue de la proposition~6.3~:

\bigskip

\noindent
{\sc Proposition 7.1.} {\it On a}
$$\openup2pt\eqalign{
1 + P_{G,x}(\nu) \; &= \; 
\Bigl(1 - {x \cdot I_G[(1-x)\nu] \over 1-x}\Bigr)^{-1}, \cr 
\partial^s Q_{G,x}(\nu) \; &= \; 
\Bigl(1 - {x \cdot I_G[(1-x)\nu] \over 1-x}\Bigr)^{-1} \cdot 
{\partial^s I_G[(1-x)\nu] \over 1-x}, \cr
\partial^{\{s,p\}} R_{G,x}(\nu) \; &= \; 
\Bigl(1 - {x \cdot I_G[(1-x)\nu] \over 1-x}\Bigr)^{-1} \cdot 
{\partial^s I_G[(1-x)\nu] \over 1-x} {\partial^p I_G[(1-x)\nu] \over 1-x}.  \cr
}$$
{\it Alors avec les nombres $i_k$ des propositions~6.1 et~6.3 on a notamment ($i_1 = 0$ si $\{s,p\}$ est une ar\^ete de $G$)}
$$\openup2pt\eqalign{
p_G(x) \; &= \; n! \cdot x^n + i_{n-1} \cdot (n-1)! \cdot x^{n-1}(1-x) + \cr
          & \quad \;\; \dots + i_2 \cdot 2 \cdot x^2(1-x)^{n-2} + i_1 \cdot x(1-x)^{n-1}, \cr
q_G(x) \; &= \; (n-1)! \cdot x^{n-1} + i_{n-1} \cdot (n-2)! \cdot x^{n-2}(1-x) + \cr
          & \quad \;\; \dots + i_2 \cdot x(1-x)^{n-2} + i_1 \cdot (1-x)^{n-1}, \cr
r_G(x) \; &= \; (n-2)! \cdot x^{n-2} + i_{n-1} \cdot (n-3)! \cdot x^{n-3}(1-x) + \cr
          & \quad \;\; \dots + i_2 \cdot (1-x)^{n-2}.\qeda \cr
}$$

\bigskip

Pour des ensembles de sommets non vides, deux \`a deux disjoints et ind\'ependants $I_1,\dots,I_k$, utilisons de nouveau le graphe
$G[\{I_1,\dots,I_k\}]$ introduit dans le paragraphe~6.
Si, pour le sommet $s \in V$, il existe un $i \in \{1,\dots,k\}$ tel que $s \in V_i$, notons $a_s \bigl( G[\{I_1,\dots,I_k\}] \bigr)$ 
le nombre d'orientations acycliques du graphe $G[\{I_1,\dots,I_k\}]$ dont le sommet correspondant \`a $V_i$ est la source unique. 
De m\^eme, si pour les deux extr\'emit\'es de l'ar\^ete $\{s,p\}$, il existe des $i,j \in \{1,\dots,k\}$ tels que $s \in V_i$ et
$p \in V_j$, notons $a_{s,p} \bigl( G[\{I_1,\dots,I_k\}] \bigr)$ le nombre d'orientations acycliques du graphe $G[\{I_1,\dots,I_k\}]$
dont le sommet correspondant \`a $V_i$ est la source unique et dont le sommet correspondant \`a $V_j$ est le puits unique
(nous supposons ici que $G$ ne contient aucun sommet isol\'e, voir la d\'efinition~4.1).

On d\'emontre alors exactement comme dans le paragraphe~6 (en s'appuyant, de plus, sur les propositions~3.2 et 4.1)~:

\bigskip

\noindent
{\sc Proposition 7.2.} (Gessel~[10]) {\it On a}
$$\openup2pt\eqalign{
P_{G,x}(\nu) \; &= \; \sum_{\scriptstyle \emptyset \subset I_1 \uplus \dots \uplus I_k \subseteq V 
                            \atop \scriptstyle I_1,\dots,I_k \; \hbox{\eightrm ind\'ependants}} 
a\Bigl(G[\{I_1,\dots,I_k\}]\Bigr) \cdot (x \nu^{I_1}) \cdot \dots \cdot (x \nu^{I_k}), \cr
\partial^s Q_{G,x}(\nu) \; &= \; \sum_{\scriptstyle s \in I_1 \uplus \dots \uplus I_k \subseteq V 
                                       \atop \scriptstyle I_1,\dots,I_k \; \hbox{\eightrm ind\'ependants}} 
\!\!\!\!\!\!\!\!\!\!\!\!\!x^{-1} \cdot a_s\Bigl(G[\{I_1,\dots,I_k\}]\Bigr) \cdot (x \nu^{I_1}) \cdot \dots \cdot (x \nu^{I_k}), \cr
\partial^{\{s,p\}} R_{G,x}(\nu) \; &= \; \sum_{\scriptstyle s,p \in I_1 \uplus \dots \uplus I_k \subseteq V 
                                               \atop \scriptstyle I_1,\dots,I_k \; \hbox{\eightrm ind\'ependants}} 
\!\!\!\!\!\!\!\!\!\!\!\!\!x^{-2} \cdot a_{s,p}\Bigl(G[\{I_1,\dots,I_k\}]\Bigr) \cdot (x \nu^{I_1}) \cdot \dots \cdot (x \nu^{I_k}). \cr
}$$
{\it En particulier,}
$$\openup2pt\eqalign{
p_G(x) \; &= \; p_n x^n + p_{n-1} x^{n-1} + \dots + p_1 x, \cr
q_G(x) \; &= \; q_{n-1} x^{n-1} + q_{n-2} x^{n-2} + \dots + q_1 x + q_0, \cr
r_G(x) \; &= \; r_{n-2} x^{n-2} + r_{n-3} x^{n-3} + \dots + r_1 x + r_0, \cr
}$$
{\it o\`u les $p_k$, $q_k$ et $r_k$ sont des entiers positifs (dans le cas des $r_k$ il faut supposer, de plus, que $G$ 
ne contient aucun sommet isol\'e) tels que $p_G(1) = n!$, $q_G(1) = (n-1)!$ et $r_G(1) = (n-2)!$
ainsi que $p_n = a(G)$, $q_{n-1} = a_s(G)$ et $r_{n-2} = a_{s,p}(G)$. 
Si $\chi(G)$ est le nombre chromatique de $G$ et $k < \chi(G)$, alors $p_k = 0$, $q_{k-1} = 0$ et $r_{k-2} = 0$ 
ainsi que $p_{\chi(G)} = i_{\chi(G)} \cdot \chi(G)!$, $q_{\chi(G)-1} = i_{\chi(G)} \cdot (\chi(G)-1)!$ et 
$r_{\chi(G)-2} = i_{\chi(G)} \cdot (\chi(G)-2)!$.  Si $k \ge \chi(G)$, on a $p_k > 0$, et $q_{k-1} > 0$ si $G$ est connexe.\qeda
}

\bigskip

\noindent
\'Evidemment, on a aussi les expressions directes~:

\bigskip

\noindent
{\sc Proposition 7.3.}
\vskip-10pt
$$\openup2pt\eqalign{
x   \cdot Q_{G,x}(\nu) \; = \; 
&-\log \Bigl(1 - {x \cdot I_G[(1-x)\nu] \over 1-x}\Bigr), \cr
x^2 \cdot R_{G,x}(\nu) \; = \; 
&\Bigl(1 - {x \cdot I_G[(1-x)\nu] \over 1-x}\Bigr) \cdot \log \Bigl(1 - {x \cdot I_G[(1-x)\nu] \over 1-x}\Bigr) \cr
&+ {x \cdot I_G[(1-x)\nu] \over 1-x} \cdot \bigl[1-\log(1-x)\bigr].\qeda \cr 
}$$

\bigskip

Notons que la positivit\'e des coefficients du polyn\^ome $r_G(x)$ est le r\'esultat principal de l'article~[10] de Gessel
(d\'emontr\'e sur plus qu'une page \`a l'aide du th\'eor\`eme fondamental de Stanley sur les $P$-partitions)
tandis que le polyn\^ome $q_G(x)$ n'y figure pas.


\bigskip
\medskip


Remarquons finalement que Stanley~[22] a introduit et \'etudi\'e la fonction chromatique $X_G = X_G(x_1,x_2,x_3,\dots)$ 
que l'on peut, avec l'aide des fonctions d'ensembles, d\'efinir comme suit~:
$$
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]. 
$$


   
\bigskip
\bigskip



%%%%%%%%%%%%%%%%%%%%
%
                 %     
%  Appendice II    %
%
                 %
%%%%%%%%%%%%%%%%%%%%


\centerline{\bf 8. Appendice~II~: se passer des fonctions d'ensembles}

\bigskip

On pourrait \^etre f\^ach\'e de cette volont\'e syst\'ematique d'imposer les fonctions d'en\-sembles ou, qui pis est, 
leurs fonctions g\'en\'eratrices. C'est pourquoi il nous semble particuli\`erement important de bien expliciter 
plusieurs m\'ethodes permettant de s'en passer. Comme indiqu\'e dans le paragraphe~2, il s'agit de construire 
des mod\`eles combinatoires infinis qui ne font intervenir que les cardinalit\'es. 

\medskip

Rempla\c cons donc chaque sommet $v \in V$ de notre graphe simple $G = (V,E)$ par une famille infinie $V_v$ de sommets, 
et relions (par une ar\^ete) deux sommets $u' \in V_u$ et $v' \in V_v$ avec $u,v \in V$ et $u \ne v$, 
si et seulement si $u$ et $v$ sont reli\'es dans le graphe~$G$. 
Ces d\'efinitions sont assez naturelles tandis qu'il n'est point clair s'il faut relier deux sommets diff\'erents
d'un m\^eme ensemble $V_v$. En effet, pour tout $v \in V$, on a le choix de laisser $V_v$ comme ensemble 
ind\'ependant infini ou bien de le remplacer par un graphe complet infini. Si l'on se d\'ecide, pour tout $v \in V$,
en faveur du graphe complet (resp.~de l'ensemble ind\'ependant), le graphe infini obtenu \`a partir de $G$
est not\'e $G_{\overline{\infty}}$ (resp.~$G_\infty$).

Soit $V = \{1,2,\dots,n\}$. Alors les fonctions d'ensembles (ou bien leur fonctions g\'en\'eratrices) comme
$I_{G_\infty}(\nu)$, $\chi_{G_\infty,\lambda}(\nu)$, $A_{G_\infty}(\nu)$, $A_{G_\infty}^*(\nu)$ et $A_{G_\infty,t}(\nu)$
(partout, $G_\infty$ peut \^etre remplac\'e par $G_{\overline{\infty}}$) sont, en effet, des fonctions g\'en\'era\-trices
du type exponentiel en des variables (alg\'ebriquement) ind\'ependantes $v_1,v_2,\dots,v_n$, dont le coefficient
de $(v_1^{i_1}/i_1!) \cdot \dots \cdot (v_n^{i_n}/i_n!)$ compte l'invariant respectif du graphe obtenu \`a partir de
$G$ en rempla\c cant le sommet $1$ par $i_1$ exemplaires, le sommet $2$ par $i_2$ exemplaires, \dots, le sommet $n$ par $i_n$ 
exemplaires. \'Evidemment, tous ces invariants peuvent \^etre interpr\'et\'es avec l'aide du seul graphe $G$, et les
th\'eor\`emes d\'emontr\'es dans les paragraphes pr\'ec\'edents fournissent des identit\'es pour eux.  
En particulier, l'identit\'e $1+A_{G_{\overline{\infty}}}(\nu) = [1+I_{G_{\overline{\infty}}}(-\nu)]^{-1}$ n'est rien d'autre
que la proposition 5.1 de~[27] tandis que l'identit\'e $\log[1+A_{G_{\overline{\infty}}}(\nu)] = A^*_{G_{\overline{\infty}}}(\nu)$
n'est rien d'autre que la proposition 5.10 de~[27]. (Pour mettre les points sur les i, il faut ajouter que Viennot a remplac\'e 
les variables $v_1,v_2,\dots,v_n$ par des s\'eries sans terme constant et qu'il n'a pas mentionn\'e que, pour chaque ensemble
de ses pi\`eces, le nombre de pyramides form\'ees de ces pi\`eces est divisible par le nombre de pi\`eces, puisque, pour chaque
pi\`ece fix\'ee, le nombre de pyramides ayant cette pi\`ece en guise d'extr\'emit\'e est toujours le m\^eme.)

En fait, m\^eme les inconditionnels des fonctions g\'en\'eratrices en une seule variable~$x$ peuvent s'y retrouver,
puisque, dans toutes les identit\'es pour le graphe $G_\infty$ ou $G_{\overline{\infty}}$, on peut remplacer 
$(\nu)$ par $(x \cdot \nu)$ (m\^eme pour les fonctions d'ensembles). 
La substitution $\nu = 1$, i.~e.~$v_1 = v_2 = \dots = v_n = 1$, est alors bien d\'efinie (ceci est un v\'eritable avantage 
des fonctions g\'en\'eratrices du type exponentiel par rapport aux fonctions d'ensembles). 
Par exemple, le coefficient de $x^k$, $k > 0$, dans $I_{G_{\overline{\infty}}}(x)$ compte, pour notre 
graphe~$G$, le nombre d'ensembles ind\'ependants de cardinalit\'e~$k$; et la sp\'ecialisation 
$1+A_{G_{\overline{\infty}}}(x) = [1+I_{G_{\overline{\infty}}}(-x)]^{-1}$ du th\'eor\`eme~3.1 
n'est rien d'autre que la relation de r\'eciprocit\'e du chapitre~2.1.2 de~[24].

\medskip

Une m\'ethode tout \`a fait diff\'erente pour obtenir des fonctions g\'en\'eratrices (du type exponentiel) en la seule 
variable $V$ consiste \`a remplacer $G = (V,E)$ par le graphe al\'eatoire $G(p,q)$, $p+q = 1$, sur un ensemble infini $V$ de 
sommets, pour lequel la probabilit\'e d'avoir une ar\^ete entre deux sommets quelconques est \'egal \`a $p$, $0 \le p \le 1$
(et tous ces \'ev\'enements sont ind\'ependants). De cette mani\`ere, tous les coefficients de nos fonctions g\'en\'eratrices
(pour les fonctions d'ensembles) deviennent des variables al\'eatoires, qui, dans les identit\'es, ne sont multipli\'ees que
si elles sont ind\'ependantes. Alors, gr\^ace \`a la multiplicativit\'e de l'esp\'erance math\'ematique dans cette situation 
(et sa lin\'earit\'e sans restriction) on peut, dans toutes les identit\'es d\'ej\`a d\'emontr\'ees, remplacer chaque 
variable al\'eatoire par sa valeur moyenne. 

\medskip

Notons, qu'un ensemble de $n$ sommets du graphe $G(p,q)$ est ind\'ependant avec la probabilit\'e $q^{n \choose 2}$. 
On en d\'eduit pour les esp\'erances math\'ematiques~:

\bigskip

\noindent
{\sc Proposition 8.1.} 
$$
1 + I_{G(p,q)} (V) \; = \; 1 + \sum_{n=1}^\infty q^{n \choose 2} \cdot V^n/n!.\qeda
$$

\bigskip

Alors, si $A_{G(p,q)} (V)$ compte le nombre moyen d'orientations acycliques, le th\'eor\`eme 3.1 implique (voir~[28], paragraphe 5)~:

\bigskip

\noindent
{\sc Proposition 8.2.} (Welsh, Janson)
$$
1 + A_{G(p,q)} (V) \; = \; \Bigl[ 1 + \sum_{n=1}^\infty q^{n \choose 2} \cdot (-V)^n/n! \Bigr]^{-1}.\qeda 
$$

\bigskip

Notons $a(n,m)$ le nombre de graphes orient\'es de fa\c con acyclique, qui ont $n$ sommets marqu\'es et $m$ ar\^etes. Il s'ensuit~:

\bigskip

\noindent
{\sc Proposition 8.3.} (Liskovec~[16], Rodionov~[19]) {\it Soit $p+q = 1$. Alors on a}
$$
1 + \sum_{n=1}^\infty \Bigl[ \sum_{m=0}^{n \choose 2} a(n,m) \cdot p^m q^{{n \choose 2}-m} \Bigr] \cdot V^n/n!
\; = \; \Bigl[ 1 + \sum_{n=1}^\infty q^{n \choose 2} \cdot (-V)^n/n! \Bigr]^{-1}.\qeda 
$$

\bigskip

\noindent
Regardons la sp\'ecialisation $p = q = 1/2$ et posons $a(n) \; := \; \sum_{m=0}^{n \choose 2} a(n,m)$.
On obtient alors le r\'esultat de Stanley (voir~[21] ou~[23], chapitre~3.15)~:

\bigskip

\noindent
{\sc Proposition 8.4.} (Stanley, Robinson~[18])
$$
1 + \sum_{n=1}^\infty a(n) \cdot V^n/(2^{n \choose 2}n!)
\; = \; \Bigl[ 1 + \sum_{n=1}^\infty (-V)^n/(2^{n \choose 2}n!) \Bigr]^{-1}.\qeda
$$

\bigskip

\'Evidemment, tous les autres r\'esultats de cet article peuvent \^etre sp\'ecialis\'es de la m\^eme fa\c con que le th\'eor\`eme~3.1.
Cette sp\'ecialisation {\lfq probabiliste\rfq} du th\'eor\`eme~3.3 fournit notamment un des deux th\'eor\`emes principaux de 
l'article~[11], que Gessel a d\'emontr\'e en \'etablissant une relation de r\'ecurrence, dont il a imagin\'e la solution 
\`a l'aide des {\lfq bons d\'enominateurs\rfq}. 

\bigskip
\bigskip

%%%%%%%%%%%%%%%%%%%%
%
                 %     
%  Appendice III   %
%
                 %
%%%%%%%%%%%%%%%%%%%%


\centerline{\bf 9. Appendice~III~: se passer de la commutativit\'e}

\bigskip

Soit $G = (V,E)$, $V = \{1,2,\dots,n\}$, un graphe simple. Associons \`a ses $n$ sommets des variables $v_1,v_2,\dots,v_n$
et supposons que tout mon\^ome contenant une de ces variables au moins deux fois est nul. Ceci ne restreint pas 
la g\'en\'eralit\'e de nos consid\'erations parce que, selon l'appendice pr\'ec\'edent, on peut remplacer $G$ par 
$G_{\overline{\infty}}$ pour obtenir pr\'ecis\'ement les m\^emes r\'esultats que dans~[5] ou dans~[27]. 
\`A la diff\'erence de tous les autres paragraphes, cependant, nous ne supposons la loi commutative pour deux variables 
$v_i$ et $v_j$ que s'il n'y a pas d'ar\^ete entre les deux sommets $i,j \in V$. L'alg\`ebre associative ainsi obtenue 
est not\'ee $A[V]$ comme dans le cas commutatif. Il n'est pas difficile de d\'emontrer que chaque mon\^ome de $A[V]$ 
correspond, de fa\c con bijective, \`a une orientation acyclique du graphe engendr\'e par les sommets qui correspondent 
aux variables du mon\^ome. Pour \'ecrire le mon\^ome, commen\c cons par les variables des sources de l'orientation acyclique 
(ces variables commutent mutuellement puisque l'ensemble des sources est ind\'ependant). En appliquant la m\^eme proc\'edure 
au graphe engendr\'e par les sommets des autres variables du mon\^ome, on finit par obtenir une partition canonique des sommets 
du mon\^ome en ensembles ind\'ependants. Celle-ci est appel\'ee {\it V-d\'ecomposition} ou {\it forme normale de Foata} 
(voir~[24] ainsi que~[5], th\'eor\`eme~1.2).

Notons $A_G(\nu)$, $A_G(0) = 0$, la somme de tous les mon\^omes diff\'erents de $A[V]$ de sorte qu'on recouvre la fonction
$A_G(\nu)$ d\'ej\`a introduite en soumettant toutes les variables \`a la loi commutative. Si $I_G(\nu)$, $I_G(0) = 0$,
d\'esigne la somme de tous les mon\^omes dont les variables commutent mutuellement (ce sont les mon\^omes correspondant aux
ensembles ind\'ependants), alors la d\'emonstration m\^eme de la proposition~3.2, i.~e. le principe d'inclusion-exclusion, 
implique encore que le produit $[1+I_G(-\nu)] \cdot [1+A_G(\nu)]$ d\'enombre les orientations acycliques sans aucune source.
Autrement dit, on a \'etabli le th\'eor\`eme de Cartier et Foata sur l'inversion (de M\"obius) dans le mono\"\i de de
commutation, \`a savoir l'identit\'e (voir~[5], th\'eo\-r\`eme~2.4) $[1+I_G(-\nu)] \cdot [1+A_G(\nu)] = 1$.

Cependant, les coefficients de $-\log[1+I_G(-\nu)]$ ne sont pas toujours des entiers dans le cas non-commutatif 
et la r\`egle $\partial^s -\log[1+I_G(-\nu)] = -[1+I_G(-\nu)]^{-1} \cdot \partial^s I_G(-\nu)$ n'est plus
valable. Voil\`a pourquoi nous nous sommes impos\'es, dans cet article, la commutativit\'e pour toutes 
les variables. 


\bigskip
\bigskip
\bigskip


{\it Remerciements.} En tout premier lieu, je voudrais remercier vivement D.~Foata de son accueil chaleureux \`a Strasbourg
et de ses explications stimulantes en ce qui concerne le livre~[5]. Son aide et assistance sont au-del\`a de toute expression. 
Je remercie aussi E.~Triesch pour tout son appui dans mon projet de th\`ese v\'eritablement lotharingien.



\bigskip
\bigskip
\bigskip


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

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

\medskip

{\baselineskip=9pt\tenrm
\item{[1]} B.~Bollob\'as, \lfq Modern Graph Theory\rfq, Springer-Verlag, Berlin, 1998.
\smallskip 

\item{[2]} M.~Bousquet-M\'elou, q-\'Enum\'eration de polyominos convexes, {\it J.~Combin.~Theory, Ser.~A} {\bf 64} (1993), 265-288.
\smallskip

\item{[3]} F.~Brenti, Expansions of chromatic polynomials and log-concavity, {\it Trans.~Amer. Math. Soc.}~{\bf 332} (1992), 729-756.
\smallskip 

\item{[4]} T.~H.~Brylawski et J.~G.~Oxley, \lfq The Tutte polynomial and its applications\rfq, in: 
           {\it Matroid Applications}, (ed.~: N.~White) Cambridge University Press, Cambridge (1992), 123-225. 
\smallskip 

\item{[5]} P.~Cartier et D.~Foata, \lfq Probl\`emes combinatoires de commutation et r\'earrangements\rfq, 
           Springer-Verlag, Berlin, 1969.
\smallskip 

\item{[6]} H.~Crapo, A higher invariant for matroids, {\it J.~Combin.~Theory}~{\bf 2} (1967), 406-417.
\smallskip 

\item{[7]} D.~Foata, A noncommutative version of the matrix inversion formula, {\it Adv. Math.}~{\bf 31} (1979), 330-349.
\smallskip 

\item{[8]} E.~R.~Gansner, K.~P.~Vo, The chromatic generating function, {\it Linear and Multilinear Algebra}~{\bf 22} (1987), 87-93.
\smallskip 

\item{[9]} D.~D.~Gebhard et B.~E.~Sagan, Sinks in acyclic orientations of graphs, 
           {\it J.~Combin.~Theory, Ser.~B}~{\bf 80} (2000), 130-146.
\smallskip

\item{[10]} I.~M.~Gessel, Acyclic orientations and chromatic generating functions, {\it Discrete Math.}~{\bf 232} (2001), 119-130.
\smallskip 

\item{[11]} I.~M.~Gessel, Counting acyclic digraphs by sources and sinks, {\it Discrete Math.}~{\bf 160} (1996), 253-258.
\smallskip 

\item{[12]} C.~Greene et T.~Zaslavsky, On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, 
            non-radon partitions, and orientations of graphs, {\it Trans. Amer.~Math.~Soc.}~{\bf 280} (1983), 97-126.
\smallskip 

\item{[13]} A.~Huck, \lfq Fl\"usse und Wege in Graphen\rfq, Bonn, 1997.
\smallskip

\item{[14]} B.~Lass, \lfq Funktionen z\"ahlen\rfq, Diplomarbeit, 1997. 
\smallskip 

\item{[15]} N.~Linial, Graph colouring and monotone functions on posets, {\it Discrete Math.}~{\bf 58} (1986), 97-98.
\smallskip 

\item{[16]} V.~A.~Liskovec, O chisle maksimalnyh vershin sluchajnogo aciklicheskogo orgrafa, 
            {\it Teor. Verojatnost.~i Primenen.}~{\bf 20} (1975), 412-421.
\smallskip 

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

\item{[18]} R.~W.~Robinson, Counting labeled acyclic digraphs, in: {\it New Directions in the Theory of Graphs,
            Proc.~Third Ann Arbor Conference on Graph Theory}, (ed.~: F.~Harary) Academic Press, New York (1971),
            239-273.
\smallskip 

\item{[19]} V.~I.~Rodionov, Javnaja formula dlja chisla pomechennyh aciklicheskih orientirovannyh grafov, 
            {\it Avtomorfnye funkcii i teorija chisel}, Sb.~nauch.~tr., Izhevsk (1987), 22-25.
\smallskip 

\item{[20]} H.~Sachs, \lfq Einf\"uhrung in die Theorie der endlichen Graphen\rfq, Teil II, 
            BSB B.~G.~Teubner Verlagsgesellschaft, 1972.
\smallskip

\item{[21]} R.~P.~Stanley, Acyclic orientations of graphs, {\it Discrete Math.}~{\bf 5} (1973), 171-178.
\smallskip 

\item{[22]} 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{[23]} R.~P.~Stanley, \lfq Enumerative Combinatorics\rfq, Volume 1, Cambridge University Press, Cambridge, 1997.
\smallskip 

\item{[24]} V.~Strehl, Counting domino tilings of rectangles via resultants, \`a para\^\i tre dans 
            {\it Adv.~Appl. Math.}~(2001).
\smallskip

\item{[25]} I.~Tomescu, Graphical Eulerian numbers and chromatic generating functions, {\it Discrete Math.}~{\bf 66} (1987), 315-318.
\smallskip 

\item{[26]} W.~T.~Tutte, \lfq Graph Theory\rfq, Addison-Wesley, 1984.
\smallskip

\item{[27]} G.~X.~Viennot, Heaps of pieces, I~: Basic definitions and combinatorial lemmas, {\it Combinatoire \'enum\'erative}, 
            Proc.~Colloq., Montr\'eal/Can.~1985, {\it Lect.~Notes Math.}~{\bf 1234} (1986), 321-350.
\smallskip

\item{[28]} D.~J.~A.~Welsh, Counting colourings and flows in random graphs, {\it Combinatorics, Paul Erd\"os is Eighty},
            Volume 2, Keszthely (Hungary), 1993, {\it Bolyai Society Mathematical Studies}~{\bf 2} (1996), 491-505. 
\smallskip 
}



\bigskip
\bigskip
\bigskip

\vskip 12pt

\rightline{\sc Bodo Lass}
\rightline{\it Lehrstuhl II f\"ur Mathematik,}
\rightline{\it RWTH Aachen,}
\rightline{\it Templergraben 55,} 
\rightline{\it D-52062 Aachen, Allemagne.} 
\rightline{Courriel: lass@math2.rwth-aachen.de} 

\vskip 6pt

\rightline{et}

\vskip 6pt

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

\vskip 12pt


\end
