%----------------------------------------------------------------------------
% HANPAPER_no     = 38
% HANPAPER_type   = article 
% PUBPAPER_author = D. Foata, G.-N. Han
% PUBPAPER_title  = Signed words and permutations,~I;\\
%                   A fundamental transformation 
% PUBPAPER_journal= ?? 
% PUBPAPER_year   = 2005
% PUBPAPER_volume = ?? 
% PUBPAPER_pp     = ???--???
% MAKEPAPER_output= ps pdf 
% MAKEPAPER_mpost = no 
% MAKEPAPER_4up   = "-W18cm -H33cm -m30 -b-90"
%----------------------------------------------------------------------------

\input amstex
%\documentstyle{proc}
%%% ====================================================================
%%% @AMSTeX-style-file{
%%%   filename  = "proc.sty",
%%%   version   = "2.1b",
%%%   date      = "1997/01/06",
%%%   time      = "21:21:56 EST",
%%%   checksum  = "38274 37 140 1245",
%%%   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 Proceedings of the AMS that are different
%%%                from those in ams-j.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 journal style
%\def\next{AMS-J}
%\ifx\styname\next \endinput \else \input ams-j.sty\fi
%%% ====================================================================
%%% @AMSTeX-style-file{
%%%   filename  = "ams-j.sty",
%%%   version   = "2.1f",
%%%   date      = "1997/10/02",
%%%   time      = "16:53:20",
%%%   checksum  = "32033 414 1082 14923",
%%%   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 journal articles. There are
%%%                also documentstyles for individual AMS journals that
%%%                input this documentstyle and add journal-specific
%%%                information (ISSN, journal 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

\catcode`\@=11

\indenti=3pc

\font@\fourteenbf=cmbx10 scaled \magstep2

\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\fivemsb
   \scriptscriptfont\msbfam\fivemsb
 \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@}
%  added \msbfam to \sevenpoint so that \Bbb can be used in running heads
%  when they are set to \sevenpoint; bnb, 10Apr96

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

%    Issue publication info

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

%    Publisher Item Identifier (we started using them in journal logos
%    as of January 1997).
\define\PII#1{\def\@PII{#1}}

%    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
\PII{\issn@(\issueyear@)0000-0}

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

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

\def\journame{AMS JOURNAL STYLE}
\def\volinfo{Volume \issuevol@, Number \number\issueno@,
  \issuemonth@\ \issueyear@}
\let\pageinfo\empty@
\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\pageinfo\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\issn@{#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@}

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

\let\thedate@\empty@
\def\date#1\enddate{\gdef\thedate@{%
  \eightpoint Received by the editors \ignorespaces#1\unskip.}}

\let\thededicatory@\empty@
\def\dedicatory #1\enddedicatory{\gdef\thededicatory@{{\vskip10pt
  \eightpoint\it \raggedcenter@#1\endgraf}}}

\def\preabstract{}

\let\thecommby@=\empty@
\def\commby #1\endcommby{\gdef\thecommby@{{\vskip1pc
  \eightpoint \raggedcenter@(Communicated by #1)\endgraf}}}

\def\title{\let\savedef@\title
  \def\title##1\endtitle{\let\title\savedef@
% Save the title text for later use (e.g., table of contents).
% Can't use a box for this purpose. [mjd,1996/10/10]
    \def\thetitle@{##1}%
    \global\setbox\titlebox@\vtop{\tenpoint\bf
      \raggedcenter@
      \frills@\uppercasetext@{##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}

\def\author#1\endauthor{%
% Save the argument for later use (e.g., table of contents)
  \def\theauthor@{#1}%
  \global\setbox\authorbox@
  \vbox{\eightpoint\raggedcenter@
    \uppercasetext@{#1}\endgraf}\relaxnext@
  \edef\next{\the\leftheadtoks}\ifx\next\empty@\leftheadtext{#1}\fi}


%    Add \commby to the topmatter
\outer\def\endtopmatter{\add@missing\endabstract
  \edef\next{\the\leftheadtoks}%
  \ifx\next\empty@
    \expandafter\leftheadtext\expandafter{\the\rightheadtoks}\fi
  \ifx\thedate@\empty@\else \makefootnote@{}{\thedate@}\fi
  \ifx\thesubjclass@\empty@\else \makefootnote@{}{\thesubjclass@}\fi
  \ifx\thekeywords@\empty@\else \makefootnote@{}{\thekeywords@}\fi
  \ifx\thethanks@\empty@\else \makefootnote@{}{\thethanks@}\fi
  \inslogo@
  \pretitle
  \begingroup % to localize variant topskip
    \topskip42pt
    \box\titlebox@
  \endgroup
  \preauthor
  \ifvoid\authorbox@\else \vskip2pc\unvbox\authorbox@\fi
  \ifx\thecommby@\empty@\else \thecommby@\fi
  \ifx\thededicatory@\empty@\else \thededicatory@\fi
  \setabstract@
  \ifvoid\tocbox@\else\vskip1.5pcplus.5pc\unvbox\tocbox@\fi
  \prepaper
  \vskip2pcplus1pc\relax
}

\def\setabstract@{%
  \preabstract
  \ifvoid\abstractbox@\else
       \vskip17ptplus.5pc\unvbox\abstractbox@ \fi
}

%    Difference from amsppt.sty:
%    - takes argument to allow uppercasing, not separate begin/end tags
\def\specialheadfont@{\tenpoint\rm}
\let\specialhead\relax
\outer\def\specialhead#1\endspecialhead{%
  \add@missing\endroster \add@missing\enddefinition
  \add@missing\enddemo \add@missing\endexample
  \add@missing\endproclaim
  \penaltyandskip@{-200}\aboveheadskip
  \begingroup\interlinepenalty\@M\rightskip\z@ plus\hsize
  \let\\\linebreak
  \specialheadfont@\raggedcenter@\noindent
	\uppercase{#1}\endgraf\endgroup\nobreak\vskip\belowheadskip}

%    Difference from amsppt.sty:
%    - adds \varindent@
\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
    \penaltyandskip@{-50}\subsubheadskip
    {\def\usualspace{\/{\subsubheadfont@\enspace}}%
     \varindent@\subsubheadfont@##1\unskip\frills@{.\enspace}}\ignorespaces}%
  \nofrillscheck\subsubhead}

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

\def\qed{\ifhmode\unskip\nobreak\fi\hfill
  \ifmmode\square\else$\m@th\square$\fi}

\newskip\prexcaskip  \prexcaskip=\medskipamount
\def\xcaheadfont@{\bf}
\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}\prexcaskip
        \bgroup{\def\usualspace{{\xcaheadfont@\enspace}}%
        \varindent@\xcaheadfont@\ignorespaces##1\unskip
        \frills@{.\xcaheadfont@\enspace}}%
        \ignorespaces}%
  \nofrillscheck\xca}
\def\endxca{\egroup\revert@envir\endxca
  \par\medskip}


%    Expand rosters to three item levels
%    This is identical to code in ams-spec.sty except for the width setting
%    of \rosteritemitemitemwd (here "ii"; "iii" in ams-spec.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(ii)}%
  \rosteritemitemitemwd=\wd\setwdbox

%    Differences from amsppt.sty:
%    - adds \itemitem, \itemitemitem
%    - omits \enspace before item label
%    - omits \smallskip following item (\rosterskip@ is place marker)
\let\rosterskip@\empty@
\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\rosterskip@\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@}

\widestnumber\key{99}

\catcode`\@=13

%    Input local initialization file; for the public distribution,
%    this will be minimal, but it provides a hook for incorporation
%    of special fonts and other production details and thus permits
%    the use of the same version of this calling file in both
%    environments.
%\input ams-j.sti
%%% ====================================================================
%%% @AMSTeX-style-file{
%%%   filename  = "ams-j.sti",
%%%   version   = "2.1b",
%%%   date      = "1997/01/31",
%%%   time      = "17:57:05 EST",
%%%   checksum  = "02894 28 127 1087",
%%%   author    = "American Mathematical Society",
%%%   address   = "PO Box 6248, Providence, RI 02940, USA",
%%%   email     = "tech-support@ams.org (Internet)",
%%%   supported = "yes",
%%%   keywords  = "",
%%%   abstract  = "Init file for ams-j.sty.  This version, for public
%%%                distribution, is minimal; it is replaced at AMS by
%%%                another file containing material relevant only for
%%%                AMS inhouse production.",
%%%   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.",
%%% }
%%% ====================================================================


\catcode`\@=11

\catcode`\@=13

\def\amsversion{2.1f}

\catcode`\@=11

\def\journame{PROCEEDINGS OF THE\newline
    AMERICAN MATHEMATICAL SOCIETY}

\issn{0002-9939}

\catcode`\@=13

\def\amsversion{2.1b}
\NoBlackBoxes

\frenchspacing
\issueinfo{00}% volume number
  {0}% issue number
  {Xxxx}% month
  {2005}% year

\def\sep{\,|\,} \def\cond{\,|\,}

\def\rem#1|{\par\medskip
            {{\it #1}.\quad}}

\def\rest#1{\ifinner\setbox1=\hbox{$\textstyle{#1}$}

            \else\setbox1=\hbox{$\displaystyle{#1}$}\fi
            \dimen1=\ht1
            \advance\dimen1 by\dp1
            \divide\dimen1 by 2
            \box1\lower 2pt\hbox{$\left|\vbox to\dimen1{}\right.$}}

\def\des{\mathop{\text{\rm des}}\nolimits}
\def\ides{\mathop{\text{\rm ides}}\nolimits}
\def\inv{\mathop{\text{\rm inv}}\nolimits}
\def\imv{\mathop{\overline{\text{\rm inv}}}\nolimits}
\def\maj{\mathop{\text{\rm maj}}\nolimits}
\def\Iligne{\mathop{\text{\rm Iligne}}\nolimits}
\def\Ligne{\mathop{\text{\rm Ligne}}\nolimits}
\def\imaj{\mathop{\text{\rm imaj}}\nolimits}
\def\sgn{\mathop{\text{\rm sgn}}}
\def\tot{\mathop{\text{\rm tot}}\nolimits}
\def\fmaj{\mathop{\text{\rm fmaj}}\nolimits}
\def\finv{\mathop{\text{\rm finv}}\nolimits}
\def\ifmaj{\mathop{\text{\rm ifmaj}}\nolimits}
\def\fdes{\mathop{\text{\rm fdes}}\nolimits}
\def\ifdes{\mathop{\text{\rm ifdes}}\nolimits}
\def\Lower{\mathop{\text{\rm Lower}}\nolimits}
\def \bfa{{\bold a}}
\def\bfm{{\bold m}}
\def\bfu{{\bold u}}
\def\bfn{{\bold n}}
\def\bfr{{\bold r}}
\def\bfc{{\bold c}}
\def\bfs{{\bold s}}
\def\bfsun{{\bold s}_{\bold 1}}
\def\bfi{{\bold i}}
\def\bfb{{\bold b}}
\def\bfB{{\bold B}}
\def\bfq{{\bold q}}
\def\bfQ{{\bold Q}}
\def\bfJ{{\bold J}}
\def\bfj{{\bold j}}
\def\bfp{{\bold p}}
\def\bft{{\bold t}}

\def\RefAROI{1}
\def\RefABROI{2}
\def\RefBiOIII{3}
\def\RefBiCa{4}
\def\RefBjW{5}
\def\RefBr{6}
\def\RefBo{7}
\def\RefFo{8}
\def\RefFoHa{9}
\def\RefFoSc{10}
\def\RefFkSS{11}
\def\RefFkE{12}
\def\RefGe{13}
\def\RefHu{14}
\def\RefKn{15}
\def\RefLo{16}
\def\RefMacIT{17}
\def\RefMacIF{18}
\def\RefMacSE{19}
\def\RefReTA{20}
\def\RefReTB{21}
\def\RefReTC{22}
\def\RefReFA{23}
\def\RefReFB{24}
\def\RefStST{25}
\def\RefStSS{26}
\def\RefStJ{27}


\topmatter
\title SIGNED WORDS AND PERMUTATIONS,~I; A FUNDAMENTAL TRANSFORMATION\endtitle
\author Dominique Foata and Guo-Niu Han\endauthor

\address Institut Lothaire, 1 rue Murner, F-67000 Strasbourg, France \endaddress
\email foata\@math.u-strasbg.fr \endemail

\address I.R.M.A. UMR 7501, Universit\'e Louis Pasteur et CNRS, 
7 rue Ren\'e-Descartes, F-67084 Strasbourg, France \endaddress
\email guoniu\@math.u-strasbg.fr \endemail

%  Math Subject Classifications
\subjclass Primary 05A15, 05A30, 05E15\endsubjclass

\date March 7, 2005\enddate

\dedicatory This paper is dedicated to the memory of 
Percy Alexander MacMahon.\enddedicatory

\keywords Flag-inversion number, flag-major index, length function, 
signed permutations, signed words
\endkeywords

\abstract
The statistics major index and inversion number, usually
defined on ordinary words, have their counterparts in signed
words, namely the so-called flag-major index and flag-inversion
number. We give the construction of a new transformation on those
signed words that maps the former statistic onto the latter one.
It is proved that the transformation also preserves 
two other set-statistics: the inverse ligne of route and the lower records.
\endabstract

\endtopmatter

\document


\head 1. Introduction\endhead
The {\it second fundamental transformation},
as it was called later on (see [\RefLo], chap.~10 or [\RefKn], ex. 5.1.1.19), 
was described
in these proceedings [\RefFo]. Let
$w=x_1x_2\ldots x_m$ be a (finite) word, whose letters $x_1$,
$x_2$, \dots~, $x_m$  are integers.
The
integer-valued statistics {\it Inversion Number} ``inv" and  {\it
Major Index} ``maj" attached to the word~$w$ are defined by
$$
\leqalignno{
\inv w&:=\sum_{1\le i\le m-1}\;
\sum_{i<j}\chi(x_i>x_j\};&(1.1)\cr
\maj w&:=\sum_{1\le i\le m-1} i\,\chi(x_i>x_{i+1});&(1.2)\cr}
$$
making use
of the $\chi$-notation that maps each
statement~$A$ to the value $\chi(A)=1$
or~$0$
depending on whether $A$ is true or not. 

If $\bfm=(m_1,m_2,\ldots,
m_r)$ is a sequence
of $r$ nonnegative integers, the rearrangement class of
the
nondecreasing word $1^{m_1}2^{m_2}\ldots r^{m_r}$, that is, the
class of
all the words than can be derived from
$1^{m_1}2^{m_2}\ldots r^{m_r}$ by
permutation of the letters,
is denoted by $R_\bfm$.  The second fundamental
transformation,
denoted by~$\Phi$, maps each word~$w$ on another
word
$\Phi(w)$ and has the following properties:

\smallskip
{\parindent=30pt
\roster
\item"(a)"$\maj w=\inv \Phi(w)$;
\item"(b)"$\Phi(w)$ is a rearrangement of~$w$ and the restriction
of~$\Phi$ to each rearrangement class $R_\bfm$ is a bijection
of $R_\bfm$ onto itself.
\endroster
}
%\smallskip

\noindent
Further properties were proved later on by Foata,
Sch\"utzenberger [\RefFoSc] and Bj\"orner, Wachs [\RefBjW], in
particular, when the transformation is restricted to act on
rearrangement classes $R_\bfm$ such that $m_1=\cdots=m_r=1$,
that is, on symmetric groups~${\goth S}_r$.
\goodbreak
\medskip
The purpose of this paper is to construct an analogous transformation not
simply
on words, but on {\it signed words}, so that new equidistribution properties
on
classical statistics, such as the (Coxeter) {\it length function} (see
[\RefBo, p.~9], [\RefHu, p.~12]), defined on the group~$B_n$ of the {\it signed
permutations} can be derived. By {\it signed word} we understand a
word 
$w=x_1x_2\ldots x_m$, whose letters are
positive or negative integers.
If
$\bfm=(m_1,m_2,\ldots, m_r)$ is a sequence of nonnegative integers
such that
$m_1+m_2+\cdots+m_r=m$, let $B_{\bfm}$ be the set of all
rearrangements $w=x_1x_2\ldots x_m$ of the sequence
$1^{m_1}2^{m_2}\ldots r^{m_r}$, with the convention that some
letters $i$  may be replaced by their opposite values
$-i$. For typographical reasons we shall use the notation
$\overline i:=-i$ in the sequel. The class
$B_{\bfm}$ contains
$2^m{m\choose m_1,m_2,\ldots, m_r}$ signed words. When
$m_1=m_2=\cdots=m_r=1$, $m=r$, the class $B_{\bfm}$ is simply the group
$B_m$ of the signed permutations of order~$m$.

Next, the statistics ``inv" and ``maj" must be adapted to signed
words and correspond to classical statistics when applied
to signed permutations. Let
$$\displaylines{\noalign{\vskip-4pt}
(\omega;q)_n:=\cases
1,&\hbox{\text{if\ }} n=0;\cr
(1-\omega)(1-\omega q)\,\ldots\,(1-\omega q^{n-1}),&\hbox{\text{if\ }}
  n\geq 1;\cr\endcases
\cr 
\noalign{\vskip3pt}
\noalign{\hbox{denote the usual $q$-{\it ascending factorial in a
ring element~$\omega$} and}}
\noalign{\vskip3pt}
{m_1+\cdots+m_r\brack m_1,\ldots,m_r}_q
:={(q;q)_{m_1+\cdots+m_r}\over
(q;q)_{m_1}\cdots(q;q)_{m_r}}\cr}
$$
be the $q$-{\it multinomial coefficient}. Back to MacMahon
[\RefMacIT, \RefMacIF, \RefMacSE] it was known that the above
$q$-multinomial coefficient, which is the true $q$-analog of the
cardinality of~$R_\bfm$, was the generating function for the class
$R_\bfm$ by either one of the statistics ``inv" or ``maj."
Consequently, the generating function for~$B_\bfm$ by the new
statistics that are to be introduced on~$B_\bfm$ must be a {\it plausible}
$q$-analog of the cardinality of~$B_\bfm$.
The most natural $q$-analog we can
think of is certainly
$(-q;q)_m{m_1+\cdots+m_r\brack m_1,\ldots,m_r}_q$, that tends
to $2^m{m_1+\cdots+m_r\choose m_1,\ldots,m_r}$ when~$q$
tends to~1. As a substitute for ``inv" we are led to introduce the
following
statistic~``$\finv$," called the {\it flag-inversion number},
which will be
shown to meet our
expectation, that is,
$$
(-q;q)_m{m_1+\cdots+m_r\brack
m_1,\ldots,m_r}_q
=\sum_{w\in B_\bfm}q^{\finv w}.\leqno(1.3)
$$
This identity is easily proved by induction on $r$.
Let $w=x_1x_2\ldots x_m$ be a signed word from
the
class~$B_\bfm$. To define $\finv w$ we use ``inv" defined in
(1.1),
together with
$$\leqalignno{\noalign{\vskip -4pt}
\imv w&:=\sum_{1\le i\le m-1}\;\sum_{i<j}\chi(\overline x_i>x_j)
&(1.4)\cr
\noalign{\vskip -3pt}
\noalign{\hbox{and define}}
\finv w&:=\inv w+\imv w+\sum_{1\le j\le
m}\chi(x_j<0).&(1.5)\cr
\noalign{\vskip -2pt}
}
$$
The salient feature of this definition of~``$\finv$" is the fact
that it does {\it not\/} involve the {\it values} of the letters,
but only the {\it comparisons} between letters, so that it can be
applied to each {\it arbitrary} signed word.
Moreover, the definition of ``finv" is similar to that of ``fmaj" given
below in (1.7).
Finally, its restriction  
to the group~$B_m$ of the {\it signed permutations} is the
traditional {\it length function}:
$$
\rest{\finv}_{B_m}=\ell.\leqno(1.6)
$$
This is easily shown, for instance, by using the formula derived by
Brenti [\RefBr] for the length function $\ell$ over~$B_n$, that reads.
$$
\ell\, w=\inv w+\sum_{1\le j\le m}
|x_j|\,\chi(x_j<0).
$$

Next, the statistic ``maj" is to be replaced by ``fmaj",
the {\it flag-major index}, introduced by Adin and
Roichman~[\RefAROI] for {\it signed permutations}. The latter
authors (see also [\RefABROI]) showed that ``fmaj" was
equidistributed with the length function~$\ell$ over~$B_n$.
Their definition of ``fmaj" can be used {\it verbatim} for signed
{\it words}, as well as their definition of ``$\fdes$." For a
signed word
$w=x_1x_2\ldots x_m$ those definitions read:
$$\leqalignno{
\fmaj w&:=2\maj w+\sum_{1\le j\le m}\chi(x_j<0);&(1.7)\cr
\fdes w&:=2\des w+\chi(x_1<0);&(1.8)\cr}
$$
where ``$\des$" is the usual {\it number of descents}
$\des w:=\sum_i\chi(x_i>x_{i+1})$.
We postpone the construction of our transformation~$\Psi$ on signed words
to the next section. The main purpose of this paper is to prove the
following theorem.

\proclaim{Theorem 1.1} The transformation $\Psi$ constructed
in
section~$2$ has the following properties:
\roster
\item"(a)"$\fmaj
w=\finv \Psi(w)$ for every signed
word~$w$;
\item"(b)"the
restriction of~$\Psi$ to each rearrangement class $B_\bfm$ of
signed words is a bijection of $B_\bfm$ onto itself, so that
``$\fmaj$" and ``$\finv$" are equidistributed over each class
$B_\bfm$.
\endroster
\endproclaim

\rem Definition $1.1$|Let $w=x_1x_2\ldots x_m\in B_{\bfm}$ be a signed
word.  We say that a {\it nonnegative} integer $i$
belongs to the {\it inverse ligne of route},
$\Iligne w$, of $w$, if one of the following two conditions holds:
\roster
\item"(1)"$i=0$, $m_1\geq 1$ and the rightmost letter $x_k$
satisfying $|x_k|=1$ is equal to $\overline 1$;

\item"(2)"$i\geq 1$, $m_{i}=m_{i+1}=1$ and the rightmost letter that
belongs to $\{i, \overline i, i+1, \overline{i+1}\}$ is equal to
$i$ or $\overline{i+1}$.
\endroster
For example, with
$w=\overline 4\,4\,\overline 1\,3\,2\,5\,\overline 5\,6\,\overline 7$
we have: $\Iligne w=\{0,2,6\}$.

\rem Remark|The expression ``line of route" was used by
Foulkes [\RefFkSS,\RefFkE]. We have added the letter ``g" making
up ``ligne of route," thus bringing a slight touch of French. Notice that~0
may or may not belong to the inverse ligne of route. The
{\it ligne of route} of a signed word $w=x_1x_2\ldots x_m$ is
defined to be the {\it set}, denoted by
$\Ligne w$, of all the~$i$'s such that either $1\le i\le m-1$ and
$x_i>x_{i+1}$, or $i=0$ and $x_1<0$. In particular, $\maj
w=\sum\limits_{0\le i\le m-1} i\, \chi(i\in \Ligne w)$. Finally, if $w$
is a {\it signed permutation}, then $\Iligne w=\Ligne w^{-1}$.
For {\it ordinary permutations}, some authors speak of 
{\it descent set} and {\it descent set of the inverse},
instead of ligne of route and inverse ligne of route, respectively.

\proclaim{Theorem 1.2} The transformation $\Psi$ constructed in
section~$2$ preserves the inverse ligne of route:
\roster
\item"(c)"$\Iligne \Psi(w)=\Iligne w$ for every signed word~$w$. 
\endroster
\endproclaim

\rem Definition $1.2$|Let $w=x_1x_2\ldots x_m$ be a signed word
of length~$m$. A letter~$x_i$ is said to be a {\it lower
record} of~$w$, if either $i=m$, or
$1\le i\le m-1$ and $|x_i|<|x_j|$ for all~$j$ such
that $i+1\le j\le m$. When reading  the lower records of~$w$ from
left to right, we get a {\it signed} subword $x_{i_1}x_{i_2}\ldots
x_{i_k}$, called the {\it lower record subword}, denoted
by~$\Lower w$, which has the property that:
$\min_i x_i=|x_{i_1}|<|x_{i_2}|<\cdots <|x_{i_k}|=|x_m|$.
The notion of lower record is classical in the statistical 
literature. In combinatorics the expression 
``strict right-to-left minimum"
is also used.

\medskip
With our previous example
$w=\overline 4\,4\,\overline 1\,3\,2\,5\,\overline 5\,6\,\overline 7$
we get $\Lower w=\overline 1\,2\,\overline 5\,6\,\overline 7$.
 Our third goal is to prove the following result.

\proclaim{Theorem 1.3} The transformation $\Psi$ constructed in
section~$2$ preserves all the
lower records: 
\roster
\item"(d)"$\Lower \Psi(w)=\Lower w$ for every signed word~$w$.
\endroster
\endproclaim

For each signed permutation $w=x_1x_2\ldots x_m$ let
$$\leqalignno{
\ifmaj w&:=2\sum_{1\le j\le m} i\,\chi(j\in \Iligne w)+\sum_{1\le
j\le m}\chi(x_j<0);&(1.11)\cr
\ifdes w&:=2\sum_{1\le j\le m} \chi(j\in \Iligne w)
+\chi(\hbox{$x_i=-1$ for some $i$)}.&(1.12)\cr}
$$
It is immediate to verify that
$$
\finv w=\finv w^{-1},\quad\ifmaj w=\fmaj w^{-1},\quad
\ifdes w=\fdes w^{-1},
$$
where $w^{-1}$ denotes the inverse of the signed permutation $w$
(written as a linear word $w^{-1}=w^{-1}(1)\ldots w^{-1}(m)$).

Let ${\bold i}\,w:=w^{-1}$; then the chain
$${
\def\rightarrowh#1{\smash{\mathop{\hbox to 9mm{\rightarrowfill}} \limits^{\textstyle#1}}}
\matrix
w & \rightarrowh{\bold i} & w_1 & \rightarrowh{\Psi} & w_2 & \rightarrowh{\bold i} & w_3 \cr 
\noalign{\medskip}
\displaystyle{\fdes\choose\ifmaj} &&
\displaystyle{\ifdes\choose\fmaj} &&
\displaystyle{\ifdes\choose\finv} &&
\displaystyle{\fdes\choose\finv}\cr
\endmatrix
}
$$
shows that the four generating polynomials\quad
$\sum t^{\fdes w}q^{\ifmaj w}$,\quad
$\sum t^{\ifdes w}q^{\fmaj w}$,\quad
$\sum t^{\ifdes w}q^{\finv w}$\quad
and\quad
$\sum t^{\fdes w}q^{\finv w}$
$(w\in B_m)$ are identical.
Their analytic expression
will be derived in a forthcoming paper [\RefFoHa].

\head 2. The construction of the transformation \endhead

\medskip
For each signed word $w=x_1x_2\ldots x_m$ the first or leftmost
(resp. last or rightmost) letter~$x_1$ (resp.~$x_m$)  is
denoted by~$F(w)$ (resp.~$L(w)$). Next, define
$\bfsun\,w:=\overline x_1x_2\ldots x_m$.
The transformation~$\bfsun$ changes the sign of the first letter.
Together with~$\bfsun$ the main ingredients of our transformation
are the bijections~$\gamma_x$ and~$\delta_x$ defined for each
integer~$x$, as follows.

If $L(w)\le x$ (resp. $L(w)>x$), then~$w$ admits the unique
factorization
$$
(v_1y_1, v_2y_2,\ldots, v_py_p),
$$
called its $x$-{\it right-to-left factorisation} having the
following properties:
\roster
\item"(i)"each $y_i$ $(1\le i\le p)$ is a {\it letter}
verifying $y_i\le x$ (resp. $y_i>x$);

\item"(ii)"each $v_i$ $(1\le i\le p)$ is a factor which is either
empty or has all its letters greater than
(resp. smaller than or equal to)~$x$.
\endroster
Then, $\gamma_x$ is defined to be the bijection that maps
$w=v_1y_1v_2y_2\ldots v_py_p$ onto the signed word
$$
\gamma_x(w):=y_1v_1y_2v_2\ldots y_pv_p.\leqno(2.1)
$$

In a dual manner, if $F(w)\geq x $ (resp. $F(w)<x$) the signed 
word~$w$ admits the unique factorization
$$
(z_1w_1,z_2w_2,\ldots, z_qw_q)
$$
called its $x$-{\it left-to-right factorisation} having the
following properties:
\roster
\item"(i)"each $z_i$ $(1\le i\le q)$ is a {\it letter}
verifying $z_i\ge x$ (resp. $z_i<x$);

\item"(ii)"each $w_i$ $(1\le i\le q)$ is a factor which is either
empty or has all its letters less than
(resp. greater than or equal to)~$x$.
\endroster
Then, $\delta_x$ is defined to be the bijection that sends
$w=z_1w_1z_2w_2\ldots z_qw_q$ onto the signed word
$$
\delta_x(w):=w_1z_1w_2z_2\ldots w_qz_q.\leqno(2.2)
$$
Next, if $(v_1y_1,v_2y_2,\ldots, y_pv_p)$ is the
$x$-right-to-left factorization of~$w$, we
define
$$
\beta_x(w):=\cases
\delta_{\overline x}\;\gamma_x(w),&\hbox{\text{if either\ }}
\overline x\le y_1\le x, \hbox{\text{or\ }}
x<y_1< \overline x;\cr
\noalign{\smallskip}
\delta_{\overline x}\;\bfsun\,\gamma_x(w),&\hbox{\text{otherwise. }}\cr\endcases
\leqno(2.3)
$$

\goodbreak
The fundamental transformation $\Psi$ on signed words that is the
main object of this paper is defined as follows:
if~$w$ is a one-letter signed word, let $\Psi(w):=w$; if it has
more than one letter, write the word as $wx$, where~$x$ is the
last letter. By induction determine~$\Psi(w)$, then apply
$\beta_x$ to $\Psi(w)$ and define $\Psi(wx)$ to be the
juxtaposition product:
$$
\Psi(wx):=\beta_x(\Psi(w))\,x.\leqno(2.4)
$$


The proof of Theorem~1.1 is given in section~3.  It is useful to
notice the following relation 
$$\displaylines{\rlap{(2.5)}\hfill
y_1\leq x\Leftrightarrow L(w)\leq x
\hfill\cr
\noalign{\hbox{\text{and the identity}}}
\noalign{\smallskip}
\rlap{(2.6)}\hfill
\Psi(wx)=\Psi(w)x,\quad
\hbox{\text{whenever}}\ x< -\max\{|x_i|\}\ \hbox{\text{or}}\
x\geq\max \{|x_i|\}.\hfill\cr}
$$

\rem Example|Let $w=3\,\overline 2\,1\, \overline 3\,\overline
4\, 3$. The factorizations used in the definitions of~$\gamma_x$
and~$\delta_{\overline x}$ are indicated by vertical bars. First,
$\Psi(3)= 3$. Then

$\sep3\sep\buildrel \gamma_{\overline 2}\over\longrightarrow 3
\buildrel \bfsun\over\longrightarrow \sep\overline 3\sep
\buildrel \delta_2\over\longrightarrow \overline 3$, so that
$\Psi(3\,\overline 2)=\overline 3\,\overline 2$;

$\sep \overline 3\sep \overline 2\sep\buildrel
\gamma_{1}\over\longrightarrow \overline 3\,\overline 2
\buildrel \bfsun\over\longrightarrow \sep 3\,\overline
2\sep \buildrel \delta_{\overline 1}\over\longrightarrow
\overline 2\,3$, so that
$\Psi(3\,\overline 2\,1)=\overline 2\,3\,1$;

$\sep \overline 2\sep 3\sep 1\sep\buildrel
\gamma_{\overline 3}\over\longrightarrow
\sep\overline 2\,3\sep 1\sep
\buildrel \delta_{3}\over\longrightarrow
3\,\overline 2\,1$, so that
$\Psi(3\,\overline 2\,1\,\overline 3)=3\,\overline 2\,1\,\overline 3$;

and $\Psi(3\,\overline 2\,1\, \overline 3\,\overline4)
=3\,\overline 2\,1\,\overline 3\,\overline 4$, because of (2.6);

$\sep 3\sep \overline 2\sep 1\sep \overline 3\sep \overline 4\sep
\buildrel
\gamma_{3}\over\longrightarrow
\sep 3\sep \overline 2\sep 1\sep \overline 3\, \overline 4\sep
\buildrel \delta_{\overline 3}\over\longrightarrow
3\,\overline 2\,1\,\overline 4\,\overline 3$.

Thus, with
$w=3\,\overline 2\,1\, \overline 3\,\overline
4\, 3$ we get $\Psi(w)=3\,\overline 2\,1\,\overline 4\,\overline
3\,3$. We verify that $\fmaj w=\finv \Psi(w)=19$,
$\Iligne w=\Iligne \Psi(w)=\{1\}$,
$\Lower w=\Lower \Psi(w)=1\,3$.
\vfill\eject

\head 3. Proof of Theorem 1.1\endhead

\nobreak
\medskip
Before proving the theorem we state a few properties involving the
above statistics and transformations. Let $|w|$ be the number of
letters of the signed word~$w$ and $|w|_{>x}$ be the number of
its letters greater than~$x$ with analogous expressions involving
ths subscripts ``$\ge x$", ``$<x$" and ``$\le x$". We have:
$$\leqalignno{\hskip 2cm
\fmaj wx&=\fmaj w+\chi(x<0)+2\,|w|\,\chi(L(w)>x);&(3.1)\cr
\finv wx&=\finv w+|w|_{>x}
+|w|_{<\overline x}+\chi(x<0);&(3.2)\cr
\finv \gamma_x(w)&=\finv w+|w|_{\le x}-|w|\,
\chi(L(w)\le x);&(3.3)\cr
\finv \delta_x(w)&=\finv w+|w|_{\ge
x}-|w|\,\chi(F(w)\ge x).&(3.4)\cr
\noalign{\hbox{Next, let $y_1$ denote the first letter of the
signed word~$w''$. Then}}
\finv \bfsun\, w''&=\finv w''+\chi(y_1>0)-\chi(y_1<0);&(3.5)\cr
|\bfsun\,w''|_{> x}
&=|w''|_{> x}+\chi(x>0)(\chi(y_1<\overline
x)-\chi(x<y_1))&(3.6)\cr
&\qquad\qquad\ {}
+\chi(x<0)(\chi(y_1\le x)-\chi(\overline x\le y_1)).\cr
}$$

\goodbreak
Theorem 1.1 is now proved by induction on the word length.
Assume that $\fmaj w=\finv \Psi(w)$ for a given $w$.
Our purpose is to show that
$$
\fmaj wx=\finv \Psi(wx)\leqno(3.7)
$$
holds for all letters~$x$. Let $w'=\Psi(w)$, so that by (2.4) the words
$w$ and $w'$ have the same rightmost letter.
Denote the $x$-right-to-left factorization of~$w'$ by $(v_1y_1,\ldots,v_py_p)$. 
By (2.3) the signed word
$v:=\beta_x(w')$ is defined by the chain
$$\leqalignno{
w'=v_1y_1\ldots v_py_p & \buildrel \gamma_x\over\longrightarrow
w''=y_1v_1\ldots y_pv_p=z_1w_1\ldots z_qw_q & (3.8)\cr
&\buildrel
\delta_{\overline x}\over\longrightarrow v
=w_1z_1\ldots w_qz_q\cr
\noalign{\hbox{if either $\overline x\le y_1\le x$, or $x<y_1<\overline x$, and
by the chain}}
w'=v_1y_1\ldots v_py_p &\buildrel \gamma_x\over\longrightarrow
w''=y_1v_1\ldots y_pv_p & (3.9)\cr
& \buildrel\bfsun\over\longrightarrow
w'''=\overline y_1v_1\ldots y_pv_p=z_1w_1\ldots z_qw_q\cr
& \buildrel
\delta_{\overline x}\over\longrightarrow v
=w_1z_1\ldots w_qz_q,\cr
}
$$
otherwise. Notice that
$(z_1w_1,\ldots, z_qw_q)$ designates the $\overline
x$-left-to-right factorization of~$w''$ in chain~(3.8) and
of~$w'''$ in chain~(3.9).

\medskip
(i) Suppose that one of the conditions
$\overline x\le y_1\le x$, $x<y_1<\overline x$ holds, so that (3.8)
applies. We have
$$
\eqalignno{\finv \Psi(wx)&=
\finv vx
=\finv v+|v|_{>x}+|v|_{<\overline x}+\chi(x<0)
&\hbox{\rm [by (3.2)]}\cr
\finv v&=\finv \delta_{\overline x}(w'')=\finv w''+|w''|_{\ge
\overline x}
-|w''|\,\chi(F(w'')\ge \overline x)
&\hbox{\rm [by (3.4)]}\cr
\finv w''&=\finv \gamma_x(w')=\finv w'+|w'|_{\le x}-|w'|\,
\chi(L(w')\le x)\kern1.5cm
&\hbox{\rm [by (3.3)]}\cr
\finv w'&=\fmaj w&\hbox{[by induction]}\cr
\fmaj w&=\fmaj wx-\chi(x<0)-2\,|w|\,\chi(L(w)>x).
&\hbox{\rm [by (3.1)]}\cr
}
$$
By induction,
$$L(w)=L(w')\ \hbox{\text{and\ }}
\chi(L(w')>x)=1-\chi(L(w')\le x).\leqno(3.10)
$$ 
Also $F(w'')=y_1$. As $w'$, $w''$, $v$
are true rearrangements of each other, we have
$|v|_{>x}+|w'|_{\le x}=|w|$, $|v|_{<\overline x}+|w''|_{\ge
\overline x}=|w|$. Hence,
$$
\finv \Psi(wx)=\fmaj wx+|w|[\chi(L(w')\le
x)-\chi(y_1\ge\overline x)].
$$
By (2.5), if $\overline x\le y_1\le x$ holds, then $L(w')\le x$
and the expression between brackets is null. If
$x<y_1< \overline x$ holds, then $L(w')>x$ and the same
expression is also null. Thus (3.7) holds.

\medskip
(ii) Suppose that none of the conditions
$\overline x\le y_1\le x$, $x<y_1<\overline x$ holds, so that (3.9)
applies. We have
$$
\eqalignno{\finv \Psi(wx)&=
\finv vx
=\finv v+|v|_{>x}+|v|_{<\overline x}+\chi(x<0)
&\hbox{\text{[by (3.2)]}}\cr
\finv v&=\finv \delta_{\overline
x}(w''')\!=\!\finv w'''+|w'''|_{\ge
\overline x}
-|w'''|\,\chi(F(w''')\ge \overline x)&
\hbox{\text{[by (3.4)]}}\cr
\finv  w'''&=\finv \bfsun\,w''=\finv w''
+\chi(y_1>0)-\chi(y_1<0)
&\hbox{\text{[by (3.5)]}}\cr
\finv w''&=\finv \gamma_x(w')=\finv w'+|w'|_{\le x}-|w'|\,
\chi(L(w')\le x)\kern1.4cm
&\hbox{\text{[by (3.3)]}}\cr
\finv w'&=\fmaj w&\hbox{[by induction]}\cr
\fmaj w&=\fmaj wx-\chi(x<0)-2\,|w|\,\chi(L(w)>x).
&\hbox{\text{[by (3.1)]}}\cr
}
$$
Moreover, $F(w''')=\overline y_1$, so that
$\chi(F(w''')\ge \overline x)=\chi(\overline y_1\ge \overline
x)=\chi(y_1\le x)=\chi(L(w')\leq x) =\chi(L(w)\leq x)$. 
As $v$ and $w'''$ are rearrangements of each
other, we have $|v|_{<\overline x}+|w'''|_{\ge \overline x}=|w|$.
Using (3.6) since $|v|_{>x}=|w'''|_{>x}=|\bfsun w''|_{>x}$ we have:
$$\eqalignno{
\finv \Psi(wx)&=
|w''|_{> x}+\chi(x>0)(\chi(y_1<\overline
x)-\chi(x<y_1))\cr
&\qquad{}+\chi(x<0)(\chi(y_1\le x)-\chi(\overline x\le
y_1))+\chi(x<0)\cr
&\qquad{}+|w|-|w|\,\chi(y_1\le x)
+\chi(y_1>0)-\chi(y_1<0)\cr
&\qquad{}+|w'|_{\le x}-|w'|\,
\chi(y_1\le x)\cr
&\qquad{}+\fmaj wx-\chi(x<0)-2\,|w|+2|w|\,\chi(y_1\le x)\cr
&=\fmaj wx+\chi(x>0)(\chi(y_1<\overline
x)-\chi(x<y_1))\cr
&\qquad{}+\chi(x<0)(\chi(y_1\le x)-\chi(\overline x\le
y_1))\cr
&\qquad{}+\chi(y_1>0)-\chi(y_1<0)\cr
&=\fmaj wx,\cr
}
$$
for, if none of the conditions $\overline x\le y_1\le x$,
$x<y_1<\overline x$ holds, then one of the following four
ones holds: 
(a) $y_1>x>0$;
(b) $\overline y_1>x>0$;
(c) $y_1\leq x<0$;
(d) $\overline y_1\leq x<0$;
and in each case the sum of the factors
in the above sum involving~$\chi$ is zero.

\medskip
The construction of~$\Psi$ is perfectly reversible. First, note that
$\bfsun$ is an involution and the maps
$\gamma_x$, $\delta_{\overline x}$ send each class~$B_\bfm$
onto itself, so that their inverses are perfectly defined. They can
also be described by means of left-to-right and right-to-left
factorizations. Let us give
the construction of the inverse $\Psi^{-1}$ of~$\Psi$. Of course,
$\Psi^{-1}(v):=v$ if~$v$ is a one-letter word. If $vx$ is a signed word,
whose last letter is~$x$, determine
$v':=\delta_{\overline x}^{-1}(v)$ and let~$z_1$ be its first
letter. If one of the conditions $\overline x\le z_1\le x$ or
$x<z_1<\overline x$ holds, the chain (3.8) is to be used
in reverse order, so that
$\Psi^{-1}(vx):=(\Psi^{-1}\,\gamma_x^{-1}\,\delta_{\overline
x}^{-1} (v))x$. If none of those two conditions holds, then
$\Psi^{-1}(vx):=(\Psi^{-1}\,\gamma_x^{-1}\,\bfsun\,\delta_{\overline
x}^{-1} (v))x$.
\quad\qed

\head 4. Proofs of Theorems 1.2 and 1.3\endhead

\medskip
Before proving Theorem 1.2 we note the following two properties.

\proclaim{Property 4.1} Let 
$I_x=\{i\in{\Bbb Z} : i<-|x|\}$
(resp. $J_x=\{i\in{\Bbb Z} :  -|x|<i<|x|\}$, 
resp. $K_x=\{i\in{\Bbb Z} :  |x|<i\}$)
and~$w$ be a signed word. Then, the
bijections $\gamma_x$ and $\delta_{\overline x}$ do not modify
the mutual order of the letters of~$w$ that belong to~$I_x$ (resp. $J_x$, 
resp. $K_x$).
\endproclaim

\demo{Proof}
Let $y\in I_x$ and $z\in I_x$ 
(resp.  $y\in J_x$ and $z\in J_x$,
resp.  $y\in K_x$ and $z\in K_x$)
be two letters of~$w$ with~$y$ to the left of~$z$. 
In the notations of (2.1)  (resp. of~(2.2)) both
$y$, $z$ are, either among the $y_i$'s (resp. the~$z_i$'s), or
letters of the~$v_i$'s (resp. the~$w_i$'s). Accordingly, $y$
remains to the left of~$z$ when $\gamma_x$ (resp.
$\delta_{\overline x}$) is applied to~$w$.
\quad\qed
\enddemo

\proclaim{Property 4.2} Let
$w=x_1x_2\ldots x_m\in B_\bfm$ be a signed word and
$i$ be a positive integer such that $m_i=m_{i+1}=1$.
Furthermore, let $x$ be an integer such that
$x\not\in\{i, \overline{i}, i+1, \overline{i+1}\}$. 
Then the following conditions are equivalent:\hfill\break
\hbox{\rm (a)} $i\in\Iligne w$;\quad
\hbox{\rm (b)} $i\in\Iligne \bfsun w$;\quad
\hbox{\rm (c)} $i\in\Iligne \gamma_x w$;\quad
\hbox{\rm (d)} $i\in\Iligne \delta_{\overline x} w$.
\endproclaim

\demo{Proof}
(a)$\Leftrightarrow$(b) holds by definition 1.1, because
$\bfsun$ has no action on the rightmost letter
belonging to $\{i, \overline i, i+1, \overline{i+1}\}$.
For the other equivalences we can say the following.
If the two letters of $w$ that belong to
$\{i, \overline i, i+1, \overline{i+1}\}$
are in $I_x$ (resp. $J_x$, resp. $K_x$), Property 4.1
applies. 
Otherwise, if $i\in\Iligne w$, then $w$ is either of the form
\quad $\ldots \overline{i+1}\ldots i\ldots$\quad or 
\quad $\ldots i \ldots \overline{i+1}\ldots$\quad and
the order of those two letters is immaterial. 
\quad\qed
\enddemo



\medskip
Theorem 1.2 holds for each one-letter signed word. Let
$w=x_1x_2\ldots x_m\in B_\bfm$ be a signed word, $x$ a letter
and~$i$ a positive integer. Assume that $\Iligne w=\Iligne
\Psi(w)$.

If $x=i$, then $i\in \Iligne wx$ if and only if $w$ contains no
letter equal to~$\pm i$ and exactly one letter equal to $\pm(i+1)$.
As $\beta_x\Psi(w)$ is a rearrangement of~$w$ with possibly sign
changes for some letters, the last statement is equivalent to saying
that $\beta_x\Psi(w)$ has no letter equal to~$\pm i$ and exactly
one letter equal to $\pm(i+1)$. This is also equivalent to
saying that $i\in\Iligne\beta_x\Psi(w)x=\Iligne\Psi(wx)$.
In the same manner, we can show that

if $x=\overline{i+1}$, then $i\in \Iligne wx$ if and only
if $i\in\Iligne\Psi(wx)$;

if $x=\overline i$, then $i\not \in\Iligne wx$ {\it and}
$i\not\in \Iligne\Psi(wx)$;

if $x=i+1$, then $i\not \in\Iligne wx$ {\it and}
$i\not\in \Iligne\Psi(wx)$.

\medskip
Now, let $i$ be such that none of the integers $i$,
$\overline{i+1}$, $\overline i$, $i+1$ is equal to~$x$.
There is nothing to prove if $m_i=m_{i+1}=1$ does
not hold, as~$i$ does not belong to any of the sets
$\Iligne w$, $\Iligne \beta_x\Psi(w)$. 
Otherwise, the result follows from Property 4.2 because
$\Psi$ is a composition product of $\beta_x$, $\bfsun$ 
and $\gamma_{\overline x}$.
Finally, the equivalence $[0\in \Iligne\beta_x(w)x]\Leftrightarrow
[0\in\Iligne wx]$ follows from Proposition~4.1 when $|x|\!>1$ and
the result is evident when $|x|\!=\!1$.
\quad\qed

\medskip
The proof of Theorem 1.3 also follows from Property 4.1. By
definition the lower records of~$wx$, other than~$x$, belong
to~$J_x$. As the bijections $\gamma_x$ and $\delta_{\overline
x}$ do not modify the mutual order of the letters of~$w$ that
belong to~$J_x$, we have $\Lower wx=\Lower \beta_x(w)x$ when
the chain~(3.8) is used. When (3.9) is applied, so that $y_1\not\in
J_x$, we also have $z_1=\overline y_1\not \in J_x$. Thus,
neither $y_1$, nor~$z_1$ can be lower records for each word
ending with~$x$. Again, $\Lower wx=\Lower \beta_x(w)x$.
\quad\qed


\head 5. Concluding remarks \endhead

\medskip
Since the works by MacMahon, much attention has been given to the
study of statistics on the symmetric group or on classes of word
rearrangements, in particular by the M.I.T. school ([\RefStST, \RefStSS, 
\RefStJ,
\RefGe, \RefBr]). It was then natural to extend those studies to other
classical Weyl groups, as was done by Reiner [\RefReTA, \RefReTB, \RefReTC,
\RefReFA, \RefReFB] for the signed permutation group. Today the work has been
pursued by the Israeli and Roman schools [\RefAROI, \RefABROI, \RefBiOIII,
\RefBiCa]. The contribution
of Adin, Roichman [\RefAROI] has been essential with their
definition of the {\it flag major index} for signed permutations. In our
forthcoming paper [\RefFoHa] we will derive new analytical expressions,
in particular for several {\it multivariable} statistics involving ``fmaj,"
``finv" and the number of lower records.

\refstyle{C}
\Refs

\ref\key \RefAROI
\by Ron M. Adin and Yuval Roichman
\paper The flag major index and group actions on polynomial rings
\jour Europ. J. Combin.
\vol 22
\yr 2001
\pages 431--446
\endref

\ref\key \RefABROI
\by Ron M. Adin, Francesco Brenti and Yuval Roichman
\paper Descent Numbers and Major Indices for the Hyperoctahedral Group
\jour Adv. in Appl. Math.
\vol 27
\yr 2001
\pages 210--224
\endref

\ref\key \RefBiOIII
\by Riccardo Biagioli
\paper Major and descent statistics for the even-signed permutation group
\jour Adv. in Appl.  Math.
\vol 31
\yr 2003
\pages 163--179
\endref

\ref\key \RefBiCa
\by Riccardo Biagioli and Fabrizio Caselli
\paper Invariant algebras and major indices for classical Weyl groups
\jour Proc. London Math. Soc.
\vol 88
\yr 2004
\pages 603--631
\endref

\ref\key \RefBjW
\by Anders Bj\"orner and Michelle L. Wachs
\paper Permutation Statistics and Linear Extensions of Posets
\jour J. Combin. Theory, Ser.~A
\vol 58
\yr 1991
\pages 85--114
\endref

\ref\key \RefBo
\by N. Bourbaki
\book Groupes et alg\`ebres de Lie, Chapitres 4,5 et 6
\publ Hermann, Paris
\yr 1968
\endref

\ref\key \RefBr
\by Francesco Brenti
\paper $q$-Eulerian Polynomials Arising from Coxeter Groups
\jour Europ. J.  Combinatorics
\vol 15
\yr 1994
\pages 417--441
\endref

\ref\key \RefFo
\by Dominique Foata
\paper On the Netto inversion number of a sequence
\jour Proc. Amer. Math. Soc.
\vol 19
\yr 1968
\pages 236--240
\endref

\ref\key \RefFoHa
\by Dominique Foata and Guo-Niu Han
\paper Signed words and permutations, III; the
MacMahon Verfahren, (preprint)
\yr 2005
\endref

\ref\key \RefFoSc
\by Dominique Foata and Marcel-Paul Sch\"utzenberger
\paper Major Index and Inversion number of Permutations
\jour Math. Nachr.
\vol 83
\yr 1978
\pages 143--159
\endref

\ref\key \RefFkSS
\by Herbert O. Foulkes
\paper Tangent and secant numbers and representations of symmetric groups
\jour Discrete Math.
\vol 15
\yr 1976
\pages 311--324
\endref

\ref\key \RefFkE
\by Herbert O. Foulkes
\paper Eulerian numbers, Newcomb's problem and representations of symmetric groups
\jour Discrete Math.
\vol 30
\yr 1980
\pages 3--49
\endref

\ref\key \RefGe
\by Ira Gessel
\book Generating functions and enumeration of sequences, Ph. D. thesis
\publ Dept. Math., M.I.T., Cambridge, Mass., 111 p.
\yr 1977
\endref

\ref\key \RefHu
\by James E. Humphreys
\book Reflection Groups and Coxeter Groups
\publ Cambridge Univ. Press, Cambridge,
(Cambridge Studies in Adv. Math., {\bf 29})
\yr 1990
\endref

\ref\key \RefKn
\by Donald E. Knuth
\book The Art of Computer Programming,  {\rm vol.3}, Sorting and
Searching
\publ Addison-Wesley, Reading
\yr 1973
\endref



\ref\key \RefLo
\by M. Lothaire
\book Combinatorics on Words
\publ Addison-Wesley, London (Encyclopedia of Math. and its Appl., {\bf 17})
\yr 1983 
\endref

\ref\key \RefMacIT
\by Percy Alexander MacMahon
\paper The indices of permutations and the derivation therefrom of functions of a single variable associated with the permutations of any assemblage of objects
\jour Amer. J. Math.
\vol 35
\yr 1913
\pages 314--321
\endref

\ref\key \RefMacIF
\by Percy Alexander MacMahon
\book Combinatory Analysis, vol.~1 and~2
\publ Cambridge, Cambridge Univ. Press, {1915}
(Reprinted by Chelsea, New York, 1995)
%\yr 1955
\endref

\ref\key \RefMacSE
\by Percy Alexander MacMahon
\book ``Collected Papers, vol.~1" [G.E. Andrews, ed.]
\publ Cambridge, Mass., The M.I.T. Press
\yr 1978
\endref

\ref\key \RefReTA
\by V. Reiner
\paper Signed permutation statistics
\jour Europ. J.  Combinatorics
\vol 14
\yr 1993
\pages 553--567
\endref

\ref\key \RefReTB
\by V. Reiner
\paper Signed permutation statistics and cycle type
\jour Europ. J. Combinatorics
\vol 14
\yr 1993
\pages 569--579
\endref

\ref\key \RefReTC
\by V. Reiner
\paper Upper binomial posets and signed permutation statistics
\jour Europ. J.  Combinatorics
\vol 14
\yr 1993
\pages 581--588
\endref


\ref\key \RefReFA
\by V. Reiner
\paper Descents and one-dimensional characters for classical Weyl groups
\jour Discrete Math.
\vol 140
\yr 1995
\pages 129--140
\endref

\ref\key \RefReFB
\by V. Reiner
\paper The distribution of descents and length
in a Coxeter group, 
\jour Electronic J. Combinatorics
\vol 2, \# R25
\yr 1995 
\endref

\ref\key \RefStST
\by Richard P. Stanley
\book Ordered structures and partitions
\publ Mem. Amer. Math. Soc. vol. 119, Amer. Math. Soc., Providence, RI
\yr 1972
\endref

\ref\key \RefStSS
\by Richard P. Stanley
\paper Binomial posets, M\"obius inversion, and permutation enumeration
\jour J. Combinatorial Theory Ser.~A
\vol 20
\yr 1976
\pages 336--356
\endref

\ref\key \RefStJ
\by John Stembridge
\paper Eulerian numbers, tableaux, and the Betti numbers of a toric variety
\jour Discrete Math.
\vol 99
\yr 1992
\pages 307--320
\endref

\endRefs

\enddocument




