%%a Plain TeX file of the paper
%%%%%Eulerian Calculus, I: Univariable Statistics%%%%
%by Robert J. Clarke and Dominique Foata
%no other format
 
%%possibly adjust :
\hoffset=1cm
\voffset=1cm
%%
\magnification=1200
\hsize=11.25cm
\vsize=18cm
\parskip 0pt
\parindent=12pt
\frenchspacing


%begin macros
\def \inv{\mathop{\rm inv} \nolimits}
\def \maj{\mathop{\rm maj} \nolimits}
\def \des{\mathop{\rm des} \nolimits}
\def \den{\mathop{\rm den} \nolimits}
\def \exc{\mathop{\rm exc} \nolimits}
\def\epsilon{\varepsilon}
\def\sep{\,|\,}

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

\def\halmos{\penalty 500 \hbox{\qed}\par\smallskip}
\let\cqfd=\halmos

\font\eightbf=cmbx8
\font\eightrm=cmr8 \font\sixrm=cmr6 
\font\eighttt=cmtt8
\font\eightsl=cmsl8
\font\eightbf=cmbx8

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

\catcode`\@=11

\def\eightpoint{%
  \textfont0=\eightrm \scriptfont0=\sixrm 
\scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\eightrm}%
\textfont\slfam=\eightsl
  \def\sl{\fam\slfam\eightsl}%
\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


%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

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

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

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

\newif\if@negarg

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

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

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

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

%added: october 93
\def\rfa{\mathop{\rm rf}\nolimits}
\def\lfa{\mathop{\rm lf}\nolimits}
\def\sfa{\mathop{\rm sf}\nolimits}
\def\ad{\mathop{\rm ad}\nolimits}

\newbox\boiteun
\newbox\boitedeux
\setbox\boiteun=\vbox{\offinterlineskip\halign{#\hfil\cr
\vrule  height .4pt depth 0pt width 25pt\cr
\vrule height 5pt depth 0pt width .4pt\kern 24.3pt 
\vrule height 5pt depth 0pt width .4pt\cr
\vrule height .4pt depth 0pt width 5.4pt
\kern19.3pt\vrule height .4pt depth 0pt width .4pt\cr
\kern5pt\vrule height 5pt depth 0pt width .4pt \kern19.3pt
\vrule height 5pt depth 0pt width .4pt\cr
\kern5pt\vrule height .4pt depth 0pt width 20pt\cr
}}
\setbox\boitedeux=\vbox{\offinterlineskip\halign{#\hfil\cr
\vrule  height .4pt depth 0pt width 20pt\cr
\vrule height 5pt depth 0pt width .4pt\kern 19.3pt 
\vrule height 5pt depth 0pt width .4pt\cr
\vrule height .4pt depth 0pt width 5.4pt
\kern14.3pt\vrule height .4pt depth 0pt width .4pt\cr
\kern5pt\vrule height 5pt depth 0pt width .4pt \kern14.3pt
\vrule height 5pt depth 0pt width .4pt\cr
\kern5pt\vrule height .4pt depth 0pt width 5.4pt
\kern9.3pt\vrule height .4pt depth 0pt width .4pt\cr
\kern10pt\vrule height 5pt depth 0pt width .4pt \kern9.3pt
\vrule height 5pt depth 0pt width .4pt\cr
\kern10pt\vrule height .4pt depth 0pt width 5.4pt
\kern4.3pt\vrule height .4pt depth 0pt width .4pt\cr
\kern15pt\vrule height 5pt depth 0pt width .4pt \kern4.3pt
\vrule height 5pt depth 0pt width .4pt\cr
\kern15pt \vrule height .4pt depth 0pt width 5.1pt\cr
}}

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

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

%end macros


\vglue 1.6cm
\centerline{{\bf  Eulerian Calculus, I : Univariable
Statistics}\footnote{\dag}{The paper has been published in
{\sl Europ. J. Combinatorics} (1994) {\bf 15},
345--263.}}   
\vskip 2.8mm 
\centerline{\sevenrm BY}
\vskip 2.8mm
\centerline{R{\sevenrm OBERT} J. C{\sevenrm LARKE}
{\sevenrm AND} D{\sevenrm OMINIQUE} F{\sevenrm OATA}
\footnote{$(^*)$}{Supported in  part  by a  grant of
the Australian Research Council, 1993, while the 
author was on leave at the University of
Adelaide.}} 


\bigskip\bigskip

{\narrower\narrower\eightpoint

\noindent
Further transformations are derived
on the symmetric group and related structures
that extend previous works on the
equidistributions of several classical univariable statistics.

\medskip\noindent
De nouvelles transformations 
sur le groupe sym\'etrique et les structures parentes
sont explicit\'ees et servent \`a prolonger des
travaux ant\'erieurs sur l'\'equidistribution de
plusieurs statistiques classiques \`a une   variable.

}

\bigskip\medskip
\centerline{ 1. I{\sevenrm NTRODUCTION}}
\medskip
This paper is the first one of
a series of three articles (see [ClFo93b] and [ClFo93c]
for the other two), in which we investigate further
extensions of the classical Eulerian Calculus that
involves, first, the constructions of transformations on
the symmetric  group and related structures, then,
explicit calculations of distributions of order statistics
on those structures.

In his treatise on Combinatory Analysis, MacMahon [Mac15]
made an extensive study of the distributions of several
statistics on permutations, or more generally, on
permutations with repeated elements (called {\it
permutations on multisets} by several authors, but
referred to as {\it words} in the present paper). He
introduced the notions of {\it descents}, {\it
excedances}, {\it major index} for finite sequences of
numbers and calculated the first generating functions. 

Those three notions can be defined as follows: let $X^*$
be the free monoid generated by a totally ordered
alphabet~$X$ that for convenience we shall take as being
the subset $[\,r\,]=\{1,2,\ldots, r\}$ $(r\ge 1)$  of the
positive integers with its standard ordering.  The
elements of~$X^*$ are finite {\it words}
$w=x_1x_2\ldots  x_m$ with letters $x_i$ taken
from~$X$. A word~$w'$ is said to be  a {\it rearrangement}
of the word~$w$ if it can be obtained from~$w$ by 
permuting the letters $x_1$, $x_2$,~\dots~, $x_m$ in
some order. The set of all the rearrangements of a  
word~$w$ will be denoted by $C(w)$. Such a  set
necessarily contains a  unique word $v=y_1y_2\ldots
y_m$ whose letters  are in non-decreasing order:
$y_1\le  y_2\le \cdots \le y_m$. There is then a
one-to-one correspondence between rearrangement
classes and non-decreasing words. It will be convenient
to  denote by $\overline w$ the  unique non-decreasing
word in the class $C(w)$ [also equal to $C(\overline w)$].

\goodbreak
Let $w=x_1x_2\ldots x_m$ and let $\overline
w=v=y_1y_2\ldots y_m$ be its  non-decreasing
rearrangement. The {\it  number of excedances}, $\exc
w$,  and the {\it number of descents}, $\des w$, of the
word~$w$ are classically defined as (see [CaFo69]) 
$$ 
\displaylines{ 
\exc w=\#\{i:1\le i\le m,\,x_i>y_i\},\cr 
\des w=\#\{i:1\le i\le  m-1,\, x_i>x_{i+1}\},\cr} 
$$
while the {\it major index}, $\maj w$, is the {\it sum} of
the~$i$'s such that $1\le i\le  m-1$ and $x_i>x_{i+1}$.

MacMahon [Mac15, p.~186] proved that for each
rearrangement class $C(v)$ and each integer~$j$ there 
are as many words $w\in C(v)$ such that $\exc w=j$ as
there are words $w'\in C(v)$ such that $\des w'=j$. To
establish the result, he made use  of his so-called
Master Theorem [Mac15, p.~97], that can be stated as
follows (see [CaFo69, chap.~V] for a non-commutative version):

\medskip
{\it Let $B=(b(i,j))$ $(1\le i,j \le r)$ be a square matrix
with coefficients in a commutative ring, let $X^*$
be the free monoid generated by $X=[\,r\,]$ and let
$u_1$, $u_2$, \dots~, $u_r$ be $r$~commutative
variables. If $w=x_1x_2\ldots x_m$ is a word in~$X^*$
whose non-decreasing rearrangement is
$v=y_1y_2\ldots y_m=1^{c_1}2^{c_2}\ldots r^{c_r}$,
define 
$$
\beta(w)=b(y_1,x_1)b(y_2,x_2)\ldots b(y_m,x_m)\quad
{\it and}\quad
u(w)=u_1^{c_1}u_2^{c_2}\ldots u_r^{c_r}.
$$
Let also  $U$ be the diagonal matrix 
$U={\rm diag}(u_1,u_2,\ldots, u_r)$. Then the following
identity holds
$$
{1\over \det (I_r-BU)}=\sum_w \beta(w)u(w),\leqno(1.1)
$$
where $I_r$ is the identity matrix and where the sum is
over all words $w\in X^*$.}

\medskip
 If $v$ is the non-decreasing word
$1^{c_1}2^{c_2}\ldots r^{c_r}$, we will also denote the
rearrangement class $C(v)$ by $R({\bf c})$ and put
${\bf u}^{\bf c}=u_1^{c_1}u_2^{c_2}\ldots u_r^{c_r}$.
The rearrangement classes will then be indexed by
sequences of non-negative integers ${\bf  c}=(c_1,c_2,\ldots,
c_r)$ of length~$r$. (A more refined notation will be used in
the sequel.) 

When $b(i,j)=t$, if $i<j$, and 1 in the other
cases, it is readily seen that the monomial $\beta(w)$ is
equal to $t^{\exc w}$. Let then
$$
A_{\bf c}(t)=\sum_w t^{\exc w}\qquad (w\in R({\bf c})),
$$
be the generating polynomial for $R({\bf c})$ by the
number of excedances ``$\exc$." The
generating function for those polynomials is then
directly derived from the Master Theorem
$$
{1\over \det (I_r-BU)}=\sum_{\bf c}{\bf u}^{\bf c}
A_{\bf c}(t),\leqno(1.2)
$$
a result already obtained by MacMahon. 

Now the determinant occurring in (1.2) can  be further
evaluated. An easy calculation shows that
$$
\eqalign{
\det(I_r-BU)&=\left|\matrix{1-u_1&-tu_2&\ldots&-tu_r\cr
-u_1&1-u_2&\ldots&-tu_r\cr
\vdots&\vdots&\ddots&\vdots\cr
-u_1&-u_2&\ldots&1-u_r\cr}\right|\cr
&=1-e_1({\bf u})+(1-t)e_2({\bf u})-\cdots+
(-1)^r(1-t)^{r-1}e_r({\bf u}),\cr} $$
where the $e_i({\bf u})$'s are the elementary symmetric
functions in the~$u_i$'s. Taking this
calculation into account after replacing each $u_i(1-t)$
by  $u_i$  and substituting into~(1.2) leads to the
identity  
$$
\sum_{s\ge 0}{t^s\over  (1-u_1)^{s+1}\ldots
(1-u_r)^{s+1}}
=\sum_{\bf c}{\bfu^\bfc\over (1-t)^{c+1}}
A_{\bf c}(t),\leqno(1.3)
$$
where $c=c_1+\cdots+c_r$.
The expression (1.3) is more appropriate for proving that
the left-hand side is actually the generating function
for the polynomials $A_{\bf c}(t)$ in the
``des"-interpretation. See section~2 in which a
calculation is made in a more general case. Those
techniques are standard (see, e.g. [Ga79]). In fact,
MacMahon proved his result on the equidistribution of
``exc" and ``des" by obtaining (1.3) in two different ways,
in the ``exc" and  ``des" interpretations.

Several years later, a ``bijective" proof (as
some people say to-day) was devised to prove the
MacMahon equidistribution property. The so-called {\it
first fundamental transformation} $\Phi$ of $X^*$ onto
itself was constructed (see [CaFo69] and also [Lo83,
chap.~10]); it maps each rearrangement class $C(v)$
onto itself, in a bijective manner, and has the
property that 
$$ 
\exc \Phi(w)=\des w \leqno(1.4) 
$$ 
holds for every $w\in C(v)$. 

For each pair of letters $(a,b)$ and each word
$w=x_1x_2\ldots x_m$ denote by $[a,b](w)$ the
number of subscripts~$i$ such that $1\le i\le m-1$ and
$x_i=a$, $x_{i+1}=b$. If $v=y_1y_2\ldots y_m$ is the
non-decreasing rearrangement of~$w$, denote by
$\displaystyle{b\brack a}(w)$ the number of
subscripts~$i$ such that $1\le i\le m$ and $y_i=b$,
$x_i=a$. As was proved in [CaFo69],  the first fundamental
transformation has the further property that for  each
pair $(a,b)$ satisfying $a>b$, the identity 
$$
[a,b](w)=\left[{b\atop a}\right](\Phi(w))\leqno(1.5)
$$
holds. Of course  property (1.4) is a consequence of (1.5).

A further  analysis of the properties of $\Phi$ shows
that the restriction $a>b$ assumed in~(1.5) can be
relaxed under certain conditions to include equality
$a=b$. The purpose of this paper is to investigate those
conditions. Instead of taking the matrix $B$ as above,
having only 1's on and under the diagonal and $t$ above
it, choose two non-negative integers
$j$ and $k$ such that $j+k=r$. Then form the matrix
$B_k$ of order~$r$ still having only 1's under the
diagonal and only $t$'s above, but let its diagonal,
${\rm diag}\, B_k$, be
made of $j$~1's, followed by $k$~$t$'s, i.e.,
$$
{\rm diag}\,B_k=\vtop{\halign{\hfil#\hfil
&\hfil#\hfil\cr
$(1,\ldots,1,$&$t,\ldots,t)$\cr
\omit\upbracefill&\omit\upbracefill\cr
$j$ times&$k$ times\cr}}\leqno(1.6)
$$
The monomial
$\beta(w)=b(y_1,x_1)\ldots b(y_m,x_m)$ 
attached to the word $w=x_1\ldots x_m$ in the Master
Theorem is then a power of~$t$, say, $t^{\exc_k w}$,
where 

\medskip
\noindent
(1.7) {\it $\exc_k w$ is the number of~$i$ such that 
$1\le i\le m$  and either $x_i>y_i$, or $x_i=y_i$ and
$x_i\ge j+1$.} 

\medskip
A refined definition will be given further
in the paper. The following two questions arise: what
statistic, say ``$\des_k$," must be defined on  $X^*$ that
has the same distribution as ``$\exc_k$" on each
rearrangement class $C(v)$ and that reduces to~``$\des$"
when $k=0$? Suppose that such a statistic can be defined
in simple terms (it can!) and has such a property. The
second question is  how a transformation $\Phi_k$ on
$X^*$ can be constructed that maps each rearrangement
class onto itself and satisfies the identity
$$
\des_k w=\exc_k \Phi_k(w).\leqno(1.8)
$$
In section 2 we show that a calculation \`a la MacMahon
first suggests the definition of the appropriate
statistic~``$\des_k$," that can be stated as:

\medskip
\noindent
(1.9) {\it $\des_k w$ is the number of~$i$ such that 
$1\le i\le m$  and either $x_i>x_{i+1}$, or
$x_i=x_{i+1}$ and $x_i\ge j+1$. (By convention,
$x_{m+1}=j+{1\over 2}$.)} 

\medskip
Section 2 also provides an answer to the first question by
proving  that the generating polynomials for each
rearrangement class $C(v)$ by either ``$\exc_k$," or
``$\des_k$," are the same.

In fact, there  are several statistics ``$\des_{k,D}$" and
``$\exc_{k,D}$" that can be defined and for which
property~(1.8) holds, depending on different total
orders~$D$ we may impose on the interval~$[\,r\,]$. This
leads to proving invariance principles that
essentially say that the  distributions of all those 
statistics ``$\des_{k,D}$" and ``$\exc_{k,D}$" are
independent of the ordering~$D$. All this is the object of
section~3 (see Theorems~3.1 and~3.2).

In  section~4 we recall the construction of the first
fundamental transformation~$\Phi$. Section~5 contains
the main result of the paper, i.e., the construction of
a transformation~$\Phi_k$ that satisfies
identity~(1.8). In fact, the construction can be made for 
each pair $(\des_{k,D},\exc_{k,D})$, as long as the
ordering~$D$ is {\it compatible} with~$k$, a
notion that  will be further defined.

In section~6 we specialize our results to the case of
{\it permutations}. When $c_1=\cdots=c_r=1$,
the polynomial
$$
\sum_w t^{\des w} = \sum_w t^{\exc w} \qquad (w\in 
R({\bf c}))
$$
is the usual {\it Eulerian polynomial} $A_r(t)$ of
order~$r$ (see, e.g., [Ri58, FoSc70]). When ``$\des$" or
``$\exc$" are replaced by ``$\des_k$" or ``$\exc_k$," the
generating polynomial $A_r^k(t)$ thereby obtained
appears to be a natural interpolation between $A_r(t)$
and $t\,A_r(t)$. We have managed to give several explicit
formulas for those polynomials. Steingr\`\i msson [Ste93]
has also generalized the definitions of  ``des'' and ``exc''
from permutations to so-called ``indexed permutations'', 
i.e., elements of the wreath product $Z_k\wr {\cal S}_n$.
As shown in section~6, his model coincides
partly with ours in this permutation case.

In the two subsequent papers we consider joint statistics,
and especially, will study the joint behaviours of
``$\des_k$" with a new major index ``$\maj_k$,''  and
``$\exc_k$" with another new mahonian
statistic~``$\den_k$." We will also calculate the
distributions of those joint statistics using the  algebra
of symmetric functions.

The following notations will be used throughout. Let $r$ be
a positive integer, let $X=[\,r\,]$ and let $k$ be a fixed
integer, $0\le k\le r.$ Put $j=r-k.$ Let 
${\bf c}=(c_1,\ldots,c_j)$  and ${\bf d}=(d_1,\ldots,d_k)$
be two vectors with positive integer components.  Let
$c=c_1+\cdots+c_j$, $d=d_1+\cdots+d_k$ and
$c+d=m$.   We will work with the rearrangement class 
$R({\bf c},{\bf d})$ of all 
$m!/(c_1!\,\ldots\,c_j!\,d_1!\,\ldots\,d_k!)$ 
rearrangements of the non-decreasing word
$v=y_1y_2\ldots y_m=1^{c_1}\ldots
j^{c_j}(j+1)^{d_1}\ldots r^{d_k}$. We call the letters
$1,\ldots,j$ {\it small} and the letters $j+1,\ldots,r$ 
{\it large}. It is convenient to adjoin to the set $X$ one
element $\star$ that is small but greater than any other 
small letter.

\goodbreak
\bigskip
\vfill\eject

\centerline{2. A C{\sevenrm ALCULATION A} L{\sevenrm A}
M{\sevenrm AC}M{\sevenrm AHON}}

\medskip
In this section we take the
natural ordering on $X=[\,r\,]$. If $w=x_1x_2\ldots x_m$ is a
word of the rearrangement class $R(\bfc ,\bfd )$, then
``$\exc_k$" refers to the definition stated in (1.7). It will be
convenient to replace the variables $u_{j+1}$, \dots~, $u_r$ by
$v_1$, \dots~, $v_k$ and write  $\bfu^\bfc $  for
$u_1^{c_1}\ldots u_j^{c_j}$ and $\bfv^\bfd $ for
$v_1^{d_1}\ldots v_k^{d_k}$. However we keep the notation $U$
for the matrix $U={\rm diag}(u_1,\ldots,u_{j},v_1,\ldots, v_k)$.
Now let
$$ 
A_{\bfc,\bfd}(t)=\sum _w t^{\exc_k w}
\qquad (w\in R(\bfc,\bfd)),\leqno(2.1)
$$
be the generating polynomial for the class $R(\bfc,\bfd)$
by~``$\exc_k$." We have seen in the introduction that the
generating function for those polynomials was simply
$$
\sum_{\bfc,\bfd} \bfu^\bfc \bfv^\bfd A_{\bfc,\bfd}(t)
={1\over \det (I_r-B_kU)},\leqno(2.2)
$$
where $B_k$ is the matrix defined in (1.6).

\proclaim L{\sevenrm EMMA} {2.1}. The following identity holds
$$
\displaylines{\noalign{\vskip 3pt}
(2.3)\quad
\det(I_r-B_kU)=1+\smash{\sum_{i=1}^j}
(-1)^{i} (1-t)^{i-1} e_i(u_1,\ldots, u_j)\hfill\cr
\hfill
{}-\sum_{i=1}^k t(1-t)^{i-1} e_i(v_1,\ldots, v_k),
\qquad\cr}
$$
where the $e_i$'s stand for the elementary symmetric
functions in the variables between parentheses.
\endproclaim

{\it Proof}.
First
$$\displaylines{
\det(I_r-B_kU)=1+\smash{\sum_{i=1}^r (-1)^i\!\!\!\!
\sum_{1\le l_1<\cdots < l_i\le r}}\!\!\!\!
u_{l_1}\ldots u_{l_i}
\det\bigl(b(l,l')\bigr)_{(l,l'\in \{l_1,\ldots,l_i\})},\cr
\noalign{\vskip 3pt}}
$$
by letting  $u_{j+1}=v_1$, \dots~, $u_r=v_k$. Secondly
notice that the determinant
$\det\bigl(b(l,l')\bigr)_{(l,l'\in \{l_1,\ldots,l_i\})}$ is  
zero, if $\{l_1,\ldots,l_i\}$ has a non-empty
intersection with both the intervals $[1,j]$ and $[j+1,r]$,
is equal to $(1-t)^{i-1}$, if
$1\le l_1<\cdots<l_i\le j$, and to
$t(t-1)^{i-1}$, if $j+1\le l_1<\cdots < l_i\le r$.\cqfd

\medskip
Now substitute the value (2.3) into identity (2.2), multiply
numerator  and denominator of the fraction by $(1-t)$
and make the substitution $u_i(1-t)\leftarrow u_i$ and
$v_i(1-t)\leftarrow v_i$. We get (remember that
$c=c_1+\cdots+c_j$ and $d=d_1+\cdots+d_k$, so that
$c+d=m$)
$$
\displaylines{
\noalign{\vskip-5pt }
\quad
\sum_{\bfc,\bfd} {\bfu^\bfc\bfv^\bfd\over
(1-t)^{c+d+1}} A_{\bfc,\bfd}(t)\hfill\cr
\noalign{\vskip-15pt}
\hskip 2.5cm
{}={1\over (1-t)+\sum\limits_{i=1}^j (-1)^i
e_i(u_1,\ldots,u_j) -\sum\limits_{i=1}^k t
e_i(v_1,\ldots,v_k)}\hfill\cr 
\noalign{\vskip-5pt}
\hskip 2.5cm{}={1\over (1-u_1)\ldots
(1-u_j)-t(1+v_1)\ldots (1+v_k)},\hfill\cr}
$$
and finally
$$
\sum_{\bfc,\bfd} {\bfu^\bfc\bfv^\bfd\over
(1-t)^{c+d+1}} A_{\bfc,\bfd}(t)
=\sum_{s\ge 0} t^s
{(1+v_1)^s\ldots (1+v_k)^s\over
(1-u_1)^{s+1}\ldots (1-u_j)^{s+1}}.
\leqno(2.4)
$$
Now recurrence relations for the polynomials
$ A_{\bfc,\bfd}(t)$ can be  derived, following
a classical pattern (see, e.g., [Ga79]). Let~$A$ be
the common value of the previous series. Comparing
the derivatives $D_{v_k}A$ and $D_tA$ calculated with
the right-hand side of (2.4) leads to the relation
$$
(1+v_k)D_{v_k}A=t\,D_tA.\leqno(2.5)
$$
Now with the help of the left-hand side of (2.4) the
latter identity yields 
%A_{\bfc,\bfd}(t) in formula below July 2
$$\displaylines{(2.6)\quad
(d_k+1)A_{\bfc,\bfd+1_k}(t)\hfill\cr
\hfill{}=(t(c+d+1+d_k)-d_k)A_{\bfc,\bfd}(t)
+t(1-t)A_{\bfc,\bfd}'(t),\quad\cr}
$$ 
where $\bfd+1_k$ is the sequence $(d_1,\ldots,d_k+1)$
and $A_{\bfc,\bfd}'(t)$ is the derivative of
$A_{\bfc,\bfd}(t)$. Next let
%no longer centered, July 2
$A_{\bfc,\bfd}(t)=\sum_s A_{\bfc,\bfd,s}t^s$.
Then (2.6) is equivalent to the recurrence relation
$$
(d_k+1)A_{\bfc,\bfd+1_k,s}
=(c+d+d_k+2-s)A_{\bfc,\bfd,s-1}
+(s-d_k)A_{\bfc,\bfd,s}.\leqno(2.7)
$$

%This paragraph has been modified July 2
We could as well look for a relation between
$D_{u_j}A$ and $D_tA$ and easily obtain
$$\displaylines{\rlap{(2.8)}\hfill
(1-u_j)D_{u_j}A=t\, D_tA+A,\hfill\cr
\noalign{\hbox{from which we can derive the relations:}}
(2.9)\quad
(c_j+1)A_{\bfc+1_j,\bfd}(t)\hfill\cr
\hfill{}=(t(c+d-c_j)+c_j+1)A_{\bfc,\bfd}(t)
+t(1-t)A_{\bfc,\bfd}'(t),\quad\cr
(2.10)\quad
(c_j+1)A_{\bfc+1_j,\bfd,s}\hfill
\hfill{}=(c+d+1-s-c_j)A_{\bfc,\bfd,s-1}
+(c_j+1+s)A_{\bfc,\bfd,s},\quad\cr}
$$
where $\bfc+1_j=(c_1,\ldots, c_{j-1},c_j+1)$.

The two pairs of recurrence relations (2.6), (2.9), on the one
hand, and (2.7), (2.10), on the other hand, uni\-que\-ly determine
the polynomials $A_{\bfc,\bfd}(t)$ using the initial condition
$A_{\bf 0,0}(t)=1$ (or $A_{{\bf 0,0},0}=1$ and
$A_{{\bf 0,0},s}=0$ for $s\not=0$). Actually, using the two
relations (2.5) and (2.8), we can reprove that the
left-hand side of (2.4) is precisely equal to the
right-hand side.

\proclaim P{\sevenrm ROPOSITION} {2.2}. Let
$A_{\bfc,\bfd}^{\des}(t)$ be the generating polynomial for
$R(\bfc,\bfd)$ by the number of $k$-descents ``$\des_k$." Then
$$A_{\bfc,\bfd}^{\des}(t)=A_{\bfc,\bfd}(t).$$
\endproclaim

{\it Proof}.
We already know that the coefficients of 
$A_{\bfc,\bfd}(t)$ satisfy (2.7)
and (2.10).
We only have to verify
that the same holds for the coefficients 
$A_{\bfc,\bfd,s}^{\des}$ of
$A_{\bfc,\bfd}^{\des}(t)$. But
$(d_k+1)A_{\bfc,\bfd+1_k,s}^{\des}$ is the number of
words in $R(\bfc,\bfd+1_k)$ with $s$ $k$-descents having
$d_k$ letters equal to~$r$, plus one letter, say, equal to
$\dot r$. To generate such a word, we can choose a word in
$R(\bfc,\bfd)$ having $s$ $k$-descents and insert $\dot
r$ into any one of the $(s-d_k)$ $k$-descents that
do not begin with~$r$. Exactly
$(s-d_k)A_{\bfc,\bfd,s}^{\des}$ words can be obtained
by such an insertion. 

The other possibility is to take a
word in $R(\bfc,\bfd)$ having $(s-1)$ $k$-descents and
insert $\dot r$ into each of the slots that is not a
$k$-descent (there are exactly $(c+d-(s-1))$ such
slots) and also after each letter~$r$ and at the end of
the word (there  are exactly $(d_k+1)$ such slots).
Altogether,  $(c+d+d_k+2-s)A_{\bfc,\bfd,s-1}^{\des}$
words in $R(\bfc,\bfd+1_k)$ with a single dotted
$\dot r$ can be obtained in this way. This shows
that the coefficients $A_{\bfc,\bfd,s}^{\des}$ also
satisfy~(2.8).

The same technique applies to identity~(2.10).\cqfd

\medskip
R{\sevenrm EMARK}. Let $\sigma$ (resp. $\tau$) be a permutation
of $\{1,2,\ldots,j\}$ (resp. of $\{1,\ldots, k\}$). Denote
by~$\sigma\bfc$ and by $\tau \bfd$ the sequences 
$(c_{\sigma 1},\ldots,c_{\sigma j})$ and 
$(d_{\tau 1},\ldots,d_{\tau k})$, respectively, and by
$R(\sigma\bfc,\tau\bfd)$ the class of all
the rearrangements of the word $1^{c_{\sigma  1}}\ldots
j^{c_{\sigma j}}(j+1)^{d_{\tau 1}} \ldots 
r^{d_{\tau k}}$. As formula (2.4) is symmetric in the
$u_i$'s and in the $v_i$'s, the two polynomials
$A_{\bfc,\bfd}(t)$ and $A_{\sigma\bfc,\tau\bfd}(t)$ are
identical. (The result will be proved combinatorially in
Theorem~3.1.) In the next table we have then only
displayed the values of the polynomials  
$A_{\bfc,\bfd}(t)$ when $\bfc$ and $\bfd$ are {\it
partitions}, i.e., non-increasing sequences.

\medskip

{\it A short table for the polynomials
$A_{\bfc,\bfd}(t)$}: 

\noindent
$A_{(0),(0)}(t)=~1$, 
$A_{(1),(0)}(t)=~1$,  $A_{(0),(1)}(t)=~t$, 

\noindent
$A_{(2),(0)}(t)=~1$,  $A_{(1,1),(0)}(t)=~1+t$, 
$A_{(1),(1)}(t)=~2t$,  $A_{(0),(1,1)}(t)=~t+t^2$, 
$A_{(0),(2)}(t)=~t^2$, 

\noindent
$A_{(3),(0)}(t)=~1$, 
$A_{(2,1),(0)}(t)=~1+2t$, 
$A_{(1,1,1),(0)}(t)=~1+4t+t^2$,  

\noindent
$A_{(2),(1)}(t)=~3t$,
$A_{(1,1),(1)}=~4t+2t^2$, 
$A_{(1),(1,1)}(t)=~2t+4t^2$, 

\noindent
$A_{(1),(2)}(t)=~3t^2$, 
$A_{(0),(1,1,1)}(t)=~t+4t^2+t^3$, 
$A_{(0),(2,1)}(t)=~2t^2+t^3$, 

\noindent
$A_{(0),(3)}(t)=~t^3$.

\vfill\eject
\centerline{3. I{\sevenrm NVARIANCE} P{\sevenrm RINCIPLES}}

\medskip
Let $D$ be a total ordering on $[\,r\,]$.  We  say that $D$ is {\it
compatible} with $k$ if, for all $x$ large and $y$ small, we
have $x>_Dy$. 
Again let $w=x_1x_2\ldots x_m \in X^*$ and $\overline
w=v=y_1y_2\ldots  y_m$ be its non-decreasing
rearrangement. We say that  $w$ has a $k$-{\it excedance
at}~$i$ $(1\le i\le m)$, if either $x_i>y_i$, or $x_i=y_i$ 
and $x_i$ is large.
We also say that $w$ has a $k$-{\it   
descent at}~$i$ $(1\le i\le m)$, if either
$x_i>x_{i+1}$, or $x_i=x_{i+1}$ and $x_i$ is large. (By
convention, $x_{m+1}=\star$.)
Note that there is a descent at~$m$ if $x_m$ is large.

The number of $k$-excedances and $k$-descents of a word
$w$ will be denoted by $\exc_k w$ and $\des_k w$,
respectively.  We will sometimes use the notations $\exc_{k,D}$ and 
$\des_{k,D}$ if we need to draw attention to the ordering $D$.

For example, if $X=[\,3\,]$, $D$ is the standard ordering and
$w$ is the word $w=3,2,2,1,1,2$  then $\des_0 w=2=\des_1 w$,
$\des_2 w=4$, $\des_3 w=5$.  As  $\overline w=1,1,2,2,2,3$,
$\exc_0 w=\exc_1 w=2$, $\exc_2 w=\exc_3 w=3$.

\proclaim T{\sevenrm HEOREM} {3.1}. Let $D$ and $E$ be total
orderings of $[\,r\,]$ compatible with $k$.  Then there  is a
bijection $\chi$ of $R({\bf c},{\bf d})$ onto itself such that for
all  $w\in R({\bf c},{\bf d})$,  
$$\des_D w=\des_E \chi(w).$$
\endproclaim

\proclaim T{\sevenrm HEOREM} {3.2}. Let $D$ and $E$ be total
orderings of $[\,r\,]$, not necessarily compatible with~$k$.
Then there is a bijection  $\theta$ of $R({\bf c},{\bf d})$ onto
itself such that for all $w\in R({\bf c},{\bf d})$, 
$$\exc_D w=\exc_E \theta(w).$$
\endproclaim

Note that Theorem 3.1 is not true
without the assumption of compatibility.  For example, let
$r=2$, $k=1$ and consider $R((1),(1))$, the rearrangement class
of $v=1,2$. Note that 1 is  small and 2 is large.
Let $2>_D 1$, $1>_E 2$. Then $D$ is compatible with $k$, but
$E$ is not. Now
$$
\displaylines{\des_D 1,2=\des_D 2,1=\exc_D 1,2=\exc_D 2,1=1,\cr
\noalign{\hbox{but}}
\des_E 1,2=2,\quad \des_E 2,1=0,\quad \exc_E 1,2=\exc_E 2,1=1.
\cr}
$$

{\it Proof of Theorem $3.1$}.
Suppose
first that  $a$, $b$ are letters in $[\,r\,]$ such that $a>_D b$ and
that there is no letter $x$ in $X$ such that $a>_D x>_D b$
(i.e., $a$  {\it covers} $b$.)  We assume that $E$ is obtained
from $D$ by reversing the order of $a$ and $b$.  (We may say
that $E$ is obtained from $D$ by a  {\it transposition}.)  Since
both $D$ and $E$ are compatible with $k$, either both $a$ and
$b$ are large or both are small.

Given a word $w\in R({\bf c},{\bf d})$, write $w=u_1v_1\ldots u_mv_m$, 
where each $u_i$ contains only the letters $a$ and $b$, and
each $v_i$ does not contain any $a$ or $b$.  Let $u_i'$ be the
word obtained from $u_i$ by reversing the order of its
letters.  Accordingly, if $u_i=z_1z_2\ldots z_s$, then
$u_i'=z_s\ldots z_2z_1$.  Put $w'=u_1'v_1\ldots u_r'v_r$. 
Since  $[b,a](w')=[a,b](w)$, $[a,a](w')=[a,a](w)$ and
$[b,b](w')=[b,b](w)$, while  for any letters $x$, $y$ other than $a$
and $b$,  $[a,x](w')+[b,x](w')=[a,x](w)+[b,x](w)$ and 
$[x,a](w')+[x,b](w')=[x,a](w)+[x,b](w)$ and also
$[x,y](w')=[x,y](w)$, we see that 
$$\des_D w=\des_E w'.$$
Hence we may define $\chi(w)=w'$. It is clear that $\chi$ is a
bijection, as one may easily write down its inverse.

In the general case, if $D$ and $E$ are any orderings on $X$ 
that are compatible with $k$, one can obtain $E$ from $D$ by a
sequence of  transpositions.  This completes the proof of
Theorem~3.1.

\medskip
Before proving Theorem 3.2, we introduce some more notation. 
If $w$ and $v$ are words, the two-rowed matrix
$\left(\displaystyle{v \atop w}\right)$ is called a {\it
biword}.  It is a {\it circuit} if $v$ is a rearrangement of 
$w$.  When calculating excedances, it is often convenient to
consider the  circuit 
$\tilde w=\left(\displaystyle{v \atop w}\right)$, 
where $v$ is the  non-decreasing rearrangement of
$w$.  A {\it cycle} is a circuit 
$\left(\displaystyle{\delta w \atop w}\right)$ such that
$\delta w$  is the right to left cyclic shift of $w$, i.e., 
$w=x_1\ldots x_n$ and $\delta w=x_2\ldots x_nx_1$.  We
will write this cycle as $[x_1,x_2,\ldots,x_n]$.   A {\it true
cycle} is a cycle  $\left(\displaystyle{\delta w\atop w}\right)$
in which no letter of $w$ is repeated.

Multiplication of biwords $\left(\displaystyle{v\atop w}\right)$
is defined to be juxtaposition.  We assume that
the biwords $\left(\displaystyle{v\atop w}\right)$ and
$\left(\displaystyle{v'\atop w'}\right)$ commute if $v$ and $v'$ 
have no letters in common.  With these definitions, 
it was shown in [CaFo69] that every circuit can be written as a
product of true cycles, and that the  factorization is unique
except for the order of the factors.  More precisely (see
[CaFo69, chapter 4, proposition 4.1]), if a circuit factorizes
into two different true cycle products, say
$\alpha_1\alpha_2\ldots\alpha_s$ and
$\beta_1\beta_2\ldots\beta_t$, then $s=t$ and we can go from
the first product to the second one by finitely many steps
consisting of permuting in a product two consecutive true
cycles having no letters in common.   Furthermore, there is an
algorithm that transforms each circuit into a  product of true
cycles.  Note of course that there may be more than one way of
writing the same cycle.  For example, the cycles
$[1,2,3]=\left(\matrix{2\ 3\ 1\cr1\ 2\ 3\cr}\right)$ and
$[2,3,1]=\left(\matrix{3\ 1\ 2\cr2\ 3\ 1\cr}\right)$ are the
same.

As an example of factorization, let $w=3,1,1,4,3,2,3,2,5,4,2,3,2,2$.
Then
$$\eqalign{
\tilde w =\left({\overline w\atop w}\right)
&=\left(\matrix{1\ 1\ 2\ 2\ 2\ 2\ 2\ 3\ 3\ 3\ 3\ 4\ 4\ 5\cr
                3\ 1\ 1\ 4\ 3\ 2\ 3\ 2\ 5\ 4\ 2\ 3\ 2\ 2\cr}\right)\cr
&=\left(\matrix{1\ 2\ 3\cr3\ 1\ 2\cr}\right|
\matrix{1\cr1\cr}\left|\matrix{2\ 5\ 3\ 4\cr4\ 2\ 5\ 3\cr}\right|
\matrix{3\ 2\ 4\cr4\ 3\ 2\cr}\left|\matrix{2\cr2\cr}\right|
\left.\matrix{2\ 3\cr3\ 2\cr}\right)\cr
&=[3,1,2][1][4,2,5,3][4,3,2][2][3,2],\cr}
$$ 
which is a product of true cycles.  
(The algorithm is explained in detail in [CaFo69].)

\medskip
\goodbreak
{\it Proof of Theorem $3.2$}.
As in the proof of Theorem~3.1, we may assume that  $a$, $b$ 
are letters in~$[\,r\,]$ such that $a>_D b$ and $a$ covers $b$. 
We assume that $E$ is obtained from $D$ by reversing the order
of $a$ and $b$.  Note that in this case  neither $D$ nor $E$ are
assumed to be compatible with $k$, so we do not  assume that
$a$ and $b$ are both large or both small.

Let $w$ be a word in $C(v)$.  Factorize the circuit
$\tilde w $ into true  cycles:  
$$\tilde w =\alpha_1\alpha_2\ldots\alpha_m.$$ 
Consider the cycle $\alpha_i$.  If the letters $a$ and $b$ do
not both occur  in this cycle then put $\alpha_i'=\alpha_i$. 
If the letters $a$ and $b$ do both occur in $\alpha_i$ then let
$\alpha_i'$ be the cycle obtained from  $\alpha_i$ by
interchanging $a$ and $b$.  Let $\tilde w '$ be the product of 
the cycles $\alpha_i'$.  Finally, reorder the columns of
$\tilde w '$ (remembering that columns
$\left(\displaystyle{x\atop y}\right)$ and
$\left(\displaystyle{x'\atop y'}\right)$ commute if $x\ne x'$)
to get the circuit $\left(\displaystyle{v'\atop w'}\right)$,
where $v'$ is the  non-decreasing rearrangement of $w'$ (in
the ordering $E$). Then define $\theta(w)=w'$.

The following relations hold :
$$
\displaylines{\left[{b\atop a}\right](w')
=\left[{a\atop b}\right](w),\quad 
\left[{a\atop a}\right](w')
=\left[{a\atop a}\right](w),\quad 
\left[{b\atop b}\right](w')
=\left[{b\atop b}\right](w);\cr
\noalign{\hbox{furthermore, for any letters $x$ and $y$
other than $a$ and $b$, we have}}
\left[{a\atop x}\right](w')+
\left[{b\atop x}\right](w')= 
\left[{a\atop x}\right](w)
+\left[{b\atop x}\right](w),\cr 
\left[{x\atop a}\right](w')
+\left[{x\atop b}\right](w')
=\left[{x\atop a}\right](w)
+\left[{x\atop b}\right](w)\cr
\noalign{\hbox{and}}
\left[{x\atop y}\right](w')
=\left[{x\atop y}\right](w).\cr}
$$  
It follows that 
$\exc_D w=\exc_E w'$.\qed

\medskip
For example, let $w=3,1,2,1,3,3,3,2,2,4,5,2,2,4$.  Then as before
$$\tilde w =\left({\overline w\atop w}\right)
                 =[3,1,2][1][4,2,5,3][4,3,2][2][3,2].
$$
Let $a=2$, $b=3$. Then 
$$\eqalign{
\tilde w '=[2,1,3][1][4,3,5,2][4,2,3][2][2,3]%\cr
&=\left(\matrix{1\ 3\ 2\ 1\ 3\ 5\ 2\ 4\ 2\ 3\ 4\ 2\ 3\ 2\cr
                2\ 1\ 3\ 1\ 4\ 3\ 5\ 2\ 4\ 2\ 3\ 2\ 2\ 3\cr}\right)\cr
&=\left(\matrix{1\ 1\ 3\ 3\ 3\ 3\ 2\ 2\ 2\ 2\ 2\ 4\ 4\ 5\cr
                2\ 1\ 1\ 4\ 2\ 2\ 3\ 5\ 4\ 2\ 3\ 2\ 3\ 3\cr}\right),\cr}
$$
so $w'=2,1,1,4,2,2,3,5,4,2,3,2,3,3$.

\goodbreak
\bigskip
\centerline{4. T{\sevenrm HE} F{\sevenrm IRST} F{\sevenrm
ONDAMENTAL} T{\sevenrm RANSFORMATION}}

\medskip
As in [Lo83, chap.~10] the construction of $\Phi$
may be described as follows.

\medskip
(a) Start with a word $w=x_1x_2\ldots x_m\in C(v)$ and
form its {\it  left to   right dominated factorization}
$w=w_1w_2\ldots w_p$. The factors $w_1$, $w_2$, 
\dots~, $w_p$ of that factorization are {\it dominated}, in
the sense that  each $w_i$ starts with its {\it maximum}
letter, say~$a_i$, and no other letter is equal to~$a_i$
in the factor. Furthermore, when reading those first letters
from left to right, they form a {\it non-decreasing}
sequence:
$a_1\le a_2\le \cdots \le a_p$.

For instance, the left to right dominated factorization of
the following word is indicated by vertical bars:
$$
w=\sep 3,1,1,1\sep 5\sep 5\sep 5,2,3,3,2,1,4\sep 6\sep
6,1,3\sep 
$$
Notice that the first letters are increasing:
$3\le 5\le5\le5\le 6\le 6$.

\medskip
(b) The next step consists of forming a second word
$\Delta w=\delta w_1\, \ldots\, \delta w_p$,
where each $\delta w_i$ is the right to  left cyclic shift
of~$w_i$, as defined in the previous section. By means of
the words $\Delta  w$ and~$w$ we set up the biword
$\left(\displaystyle{\Delta w \atop w}\right)$.  With our
example 
$$
\left({\Delta w\atop w}\right)
=\left(\matrix{1\ 1\ 1\ 3\cr
3\ 1\ 1\ 1\cr}\right|
\matrix{5\cr 5\cr}
\left|\matrix{5\cr 5\cr}\right|
\matrix{2\ 3\ 3\ 2\ 1\ 4\ 5\cr
5\ 2\ 3\ 3\ 2\ 1\ 4\cr}
\left|\matrix{6\cr 6\cr}\right|
\left.\matrix{1\ 3\ 6\cr
6\ 1\ 3\cr}\right)
$$

(c) In the following stage the two-row columns of
$\left(\displaystyle{\Delta w \atop w}\right)$   are
rearranged in such a way that the top row is
non-decreasing. When making the rearrangement we adopt
the previous commutation rules:
$$
\pmatrix{a\cr b\cr}\pmatrix{c\cr d\cr}
=\pmatrix{c\cr  d\cr}\pmatrix{a\cr b\cr},
\qquad{\rm iff}\quad a\not=c.\leqno(4.1)
$$
In particular, two two-row  columns  with identical top
entries cannot commute. Again working  with the  same
example leads to the biword:
$$
\pmatrix{\ldots\cr \Phi(w)\cr}\!\!=\!\!
\pmatrix{1&1&1&1&1&2&2&3&3&3&3&4&5&5&5&6&6\cr
\bf{3}&1&1&\bf{2}&\bf{6}&\bf{5}&\bf{3}&1&2&3&1&1&5&
5&4&6&3\cr}
$$

(e) By definition the bottom word of this last two-row
matrix is the transformed word $\Phi(w)$. Its   excedances
have been printed in bold-face and they  correspond, in a 
one-to-one manner, with the descents of~$w$ that  are:
31, 52, 32, 21, 61.

\goodbreak
\bigskip
\centerline{5. T{\sevenrm HE} C{\sevenrm ONSTRUCTION OF}
$\Phi_k$}

\medskip
First, assume that the
total ordering on $[\,r\,]$ is the natural ordering. We then
construct a {\it bijection} $\Phi_k$ of each rearrangement class 
$R(\bfc,\bfd)$ onto itself such that for all $w\in R(\bfc,\bfd)$, 
$$
\des_k w=\exc_k \Phi_k(w).\leqno(5.1) 
$$
When $k=0$, it suffices to take
$\Phi_k=\Phi$ (the first fundamental transformation), since
$\des_k=\des$ and $\exc_k=\exc$ in such a  case. 
Suppose that $1\le k\le r$  and  consider
a word  $w=x_1x_2\ldots x_m\in C(v)=R({\bf c}, {\bf d})$.
The construction of $\Phi_k(w)$ is made in several steps
(the reader is advised to follow the successive steps with the
help of the example given just after this present description) :

\medskip
(a) Add $\star$ at the end of $w$.

\medskip
(b) Consider the left to right dominated factorization
of $w\star$ and for a reason that will be evident hereafter
denote it by
$$\displaylines{\quad
w\star=\sep a_1u_1\sep \ldots \sep a_pu_p\sep
b_{1}v_{1,1}\sep b_1v_{1,2}\sep
\ldots \sep b_{1}v_{1,m_1}\sep\hfill\cr
\hfill\ldots
\sep b_{q}v_{q,1}\sep b_{q}v_{q,2}\sep 
\ldots \sep b_{q}v_{q,m_q}\sep,\quad\cr}
$$
where the $a$'s and $b$'s are letters, the $u$'s and $v$'s
words, such that $1\le a_1\le\cdots\le a_p\le j$,
$j+1\le b_{1}<\cdots <b_q=r$ and where all letters in
$u_i$ (resp. $v_{i,l}$)  are {\it less} than $a_i$ (resp.
$b_{i}$).

\medskip
(c) Next form the word
$$\displaylines{\quad
w'=\sep a_1u_1\sep \ldots \sep a_pu_p
\sep b_{1}v_{1,m_1}\sep \ldots \sep b_1 v_{1,2}\sep
b_{1}v_{1,1}\sep\hfill\cr
\hfill \ldots
\sep b_{q}v_{q,m_q}\sep \ldots \sep b_q v_{q,2}
\sep b_{q}v_{q,1}\sep.\quad\cr}
$$
Notice the difference between $w$ and $w'$: we have only
changed the orders of the factors beginning with the same
large letter.

\medskip
(d) Then form the biword
$$\displaylines{\quad
\left({\Delta w'\atop w'}\right)
=\left(\matrix{u_1a_1\cr
a_1u_1\cr}\right|
\matrix{\ldots\cr \ldots\cr}
\left|\matrix{u_pa_p\cr a_pu_p\cr}\right|
\matrix{v_{1,m_1}b_{1}\cr
b_{1}v_{1,m_1}\cr}
\left|\matrix{\ldots\cr \ldots\cr}\right|
\left.\matrix{v_{1,2}b_{1}\cr b_{1}v_{1,2}\cr}\right|
\left.\matrix{v_{1,1}b_{1}\cr b_{1}v_{1,1}\cr}
\right|\hfill\cr
\hfill
\left.\matrix{\ldots\cr \ldots\cr}\right|
\matrix{v_{q,m_q}b_{q}\cr
b_{q}v_{q,m_q}\cr}
\left|\matrix{\ldots\cr \ldots\cr}\right|
\left.\matrix{v_{q,2}b_{q}\cr
b_{q}v_{q,2}\cr}\right|
\left.\matrix{v_{q,1}b_{q}\cr
b_{q}v_{q,1}\cr}\right)\quad\cr}
$$

(e) Rearrange the columns of the latter biword in  such a
way that the top row is non-decreasing,  still using the
previous  commutation rules~(4.1). Thereby we obtain
$\Phi(w')$:
$$
\pmatrix{\dots\cr \Phi(w')\cr}=
\pmatrix{1^{c_1}&\ldots&j^{c_j}&\star&(j+1)^{d_1}&
\ldots&r^{d_k}\cr
w_1&\ldots&w_j&w_\star &z_1&\ldots&z_k\cr},
$$
where $w_1$, \dots\ , $w_j$, $w_\star $, $z_1$, \dots~, $z_k$
are words of lengths  $c_1$, \dots~, $c_j$, 1, $d_1$,
\dots~, $d_k$, respectively. Note that $w_\star$ is equal to
the last letter of~$w$.

\medskip
(f) Now reverse  (i.e., take the  mirror-image of) each of the
words $z_1$, \dots~, $z_k$ to obtain 
$\widetilde z_1$, \dots~, $\widetilde z_k$ within the biword
$$
\pmatrix{\dots\cr w'' \cr}=
\pmatrix{1^{c_1}&\ldots&j^{c_j}&\star&(j+1)^{d_1}&
\ldots&r^{d_k}\cr
w_1&\ldots&w_j&w_\star &\widetilde z_1&\ldots&
\widetilde z_k\cr};
$$

(g) By construction, $\star $ is the last letter of
$v_{q,m_q}$,  then becomes the first letter of~$z_k$, and,
finally, appears as the last letter of~$\widetilde z_k$
and therefore of~$w''$.
Write $\widetilde z_k=\widetilde y_k\star $.
We can then drop the last letter of the bottom word~$w''$ of the
previous biword  and obtain a word of the class
$R({\bf c}, {\bf d})$, which is, by definition, the word
$\Phi_k(w)$. Thus $\Phi_k(w)\star=w''$, so that
$$
\pmatrix{\dots\cr \Phi_k(w)\cr}=
\pmatrix{1^{c_1}&\ldots&j^{c_j}&(j+1)^{d_1}\ 
\ldots \quad r^{d_k}\cr
w_1&\ldots&w_j&\quad w_\star  \widetilde z_1\quad
\ldots\quad \widetilde y_k\cr}.
$$

Note that $w_\star  \widetilde  z_{1}$ is of length
$(d_1+1)$ and $\widetilde  y_k$ is of length $(d_k-1)$.
Accordingly, the bottom word has the required length.

\medskip

For example, suppose $j=2$, $k=4$, $r=6$ and let $w$ be the
word 
$$
w= 2, 1, 1, 3, 1, 3, 3, 5, 5, 2, 3, 3, 2, 1, 4, 5, 4, 6, 6, 1, 3.
$$

The steps  (a) -- (g)  for $w$ are the following:
$$\leqalignno{ 
w{\star }
=& 2, 1, 1, 3, 1, 3, 3, 5, 5, 2, 3, 3, 2, 1, 4, 5, 4, 6, 6, 1, 3,{\star };
&{\rm (a)}\cr
w{\star }
=&\sep 2,1,1\sep 3,1\sep 3\sep 3\sep 5\sep
5,2,3,3,2,1,4\sep 5,4\sep 6\sep 6,1,3,{\star }\sep; 
&{\rm (b)}\cr
w'=&\sep 2,1,1\sep 3\sep 3\sep 3,1\sep 5,4\sep 5,2,3,3,2,1,4
\sep 5\sep 6,1,3,{\star }\sep 6\sep;
&{\rm (c)}\cr
\left(\displaystyle{\Delta w'\atop w'}\right)
=&\left(\matrix{1\ 1\ 2\cr
2\ 1\ 1\cr}\right|
\matrix{3\cr 3\cr}
\left|\matrix{3\cr 3\cr}\right|
\matrix{1\ 3\cr 3\ 1\cr}
\left|\matrix{4\ 5\cr 5\ 4\cr}\right.\kern-3pt
\left|\matrix{2\ 3\ 3\ 2\ 1\ 4\ 5\cr
5\ 2\ 3\ 3\ 2\ 1\ 4\cr}\right|
\matrix{5\cr 5\cr}
\left|\matrix{1\ 3\ {\star }\ 6\cr
6\ 1\ 3\ {\star }\cr}\right|\kern-3pt
\left.\matrix{6\cr 6\cr}\right);
&{\rm (d)}\cr
\pmatrix{\dots\cr\Phi(w')\cr}=
&\left(\matrix{1\ 1\ 1\ 1\ 1\cr
2\ 1\ 3\ 2\ 6\cr}\right|
\left.\matrix{2\ 2\ 2\cr 1\ 5\ 3\cr}\right|
\matrix{\star\cr
3\cr}
\left|\matrix{3\ 3\ 3\ 3\ 3\ 3\cr
3\ 3\ 1\ 2\ 3\ 1\cr}\right|\kern-3pt
\left.\matrix{4\ 4\cr 5\ 1\cr}\right|
\matrix{5\ 5\ 5\cr 4\ 4\ 5\cr}
\left|\matrix{6\ 6\cr
{\star }\ 6\cr}\right);
&{\rm (e)}\cr
\pmatrix{\dots\cr  w''\cr}=
&\left(\matrix{1\ 1\ 1\ 1\ 1\cr
2\ 1\ 3\ 2\ 6\cr}\right|
\left.\matrix{2\ 2\ 2\cr 1\ 5\ 3\cr}\right|
\matrix{\star\cr
3\cr}
\left|\matrix{3\ 3\ 3\ 3\ 3\ 3\cr
1\ 3\ 2\ 1\ 3\ 3\cr}\right|\kern-3pt
\left.\matrix{4\ 4\cr 1\ 5\cr}\right|
\matrix{5\ 5\ 5\cr 5\ 4\ 4\cr}
\left|\matrix{6\ 6\cr
6\ {\star }\cr}\right);
&{\rm (f)}\cr
\pmatrix{\dots\cr  \Phi_4(w)\cr}=
&\left(\matrix{1\ 1\ 1\ 1\ 1\ 2\ 2\ 2\ 
3\ 3\ 3\ 3\ 3\ 3\ 4\ 4\ 5\ 5\ 5\ 6\ 6\cr
2\ 1\ 3\ 2\ 6\ 1\ 5\ 3\ 
3\ 1\ 3\ 2\ 1\ 3\ 3\ 1\ 5\ 5\ 4\ 4\ 6\cr}\right).
&{\rm (g)}\cr}
$$

Let us verify that  $\Phi_k$ is a {\it bijection} of
$R({\bf c},{\bf d})$ onto itself. First, steps~(a)
and~(b) make up a bijection of the latter set onto
$R({\bf c},{\bf d}){\star }$. Next, step~(c) maps
this new  set onto the  set, say $R'$, of all the
rearrangements of $1^{c_1}\ldots j^{c_j}{\star }
(j+1)^{d_1}\ldots r^{d_k}$ whose first  factor
(when read from left to right) in its left to
right dominated factorization beginning with~$r$
ends with~$\star $. This step  makes up a true
bijection, since the forementioned factorization
is unique.

Next steps (d) and (e) are nothing but the definition of the
bijection~$\Phi$. Therefore, $\Phi$ maps $R'$, in  a one-to-one
manner, onto the set, say $R^{\hbox{\sevenrm (e)}}$, of
 rearrangements  $w^{\hbox{\sevenrm (e)}}$ such that the
$d_k$-th letter of  $w^{\hbox{\sevenrm (e)}}$, when read {\it
from right to left} is~$\star $. Clearly, step~(f) is a bijection
of $R^{\hbox{\sevenrm (e)}}$ onto $R({\bf c},{\bf d}){\star }$ 
and step~(g) is straightforward. 

Thus  $\Phi_k$ is a well-defined bijection. All
the steps are reversible and rather simple to
describe with the exception of the reverse of
step~(e). However this step is simply the inverse
of the first fundamental transformation, a
description of which may be found in [Lo83,
p.~199].

\medskip
It remains to verify the  property:
$\des_k w=\exc_k \Phi_k(w)$. To achieve this goal introduce
the following notations. For each word~$w$ and each large
letter~$b$ let $\rfa_b(w)=1$, if the single letter word~$b$
occurs as a factor in the left to right factorization of~$w$
and is {\it the rightmost} factor starting with~$b$. Otherwise,
let $\rfa_b(w)=0$. For instance, with the notations of
step~(b), $\rfa_{b_i}(w\star)=1$, if and only if $v_{i,m_i}$ is
empty $(1\le i\le q)$. Also with our previous example we have
$\rfa_3(w\star)=1$,
$\rfa_4(w\star)= \rfa_5(w\star)=\rfa_6(w\star)=0$.

When a word is written as a biword $u\choose v$, 
with a {\it non-decreasing} top row~$u$ (as in steps (e), (f),
(g)), let  $\rfa_b{u\choose v}=1$, if the rightmost biletter
$x\choose y$ such that $x=b$ is equal to $b\choose b$.
Otherwise, let $\rfa_b{u\choose v}=0$. For instance, 
$\rfa_{j+i}{\ldots\choose w''}=1$ (in step~(f)), if
and only if the last letter of the word~$\widetilde z_i$ is equal
to~$(j+i)$ $(1\le i\le k)$. Also with our previous example we
have
$\rfa_{3}{\ldots\choose w''}=1$,
$\rfa_{4}{\ldots\choose w''}
=\rfa_{5}{\ldots\choose w''}
=\rfa_{6}{\ldots\choose w''}=0$.

\medskip
Let us examine step by step how the $k$-descents in $w$ are
mapped onto the $k$-excedences in $\Phi_k(w)$. To stress the
fact that the statistic ``$\exc_k w$" depends on the ``vertical"
pairs $x\choose y$ we will also write
$\exc_k{\ldots\choose w}$. We also make use of the notation
introduced just before~(1.5).

\medskip
(a) $\rightarrow$ (b) :
first, note that the $k$-descents of $w$ are the $k$-descents
of $w\star $, as $\star$ cannot create any $k$-descent at the
end. Therefore
$$
\des_k w=\des_k (w\star). 
$$

(b) $\rightarrow$ (d) :
when $x>y$ all the $k$-descents of the form $xy$ in $w\star$
(or in~$w'$) occur {\it inside} the factors of the left to right
dominated factorization. Therefore
$$
{y\brack x}{\Delta w'\choose w'}=[x,y](w\star)
\qquad ({\rm whenever}\ x>y).
$$
On the other hand, the number of biletters $b\choose b$ occurring
in $\Delta w'\choose w'$ is equal to one plus the number of
factors $bb$ in $w\star$, if the rightmost factor of $w\star$
starting with~$b$ is the single letter word~$b$. Otherwise, the
former numbers are equal. Thus
$$
\displaylines{
{b\brack b}{\Delta w'\choose w'}
=[b,b](w\star)+\rfa_b(w\star)\qquad(b\ {\rm large}).\cr
\noalign{\hbox{Therefore}}
\exc_k{\Delta w'\choose w'}=\des_k (w \star)
+\sum_{b\ \hbox{\sevenrm large}} \rfa_b(w\star).\cr}
$$

(d) $\rightarrow$ (f) :
as the biwords
$ {\dots \choose \Phi(w')}$
and ${\dots\choose w''}$ in
steps~(e) and~(f) are derived from
$\Delta w'\choose w'$ by permuting the columns of the
biwords, we have :
$$\leqalignno{
\exc_k{\ldots \choose w''}&=\exc_k{\Delta w'\choose w'},\cr
\noalign{\hbox{and therefore}}
\exc_k{\ldots \choose w''}&=\des_k (w \star)
+\sum_{b\ \hbox{\sevenrm large}} \rfa_b(w\star).
&(5.2)\cr}
$$

(f) $\rightarrow$ (g) :
first, we have the relations 
$$
\rfa_b{\ldots\choose w''}
=\rfa_b(w\star)
\qquad(b\ {\rm large}),\leqno(5.3)
$$
because if the rightmost factor of $w\star$
starting with~$b$ is a single letter word, the {\it leftmost}
factor starting with~$b$ in~$w'$ is~$b$. Hence the {\it leftmost}
biletter $x\choose y$ in $\Delta w'\choose w'$ such that $x=b$
is $b\choose b$ (step~(d)). It is also true in $\ldots \choose
\Phi(w')$ (step~(e)), when the commutation rules~(4.1) are
applied. Therefore $\rfa_b{\ldots\choose w''}=1$
(step~(f)). In the same manner
$\rfa_b{\ldots\choose w''}=0$, if
$\rfa_b(w\star)=0$.

It remains to examine the effect of the (g)-shift on the biword
$\ldots\choose w''$. If $y$ is small and different from~$\star$,
each column  of the form $y\choose x$ remains alike in step~(g)
(no shift in the first $(c_1+\cdots+c_j)$ columns), so that
all the $k$-excedences in those columns are preserved.

Next the column $\star \choose w_\star$ in ${\dots \choose w''}$
is mapped onto the column ${j+1\choose w_\star}$ in 
${\dots \choose \Phi_k(w)}$. Hence that column provides a
$k$-excedence, iff $\star\choose w_\star$ was one.

Finally, when the shift is made on the rightmost
$(d_1+\cdots+d_k)$ columns, all the $k$-excedences are
preserved, except those of the form $b\choose b$ followed by a
column of the form $(b+1)\choose x$. The column $b\choose b$
is transformed into $(b+1)\choose b$ and the $k$-excedence is
killed by the shift. By definition of ``$\rfa_b$" the number of
those columns is exactly $\sum\rfa_b{\ldots\choose w''}$ 
$(b\ {\rm large})$. Therefore  
$$
\exc_k{\ldots\choose \Phi_k(w)} 
=\exc_k{\ldots\choose w''}-\sum_{b\ {\rm large}}
\rfa_b{\ldots\choose w''}.\leqno(5.4)
$$
From (5.2), (5.3) and (5.4) we then conclude that
$$
\exc_k {\ldots\choose \Phi_k(w)} =\des_k(w\star)
=\des_k w.\qed
$$

Let $D$ be a total ordering of $[\,r\,]$ {\it compatible
with}~$k$. By means of the present transformation $\Phi_k$ and
the bijections derived in Theorems~3.1 and~3.2 we can set up a
bijection of $R(\bfc,\bfd)$ that maps the statistic ``$\des_D$"
onto ``$\exc_D$."  Thus the following theorem is proved.

\proclaim T{\sevenrm HEOREM} {5.1}. Let $D$ be a total ordering
of $[\,r\,]$ compatible with~$k$. Then there is a bijection
$\Phi_k$ of $R({\bf c}, {\bf d})$ onto itself such that for
all  $w \in R({\bf c}, {\bf d})$,
$$
\des_D w=\exc_D \Phi_k(w).
$$
\endproclaim


R{\sevenrm EMARK}. By examining the forementioned
argument in detail we see that the
transformation~$\Phi_k$ satisfies the identity
$$
{y\brack x}{\ldots \choose \Phi_k(w)}=[x,y](w\star)
\qquad(x>y,\ y\ {\rm small}),\leqno(5.5)
$$
and also the following property : 

{\it If the last letter $w_\star$ of $w$ is small, then for every
large letter~$x$ :
$$\leqalignno{
\sum_y {y\brack x} {\ldots\choose \Phi_k(w)}
&=\sum_y [x,y](w)\qquad(y\ {\it large}\le x).&(5.6)\cr}
$$
If $w_\star$ is large, identity $(5.7)$ always holds for every
large letter~$x$ different from~$w_\star$. When $x=w_\star$,
$(5.7)$ must be replaced by :
$$\leqalignno{
1+\sum_y {y\brack x} {\ldots\choose \Phi_k(w)}
&=\sum_y [x,y](w)\qquad(y\ {\it large}\le x).&(5.7)\cr}
$$
}

Let us illustrate the latest result by means of the example
already used in this section. Define the matrix
$D_k(w)$ as the $r\times r$-matrix whose $(y,x)$-entry 
($y$ row index and $x$ column index) is the
number $[x,y](w)$, except for the $(y=j+1,x=w_\star)$-entry
that is equal to $1+[x,y](w)$. Also define $E_k(w)$ to be the
$r\times r$-matrix whose $(y,x)$-entry ($y$ row index and $x$
column index) is the number ${y\brack x}(w)$. 


Then (5.5) says that the entries in the cells $(y,x)$ with
$1\le y\le j$ and $y<x$ in the matrices 
$D_k(w)$ and $E_k(\Phi_k(w))$ coincide (i.e., the
entries in the shape $\vcenter{\box\boiteun}$~). Identities
(5.6) and (5.7)  say that only the {\it column sums} in the areas
$(j+1\le y\le x)$ of the two matrices $D_k(w)$ and 
$E_k(\Phi_k(w))$ coincide (i.e., the entries in the shape
$\vcenter{\box\boitedeux}$~).

The two matrices $D_4(w)$ and $E_4(\Phi(w))$ resulting from 
the previous example are shown below.

\vskip-.5cm
\centerline{\vbox{
\offinterlineskip
%\Grille
\segment(6,-6)\dir(1,-1)\long{4}
\centerput(12,-9){$x$}
\centerput(8,-12){$y$}
\segment(10,-10)\dir(1,0)\long{30}
\segment(10,-10)\dir(0,-1)\long{27}
\segment(10,-37)\dir(1,0)\long{30}
\segment(14,-10)\dir(0,-1)\long{5}
\segment(14,-15)\dir(1,0)\long{5}
\segment(19,-15)\dir(0,-1)\long{9}
\segment(19,-20)\dir(1,0)\long{21}
\segment(19,-24)\dir(1,0)\long{5}
\segment(24,-24)\dir(0,-1)\long{4}
\segment(24,-28)\dir(1,0)\long{5}
\segment(29,-28)\dir(0,-1)\long{4}
\segment(29,-32)\dir(1,0)\long{5}
\segment(34,-32)\dir(0,-1)\long{5}
%\segment(34,-37)\dir(1,0)\long{5}
\segment(40,-10)\dir(0,-1)\long{27}
\centerput(2,-27){$D_4(w)={}$}
\leftput(10,-27){$\matrix{1&2&1&0&0&1\cr
0&0&1&0&1&0\cr
3&1&3&0&0&0\cr
1&0&0&0&1&0\cr
0&0&1&1&1&0\cr
0&0&0&1&0&1\cr
&&3&0&2&1\cr
}$}
}\kern 6cm\vbox{
\offinterlineskip
%\Grille
\segment(6,-6)\dir(1,-1)\long{4}
\centerput(12,-9){$x$}
\centerput(8,-12){$y$}
\segment(10,-10)\dir(1,0)\long{30}
\segment(10,-10)\dir(0,-1)\long{27}
\segment(10,-37)\dir(1,0)\long{30}
\segment(14,-10)\dir(0,-1)\long{5}
\segment(14,-15)\dir(1,0)\long{5}
\segment(19,-15)\dir(0,-1)\long{9}
\segment(19,-20)\dir(1,0)\long{21}
\segment(19,-24)\dir(1,0)\long{5}
\segment(24,-24)\dir(0,-1)\long{4}
\segment(24,-28)\dir(1,0)\long{5}
\segment(29,-28)\dir(0,-1)\long{4}
\segment(29,-32)\dir(1,0)\long{5}
\segment(34,-32)\dir(0,-1)\long{5}
%\segment(34,-37)\dir(1,0)\long{5}
\segment(40,-10)\dir(0,-1)\long{27}
\centerput(-2,-27){$E_4\bigl(\Phi_4(w)\bigr)={}$}
\leftput(10,-27){$\matrix{1&2&1&0&0&1\cr
1&0&1&0&1&0\cr
2&1&3&0&0&0\cr
1&0&1&0&0&0\cr
0&0&0&1&2&0\cr
0&0&0&1&0&1\cr
&&3&0&2&1\cr
}$}
}\kern4cm}

\vskip 4.5cm

\centerline{6. T{\sevenrm HE} P{\sevenrm ERMUTATION}
C{\sevenrm ASE}}

\medskip
Suppose $c_1=\cdots=c_j=1$, $d_1=\cdots=d_k=1$ and still
$j+k=r$. Then the rearrangement class $R(\bfc,\bfd)$
becomes the symmetric group ${\cal S}_r$ of order~$r$.
As the length $l(\bfd)$ of~$\bfd$ is~$k$, we will write
$$
A_{\bfc,\bfd}(t)=A_r^k(t)
=\sum_{s=0 }^r A_{r,s}^k t^s
=\sum_w t^{\des_k w}
=\sum_w t^{\exc_k w}\quad (w\in {\cal S}_r).
$$
The statistic ``$\des_k$" applied to each permutation
$w=x_1x_2\ldots x_r \in {\cal S}_r$ has the following
simple form:
$$\des_k w =\cases{\des w,&if $x_r\le j$;\cr
1+\des w,&if $x_r\ge j+1$.\cr}\leqno(6.1)
$$
When $k=0$, the polynomial $A_r^k(t)$ is the usual
{\it Eulerian polynomial}, denoted by $A_r(t)$. Moreover,
$A_r^r(t)=t\,A_r(t)$. As it is well-known (see,~e.g.,
[Ri58, p.~211]), the exponential generating functions for
those polynomials are given~by
$$
\leqalignno{
1+\sum_{r\ge 1} {u^r\over r!} A_r(t)
&={1-t\over -t+\exp((t-1)u)};&(6.2)\cr
1+\sum_{r\ge 1} {u^r\over r!} t\,A_r(t)
&={(1-t)\exp(u(t-1))\over -t+\exp((t-1)u)}.&(6.3)\cr}
$$

The ``$\des_k$" interpretation given above for $A_r^k(t)$
provides the following recurrence relation for the
polynomials $A_r^k(t)$, namely
$$A_r^k(t)=A_r^{k-1}(t)+(t-1)A_{r-1}^{k-1}(t)
\qquad (1\le k\le r).\leqno(6.4)
$$

For the proof we just have to verify that
$t\,A_{r-1}^{k-1}(t)$ is the generating  polynomial for
the permutations ending with~$(j+1)$ by ``$\des_k$," while
$A_r^{k-1}(t)-A_{r-1}^{k-1}(t)$ is the generating
polynomials for the other permutations.\cqfd

\medskip
By iteration the recurrence (6.4) leads to:
$$\displaylines{(6.5)\quad
A_r^k(t)=A_r^0(t)+{k\choose 1}(t-1)A_{r-1}^0(t)
+{k\choose 2}(t-1)^2A_{r-2}^0(t)\hfill\cr
\hfill{}+\cdots
+\smash{{k\choose k}(t-1)^k} A_{r-k}^0(t).\quad\cr}
$$
Using the umbral notation $A^r\equiv A_r\equiv A_r^0(t)$
and $A^0\equiv 1$, formula (6.5) may be rewritten as
$$
A_r^k(t)=A^{r-k}\bigl((t-1)+A\bigr)^k.\leqno(6.6)
$$
The two complementary exponents $k$ and $r-k$ in (6.6)
suggest the introduction of the following polynomials in
the three variables~$x$, $y$,~$t$:
$$\leqalignno{
A_r(x,y,t)&=\sum_{k=0}^r {r\choose k}x^ky^{r-k}
A_r^k(t),&(6.7)\cr
\noalign{\hbox{so that}}
A_r(x,y,t)&=\bigl(x(t-1)+(x+y)A\bigr)^r,\qquad
A^r\equiv A_r.&(6.8)\cr}
$$
Now the familiar exponential generating function (6.2)
for the Eulerian polynomials may be rewritten as
$$
\exp(uA)={1-t\over -t+\exp((t-1)u)},
$$
so that
$$\leqalignno{\sum_{r\ge 0}{u^r\over r!}A_r(x,y,t)
&=\sum_{r\ge 0}{u^r\over r!}\bigl(x(t-1)
+(x+y)A\bigr)^r\cr
&=\exp\bigl(ux(t-1)\bigr)\exp\bigl(u(x+y)A\bigr)\cr
&={(1-t)\exp(ux(t-1))\over -t+\exp(u(x+y)(t-1))}\cr
\sum_{r\ge 0}{u^r\over r!}A_r(x,y,t)
&={(1-t)\exp(uy(1-t))\over
1-t\exp(u(x+y)(1-t))},&(6.9)\cr
}
$$
which in its turn specializes to (6.2) and (6.3) for
$x=0$, $y=1$, and $x=1$, $y=0$, respectively.

For the sake of completeness, we mention several formulas
on the polynomials $A_r(x,y,t)$ that can be derived from
(6.9) or even from the polynomials $A_{\bfc,\bfd}(t)$ of
section~2 by various (and classical) methods. First, let
$$\leqalignno{
A_r(x,y,t)&=\sum_{s=0}^r A_{r,s}(x,y)t^s,\cr
\noalign{\hbox{so that}}
A_{r,s}(x,y)&=\sum_k {r\choose k}
x^ky^{r-k}A_{r,s}^k.&(6.10)\cr}
$$
Then, a standard calculation (see, e.g., [Ri58, p.~39])
transforms (6.9) into
$$
{A_r(x,y,t)\over  (1-t)^{r+1}}
=\sum_{s\ge 0} t^s (xs+y(1+s))^r.\leqno(6.11)
$$
Formula (6.11) has an inverse formula, usually
called the {\it Worpitzky identity} (see, e.g., [Ri58,
p.~236]) 
$$\displaylines{\rlap{(6.12)}\hfill
\sum_{i=0}^r {z+i\choose r} A_{r,i}(x,y)
=\bigl(xz+y(1+z)\bigr)^r,\hfill\cr
\noalign{\hbox{that can be derived from (6.11) by
expanding $(1-t)^{r+1}$:}}
\sum_s A_{r,s}t^s \sum_l {r+l\choose r}t^l
=\sum_{s\ge 0} t^s (xs+y(1+s))^r\cr}
$$
and by looking for the coefficients of the same  power
of~$t$ in both members.

Now the recurrence formulas (2.7) and (2.10) for the
coefficients of the polynomials $A_{\bfc,\bfd}(t)$
specialize to
$$
\leqalignno{
A_{r,s}^k&=(r-s+1)A_{r-1,s-1}^{k-1}
+sA_{r-1,s}^{k-1};&(6.13)\cr
A_{r,s}^k&=(r-s)A_{r-1,s-1}^k+(s+1)A_{r-1,s}^k.
&(6.14)\cr}
$$
In their turn, those two formulas imply (easy derivation)
$$\displaylines{(6.15)\quad
A_{r,s}(x,y)=((r-s+1)x+(r-s)y)A_{r-1,s-1}\hfill\cr
\hfill{}+(sx+(s+1)y)A_{r-1,s}(x,y),\qquad\cr
\noalign{\hbox{a formula that can 
also be expressed as:}}
(6.16)\quad
A_r(x,y,t)=\bigl(y(1+(r-1)t)+xrt\bigr)A_{r-1}(x,y,t)
\hfill\cr
\hfill{}+ t(1-t)(x+y)A'_{r-1}(x,y,t).\qquad\cr}
$$


R{\sevenrm EMARK} 1. Notice that (6.16) was derived from the
recurrence formulas (2.7) and (2.10) that were given true
combinatorial interpretations in terms of ``$\des_k$." It
is also possible to derive the exponential generating
function for the polynomials $A_r(x,y,t)$, say~$A=A(u)$,
given in  (6.9), from (6.16) by using the same method that
was utilized in section~2. In fact, (6.16) is equivalent to
the  differential equation
$$yA+t(x+y)D_tA=D_uA,$$
whose solution in $A$ is precisely given by~(6.9).

\medskip
R{\sevenrm EMARK} 2. The exponential generating
function (6.9) has already been derived by several authors:
Stembridge [Stem91], Steingr\`\i msson [Ste93] and apparently
Brenti [Br93] in a paper to come. They all have worked in a
different context from the one  discussed in this paper.

\medskip
Steingr\`\i msson [Ste93] has recently generalized the
definitions of ``des" and ``exc" from permutations to
so-called ``indexed permutations", i.e., elements of the
wreath product $Z_n\wr {\cal S}_r$, where $Z_n$ stands
for the group of the integers mod~$n$. The elements of
$Z_n\wr {\cal S}_r$  are pairs $(w,p)$, where 
$w\in {\cal S}_r$ and $p$ is a mapping of $[\,r\,]$ into
$Z_n$. In his model, a indexed permutation $(w,p)$ has
a  descent at~$i$, if $1\le i\le r$, and if, either
$p(i)>p(i+1)$, or $p(i)=p(i+1)$ and $x_i>x_{i+1}$. (By
convention, $x_{r+1}=r+1$ and $p(r+1)=0$.) The indexed
permutation $(w,p)$ has an excedance at~$i$, if, either
$x_i>i$, or $x_i=i$ and $p(i)\ge 1$.

He does construct a bijection of 
$Z_n\wr {\cal S}_r$ onto itself that maps his ``$\des$"
onto his ``$\exc$." For each mapping~$p$ let
${\rm Pos}\,p=\{x\in Z_n:p(x)\ge 1\}$. Steingr\`\i msson 
shows that if $\#{\rm Pos}\,p=\#{\rm Pos}\,p'$, then
the two polynomials $\sum_w t^{\des (w,p)}$ and
$\sum_w t^{\des(w,p')}$ $(w\in {\cal S}_r)$ are identical.
When $p(x)=0$ for $x\le j=r-k$ and $p(x)\ge 1$ for 
$j+1\le x \le r$, the corresponding polynomial
$\sum_w t^{\des (w,p)}$ is equal to our  polynomial
$A_r^k(t)$, since $\des(w,p)=\des_k w$ in this case.

\vfill\eject
The generating  polynomial $D_r^n(t)$ for  
$Z_n\wr {\cal S}_r$ by ``des"  can then be evaluated as
follows 
$$
\eqalign{
D_r^n(t)&=\sum_{w,p}t^{\des(w,p)}
=\sum_{k=0}^r
\sum_{p,\,\#{\rm Pos}\,p=k} \sum_w t^{\des(w,p)}\cr
&=\sum_{k=0}^r A_r^k(t)\times
\#\{p:{\rm Pos}\,p=k\}
=\sum_{k=0}^r
A_r^k(t){r\choose k}(n-1)^k\cr
&=A(x,y,t)\bigm|_{\textstyle \{x=n-1,\, y=1\}}.\cr }
$$

Notice that the indexed permutation model coincides
partly with ours in the permutation case and has not
been extended to the case of arbitrary words (with
repetitions). However we give credit to
Steingr\`\i msson to have stated and proved analogues of
our theorems~3.1,~3.2 and~5.1 in his indexed permutation
set-up.


\medskip
A{\sevenrm ACKNOWLEDGEMENT}. The authors should like to thank
Guo-Niu Han for a careful reading of a former version of
the paper and for his helpful remarks.

\bigskip
\vfill\eject

%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}.\enspace 
     #3, {\sl #4}, vol.\nobreak\ {\bf #5}, {#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}.\enspace 
    {\sl #3}.\enspace  #4.\par}}
%reference complementaire :
\def\divers#1|#2|#3|
    {{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
     \llap{[#1]\hskip.35em}{#2}.\enspace 
     #3.\par}}

\vglue 44pt
\centerline{R{\sevenrm EFERENCES}}

{\eightpoint
\bigskip
\divers Br93|F. Brenti|Combinatorial properties of Betti
numbers of some toric varieties, Insitut Mittag-Leffler,
Report no.~9, {1991}-{1992}|

\livre CaFo69|Pierre Cartier and Dominique Foata|Probl\`emes
combinatoires de commutation et r\'earrangements|Berlin,
Springer-Verlag, $1969$ ({\sl Lecture Notes in Math.}, {\bf
85})|

\divers ClFo93b|Robert J. Clarke and Dominique
Foata|Eulerian Calculus, II: An extension of Han's
fundamental transformation, preprint, {1993}|

\divers ClFo93c|Robert J. Clarke and Dominique
Foata|Eulerian Calculus, III: the ubiquitous Cauchy
formula, preprint, {1993}|

\livre FoSc70|Dominique Foata   and
Marcel-Paul  Sch\"utzenberger|Th\'eorie g\'eom\'etrique
des po\-ly\-n\^omes eul\'eriens|Berlin, Springer-Verlag,
$1970$ ({\sl Lecture Notes in Math.}, {\bf 138})|

\article Ga79|Adriano  M. Garsia|On the ``maj" and ``inv"
$q$-analogues of Eulerian Polynomials|Linear and
Multilinear  Algebra|8|1979|21--34|

\livre Lo83|M.  Lothaire|Combinatorics on
words|Addison-Wesley, Reading, {1983}
({\sl Ency\-clo\-pedia of Math. and its Appl.}, {\bf 17})|

\livre Mac15|(Major) P.A. MacMahon|Combinatory
Analysis, {\rm vol.~1}|Cambridge, Cambridge Univ. Press,
$1915$ (Reprinted by Chelsea, New York,
$1955$)|

\livre Ri58|John Riordan|An Introduction to
Combinatorial Analysis|New York, J. Wiley, {1958}|

\divers Stem92|John  Stembridge|Some Permutation
Representations of Weyl Groups Associated with the
Cohomology of Toric Varieties, preprint
{1992}|

\divers Ste93|Einar
Steingr\`\i msson|Permutation Statistics of Indexed 
Permutations, to appear in {\sl Europ. J. Combinatorics},
1994|

\nobreak
\vskip 1cm
\line{\quad\vtop{\hbox{R{\fiverm OBERT} J. C{\fiverm LARKE},}
             \hbox{Pure Mathematics Department,}
              \hbox{University of Adelaide,}
             \hbox{Adelaide, South Australia 5005, Australia}
            \hbox{email : {\eightrm
rclarke@maths.adelaide.edu.au}}}\hfill
\vtop{\hbox{D{\fiverm OMINIQUE} F{\fiverm OATA,}}
                 \hbox{D\'epartement de math\'ematique,}
                 \hbox{Universit\'e Louis-Pasteur,}
                 \hbox{7, rue Ren\'e-Descartes,}
                 \hbox{F-67084 Strasbourg, France.}
                 \hbox{email : {\eightrm
foata@math.u-strasbg.fr}}}\quad}

}




\bye






