\def\edate{\ifcase\month\or January\or February\or March\or 
April\or May\or
   June\or July\or August\or September\or
October\or November\or December\fi\space
   \number\day,\space\number\year}

\hoffset=1cm
\voffset=1cm
%%
\magnification=1200
\hsize=11.25cm
\vsize=18cm
\parskip 0pt
\parindent=12pt
\frenchspacing
\font\smc=cmcsc10
\font\cmmi=cmmi8


%begin macros
\def \inv{\mathop{\rm inv} \nolimits}
\def \maj{\mathop{\rm maj} \nolimits}
\def \desbf{\mathop{\bf des} \nolimits}
\def \des{\mathop{\rm des} \nolimits}
\def \den{\mathop{\rm den} \nolimits}
\def \exc{\mathop{\rm exc} \nolimits}
\def\epsilon{\varepsilon}
\def\C{B}

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

\def\halmos{\penalty 500 \hbox{\qed}\par\smallskip}

\font\eightbf=cmbx8
\font\eightrm=cmr8 \font\sixrm=cmr6 
\font\eighttt=cmtt8
\font\eightit=cmti8

\def\diag{\mathop{\rm diag}\nolimits}
\def\card{\mathop{\rm card}\nolimits}
\def\proof{{\smc Proof.\enspace }}
\def\bfc{{\bf c}}
\long\def\proclaim #1. #2\endproclaim{\medbreak
{\bf #1.\enspace}{\sl#2}\par\medbreak}


\catcode`\@=11

\def\eightpoint{%
  \textfont0=\eightrm \scriptfont0=\sixrm 
\scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\eightrm}%
\textfont\itfam=\eightit
  \def\it{\fam\itfam\eightit}%
\textfont\bffam=\eightbf 
  \def\bf{\fam\bffam\eightbf}%
  \abovedisplayskip=9pt plus 2pt minus 6pt
  \abovedisplayshortskip=0pt plus 2pt
  \belowdisplayskip=9pt plus 2pt minus 6pt
  \belowdisplayshortskip=5pt plus 2pt minus 3pt
  \smallskipamount=2pt plus 1pt minus 1pt
  \medskipamount=4pt plus 2pt minus 1pt
  \bigskipamount=9pt plus 3pt minus 3pt
  \normalbaselineskip=9pt
  \setbox\strutbox=\hbox{\vrule height7pt depth2pt width0pt}%
  \let\bigf@ntpc=\eightrm \let\smallf@ntpc=\sixrm
  \normalbaselines\rm}

\def\appeln@te{}
\def\vfootnote#1{\def\@parameter{#1}\insert
  \footins\bgroup\eightpoint
  \interlinepenalty\interfootnotelinepenalty
  \splittopskip\ht\strutbox %
  \splitmaxdepth\dp\strutbox \floatingpenalty\@MM
  \leftskip\z@skip \rightskip\z@skip
  \ifx\appeln@te\@parameter\indent \else{\noindent #1\ }\fi
  \footstrut\futurelet\next\fo@t}

\def\footnoterule{\kern-6\p@
  \hrule width 2truein \kern 5.6\p@} % the \hrule is .4pt high

\catcode`\@=12

\catcode`\@=11
\def\matrice#1{\null \,\vcenter {\normalbaselines \m@th
\ialign {\hfil $##$\hfil &&\  \hfil $##$\hfil\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip } #1\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip }}}\,}
\catcode`\@=12


\def\bfu{{\bf u}} 
\def\bfv{{\bf v}} 
\def\bfc{{\bf c}} 
\def\bfd{{\bf d}} 
\def\bfi{{\bf i}} 

%set of macros to typeset the figures

 \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

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

\newbox\tbox
\newbox\tboxa

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

\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

\def\cput(#1,#2)#3{\noalign{\nointerlineskip
\centerput(#1,#2){#3}
\nointerlineskip}}

\def\segment(#1,#2)\dir(#3,#4)\long#5{%
\leftput(#1,#2){\lline(#3,#4){#5}}}

%end of set of macros to typeset the figures

\def\SteiAA{20}
\def\StanAB{19}
\def\RhotAA{18}
\def\ReivAE{17}
\def\ReivAD{16}
\def\ReivAC{15}
\def\ReivAA{14}
\def\NettAA{13}
\def\MacMAB{12}
\def\MacMAE{11}
\def\MacMAA{10}
\def\MacMAC{9}
\def\HanGAE{8}
\def\HanGAH{7}
\def\GaRaAA{6}
\def\FoZeAE{5}
\def\ClFoAC{4}
\def\ClFoAB{3}
\def\ClFoAA{2}
\def\AndrAF{1}

\def\R{{\Bbb R}}
\def\al{\alpha}
\def\be{\beta}
\def\ga{\gamma}
\def\de{\delta}
\def\ep{\varepsilon}
\def\ze{\zeta}
\def\et{\eta}
\def\th{\theta}
\def\vt{\vartheta}
\def\io{\iota}
\def\ka{\kappa}
\def\la{\lambda}
\def\rh{\rho}
\def\si{\sigma}
\def\ta{\tau}
\def\ph{\varphi}
\def\ch{\chi}
\def\ps{\psi}
\def\om{\omega}
\def\Ga{\Gamma}
\def\De{\Delta}
\def\Th{\Theta}
\def\La{\Lambda}
\def\Si{\Sigma}
\def\Ph{\Phi}
\def\Ps{\Psi}
\def\Om{\Omega}
\def\nU{\hbox{${}\kern-2pt\not\kern-2pt U$}}
\def\v#1{\vert #1\vert}
\def\prodl{\prod\limits}
\def\pmaj{\maj_{(h)}}
\def\pdes{\des_{(h)}}
\def\hh{h}
\def\({\left(}
\def\){\right)}
\def\[{\left[}
\def\]{\right]}

\def\cite#1{[#1]}
\let\bold=\bf
\def\frac#1#2{{#1\over #2}}

\vglue 2cm
\centerline{{\bf GRAPHICAL MAJOR INDICES, II}\footnote{}{1991
{\it Mathematics Subject Classification}: Primary 05A15;
Secondary 05A10, 05A30.\hfil\break
\indent
{\it Key words and phrases}: permutations, words, permutation
statistics, major index, inversions, {\cmmi q}-exponential}} 
\bigskip
\centerline{D.~F{\sevenrm OATA}$^\dagger$ {\sevenrm AND}
C.~K{\sevenrm RATTENTHALER}\footnote{$^\dagger$}{Supported in
part by EC's Human Capital and Mobility Program, grant
CHRX-CT93-0400, the second author was also supported by the
Austrian Science Foundation FWF, grant P10191-PHY}}
\bigskip
\centerline{\vbox{\halign{\hfil#\hfil\cr
D\'epartement de math\'ematique, Universit\'e Louis Pasteur,\cr
7, rue Ren\'e Descartes, F-67084 Strasbourg, France\cr
e-mail: {\tt foata@math.u-strasbg.fr}\cr
\noalign{\vskip6pt}
Institut f\"ur Mathematik der Universit\"at Wien,\cr
Strudlhofgasse 4, A-1090 Wien, Austria.\cr
e-mail: {\tt KRATT@Pap.Univie.Ac.At}\cr}}}

\bigskip\medskip
{\narrower\narrower\eightpoint

\noindent
A{\sixrm BSTRACT}.  Generalizations of the classical statistics
``maj" and ``inv" (the major index and the number of inversions)
on words are introduced that depend on a graph on the underlying
alphabet and the behaviour of each letter at the end of a word.
The question of characterizing those graphs that lead to
equidistributed ``maj" and ``inv" is posed and answered. This
work extends a previous result of Foata and Zeilberger who
considered the same problem under the assumption that all
letters have the same behaviour at the end of a word.

}
\bigskip\medskip
\centerline{\bf 0. Introduction}

\medskip
Let $X$ be a finite alphabet and $U$ be a relation on $X$.
Without loss of generality we may assume $X=\{1,2,\dots,r\}$. As
$U$ is a subset of $X\times X$, the relation $U$ can also be
considered as a directed graph without multiple edges on $X$.
This explains the `graphical' in our title. Given such a relation
$U$, in \cite{\FoZeAE} extensions
$\maj'_U$ and $\inv'_U$ of the classical major index and the
number of inversions, respectively, were introduced for words
$w=x_1x_2\dots x_m$ with letters from $X$ by
$$
\eqalignno{\maj'_U w&=\sum _{i=1} ^{m-1}i\cdot 
\chi(x_{i+1}U x_i)&(0.1{\rm a})\cr
\inv'_U w&=\sum _{1\le i<j\le m} ^{}\chi(x_{j}U x_i).
&(0.1{\rm b})\cr}
$$
(Here, as usual, $\chi({\cal A})=1$ if $\cal A$ is true, and
$\chi({\cal A})=0$ otherwise.) Note that $\maj'_<$ is the classical
major index $\maj$ (introduced by MacMahon \cite{\MacMAC,
\MacMAB} as ``greater index", see also \cite{\AndrAF, Def.~3.5}),
$$
\maj w =\sum _{i=1} ^{m-1}i\cdot \chi(x_{i+1}< x_i),
$$
 and $\inv'_<$
is the usual number of inversions (often attributed to Netto
\cite{\NettAA, pp.~92f}, though he cites earlier occurences;
maybe the first occurence under this name is \cite{\RhotAA}; but
probably MacMahon \cite{\MacMAE, \MacMAB} was the first to
consider inversions of words instead of just permutations; see
also \cite{\AndrAF, Def.~3.4}), 
$$
\inv w=\sum _{1\le i<j\le m} ^{}\chi(x_{j}< x_i).
$$

Let ${\bold c}=(c(1),c(2),\dots,c(r))$ be a sequence of $r$
nonnegative integers, and let $v$ be the (non-decreasing) word
$v=1^{c(1)}2^{c(2)}\dots r^{c(r)}$. We will denote by $R(v)$ (or by
$R(\bold c)$ if there is no ambiguity) the class of all
rearrangements of the word $v$, i.e., the class of all words
containing exactly $c(i)$ occurences of the letter $i$ for all
$i=1,2,\dots,r$. Then MacMahon \cite{\MacMAE, \MacMAB}
showed that $\maj$ and $\inv$ are equidistributed on each
rearrangement class $R(\bold c)$ (see also \cite{\AndrAF,
Cor.~3.8}). This motivates to pose the same question for the
generalized major index and generalized number of inversions:

{\it For which relations $U$ on $X$ are
$\maj'_U$ and $\inv'_U$ equidistributed 
on each rearrangement class
$R(\bfc)$?}

This question was answered in \cite{\FoZeAE, Theorem~1} by
giving a full characterization of all such relations $U$. More
precisely, there it is shown that
\proclaim Theorem~A. The statistics $\maj'_U$ and $\inv'_U$ are
equidistributed on each rearrangement class $R(\bfc)$
if and only if $U$ is a ``bipartitional"
relation.
\endproclaim

To make this understandable, we have to explain what a bipartitional
relation is.

\medskip
D{\eightrm EFINITION}. A relation $U$ on $X$ is said to be
{\it bipartitional\/} if there exists a partition 
$(B_1,B_2,\dots,B_k)$ of the set $X$ into blocks $B_l$ together
with a vector $(\be_1,\be_2,\dots,\be_k)$ of $0$'s and $1$'s
such that $x\,U y$ if and only if either (1) $x\in B_l$, $y\in
B_{l'}$, and $l<l'$, or (2) $x,y\in B_l$, and $\be_l=1$.

\medskip
In words, there are two different types of blocks $B_l$, those
with associated $\be_l=0$, let us call them {\it
$\nU$-blocks\/}, and those with associated $\be_l=1$, let us
call them {\it $U$-blocks\/}. Then $x\,U y$ if and only if $x$ is
in an ``earlier" block than $y$, or if both $x$ and $y$ are in the
same $U$-block. In particular, if $x,y$ are elements of the same 
$\nU$-block then we have $x\nU y$ and $y\nU x$.

\medskip
For later use we record that Han \cite{\HanGAE} has given the
following axiomatic characterization of bipartitional relations.

\proclaim Proposition. A relation $U$ on $X$ is bipartitional if
and only if $(1)$ $x\,U y$ and $y\,U z$ imply $x\,Uz$, and $(2)$
$x\,Uy$ and $z\nU y$ imply $x\,Uz$.
\endproclaim

{\it More general\/} major indices and inversion numbers have been
introduced when the underlying alphabet~$X$ is partitioned into
two subsets. For {\it signed permutations\/}, for example, Reiner
\cite{\ReivAA}, \cite{\ReivAC}, \cite{\ReivAD}, while developing his theory 
of $B_n$ $P$-partitions,
was lead to define a major index by making a
distinction between {\it positive\/} and {\it negative\/} integers.
This idea was extended to {\it words\/} by Clarke and Foata~\cite{\ClFoAA},
\cite{\ClFoAB}, \cite{\ClFoAC} who considered {\it small\/} letters and {\it large\/}
letters and could calculate the corresponding generating
functions. Finally, Theorem~2 proved in~\cite{\FoZeAE} that involved
another definition of the major index closely related to the
definitions used by the previous three authors, suggested that
a {\it more general\/} equidistribution result was to be
discovered, if major index and inversion number for
words with two kinds of letters could be adequately defined.

The purpose of this paper is to state and prove such a result.
It is the content of Theorem~B below. This theorem contains both
Theorem~A and Theorem~2 of \cite{\FoZeAE} as special cases
(see the Remark after Theorem~\C). It can even be
considered as a merge of Theorem~A and Theorem~2 of
\cite{\FoZeAE} into a single theorem. 

Of course, the new major index $\maj_U$ and inversion number
$\inv_U$ introduced in this paper will have to generalize the
major index and inversion number of \cite{\FoZeAE}. For their
definitions we need to partition the underlying alphabet~$X$ 
into two disjoint subsets
$X=X_n\dot\cup X_d$. (The subscripts ``$n$" and ``$d$" stand for
{\it no descent\/} and {\it descent\/} at the end of the word, as
will be explained in section~1.) Now let $U$ be a relation on~$X$
and given a word $w=x_1x_2\ldots x_m$ with letters from~$X$
define
$$
\eqalignno{\maj_U w&=\sum_{i=1}^{m-1} i\cdot
\chi(x_{i+1}Ux_i)+m\cdot\chi(x_m\in X_d);&(0.3{\rm a})\cr
\inv_U w&=\sum_{1\le i<j\le m}\chi(x_jUx_i)
+|\{i:x_i\in X_d\}|.&(0.3{\rm b})\cr}
$$
Note that the difference between $\maj_U w$ and $\maj'_U w$ equals 0 if
the last letter belongs to $X_n$ and equals
the length of the word $w$ if the last letter of $w$ belongs to
$X_d$. The difference between $\inv_U w$ and $\inv'_U w$ is simply
the number of letters of the word $w$ that belong to $X_d$.

As done for the previous pairs of statistics we can ask the
following question : 

{\it For which relations $U$ on~$X$ are
$\maj_U$ and $\inv_U$ equidistributed
on each rearrangement class $R(\bfc)$?} 

The main purpose
of this paper is to answer this question by fully characterizing
all such relations~$U$.

\proclaim Theorem \C. Let $X=X_n\dot\cup X_d$ be a given
partition. Then the statistics $\inv_U$ and $\maj_U$
are equidistributed on each rearrangement class $R(\bfc)$, if and only if
$U$ is bipartitional and ``compatible with the partition $X=X_n\dot\cup X_d$."
\endproclaim

To make this statement understandable, we have to explain what
``compatible" means.

\medskip
D{\eightrm EFINITION}. A relation~$U$ is said to be {\it compatible
with the partition\/} $X=X_n\dot\cup X_d$,
if for all $x\in X_n$ and $y\in X_d$ the relations
$x\,Uy$ and $y\not\kern-2pt Ux$ hold.

\medskip
Thus, a bipartitional relation $U$ is compatible with the partition
$X=X_n\dot\cup X_d$ if and only if $U$ is bipartitional
on {\it each\/} of the subalphabets $X_n$, $X_d$, and is such
that for all $x\in X_n$ and $y\in X_d$ the relations
$x\,Uy$ and $y\not\kern-2pt Ux$ hold. This can be made even more
explicit. Let $(B_1,B_2,\ldots,B_k)$ be the partition of $X$ and
$(\be_1,\be_2,\ldots,\be_k)$ the 0-1 vector associated with the
bipartitional relation $U$. Then there is an integer $\hh$, $1\le
\hh\le k$, such that $X_n=B_1\dot\cup B_2\dot\cup \cdots\dot\cup B_\hh $ and
$X_d=B_{\hh +1}\dot\cup B_{\hh +2}\dot\cup \cdots\dot\cup B_k$.

Recall \cite{\FoZeAE} that a bipartitional relation $U$ can also be visualized as
follows: Again let $U=(B_1,B_2,\ldots, B_k)$,
be the partition associated with~$U$
and let $(\beta_1,\beta_2,\ldots,\beta_k)$ be the associated
0-1 vector. Rearrange the elements of~$X$ in a row in such a
way that the elements of $B_1$ come first, in any order, then the
elements of~$B_2$, etc. Then $U$ will consist of all the block
products $B_l\times B_{l'}$ with $l<l'$, as well as the block
product $B_l\times B_l$ whenever $\beta_l=1$.

In Figure 1, for instance, the underlying relation
consists of four blocks $(B_1,B_2,B_3,B_4)$; the 0-1 vector is
$(1,0,0,1)$. 

\midinsert
\def\segment(#1,#2)\dir(#3,#4)\long#5{%
\leftput(#1,#2){\lline(#3,#4){#5}}}

\newbox\partitionalA
 
\setbox\partitionalA=\vbox{\offinterlineskip 
\segment(0,0)\dir(0,-1)\long{40}
\segment(0,0)\dir(1,0)\long{40}
\segment(40,0)\dir(0,-1)\long{40}
\segment(0,-40)\dir(1,0)\long{40}
\segment(5,0)\dir(0,-1)\long{40}
\segment(0,-35)\dir(1,0)\long{40}
\segment(0,-15)\dir(1,0)\long{40}
\segment(25,0)\dir(0,-1)\long{40}
\segment(0,-20)\dir(1,0)\long{40}
\segment(20,0)\dir(0,-1)\long{40}
\centerput(3,-39){$U$}
\centerput(3,-29){$U$}
\centerput(3,-19){$U$}
\centerput(3,-10){$U$}
\centerput(12,-10){$U$}
\centerput(22,-10){$U$}
\centerput(32,-10){$U$}
\centerput(12,-19){$U$}
\centerput(-5,-10){$B_4$}
\centerput(-5,-19){$B_3$}
\centerput(-5,-29){$B_2$}
\centerput(-5,-39){$B_1$}
\centerput(3,-45){$B_1$}
\centerput(12,-45){$B_2$}
\centerput(22,-45){$B_3$}
\centerput(32,-45){$B_4$}
}

\centerline{\box\partitionalA\hskip
37mm} 
\kern 135pt
\centerline{Fig. 1}

\endinsert
By the above considerations, 
this relation is compatible with each partition $X=X_n\dot\cup
X_d$ provided $X_n=B_1\cup \cdots \cup B_\hh $ with
$0\le \hh \le 4$.

\medskip
\overfullrule0pt
R{\eightrm EMARK}.
Notice that Theorem A is the particular case of Theorem~{\C}
when $X_d=\emptyset$. Theorem~2 of \cite{\FoZeAE} refers to
bipartitional relations $(B_1,\ldots, B_k)$,
$(\beta_1,\ldots,\beta_k)$ such that
$X_n=\bigcup\limits_{l\hbox{\sevenrm\ with }\beta_l=0}B_l$ and
$X_d=\bigcup\limits_{l\hbox{\sevenrm\ with }\beta_l=1}B_l$.

\overfullrule5pt
\medskip
We shall give two different proofs of the `if' part of Theorem~\C.
The first proof is by means of generating function techniques and
the so-called ``MacMahon Verfahren" that essentially gives a
general tool for building bijections between words and sets
of non-increasing sequences that record the horizontal word
statistics such as~$\maj_U$ (see sections 2,~3). In an earlier
version of the paper we have also described two $P$-partition proofs
(not reproduced in the final version) inspired by Stanley's
work  \cite{\StanAB}\ and Reiner's
\cite{\ReivAA}, \cite{\ReivAC}, \cite{\ReivAD}, \cite{\ReivAE}.
However, we decided to give a direct proof instead, avoiding all the
definitions that would be necessary to explain the $P$-partition
proofs.
The second proof is by means of an explicit bijection
(section~4). 

In section~5 we prove the `only if' part of
Theorem~B. The proof relies on the `only if' part of Theorem~A.
In addition, we start section~5 with a new proof for the `only if'
part of Theorem~{\C} that is much shorter than the original proof,
thus also providing a new proof of the full Theorem~A. (We
remark that another proof of the `only if' part of Theorem~A, 
which is computer-assisted, was found by Han \cite{\HanGAH}.)
Our proof takes advantage of Han's axiomatic characterization
of bipartitional relations given in the Proposition above. All the
notation that we are going to use throughout the paper is
introduced in section~1.

Finally, in passing, we note that the exponential generating
function for the number $f_r$ of all bipartitional relations on
$X=\{1,2,\dots,r\}$ that are compatible with {\it some\/} partition
of $X$ into two disjoint subsets equals
$$\displaylines{\quad \sum _{r=0} ^{\infty}f_r\frac {u^r}
{r!}=\frac {1} {(3-2e^u)^2}=1+4u+28\frac {u^2} {2!}+268\frac
{u^3} {3!}\hfill\cr
 \hfill{}+3244\frac {u^4} {4!}+47404\frac {u^5}
{5!}+810988\frac {u^6} {6!}+\cdots.\quad\cr}
$$

\medskip
\centerline{\bf 1. Notation and preliminaries}

\medskip
The $q$-notations that we use are
$$\displaylines{
\eqalign{(a;q)_k&=\prodl _{j=0} ^{k-1}(1-aq^j),
\quad {\rm with}\ (a;q)_0=1,\cr
(a;q)_\infty &=\prodl _{j=0} ^{\infty}(1-aq^j)
\cr}\cr
\noalign{\hbox{for the finite and infinite $q$-factorials;}}
{n\brack k}= \frac {(q;q)_n} {(q;q)_k\,(q;q)_{n-k}}\cr
\noalign{\hbox{for the $q$-binomial coefficient, and}}
{ n_1+n_2+\cdots+n_k\brack n_1,n_2,\dots,n_k}=
\frac {(q;q)_{n_1+n_2+\cdots+n_k}}
{(q;q)_{n_1}\,(q;q)_{n_2}\cdots(q;q)_{n_k}},\cr}
$$
for the $q$-multinomial coefficient.

\goodbreak
We shall use a number of special cases of the $q$-binomial 
theorem (cf. \cite{\AndrAF}, Theorem~2.1 or \cite{\GaRaAA},
\S~1.3), 
$$\eqalignno{
\sum _{n=0} ^{\infty}\frac {(a;q)_n} {(q;q)_n}u^n&=\frac
{(au;q)_\infty} {(u;q)_\infty}.&(1.1)\cr
\noalign{\hbox{First, for $a=0$,}}
\sum _{n=0} ^{\infty}\frac {u^n} {(q;q)_n}&=\frac
{1} {(u;q)_\infty},&(1.2)\cr
\noalign{\hbox{and for $u\to -u/a$, $a\to \infty$,}}
\sum _{n=0} ^{\infty}\frac {q^{n\choose 2}u^n} {(q;q)_n}&=
{(-u;q)_\infty} .&(1.3)\cr
\noalign{\hbox{Furthermore, with $a=q^{s+1}$,}}
\sum _{n=0} ^{\infty}{s+n\brack n} u^n&=\frac {1}
{(u;q)_{s+1}},&(1.4)\cr
\noalign{\hbox{and with $a=q^{-s}$, $u\to -uq^s$,}}
\sum _{n=0} ^{\infty}q^{n\choose 2}{s\brack n}
u^n&= {(-u;q)_{s}}.&(1.5)\cr}
$$
Finally, extraction of coefficients of $u^n$ in
(1.4) gives
$$\eqalignno{
{s+n\brack n}&=\sum _{s\ge a_1\ge
\cdots\ge a_n\ge0} ^{}q^{a_1+\cdots +a_n},&(1.6)\cr
\noalign{\hbox{and in (1.5) gives}}
q^{n\choose 2}{s\brack n}&=\sum _{s-1\ge a_1>
\cdots> a_n\ge0} ^{}q^{a_1+\cdots +a_n}.&(1.7)\cr}
$$

Next we review our ``$U$-notations" from the Introduction and
add some new ones. Let $w=x_1x_2\dots x_m$ be a word with
letters from $X$.  Classically we say that $i$, $1\le i\le m-1$,
is a {\it descent\/} of the word $w$, if $x_{i+1}<x_i$. The
number of descents of $w$ is usually denoted by $\des w$.
Furthermore, $\maj w$ is simply the sum of all descents of $w$.

Now let $X$ be partitioned into two disjoint subsets, 
$X=X_n\dot\cup X_d$, and let $U$ be a relation on~$X$.
In analogy with the above terminology, we call $i$, $1\le i\le
m$, a {\it $U$-descent\/} of $w$, if either $x_{i+1}Ux_i$,
or if $i=m$ and $x_i\in X_d$. 
(By the way, this makes the
explanation for our notation $X_n$ and $X_d$ that was promised in the
Introduction. $X_n$ is the set of all letters that create ``n"o
descent at the end, $X_d$ is the set of all letters that create a
``d"escent at the end of a word.)
Also, denote by $\des_U w$ the
number of all $U$-descents of $w$ (including a possible
``descent at the end of $w$" when the last letter belongs
to~$X_d$). Then $\maj_U w$ is the sum of all $U$-descents of
$w$.

Finally, we adopt the ``bipartitional" notations from
\cite{\FoZeAE}, section~2. Namely, given a partition
$(B_1,B_2,\dots,B_k)$ of $X$ together with a 0-1
vector $(\be_1,\be_2,\dots,\be_k)$ we make the following
conventions. Let ${\bold c}$ be the
sequence ${\bf c}=(c(1),c(2),\dots,c(r))$ of
nonnegative integers. As before, let $v=1^{c(1)}2^{c(2)}\dots
r^{c(r)}$ and denote by $R(v)$ (or by $R(\bold c)$) the class of
rearrangements of the word~$v$. If the block $B_l$ consists of
the integers $i_1,i_2,\dots,i_\ell$ and if $u_1,u_2,\dots,u_r$
are $r$ commuting variables, then we write 
$$\eqalign{
{\bold c}\ge0\ &{\rm  for\ }c(1)\ge0,\
c(2)\ge0,\ \ldots,\ c(r)\ge0;\cr
 \vert\bold c\vert\ &{\rm  for\ the\ }
{\it sum}\ c(1)+c(2)+\cdots+c(r);\cr
 {\bold u}^{\bold c}\ &
{\rm for\ the\ {\it monomial\/}\ }u_1^{c(1)} u_2^{c(2)}\cdots
u_r^{c(r)};\cr
 c(B_l)\ &{\rm for\ the\ {\it sequence}\ }
c(i_1),c(i_2),\ldots,c(i_\ell);\cr
c(B_l)\ge0\ &{\rm for\ }c(i_1)\ge0,\ c(i_2)\ge0,\ \dots,\
c(i_\ell)\ge0;\cr
 \v{c(B_l)}\ &{\rm for\ the\ {\it sum}\ }
c(i_1)+c(i_2)+\cdots+c(i_\ell);\cr
 u(B_l)^{c(B_l)}\ &{\rm for\ 
the\ {\it monomial}\ } u_{i_1}^{c(i_1)} u_{i_2}^{c(i_2)}\cdots
u_{i_\ell}^{c(i_\ell)};\cr
\textstyle \sum u(B_l)\ &{\rm for\ the\ {\it sum}\ }
u_{i_1}+u_{i_2}+\cdots+u_{i_\ell}.\cr}
\eqno(1.8)$$
In particular, $\,\v{c(B_l)}\,\choose c(B_l)$ will denote
the multinomial coefficient 
$${
c(i_1)+c(i_2)+\cdots+c(i_\ell)\choose
c(i_1),c(i_2),\dots,c(i_\ell)}.
$$

\bigskip
\centerline{\bf 2. The generating function by $\inv_U$}
\medskip

Let $U$ be a bipartitional relation on $X$
supposed to be compatible with the partition 
$X=X_n\dot\cup X_d$. Denote by $(B_1,B_2,\dots,B_k)$ 
the partition of $X$ and 
$(\be_1,\be_2,\dots,\be_k)$ the 0-1 vector
associated with~$U$. Furthermore, let~$\hh $ be the integer 
such that
$X_n=B_1\dot\cup B_2\dot\cup \cdots\dot\cup B_\hh $ 
and
$X_d=B_{\hh +1}\dot\cup B_{\hh +2}\dot\cup 
\cdots\dot\cup B_k$. Finally, denote by
$$
A^{\inv_U}(q;{\bf c}):
=\sum _{w\in R({\bf c})} ^{}q^{\inv_U w}
$$
the generating function for the class $R({\bf c})$
by~$\inv_U$. Under those assumptions we have the two
identities:
$$\displaylines{\quad
A^{\inv_U}(q;{\bf c})
={\v{\bfc}\brack\v{c(B_1)},\v{c(B_2)},\dots,\v{c(B_k)}}
\times \prod _{l=1} ^{k}{\v{c(B_l)}\choose c(B_l)}
\hfill\cr
\hfill\times{}
\prod_{\scriptstyle 1\le l\le \hh \atop \scriptstyle \be_l=1}
q^{\v{c(B_l)}\choose 2}
\times
\prod_{\scriptstyle \hh +1\le l\le k \atop \scriptstyle \be_l=0}
q^{\v{c(B_l)}}
\times
\prod_{\scriptstyle \hh +1\le l\le k\atop \scriptstyle \be_l=1}
q^{\v{c(B_l)}+ {\v{c(B_l)}\choose 2}},\quad(2.1)\cr
\quad
\sum _{\bfc\ge0}
\frac {A^{\inv_U}(q;\bfc)} {(q;q)_{\bfc}}\bold u^{\bfc}
\hfill\cr
\hfill{}=\frac 
{\prod\limits_{\scriptstyle 1\le l\le \hh \atop \scriptstyle \be_l=1} 
(-\sum u(B_l);q)_\infty
\prod\limits_{\scriptstyle \hh +1\le l\le k\atop \scriptstyle \be_l=1}
(-q\sum u(B_l);q)_\infty}
{\prod\limits_{\scriptstyle 1\le l\le \hh \atop \scriptstyle \be_l=0}
(\sum u(B_l);q)_\infty
\prod\limits_{\scriptstyle \hh +1\le l\le k \atop \scriptstyle \be_l=0}
(q\sum u(B_l);q)_\infty}.
\quad(2.2)\cr}
$$

Call a pair $(i,j)$ a {\it $U$-inversion\/} in the word $w=x_1x_2\ldots x_m$ 
if $i<j$ and $x_jUx_i$. Formula (2.1) follows from
the well-known generating function in the ordinary ``inv" case.
The $q$-multinomial coefficient  is the generating function for
the class of words having exactly $\v{c(B_1)}$ letters equal
to~1, \dots~, $\v{c(B_k)}$ letters equal to~$k$ by ``inv." Such a
word gives rise to exactly $\prod\limits_l {\v{c(B_l)}\choose
c(B_l)}$ words in $R(\bfc)$. Now the letters belonging to
each block $B_l$ such that $1\le l\le \hh $ and $\beta_l=0$
provide no further $U$-inversions and those belonging to
each block $B_l$ such that $\beta_l=1$ bring 
${\v{c(B_l)}\choose 2}$ extra $U$-inversions when they are
compared between themselves. Finally, the term
$|\{i:x_i\in X_d\}|$ that is to be added to the number of
$U$-inversions can also be written  as 
$\sum\limits_{\hh+1\le l\le k}
\v{c(B_l)}$. This proves (2.1).

Finally, we go from (2.1) to (2.2) by a routine $q$-calculation,
using the multinomial theorem.\qed

\bigskip
\centerline{\bf 3. The generating function by $\maj_U$}

\medskip
We keep the same assumptions on~$U$ and the same notations as
in the beginning of section~2. Let 
$$A^{\maj_U}(q;\bfc):=\sum\limits _{w\in R(\bfc)}
^{}q^{\maj_U w}$$ 
denote the generating function for the class
$R(\bfc)$ by the statistics $\maj_U$. Our purpose is to show that
$A^{\maj_U}(q;\bfc)$ is equal to the right-hand side of (2.1), so
that $\inv_U$ and $\maj_U$ are equidistributed on each
rearrangement class~$R(\bfc)$. We first
prove a stronger result, namely, we calculate the generating
function for each class $R(\bfc)$ by the {\it pair\/}
$(\des_U,\maj_U)$ (remember the definition of the statistic
$\des_U$ in section~1) and show by specialization that
the generating polynomial by $\maj_U$ is equal to that
right-hand side. 

\proclaim Proposition 3.1. Let
$$A^{\des_U,\maj_U}(t,q;\bfc):=\sum _{w\in R(\bfc)}
t^{\des_U w }q^{\maj_U w }
$$
be the generating polynomial for $R(\bfc)$ by the pair
$(\des_U,\maj_U)$. Keeping the assumptions of the beginning 
of section~2 and the notations $(1.8)$ we have the
identities :
$$\displaylines{
\quad\frac {A^{\des_U,\maj_U}(t,q;\bfc)} 
{(t;q)_{\v{\bfc}+1}}\hfill\cr
\hfill{}
=\prod _{l=1} ^{k}\! {\v{c(B_l)}\choose c(B_l)} 
\bigg(\sum _{s\ge 0} t^s \prod_
{\scriptstyle 1\le l\le \hh \atop \scriptstyle \be_l=0} 
{\v{c(B_l)}+s\brack \v{c(B_l)}} \prod_
{\scriptstyle 1\le l\le \hh \atop \scriptstyle \be_l=1} 
q^{\v{c(B_l)}\choose 2}
{s+1\brack \v{c(B_l)}}\quad\cr
\hfill{}\times \prod_
{\scriptstyle \hh +1\le l\le k\atop \scriptstyle \be_l=0}
 q^{\v{c(B_l)}}
{\v{c(B_l)}+s-1\brack \v{c(B_l)}}
\prod_
{\scriptstyle \hh +1\le l\le k\atop \scriptstyle \be_l=1} 
q^{\v{c(B_l)}+1\choose 2}
{s\brack \v{c(B_l)}}\bigg)
\ (3.2)\cr
\noalign{\hbox{and}}
\quad
\sum_{\bfc\ge0} \frac {A^{\des_U,\maj_U}(t,q;\bfc)}
{(t;q)_{\v{\bfc}+1}} \bfu^{\bfc}\hfill\cr
\hfill{}=\sum_{s\ge 0} t^s 
\frac
{\prod\limits_
{\scriptstyle 1\le l\le \hh \atop \scriptstyle \be_l=1}
\bigl(-\sum u(B_l);q\bigr)_{s+1} 
\prod\limits_
{\scriptstyle \hh +1\le l\le k\atop \scriptstyle \be_l=1}
\bigl(-q\sum u(B_l);q\bigr)_s} 
{\prod\limits_
{\scriptstyle 1\le l\le \hh \atop \scriptstyle \be_l=0}
\bigl(\sum u(B_l);q\bigr)_{s+1}
\prod\limits_
{\scriptstyle \hh +1\le l\le k\atop \scriptstyle \be_l=0}
\bigl(q\sum u(B_l);q\bigr)_s}.\quad(3.3)\cr
}
$$
\endproclaim

Suppose that (3.2) has been proved.
Multiply both sides of that identity by $(t;q)_{\bfc+1}$ and let
$t$ tend to~1. It is straightforward to see that the
right-hand side tends to the right-hand side of (2.1), so that
$A^{\maj_U}(q;\bfc)=A^{\inv_U}(q;\bfc)$, i.e., $\maj_U$ and
$\inv_U$ are equidistributed. Furthermore, it is again a routine
$q$-calculation to derive (3.3) from (3.2). It then suffices to
prove (3.2).

\medskip
P{\eightrm ROOF OF }P{\eightrm ROPOSITION}~3.1.
We could accomplish this by appealing to the
$P$-partition theory developed by Stanley \cite{\StanAB}; another possibility
would be to make use of the $B_n$ $P$-partition theory
developed by Reiner \cite{\ReivAA}. 
Both theories can be considered as generalizations of the ``MacMahon
Verfahren" (see~\cite{\MacMAC} or \cite{\AndrAF}, chap.~3). Instead
of going through the definitions of ($B_n$) $P$-partitions, we prefer
to give a direct approach, modelled after the MacMahon Verfahren.
As in \cite{\FoZeAE}
\S~4, we proceed as follows:

Let $w=x_1x_2\ldots x_m$ be a word of the class $R(\bfc)$,
so that $m=|\bfc|$. Denote by $w(B_l)$ the {\it subword\/}
of~$w$ consisting of all the letters belonging to~$B_l$
$(l=1,\ldots, k)$. Then replace each letter belonging to~$B_l$ by
$b_l=\min B_l$ (with respect to the usual order). Call 
$\overline w=\overline x_1\overline x_2\ldots \overline x_m$
the resulting word. Clearly the mapping
$$
w\mapsto \bigl(\overline w, w(B_1),\ldots,w(B_l)\bigr)\eqno(3.4) 
$$
is bijective. Moreover, $\des_U w=\des_U\overline w$ and
$\maj_U w=\maj_U\overline w$. Accordingly, the polynomial
$A^{\des_U,\maj_U}(t,q;\bfc)$ is divisible by 
$\prod\limits_l {\v{c(B_l)}\choose c(B_l)}$.

In the sequel, for each $l=1,\ldots, k$ let $m_l=\v{c(B_l)}$.
For each $i=1,2,\ldots,m$ let $z_i$ denote the number of
$U$-descents in the right factor $\overline
x_i \overline x_{i+1}\ldots \overline x_m$ of~$\overline w$
(including one descent in~$m$ if $x_m\in X_d$).
Clearly, $z_1=\des_U \overline w$ and 
$z_1+\cdots +z_m=\maj_U \overline w$.

Now let ${\bf p}=(p_1,\ldots, p_m)$ be a sequence of $m$ integers
satisfying  $s'\ge p_1\ge p_2\ge \cdots\ge p_m\ge 0$, where $s'$
is a {\it given\/} integer. Form the {\it non-increasing\/} word
$v=y_1y_2\ldots y_m$ defined by $y_i=p_i+z_i$ $(1\le i\le m)$ 
and consider the biword
$$
\Bigl(\matrix{v\cr \overline w\cr}\Bigr)=
\Bigl(\matrix{y_1y_2\ldots y_m\cr
\overline x_1\overline x_2\ldots \overline x_m\cr}\Bigr). 
$$
Next rearrange the columns of the previous matrix in such a
way that the mutual orders of the columns with the same bottom
entries are preserved and the entire bottom row is of the form
$b_1^{m_1}b_2^{m_2}\ldots b_k^{m_k}$. We obtain the matrix
$$
\Bigl(\matrix{a_{1,1}\ldots  a_{1,m_1}\cr
b_1\  \ldots\  b_1\cr}
\matrix{\ldots\cr \ldots\cr}
\matrix{a_{k,1}\ldots  a_{k,m_k}\cr
b_k\ \ldots\ b_k\cr}\Bigr).
$$
By construction each of the $k$ words
$a_{1,1}\ldots  a_{1,m_1}$, \dots~, 
$a_{k,1}\ldots  a_{k,m_k}$ is {\it non-increasing\/}. 

Next, if $i<i'$, $\overline x_i=\overline x_{i'}\in B_l$
and $\beta_l=1$, there is necessarily a $U$-descent
within $\overline x_i \overline x_{i+1}\ldots \overline x_{i'}$.
Hence $z_i>z_{i'}$ and 
so $y_i>y_{i'}$. The word
$a_{l,1}\ldots a_{l,m_l}$ 
corresponding to the block $B_l$
will then be {\it strictly decreasing\/}.

On the other hand, $z_m=1$ iff $\overline x_m\in X_d$.
Let $B_l$ be a block of $X_d$, so that $\hh +1\le l$ and
denote by $\overline x_i$ the {\it rightmost\/} letter
of~$\overline w$ that belongs to~$B_l$. If $i=m$, then
$a_{l,m_l}=p_m+z_m\ge 1$; if $i<m$, then, either there is one
letter of $X_n$ in the factor
$\overline x_{i+1}\ldots\overline x_m$ and necessarily one
$U$-descent because $U$ is supposed to be {\it compatible\/}
with $X_n\dot \cup X_d$, or all the letters in that factor are
in~$X_d$ and in particular $z_m=1$. In both cases,
$a_{l,m_l}\ge 1$.
Also note that
$$
a_{l,i}\le y_1=p_1+z_1\le s'+\des_U \overline w
$$
for all $l,i$. Let then $s=s'+\des_U \overline w$. It follows
that each of the words $a_{l,1}\ldots a_{l,m_l}$ satisfies
$$
\eqalign{
s&\ge a_{l,1}\ge \cdots \ge a_{l,m_l}\ge 0,
\hbox{ if $1\le l\le \hh $ and $\beta_l=0$;}\cr
s&\ge a_{l,1}>\cdots >a_{l,m_l}\ge 0,
\hbox{ if $1\le l\le \hh $ and $\beta_l=1$;}\cr
s&\ge a_{l,1}\ge\cdots \ge a_{l,m_l}\ge 1,
\hbox{ if $\hh +1\le l\le k$ and $\beta_l=0$;}\cr
s&\ge a_{l,1}>\cdots >a_{l,m_l}\ge 1,
\hbox{ if $\hh +1\le l\le k$ and $\beta_l=1$.}\cr
}\eqno(3.5)
$$
The mapping $(s',{\bf p},\overline w)\mapsto (s,(a_{l,i}))$ is a
bijection satisfying
$$
\eqalign{s&=s'+\des_U \overline w\,;\cr
\sum_{l,i}a_{l,i}=p_1+\cdots +p_m&+z_1+\cdots +z_m
=\sum_i p_i +\maj_U \overline w.\cr}\eqno(3.6)
$$
Now it follows from (1.4) and (1.6) that
$$
{1\over (t;q)_{m+1}} 
=\sum_{s'\ge 0} t^{s'} \sum_{{s'}\ge p_1\ge\cdots\ge p_m\ge 0} 
q^{p_1+\cdots +p_m},
$$
so that by (3.4)
\overfullrule0pt
$$\displaylines{
{1\over \prod\limits_l{m_l\choose c(B_l)}}
{A^{\des_U,\maj_U}(t,q;\bfc)\over (t;q)_{m+1}}
=\sum_{{s'}\ge 0} t^{s'} 
\sum_{{s'}\ge p_1\ge \cdots \ge p_m\ge 0}\kern-8pt
q^{\Sigma\,p_i} \sum_{\overline w} t^{\des_U \overline w}
q^{\maj_U\overline w}\hfill\cr
\kern.5cm{}
=\sum_{(s',{\bf p},\overline w)} t^{s'+\des_U \overline w}
q^{\Sigma\,p_i+\maj_U\overline w}
=\sum_{(s,(a_{l,i}))} t^s 
q^{\Sigma a_{l,i}}\hfill[{\rm by\ (3.6)}]\cr
\kern.5cm{}
=\sum_{s\ge0} t^s
\prod_{\scriptstyle 1\le l\le \hh \atop \scriptstyle \be_l=0} 
\sum_{s\ge a_{l,1}\ge\cdots\ge a_{l,m_l}\ge 0}\kern-24pt
q^{a_{l,1}+\cdots+a_{l,m_l}} 
\prod_{\scriptstyle 1\le l\le \hh \atop \scriptstyle \be_l=1} 
\sum_{s\ge a_{l,1}>\cdots>a_{l,m_l}\ge 0}\kern-24pt
q^{a_{l,1}+\cdots+a_{l,m_l}}\hfill\cr
\kern .8cm{}\times
\prod_{\scriptstyle \hh +1\le l\le k\atop \scriptstyle \be_l=0} 
\sum_{s\ge a_{l,1}\ge\cdots\ge a_{l,m_l}\ge 1}\kern-24pt
q^{a_{l,1}+\cdots+a_{l,m_l}} 
\prod_{\scriptstyle \hh +1\le l\le k\atop \scriptstyle \be_l=1} 
\sum_{s\ge a_{l,1}>\cdots>a_{l,m_l}\ge 1}\kern-24pt
q^{a_{l,1}+\cdots+a_{l,m_l}}\hfill\cr
\kern.5cm{}
=\sum_{s\ge0} t^s
\prod_{\scriptstyle 1\le l\le \hh \atop \scriptstyle \be_l=0} 
{m_l+s\brack m_l} 
\prod_{\scriptstyle 1\le l\le \hh \atop \scriptstyle \be_l=1} 
q^{m_l\choose 2}{s+1\brack m_l}\hfill\cr
\kern 1.5cm{}\times
\prod_{\scriptstyle \hh +1\le l\le k\atop \scriptstyle \be_l=0} 
q^{m_l}{m_l+s-1\brack m_l} 
\prod_{\scriptstyle \hh +1\le l\le k\atop \scriptstyle \be_l=1} 
q^{m_l+1\choose 2}{s\brack m_l},\hfill\cr 
}
$$
by (1.6) and (1.7). Hence (3.2) is established.\qed

\overfullrule5pt
\bigskip
\centerline{\bf 4. The bijective proof of the `if' part 
of Theorem~\C}

\medskip
Again keep for the relation~$U$ on~$X$ the same assumptions
as in the beginning of section~2. In this
section we construct a bijection $\Ps_U$ from each class
$R(\bold c)$ onto itself, satisfying
$$
\maj_U w=\inv_U \Ps_U(w) \eqno(4.1)
$$
for all words $w\in R(\bold c)$. The construction of the bijection
$\Ps_U$ parallels the bijective construction in 
\cite{\FoZeAE}, \S~8. 

As done in previous papers \cite{\SteiAA}, \cite{\ClFoAA},
\cite{\ClFoAB}, \cite{\ClFoAC}, \cite{\FoZeAE} we add a new
letter $*$ to $X$. Then we extend $U$ to the relation $U^*$ on
$X\cup\{*\}$ by adding the relations $*\,Uj$, $j\in X_d$, to $U$.
In other words, $U^*$ is the bipartitional relation on
$X\cup\{*\}$ with blocks
$(B_1,\dots,B_\hh,\{*\},B_{\hh+1},\dots,B_k)$ and vector
$(\be_1,\dots,\be_\hh,0,\be_{\hh+1},\dots,\be_k)$. Note that for any
word $w$ with letters from $X$ we have  
$$\eqalignno{
\maj_U w&=\maj_{U^*} w*,&(4.2)\cr
\inv_U w&=\inv_{U^*} \hbox{$w*$}.&(4.3)\cr}
$$

Now we make use of a map that was constructed in
\cite{\FoZeAE}, \S~5. There, given a bipartitional relation,
$B$ say, a bijection $\Ph_B$ from each rearrangement class
$R(\bold c)$ onto itself was constructed that satisfies
$$
\maj'_B w=\inv'_B \Ph_B(w) \eqno(4.4)
$$
for any word $w\in R(\bfc)$. This map $\Ph_B$ had the additional
property that it fixes the last letter. To be precise, we use the
above construction with $X$ replaced by $X\cup \{*\}$ and with
the bipartitional relation $B=U^*$.

Let $w$ be a word with letters from $X$. Form the concatenation
$w*$. Then we apply $\Ph_{U^*}$ to $w*$. Since $\Ph_{U^*}$
fixes the last letter, we have $\Ph_{U^*}(w*)=w'*$ for some
word $w'$ with letters from $X$.  This given, we define
$\Ps_U$ by $\Ps_U(w):=w'$. 

That $\Ps_U$ is a bijection is immediate from the construction. Of
course, we also have to check (4.1). Now, we have
$$
\eqalignno{ 
\maj_U w&=\maj'_{U^*}w*\qquad\quad&[{\rm by}\ (4.2)]\cr
&=\inv'_{U^*}\Ph_{U^*}(w*)&[{\rm by}\ (4.4)]\cr
&=\inv'_{U^*}w'*&[{\rm by\ definition}]\cr
&=\inv_{U} w'&[{\rm by\ }(4.3)]\cr
&=\inv_{U}\Ps_{U}(w),&[{\rm by\ definition}]\cr
}
$$
which is exactly (4.1).\quad \qed

\bigskip
\centerline{\bf 5. The proof of the `only if' part of Theorem \C}

\medskip
We start this section by giving a new proof of the `only if' part
of Theorem~A. This new proof is much shorter than the original
one. We remark that this gives also a proof of the complete
Theorem~A, because the `if' part of Theorem~A is contained in
the `if' part of Theorem~\C. (To obtain the `if' part of Theorem~A,
choose the trivial partition $X=X_n\cup\{\}$ in the `if' part of
Theorem~\C.) In our new proof we take advantage of Han's
axiomatic characterization of bipartitional relations given in
the Proposition in the Introduction.  

\medskip
P{\eightrm ROOF OF THE `ONLY IF' PART OF }T{\eightrm
HEOREM}~A. Let $U$ be a relation on $X$ such that
$\maj'_U$ and $\inv'_U$ are equidistributed on each
rearrangement class $R(\bold c)$. We want to show that $U$ is
bipartitional. In view of the Proposition in the Introduction, it
suffices to show 

(U1)\quad $x\,Uy$ and $y\,Uz$ imply $x\,Uz$ for all 
$x,y,z\in X$, 

(U2)\quad $x\,Uy$ and $z\nU y$ imply $x\,Uz$ for all
$x,y,z\in X$. 

\goodbreak
{\it Proof of {\rm(U1)}}.
Let $x,y,z$ be elements in $X$ such that $x\,Uy$ and $y\,Uz$. By
way of contradiction, let us assume that $x\nU z$. We consider
the rearrangement class $R(xyz)$. By our assumptions, we have
$\maj'_U zyx=3$. Since, also by assumption, $\maj'_U$ and
$\inv'_U$ are equidistributed on $R(xyz)$, there must be a word
$v\in R(xyz)$ with $\inv'_U v=3$. We observe that $3$ is the
maximum value that can be attained. So, since $x$ and $z$ occur
in $v$, and since $x\nU z$, we must necessarily have $z\,Ux$,
and $x$ must occur before $z$ in $v$. Thus there are the
following possibilities for $v$: 
$$\eqalign{
v&=xzy,\quad \quad
\hbox{and in addition }y\,Ux,\cr
v&=xyz,\quad \quad \hbox{and
in addition }y\,Ux\hbox{ and }z\,Uy,\cr 
v&=yxz,\quad \quad 
\hbox{and in addition }z\,Uy. \cr}
$$ 
There remain the
following three cases for the relation $U$ on $\{x,y,z\}$,
$$
\vbox{\halign{#\hfil\quad&\hfil$#$\hfil&\qquad
#\hfil\quad&\hfil$#$\hfil&\qquad
#\hfil\quad&\hfil$#$\hfil\cr
Case I.&x\,Uy\,Ux&Case II.&x\,Uy\,Ux&Case III.&x\,Uy\nU x\cr
&x\nU z\,Ux&&x\nU z\,Ux&&x\nU z\,Ux\cr
&y\,Uz\nU y&&y\,Uz\,U y&&y\,Uz\,U y\cr}}
$$

ad Case I. There holds $\maj'_U yzx=0$, but also
$\inv'_U w\ge1$ for any word $w\in R(xyz)$, because of
$x\,Uy\,Ux$. Thus $\maj'_U$ and $\inv'_U$ are not
equidistributed on $R(xyz)$, which is absurd.

ad Case II. There holds $\maj'_U yzx =1$, but also
$\inv'_U w\ge2$ for any word $w\in R(xyz)$, because of
$x\,Uy\,Ux$ and $y\,Uz\,Uy$.  Thus $\maj'_U$ and
$\inv'_U$ are not equidistributed on $R(xyz)$, which is absurd.

ad Case III. There holds $\maj'_U zxy=0$, but also
$\inv'_U w\ge1$ for any word $w\in R(xyz)$, because of
$y\,Uz\,Uy$. Thus $\maj'_U$ and $\inv'_U$ are not equidistributed
on $R(xyz)$, which is absurd.

Altogether this shows that we obtain a contradiction in any case.
Hence we must have $x\,Uz$.

\medskip
{\it Proof of {\rm(U2)}}.
Let $x,y,z$ be elements in $X$ such that $x\,Uy$ and
$z\nU y$. By way of contradiction, let us assume that $x\nU z$. 
Now observe that (U1), which was already established, implies
$y\nU z$. This is because in case $y\,Uz$ we would have $x\,Uy$
and $y\,Uz$, and thus $x\,Uz$, in contradiction with our
assumption. 

Now we consider again the rearrangement class $R(xyz)$. By our
assumptions, we have $\maj'_U yzx=0$. Since, also by
assumption, $\maj'_U$ and $\inv'_U$ are equidistributed on
$R(xyz)$, there must be a word $v\in R(xyz)$ with $\inv'_U v=0$.
Since $x$ and $y$ occur in $v$, and since $x\,U y$, we must
necessarily have $y\nU x$ (and $x$ must occur before $y$ in
$v$). 

There remain the following two cases for the relation $U$ on
$\{x,y,z\}$,
$$
\vbox{\halign{#\hfil\quad&\hfil$#$\hfil&\qquad
#\hfil\quad&\hfil$#$\hfil\cr
Case I.&x\,Uy\nU x&Case II.&x\,Uy\nU x\cr
&x\nU z\,Ux&&x\nU z\nU x\cr
&y\nU z\nU y&&y\nU z\nU y\cr}}
$$

ad Case I. There holds $\maj'_U yxz=3$, but also
$\inv'_U w\le2$ for any word $w\in R(xyz)$, because of $y\nU
z\nU y$. Thus $\maj'_U$ and $\inv'_U$ are not equidistributed on
$R(xyz)$, which is absurd.

ad Case II. There holds $\maj'_U zyx=2$, but also
$\inv'_U w\le1$ for any word $w\in R(xyz)$, because of $x\nU
z\nU x$ and $y\nU z\nU y$.  Thus $\maj'_U$ and
$\inv'_U$ are not equidistributed on $R(xyz)$, which is absurd.

Altogether this shows that we obtain a contradiction in any case.
Hence we must have $x\,Uz$.\quad \qed

\medskip
R{\eightrm EMARK}. The argument above shows that it is even sufficient
to require equidistribution of $\maj'_U$ and $\inv'_U$ only on
rearrangement classes containing only three letters.
Han \cite{\HanGAH} has given another proof of the `only if' part
of Theorem~A based on his axiomatic characterization
of bipartitional relations (the Proposition in the Introduction).
In fact, our proof is directly inspired by his. Instead of
letting the computer 
verify {\it all\/} possible relations $U$
on the letters $\{x,y,z\}$ (there are $2^9=512$ such relations!)
and sorting out the ``right" ones, as he did, we have just
provided
an argument to reduce the number of cases to consider. 

\medskip
P{\eightrm ROOF OF THE `ONLY IF' PART OF }T{\eightrm
HEOREM}~\C.
Let $U$ be a relation on $X=X_n\dot\cup X_d$ such that
$\maj_U$ and $\inv_U$ are equidistributed on each
rearrangement class $R(\bfc)$. First choose $\bfc$ such that only
letters from $X_n$ are chosen. For these rearrangement classes,
$\maj_U$ and $\inv_U$ reduce to $\maj'_U$ and $\inv'_U$,
respectively. Hence, by the `only if' part of Theorem~A, we infer
that $U$ is bipartitional on $X_n$. Secondly, choose $\bfc$ such
that only letters from $X_d$ are chosen. For these
rearrangement classes, $\maj_U$ and $\inv_U$ reduce to
$\maj'_U+\v{\bfc}$ and $\inv'_U+\v{\bfc}$, respectively.  Again,
by the `only if' part of Theorem~A, we infer that $U$ is
bipartitional on $X_d$.

Thus it remains to see how letters from $X_n$ are related to letters
from $X_d$. Take a letter $x\in X_n$ and a letter $y\in X_d$. We want
to show that we must have $x\,Uy$ and $y\nU x$. We establish this by
excluding the other three cases.

Case I: $x\nU y\nU x$. Then $\maj_U xy=2$, $\maj_U yx=0$, but
$\inv_U xy=\inv_U yx=1$. Thus $\maj_U$ and
$\inv_U$ are not equidistributed on $R(xy)$, which is absurd.

Case II: $x\nU y\,U x$. Then $\maj_U xy=3$, $\maj_U yx=0$, but
$\inv_U xy=2$, $\inv_U yx=1$. Thus $\maj_U$ and
$\inv_U$ are not equidistributed on $R(xy)$, which is absurd.

Case III: $x\,U y\,U x$. Then $\maj_U xy=3$, $\maj_U yx=1$, but
$\inv_U xy=\inv_U yx=2$. Thus $\maj_U$ and
$\inv_U$ are not equidistributed on $R(xy)$, which is absurd.

\smallskip
This shows that the only legal possibility is $x\,Uy\nU x$. Hence, $U$
is a bipartitional relation on $X$ that is compatible with the
partition $X=X_n\dot\cup X_d$.\quad  \qed

\goodbreak


\vglue 15pt


\centerline{\bf References}
\medskip

{\eightpoint

\itemitem{\AndrAF.} G. E. Andrews, {\it The Theory of 
Partitions}, Encyclopedia of Mathematics and its
Applications, Vol.~2, Addison--Wesley, Reading, 1976.

\itemitem{\ClFoAA.} R. J. Clarke and D. Foata,
{\it Eulerian calculus I: Univariable statistics},
Europ. J. Combin. {\bf 15} (1994),
345--362.

\itemitem{\ClFoAB.} R. J. Clarke and D. Foata, 
{\it Eulerian calculus II: An extension of Han's fundamental
transformation}, Europ. J. Combin. {\bf 16} (1995),
345--362.

\itemitem{\ClFoAC.} R. J. Clarke and D. Foata,
{Eulerian calculus III: The ubiquitous Cauchy formula},
Europ. J. Combin. (1995) (to appear).

\itemitem{\FoZeAE.} D. Foata and D. Zeilberger,
{\it Graphical major indices}, J. of Computational and Applied
Math. (1995) (to appear).

\itemitem{\GaRaAA.} G. Gasper and M. Rahman,
{\it Basic  hypergeometric series}, Encyclopedia of
Mathematics And  Its Applications~35, Cambridge University
Press, 1990.

\itemitem{\HanGAH.} G.-N. Han, {\it Une
d\'emonstration  ``v\'erificative" d'un r\'esultat de
Foata--Zeilberger sur les relations  bipartitionnaires}, 
J. of Computational and Applied
Math. (1995) (to appear).

\itemitem{\HanGAE.} G.-N. Han,
{\it Ordres bipartitionnaires et statistiques sur les mots},
Electronic J. Combin. (1995) (to appear).

\itemitem{\MacMAC.} P. A. MacMahon,
{\it The indices of permutations and the derivation therefrom of 
functions of a single variable associated with the permutations of 
any assemblage of objects}, Amer. J. Math. {\bf 35} (1913),
282--322.

\itemitem{\MacMAA.} P. A. MacMahon, {\it Combinatory Analysis},
vol.~2, Cambridge University Press, 1916; reprinted by
Chelsea,  New York, 1960.

\itemitem{\MacMAE.} P. A. MacMahon, {\it Two applications
of  general theorems in combinatory analysis}, Proc.
London Math.  Soc., Ser.~II {\bf 15} (1916), 314--321.

\itemitem{\MacMAB.} P. A. MacMahon, {\it Collected Papers: 
Combinatorics},  Vol.~I, MIT Press,
Cambridge,  Mass\-achu\-setts, 1978.

\itemitem{\NettAA.} E. Netto, {\it Lehrbuch der Combinatorik},
Teubner--Verlag, Leipzig, Berlin, 1901; 2nd ed., 1927.

\itemitem{\ReivAA.} V.    Reiner,
{\it Signed posets},
J.~Combin. Theory Ser.~A {\bf  62} (1993),
324--360.

\itemitem{\ReivAC.} V.    Reiner,
{\it Signed permutation statistics}
Europ. J. Combin.  {\bf 14} (1993),
553--567.

\itemitem{\ReivAD.} V.    Reiner,
{\it Signed permutation statistics and cycle type},
Europ. J. Combin.  {\bf 14} (1993),
569--579.

\itemitem{\ReivAE.} V.    Reiner,
{\it Upper binomial posets and signed permutation statistics},
Europ. J. Combin.  {\bf 14} (1993),
581--588.

\overfullrule0pt
\itemitem{\RhotAA.} H. A. Rothe, {\it Sammlung 
combinatorisch-analytischer Abhandlungen}~2
(K.~F.~Hin\-den\-burg, ed.), Leipzig, 1800, pp.
263--305.

\overfullrule5pt
\itemitem{\StanAB.} R. P. Stanley, {\it Ordered structures
and  partitions}, Mem. Amer. Math. Soc. No.~119, 
American Mathematical Society, Providence, R.~I., 1972.

\itemitem{\SteiAA.} E. Steingr\`\i msson,
{\it Permutation statistics of indexed permutations}
Europ. J. Combin. {\bf 15} (1994), 


\bigskip\medskip

{\sixrm
D\'EPARTEMENT DE MATH\'EMATIQUE, UNIVERSIT\'E LOUIS PASTEUR,
7, RUE REN\'E DESCARTES, F-67084 STRASBOURG, FRANCE.

\bigskip
INSTITUT F\"UR MATHEMATIK DER UNIVERSIT\"AT WIEN,
STRUDLHOFGASSE 4, A-1090 WIEN, AUSTRIA.

}

}




\bye