
\magnification=1200
\hsize=11.25cm
\voffset=.5cm

%%%
%eineri.tex: ``Babson-Steingr\'\imsson
%Statistics Are Indeed Mahonian (and Sometimes Even Euler-Mahonian)''
%a Plain TeX file by Dominique Foata and Doron Zeilberger 
%(14 pages)
 
%begin macros
\def\Grille{\setbox13=\vbox to 5mm{\hrule width 110mm\vfill}
\setbox13=\vbox{\offinterlineskip
   \copy13\copy13\copy13\copy13\copy13\copy13\copy13\copy13
   \copy13\copy13\copy13\copy13\box13\hrule width 110mm}
\setbox14=\hbox to 5mm{\vrule height 65mm\hfill}
\setbox14=\hbox{\copy14\copy14\copy14\copy14\copy14\copy14
   \copy14\copy14\copy14\copy14\copy14\copy14\copy14\copy14
   \copy14\copy14\copy14\copy14\copy14\copy14\copy14\copy14\box14}
\ht14=0pt\dp14=0pt\wd14=0pt
\setbox13=\vbox to 0pt{\vss\box13\offinterlineskip\box14}
\wd13=0pt\box13}

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

%������������������������������������������������������������������

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

%������������������������������������������������������������������

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

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

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

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

%������������������������������������������������������������������


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

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

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

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

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


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

\unitlength =1pt

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

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

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



\newif\if@negarg

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

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

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


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

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

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

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

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

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

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

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



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


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

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

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

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

%INITIALIZATION
\thinlines

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


% macros supplementaires (J.D.)

\newbox\tbox
\newbox\tboxa

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

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

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

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

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

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

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

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

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

\unitlength=1mm

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


\frenchspacing
\def\P{{\cal P}}
\def\Tilde{\char126\relax}
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
 0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
 height0.15cm width 0.01cm}}
\def\tir{\raise 2pt\hbox{{\thinspace\vrule height.5pt 
depth0pt width 3pt\thinspace}}}

\def\des{\mathop{\rm des}}
\def\rise{\mathop{\rm rise}}
\def\maj{\mathop{\rm maj}}
\def\mak{\mathop{\rm mak}}
\def\makl{\mathop{\rm makl}}
\def\stat{\mathop{\rm stat}}
\def\DESBOT{\mathop{{\hbox{\sevenrm DESBOT}}}}
\def\DES{\mathop{{\hbox{\sevenrm DES}}}}
\def\RISE{\mathop{{\hbox{\sevenrm RISE}}}}
\def\TROUGH{\mathop{{\hbox{\sevenrm TROUGH}}}}
\def\inv{\mathop{\rm inv}}
\def\card{\mathop{\rm card}}
\def\bfr{{\bf r}}
\def\bfc{{\bf c}}
\def\bfs{{\bf s}}
\def\rmS{{\rm S}}
\def\rmT{{\rm T}}
\def\red{\mathop{\rm red}}
\def\weight{\mathop{\rm weight}}
\def\gf{\mathop{\rm gf}}
\def\GF{\mathop{\rm GF}}

\font\eightrm=cmr8 \font\sixrm=cmr6 
\font\eighttt=cmtt8
\font\bigbf=cmbx10 at 11pt
\newif\ifpagetitre
\newtoks\auteurcourant \auteurcourant={DOMINIQUE FOATA AND
DORON ZEILBERGER}
\newtoks\titrecourant \titrecourant={BABSON-STEINGR\'IMSSON 
STATISTICS}

\pretolerance=500 \tolerance=1000 \brokenpenalty=5000
\newdimen\hmargehaute \hmargehaute=0cm
\newdimen\lpage \lpage=13.3cm
\newdimen\hpage \hpage=20cm
\newdimen\lmargeext \lmargeext=1cm
\def\margehaute{\vbox to \hmargehaute{\vss}}%
\def\margebasse{\vss}

\output{\shipout\vbox to \hpage{\margehaute\nointerlineskip
  \corpsdepage\margebasse}
  \advancepageno \global\pagetitrefalse
  \ifnum\outputpenalty>-20000 \else\dosupereject\fi}

\def\corpsdepage{\hbox to \lpage{\hss\pagetexte\hskip\lmargeext}}
\def\pagetexte{\vbox{\makeheadline\pagebody\makefootline}}
\headline={\ifpagetitre\titleheadline \else
  \ifodd\pageno\rightheadline \else\leftheadline\fi\fi}
\def\leftheadline{\eightrm\hfil\the\auteurcourant\hfil}
\def\rightheadline{\eightrm\hfil\the\titrecourant\hfil}
\def\titleheadline{\hfill}
\pagetitretrue

%\overfullrule=0in
%end macros
 
\vglue2cm

\centerline {\bigbf Babson-Steingr\'\i msson
Statistics Are Indeed Mahonian}
\smallskip
\centerline{\bigbf (and Sometimes Even Euler-Mahonian)}

