% Word straightening and $q$-Eulerian Calculus 
% Dominique Foata and Guoniu Han 
% 26 Sept. 1998
% 12 Jan.  1999
% Ams-tex, 15 pages.
% make use of the three files conm-p.sty, ams-p.sty and ams-spec.sty



%-----------------------------------------------------------------------------
% Beginning of article.tex
%-----------------------------------------------------------------------------
%
% AMS-TeX 2.1 sample file for proceedings style volumes.
%
\input amstex
%%%%%%%%%%%%%%%%%%%%%\documentstyle{conm-p}



%%% ====================================================================
%%% @AMSTeX-style-file{
%%%   filename  = "conm-p.sty",
%%%   version   = "2.1b",
%%%   date      = "1997/01/07",
%%%   time      = "13:14:07 EST",
%%%   checksum  = "11260 37 136 1230",
%%%   author    = "American Mathematical Society",
%%%   address   = "PO Box 6248, Providence, RI 02940, USA",
%%%   email     = "tech-support@ams.org (Internet)",
%%%   supported = "yes",
%%%   keywords  = "",
%%%   abstract  = "This is an AMSTeX documentstyle containing the specs
%%%                for the Contemporary Math proceedings series that are
%%%                different from those in ams-p.sty.",
%%%   docstring = "The checksum field above contains: CRC-16 checksum,
%%%                number of lines, number of words, and number of
%%%                characters, as produced by Robert Solovay's checksum
%%%                utility.",
%%% }
%%% ====================================================================

%  First input the basic proceedings style

\def\next{AMS-P}
\ifx\styname\next \endinput \else
%%%%%%%%%%%%%%%%%%%%%%\input ams-p.sty

%%% ====================================================================
%%% @AMSTeX-style-file{
%%%   filename  = "ams-p.sty",
%%%   version   = "2.1f",
%%%   date      = "1997/10/02",
%%%   time      = "16:54:44",
%%%   checksum  = "60656 253 743 8387",
%%%   author    = "American Mathematical Society",
%%%   address   = "PO Box 6248, Providence, RI 02940, USA",
%%%   email     = "tech-support@ams.org (Internet)",
%%%   supported = "yes",
%%%   keywords  = "",
%%%   abstract  = "This is an AMSTeX documentstyle. It uses the amsppt
%%%                documentstyle as a base and adds a few refinements
%%%                to give printed documents the visual form used for
%%%                final publication of AMS proceedings articles. There
%%%                are also documentstyles for individual AMS series
%%%                that input this documentstyle and add series-specific
%%%                information (ISSN, series name, etc).",
%%%   docstring = "The checksum field above contains: CRC-16 checksum,
%%%                number of lines, number of words, and number of
%%%                characters, as produced by Robert Solovay's checksum
%%%                utility.",
%%% }
%%% ====================================================================

