%% 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\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 ix _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\x \ou z\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=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 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 \x $. Dans ce cas, on a ou bien $z\>y $, $z\in A \et z\notin B$; ou bien $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 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\y $, alors $z\in A$ et $z\notin B$; si $z\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$. 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 &\Longrightarrow x\y \et y\>x &\Longrightarrow x\>x \et y\>y; &(5)\cr x\y \et y \> x$ ou bien 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