%%  This article has been submitted and accepted for publication in
%%  THE FOATA FESTSCHRIFT, 
%%  a special issue of THE ELECTRONIC JOURNAL OF COMBINATORICS
%%  dedicated to DOMINIQUE FOATA at the occasion of his 60th birthday.
%%
%%  Author(s):		GUO-NIU HAN
%%  Title:		ORDRES BIPARTITIONNAIRES ET STATISTIQUES SUR LES MOTS
%%  Date of submission:	February 9, 1995
%%  TeX version:	plain TeX
%%  File size (approx):	24 kB
%%  Number of pages:	5
%%  Author's email:	guoniu@math.u-strasbg.fr
%%
%%
\message{ [Typset : TeX Plain format.]}

\hsize=11.25cm    
\vsize=18cm       
\parindent=12pt   \parskip=0pt 
\font\smcp=cmcsc8 
\headline={\ifnum\pageno>1 {\smcp the electronic journal of combinatorics 3 (2) (1996), \#R3\hfill\folio} \fi} 
    
\pageno=1 
 

\ifnum\mag=1200
\hoffset=7 mm   
\voffset=8 mm   
\fi
 

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


% PPPPPPPPPPPP Debut des macros privees PPPPPP 
\catcode`\@=11

\font\eightrm=cmr8         \font\eighti=cmmi8
\font\eightsy=cmsy8        \font\eightbf=cmbx8
\font\eighttt=cmtt8        \font\eightit=cmti8
\font\eightsl=cmsl8        \font\sixrm=cmr6
\font\sixi=cmmi6           \font\sixsy=cmsy6
\font\sixbf=cmbx6

% Fontes AMS

\font\tengoth=eufm10   

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

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

% Nouvelles familles pour les maths

\def\tenpoint{%
  \textfont0=\tenrm \scriptfont0=\sevenrm 
  \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\tenrm
  \let\bigf@nt=\tenrm\let\smallf@nt=\sevenrm}%
  \textfont1=\teni  \scriptfont1=\seveni  
  \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\teni}\let\old=\oldstyle
  \textfont2=\tensy \scriptfont2=\sevensy 
  \scriptscriptfont2=\fivesy
  \def\calfont{\fam2 \tensy}%
  \textfont\itfam=\tenit
  \def\it{\fam\itfam\tenit\let\bigf@nt=\tenit 
  \let\smallf@nt=\eightit}%
  \textfont\slfam=\tensl
  \def\sl{\fam\slfam\tensl}%
  \textfont\bffam=\tenbf \scriptfont\bffam=\sevenbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\tenbf\let\bigf@nt=\tenbf 
  \let\smallf@nt=\sevenbf}%
  \textfont\ttfam=\tentt
  \def\tt{\fam\ttfam\tentt}%
  \abovedisplayskip=13pt plus 3pt minus 9pt
   \belowdisplayskip=11pt plus 3pt minus 9pt
    \abovedisplayshortskip=6pt plus 3pt
     \belowdisplayshortskip=11pt plus 3pt minus 9pt
  \smallskipamount=3pt plus 1pt minus 1pt
  \medskipamount=6pt plus 2pt minus 2pt
  \bigskipamount=12pt plus 4pt minus 4pt
  \normalbaselineskip=13pt
  \setbox\strutbox=
    \hbox{\vrule height8.5pt depth3.5pt width0pt}%
  \normalbaselines\rm}

\def\eightpoint{%
  \textfont0=\eightrm \scriptfont0=\sixrm 
  \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\eightrm
  \let\bigf@nt=\eightrm\let\smallf@nt=\sixrm}%
  \textfont1=\eighti  \scriptfont1=\sixi  
  \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\eighti}\let\old=\oldstyle
  \textfont2=\eightsy \scriptfont2=\sixsy 
  \scriptscriptfont2=\fivesy
  \def\calfont{\fam2 \eightsy}%
  \textfont\itfam=\eightit
  \def\it{\fam\itfam\eightit
  \let\bigf@nt=\eightit\let\smallf@nt=\eightit}%
  \textfont\slfam=\eightsl
  \def\sl{\fam\slfam\eightsl}%
  \textfont\bffam=\eightbf \scriptfont\bffam=\sixbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\eightbf
  \let\bigf@nt=\eightbf\let\smallf@nt=\sixbf}%
  \textfont\ttfam=\eighttt
  \def\tt{\fam\ttfam\eighttt}%
  \abovedisplayskip=9pt plus 3pt minus 6pt
   \belowdisplayskip=\abovedisplayskip
    \abovedisplayshortskip=4pt plus 3pt
     \belowdisplayshortskip=9pt plus 3pt minus 6pt
  \smallskipamount=2pt plus 1pt minus 1pt
  \medskipamount=4pt plus 2pt minus 1pt
  \bigskipamount=9pt plus 3pt minus 3pt
  \normalbaselineskip=10pt
  \setbox\strutbox=\hbox{\vrule height7pt depth2pt width0pt}%
  \normalbaselines\rm}

\tenpoint

\def\cal#1{{\calfont#1}}
\def\bb#1{{\bbfont#1}}
\def\goth#1{{\gothfont#1}}


\def\pc{\pcprep}
%\def\pcprep{\bgroup\def\'##1{%
%   \expandafter\accent 19 ##1}\def\'e{\'E}\dosmallcap}
\def\pcprep{\bgroup\dosmallcap} % Han Modifie
\def\dosmallcap #1#2|%
  {\edef\firstletter{#1}% 
   \edef\otherletters{#2}%         
   \bigf@nt\expandafter\uppercase\expandafter{\firstletter}%
   \smallf@nt\expandafter\uppercase\expandafter{\otherletters}\egroup}

\def\pd#1 {\pc#1| }

%PPPPPPPPPPPP dactylographie francaise PPPPPPPPP 

{\catcode`\;=\active
  \catcode`\:=\active
   \catcode`\!=\active
    \catcode`\?=\active
\gdef\frenchdactylography{\frenchspacing
      \catcode`\;=\active
       \catcode`\:=\active
        \catcode`\!=\active
         \catcode`\?=\active
\def;{\relax\ifhmode\ifdim\lastskip>\z@
       \unskip\fi\kern\fontdimen2 
       \font\kern -1.2 \fontdimen3 \font\fi\string;}%
\def:{\relax\ifhmode\ifdim\lastskip>\z@\unskip\fi
      \penalty\@M\ \fi\string:}%
\def!{\relax\ifhmode\ifdim\lastskip>\z@
       \unskip\fi\kern\fontdimen2 \font \kern -1.1 
         \fontdimen3 \font\fi\string!}%
\def?{\relax\ifhmode\ifdim\lastskip>\z@
       \unskip\fi\kern\fontdimen2 \font \kern -1.1 
        \fontdimen3 \font\fi\string?}%
}}
% fin \frenchdactylography

\frenchdactylography
% \frenchspacing

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

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

%PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 
% Les sections

\long\def\section#1\endsection 
      {\bigskip{\bf#1\unskip}\pointir}

\long\def\sectiona#1\endsection 
     {\bigskip\vbox{\bf#1\unskip}\par\nobreak}

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

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

\def\virg@le{\relax
     \ifmmode\string,
      \else{\rm\string,}%
       \fi}

\def\point@virgule{\relax
     \ifhmode
      \ifdim\lastskip>\z@\unskip\fi
       \kern\fontdimen2 \font\kern -1.2 \fontdimen3 \font
        {\rm\string;}%
         \else\ifmmode
          \mathpunct{\string;}%
           \fi\fi}

\def\deux@points{\relax
     \ifhmode
      \ifdim\lastskip>\z@\unskip\fi
       \penalty\@M\space{\rm \string:}%
        \else\ifmmode
         \mathrel{\string:}%
          \fi\fi}

{\catcode`\(=\active 
  \catcode`\)=\active 
   \catcode`\,=\active 
    \catcode`\;=\active 
     \catcode`\:=\active 
\gdef\specialit{%
      \catcode`\(=\active  
      \gdef({\ifmmode\string(\else{\rm\string(}\fi}%
       \catcode`\)=\active  
     \gdef){\ifmmode\string)\else{\rm\string)}\fi}%
        \catcode`\,=\active  
      \gdef,{\virg@le}%
         \catcode`\;=\active  
       \gdef;{\point@virgule}%
          \catcode`\:=\active  
       \gdef:{\deux@points}%
           \it}}
%---------------------------- 
\def\th#1 #2\enonce{\medbreak
              \pc#1| {#2\unskip}\pointir
               \bgroup\specialit}

\def\endth{\ifdim\lastskip<4pt\vskip-\lastskip
            \medskip\fi\egroup
            \frenchdactylography}

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

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

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

\def\qed{\lower 2pt\hbox{%
     \vrule\vbox to 10pt{\hrule width 4pt
      \vfill\hrule}\vrule}}

\def\cqfd{\unskip\penalty 500\kern 10pt\qed}
%----------------------------

\font\ninerm=cmr9

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

\def\demi{\sfrac 12}

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

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

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

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

%PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
%reference pour un article :
\def\article#1|#2|#3|#4|#5|#6|#7|
    {{\leftskip=7mm\noindent
     \hangindent=2mm\hangafter=1
     \llap{[#1]\hskip.35em}{#2}\pointir
     #3, {\sl #4}, t.\nobreak\ {\bf #5}, {\oldstyle #6},
     p.\nobreak\ #7.\par}}
%reference pour un livre :
\def\livre#1|#2|#3|#4|
    {{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
    \llap{[#1]\hskip.35em}{#2}\pointir
    {\sl #3}\pointir #4.\par}}
%reference complementaire :
\def\divers#1|#2|#3|
    {{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
     \llap{[#1]\hskip.35em}{#2}\pointir
     #3.\par}}


\magnification=1200
%PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
% Les op\'erateurs math\'ematiques

\def\maj{\mathop{\rm maj}\nolimits}
\def\inv{\mathop{\rm inv}\nolimits}

\def\maju{\mathop{\rm maj}_U\nolimits}
\def\majv{\mathop{\rm maj2}_U\nolimits}
\def\invu{\mathop{\rm inv}_U\nolimits}
\def\Card{\mathop{\rm Card}\nolimits}
%PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
% Les symboles

\def\S{\hbox{\tengoth S}}
\def\[{{ [\![ }}
\def\]{{ ]\!]}}
\def\inter#1#2{\]#1,#2\]_U}

\def\suite#1#2{#1_1#1_2\cdots#1_{#2}}
\def\sousuite#1#2#3{#1_{#2_1}#1_{#2_2}\cdots
   #1_{#2_{#3}} }

\def\>{\succ}
\def\<{\not\succ}
\def\scalaire#1#2{\langle#1\,,\,#2\rangle}
\def\scalairepro#1#2#3{\scalaire{\Fact_j#1}{\inter {#2_j}{#3}}}


\def\et{\hbox{\ {\rm et}\ }}
\def\ou{\hbox{\ {\rm ou}\ }}
\def\si{\hbox{\ {\rm si}\ }}
%PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP


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

\centerline{\bf Ordres bipartitionnaires et statistiques sur les mots}
\medskip
\centerline{Guo-Niu  HAN \footnote{$(^*)$}{Avec le concours du
programme des Communaut\'es Europ\'eennes en Combinatoire
Alg\'ebrique, 1994-95.}}

\bigskip
\centerline{\sl D\'edi\'e \`a Dominique Foata \`a l'occasion de son 
 soixanti\`eme anniversaire}
\bigskip
\centerline{Submitted: February 9, 1995; Accepted: March 28, 1995}
\bigskip
%PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP

%----------------------------------------------------------
{\eightpoint
{\pc R\'esum\'e|}\pointir
Soit $U$ un ensemble de couples de lettres. Foata et Zeilberger
[FZ] ont introduit les $U$-statistiques pour les mots quelconques.
Dans cette note, on \'etablit une condition n\'ecessaire et suffisante
pour que les deux d\'efinitions ``$\maju$" et  ``$\majv$", qu'on
rencontre dans le cas classique [H], sont \'equivalentes. Il est
remarquable que cette condition est exactement la m\^eme que celle
qui a \'et\'e trouv\'ee pour l'\'equidistribution des deux statistiques 
``$\maju$" et ``$\invu$". 
}

%----------------------------------------------------------
\section
1. Introduction
\endsection
%
Soient $X$ un alphabet et $X^*$ le mono\"\i de libre engendr\'e par
$X$. Si $w=\suite xm \in X^*$ est un mot de longueur~$m$, on appelle
{\it r\'earrangement} de $w$ tout mot $u=\sousuite x \sigma m$, o\`u
$\sigma $ est une permutation appartenant \`a ${\S}_m$.  On
note $R(w)$ la classe de tous les r\'earrangements du mot~$w$. 

On repr\'esente les sous-ensembles $U\subset X\times X$ comme
suit : pour tout $x,y\in X$, on \'ecrit $x\> y$ si $(x,y)\in U$ et
$x\< y$ si $(x,y)\notin U$.
Un sous-ensemble $U$ est appel\'e {\it ordre bipartitionnaire},
\footnote{$(^{**})$}{Cette d\'efinition est diff\'erente de celle qui a \'et\'e donn\'ee
dans [FZ]. Le th\'eor\`eme 5 dans la derni\`ere section montre que ces
deux d\'efinitions sont \'equivalentes.} si les deux conditions
suivantes sont remplies : $$
\eqalignno{
z\>y \et y\>x &\Longrightarrow z\>x;  &(1)\cr
z\>y \et x\<y &\Longrightarrow z\>x. &(2)\cr
}
$$

Pour une relation  $U\subset X\times X$ quelconque,  on g\'en\'eralise les
statistiques classiques ``inv" (nombre d'inversions) et  ``maj"
(indice majeur) pour les mots quelconques de la fa\c con suivante.
Soit $w=\suite x m\in X^*$ un mot, on d\'efinit :  
$$
\displaylines{ \invu w=\Card\{(i,j)\mid 1\le i<j\le m, x
_i\>x _j\},\cr \maju w=\sum \{i\mid 1\le i\le n-1,\ x
_i\>x _{i+1}\}.\cr }
$$  

Lorsque $X$ est totalement ordonn\'e, 
l'ordre sous-jacent ``$>$" v\'erifie bien les deux conditions (1) et
(2), et est donc bipartitionnaire. Lorsque le sous-ensemble $U$
est cet ordre, c'est-\`a-dire, $x\>y$ si et seulement si
$x>y$, on a alors $\invu=\inv$ et $\maju=\maj$.
De plus, on peut v\'erifier que les deux statistiques
pr\'ec\'edentes g\'en\'eralisent les statistiques $\inv_k$ et $\maj_k$
introduites dans [CF2]. Un autre exemple d'ordre bipartitionnaire se
trouve dans la section~3. Le nombre des ordres bipartitionnaires $B_r$
sur un alphabet de cardinal~$r$ est donn\'e par la fonction
g\'en\'eratrice suivante~[FZ] :
$$
\eqalign{
\sum_{r\ge 0}B_r {u^r\over r!} 
&= {1\over 3-2e^u}\cr
&=1+2u+10{u^2\over 2!}+74{u^3\over 3!}+730{u^4\over 4!}+9002{u^5\over 5!}+\cdots\cr
}
$$


\medskip

Foata et Zeilberger ont \'etabli le r\'esultat suivant [FZ] :
\th Th\'eor\`eme 1 (\pc Foata| et \pc Zeilberger|)
\enonce Les deux statistiques $\maju$ et\/ $\invu$ sont
\'equidistribu\'ees, si et seulement si le sous-ensemble $U$ est un
ordre bipartitionnaire. 
\endth

Depuis [H], on sait qu'il existe une autre d\'efinition ``$\majv$"
qui est \'equivalente \`a ``$\maj$" dans le cas classique. Cette
statistique peut \^etre aussi g\'en\'eralis\'ee pour un sous-ensemble 
$U\in X\times X$  quelconque. La d\'efinition de  ``$\majv$" se trouve
dans la section~2. Dans cette note, on d\'emontre le th\'eor\`eme
suivant : 
\th Th\'eor\`eme 2
\enonce Les deux statistiques $\maju$ et $\majv$ sont
\'equivalentes, si et seulement si le sous-ensemble  $U$ est un
ordre bipartitionnaire. 
\endth

D'apr\`es les deux th\'eor\`emes pr\'ec\'edents, on peut dire que
les ordres bipartitionnaires sont des objets
combinatoires ``naturels". 

%---------------------------------------------------------
\section
2. Intervalles cycliques 
\endsection
%
Pour $x,y\in X$, l'{\it intervalle cyclique} (g\'en\'eralis\'e), not\'e
$\inter xy$, est d\'efini par   
$$ 
\inter xy = \cases{
\{z\in X \mid  z\>x \et z\<y \},  &si $x\< y$;\cr
\vspace[3pt]
\{z\in X \mid  z\>x \ou z\<y \}, &si $x\>y$.\cr  
}
$$

Parfois, on a besoin d'ajouter l'\'el\'ement $``\infty"$ dans notre alphabet
pour former l'ensemble $[r]\cup\{\infty\}$, et on suppose alors
$x\<\infty\et\infty\>x$ pour tout $x$. Dans ce cas, on a $z\in\inter
x\infty$ si et seulement si $z\>x$. Deux exemples d'
intervalle cyclique se trouvent dans la section~3.

Soient $w=\suite x m \in
X^*$ un mot et $S\subset X$, on note  $$
\scalaire wS=\#\{i \mid 1\le i\le m, x _i\in S\}.
$$

Soient $w=\suite x m, u\in X^*$ deux mots et $S,T\in X$ deux
sous-ensembles. On a les propri\'et\'es suivantes :
$$
\displaylines{
\scalaire w\emptyset =0\, , \ \scalaire wX=m, \cr
\scalaire {wu}S=\scalaire wS + \scalaire uS, \cr
\scalaire wS + \scalaire wT =
\scalaire w{S\cup T}+\scalaire w{S\cap T}.\cr
}
$$


{\pc D\'efinition|}\pointir
Soient $w=\suite x m$ un mot. Avec la convention $x _{n+1}=\infty$,
on d\'efinit :  
$$
\majv w =\sum_{j=1}^m 
\scalaire{\suite x {j-1}}{\inter{x _j}{x _{j+1}}} \ . 
$$ 
La suite $(s_j)_{1\le  j\le  m}$ o\`u 
$
s_j=\scalaire{\suite x {j-1}}{\inter{x _j}{x _{j+1}}}
$ 
est appel\'ee {\it maj-codage} du mot~$w$.

%---------------------------------------------------------
\section
3. Exemple
\endsection
%
Consid\'erons l'alphabet $X=\{0,1,2,\cdots, 6\}$. On v\'erifie que
l'ensemble 
$$
U=\left\{
\matrix{
0\>0,& 0\>1,&&&& \cr
1\>0,& 1\>1,&&&& \cr
2\>0,& 2\>1,& 2\>2,&&& \cr
3\>0,& 3\>1,& 3\>2,&&& \cr
4\>0,& 4\>1,& 4\>2,&&& \cr
5\>0,& 5\>1,& 5\>2,&&& \cr
6\>0,& 6\>1,& 6\>2,& 6\>3,& 6\>4,& 6\>5\cr
}
\right\}
$$ 
est bien un ordre bipartitionnaire. On a par exemple les
intevalles cycliques $\inter 62=\{0,1\}$ et $\inter 23=\inter 24=\inter
25=\{2,3,4,5\}$.
Pour le mot $w=3 1 5 0 1 6 4 0 6 2 5 4 3 2
0$, on a  $\maju w=1+3+4+6+7+9+13+14=57$ et $\majv
w=1+3+4+5+1+6+5+3+6+9+14=57$. Les calculs complets sont
consign\'es dans le tableau suivant : \medskip $$\matrix{
i& 1 & 2 & 3 & 4 & 5&  6&  7&  8&  9&10&  11& 12& 13& 14& 15&\cr
x _i& 3 & 1 & 5 & 0 & 1 & 6 & 4 & 0 & 6 & 2 & 5 & 4& 3& 2 & 0&\cr
\vspace[-5pt]
\hbox{\eightpoint\rm descente}    & - &    &  -  & -&  &- & -&   &- &   &  &    &
-& - &  &  \cr 
s_i&  0&  1 & 0 & 3 & 4 & 5 & 1 & 7 & 4 & 3 & 0& 0&  6& 9 &14& \cr }
$$
\medskip
%---------------------------------------------------------
\section
4. Propri\'et\'es des intervalles cycliques
\endsection
%
Soit $U\in X\times X$ un sous-ensemble. Pour abr\'eger les \'ecritures, notons
$A=\inter y \infty, B=\inter x y , C=\inter x \infty$ pour deux lettres
$x ,y \in X$. On a le r\'esultat suivant :  
\th Lemme 3
\enonce Le sous-ensemble $U$ est un ordre bipartitionnaire, si et
seulement si,  pour tout $x ,y \in X$, les relations entre $A,B$ et $C$
suivants sont remplies : 
\decale{(i)} si $x \<y $, alors $A\cap B=\emptyset, A\cup B=C$;  
\decale{(ii)} si $x \>y $, alors $A\cap B=C, A\cup B=X$.
\endth

{\it D\'emonstration}\pointir
{\it La partie ``si"}\pointir
D'apr\`es la condition (i), pour tout $x ,y $, si $x \<y $ et $z\in A$, alors
$z\in C$. Ceci d\'emontre la relation (1) de la section~1. D'apr\`es la
condition (ii), pour tout $x ,y $, si $x \>y $ et $z\in C$, alors $z\in A$.
Ceci d\'emontre la relation (2) de la section~1.

{\it La partie ``seulement si"}\pointir
Dans le premier cas, i.e., $x \<y $, on v\'erifie :
\decale{$\bullet$} Si $z\in C$, alors $z\>x $. Dans ce cas, on a ou
bien  $z\>y $,  $z\in A \et z\notin B$; ou bien $z\<y $, $z\in B
\et z\notin A$;
\decale{$\bullet$} Si $z\in A$, alors $z\>y $. D'apr\`es la relation (1), on a
$z\>x $, $z\in C$;
\decale{$\bullet$} Si $z\in B$, alors $z\>x  \et z\<y $. On a $z\in C$.

Dans le second cas, i.e., $x \>y $, on v\'erifie :
\decale{$\bullet$} Si $z\in C$, alors $z\>x $, $z\in B$. D'autre part,
d'apr\`es (2), on a $z\>y $ et $z\in A$.
\decale{$\bullet$} Si $z\notin C$, i.e., $z\<x $. Dans ce cas, si $z\>y $,
alors $z\in A$ et $z\notin B$; si $z\<y $, alors $z\notin A$ et $z\in B$.
\cqfd

%--------------------------------------------------------
\section
5. D\'emonstration du th\'eor\`eme 2 
\endsection
%
Posons 
$w'=\suite x {m-1}$. On note $(s_j)_{1\leq j<m}$ et
$(s'_j)_{1\leq j<m-1}$ les maj-codages de~$w$ et de $w'$
respectivement, il est clair qu'on a $s_j=s'_j$ pour
tout $j<m-1$. 
Pour abr\'eger les \'ecritures, notons
$A=\inter {x _m}\infty,  B=\inter {x _{m-1}}{x _m}, C={\inter
{x _{m-1}}\infty} $ et $u=\suite x {m-2}$. On calcule maintenant
$$\eqalign{
\Delta =&s_m+s_{m-1}-s'_{m-1}\cr
=&\scalaire{ux _{m-1}}{A} +\scalaire uB -\scalaire uC \cr
=&\scalaire{x _{m-1}}{A}+\scalaire {u}{ A\cup B}+
\scalaire {u}{ A\cap B} -\scalaire {u}{C}.\cr
}$$

{\it La partie ``si"}\pointir
Si $x _{m-1}\<x _m$, alors $x _{m-1}\notin A$. D'apr\`es les propri\'et\'es
pr\'ec\'edentes,  on a 
$$
\Delta =0+\scalaire uC +\scalaire u\emptyset -\scalaire uC=0.
$$
D'autre part, si $x _{m-1}\>x _m$, alors
$x _{m-1}\in A$, on a 
$$
\Delta =1+\scalaire uX +\scalaire uC -\scalaire uC=m-1.
$$
D'o\`u $\maju w=\majv w$ par r\'ecurrence sur la longueur $m$ du
mot~$w$. 

{\it La partie ``seulement si"}\pointir
Puisque $\maju w=\majv w$ pour tout~$w$, on a $\Delta =0$ si
$x _{m-1}\<x _m$ et  $\Delta =m-1$ si $x _{m-1}\>x _m$. Dans le premier cas, on a
$
\Delta =0+\scalaire {u}{ A\cup B}+
\scalaire {u}{ A\cap B} -\scalaire {u}{C}=0
$
pour {\it tout} $u$ de longueur $m-2$, et forc\'ement $A\cap
B=\emptyset$ et $A\cup B=C$; et dans le second cas, on a
$
\Delta =1+\scalaire {u}{ A\cup B}+
\scalaire {u}{ A\cap B} -\scalaire {u}{C}=m-1
$
pour {\it tout} $u$ de longueur $m-2$, et forc\'ement $A\cap
B=C$ et $A\cup B=X$. D'apr\`es le lemme pr\'ec\'edent, le sous-ensemble
$U$ est donc un ordre bipartitionnaire.\cqfd

%--------------------------------------------------------
\section
6. Structures des ordres bipartitionnaires
\endsection
%
D'apr\`es la d\'efinition de l'ordre bipartitionnaire, on a imm\'ediatement les propri\'et\'es
suivantes :
$$
\eqalignno{
x\<y \et z\>y &\Longrightarrow x\<z; &(3)\cr
x\<y \et y\<z &\Longrightarrow x\<z; &(4)\cr
x\>y \et y\>x &\Longrightarrow x\>x \et y\>y; &(5)\cr
x\<y \et y\<x &\Longrightarrow x\<x \et y\<y. &(6)\cr
}
$$
Soit $U\subset X\times X$ un sous-ensemble quelconque. Pour tout $x,y\in X$, on dit
que la lettre $x$ est {\it incomparable} \`a $y$, si $x\>y \et y \> x$ ou bien
si  $x\<y \et y \< x$. On note $x\approx y$ si $x$ est incomparable \`a $y$,
et la relation ``$\approx$" est appel\'ee {\it relation d'incomparabilit\'e}
d\'efinie par $U$.

\th Lemme 4
\enonce Si $U\subset X\times X$ est un ordre bipartitionnaire, alors la
relation d'incom\-para\-bilit\'e~``$\approx$" d\'efinie par $U$ est une
relation d'\'equivalence. \endth

{\it D\'emonstration}\pointir
La reflexivit\'e et la sym\'etrie sont \'evidentes d'apr\`es la d\'efinition.
Pour la transitivit\'e, on suppose $x\approx y\et y\approx z$. D'abord, si
$x\>y \et y\> x$, on a $y\>y$ d'apr\`es (5). On a alors $y\>z \et z\>y$.
Ainsi, par la relation (1), on a $x\approx z$. Dans le second cas, si $x\<
y\et y\< x$, c'est la m\^eme v\'erification.\cqfd
\medskip

{\pc D\'efinition|}\pointir
Une {\it bipartition ordonn\'ee} de $X$ est une suite ordonn\'ee $(B_1, B_2,
\cdots, B_k)$ de blocs non vides, disjoints deux \`a deux, de reunion $X$, dont
certains peuvent \^etre soulign\'es.

\th Th\'eor\`eme 5
\enonce Une relation $U$ est bipartitionnaire, si et seulement s'il existe une
bipartition ordonn\'ee $B=(B_1, B_2, \cdots, B_k)$ de $X$, tel que
$$
y\>x \Longleftrightarrow 
{x\in B_l, y\in B_h, \hbox{\it avec } l<h;\atop 
\hbox{\it ou bien } x,y\in B_l, \hbox{\it avec $B_l$ soulign\'e}.}
\eqno(7)
$$
\endth

{\it D\'emonstration}\pointir
La partie ``si" est triviale : il est suffit de v\'erifier les deux relations (1) et
(2) de la section 1. Pour la partie ``seulement si", d'apr\`es le lemme
pr\'ec\'edent, l'ensemble quotient $X/\!\joinrel\approx$ de $X$ par
rapport \`a la relation d'incomparabilit\'e ``$\approx$" existe. Il est clair
qu'avec l'ordre induit par la relation $U$, cet ensemble
$X/\!\joinrel\approx$ est totalement ordonn\'e. Soient $B_1, B_2, \cdots,
B_k$ les \'el\'ements de $X/\!\joinrel\approx$ suivant cet ordre total. On
peut v\'erifier la relation (7) avec la suite de $B_1, B_2, \cdots, B_k$ ainsi
d\'efinie. \cqfd

\medskip
{\it Exemple}\pointir
Pour la relation $U$ donn\'ee dans la section 3, la bipartition associ\'ee est 
${\let\s=\underline
B=(\{\s 0,\s 1\},  \{\s 2\} , \{3,4,5\}, \{6\}
)}$.





%PPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
%\vfill\eject\vglue 2cm

{\eightpoint
\vskip 1cm
\centerline{BIBLIOGRAPHIE}
\nobreak
\bigskip
%\overfullrule=0pt

\article CF1|R. J. {\pc Clarke|} et D. {\pc Foata|}|Eulerian
Calculus, I : Univariable Statistics|Europ. J. Combinatorics|15|1994|345-362|


\divers CF2|R. J. {\pc Clarke|} et D. {\pc Foata|}|Eulerian
calculus, II : An extension of Han's fundamental transformation, \`a para\^\i tre dans
{\sl Europ. J. Combinatorics}|


\divers FZ|D. {\pc Foata|} et D. {\pc Zeilberger|}|Graphical Major Indices, soumis pour
publication, 1995|


\article K|K. W. J.  {\pc Kadell|}|Weighted inversion numbers,
restricted growth function, and standard Young tableaux|J.
Comb. Theory, Ser. A|40|1985|22-44|


\article H|G.-N. {\pc Han|}|Une transformation fondamentale sur les
r\'earrangements de mots|Advances in Math.|105|1994|26-41|


}

\medskip
{\eightpoint
\rightline{\hbox to 5cm{\hrulefill}}
\rightline{I.R.M.A., Universit\'e Louis Pasteur \& C.N.R.S.}
\rightline{7, rue Ren\'e Descartes, 67084 Strasbourg Cedex, France}
\rightline{email : \tt guoniu@math.u-strasbg.fr}
}

\bye






.