\bigskip
\centerline{%
{\it Dominique FOATA}\footnote{$^1$}{\eightrm
D\'epartement de math\'ematique, Universit\'e Louis Pasteur,
F-67084  Strasbourg,\hfil\break 
{\eighttt foata@math.u-stasbg.fr};\quad
{\eighttt http://cartan.u-stasbg.fr/\Tilde foata/.}\hfil\break
Supported by the NSF, as a consultant on Zeilberger's grant.} 
and
{\it Doron ZEILBERGER}\footnote{$^2$}{\eightrm
Department of Mathematics, Temple University,
Philadelphia, PA 19122, USA. 
{\eighttt zeilberg@math.temple.edu};\quad 
{\eighttt http://www.math.temple.edu/\Tilde zeilberg/.}\hfil\break
Supported in part by the NSF.} 
}
 
\bigskip\bigskip
{\narrower
\noindent
{\bf Abstract:} Babson and Steingr\'\i msson have
recently introduced  eight new permutation statistics,
that they conjectured were all Mahonian (i.e. equi-distributed
with the number of inversions). We prove their conjecture
for the first four, and also prove that the first and
the fourth are even Euler-Mahonian. 
We use two different, in fact, opposite, techniques.
For three of them we give a computer-generated
proof, using the Maple package {\tt ROTA}, that implements
the second author's ``Umbral Transfer Matrix Method."
For the fourth one a geometric permutation transformation is
used that leads to a further refinement of this Euler-Mahonian
distribution study.

}

\bigskip\bigskip 
\centerline{\bf 1. Babson and Steingr\'\i msson's Notation}
 
\medskip
In [BaSt00] Babson and  Steingr\'\i msson introduced a convenient
notation for ``atomic" permutation statistics. Given a permutation
$w=x_1x_2\ldots x_n$ of $1,2,\ldots,n$ they define, for example,
$(a\tir bc)(w)$ to be the number of occurrences of the ``pattern"
$a\tir bc$, i.e. the number of pairs of places $1 \leq i <j<n$ such
that $x_i<x_j<x_{j+1}$. Similarly, the pattern $(b\tir ca)(w)$ is
that number of occurrences of $x_{j+1}<x_i<x_j$, and in general,
for any permutation $\alpha,\beta,\gamma$ of ${a,b,c}$, the
expression $(\alpha\tir \beta\gamma)(w)$ is the number of pairs
$(i,j)$, $1 \leq i <j<n$, such that the orderings of
the two triples $(x_i,x_j,x_{j+1})$ and $(\alpha,\beta,\gamma)$
are identical. The statistic $(ab\tir c)(w)$ is defined in the same
way by looking at the occurrences $(x_i,x_{i+1},x_j)$
such that $i+1<j$ and $x_i<x_{i+1}<x_j$. Of course,
$(ba)(w)$ denotes the number of {\it descents}, $\des w $ (i.e. the
number of places $1 \leq i <n$ such that $x_i>x_{i+1}$), and 
$(ab)(w)$ denotes the number of {\it rises}, $\rise w $ (i.e. the
number of places $1 \leq i <n$ such that $x_i<x_{i+1}$).
 

Using these atomic objects, Babson and Steingr\'\i msson noticed
that the classical permutation statistics ``$\inv$" and ``$\maj$"
may be written as $(bc\tir a)+(ca\tir b)+(cb\tir a)+(ba)$ and
$(a\tir cb)+(b\tir ca)+(c\tir ba)+(ba)$, respectively. This inspired them to 
perform a computer search for all statistics that could be thus
written, and look for those that appear to be Mahonian. They came
up with a list of 18. Some of them turned out to be well-known
(e.g. ``$\inv$" and ``$\maj$"), and some were new, but they could
do themselves. Yet eight new ``conjecturally Mahonian'' statistics
were left open. Here we do four of them. The other four should 
also be amenable to our methods.
 
\bigskip
\centerline{\bf 2. Notations and Results}
\medskip
Recall the usual notations
$$\leqalignno{
(a;q)_n&:=\cases{1,&if $n=0$;\cr
(1-a)(1-a q)\,\ldots\,(1-a q^{n-1}),&if
$n\geq 1$;\cr} &(2.1)\cr
(a;q)_{\infty }&:=\lim\nolimits_n(a;q)_n=
{\textstyle \prod\limits _{n\geq 0}(1-a
q^n)}.&(2.2)\cr 
\noalign{\hbox{Also, let}}
[n]_q&:={1-q^n\over 1-q}=(1+q+\cdots +q^{n-1});&(2.3)\cr
[n]_q!&:={(q;q)_n\over (1-q)^n}
=[n]_q\,[n-1]_q\,\cdots\,[1]_q&(2.4)\cr &=(1+q+\cdots
+q^{n-1})(1+q+\cdots+q^{n-2})\cdots(1).\cr }
$$

The sequence of polynomials $([n]_q!)$
$(n\ge 0)$ is said to be {\it Mahonian}. On the other hand, a
statistic ``stat" (actually, we should say a sequence
$(\stat_n)$ $(n\ge 0$) of statistics, where $\stat_n$ is defined on
the symmetric group~${\cal S}_n$) is  said to be {\it Mahonian},
if for every $n\ge0$ we have
$$
\sum_{w\in {\cal S}_n} q^{\stat w}=[n]_q!
$$

A sequence $(A_n(t,q))$ $(n\ge 0)$ of polynomials in two
variables~$t$ and~$q$, is said to be {\it Euler-Mahonian}, if one
of the following {\it equivalent} conditions holds:

(1) For every $n\ge 0$,
$$
{1\over (t;q)_{n+1}}\,A_n(t,q)
=\sum_{s\ge 0}t^s\,
\bigl([s+1]_q\bigr)^n.\leqno(2.5)
$$

(2) The exponential generating function for the fractions
$\displaystyle\smash{{A_n(t,q)\over (t;q)_{n+1}}}$ is given by:
$$
\sum_{n\ge 0}{u^n\over n!}\,
{A_n(t,q)\over (t;q)_{n+1}}
=\sum_{s\ge 0} t^s\, \exp(u\,[s+1]_q).\leqno(2.6)
$$

(3) The sequence $(A_n(t,q))$ satisfies the recurrence relation:
$$
(1-q) \,A_n(t,q)
= (1-tq^{n}) \,A_{n-1}(t,q) -q
(1-t) \,A_{n-1}(tq,q).\leqno(2.7)
$$

(4) Let \smash{$A_n(t,q)=\sum \limits_{s\ge
0} t^s\,A_{n,s}(q)$}. Then the coefficients $A_{n,s}(q)$
satisfy the recurrence:
$$
A_{n,s}(q)
= [s+1]_q\,A_{n-1,s}(q)
+q^{s}[n-s]_q\,A_{n-1,s-1}(q).\leqno(2.8)
$$

\medskip
It is routine to prove that those four conditions are equivalent
(see, e.g. [ClFo95, \S\S\kern2pt 6,7] for a proof in a more general
setting). Now a pair of statistics $(\stat_1,\stat_2)$ defined on
each symmetric group ${\cal S}_n$ $(n\ge 0)$ is said to be {\it
Euler-Mahonian}, if for every $n\ge 0$ we have
$$
\sum_{w\in {\cal S}_n} t^{\stat_1 w}q^{\stat_2 w}
=A_n(t,q).
$$

The first values of the Euler-Mahonian polynomials are the
following:
$A_0(t,q)=A_1(t,q)=1$; $A_2(t,q)=1+tq$;
$A_3(t,q)=1+t(2q+2q^2)+t^2q^3$;

\noindent
$A_4(t,q)=1+t(3q+5q^2+3q^3)+t^2(3q^3+5q^4+3q^5)
+t^3q^6$;

\noindent
$A_5(t,q)=1+t(4q+9q^2+9q^3+4q^4)
+t^2(6q^3+16q^4+22q^5+16q^6+6q^7)$

$\qquad{}+t^3(4q^6+9q^7+9q^8+4q^9)+t^4q^{10}$.
                    
\medskip
Our results are the following.
 
\proclaim Theorem 1. The permutation statistic\hfil\break
$\hbox{\hskip3.1cm} \rmS 11:=(a\tir cb)+2(b\tir
ca)+(ba)$\hfil\break is Mahonian.
 
\proclaim Theorem 2. The permutation statistic\hfil\break
$\hbox{\hskip3.1cm}\rmS 13:=(a\tir cb)+2(b\tir
ac)+(ab)$\hfil\break is Mahonian .

 \proclaim Theorem 3. Let\quad
$\rmS 5:=(b\tir ca)+(c\tir ab)+(a\tir
bc)+(ab)$.\hfil\break  Then, the pair $(\rise, \rm S5)$ is
Euler-Mahonian.
 
\proclaim Theorem 4. Let\quad
$\rmS 6:=(ba\tir c)+(c\tir ba)+(ba)+(ac\tir b)$.
\hfil\break
Then, the pair $(\des,\rmS 6)$ is Euler-Mahonian.
 
Our Theorems 1, 2, and 4 are the three parts of Conjecture 8 of
[BaSt00], while Theorem 3 is Conjecture~10 of [BaSt00]. In fact, our
Theorem 4 is stronger, since in [BaSt00] $\rmS6$ is only
conjectured to be Mahonian, but we will prove that it is in fact 
Euler-Mahonian when associated with ``des".
 
Several pairs of statistics are known to be Euler-Mahonian, the
pair $(\des,\maj)$ being the Euler-Mahonian pair, {\it par
excellence}, a result that goes back to Carlitz [Ca54], [Ca59], or
even in an implicit form to MacMahon [Ma15, vol.~2, p.~211]. For
proving that a given pair $(\stat_1,\stat_2)$ is Euler-Mahonian,
we can form the generating polynomial for ${\cal S}_n$ by the
pair
$(\stat_1,\stat_2)$, say, $B_n(t,q)$ and show that one of the
conditions (1), (2), (3) or (4) holds when $A_n(t,q)$ is replaced
by $B_n(t,q)$. This is the approach we have adopted for proving
the first three results, but we have done it in such a way that the
calculation can be computer-implemented, as we now explain.

It turns out that, thanks to the second author's recent theory
of the ``Umbral Transfer Matrix Method" [Ze00], the proofs of
the first three theorems are completely automatic, using the
general Maple package {\tt ROTA}, together with a new 
{\it interfacing} package {\tt PERCY} that computes the appropriate
Rota operators for what we will call {\it Markovian Permutation
Statistics}.
 
Since {\it Markovian Permutation Statistics} are easily amenable
to automatic treatment by {\tt ROTA}, and $\rmS 5$, $\rmS 11$,
and $\rmS 13$ happen to belong to that class (thanks to the
consistent location of the `dash'), all we did, after writing 
{\tt PERCY}, was to `plug them in'. {\tt PERCY} can, actually, handle
{\it arbitrary} Markovian Permutation Statistics. In particular, it
can be used to prove, in a few nano-seconds, MacMahon's classical
result that ``maj" is Mahonian. We believe that it can also discover
and prove many new results in addition to those proved here.
 
However, {\tt ROTA} is useless in the case of $\rmS6$,
since the location of the dash in 
$\rmS6:=(ac\tir b)+(ba\tir c)+(c\tir ba)+(ba)$ is not consistent.
So proving Theorem~4 still requires the traditional
combinatorial method: construct a {\it bijection} $w\mapsto w'$
of ${\cal S}_n$ onto itself which has the property that
$$
(\des,\rmS6)\,w'=(\des,\maj)\,w
$$
holds for every $w\in {\cal S}_n$. Instead of the pair
$(\des,\maj)$ we will take another Euler-Mahonian pair
$(\des,\mak)$, where ``mak" is a Mahonian statistic that was
introduced in our previous paper [FoZe90]. In the
Babson-Steingr\'\i msson notation ``mak" reads
$$
\mak:=(a\tir cb)+(cb \tir a)+(ba)+(ca\tir b),\leqno(2.9)
$$
wrongly designated by ``makl" in [BaSt00]. 
We will make use of the Euler-Mahonian pair
$(\des,\mak)$, but prove the stronger 
Theorem~$4'$, where an involution of~${\cal S}_n$ is
constructed that preverses the descent set and permutes two word
statistics~$U$ and~$V$ we now define.

First, the {\it descent bottom set} of a permutation
$w=x_1x_2\ldots x_n$ is defined to be the set $\DESBOT w$ of all
the $x_i$'s such that $2\le i\le n$ and $x_{i-1}>x_i$. Its
cardinality is the {\it number of descents} of~$w$,  $\des w$, so
that
$$
\des w=\# \DESBOT w.\leqno(2.11)
$$

Next, the word statistics $U$ and $V$ are introduced as follows.
Let $y=x_i$ be a letter of the permutation
$w=x_1x_2\ldots x_n$. Define
$$\leqalignno{
U_y(w)&:=(ca-b)\mid_{\textstyle b=y} w;&(2.12)\cr
V_y(w)&:=(b-ac)\mid_{\textstyle b=y} w.&(2.13)\cr
}
$$
Thus, $U_{y}(w)$ is the number of pairs of
adjacent letters
$x_jx_{j+1}$ to the left of $y=x_i$ such that $x_j>x_i>x_{j+1}$.
The word statistics $U$ and $V$ are then:
$$
\leqalignno{\noalign{\vskip-8pt}
U(w)&:=U_1(w)U_2(w)\,\ldots\, U_n(w);&(2.14)\cr
V(w)&:=V_1(w)\,V_2(w)\,\ldots\,V_n(w).&(2.15)\cr
}
$$
Now, recall the traditional  {\it reverse image}~$\bfr$, which is an
involution that maps each permutation  $w=x_1x_2\cdots x_n$
onto $\bfr\,w:=x_n\cdots x_2x_1$. We shall introduce another
involution~$\bfs$ of ${\cal S}_n$, called the 
{\it rise-des-exchange}, which exchanges the rises and the
descents of a permutation (in a sense that will be explained in
Section~6, but can be immediately visualized in Fig.~1) and keeps
peaks and troughs in their original ordering. We can then consider
the involution $\bfr\,\bfs$.

\proclaim Theorem $4'$. The involution $\bfr\,\bfs$
of  ${\cal S}_n$  has the following properties:
$$\displaylines{\noalign{\vskip-8pt}
{\rm (a)}\quad \DESBOT \bfr\,\bfs\,w=\DESBOT w;\hfill\cr
{\rm (b)}\quad (U,V)\,\bfr\,\bfs\,w=(V,U)\,w.\hfill\cr}
$$

\noindent
In Section~6 we will show how Theorem $4'$ implies Theorem~4.

\bigskip

\centerline{\bf 3. Markovian Permutation Statistics}
\medskip
The {\it reduction} of a sequence of $n$ distinct integers $w$,
denoted by $\red (w)$, is the permutation obtained by replacing
the smallest member by $1$, the second-smallest by $2$, \dots~,
and the largest by $n$. For example, $\red (8\,3\,5\,9\,2)
=4\,2\,3\,5\,1$.

\medskip
{\it Definition}.\quad A permutation statistic 
$F:{\cal S}_n \rightarrow {\bf Z}$ is said to be {\it Markovian}, if
there exists a function $h(j,i,n)$ such that
$$
F(x_1 \cdots x_n)
=F(\red(x_1 \cdots x_{n-1}))+h(x_{n-1},x_n,n).
$$
 
{\it Definition}: A Markovian permutation statistic $F:{\cal S}_n
\rightarrow Z$ is said to be {\it Nice Markovian} if the above 
$h(j,i,n)$ can be written as
$$
h(j,i,n)= \cases {f(j,i,n),&if $j<i$;\cr
                 g(j,i,n),&if $j>i$;\cr} 
$$
where $f$ and $g$ are {\it affine linear functions} of their
arguments, i.e. can be written as $ai+bj+cn+d$, for some integers
$a,b,c,d$.

\medskip
>From now on we, and the Maple package {\tt PERCY}, will only
consider Nice Markovian Permutation Statistics.
We will denote them by $[f,g,j,i,n]$. For example,
$\inv=[n-i,n-i,j,i,n]$, $\maj=[0,n-1,j,i,n]$, $\des=[0,1,j,i,n]$,
$\rise=[1,0,j,i,n]$, etc.
 
Given a permutation statistic $F$ we are interested in
the sequence  of polynomials
$$
\gf (F)_n(q):=\sum_{w \in {\cal S}_n} q^{F(w)}\quad(n\ge 0).
$$
However, in order to take advantage of Markovity,
we need to consider the more refined
$$
\GF(F)_n(q,z)
:=\sum_{w=x_1\ldots x_n \in {\cal S}_n} q^{F(w)}z^{x_n} \quad
(n\ge 0)
$$
that also keeps track of the last letter~$x_n$.
Now, using {\it Rota operators} (see [Ze00]),
it is easy to express $\GF(F)_n$ in terms of $\GF(F)_{n-1}$.
Let $w':=x'_1\cdots x'_{n-1}=\red(x_1 \cdots x_{n-1}$); then
$$\eqalignno{
\GF(F)_n(q,z)&:=
\sum_{i=1}^n z^i \sum_
{\scriptstyle w \in {\cal S}_n \atop  \scriptstyle x_n=i} 
q^{F(w)}\cr
&=\sum_{i=1}^n  z^i 
\Bigl(\sum_{j=1}^{i-1} 
\sum_{\scriptstyle w \in {\cal S}_n \atop \scriptstyle 
x_{n-1}=j,\,x_n=i} 
\kern-15pt q^{F(w)} 
+\sum_{j=i+1}^n 
\sum_{\scriptstyle w\in {\cal S}_n \atop \scriptstyle
x_{n-1}=j,\,x_n=i} 
\kern-15pt q^{F(w)} \Bigr )\cr
&=\sum_{i=1}^n z^i 
\Bigl(\sum_{j=1}^{i-1} \kern-5pt
\sum_{\scriptstyle w \in {\cal S}_n\atop\scriptstyle x_{n-1}=j}
\kern-8pt q^{F(w')+f(j,i,n)}
+\kern-5pt\sum_{j=i+1}^n \kern-5pt
\sum_{\scriptstyle w\in {\cal S}_n \atop \scriptstyle x_{n-1}=j}
\kern-8pt q^{F(w')+g(j,i,n)}\Bigr)\cr
&=\kern-5pt\sum_{j<i\leq n} 
\kern-5pt z^i \kern-5pt
\sum_{\scriptstyle w' \in S_{n-1} \atop \scriptstyle x'_{n-1}=j}
\kern-10pt q^{F(w')+f(j,i,n)}
+\kern-8pt \sum_{i\le j\leq n-1}z^i\kern -5pt 
\sum_{\scriptstyle w' \in S_{n-1} \atop \scriptstyle x'_{n-1}=j}
\kern-10pt q^{F(w')+g(j+1,i,n)} \cr
&=\sum_{j=1}^{n-1}
\sum_{\scriptstyle w' \in S_{n-1}\atop \scriptstyle x'_{n-1}=j}
\Bigl( \sum_{i=1}^j 
q^{g(j+1,i,n)} z^i
+\sum_{i=j+1}^{n} q^{f(j,i,n)}z^i \Bigr) 
q^{F(w')}.\cr}
$$
Now for $1\le j\le n-1$ introduce the {\it umbra} $\P$,
$$
\P (z^j):=
\Bigl( \sum_{i=1}^j q^{g(j+1,i,n)}z^i+
\sum_{i=j+1}^{n} q^{f(j,i,n)}z^i \Bigr),\leqno(3.1)
$$
and extend by linearity, so that $\P$ is defined 
on all polynomials of degree $\le n-1$.
In terms of $\P$, we have the very simple recurrence:
$$
\GF(F)_n(q,z)= \P (\GF(F)_{n-1}(q,z)).
$$
Of course, $\P$ itself may (and usually is) complicated, but 
{\it we don't care}, we don't even have to see it, since Maple can
compute the umbra automatically,  (all it has to do is to be able
to sum geometric series symbolically, that it does very well), and
store it for later. All the users have to enter is $f$ and $g$, or if
they prefer, they may use the notation of [BaSt00], and
{\tt PERCY} would convert it to the Markovian notation, and take it
from there.

\bigskip
\centerline{\bf 4. Proofs of Theorems 1, 2, 3}
\medskip
{\it Proof of Theorem $1$}.\quad
 Using {\tt PERCY} (and {\tt ROTA}) (or even by hand!) we get that
the umbra $\P$ linking $\GF(\rmS11)_{n-1}(q,z)$ to
$\GF(\rmS11)_{n}(q,z)$, as defined in (3.1), maps the polynomial
$a(z)$ onto
$$
{ {z^{n+1}a(1)-za(z)} \over {z-1}}+
{ {z(a(qz)-a(q^2))} \over {z-q}} .
$$
Hence $b_{n}(z):=\GF(\rmS11)_n(q,z)$ satisfies the functional
recurrence
$$
b_n(z)={ {z^{n+1}b_{n-1}(1)-zb_{n-1}(z)} \over {z-1}}+
{ {z(b_{n-1}(qz)-b_{n-1}(q^2))} \over {z-q}} ,
$$
with the initial condition $b_1(z)=z$.
But, the same is true of
$$
c_n(z):=z\,{{(z^n-q^n)} \over {(z-q)}} [n-1]_q! 
\quad {\rm (check!).}
$$
Hence $b_n(z)=c_n(z)$, and finally $b_n(1)=c_n(1)=[n]_q!$

\bigskip
{\it Proof of Theorem $2$}.\quad
Using {\tt PERCY} (and {\tt ROTA}) (or even by hand!) we get that
the umbra linking $\GF(\rmS 13)_{n-1}(q,z)$ to 
$\GF(\rmS 13)_{n}(q,z)$ is
$$
a(z) \mapsto  {{z(a(zq)-a(1))} \over {qz-1}}+
{ {zqa(z)-q^{2n+1}z^{n+1}a(q^{-2})} \over {1-zq^2}}.
$$
Hence $d_{n}(z):=\GF(\rmS 13)_n(q,z)$ satisfies the functional
recurrence
$$
d_n(z)={{ z(d_{n-1}(zq)-d_{n-1}(1))} \over {qz-1}}+
{ {zqd_{n-1}(z)-q^{2n+1}z^{n+1}
d_{n-1}(q^{-2})} \over {1-zq^2}}.
$$
with the initial condition $d_1(z)=z$. But, the same is true of
$$
e_n(z):=z\,{{(1-q^nz^n)} \over {(1-qz)}} [n-1]_q! \quad {\rm
(check!).}
$$
Hence $d_n(z)=e_n(z)$, and finally $d_n(1)=e_n(1)=[n]_q!$

\goodbreak
\bigskip
{\it Proof of Theorem $3$}.\quad
 {\tt PERCY} can just as easily compute the Umbra for 
{\it multi-statistics}, when the generating function is the
weight-enumerator of
${\cal S}_n$  according to the weight
$$
\weight(w):=z^{x_n} \prod_{j=1}^{r}
q_j^{F_j(w)},
$$
where $w=x_1\ldots x_n$ and $F_1(w)$, \dots~, $F_r(w)$ are {\it
several} Nice Markovian permutation statistics.
Define
$$
A_n(t,q;z):=\sum_{w \in {\cal S}_n} 
\kern -3pt t^{\des w}q^{\maj w} z^{x_n},\quad
B_n(t,q;z):=\sum_{w \in {\cal S}_n} 
\kern-3pt t^{\rise w}q^{\rmS5\,w}z^{x_n}.
$$
{\tt PERCY}, using {\tt ROTA}, computes the following functional
equations (that in fact, are simple enough to be derivable by
humans):
$$\displaylines{(4.1)\kern5pt
A_n(t,q;z)=
{{z(1-tq^{n-1})A_{n-1}(t,q;z)-z(z^n-tq^{n-1})A_{n-1}(t,q;1)}
\over {1-z}};\hfill\cr
(4.2)\kern5pt
B_n(t,q;z)=
{{z(1-tq^n)B_{n-1}(t,q;z)-z(1-tz^n)B_{n-1}(t,q;q)}
\over {z-q}}.\hfill\cr}
$$
We have to prove that $B_n(t,q;1)=A_n(t,q;1)=A_n(t,q)$, the
Euler-Mahonian polynomial, as defined in (2.5)-(2.8), as we
already know that $(\des,\maj)$ is Euler-Mahonian. By comparing
the two functional recurrences, we get that
$B_n(t,q;z)=q^{-n}z^{n+1} A_n(tq,q;q/z)$, hence
we have to prove that $A_n(tq,q;q)=q^nA_n(t,q;1)=A_n(t,q)$.
By plugging $t=tq$, $z=q$ into (4.1), and using the
induction hypothesis, we get that 
$$\displaylines{\quad
A_n(tq,q;q)\hfill\cr
\kern1.2cm{}=
{{q(1-(tq)q^{n-1})A_{n-1}(tq,q;q)
-q(q^n-(tq)q^{n-1})A_{n-1}(tq,q;1)}\over {1-q}}\hfill\cr
\kern1.2cm{}=
{{q(1-tq^n)q^{n-1}A_{n-1}(t,q;1)-q^{n+1}(1-t)A_{n-1}(tq,q;1)}
\over {1-q}}\hfill\cr
\kern1.2cm{}=
q^n{{(1-tq^n)A_{n-1}(t,q)-q(1-t)A_{n-1}(tq,q)}
\over
{1-q}}. \hfill\cr}
$$
But, this equals $q^n A_n(t,q)$ by (2.7).\quad\halmos

\medskip
 
The input and output files of {\tt PERCY}, for all the
above claimed statements, can be downloaded from
$$
\hbox{\tt http://www.math.temple.edu/\Tilde
zeilberg/programs.html}.
$$
\bigskip
\vfill\eject
\centerline{\bf 5. A Brief Description of {\tt PERCY}}

\medskip
You must have  {\tt MAPLE$^{{\eighttt TM}}$}.
First go to Zeilberger's homepage
$$
\hbox{\tt http://www.math.temple.edu/\Tilde zeilberg/},
$$
click on programs, and download {\tt PERCY} and {\tt ROTA}.
Make sure that they reside in the same directory in your 
computer. Then go into Maple (by typing: {\tt maple } ,
followed by {\tt ENTER} ), and type
{\tt read PERCY;} . Then follow the on-line instructions.
In particular, to get a list of all procedures, type:
{\tt Ezra(); } (not to be confused with {\tt ezra();}
and {\tt ezra1();}, that refer to {\tt ROTA}; for 
information about {\tt ROTA}, see [Ze00]).
 
{\tt BSE(bitui,j,i,n)} inputs an expression,
{\tt bitui} in the notation of
[BaSt00], and three variables {\tt j,i,n} and returns the
Nice Markovian Statistic in the $[f,g,j,i,n]$ notation.
Given a Markovian permutation statistic
{\tt MPS=[f,g,j,i,n]}, {\tt PermPreUmbra(MPS,q,z);} 
and {\tt PermUmbra(MPS,q,z);} find
the pre-umbra and umbra respectively connecting the
weight-enumerator of $S_{n-1}$ to that of ${\cal S}_n$.
For example {\tt PermUmbra([0,n-1,j,i,n],q,z)}
does it for {\it maj}. 
 
Given a Markovian permutation
statistic, {\tt MPS}, a variable {\tt q}, and a positive integer
$L$,  {\tt GF(MPS,q,L);} finds the first $L$ terms
in the weight-enumeration sequence, {\it fast}, using
the umbra (by calling {\tt ROTA}). The skeptic can check
the answer (for small $L$!), by also doing
{\tt GFdirect(MPS,q,L);}, which computes by direct (super-exponentially
slow) enumeration.
{\tt PermUmbraMS(MPSs,qs,z)} and 
{\tt GFMS(MPSs,qs,L)} are the analogous functions for multi-statistics,
where {\tt MPSs} is a list of Markovian permutation statistics and
{\tt qs} is a list of corresponding variables.
For example, to get the first $10$ terms in the sequence
of the Euler-Mahonian polynomials, type
{\tt GFMS([[0,n-1,j,i,n],[0,1,j,i,n]],[q,t],10);} .
For more details, download {\tt PERCY} and use the on-line
help.

\bigskip 
\centerline{\bf 6. Proof of Theorem $\bf 4'$}

\medskip
The {\it reverse image}~$\bfr$ was redefined at the
end of Section~2. The definition of the involution
$\bfs$, which is now given, is based on the {\it peak-trough
factorization} of a permutation. By {\it peak} of the permutation
$w=x_1x_2\cdots x_n$ we mean a letter $x_j$ such that $1\le
j\le n$ and
$x_{j-1}<x_j$,
$x_j>x_{j+1}$. [By convention, $x_0=x_{n+1}:=0$.] By {\it trough}
we mean a letter $x_j$ such that $2\le j\le n-1$ and
$x_{j-1}>x_j$, $x_j<x_{j+1}$. Accordingly, each permutation has
$k$~troughs and $(k+1)$ peaks for some $k\ge 0$. By 
{\it double descent} we mean a letter $x_j$ such that $2\le j\le n$
and $x_{j-1}>x_j>x_{j+1}$. By {\it double rise} we mean a letter
$x_j$ such that $1\le j\le n-1$ and $x_{j-1}<x_j<x_{j+1}$.

In the following $p$ and $t$ will designate 
{\it letters} which are peaks and troughs, respectively, while $d$,
$h$, will designate {\it words} all letters of which are double
descents, double rises, respectively.

\goodbreak
\medskip
Each permutation~$w$ has a unique factorization, called its 
{\it peak-trough factorization}
$w=h_1p_1d_1t_1\;\ldots \;h_{k-1}p_{k-1}d_{k-1}t_{k-1}\;
h_kp_kd_k$, having the following properties:

(1) $k\ge 1$;

(2) the $p_i$'s are the {\it peaks} and the $t_i$'s the {\it troughs} of the
permutation;

(3) for each $i$ the symbols $h_i$, $d_i$ are {\it words}, possibly
empty, all letters of which are {\it double rises}, {\it double rises},
respectively.

\medskip
It will be convenient to put $t_0=t_k:=0$. The set of all the
letters in the juxtaposition product
$d_1t_1\ldots d_{k-1}t_{k-1}d_k$, i.e. the set of all the double
descents and troughs of the permutation~$w$, is the 
{\it descent bottom set}, $\DESBOT w$, of~$w$ introduced in
Section~2 (see (2.11)).

\medskip
{\it Definition of the involution $\bfs$.}\quad
Let $y$ be a {\it double rise} of~$w$, so that~$y$ is a letter of a
factor~$h_j$ for some~$j$ $(1\le j\le k)$. Define $\varphi_w(y)$
to be the {\it least integer}~$i$ such that $j\le i\le k$ and
$p_i>y>t_i$.

Define $d'_i$ to be the {\it decreasing word} of all double
rises~$y$ in~$w$ such that $\varphi_w(y)=i$. If
$\varphi_w(y)\not=i$ for every double rise~$y$ of~$w$, let
$d_i'$ be the empty word.

Let $y$ be a double descent of~$w$, so that~$y$ is a letter of a
factor~$d_j$ for some~$j$ $(1\le j\le k)$ and $p_j>y>t_j$. Define
$\varphi_w(y)$ to be the {\it greatest integer}~$i$ such that
$1\le i\le j$ and $t_{i-1}<y<p_i$.

Define $h'_i$ to be the {\it increasing word} of all double
descents~$y$ in~$w$ such that $\varphi_w(y)=i$. If
$\varphi_w(y)\not=i$ for every double descent~$y$ of~$w$, let
$h'_i$ be the empty word.

Then, let
$$
\bfs\,w:=h'_1p_1d'_1t_1\;\ldots \;h'_{k-1}
p_{k-1}d'_{k-1}t_{k-1}\;h'_kp_kd'_k.\leqno(6.1)
$$

The construction is illustrated in Fig. 1. To obtain the graph of
$\bfs\,w$ we have to move the double rises to the right until they
hit the first decreasing segment $p_i>t_i$. There is necessarily
one since, by assumption, $t_k=0$. Likewise, we move the double
descents to the left until they reach the first increasing segment
$t_{i-1}<p_i$, which exists since $t_0=0$ by convention.

\def\pic#1{#1\hskip-8pt\raise 10pt\hbox{$\wedge$}\thinspace}
\def\petitpic#1{#1\hskip-5pt\raise
10pt\hbox{$\wedge$}\kern-2pt}
\def\petittrou#1{#1\hskip-6pt\lower
8pt\hbox{$\vee$}\kern-1pt}

In the example we start with the permutation
$$\leqalignno{
w&=10, \pic{11}, \petittrou 2, 4, 5, 
\petitpic {9}, \petittrou 6, 12, 14, \pic{15}, 7, 3,
\petittrou 1, 8,
\pic{13}\cr
\noalign{\hbox{and we obtain the permutation}}
\bfs\,w&=\pic{11}, 10, \petittrou 2,3,
\petitpic 9, \petittrou 6, 7, \pic{15}, 14,12,5,4, \petittrou 1, 
\pic{13},8,\cr}
$$
where the peaks (resp. the troughs) are materialized by
``$\wedge$" (resp. ``$\vee$")

\midinsert

\newbox\boxredblue

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

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


\setbox\boxredblue=\vbox{
\vskip20mm
\offinterlineskip 
\centerput(20,20){$w$}
\segment(0,10)\dir(1,1)\long{5}
\centerput(-3,10){\sevenrm 10}
\fleche(1,10)\dir(1,0)\long{4}
\segment(5,15)\dir(1,-6)\long{5}
\centerput(5,16){\sevenrm 11}
\segment(10,-15)\dir(1,1)\long{5}
\centerput(10,-18){\sevenrm 2}
\segment(15,-10)\dir(1,1)\long{5}
\centerput(14,-9){\sevenrm 4}
\fleche(16,-10)\dir(1,0)\long{37}
\segment(20,-5)\dir(1,3)\long{5}
\centerput(18.5,-5){\sevenrm 5}
\fleche(21,-5)\dir(1,0)\long{30}
\segment(25,10)\dir(1,-2)\long{5}
\centerput(25,11){\sevenrm 9}
\segment(30,0)\dir(1,4)\long{5}
\centerput(30,-2.5){\sevenrm 6}
\segment(35,20)\dir(1,1)\long{5}
\centerput(33,20){\sevenrm 12}
\fleche(36,20)\dir(1,0)\long{9.5}
\segment(40,25)\dir(2,1)\long{5}
\centerput(40,26){\sevenrm 14}
\fleche(41,25)\dir(1,0)\long{4}
\segment(45,27.5)\dir(1,-5)\long{5}
\centerput(45,28){\sevenrm 15}
\segment(50,2.5)\dir(1,-3)\long{5}
\centerput(51,2.5){\sevenrm 7}
\fleche(49.5,2.5)\dir(-1,0)\long{18}
\segment(55,-12.5)\dir(3,-4)\long{5}
\centerput(56.5,-12.5){\sevenrm 3}
\fleche(54,-12.5)\dir(-1,0)\long{40}
\segment(60,-19)\dir(1,5)\long{5}
\centerput(60,-22){\sevenrm 1}
\segment(65,5.5)\dir(1,3)\long{5}
\centerput(63.5,5.5){\sevenrm 8}
\fleche(66.5,5.5)\dir(1,0)\long{7}
\centerput(69.5,21){\sevenrm 13}
%
}

\vglue2cm
\centerline{\box\boxredblue\hskip7.5cm}

\newbox\boxredred
\def\tiret{\vrule height 1pt depth0pt width 3pt}
\setbox\boxredred=\vbox{\vskip
28mm\offinterlineskip 
%
\centerput(20,20){${\bf s}\,w$}
\centerput(8,10){\sevenrm 10}
\centerput(5.7,10){\tiret}
\segment(5,15)\dir(1,-6)\long{5}
\centerput(5,16){\sevenrm 11}
\segment(10,-15)\dir(1,1)\long{5}
\centerput(10,-18){\sevenrm 2}
\segment(15,-10)\dir(1,1)\long{5}
\centerput(55.5,-10){\sevenrm 4}
\centerput(54,-10){\tiret}
\segment(20,-5)\dir(1,3)\long{5}
\centerput(54,-5){\sevenrm 5}
\centerput(52.5,-5){\tiret}
\segment(25,10)\dir(1,-2)\long{5}
\centerput(25,11){\sevenrm 9}
\segment(30,0)\dir(1,4)\long{5}
\centerput(30,-2.5){\sevenrm 6}
\segment(35,20)\dir(1,1)\long{5}
\centerput(48.5,20){\sevenrm 12}
\centerput(46.3,20){\tiret}
\segment(40,25)\dir(2,1)\long{5}
\centerput(47.5,24){\sevenrm 14}
\centerput(45.5,24){\tiret}
\segment(45,27.5)\dir(1,-5)\long{5}
\centerput(45,28){\sevenrm 15}
\segment(50,2.5)\dir(1,-3)\long{5}
\centerput(32.5,2.5){\sevenrm 7}
\centerput(31,2.5){\tiret}
\segment(55,-12.5)\dir(3,-4)\long{5}
\centerput(15,-13.5){\sevenrm 3}
\centerput(12.5,-12.5){\tiret}
\segment(60,-19)\dir(1,5)\long{5}
\centerput(60,-22){\sevenrm 1}
\segment(65,5.5)\dir(1,3)\long{5}
\segment(70,20)\dir(1,-3)\long{5}
\centerput(76,5.5){\sevenrm 8}
\centerput(75,4.5){\tiret}
\centerput(69.5,21){\sevenrm 13}
%
}

\vglue3cm
\centerline{\box\boxredred\hskip7.5cm}


\newbox\boxblueblue
\def\tiret{\vrule height 1pt depth0pt width 3pt}
\setbox\boxblueblue=\vbox{\vskip
28mm\offinterlineskip 
%
\centerput(20,25){${\bf r\,s}\,w$}
\centerput(72,10){\sevenrm 10}
\centerput(74.3,10){\tiret}
\segment(75,15)\dir(-1,-6)\long{5}
\centerput(75,16){\sevenrm 11}
\segment(70,-15)\dir(-1,1)\long{5}
\centerput(70,-18){\sevenrm 2}
\segment(65,-10)\dir(-1,1)\long{5}
\centerput(24.5,-10){\sevenrm 4}
\centerput(26,-10){\tiret}
\segment(60,-5)\dir(-1,3)\long{5}
\centerput(26,-5){\sevenrm 5}
\centerput(27.5,-5){\tiret}
\segment(55,10)\dir(-1,-2)\long{5}
\centerput(55,11){\sevenrm 9}
\segment(50,0)\dir(-1,4)\long{5}
\centerput(50,-2.5){\sevenrm 6}
\segment(45,20)\dir(-1,1)\long{5}
\centerput(31.,20){\sevenrm 12}
\centerput(33.2,20){\tiret}
\segment(40,25)\dir(-2,1)\long{5}
\centerput(32,24){\sevenrm 14}
\centerput(34.5,24){\tiret}
\segment(35,27.5)\dir(-1,-5)\long{5}
\centerput(35,28){\sevenrm 15}
\segment(30,2.5)\dir(-1,-3)\long{5}
\centerput(47.5,2.5){\sevenrm 7}
\centerput(49.5,2.5){\tiret}
\segment(25,-12.5)\dir(-3,-4)\long{5}
\centerput(65,-13.5){\sevenrm 3}
\centerput(67.5,-12.5){\tiret}
\segment(20,-19)\dir(-1,5)\long{5}
\centerput(20,-22){\sevenrm 1}
\segment(15,5.5)\dir(-1,3)\long{5}
\segment(10,20)\dir(-1,-3)\long{5}
\centerput(7,5.5){\sevenrm 8}
\centerput(5,4.5){\tiret}
\centerput(9.5,21){\sevenrm 13}
%
}

\vglue3cm
\centerline{\box\boxblueblue\hskip7.5cm}

\vskip2.2cm
\centerline{Fig. 1}

\endinsert

\bigskip
Let $\RISE w$ (resp. $\DES w$, resp. $\TROUGH w$) be the set of
of all the double rises (resp. the double descents, resp. the troughs)
of~$w$, so that $\DESBOT w=\DES w\cup \TROUGH w$.

\proclaim Lemma 6.1. The operation $\bfs$ is an
involution. Moreover,\hfil\break 
{\rm (a)} $\DES\, \bfs\,w=\RISE\,w$,
$\RISE\, \bfs\,w=\DES \,w$
and $\TROUGH \bfs\,w=\TROUGH w$;\hfil\break
{\rm (b)} $(U,V)\,\bfs\,w=(U,V)\,w$.

{\it Proof.}\ 
When passing from $w$ to $\bfs\,w$ the subword
$p_1t_1\;\ldots \;p_{k-1}t_{k-1}\; p_k$ made of the successive
peaks and troughs remains alike. The double rises (resp. double
descents) of~$w$ are transformed into double descents (resp.
double rises) of~$\bfs\,w$. 

By considering the graphs of the permutations~$w$ and $\bfs\,w$
it is clear that we recover~$w$ by applying~$\bfs$ to $\bfs\,w$
itself.

Finally, if $y$ is a double rise of~$w$ between $t_{j-1}$ and
$p_j$, we have defined $\varphi_w(y)$ as the {\it least
integer}~$i$ such that $j\le i\le k$ and $p_i>y>t_i$.
Accordingly,  the number of pairs $p_l>t_l$ to the left of~$y$ in
both $w$ and $\bfs\,w$ is the same and the number of pairs
$t_{l-1}<p_l$ to the right of~$y$ is also the same in both~$w$
and $\bfs\,w$. Accordingly,
$$\eqalignno{
U_y(w)&:=(ca\tir b)\mid_{\textstyle b=y} w\cr
&=\sum_{1\le l\le j-1}\chi(p_l>y>t_l)\cr
&=\sum_{1\le l\le i-1}\chi(p_l>y>t_l)\cr
&=(ca\tir b)\mid_{\textstyle b=y} \bfs\,w=U_y(\bfs\,w).\cr}
$$
In the same manner,
$$\eqalignno{
V_y(w)&:=(b\tir ac)\mid_{\textstyle b=y} w\cr
&=\sum_{j+1\le l\le k-1}\chi(t_{l}<y<p_{l+1})\cr
&=\sum_{i\le l\le k-1}\chi(t_{l}<y<p_{l+1})\cr
&=(b\tir ac)\mid_{\textstyle b=y} \bfs\,w=V_y(\bfs\,w).\cr}
$$
There is an analogous proof when $y$ is a double
descent of~$w$.\quad\halmos

\proclaim Lemma 6.2. The reverse image $\bfr$ has the
following properties:\hfil\break 
{\rm (a)} $\DES\, \bfr\,w=\RISE\,w$,
$\RISE\, \bfr\,w=\DES \,w$
and $\TROUGH \bfr\,w=\TROUGH w$;\hfil\break
{\rm (b)} $(U,V)\,\bfr\,w=(V,U)\,w$.

{\it Proof}.\quad 
Property (a) is obvious. On the other hand, when going from~$w$
to $\bfr\,w$ each decrease $ca$ to the left of~$y$ in~$w$ will
become an increase $ac$ to the right of~$y$ in $\bfr\,w$, so that
(b) holds.\quad\halmos

\medskip
It follows from Lemmas 6.1 and 6.2 that
$\DES \bfr\,\bfs\,w=\RISE \bfs\,w=\DES\,w$ and
$\TROUGH \bfr\,\bfs\,w=\TROUGH \bfs\,w=\TROUGH\,w$, so that
$\DESBOT \bfr\,\bfs\,w=\DESBOT\,w$. Finally,
$(U,V)\,\bfs\,\bfr\,w=(U,V)\,\bfr\,w=(V,U)\,w$. This completes the
proof of Theorem $4'$.

\goodbreak
\medskip
In the example of Fig.~1 we have
$$\leqalignno{
w&=10, \pic{11}, \petittrou 2, 4, 5, 
\petitpic {9}, \petittrou 6, 12, 14, \pic{15}, 7, 3,
\petittrou 1, 8,
\pic{13},\cr
\bfs\,w&=\pic{11}, 10, \petittrou 2,3,
\petitpic 9, \petittrou 6, 7, \pic{15}, 14,12,5,4, \petittrou 1, 
\pic{13},8,\cr
\bfr\,\bfs\,w&=
8,\pic{13},\petittrou 1,4,5,12,14,\pic{15},7,\petittrou 6,
\petitpic 9,3,\petittrou 2,10,\pic{11},  \cr
}
$$
and we can verify that:
$$\pmatrix{y\cr U_y(\bfr\,\bfs\,w)\cr V_y(\bfr\,\bfs\,w)\cr}
\!=\!\left(\vcenter{\halign{&\hfil\kern2pt #\kern 2pt\hfil\cr
\ 1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\cr
\ 0&1&1&1&1&1&1&0&2&2&2&1&0&0&0\cr
\ 0&0&1&1&1&1&2&3&1&0&0&0&1&0&0\cr
}}\right)
\!=\!\pmatrix{y\cr V_y(w)\cr U_y(w)\cr}\!.
$$

\bigskip
\centerline{\bf 7. Proof of Theorem 4 and Consequences}

\medskip
Let $\Sigma\DESBOT w$ be the {\it sum} of all the letters~$x_i$
of the permutation $w=x_1x_2\cdots x_n$ which belong to the
descent bottom set 
$\DESBOT w$. 

\proclaim Lemma 7.1. For each permutation~$w$ we have:
$$
\Sigma\DESBOT w=
\bigl((a\tir cb)+(cb\tir a)+(ba)\bigr)\,w.\leqno(7.1)
$$

{\it Proof}.\quad
Let $x_i\in \DESBOT w$, so that $x_{i-1}>x_i$ and
$(ba)\mid_{\textstyle b=x_i}w=1$.
Then $(a\tir cb)\mid_{\textstyle b=x_i}w$ counts the 
letters~$x_j$, less than $x_i$, which are to the left of~$x_i$,
while $(cb\tir a)\mid_{\textstyle b=x_i}w$ counts the 
letters~$x_j$, less than~$x_i$, to the right of~$x_i$. Hence,
$\bigl((a\tir cb)+(cb\tir a)+(ba)\bigr)\mid_{\textstyle b=x_i}\,w$
is equal to~$x_i$.\quad\halmos

\medskip
Next, introduce the other classical operation of the dihedral
group, the {\it complement to} $(n+1)$, denoted by~$\bfc$, that
maps each permutation $w=x_1x_2\ldots x_n$ onto
$\bfc\,w:=(n+1-x_1)(n+1-x_2)\cdots (n+1-x_n)$. It is
straightforward to verify the relations:
$(ba\tir c)\,\bfr\,\bfc=(a\tir cb)$,
$(c\tir ba)\,\bfr\,\bfc=(cb\tir a)$,
$(ac\tir b)\,\bfr\,\bfc=(b\tir ac)$, $(ba)\,\bfr\,\bfc=(ba)$. 

As stated in
Theorem~4, the statistic $\rmS6$ is defined by
$$
\leqalignno{
\rmS6&:=(ba\tir c)+(c\tir ba)+(ba)+(ac\tir b),\cr
\noalign{\hbox{so that the statistic $\rmS6\,\bfr\,\bfc$ reads}}
\rmS6\,\bfr\,\bfc&:=(a\tir cb)+(cb\tir a)+(ba) 
+(b\tir ac),\cr
\noalign{\hbox{while the ``mak" statistic defined in (2.9) is}}
\mak&=(a\tir cb)+(cb\tir a)+(ba)+(ca\tir b).\cr}
$$
Taking Lemma 7.1 into account, as well as the definitions of the
word statistics $U$, $V$ given in (2.12)--(2.15), we get the
expressions:
$$
\leqalignno{
\mak,w&=\Sigma\DESBOT w+U_1(w)+\cdots+U_n(w);\cr
\rmS6\,\bfr\,\bfc\,w&=\Sigma\DESBOT w+V_1(w)+\cdots+V_n(w).\cr
}
$$
Now, remember that $\des w$ is the number of elements in
$\DESBOT w$. Therefore, Theorem $4'$ implies the following
corollary.

\proclaim Corollary 7.2. The involution $\bfr\,\bfs$ is an
involution of~${\cal S}_n$ having the property:
$$
(\des,\mak)\,w=(\des, \rmS6\,\bfr\,\bfc)\,w.
$$

But $(\des,\mak)$ is Euler-Mahonian, as proved in [FoZe90].
Therefore, the pair $(\des, \rmS6\,\bfr\,\bfc)$ is 
Euler-Mahonian, as well as $(\des,\rmS6)$, since we always have
$\des \bfr\,\bfc\,w=\des w$. Hence Theorem~4 is proved.

\vglue2cm


\centerline{\bf References}
 
\bigskip
[BaSt00] Eric Babson and Einar Steingr\'\i msson,
Generalized permutation patterns and a classification
of the Mahonian statistics, {\sl S\'em. Loth. Comb. }
[{\tt http://mat.univie.ac.at/$\sim$slc/}]
{\bf 44 }, 2000, B44b, 18~pp.

[Ca54] Leo Carlitz, $q$-Bernoulli and
Eulerian numbers,{\sl Trans. Amer. Math. Soc.},
{\bf 76}, 1954, 332--350.

[Ca59] Leo Carlitz, Eulerian numbers and polynomials, {\sl Math.
Magazine}, {\bf 33}, 1959, 247--260.

[ClFo95] Robert J. Clarke and Dominique Foata,
Eulerian Calculus, II: An Extension
of Han's Fundamental Transformation,
{\sl Europ. J. Combinatorics}, {\bf 16}, 1995, 221--252. 


[FoZe90] Dominique Foata and Doron Zeilberger,
Denert's Permutation Statistic Is Indeed Euler-Mahonian,
{\sl Studies in Appl. Math.}, {\bf 83}, 1990, 31--59.

[Ma15] Percy Alexander MacMahon, {\sl Combinatory
Analysis,} {\rm vol.~1 and~2}. Cambridge, Cambridge Univ. Press,
1915 (Reprinted by Chelsea, New York,
1955).

[Ze00] Doron Zeilberger, The Umbral Transfer Matrix Method:
I. Foundations, {\sl J. Comb. Theory, ser.~A} [Rota Memorial Issue],
{\bf 91}, 2000, 451--463.

 
\bye
 
 
 