%    Input the AMS preprint style (checking first to see if
%    it's preloaded).
\def\next{AMSPPT}
\ifx\styname\next \else\input amsppt.sty \relax\fi

%    Then load specs that are shared between ams-m and ams-p.
%%%%%%%%%%%%%%%%%%%%%%%\input ams-spec.sty 

%%% ====================================================================
%%% @AMSTeX-style-file{
%%%   filename  = "ams-spec.sty",
%%%   version   = "2.1f",
%%%   date      = "1997/01/31",
%%%   time      = "21:13:13 EST",
%%%   checksum  = "15755 471 1088 17561",
%%%   author    = "American Mathematical Society",
%%%   address   = "PO Box 6248, Providence, RI 02940, USA",
%%%   email     = "tech-support@ams.org (Internet)",
%%%   supported = "yes",
%%%   keywords  = "",
%%%   abstract  = "This is an AMSTeX documentstyle containing specs
%%%                that are shared in common between ams-m.sty and
%%%                ams-p.sty (for AMS book series, monographs and
%%%                proceedings respectively).",
%%%   docstring = "The checksum field above contains: CRC-16 checksum,
%%%                number of lines, number of words, and number of
%%%                characters, as produced by Robert Solovay's checksum
%%%                utility.",
%%% }
%%% ====================================================================

%    Disallow widows, orphans, and hyphens at the end of a page.

\brokenpenalty=10000
\clubpenalty=10000
\widowpenalty=10000

\catcode`\@=11

%    Dummy definition of \keyboarder, for now [mjd,1995/04/03]
\def\keyboarder#1{}%

%    Page dimensions = 30pc x 50.5pc
\def\pagewidth#1{\hsize#1
  \captionwidth@24pc}

\pagewidth{30pc}

\parindent=18\p@
\normalparindent\parindent

\parskip=\z@

\def\foliofont@{\sevenrm}
\def\headlinefont@{\sevenpoint}

%  Heading styles are different from AMSPPT.STY:

\def\specialheadfont@{\elevenpoint\smc}
\def\headfont@{\bf}
\def\subheadfont@{\bf}
\def\refsheadfont@{\bf}
\def\abstractfont@{\smc}
\def\proclaimheadfont@{\smc}
\def\xcaheadfont@{\smc}
\def\captionfont@{\smc}
\def\citefont@{\bf}
\def\refsfont@{\eightpoint}

\font\sixsy=cmsy6

%    Added \msbfam and \eufmfam to all additional sizes so that \Bbb
%    and \frak can be used in titles, running heads.  [bnb, 1996/05/07]

%    Twelvepoint (12/14) used for titles
\font@\twelverm=cmr10 scaled \magstep1
\font@\twelvebf=cmbx10 scaled \magstep1
\font@\twelveit=cmti10 scaled \magstep1
\font@\twelvesl=cmsl10 scaled \magstep1
\font@\twelvesmc=cmcsc10 scaled \magstep1
\font@\twelvett=cmtt10 scaled \magstep1
\font@\twelvei=cmmi10 scaled \magstep1
\font@\twelvesy=cmsy10 scaled \magstep1
\font@\twelveex=cmex10 scaled \magstep1
\font@\twelvemsb=msbm10 scaled \magstep1
\font@\twelveeufm=eufm10 scaled \magstep1

\newtoks\twelvepoint@
\def\twelvepoint{\normalbaselineskip14\p@
  \abovedisplayskip12\p@ plus3\p@ minus9\p@
  \belowdisplayskip\abovedisplayskip
  \abovedisplayshortskip\z@ plus3\p@
  \belowdisplayshortskip7\p@ plus3\p@ minus4\p@
  \textonlyfont@\rm\twelverm \textonlyfont@\it\twelveit
  \textonlyfont@\sl\twelvesl \textonlyfont@\bf\twelvebf
  \textonlyfont@\smc\twelvesmc \textonlyfont@\tt\twelvett
  \ifsyntax@ \def\big##1{{\hbox{$\left##1\right.$}}}%
    \let\Big\big \let\bigg\big \let\Bigg\big
  \else
    \textfont\z@\twelverm  \scriptfont\z@\eightrm
       \scriptscriptfont\z@\sixrm
    \textfont\@ne\twelvei  \scriptfont\@ne\eighti
       \scriptscriptfont\@ne\sixi
    \textfont\tw@\twelvesy \scriptfont\tw@\eightsy
       \scriptscriptfont\tw@\sixsy
    \textfont\thr@@\twelveex \scriptfont\thr@@\eightex
        \scriptscriptfont\thr@@\eightex
    \textfont\itfam\twelveit \scriptfont\itfam\eightit
        \scriptscriptfont\itfam\eightit
    \textfont\bffam\twelvebf \scriptfont\bffam\eightbf
        \scriptscriptfont\bffam\sixbf
    \textfont\msbfam\twelvemsb \scriptfont\msbfam\eightmsb
        \scriptscriptfont\msbfam\sixmsb
    \textfont\eufmfam\twelveeufm \scriptfont\eufmfam\eighteufm
        \scriptscriptfont\eufmfam\sixeufm
    \setbox\strutbox\hbox{\vrule height8.5\p@ depth3.5\p@ width\z@}%
    \setbox\strutbox@\hbox{\lower.5\normallineskiplimit\vbox{%
        \kern-\normallineskiplimit\copy\strutbox}}%
    \setbox\z@\vbox{\hbox{$($}\kern\z@}\bigsize@1.2\ht\z@
  \fi
  \normalbaselines\rm\dotsspace@1.5mu\ex@.2326ex\jot3\ex@
  \the\twelvepoint@}

%    Elevenpoint (11/13) used for authors in proceedings.
\font@\elevenrm=cmr10 scaled \magstephalf
\font@\elevenbf=cmbx10 scaled \magstephalf
\font@\elevenit=cmti10 scaled \magstephalf
\font@\elevensl=cmsl10 scaled \magstephalf
\font@\elevensmc=cmcsc10 scaled \magstephalf
\font@\eleventt=cmtt10 scaled \magstephalf
\font@\eleveni=cmmi10 scaled \magstephalf
\font@\elevensy=cmsy10 scaled \magstephalf
\font@\elevenex=cmex10 scaled \magstephalf
\font@\elevenmsb=msbm10 scaled \magstephalf
\font@\eleveneufm=eufm10 scaled \magstephalf

\newtoks\elevenpoint@
\def\elevenpoint{\normalbaselineskip13\p@
  \abovedisplayskip12\p@ plus3\p@ minus9\p@
  \belowdisplayskip\abovedisplayskip
  \abovedisplayshortskip\z@ plus3\p@
  \belowdisplayshortskip7\p@ plus3\p@ minus4\p@
  \textonlyfont@\rm\elevenrm \textonlyfont@\it\elevenit
  \textonlyfont@\sl\elevensl \textonlyfont@\bf\elevenbf
  \textonlyfont@\smc\elevensmc \textonlyfont@\tt\eleventt
  \ifsyntax@ \def\big##1{{\hbox{$\left##1\right.$}}}%
    \let\Big\big \let\bigg\big \let\Bigg\big
  \else
    \textfont\z@\elevenrm  \scriptfont\z@\eightrm
       \scriptscriptfont\z@\sixrm
    \textfont\@ne\eleveni  \scriptfont\@ne\eighti
       \scriptscriptfont\@ne\sixi
    \textfont\tw@\elevensy \scriptfont\tw@\eightsy
       \scriptscriptfont\tw@\sixsy
    \textfont\thr@@\elevenex \scriptfont\thr@@\eightex
        \scriptscriptfont\thr@@\eightex
    \textfont\itfam\elevenit \scriptfont\itfam\eightit
        \scriptscriptfont\itfam\eightit
    \textfont\bffam\elevenbf \scriptfont\bffam\eightbf
        \scriptscriptfont\bffam\sixbf
    \textfont\msbfam\elevenmsb \scriptfont\msbfam\eightmsb
        \scriptscriptfont\msbfam\sixmsb
    \textfont\eufmfam\eleveneufm \scriptfont\eufmfam\eighteufm
        \scriptscriptfont\eufmfam\sixeufm
    \setbox\strutbox\hbox{\vrule height8.5\p@ depth3.5\p@ width\z@}%
    \setbox\strutbox@\hbox{\lower.5\normallineskiplimit\vbox{%
        \kern-\normallineskiplimit\copy\strutbox}}%
    \setbox\z@\vbox{\hbox{$($}\kern\z@}\bigsize@1.2\ht\z@
  \fi
  \normalbaselines\rm\dotsspace@1.5mu\ex@.2326ex\jot3\ex@
  \the\elevenpoint@}

\addto\tenpoint{\normalbaselineskip12\p@
 \abovedisplayskip6\p@ plus6\p@ minus0\p@
 \belowdisplayskip6\p@ plus6\p@ minus0\p@
 \abovedisplayshortskip0\p@ plus3\p@ minus0\p@
 \belowdisplayshortskip2\p@ plus3\p@ minus0\p@
 \ifsyntax@
 \else
  \setbox\strutbox\hbox{\vrule height9\p@ depth4\p@ width\z@}%
  \setbox\strutbox@\hbox{\vrule height8\p@ depth3\p@ width\z@}%
 \fi
 \normalbaselines\rm}

%    Add sevenpoint for running heads.
\newtoks\sevenpoint@
\def\sevenpoint{\normalbaselineskip9\p@
 \textonlyfont@\rm\sevenrm \textonlyfont@\it\sevenit
 \textonlyfont@\sl\sevensl \textonlyfont@\bf\sevenbf
 \textonlyfont@\smc\sevensmc \textonlyfont@\tt\seventt
  \textfont\z@\sevenrm \scriptfont\z@\sixrm
       \scriptscriptfont\z@\fiverm
  \textfont\@ne\seveni \scriptfont\@ne\sixi
       \scriptscriptfont\@ne\fivei
  \textfont\tw@\sevensy \scriptfont\tw@\sixsy
       \scriptscriptfont\tw@\fivesy
  \textfont\thr@@\sevenex \scriptfont\thr@@\sevenex
   \scriptscriptfont\thr@@\sevenex
  \textfont\itfam\sevenit \scriptfont\itfam\sevenit
   \scriptscriptfont\itfam\sevenit
  \textfont\bffam\sevenbf \scriptfont\bffam\sixbf
   \scriptscriptfont\bffam\fivebf
  \textfont\msbfam\sevenmsb \scriptfont\msbfam\sixmsb
   \scriptscriptfont\msbfam\fivemsb
  \textfont\eufmfam\seveneufm \scriptfont\eufmfam\sixeufm
   \scriptscriptfont\eufmfam\fiveeufm
 \setbox\strutbox\hbox{\vrule height7\p@ depth3\p@ width\z@}%
 \setbox\strutbox@\hbox{\raise.5\normallineskiplimit\vbox{%
   \kern-\normallineskiplimit\copy\strutbox}}%
 \setbox\z@\vbox{\hbox{$($}\kern\z@}\bigsize@1.2\ht\z@
 \normalbaselines\sevenrm\dotsspace@1.5mu\ex@.2326ex\jot3\ex@
 \the\sevenpoint@}

%    Differences from amsppt.sty:
%    - own skips above and below, not the same as \head
%    - centered, not flush left
\newskip\abovespecheadskip   \abovespecheadskip20\p@ plus8\p@ minus2\p@
\newdimen\belowspecheadskip  \belowspecheadskip6\p@
\outer\def\specialhead{%
  \add@missing\endroster \add@missing\enddefinition
  \add@missing\enddemo \add@missing\endexample
  \add@missing\endproclaim
  \penaltyandskip@{-200}\abovespecheadskip
  \begingroup\interlinepenalty\@M\rightskip\z@ plus\hsize
  \let\\\linebreak
  \specialheadfont@\raggedcenter@\noindent}
\def\endspecialhead{\endgraf\endgroup\nobreak\vskip\belowspecheadskip}

\let\varindent@\indent

\def\num#1{{\rm #1\enspace}}

%    Differences from amsppt.sty:
%    - no \penaltyandskip@ before
\let\subsubhead\relax
\outer\def\subsubhead{%
  \add@missing\endroster \add@missing\enddefinition
  \add@missing\enddemo
  \add@missing\endexample \add@missing\endproclaim
  \let\savedef@\subsubhead \let\subsubhead\relax
  \def\subsubhead##1\endsubsubhead{\restoredef@\subsubhead
      {\def\usualspace{\/{\subsubheadfont@\enspace}}%
    \subsubheadfont@##1\unskip\frills@{.\enspace}}\ignorespaces}%
  \nofrillscheck\subsubhead}

%    Indentation for \proclaim, \demo, etc., are the same as for
%    \subhead, and are taken care of by \varindent.
%    \proclaim head font is small caps, and the text font is italic
%    (not \sl). Vertical space only above proclaim, no added space to
%    other math environments.

\newskip\abstractindent         \abstractindent=3pc
\long\def\block #1\endblock{\vskip 6pt
        {\leftskip=\abstractindent \rightskip=\abstractindent
        \noindent #1\endgraf}\vskip 6pt}

\long\def\ext #1\endext{\removelastskip\block #1\endblock}

\outer\def\xca{\let\savedef@\xca \let\xca\relax
  \add@missing\endproclaim \add@missing\endroster
  \add@missing\endxca \envir@stack\endxca
  \def\xca##1{\restoredef@\xca
    \penaltyandskip@{-100}\medskipamount
    \bgroup{\def\usualspace{{\xcaheadfont@\enspace}}%
      \varindent@\xcaheadfont@\ignorespaces##1\unskip
      \frills@{.\xcaheadfont@\enspace}}%
      \ignorespaces}%
  \nofrillscheck\xca}
\def\endxca{\egroup\revert@envir\endxca
  \par\medskip}

%    Differences from amsppt.sty:
%    - font is \smc, not \it
%    - good break point before
%    - skip after
\def\remarkheadfont@{\smc}
\def\remark{\let\savedef@\remark \let\remark\relax
  \add@missing\endroster \add@missing\endproclaim
  \envir@stack\endremark
  \def\remark##1{\restoredef@\remark
    \penaltyandskip@{-100}\medskipamount
    {\def\usualspace{{\remarkheadfont@\enspace}}%
     \varindent@\remarkheadfont@\ignorespaces##1\unskip
     \frills@{.\enspace}}\rm
    \ignorespaces}\nofrillscheck\remark}
\def\endremark{\par\revert@envir\endremark\medskip}

%    Differences from amsppt.sty:
%    - square is flush right
\def\qed{\ifhmode\unskip\nobreak\fi\hfill
  \ifmmode\square\else$\m@th\square$\fi}


%%%%%%

%    Expand rosters to three item levels
%    This is identical to code in ams-j.sty except for the width setting
%    of \rosteritemitemitemwd (here "iii"; "ii" in ams-j.sty).
\newdimen\rosteritemsep
\rosteritemsep=.5pc

\newdimen\rosteritemitemwd
\newdimen\rosteritemitemitemwd

\newbox\setwdbox
\setbox\setwdbox\hbox{0.}\rosteritemwd=\wd\setwdbox
\setbox\setwdbox\hbox{0.\hskip.5pc(c)}\rosteritemitemwd=\wd\setwdbox
\setbox\setwdbox\hbox{0.\hskip.5pc(c)\hskip.5pc(iii)}%
  \rosteritemitemitemwd=\wd\setwdbox

%    Differences from amsppt.sty:
%    - adds \itemitem, \itemitemitem
%    - omits \enspace before item label
%    - omits \smallskip following item
\def\roster{%
  \envir@stack\endroster
  \edef\leftskip@{\leftskip\the\leftskip}%
  \relaxnext@
  \rostercount@\z@% Initialize \rostercount@ to 0.
  \def\item{\FN@\rosteritem@}%
  \def\itemitem{\FN@\rosteritemitem@}%
  \def\itemitemitem{\FN@\rosteritemitemitem@}%
  \DN@{\ifx\next\runinitem\let\next@\nextii@
    \else\let\next@\nextiii@
    \fi\next@}%
  \DNii@\runinitem% If \runinitem occurs, \nextii@ must kill it off.
    {\unskip% This unskips any space before the original \roster.
     \DN@{\ifx\next[\let\next@\nextii@
       \else\ifx\next"\let\next@\nextiii@\else\let\next@\nextiv@\fi
       \fi\next@}%
     \DNii@[####1]{\rostercount@####1\relax
       \therosteritem{\number\rostercount@}~\ignorespaces}%
     \def\nextiii@"####1"{{\rm####1}~\ignorespaces}%
     \def\nextiv@{\therosteritem1\rostercount@\@ne~}%
     \par@\firstitem@false% Before doing any of this we still change
     \FN@\next@}%      End of definition of \nextii@\runinitem.
  \def\nextiii@{\par\par@% End the present paragraph, change \everypar
    \penalty\@m\vskip-\parskip
    \firstitem@true}%
  \FN@\next@}

%    Differences from amsppt.sty:
%    - \leftskip = .5pc, not .5em
\def\rosteritem@{\iffirstitem@\firstitem@false
  \else\par\vskip-\parskip
  \fi
  \leftskip\rosteritemwd \advance\leftskip\normalparindent
  \advance\leftskip.5pc \noindent
  \DNii@[##1]{\rostercount@##1\relax\itembox@}%
  \def\nextiii@"##1"{\def\therosteritem@{\rm##1}\itembox@}%
  \def\nextiv@{\advance\rostercount@\@ne\itembox@}%
  \def\therosteritem@{\therosteritem{\number\rostercount@}}%
  \ifx\next[\let\next@\nextii@
  \else\ifx\next"\let\next@\nextiii@\else\let\next@\nextiv@\fi
  \fi\next@}

%    Differences from amsppt.sty:
%    - \skip after label = .5pc, not \enspace
\def\itembox@{\llap{\hbox to\rosteritemwd{\hss
  \kern\z@ % kern to thwart \unskip in \rom
  \therosteritem@}\hskip.5pc}\ignorespaces}

%    Differences from amsppt.sty:
%    - period after, no parentheses around label
\def\therosteritem#1{\rom{\ignorespaces#1.\unskip}}

%    Two new levels.
\def\rosteritemitem@{\iffirstitem@\firstitem@false
  \else\par\vskip-\parskip
  \fi
  \leftskip\rosteritemitemwd \advance\leftskip\normalparindent
  \advance\leftskip.5pc \noindent
  \DNii@[##1]{\rostercount@##1\relax\itemitembox@}%
  \def\nextiii@"##1"{\def\therosteritemitem@{\rm##1}\itemitembox@}%
  \def\nextiv@{\advance\rostercount@\@ne\itemitembox@}%
  \def\therosteritemitem@{\therosteritemitem{\number\rostercount@}}%
  \ifx\next[\let\next@\nextii@
  \else\ifx\next"\let\next@\nextiii@\else\let\next@\nextiv@\fi
  \fi\next@}

\def\itemitembox@{\llap{\hbox to\rosteritemitemwd{\hss
  \kern\z@ % kern to thwart \unskip in \rom
  \therosteritemitem@}\hskip.5pc}\ignorespaces}

\def\therosteritemitem#1{\rom{(\ignorespaces#1\unskip)}}

\def\rosteritemitemitem@{\iffirstitem@\firstitem@false
  \else\par\vskip-\parskip
  \fi
  \leftskip\rosteritemitemitemwd \advance\leftskip\normalparindent
  \advance\leftskip.5pc \noindent
  \DNii@[##1]{\rostercount@##1\relax\itemitemitembox@}%
  \def\nextiii@"##1"{\def\therosteritemitemitem@{\rm##1}\itemitemitembox@}%
  \def\nextiv@{\advance\rostercount@\@ne\itemitemitembox@}%
  \def\therosteritemitemitem@{\therosteritemitemitem{\number\rostercount@}}%
  \ifx\next[\let\next@\nextii@
  \else\ifx\next"\let\next@\nextiii@\else\let\next@\nextiv@\fi
  \fi\next@}

\def\itemitemitembox@{\llap{\hbox to\rosteritemitemitemwd{\hss
  \kern\z@ % kern to thwart \unskip in \rom
  \therosteritemitemitem@}\hskip.5pc}\ignorespaces}

\def\therosteritemitemitem#1{\rom{(\ignorespaces#1\unskip)}}

\def\endroster{\relaxnext@
  \revert@envir\endroster % restore \envir@end
  \par\leftskip@% End the paragraph, and restore the \leftskip.
  \penalty-50 % \vskip-\parskip% Add a good break
  \DN@{\ifx\next\Runinitem\let\next@\relax
    \else\nextRunin@false\let\item\plainitem@% Otherwise, set
      \ifx\next\par% moreover, if \endroster is followed by \par,
        \DN@\par{\everypar\expandafter{\the\everypartoks@}}%
      \else% but if the \endroster isn't followed by a new paragraph,
        \DN@{\noindent\everypar\expandafter{\the\everypartoks@}}%
      \fi
    \fi\next@}%
  \FN@\next@}

%%%%%%%%%%

%    Differences with amsppt.sty (all address-related items):
%    - break not suppressed before \address
%    - \addressfont@ specified
\def\address#1\endaddress{\global\advance\addresscount@\@ne
  \expandafter\gdef\csname address\number\addresscount@\endcsname
  {\vskip12\p@ minus6\p@\indent\addressfont@\smc\ignorespaces#1\par}}

%  Current addresses as well as permanent ones must be accommodated.
%  Check on the skip before the address; it may be a fixed 6pt.
%  \smallskip has been assumed before the current address, as that
%  is what has been used for \email.

\def\curraddr{\let\savedef@\curraddr
  \def\curraddr##1\endcurraddr{\let\curraddr\savedef@
  \toks@\expandafter\expandafter\expandafter{%
       \csname address\number\addresscount@\endcsname}%
  \toks@@{##1}%
  \expandafter\xdef\csname address\number\addresscount@\endcsname
  {\the\toks@\endgraf\noexpand\nobreak
    \indent\noexpand\addressfont@{\noexpand\rm
    \frills@{{\noexpand\it Current address\noexpand\/}:\space}%
    \def\noexpand\usualspace{\space}\the\toks@@\unskip}}}%
  \nofrillscheck\curraddr}

\def\email{\let\savedef@\email
  \def\email##1\endemail{\let\email\savedef@
  \toks@{\def\usualspace{{\it\enspace}}\endgraf\indent\addressfont@}%
  \toks@@{{\tt ##1}\par}%
  \expandafter\xdef\csname email\number\addresscount@\endcsname
  {\the\toks@\frills@{{\noexpand\it E-mail address\noexpand\/}:%
     \noexpand\enspace}\the\toks@@}}%
  \nofrillscheck\email}


\def\rom#1{{\rm #1}}

%    Differences from amsppt.sty:
%    - rule is 2pc, not 3em
\def\bysame{\by\hbox to2pc{\hrulefill}\thinspace\kern\z@}

%    Differences from amsppt.sty:
%    - indent differs in style B
\def\refstyle#1{\uppercase{%
  \gdef\refstyle@{#1}%
  \if#1A\relax \def\keyformat##1{[##1]\enspace\hfil}%
  \else\if#1B\relax
    \refindentwd2pc
    \def\keyformat##1{\aftergroup\kern
              \aftergroup-\aftergroup\refindentwd}%
  \else\if#1C\relax
%    \refindentwd\parindent
    \def\keyformat##1{\hfil##1.\enspace}%
  \fi\fi\fi}% end of \uppercase
}

\refstyle{A}

%\endinput



\relax

\catcode`\@=11

\def\pretitle{\null\vskip74pt}

\def\addressfont@{\eightpoint}


%    Issue publication info; the same as for journals, for consistency

%    \issueinfo{330}% volume number
%    {2}% issue number
%    {July}% month
%    {1995}% year
%
%    \copyrightinfo{1995}{American Mathematical Society}
%
%    \pagespan{START}{END} % not needed for all journals

\define\issueinfo#1#2#3#4{%
  \def\issuevol@{#1}\def\issueno@{#2}%
  \def\issuemonth@{#3}\def\issueyear@{#4}}

%    For a translation, give the information for the original language
%    publication:
\define\originfo#1#2#3#4{\def\origvol@{#1}\def\origno@{#2}%
  \def\origmonth@{#3}\def\origyear@{#4}}

%    Copyright year is presumably always the same as issue year? But
%    just to be safe, let's allow it to be specified separately. It is
%    probably more natural anyway, from the user's perspective, to give
%    the copyright year in the same command when giving the name of the
%    copyright holder.
\define\copyrightinfo#1#2{\def\copyrightyear{#1}\def\crholder@{#2}}

\define\pagespan#1#2{\pageno=#1\def\start@page{#1}\def\end@page{#2}}

%    Set default values:
\issueinfo{00}{0}{}{1997}
\originfo{00}{0}{}{1997}
\copyrightinfo{\issueyear@}{American Mathematical Society}
\pagespan{000}{000}
\pageno=1 % reset the actual counter to a more sensible value

%    Define a logo for the top of the first page.

\def\nojourlogo{\let\jourlogo\empty@}

\def\journame{AMS Proceedings Style}
\def\volinfo{Volume {\sixbf\issuevol@}, \issueyear@}
\let\jourlogoextra@\empty@
\let\jourlogoright@\empty@

\def\jourlogofont@{\sixrm\baselineskip7\p@\relax}
\def\jourlogo{%
  \vbox to\headlineheight{%
%    Cancel odd parameter settings that might be in effect if the output
%    routine is invoked in the middle of a roster or whatnot.
    \parshape\z@ \leftskip\z@ \rightskip\z@
    \parfillskip\z@ plus1fil\relax
    \jourlogofont@ \frenchspacing
    \line{\vtop{\parindent\z@ \hsize=.5\hsize
%    Leave a hook for something extra at the bottom of the series logo;
%    for book reviews, the copyright line may be inserted here.
      \journame\newline\volinfo\jourlogoextra@\endgraf\vss}%
      \hfil
%    If there is a right-hand side for the series logo (e.g., in
%    translation journals), put it as another \vtop here.
      \jourlogoright@
    }%
    \vss}%
}

\def\flheadline{\jourlogo} \let\frheadline\flheadline

\def\issn#1{\gdef\theissn{#1}}
\issn{0000-0000}

%  The copyright block takes the place of the AMS-TeX logo; otherwise the
%  AMSPPT.STY output routine does what we want.

\def\copyrightline@{%
  \rightline{\sixrm \textfont2=\sixsy \copyright\copyrightyear\ \crholder@}}

\def\logo@{\copyrightline@}

%    \titlefont is 12/14; \twelvepoint defined in ams-spec.sty.
\def\titlefont{%
 \ifsyntax@\else \twelvepoint\bf \fi }

%    \authorfont is 11/13; \elevenpoint defined in ams-spec.sty.
\def\authorfont{%
  \ifsyntax@
  \else \elevenpoint
  \fi}

%    Differences from amsppt.sty:
%    - font is larger size; no need to adjust baselines
%    - not automatically uppercase
\def\title{\let\savedef@\title
  \def\title##1\endtitle{\let\title\savedef@
    \global\setbox\titlebox@\vtop{\titlefont\bf
      \raggedcenter@\frills@{##1}\endgraf}%
    \ifmonograph@
      \edef\next{\the\leftheadtoks}\ifx\next\empty \leftheadtext{##1}\fi
    \fi
    \edef\next{\the\rightheadtoks}\ifx\next\empty \rightheadtext{##1}\fi
  }%
  \nofrillscheck\title}

%    Differences from amsppt.sty:
%    - font specified indirectly as \authorfont
%    - running head text uppercased
\def\author#1\endauthor{\global\setbox\authorbox@
  \vbox{\authorfont\raggedcenter@
    {\ignorespaces#1\endgraf}}\relaxnext@
  \edef\next{\the\leftheadtoks}%
  \ifx\next\empty\expandafter\uppercase{\leftheadtext{#1}}\fi}

%    Differences from amsppt.sty:
%    - \indenti reset to larger value
%    - \abstractfont@ specified indirectly
\def\abstract{\let\savedef@\abstract
  \def\abstract{\let\abstract\savedef@
    \setbox\abstractbox@\vbox\bgroup\indenti=3pc\noindent$$\vbox\bgroup
      \def\envir@end{\endabstract}\advance\hsize-2\indenti
      \def\usualspace{\enspace}\eightpoint \noindent
      \frills@{{\abstractfont@ Abstract.\enspace}}}%
  \nofrillscheck\abstract}

%    Differences from amsppt.sty:
%    - preceding skip is larger
\def\dedicatory #1\enddedicatory{\def\preabstract{{\vskip 20\p@
  \eightpoint\it \raggedcenter@#1\endgraf}}}

%    Differences from amsppt.sty:
%    - no test for monograph
%    - different spacing around author, date, etc.
\outer\def\endtopmatter{\add@missing\endabstract
  \edef\next{\the\leftheadtoks}%
  \ifx\next\empty@
    \expandafter\leftheadtext\expandafter{\the\rightheadtoks}%
  \fi
  \ifx\thesubjclass@\empty@\else \makefootnote@{}{\thesubjclass@}\fi
  \ifx\thekeywords@\empty@\else \makefootnote@{}{\thekeywords@}\fi
  \ifx\thethanks@\empty@\else \makefootnote@{}{\thethanks@}\fi
  \inslogo@
  \pretitle
  \box\titlebox@
  \topskip10pt% reset to normal value
  \preauthor
  \ifvoid\authorbox@\else \vskip16\p@ plus6\p@ minus0\p@\unvbox\authorbox@\fi
  \predate
  \ifx\thedate@\empty\else \vskip6\p@ plus2\p@ minus0\p@
    \line{\hfil\thedate@\hfil}\fi
  \setabstract@
  \nobreak
  \ifvoid\tocbox@\else\vskip1.5pc plus.5pc \unvbox\tocbox@\fi
  \prepaper
  \vskip36\p@\tenpoint
}

\def\setabstract@{%
  \preabstract
  \ifvoid\abstractbox@\else \vskip20\p@ \unvbox\abstractbox@ \fi
}

%  Some patches are needed, to make \yr appear in translation information,
%  and to avoid the spurious unboxing of some empty boxes.


%%%% table of contents

\begingroup
\let\specialhead\relax
\let\head\relax
\let\subhead\relax
\let\subsubhead\relax
\let\title\relax
\let\chapter\relax

%    Differences from amsppt.sty:
%    -  style of roster items; additional item levels
\gdef\setwidest@#1#2{%
   \ifx#1\head\setbox\tocheadbox@\hbox{#2.\enspace}%
   \else\ifx#1\subhead\setbox\tocsubheadbox@\hbox{#2.\enspace}%
   \else\ifx#1\subsubhead\setbox\tocsubheadbox@\hbox{#2.\enspace}%
   \else\ifx#1\key
       \if C\refstyle@ \else\refstyle A\fi
       \setboxz@h{\refsfont@\keyformat{#2}}%
       \refindentwd\wd\z@
   \else\ifx#1\no\refstyle C%
       \setboxz@h{\refsfont@\keyformat{#2}}%
       \refindentwd\wd\z@
   \else\ifx#1\page\setbox\z@\hbox{\quad\bf#2}%
       \pagenumwd\wd\z@
   \else\ifx#1\item
       \setboxz@h{#2}\rosteritemwd=\wd\z@
   \else\ifx#1\itemitem
       \setboxz@h{#2}\rosteritemitemwd=\wd\z@
        \advance\rosteritemitemwd by .5pc
        \advance\rosteritemitemwd by \rosteritemwd
   \else\ifx#1\itemitemitem
       \setboxz@h{#2}\rosteritemitemitemwd=\wd\z@
        \advance\rosteritemitemitemwd by .5pc
        \advance\rosteritemitemitemwd by \rosteritemitemwd
   \else\message{\string\widestnumber\space not defined for this
      option (\string#1)}%
\fi\fi\fi\fi\fi\fi\fi\fi\fi}

\refstyle{A}
\widestnumber\key{M}

\endgroup

\catcode`\@=13

\def\amsversion{2.1f}
%\endinput

\fi

\catcode`\@=11

\def\journame{Contemporary Mathematics}

\issn{0271-4132}

\catcode`\@=13

\def\amsversion{2.1b}
%\endinput







%\NoBlackBoxes

%  The following items provide publication information for the AMS-P logo
\issueinfo{00}% volume number
  {ZZ}% issue number
  {YY}% month
  {XXXX}% year


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

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


\def\exc{\mathop{\text{exc}}\nolimits}
\def\sep{\,|\,}

\def\des{\mathop{\text{des}}\nolimits}
\def\den{\mathop{\text{den}}\nolimits}
\def\excindex{\mathop{\text{excindex}}\nolimits}
\def\maj{\mathop{\text{maj}}\nolimits}
\def\inv{\mathop{\text{inv}}\nolimits}

\def\bfu{{\bold u}}
\def\bfv{{\bold v}}
\def\bfa{{\bold a}}
\def\bfb{{\bold b}}
\def\bfc{{\bold c}}
\def\bfd{{\bold d}}
\def\bfw{{\bold w}}
\def\bfp{{\bold p}}
\def\sortalg{\mathop{\hbox{\eightbf SORT}}\nolimits}


\def\decale#1|{\par\noindent\hskip 28pt\llap{#1}\kern 5pt}


\def\imv{\mathop{\text{imv}}\nolimits}
\def\Exc{\mathop{\text{Exc}}\nolimits}
\def\Nexc{\mathop{\text{Nexc}}\nolimits}
 
\def\Com{\mathop{\text{Com}}\nolimits}
\def\stat{\mathop{\text{stat}}\nolimits}
\def\excindex{\mathop{\text{excindex}}\nolimits}
\def\id{\mathop{\text{id}}\nolimits}

\def\il{\bigl]\kern-.25em\bigl]}
\def\ir{\bigr]\kern-.25em\bigr]}

\def\iil{\bigl>\kern-.25em\bigl>}
\def\iir{\bigr>\kern-.25em\bigr>}


\newbox\rightcrochet
\setbox\rightcrochet=\vbox{\halign{#\hfil\cr
\offinterlineskip
\vrule width 3pt height 0pt depth 1pt\cr
\noalign{\vskip -1pt}
\kern2pt \vrule width 1pt height 10pt depth 0pt\cr
\noalign{\vskip -12pt}
\vrule width 3pt height 0pt depth 1pt\cr
}}

\newbox\leftcrochet
\setbox\leftcrochet=\vbox{\halign{#\hfil\cr
\offinterlineskip
\vrule width 3pt height 0pt depth 1pt\cr
\noalign{\vskip -1pt}
\vrule width 1pt height 10pt depth 0pt\cr
\noalign{\vskip -12pt}
\vrule width 3pt height 0pt depth 1pt\cr
}}

%%% debut de grille

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

\font\tenln    = line10
\font\tenlnw   = linew10

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

\unitlength =1pt

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

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

\newif\if@negarg

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

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


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

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

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

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

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

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

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

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



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


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

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

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

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

%INITIALIZATION
\thinlines

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


\newbox\tbox
\newbox\tboxa

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

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

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

\def\image(#1,#2)#3{\vbox to #1{\offinterlineskip
    \vss #3 \vskip #2}}


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

%%%fin de grille



\topmatter
\title Word straightening and $q$-Eulerian Calculus\endtitle
\author Dominique Foata and Guoniu Han\endauthor
\leftheadtext{DOMINIQUE FOATA AND GUONIU HAN}%
\rightheadtext{Word straightening and $q$-Eulerian Calculus}%


\address 
D\'epartement de math\'ematique,
Universit\'e Louis Pasteur, %\hfil\break
7, rue Ren\'e-Descartes,
F-67084 Strasbourg, France
\endaddress

\email 
foata\@math.u-strasbg.fr
\endemail

\address 
I.R.M.A., Universit\'e Louis Pasteur et {C.N.R.S.}, %\hfil\break
7, rue Ren\'e-Descartes,
F-67084 Strasbourg, France
\endaddress

\email 
guoniu\@math.u-strasbg.fr
\endemail





%  Math Subject Classifications 
\subjclass Primary 05A15, 33A15; Secondary 05A17, 33A75\endsubjclass

\dedicatory This paper is dedicated to Richard Askey for
his great scholarship and his successful savoir-faire in 
promoting the classical theory of Special Functions and making
it accessible and useful to new areas of mathematics.
\enddedicatory

\keywords Straightening algorithm, rearrangements,
permutation statistics, $q$-Eulerian polynomials
\endkeywords

\abstract
This paper contains a new description of the straightening
algorithm for pairs of finite words called circuits. The
commutation rule underlying the straightening algorithm that keeps
invariant a specific word bivariate statistic, is fully
characterized. A methodology is developed that makes possible the
calculation of the bivariate generating function for that pair of
statistics. That generating function appears to be a generalized
form of the classical $q$-Eulerian polynomial. 
\endabstract

\endtopmatter

\document



\head
1. Introduction
\endhead


The present paper has been motivated by a remark of Richard Askey
who asked us to unveil the mysteries hidden in each combinatorial
construction, to fully explain how an intricate
bijection leading to an explicit calculation dealing with
$q$-series was invented or discovered. We should like to try to
match his expectations in this paper by going back to the study of
a problem on multipermutation statistics that has kept several of
us busy in the past eight years. In doing so we have been lucky to
obtain the following new results we will now explain in full
details.

In studying the genus zeta function of local minimal hereditary
orders Denert \cite{9} introduced a new permutation statistic, that
was later christened ``den." When associated with the classical
statistic ``exc," the number of excedances (all those terms will
be fully redefined further in the paper), the generating
function for the pair $(\exc,\den)$ over the symmetric group
${\Cal S}_r$ is equal to the $q$-Eulerian polynomial
\cite{2, 3, 4}, a result proved in \cite{12}. The
definition of ``den" for arbitrary words (with repetitions)
whose letters belong to an alphabet~$X$ was imagined by Han
\cite{14}. He proved that the generating function for the pair
$(\exc,\den)$ over each class of rearrangements of an arbitrary
word was equal to the generalised $q$-Eulerian polynomial, i.e.,
the polynomial denoted by $A_{\bfc,\bfd}(t,q)$ in formula (4.1)
when $\bfd$ is the empty sequence.

When the underlying alphabet $X$ is partitioned into two
subalphabets $S$ of {\it small} letters and $L$ of {\it large}
letters, the statistics ``exc" and ``den" can be further refined to
take large inequalities into account \cite{6, 7, 8}. Those statistics 
are denoted by $\exc_\ell$,
$\den_\ell$. It was proved in \cite{7} that the
generating function for the pair $(\exc_\ell,\den_\ell)$ over each class
$R(\bfc,\bfd)$ was equal to the further generalized $q$-Eulerian
polynomial $A_{\bfc,\bfd}(t,q)$, as it appears in (4.1).

It was not easy to prove those results. In each case a
transformation on words $\Phi$ (resp. $\Phi_\ell$ in the case of a
bi-alphabet) was to be constructed. It maps each rearrangement
class onto itself and has the further property that
$$(\exc,\den)\,w=(\des,\maj)\,\Phi(w)\quad\text{and}\quad
(\exc_\ell,\den_\ell)\,w=(\des_\ell,\maj_\ell)\,\Phi_\ell(w).$$
Here ``des," ``maj," ``$\des_\ell$" and ``$\maj_\ell$" are more
traditional word statistics, namely, the number of descents, the
major index, the number of $\ell$-descents, the $\ell$-major
index, respectively, for which it is more easy to calculate the
generating functions for the pairs $(\des,\maj)$ and
$(\des_\ell,\maj_\ell)$ over each rearrangement class (see, in
particular, \cite{8}). The derivation of the generating functions
for the pairs $(\exc,\den)$ and $(\exc_\ell,\den_\ell)$ is
then a consequence of what is already known for the pairs
$(\des,\maj)$ and $(\des_\ell,\maj_\ell)$ using the
transformations~$\Phi$ (resp.~$\Phi_\ell$).

In \cite{10} it was shown that the following classical
transformations on words, the Cartier-Foata transform
\cite{5}, the transform $\Phi$ itself \cite{14}, as well as its two
extensions derived in \cite{6} and in \cite{7} for $\Phi_\ell$,
could be described by means of a {\it single} algorithm, the {\it
straightening algorithm}. 

\medskip

In the present paper we will again describe the straightening
algorithm (section~2), but we will prove (Theorem~2.1) that it can
be further extended to provide a bijective transformation between
two classes of special pairs of words, the well-factorized
circuits and the well-sorted circuits. 

The straightening algorithm can be constructed for each
commutation rule. Once the statistics ``$\exc_L$" and
``$\den_L$" are introduced (see section~3), it is shown that
there is one and only one commutation rule that preserves the pair
of statistics $(\exc_L,\den_L)$ (Theorem~3.1), making the
construction of the desired straightening algorithm unique.

Section~4 is devoted to the algebra of the generalized
$q$-Eulerian polynomials $A_{\bfc,\bfd}(t,q)$. To show in
particular that $A_{\bfc,\bfd}(t,q)$ is the generating polynomial
for a pair of statistics $(f,g)$ it suffices to construct an
explicit bijection involving finite sequences of integers (see
Criterion~4.1).

To apply Criterion~4.1 successfully for the pairs 
$(\exc_L,\den_L)$ it is essential to find an appropriate partition
of the alphabet~$X$ into small and large letters and further to
derive a total ordering  ``$\preceq$" such that the second
statistic $\den_L$ depend only on the $L$-excedances of each
$\preceq$-well-factorized circuit. Such a partition and such
a total ordering, denoted by $\preceq_\ell$, are characterized
in Section~5. 

Criterion 4.1 is fully applied in section~6 in which we show
that the generating functions for the classes of
$\preceq_\ell$-well-sorted circuits by the pair
$(\exc_\ell,\den_\ell)$ are given by the generalized $q$-Eulerian
polynomials presented in section~4. 

It will be noticed that all our $q$-calculations are made directly
on the pairs $(\exc,\den)$ and
$(\exc_\ell,\den_\ell)$ without any reference to the classical
pairs $(\des,\maj)$ and 
$(\des_\ell,\maj_\ell)$. In section~7 we show how we can construct
a transformation $w\mapsto w'$ having the
property that
$(\des_\ell,\maj_\ell)\,w=(\exc_\ell,\den_\ell)\, w'$.


\head
2. The straightening algorithm
\endhead

The straightening algorithm in question acts on {\it biwords},
defined to be ordered pairs $\alpha=(v,w)$, preferably written as
$$\displaylines{
\alpha=\left(\matrice{v\cr w\cr}\right)=\left(\matrice{ y_1&\ldots
&y_{i-1}&y_i&y_{i+1}&y_{i+2}&\ldots&y_m\cr 
x_1&\ldots&x_{i-1}&x_i&x_{i+1}&x_{i+2}&\ldots&x_m\cr}\right)\cr
\noalign{\hbox{of  words}}
v=y_1\ldots
y_{i-1}y_iy_{i+1}y_{i+2}\ldots y_m, \quad
w=x_1\ldots x_{i-1}x_ix_{i+1}x_{i+2}\ldots x_m,\cr}
$$
of the same length. The letters $x_i$, $y_i$ are taken
from a finite alphabet~$X$ that for convenience we shall take as
the subset $\{1,2,\ldots, r\}$ of the integers, equipped with its
standard ordering. The above integer~$m$ is said to be the {\it
length} of the biword~$\alpha$. When the words~$v$ and $w$ are
rearrangements of each other, i.e., when each of them can be derived
from the other by permuting the letters in some order, we say that
the biword is a {\it circuit}.

The straightening algorithm is completely described once 
a Boolean function $Q(x,y; z,t)$ has been defined on quadruples of
letters. Starting with~$Q$ we define a {\it commutation rule},
$\Com_Q$, that maps each pair $(\alpha,i)$, where $\alpha$ is a
biword and $i$ is an integer less than the length of~$\alpha$, onto a
biword
$$
\alpha'=\Com_Q(\alpha,i)=\left(\matrice{v'\cr w'\cr}\right)=
\left(\matrice{y_1&\ldots&
y_{i-1}&y_{i+1}&y_i&y_{i+2}&\ldots& y_m\cr 
x_1&\ldots
&x_{i-1}&z&t&x_{i+2}&\ldots &x_m\cr}\right),
$$
where
 $z=x_i$ and $t=x_{i+1}$ if
$Q(y_i,y_{i+1};x_i,x_{i+1})$ true; 
$z=x_{i+1}$ and $t=x_i$ if
$Q(y_i,y_{i+1};x_i,x_{i+1})$ false.
Notice that the successive {\it top} letters $y_i$, $y_{i+1}$ always
commute under the action of $\Com_Q$, but not necessarily the
corresponding {\it bottom} letters $x_i$, $x_{i+1}$. Also notice that
$\Com_Q(\alpha,i)$ is a circuit if and only if~$\alpha$ is a circuit.

It is convenient to call {\it pointed biword} each pair
$(\alpha,i)$ where $\alpha$ is a biword of length~$m$ and $1\le i\le
m-1$. Now let
$\alpha'=\Com_Q(\alpha;i)$. If
$1\le j\le\nobreak m-\nobreak 1$, we can form the pointed biword
$(\alpha',j)$ and further apply $\Com_Q$ to
$(\alpha',j)$. We obtain the biword
$\Com_Q(\alpha',j)=\Com_Q(\Com_Q(\alpha,i),j)$, we shall denote by
$\Com_Q(\alpha;i,j)$. By induction it makes sense to define
$\Com_Q(\alpha;i_1,\ldots, i_n)$, where $(i_1,\ldots, i_n)$ is a given
sequence of integers less than~$m$.

As each commutation always permutes two adjacent letters
within the {\it top} word, we
can transform each biword $\alpha={v\choose w}$ into a biword
$\alpha'={v'\choose w'}$ whose top word $v'$ is {\it non-decreasing}
by applying a sequence of commutations. We can also say that for each
biword $\alpha={v\choose w}$ there exists a sequence $(i_1,\ldots,
i_n)$ of integers such that the top word in the resulting biword
$\Com_Q(\alpha;i_1,\ldots,i_n)$ is  non-decreasing. Such a biword is
called a {\it well-sorted} biword. The sequence $(i_1,\ldots,i_n)$
is called a {\it commutation sequence}. We define a particular
commutation sequence $(i_1,\ldots,i_n)$ called {\it minimal} by
the following two conditions:

(i) it is of minimum length;

(ii) it is minimal with respect to the lexicographic order.

\noindent
Clearly the minimal sequence is uniquely defined by those two
conditions and depends only on the top word~$v$ in
$\alpha={v\choose w}$. The minimal biword derived from $\alpha$ by
using the minimal sequence is called the {\it straightening} of the
biword $\alpha$ and will be denoted by $\sortalg_Q(\alpha)$.


\example{Example 1}
Consider the following Boolean function $Q_{CF}$ defined by
$$
Q_{CF}(x,y;z,t) \hbox{\rm\ true, if and only if\ } x=y.
$$
Take 
$\alpha=
\displaystyle{4\,4\,5\,1\,3\,1\,2\,3\,5\choose 6\,5\,4\,3\,3\,2\,1\,1\,1}$;
then $\sortalg_{Q_{CF}}(\alpha)=\displaystyle{1\,1\,2\,3\,3\,4\,4\,5\,5\choose
3\,2\,1\,3\,1\,6\,5\,4\,1}$.
\endexample

The ``CF" subscript stands for ``Cartier-Foata", as those two authors introduced
that commutation in [5]. The present description of $Q_{CF}$ appeared in [10].

Now let $\bfc=(c_1,c_2,\ldots,c_r)$ be a sequence of
$r$ nonnegative integers and consider the nondecreasing
word $y_1y_2\ldots y_m=1^{c_1}2^{c_2}\ldots r^{c_r}$, i.e.,  
$m=c_1+c_2+\cdots+c_r$ and
$y_1=\cdots=y_{c_1}=1$, $y_{c_1+1}=\cdots=y_{c_1+c_2}=2$,
\dots~, $y_{c_1+\cdots+c_{r-1}+1}=\cdots=y_m=r$. The class
of all rearrangements of the word
$y_1y_2\ldots y_m$ will be denoted by $R(\bfc)$.

The set of the {\it circuits} $\alpha={v\choose w}$,
where both words $v$ and $w$ belong to $R(\bfc)$ 
will be denoted by $C(\bfc)$. When $v$ is the nondecreasing word
$1^{c_1}2^{c_2}\ldots r^{c_r}$, we say that the circuit~$\alpha$
is {\it well-sorted}. The subset of all {\it
well-sorted} circuits in $C(\bfc)$ will be denoted by
$S(\bfc)$. To each word $w\in R(\bfc)$
there corresponds a unique well-sorted circuit $\Gamma(w)=
{\overline w\choose w}\in S(\bfc)$, where $\overline w$ denotes the
nondecreasing rearrangement $1^{c_1}2^{c_2}\ldots r^{c_r}$
of~$w$. The natural bijection $\Gamma:R(\bfc)\rightarrow S(\bfc)$
will be one of the ingredients in our derivation.

We consider a second class $F_\preceq(\bfc)$ of circuits, called 
$\preceq$-{\it well-factorized},  that will also be in bijection with
$R(\bfc)$. To this end we suppose given a total order
``$\preceq$" on~$X$, not necessarily identical with the standard
order and make use of the obvious notations: ``$\prec$," ``$\succ$,"
``$\succeq$."  A nonempty word 
$w=x_1x_2x_3\ldots x_m$ is said to be {\it
$\preceq$-domi\-na\-ted}, if $x_1 \succ x_2$, $x_1\succ
x_3$, \dots~, 
$x_1\succ x_{m}$. The {\it right to left cyclic shift} of~$w$ is
defined to be the word $\delta w=x_2x_3\ldots x_{m}x_{1}$. A
circuit of the form $\delta w\choose w$ with $w$
$\preceq$-domi\-na\-ted is called a {\it
$\preceq$-domi\-nated cycle}.


As it is known (see, e.g. \cite{15} (Lemma~10.2.1)) or easily verified,
each word $w$ is the juxtaposition product
$u^1u^2\ldots$ of $\preceq$-domi\-nated words 
whose first letters ${\text{pre}}(u^1)$, ${\text{pre}}(u^2)$, \dots\ are
in nondecreasing order with respect to ``$\preceq$" :
$$
{\text{pre}}(u^1) \preceq {\text{pre}}(u^2)\preceq \cdots{}
\eqno(2.1)
$$
This factorization, called the $\preceq$-{\it
increasing factorization} of~$w$, is unique. 

\goodbreak
Given the $\preceq$-increasing factorization $u^1u^2\ldots$ of a
word~$w$ we can form the
juxtaposition product 
$$
\Delta(w)=\left(\matrice{\delta u^1&\delta u^2&\ldots\cr
 u^1&u^2&\ldots\cr}\right)\eqno(2.2)
$$
of the $\preceq$-domi\-nated cycles.
Clearly $\Delta$ maps each word onto a product of 
$\preceq$-domi\-nated cycles satisfying inequalities
(2.1), in a bijective manner. Such a product, written as a circuit
(2.2), will be called a $\preceq$-{\it well-factorized circuit}.
The set of all $\preceq$-well-factorized circuits in $C(\bfc)$ will
be denoted by $F_\preceq(\bfc)$.

\medskip
\example{Example 2}
Consider the total ordering
$5\prec 4\prec 1\prec 2\prec 3$ of the set
$X=\{1,\ldots,5\}$ and the word
$w=4\,4\,5\,1\,3\,1\,2\,3\,5$. To~$w$ there corresponds
the {\it well-sorted} ciruit
$\Gamma(w)=\left(\matrice{1&1&2&3&3&4&4&5&5\cr
4&4&5&1&3&1&2&3&5\cr}\right)$. On the other hand,
the $\preceq$-increasing factorization of~$w$ reads $4\sep
4\,5\sep1\sep 3\,1\,2\sep 3\,5$, so that the corresponding
$\preceq$-{\it well-factorized} circuit is:
$$
\Delta(w)=\left(\matrice{4\cr
4\cr}\right|\left.\matrice{5&4\cr
4&5\cr}\right|\left.
\matrice{1\cr 1\cr}\right|\left.
\matrice{1&2&3\cr
3&1&2\cr}\right|\left.
\matrice{5&3\cr 3&5\cr}\right).
$$
\endexample

For every~$\bfc$ the two classes $F_\preceq(\bfc)$ and $S(\bfc)$ are
equinumerous. For instance, $\Gamma\Delta^{-1}$ is a bijection
between the two sets. However we want to build a bijection based on
algorithm $\sortalg_Q$ that, in general, maps $F_\preceq(\bfc)$
{\it into} $S(\bfc)$. We then impose a condition on the Boolean
function~$Q$ that will transform the ``into" into an ``onto".  The
restriction of $\sortalg_Q$ to  $F_\preceq(\bfc)$ will be denoted by
$\sortalg_{(\preceq,Q)}$.

\medskip

\definition{Definition}
A Boolean function $Q(x,y;z,t)$ is said to be {\it bi-symmetric} if
it is symmetric in the two sets of parameters $\{x,y\}$ and $\{z,t\}$, i.e.,
$Q(x,y;z,t)=Q(y,x;z,t)$ and $Q(x,y;z,t)=Q(x,y;t,z)$.
\enddefinition

\medskip
It is straightforward to verify that the commutation rule $\Com_Q$
induced by a bi-symmetric Boolean function $Q$ is
involutive, i.e., if $\alpha'=\Com_Q(\alpha;i)$, then 
$\alpha=\Com_Q(\alpha';i)$.

\proclaim{Theorem 2.1}
Let $Q$ be a bi-symmetric four-variable Boolean
function. Then $\sortalg_{(\preceq,Q)}$ is a bijection
of $F_\preceq(\bfc)$ onto $S(\bfc)$.
\endproclaim

\demo{Proof}
The proof is essentially the description of the action of 
$\sortalg_{(\preceq,Q)}$ when it is applied to a well-factorized circuit.
As will be seen, the bi-symmetry property makes each step reversible.
Let $\alpha'=\left(\matrice{ z_1&\ldots
&z_{m-1}\cr 
t_1&\ldots&t_{m-1}\cr}\right)$ be a biword and the
juxtaposition product
$\alpha=\alpha' \displaystyle{z_m\choose t_m}$ be a
$\preceq$-well-factorized circuit in $F_\preceq(\bfc)$. Then the
letter~$z_m$ is necessarily the $\preceq$-greatest letter in the
word $z_1\ldots z_m$ (or in $t_1\ldots t_m$). To avoid cumbersome
notation let
$f:=\sortalg_{(\preceq,Q)}$. By definition of the straightening
algorithm we have
$$
f(\alpha)=f\Bigl(f(\alpha'){z_m\choose t_m}\Bigr).
$$
Now let
$f(\alpha')=\left(\matrice{ z'_1&\ldots
&z'_{m-1}\cr 
x'_1&\ldots&x'_{m-1}\cr}\right)$, so that
$z'_1\le \cdots\le z'_{m-1}$. There is a unique
integer~$i$ such that $1\le i\le m-1$ and $z'_i\le z_m<z'_{i+1}$.
To derive $f(\alpha)$ we only have to move $z_m$ to the left (using
the commutation rule $\Com_Q$) until $z_m$ lies between $z'_i$ and
$z'_{i+1}$. Using the previous notations we then have
$$
f(\alpha)=\Com_Q(f(\alpha'){z_m\choose t_m};m-1,m-2,\ldots,i+1).
$$
Let
$f(\alpha)=\left(\matrice{ y_1&\ldots
&y_{m-1}&y_m\cr 
x_1&\ldots&x_{m-1}&x_m\cr}\right)$, so that
$y_1\le \cdots\le y_{m-1}\le y_m$.
To recover the pair $\Bigl(f(\alpha'), \displaystyle{z_m\choose
t_m}\Bigr)$  from $f(\alpha)$ we only have to locate the
letter which is the rightmost one in $y_1y_2\ldots y_m$
among those which are the $\preceq$-largest. This defines an integer
$i$ without ambiguity. We then define
$$
f(\alpha'){z_m\choose t_m}=
\Com_Q(f(\alpha);i+1, \ldots, m-2,m-1).
$$
As the commutation rule $\Com_Q$ is involutive, this reverse
procedure leads to the initial pair
$(f(\alpha'),\displaystyle{z_m\choose t_m})$.

In the same manner, $f(\alpha')
=f\Bigl(f(\alpha'')\displaystyle{z_{m-1}\choose t_{m-1}}\Bigr)$,
where $\alpha''$ is the biword
$\left(\matrice{ z_1&\ldots
&z_{m-2}\cr 
t_1&\ldots&t_{m-2}\cr}\right)$.
If $z_m=t_m$, then
$z_{m-1}$ is the $\preceq$-greatest letter in $z_1\ldots z_{m-1}$.
If $z_m\not=t_m$, then necessarily $z_{m-1}=t_m$ as $\alpha$ is
$\preceq$-well-factorized. As before, there is a unique sequence of
commutations that bring $z_{m-1}$ to a position where the
resulting top word is nondecreasing. 

Conversely, starting with $f(\alpha')$ we know that the letter on the
top word that must be brought to the right end is the rightmost
letter equal to~$t_m$. We also know that the product of the
commutations involved will give back the pair
$$(f(\alpha''),\displaystyle{z_{m-1}\choose t_{m-1}}),$$ as the
commutation rule is involutive. As each step has a well-defined
reverse step uniquely defined, the mapping
$\sortalg_{(\preceq,Q)}$ is truly bijective.
\qed\enddemo

\head
3. Unicity of the word transformation
\endhead

Our next task is to characterize the transformations 
$\sortalg_{(\preceq,Q)}$ that preserves the pair of statistics
$(\exc_L,\den_L)$ that will be defined shortly. To this end we will
suppose that the alphabet~$X=\{1,2,\ldots,r\}$ is made of two
disjoint sets~$S$ and~$L$ of so-called {\it small} and {\it large}
letters, respectively. Let $s$ (resp. $\ell$) be the cardinality of~$S$
(resp. of~$L$), so that $s+\ell=r$. With respect to the standard
ordering of~$X$ the small letters are not necessarily smaller than
the large ones. The features ``small" and ``large" refer to two
different ways of considering inequalities, as we will explain
below. 

Let $\alpha=\displaystyle{v\choose w}
=\left(\matrice{y_1&y_2&\ldots& y_m\cr
x_1&x_2&\ldots& x_m\cr}\right)$ be a circuit. The {\it number of
$L$-excedances} of~$\alpha$, $\exc_L\alpha$, is defined be the
number of integers~$i$ such that $1\le i\le m$ and either
$x_i>y_i$, or
$x_i=y_i$ and $x_i$ large.

The definition of $\den_L\alpha$ is based on
the notion of {\it cyclic interval} defined as follows. Place the $r$
elements $1, 2, \ldots, r$ of ~$X$ on a circle
counterclockwise. If $x$ is small (resp. large), place a bracket in the
form \quad$\vcenter{\copy\rightcrochet} \kern-13pt \longrightarrow$
(resp. $\quad\vcenter{\copy\leftcrochet} \kern-15pt
\longrightarrow$) on the vertex~$x$. For $x,y\in X$ $(x\not=y)$ the
cyclic interval $\il x,y\ir_L$ is defined to be the subset of all the
elements that lie between~$x$ and~$y$ when the circle is read
counterclockwise. The brackets (in the French notation) indicate if
the ends of the interval are to be included or not. 

Suppose $x<y$. If $x$, $y$ are both small, then
$\il x,y\ir_L=\vcenter{\copy\rightcrochet}\,
x,y\,\vcenter{\copy\rightcrochet}=\{x+1,\ldots,y\}$ (origin excluded
and end included); if $x$ small and $y$ large, then
$\il x,y\ir_L=\vcenter{\copy\rightcrochet}\,
x,y\,\vcenter{\copy\leftcrochet}=\{x+1,\ldots, y-1\}$ (both ends are
excluded); if $x$ large and $y$ small, then $\il
x,y\ir_L=\vcenter{\copy\leftcrochet}\,
x,y\,\vcenter{\copy\rightcrochet}=
\{x,x+1,\ldots ,y-1,y\}$ (both ends are included); if
$x$ and $y$ are both large, then
$\il x,y\ir_L=\vcenter{\copy\leftcrochet}\,
x,y\,\vcenter{\copy\leftcrochet}=
\{x,x+1,\ldots, y-1\}$ (the origin~$x$ included, but the
end~$y$ excluded). Moreover $\il y,x\ir_L=X\setminus
\il x,y\ir_L$. Finally, define $\il x,x\ir_L=\emptyset$ or~$X$
depending on whether $x$ is small or large.

The {\it $L$-Denert statistic},
$\den_L \alpha$, of the circuit~$\alpha$ is defined to be the
number of pairs $(i,j)$ such that $1\le i<j\le m+1$ and $x_i\in \il
x_j,y_j\ir_L$ (by convention $\il x_{m+1},y_{m+1}\ir_L=L$,
the subset of all large letters).
 For each $i=1,2,\ldots,m$ let $p_i$ be
the number of
$j$ such that
$i+1\le j\le m+1$ and $x_i\in \il x_j,y_j\ir_L$. We also have
$\den_L \alpha=p_1+p_2+\cdots+p_m$.
The sequence
$(p_1,p_2,\ldots, p_{m})$ is said to be the $L$-{\it den-coding}
of~$\alpha$ and is denoted by
$\hbox{$L$-den-coding}(\alpha)$. 


\medskip
\example{Example 3}
Take $r=5$ and suppose that 1, 2, 4 are small and 3, 5
are large, so that the brackets on the circle (here a square!) are
displayed as in Fig.~1. There are $s=3$ small letters and $\ell=2$
large letters. In particular the small letter~4 is larger than the
large letter~3 with respect to the standard ordering.

\medskip


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

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

\newbox\cycleSab

\def\crochet{\vrule width1pt height 3pt depth 0pt
\vrule width 10pt height 1pt depth 0pt
\vrule width1pt height 3pt depth 0pt}

\def\crochetdown{\vrule width1pt height 1pt depth 3pt
\vrule width 10pt height 1pt depth 0pt
\vrule width1pt height 1pt depth 3pt}

\setbox\cycleSab=\vbox{\offinterlineskip 
\segment(0,0)\dir(0,-1)\long{30}
\segment(0,0)\dir(1,0)\long{30}
\fleche(30,0)\dir(-1,0)\long{16}
\segment(30,0)\dir(0,-1)\long{30}
\fleche(0,-30)\dir(1,0)\long{21}
\segment(0,-30)\dir(1,0)\long{30}
\centerput(15,-31){$\vcenter{\copy\leftcrochet}$}
\centerput(0,-5){\crochet}
\centerput(-5,-5){$1$}
\centerput(-5,-20){$2$}
\centerput(15,-36){$3$}
\centerput(0,-20){\crochet}
\centerput(30,-5){\crochet}
\centerput(35,-5){$5$}
\centerput(35,-20){$4$}
\centerput(30,-20){\crochetdown}
\fleche(0,0)\dir(0,-1)\long{15}
\fleche(30,-30)\dir(0,1)\long{15}
\centerput(15,-41){Fig. 1}
}


\centerline{\box\cycleSab\hskip30mm}

\vskip 4.5cm
The following circuit~$\alpha$ with letters in~$X$ is
displayed in the first two rows of the matrix. The third row
shows the content of each cyclic interval $\il x_i,y_i\ir_L$ and the
fourth row the $L$-den-coding of~$\alpha$:
$$
\left(\matrice{y_i\cr
x_i\cr
\il x_i,y_i\ir_L\cr
p_i\cr
}\right)
=\left(\matrice{1&1&2&3&3&4&4&5&5\cr
\bold 4&\bold 5&1&\bold 4&1&3&2&3&\bold 5\cr
\{5,1\}&\{5,1\}&\{2\}&\{5,1,2\}&\{2\}
&\{3,4\}&\{3,4\}&\{3,4\}&X\cr
4&3&2&4&1&4&1&2&1\cr}
\right)
$$
and $\il x_{m+1},y_{m+1}\ir_L=L=  \{3,5\}$.
There are four excedences indicated in bold-face, so that
$\exc_L \alpha=4$ and $\den_L \alpha=
4+3+2+4+1+4+1+2+1=22$.
\endexample

\medskip
Our next task is the following: given a subset
$L$ of $X$ of large letters, so that both statistics ``$\exc_L$" and
``$\den_L$" are well-defined, find a  Boolean function~$Q_L$ having
the property that

\medskip
{\narrower\narrower\noindent {\sl
for every circuit $\alpha$ of length~$m$ and every place $i$
$(1\le i\le m-1)$, the following identity holds}
$$
(\exc_L,\den_L)\,\alpha
=(\exc_L,\den_L)\,\Com_{Q_L}(\alpha,i).\eqno(3.1)
$$
}


Suppose that such a Boolean function $Q=Q_L$ exists and consider a
circuit $\alpha$ of length~$m$. Denote
the image of the pointed circuit
$(\alpha,i)$ under the corresponding commutation rule
by $\alpha'=\Com_Q(\alpha,i)$ 
and take again the
notations of  section~2 for the circuits~$\alpha$ and~$\alpha'$. 
If (3.1) holds, it follows from the definitions of
``$\exc_L$" and ``$\den_L$" that
$$\eqalignno{\exc_L \alpha-\exc_L \alpha'
&=\chi(x_i>y_i)+\chi(x_{i+1}>y_{i+1})\cr
&\kern.5cm{}
+\chi(x_i=y_i\ {\text{large}})+\chi(x_{i+1}=y_{i+1}\ {\text{large}})\cr
&\kern1cm{}
-\chi(z>y_{i+1})-\chi(t>y_{i})\cr
&\kern1cm{}
-\chi(z=y_{i+1}\ {\text{large}})-\chi(t=y_{i}\ {\text{large}})\cr
}
$$

$$\eqalignno{
\den_L \alpha-\den_L \alpha'
&=\sum_{1\le h\le i-1}\Bigl(\chi(x_h\in \il x_i,y_i\ir_L)
+\chi(x_h\in \il x_{i+1},y_{i+1}\ir_L )\cr
\noalign{\vskip-12pt}
&\kern2cm{}-\chi(x_h\in \il z,y_{i+1}\ir_L )
-\chi(x_h\in \il t,y_{i}\ir_L )\Bigr)\cr
&\kern1cm{}+\chi(x_i\in \il x_{i+1},y_{i+1}\ir_L )
-\chi(z\in \il t,y_{i}\ir_L ).\cr}
$$
If condition $Q(y_i,y_{i+1},x_i,x_{i+1})$ is true, 
we must have:
%
$$\eqalignno{\exc_L \alpha-\exc_L \alpha'
&=\chi(x_i>y_i)+\chi(x_{i+1}>y_{i+1})\cr
&\kern.5cm{}
+\chi(x_i=y_i\ {\text{large}})+\chi(x_{i+1}=y_{i+1}\ {\text{large}})\cr
&\kern1cm{}
-\chi(x_i>y_{i+1})-\chi(x_{i+1}>y_{i})\cr
&\kern1cm{}
-\chi(x_i=y_{i+1}\ {\text{large}})
-\chi(x_{i+1}=y_{i}\ {\text{large}})&(3.2)\cr
%}
%$$
%$$
%\eqalignno{
\den_L \alpha-\den_L \alpha'
&=\sum_{1\le h\le i-1}\Bigl(\chi(x_h\in \il x_i,y_i\ir_L )
+\chi(x_h\in \il x_{i+1},y_{i+1}\ir_L )\cr
\noalign{\vskip-10pt}
&\kern1.4cm{}-\chi(x_h\in \il x_i,y_{i+1}\ir_L )
-\chi(x_h\in \il x_{i+1},y_{i}\ir_L )\Bigr)\cr
&\kern.5cm{}+\chi(x_i\in \il x_{i+1},y_{i+1}\ir_L )
-\chi(x_i\in \il x_{i+1},y_{i}\ir_L ).&(3.3)\cr}
$$
%
If condition $Q(y_i,y_{i+1},x_i,x_{i+1})$ is false, we must have:
$$\eqalignno{
\exc_L \alpha-\exc_L \alpha'
&=0,&(3.4)\cr
\den_L \alpha-\den_L \alpha'
&=\sum_{1\le h\le i-1}\Bigl(\chi(x_h\in \il x_i,y_i\ir_L )
+\chi(x_h\in \il x_{i+1},y_{i+1}\ir_L )\cr
\noalign{\vskip-5pt}
&\kern1cm{}-\chi(x_h\in \il x_{i+1},y_{i+1}\ir_L )
-\chi(x_h\in \il x_{i},y_{i}\ir_L )\Bigr)\cr
&\kern1cm{}+\chi(x_i\in \il x_{i+1},y_{i+1}\ir_L )
-\chi(x_{i+1}\in \il x_{i},y_{i}\ir_L )\cr
&=\chi(x_i\in \il x_{i+1},y_{i+1}\ir_L )
-\chi(x_{i+1}\in \il x_{i},y_{i}\ir_L ).&(3.5)\cr
}
$$

Now given four elements $x,y,z,t$ of~$X$ we say that
$z,t$ are {\it neighbors} with respect
to $x,y$, if both $z$ and $t$ are in $\il
x,y\ir_L$, or neither in
$\il x,y\ir_L$. Otherwise, $z$ and $t$ are said to be
{\it strangers} with respect to $x,y$.

When expression (3.2) is zero, it is easy to see that
$x_i$ and $x_{i+1}$ are neighbors with respect to
$\il y_i,y_{i+1}\ir_L$. In that case expression (3.3)
is also equal to zero.
On the other hand, when (3.5) is zero, then 
$x_i$ and $x_{i+1}$ must be
strangers with respect to
$\il y_i,y_{i+1}\ir_L$. 
We have then proved the following theorem.

\proclaim{Theorem 3.1}
Let $Q_L$ be the  Boolean function
defined by:
$$
Q_L(x,y,z,t)\ \hbox{\sl true if and only if }
z,t\ \hbox{\sl are neighbors with respect to }
x,y. $$
Then $Q_L$ is the unique Boolean function such that
for every circuit $\alpha$ and every place $i$ the following identity
holds
$$\hbox{\rm $
(\exc_L ,\den_L )\,\alpha
=(\exc_L ,\den_L)\,\Com_{Q_L}(\alpha,i).$}
$$
\endproclaim
The Boolean function $Q_L$ here characterized was first introduced in [10]
under the name of $Q_H$.

Now it is clear that the above four-variable Boolean function~$Q_L$
is bisymmetric. The combination of Theorems 1.1 and 2.1 yields the
following result.

\proclaim{Theorem 3.2}
For every total ordering ``$\preceq$" on the alphabet $X$, for every
subset~$L$ of large letters of~$X$ and every sequence~$\bfc$, the
mapping $\sortalg_{(\preceq,Q_L)}$ is a bijection of
$F_{\preceq}(\bfc)$ onto
$S(\bfc)$ that satisfies
$$\hbox{\rm $
(\exc_L ,\den_L )\,\alpha
=(\exc_L ,\den_L)\,\sortalg_{(\preceq,Q_L)}(\alpha).$}
$$
\endproclaim

\head
4. Generalized $q$-Eulerian polynomials
\endhead


To introduce those polynomials it is convenient to use the
traditional notations of $q$-calculus, first, the $q$-{\it ascending
factorial} 
$$
(a;q)_n:=\cases
1,& \hbox{\text{if\ }} n=0;\cr
(1-a)(1-aq)\ldots (1-aq^{n-1}), &\hbox{\text{if\ }} n\ge 1;\cr
\endcases\
$$
then the $q$-{\it binomial coefficient} (or the Gaussian
polynomial) 
$$
{n\brack k}:=\cases
\displaystyle{ (q;q)_n\over
(q;q)_k\,(q;q)_{n-k}},& \hbox{\text{if\ }} 0\le k\le n;\cr
\noalign{\smallskip}
0,& \text{otherwise}.\cr
\endcases
$$
As before, $r$ will denote a fixed positive integer and $s$,
$\ell$ two nonnegative integers of sum~$r$. Finally, if
$\bfa=(a_1,\ldots,a_m)$ is a sequence of nonnegative integers, we
let $\|\bfa\|$ be the sum $a_1+\cdots+a_m$.

The generalized $q$-Eulerian polynomials $A_{\bfc,\bfd}(t,q)$,
already introduced in \cite{7}, are polynomials in two
variables~$t$,
$q$, indexed by pairs of sequences 
$\bfc=(c_1,\ldots,c_s)$ and
$\bfd=(d_1,\ldots, d_\ell)$ of nonnegative integers. They are
defined by
$$\displaylines{\quad
{1\over (t;q)_{1+\|\bfc\|+\|\bfd\|}}\,A_{\bfc,\bfd}(t,q)
:=\sum_{i\ge 0} t^i {c_1+i\brack i}\cdots {c_s+i\brack i}\hfill\cr
\hfill{}\times
q^{d_1+1\choose 2}{i\brack d_1}\cdots
q^{d_\ell+1\choose 2}{i\brack d_\ell}.\quad (4.1)\cr}
$$

There exist other extensions of $q$-Eulerian polynomials depending
on more parameters, see, e.g. \cite{11}, but the previous polynomials
indexed by pairs of sequences of integers will meet our present
needs.

Now let $u_1,\ldots, u_s$, $v_1,\ldots, v_\ell$ be
commuting variables. For convenience we will use the traditional
notations
$\bfu^\bfc:=u_1^{c_1}\ldots u_s^{c_s}$,
$\bfv^\bfd:=v_1^{d_1}\ldots v_\ell^{d_\ell}$
and
$$
(u_1,\ldots,u_s;q)_i:=(u_1;q)_{i}\cdots (u_s;q)_i.
$$ 
By means of a simple manipulation on $q$-series it is readily
seen that (4.1) is actually equivalent to the following identity
involving the {\it factorial} generating function for
the polynomials $A_{\bfc,\bfd}(t,q)$, namely
$$
\sum_{\bfc,\bfd} A_{\bfc,\bfd}(t,q)\,
{\bfu^\bfc\bfv^\bfd \over (t;q)_{1+\|\bfc\|+\|\bfd\|}}
=\sum_{i\ge 0}t^i
{(-qv_1,\ldots,-qv_\ell;q)_i\over 
(u_1,\ldots,u_s;q)_{i+1}}.\eqno(4.2)
$$
Notice that the summation is over all pairs of
sequences $\bfc=(c_1,\ldots, c_s)$,
$\bfd=(d_1,\ldots, d_\ell)$,
including the null sequence. Also notice the occurrences of
two different subscripts
$i$ and $(i+1)$ in the right-hand side of (4.2) that correspond to
the two types of $q$-binomial coefficients in~(4.1).

To be able to make use of identity (4.1) in combinatorial problems
and especially in the present paper it is essential to express the
$q$-ascending factorials and the $q$-binomial coefficients in terms
of generating functions for finite sequences of integers.
{}From the classial $q$-binomial theorem (see, e.g., \cite{1}, p.~17 or
\cite{13}, \S~1.3) we can easily derive the identities:
$$\eqalignno{
{1\over (t;q)_{1+m}}&=\sum_{i\ge 0} t^i
\sum_{i\ge a_1\ge \cdots \ge a_m\ge 0}
q^{\|{\bfa}\|};&(4.3)\cr
{c+i\brack i}&=\sum_{i\ge a_1\ge \cdots\ge a_c\ge 0}
q^{\|{\bfa}\|};&(4.4)\cr
q^{d+1\choose 2}{i\brack d}&=\sum_{i\ge a_1> \cdots> a_d\ge 1}
q^{\|{\bfa}\|}.&(4.5)\cr}
$$
On the other hand, each polynomial $A_{\bfc,\bfd}(t,q)$ defined  by
identity (4.1) has positive integral coefficients. Moreover, by
multiplying that same identity by $(1-t)$ and making $t=1$ then
$q=1$, the expression  $A_{\bfc,\bfd}(1,1)$ is equal to the
multinomial coefficient
$M(\bfc,\bfd)={c_1+\cdots+c_s+d_1+\cdots+d_\ell
\choose c_1, \ldots, c_s,d_1,\ldots,d_\ell}$. Consequently, if
$F(\bfc,\bfd)$ is a finite set of cardinality $M(\bfc,\bfd)$ and if
$f$, $g$ are two integer-valued statistics defined on
$F(\bfc,\bfd)$, it makes sense to consider the generating
polynomial
$$
A^{f,g}_{F(\bfc,\bfd)}(t,q):=\sum_{\alpha\in F(\bfc,\bfd)}
t^{f(\alpha)}q^{g(\alpha)}.\eqno(4.6)
$$
Now the pair $(f,g)$ has a generating function equal to 
$A_{\bfc,\bfd}(t,q)$ over $F(\bfc,\bfd)$, i.e., the following
identity 
$$
A^{f,g}_{F(\bfc,\bfd)}(t,q)=A_{\bfc,\bfd}(t,q)
$$ 
holds, if identity (4.1) is valid  when 
$A_{\bfc,\bfd}(t,q)$ is replaced by
$A^{f,g}_{F(\bfc,\bfd)}(t,q)$. By using the expansions (4.3)-(4.6)
we can rewrite that condition as
$$
\sum_{(i',\bfa,\alpha)} t^{i'+f(\alpha)}q^{\|\bfa\|+g(\alpha)}
=\sum_{(i,\bfa^{(1)},\ldots,\bfa^{(r)})}
t^iq^{\|\bfa^{(1)}\|+\cdots+\|\bfa^{(r)}\|}.\eqno(4.7)
$$

\noindent
In (4.7) the first sum is over all triples
$(i',\bfa,\alpha)$ such that 
$$
\left\{\quad
\vcenter{\vbox{
\hsize=10.5cm
\parindent=-10pt
$i'$ is a nonnegative integer; 

$\bfa=(a_1,\ldots,a_{\|\bfc\|+\|\bfd\|})$ is a nonincreasing
sequence of nonnegative integers of length
$\|\bfc\|+\|\bfd\|$ satisfying
$i'\ge a_1\ge \cdots\ge a_{\|\bfc\|+\|\bfd\|}\ge 0$;

$\alpha$ is an element of $F(\bfc,\bfd)$. 
}}
\right.\leqno{(4.8)}
$$
The second sum is over all sequences 
$(i,\bfa^{(1)},\ldots,\bfa^{(r)})$, where 
$$
\left\{\quad
\vcenter{\vbox{
\hsize=10.5cm
\parindent=-10pt
$i$ is a nonnegative integer;

each $\bfa^{(j)}$ is a
sequence $\bfa^{(j)}=(a_{j,1},\ldots, a_{1,c_j})$ of integers
satisfying
$i\ge a_{j,1}\ge\cdots \ge a_{j,c_j}\ge 0$
($1\le j\le s$);

each $\bfa^{(s+j)}$  is a sequence
$\bfa^{(s+j)}=(a_{s+j,1},\ldots, a_{s+j,d_j})$ of integers
satisfying $i\ge a_{s+j,1}>\cdots > a_{s+j,d_j}\ge 1$
($1\le j\le \ell$).
}}
\right.\leqno{(4.9)}
$$
We then have the following criterion.

\proclaim{Criterion  4.1}
For the identity
$A^{f,g}_{F(\bfc,\bfd)}(t,q)=A_{\bfc,\bfd}(t,q)$
to hold, it suffices to
build a bijection
$(i',\bfa,\alpha)\mapsto (i,\bfa^{(1)},\ldots,\bfa^{(r)})$
of triples having properties $(4.8)$ onto sequences having
properties $(4.9)$ and satisfying
$$
i'+f(\alpha)=i\quad
{\text{and}}\quad
\|\bfa\|+g(\alpha)=\|\bfa^{(1)}\|+\cdots+\|\bfa^{(r)}\|.
\eqno(4.10)
$$
\endproclaim

\head
5. The well-factorized circuits
\endhead

Take up again the notations of section~3 where the $r$ elements of
the alphabet $X$ have been displayed on a circle. For convenience,
insert a new element, called~$*$, between the maximum letter~$r$
and the minimum~$1$. With this new convention and when $x>y$, we see
that the cyclic interval
$\il x,y\ir_L$ will {\it always} contain~$*$. Actually, 
$\il x,y\ir_L$ is reduced to the singleton $\{*\}$ if and only if
$x=r$, $y=1$, $r$ small and $1$ large. We also see that there is an
$L$-excedance at position~$i$ in the circuit 
$\alpha=\displaystyle{v\choose w}
=\left(\matrice{y_1&y_2&\ldots&y_m\cr 
x_1&x_2&\ldots& x_m\cr}\right)$ 
if and only if the cyclic interval $\il x_i,y_i\ir_L$ contains~$*$.

It is also convenient to introduce the cyclic {\it sequence} 
$\iil x,y\iir_L$ defined, when $x,y\in X$, $x\not=y$, to be the
sequence of the elements of~$X\cup\{*\}$ that occur when reading the
interval $\il x,y\ir_L$ counterclockwise. When $x$ is small (resp.
large), let $\iil x,x\iir_L$ be the empty sequence (resp. the
sequence $(x,x+1,\ldots,x-1)$.) 

For instance, if $x>y$ and if both $x$, $y$ are small, then
$$
\iil x,y\iir_L=(x+1,x+2,\ldots,r,*,1,\ldots, y-1,y),
$$
while if $x<y$ and $x$ is large, but $y$ small, then
$$
\iil x,y\iir_L=(x,x+1,\ldots,y-1,y),
$$
with the convention that $x+1=*$ and $y-1=*$ when $x=r$ and $y=1$.

Using the notion of cyclic sequences we can also say that there is
an $L$-excedance at position~$i$ in the circuit 
$\alpha=\displaystyle{v\choose w}
=\left(\matrice{y_1&y_2&\ldots&y_m\cr 
x_1&x_2&\ldots& x_m\cr}\right)$ 
if and only if the cyclic sequence $\iil x_i,y_i\iir_L$
contains~$*$. 

Now as the words $v$ and $w$ are rearrangements of each
other, there exists a permutation~$\sigma$ of the sequence
$(1,2,\ldots,m)$ such that 
$y_1y_2\ldots y_m
\!=\!
x_{\sigma(1)}x_{\sigma( 2)}\ldots x_{\sigma(m)}$.  
Write $\sigma$  as a product of disjoint cycles:
$$
\sigma=\cdots(a,b,\ldots,z) \cdots 
$$
The juxtaposition product
$W=\iil x_a,y_a\iir_L 
\iil x_b, y_b\iir_L\cdots \iil x_z, y_z\iir_L$ 
is then equal to 
$\iil x_a,x_b\iir_L \cdots \iil x_z,x_a\iir_L$. It is empty
only if
$\displaystyle{x_b\ldots  x_a\choose x_a\ldots x_z}$
is equal to $\displaystyle{r\ldots  r\choose r\ldots r}$
and $r$ is a small letter. Otherwise, $W$ is equal to the sequence
$(x_a+1,\ldots,r,*,1,\ldots,x_a)$ (resp.
$(x_a,\ldots,r,*,1,\ldots,x_a-1))$,
if $x_a$ is small (resp. large),
repeated as many times as there are $L$-exce\-dances in the
circuit
$$
\left(\matrice{y_a& y_b&\ldots&  y_z\cr
x_a&x_b& \ldots & x_z\cr}\right)
=\left(\matrice{x_b&&\ldots&x_z&x_a\cr
x_a&x_b&\ldots&&x_z\cr}\right).
$$
Hence, for every $x\in X$ we have:
$$
\sum_{j\in\{a,b,\ldots ,z\}}
\chi(x\in \ir x_j,y_j\il_L)
=
\sum_{j\in\{a,b,\ldots ,z\}}
\chi(\hbox{$L$-excedance at $j$}).\eqno(5.1)
$$
By summing the above identity over all the cycles of the
permutation~$\sigma$ we deduce that
$$
\sum_{1\le j\le m}
\chi(x\in \ir x_j,y_j\il_L)
=\exc_L\alpha.
$$
Now if $x_1$ is small (resp. large), then the cyclic interval
$\il x_1,y_1\ir_L$ does not contain (resp. contains)
$x_1$. Hence $x_1$ occurs in exactly $\exc_L\alpha$ cyclic
intervals
$\il x_j,y_j\ir_L$ for $j=2,\ldots,m$
and not in  $\il x_{m+1},y_{m+1}\ir_L$
(resp. in exactly $\exc_L\alpha-1$ 
intervals
$\il x_j,y_j\ir_L$ for $j=2,\ldots,m$
and once in  $\il x_{m+1},y_{m+1}\ir_L$).
We have then proved the following proposition.

\proclaim{Proposition 5.1}
Let $(p_1,p_2,\ldots, p_m)$ be the $L$-den-coding of a
circuit~$\alpha$, then $\exc_L\alpha=p_1$.
\endproclaim

Besides the $L$-den-coding of a
circuit $\alpha=\displaystyle
{y_1\ldots y_m\choose x_1\ldots x_m}$ we also introduce
its {\it $L$-exc-coding}, denoted by 
$\hbox{$L$-exc-coding}(\alpha)
=(q_1,q_2,\ldots,q_m)$, where each
$q_i$ is defined to be the number of $L$-excedances in the right
factor
$\displaystyle
{y_i\ldots y_m\choose x_i\ldots x_m}$ of~$\alpha$. In particular,
$p_1=q_1=\exc_L\alpha$. We look for a necessary and sufficient
condition for the $L$-den-coding to be identical with the
$L$-exc-coding. As will be seen in the next section, when this
property holds, the calculation of the distribution of
$(\exc_L,\den_L)$ can easily be made by using Criterion~4.1.

\medskip
When the set $L$ of large letters is the set of the largest letters
in $X$ with respect to the standard ordering, i.e., when
$S=\{1,2,\ldots, s\}$ and $L=\{s+1,s+2,\ldots, r\}$ $(s+\ell=r)$,
we write $S<L$ and we speak of ``$\ell$-den-coding,"
``$\exc_\ell$"  and ``$\den_\ell$" instead of ``$L$-den-coding,"
``$\exc_L$" and ``$\den_L$." (Remember that $\ell$ is the number of
elements in~$L$.)

Next we introduce the following total ordering
$\preceq_\ell$ on~$X$ defined by
$$
r\prec_\ell(r-1)\prec_\ell\cdots\prec_\ell
(s+1)\prec_\ell 1\prec_\ell 2\prec_\ell \cdots \prec_\ell s.
$$

\proclaim{Proposition 5.2}
If $S<L$, then
$$
L\hbox{\rm {-den-coding}}(\alpha)
=L\hbox{\rm -exc-coding}(\alpha)\eqno(5.2)
$$
holds for every $\preceq_\ell$-well-factorized circuit~$\alpha$.
\endproclaim

\demo{Proof}
{}From (5.1) it suffices to prove the property when $\alpha$ is a 
$\preceq_\ell$-dominated cycle 
$\displaystyle
{y_1 y_2\ldots y_m\choose x_1 x_2\ldots x_m}=\displaystyle
{x_2 x_3\ldots x_1\choose x_1 x_2\ldots x_m}$.
Identity (5.2) holds if and only if for every $i=1,\ldots,m$ we
have
$$
\sum_{i+1\le j\le m+1}
\chi(x_i\in \il x_j,y_j\ir_L)
=
\sum_{i\le j\le m} \chi(\hbox{$L$-excedance at $j$}).\eqno{(5.3)}
$$

Let $1\leq i\leq m$.
As we have noticed earlier, the number of $\ell$-excedances in
$$
\alpha'=\left(\matrice{y_i& y_{i+1}&\ldots&  y_m\cr
x_i&x_{i+1}& \ldots & x_m\cr}\right)
=\left(\matrice{x_{i+1}&x_{i+2}&\ldots& x_m &x_1\cr
x_i&x_{i+1}&\ldots&x_{m-1}&x_m\cr}\right)
$$
is equal to the number of occurrences of~$*$ in
the juxtaposition product
$$W':=\iil x_i,x_{i+1}\iir_L \cdots \iil x_{m-1},x_m\iir_L
\iil x_m, x_1\iir_L.$$ 

If $x_i$ is small, then $x_1=y_m$ is also small and $x_1\geq x_i$. 
The product $W'$ is of the form
$$(x_i+1,\ldots,x_1,\ldots,*,\ldots,x_i,\ldots,x_1).$$
In that sequence the number of occurrences of $x_i$ is equal to the number of
occurrences of $*$. 
As $x_i$ does
not occur in 
$\il x_i,y_{i}\ir_L$, identity (5.3) holds.

If $x_i$ is large and $x_1$ is small, then $x_i> x_1$. The product $W'$ is of the form
$$(x_i,\ldots,*,\ldots,x_1, \ldots,x_i, \ldots, *, \ldots, x_1).$$
If $x_i$ and $x_1$ both large, then $x_i\geq x_1$, and $W'$ is of the form
$$(x_i,\ldots,*,\ldots,x_1, \ldots,x_i, \ldots, *, \ldots, x_1-1).$$
In the last two cases the number of occurrences of $x_i$ is still equal to the number of
occurrences of $*$. 
Moreover, $x_i$ {\it occurs} in both $\il x_i,y_i\ir_L$, $\il x_{m+1},y_{m+1}\ir_L$, so that
$$\sum_{i+1\le j\le m+1}
\chi(x_i\in \il x_j,y_j\ir_L) = \sum_{i\le j\le m}
\chi(x_i\in \il x_j,y_j\ir_L), 
$$
and (5.3) also holds.\qed\enddemo

\proclaim{Proposition 5.3}
If there exists a total ordering $\preceq$ such that for every
$\preceq$-well factorized circuit condition $(5.2)$ holds, then $S<L$
and the ordering $\preceq$ is identical with $\preceq_\ell$.
\endproclaim


The four columns in the table below refer to the four particular cases
considered in the proof. For each circuit appearing in the fifth row the excedances
have been indicated in bold-face. The last two rows show the values
of the $L$-den-coding and the $L$-exc-coding of the circuits.

{
\newbox\cyclecaseun
\newbox\cyclecasedeux
\newbox\cyclecasetrois
\newbox\cyclecasequatre

\def\crochet{\vrule width1pt height 3pt depth 0pt
\vrule width 10pt height 1pt depth 0pt
\vrule width1pt height 3pt depth 0pt}

\def\crochetdown{\vrule width1pt height 1pt depth 3pt
\vrule width 10pt height 1pt depth 0pt
\vrule width1pt height 1pt depth 3pt}

\setbox\cyclecaseun=\vbox{\offinterlineskip
\segment(0,0)\dir(0,-1)\long{10}
\segment(0,0)\dir(1,0)\long{10}
\segment(10,0)\dir(0,-1)\long{10}
\segment(0,-10)\dir(1,0)\long{10}
\centerput(0,-5){\crochetdown}
\centerput(-4,-6){$x$}
\centerput(14,-6){$y$}
\centerput(10,-5){\crochetdown}
}

\setbox\cyclecasedeux=\vbox{\offinterlineskip
\segment(0,0)\dir(0,-1)\long{10}
\segment(0,0)\dir(1,0)\long{10}
\segment(10,0)\dir(0,-1)\long{10}
\segment(0,-10)\dir(1,0)\long{10}
\centerput(0,-5){\crochetdown}
\centerput(-4,-6){$x$}
\centerput(14,-6){$y$}
\centerput(10,-5){\crochetdown}
}

\setbox\cyclecasetrois=\vbox{\offinterlineskip
\segment(0,0)\dir(0,-1)\long{10}
\segment(0,0)\dir(1,0)\long{10}
\segment(10,0)\dir(0,-1)\long{10}
\segment(0,-10)\dir(1,0)\long{10}
\centerput(0,-5){\crochet}
\centerput(-4,-6){$x$}
\centerput(14,-6){$y$}
\centerput(10,-5){\crochetdown}
}

\setbox\cyclecasequatre=\vbox{\offinterlineskip
\segment(0,0)\dir(0,-1)\long{10}
\segment(0,0)\dir(1,0)\long{10}
\segment(10,0)\dir(0,-1)\long{10}
\segment(0,-10)\dir(1,0)\long{10}
\centerput(0,-5){\crochetdown}
\centerput(-4,-6){$y$}
\centerput(14,-6){$x$}
\centerput(10,-5){\crochet}
}
\vskip -10pt
$$\vbox{\offinterlineskip
\halign{\hfil#&\vrule\vrule depth 3pt height 12pt width 0pt
\ \hfil$#$\hfil\  &\vrule\ \hfil$#$\hfil\
&\vrule\ \hfil$#$\hfil\
&\vrule\ \hfil$#$\hfil\ \vrule\cr
\noalign{\hrule}
&{\text {case\ 1}}&{\text {case\ 2}}&{\text {case\ 3}}&{\text
{case\ 4}}\cr
\noalign{\hrule}
&x\in L,\, y\in S, &x\in L,\, y\in S,
&x\in S,\, y\in S,&x\in L,\, y\in L,\cr
&x<y,\,x\prec y&\, x<y,\,x\succ y&x<y,\,y\prec x&x>y,\,y\prec
x\cr
\noalign{\hrule}
&\vrule depth 35pt height 0pt width
0pt
\box\cyclecaseun\qquad\quad
&\box\cyclecasedeux\qquad \quad
& \box\cyclecasetrois\qquad\quad
&\box\cyclecasequatre\qquad\quad\cr
\noalign{\hrule}
&\il x,y\ir_L=\{x,y\}&\il x,y\ir_L=\{x,y\}&\il x,y\ir_L=\{y\}
&\il x,y\ir_L=\{x\}\cr
&\vrule depth 8pt height 12pt width 0pt
\il y,x\ir_L=\emptyset&\il y,x\ir_L=\emptyset&\il y,x\ir_L=\{x\}
&\il y,x\ir_L=\{y\}\cr
\noalign{\hrule}
&\vbox{\offinterlineskip
\halign{\vrule depth 3pt height 12pt width 0pt
\ \hfil$#$\hfil\ &\ \hfil$#$\hfil\ &\ \hfil$#$\hfil\ \cr
x&y\cr
\noalign{\vskip-8pt}
\kern-12pt\bigl(&\kern12pt\bigr)\cr
\noalign{\vskip-8pt}
{\bold y}&x\cr
\emptyset&\{x,y\}&\{x\}\cr}}
&\vbox{\offinterlineskip
\halign{\vrule depth 5pt height 10pt width 0pt
\ \hfil$#$\hfil\ &\ \hfil$#$\hfil\ &\ \hfil$#$\hfil\ \cr
y&\kern-8pt x\cr
\noalign{\vskip-8pt}
\kern-12pt\bigl(&\kern8pt\bigr)\cr
\noalign{\vskip-8pt}
x&\kern-8pt {\bold y}\cr
\{x,y\}&\kern-8pt\emptyset&\kern-8pt\{x\}\cr}}
&\vbox{\offinterlineskip
\halign{\vrule depth 3pt height 12pt width 0pt
\ \hfil$#$\hfil\ &\ \hfil$#$\hfil\ &\ \hfil$#$\hfil\ \cr
y&x\cr
\noalign{\vskip-8pt}
\kern-12pt\bigl(&\kern12pt\bigr)\cr
\noalign{\vskip-8pt}
x&{\bold y}\cr
\{y\}&\{x\}&\emptyset\cr}}
&\vbox{\offinterlineskip
\halign{\vrule depth 3pt height 12pt width 0pt
\ \hfil$#$\hfil\ &\ \hfil$#$\hfil\ &\ \hfil$#$\hfil\ \cr
y&x\cr
\noalign{\vskip-8pt}
\kern-12pt\bigl(&\kern12pt\bigr)\cr
\noalign{\vskip-8pt}
{\bold x}&y\cr
\{x\}&\{y\}&\{x,y\}\cr}}\cr
\noalign{\hrule}
&\kern-45pt
\qquad 1\qquad 1\
&\kern-13pt 1\qquad 0&\kern-15pt 1\qquad 0&\kern-30pt
1\qquad 1\cr
\noalign{\hrule}
&\kern-45pt
\qquad 1\qquad 0\
&\kern-13pt 1\qquad 1&\kern-15pt 1\qquad 1&\kern-30pt
1\qquad 0\cr
\noalign{\hrule}
}}
$$
}

\demo{Proof}
If $S<L$ does not hold, there exists a pair $(x,y)$ of
letters such that $x<y$ with $x$ large and $y$ small. If $x\prec
y$ (case 1), then for the $\preceq$-well-factorized circuit
$\alpha={x\,y\choose y\,x}$ we have
$\hbox{$L$-den-coding}(\alpha)=(1,1)\not=(1,0)
=\hbox{$L$-exc-coding}(\alpha)$, while if $y\prec x$ (case 2) by taking the
$\preceq$-well-factorized circuit
$\alpha={y\,x\choose x\,y}$ we get
$\hbox{$L$-den-coding}(\alpha)=(1,0)\not=(1,1)
=\hbox{$L$-exc-coding}(\alpha)$.


Now suppose $S<L$ and $\preceq \not= \preceq_\ell$.  
There exists a pair $(x,y)$ such that 
$y\prec x$ and $x\prec_\ell y$ and $x,y$ are either
both small, or both large.
Consider the $\preceq$-well-factorized
circuit ${y\,x\choose x\,y}$.
If $x,y$ are both small, then $x<y$ (case 3).  Its $L$-den-coding is $(1,0)$, while its
$L$-exc-coding is $(1,1)$.
If $x,y$ are both large, then  $x>y$ (case 4). Its $L$-den-coding is $(1,1)$, while its
$L$-exc-coding is $(1,0)$. See the explicit calculations of the 
$L$-den-coding and $L$-exc-coding in the preceding table.\qed
\enddemo


\head
6. A $q$-calculation
\endhead

When $S<L$ holds, we will adopt a new notation for
the classes of the rearrangements of a given word. Let
${\bfc}=(c_1,\ldots,c_s)$ and ${\bfd}=(d_1,\ldots,d_\ell)$ be two
vectors with non negative integer components. The
class of all  rearrangements of the  word
$1^{c_1}\ldots s^{c_s}(s+1)^{d_1}\ldots r^{d_l}$ 
will be denoted by $R({\bfc},{\bfd})$. Also $C(\bfc,\bfd)$
(resp. $S(\bfc,\bfd)$, resp. $F_{\preceq_\ell}(\bfc,\bfd)$)
will denote the set of all circuits $\alpha={v\choose w}$
(resp. the subset of well-sorted circuits, resp. the subset of
$\preceq_\ell$-well-factorized circuits) with $v$ and $w$ in
$R(\bfc,\bfd)$.

\medskip
Let $A^{\exc_\ell,\den_\ell}_{F_{\preceq_\ell}(\bfc,\bfd)}(t,q)$ be
the generating function for the set
$F_{\preceq_\ell}(\bfc,\bfd)$ by the pair $(\exc_\ell,\den_\ell)$,
i.e.,
$$
A^{\exc_\ell,\den_\ell}_{F_{\preceq_\ell}(\bfc,\bfd)}(t,q)
=\sum_\alpha
t^{\exc_\ell\alpha} q^{\den_\ell
\alpha}\quad
(\alpha\in F_{\preceq_\ell}(\bfc,\bfd)).
$$

\proclaim{Theorem 6.1}
For each pair $(\bfc,\bfd)$ we have
$$
A^{\exc_\ell,\den_\ell}_{F_{\preceq_\ell}(\bfc,\bfd)}(t,q)
=A_{\bfc,\bfd}(t,q),
$$
where $A_{\bfc,\bfd}(t,q)$ is the generalized $q$-Eulerian
polynomial defined in $(4.1)$.
\endproclaim

\demo{Proof}
We will make use of Criterion 4.1 with $F(\bfc,\bfd)$ replaced by
$F_{\preceq_\ell}(\bfc,\bfd)$, $f$ by $\exc_\ell$ and $g$ by
$\den_\ell$. On the other hand, keep the same notations as in
(4.8) and (4.9) and take
$\alpha=\displaystyle {y_1\ldots y_m\choose x_1\ldots x_m}$ in
$F_{\preceq_\ell}(\bfc,\bfd)$. Let $\bfp=(p_1,\ldots,p_m)$ be its
$\ell$-den-coding which is also its $\ell$-exc-coding. In
particular, $p_1=\exc_\ell\alpha$ and the sequence
$\bfp$ is nonincreasing, as well as
$\bfb=(b_1,\ldots,b_m)=\bfa+\bfp$.

The construction of the bijection $(i',\bfa,\alpha)\mapsto
(i,\bfa^{(1)},\ldots,\bfa^{(r)})$ can be described as follows.
Consider the biword
$
\left(\matrice{x_1&x_2&\ldots&x_m\cr
b_1&b_2&\ldots&b_m\cr}\right)
$
to which we apply $\sortalg_{Q_{CF}}$ (see Example 1). Let 
$(z_1,z_2,\ldots, z_m)$ be the bottom word of 
$\sortalg_{Q_{CF}}\left(\matrice{x_1&x_2&\ldots&x_m\cr
b_1&b_2&\ldots&b_m\cr}\right)$.
Then define
$i:=i'+p_1$, $\bfa^{(1)}:=(z_1,\ldots,z_{c_1})$,
$\bfa^{(2)}:=(z_{c_1+1},\ldots,z_{c_1+c_2})$, \dots~,
$\bfa^{(r)}:=(z_{m-d_\ell+1},\ldots,z_{m})$.
Then the two relations in (4.10) rewritten as
$$
i=i'+\exc_\ell\alpha,\quad
\|\bfa\|+\den_\ell\alpha=\|\bfa^{(1)}\|+\cdots+\|\bfa^{(r)}\|
$$
hold, as $p_1=\exc_\ell\alpha$ and
$\|\bfa^{(1)}\|+\cdots+\|\bfa^{(r)}\|=\|\bfb\|=\|\bfa\|+\|\bfp\|
=\|\bfa\|+\den_\ell\alpha$.

\medskip
For instance, consider $S=\{1,2,3\}$, $L=\{4,5\}$ and take the
$\preceq_\ell$-well-factorized circuit
$\alpha:=\left(\matrice{v\cr w\cr}\right)=\left(\matrice{4\cr
4\cr}\right|\left.\matrice{5&4\cr
4&5\cr}\right|\left.
\matrice{1\cr 1\cr}\right|\left.
\matrice{1&2&3\cr
3&1&2\cr}\right|\left.
\matrice{5&3\cr 3&5\cr}\right).
$
First we get the $\ell$-den-coding $\bfp=(4,3,3,2,2,1,1,1,1)$. 
Now with $\bfa:=(2,2,1,1,1,1,0,0,0)$ and $i':=3>a_1=2$ we obtain
$\bfb=\bfa+\bfp=(6,5,4,3,3,2,1,1,1)$. 
Then
%
$$\sortalg_{Q_{CF}}{4\,4\,5\,1\,3\,1\,2\,3\,5\choose 6\,5\,4\,3\,3\,2\,1\,1\,1}
={1\,1\,2\,3\,3\,4\,4\,5\,5\choose
3\,2\,1\,3\,1\,6\,5\,4\,1}
$$
%
and $(z_1,\ldots,z_m)=(3,2,1,3,1,6,5,4,1)$. We get $i=i'+\exc_\ell\alpha
=3+4=7$ and
$\bfa^{(1)}=(3,2)$, $\bfa^{(2)}=(1)$, $\bfa^{(3)}=(3,1)$,
$\bfa^{(4)}=(6,5)$, $\bfa^{(5)}=(4,1)$.

\medskip

By construction all the sequences $\bfa^{(j)}$ are nonincreasing.
Moreover, if $x_k$, $x_{k'}$ $(k<k')$ are two occurrences of
the same large letter $s+j$ in the word~$w$, there is necessarily an
$\ell$-excedance in the factor
$\left(\matrice{y_k&\ldots&y_{k'}\cr
x_k&\ldots&x_{k'}\cr}\right)$ of the circuit~$\alpha$, so that all
the sequences $\bfa^{(s+1)}$, \dots~, $\bfa^{(r)}$ are {\it
decreasing}. Finally, if $x_k$ is the rightmost occurrence of a
given large letter $s+j$ in the word~$w$, then the right factor
$\left(\matrice{y_k&\ldots&y_{m}\cr
x_k&\ldots&x_{m}\cr}\right)$ of $ \alpha$ necessarily contains an
$\ell$-excedance, so that all the terms in the sequences
$\bfa^{(s+1)}$, \dots~, $\bfa^{(r)}$ are greater than or equal
to~1.\qed\enddemo

\head
7. The transformations
\endhead

Let $w=x_1x_2\ldots x_m$ be a word in $R(\bfc,\bfd)$. Supposing
$S<L$ form the $\preceq_\ell$-well-factorized circuit
$\alpha=\Delta(w)$ (see section~2). Next apply the transformation
$\sortalg_{(\preceq,Q_L)}$ to~$\alpha$ (see section~3), where
$Q_L$ is the Boolean function derived when $S<L$. {}From
Theorem~3.2 we know that
$$
(\exc_L ,\den_L )\,\alpha
=(\exc_L ,\den_L)\,\sortalg_{(\preceq,Q_L)}(\alpha).\eqno(7.1)
$$
The circuit $\alpha'=\sortalg_{(\preceq,Q_L)}(\alpha)$ is
well-sorted. Using the transformation~$\Gamma$ (see section~2) we
know that to~$\alpha$ there corresponds a unique word
$w'$ in $R(\bfc,\bfd)$ such that $\Gamma(w')=\alpha'$. We then
have the chain
$$
w\mapsto \Delta(w)=\alpha\mapsto 
\sortalg_{(\preceq,Q_L)}(\alpha)=\alpha'
\mapsto \Gamma^{-1}(\alpha')=w'.\eqno(7.2)
$$
Let $w=x_1x_2\ldots x_m$ be a word in $R(\bfc,\bfd)$. The
statistic $\des_\ell w$ (resp. $\maj_\ell w$) is defined (see,
e.g. \cite{7}) as the number (resp. the sum) of the integers~$i$
such that $1\le i\le m$ and either $x_i>x_{i+1}$ or
$x_i=x_{i+1}$ and $x_i$ large (by convention
$x_{m+1}=s$). It is easy to verify that
$$
(\des_\ell,\maj_\ell)\,w=(\exc_\ell,\den_\ell)\,\Delta(w).
\eqno(7.3)
$$
On the other hand, the definitions of the number of
$\ell$-excedances and the $\ell$-Denert statistic for the
words~$w'$ can be taken as
$$
(\exc_\ell,\den_\ell)\,w':=(\exc_\ell,\den_\ell)\,\Gamma(w').
\eqno(5.4)
$$
It then follows that the chain displayed in (7.2) provides a
bijection $w\mapsto w'$ of $R(\bfc,\bfd)$ onto itself having the
property that
$$
(\des_\ell,\maj_\ell)\,w=(\exc_\ell,\den_\ell)\, w'.
\eqno(5.5)
$$

\vfill\eject

\subhead
Acknowledgements
\endsubhead
The authors should like to thank one of the referees for his careful reading of
the paper that improves the tenor of the final version.

\bigskip\bigskip\bigskip

\Refs

\ref\no 1
\by G. E. Andrews
\book The Theory of Partitions
\publ Addison--Wesley (Encyclopedia of Math. and its Appl., vol.~2)
\publaddr Reading
\yr 1976
\endref


\ref\no 2
\by L.  Carlitz
\paper $q$-Bernoulli and Eulerian numbers
\jour Trans. Amer. Math. Soc.
\vol 76
\yr 1954
\pages 332--350
\endref

\ref\no 3
\by L.  Carlitz
\paper Eulerian numbers and polynomials
\jour Math. Magazine
\vol 33
\yr 1959
\pages 247--260
\endref

\ref\no 4
\by L.  Carlitz
\paper A combinatorial property of $q$-Eulerian numbers
\jour Amer. Math. Monthly
\vol 82
\yr 1975
\pages 51--54
\endref

\ref\no 5
\by P. Cartier and D. Foata
\book Probl\`emes combinatoires de permutations et r\'earrangements
\publ Spring\-er-Verlag (Lecture Notes in Math., vol. 85)
\publaddr Berlin
\yr 1969
\endref

\ref\no 6
\by R. J. Clarke and D. Foata
\paper Eulerian Calculus, I: Univariable Statistics
\jour Europ. J. Combinatorics
\vol 15
\yr 1994
\pages 345--362
\endref


\ref\no 7
\by R. J. Clarke and D. Foata
\paper Eulerian Calculus, II: An Extension of Han's Fundamental
Transformation
\jour Europ. J. Combinatorics
\vol 16
\yr 1995
\pages 221--252
\endref

\ref\no 8
\by R. J. Clarke and D. Foata
\paper Eulerian Calculus, III: The Ubiquitous Cauchy Formula
\jour Europ. J. Combinatorics
\vol 16
\yr 1995
\pages 329--355
\endref

\ref\no 9
\by M. Denert
\paper The genus zeta function of
hereditary orders in central simple algebras over global fields
\jour Math. Comp.
\vol 54
\yr 1990
\pages 449--465
\endref

\ref\no {10}
\by D. Foata and G.N. Han
\paper Transformations on Words
\jour J. Algorithms
\vol 28
\yr 1998
\pages 172--191
\endref


\ref\no{11}
\by D. Foata and C. Krattenthaler
\paper Graphical Major Indices, II
\jour S\'eminaire Lotha\-rin\-gien de Combinatoire
({\tt http://cartan.u-strasbg.fr/$\sim$slc}) 
\vol B34k
\yr 1995 
\pages 16 pp
\endref

\ref\no {12}
\by D. Foata and D. Zeilberger
\paper Denert's permutation statistic is indeed Euler-Mahonian
\jour Studies in Appl. Math.
\vol 83
\yr 1990
\pages 31--59
\endref

\ref\no 13
\by G. Gasper and M. Rahman
\book Basic  hypergeometric series
\publ Cambridge Univ. Press (Encyclopedia of Math. and its Appl.,
vol.~35)
\publaddr Cambridge
\yr 1990
\endref

\ref\no 14
\by G. N. Han
\paper Une transformation fondamentale sur les r\'earrangements de mots
\jour Advances in  Math.
\vol 105
\yr 1994
\pages 26--41
\endref

\ref\no 15
\by M. Lothaire
\book Combinatorics on Words
\publ Addison-Wesley (Encyclopedia of Math. and its Appl., vol.~17)
\publaddr Reading, Mass.
\yr 1983
\endref



\endRefs


\enddocument

%-----------------------------------------------------------------------------
% End of article.tex
%-----------------------------------------------------------------------------
