%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%% Latex-file of the paper 
%%% "A note on some mahonian statistics"
%%% by R.J. Clarke
%%%Version 2 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[12pt]{amsart} 
%\usepackage{amsmath, amsthm,amsfonts}

\theoremstyle{plain} 
\newtheorem{thm}{Theorem}
\newtheorem{lem}[thm]{Lemma}

\DeclareMathOperator{\inv}{inv}
\DeclareMathOperator{\maj}{maj}
\DeclareMathOperator{\inmaj}{inmaj}
\DeclareMathOperator{\Fact}{Fact}

\def\il{\bigl]\kern-.25em\bigl]}
\def\ir{\bigr]\kern-.25em\bigr]}
 
\begin{document} 
\title{A note on some mahonian statistics} 
\author[Bob Clarke]{Bob Clarke$^*$} 
%\date{}                                      

\thanks{$^*$School of Mathematical Sciences, University of Adelaide, Australia 5005, \textsl{robert.clarke at adelaide.edu.au}}

\begin{abstract} We construct a class of mahonian statistics on words, related to the classical statistics maj and inv.  These statistics are constructed via Foata's second fundamental transformation.  \end{abstract}

\maketitle

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 53 \rms (2005), Article~B53a\hfill}
\def\thepage{}
%
%

\section{Introduction} Consider the alphabet $\mathcal{X}=[r] =\{1,2,\ldots,r\}$.

A \emph{word} $w = w_1 w_2\cdots w_n$ on $\mathcal{X}$ is a finite string of not-necessarily distinct elements of $\mathcal{X}$.  The set of all words on $\mathcal{X}$ is written $\mathcal{X}^*$.  The \emph{rearrangement class} $R(w)$ of a word $w$ is the set of all words that can be obtained by permuting the letters of $w$.  If the letters of $w$\ are distinct, then $w$ is a permutation and $R(w)$ is the set of elements of the symmetric group 
$\mathcal{S}_n$.

The statistics $\inv$ and $\maj$ are defined on $\mathcal{X}^*$ by
\begin{align*}
\inv w&=\#\{\,(i,j)\mid 1\le i<j\le n, w_i>w_j\,\},\\
\maj w&=\sum\{\,i\mid 1\le i<n, w_i>w_{i+1}\,\}.
\end{align*}
It is a result of MacMahon \cite{mac} that $\inv$ and $\maj$ are equidistributed on any rearrangement class $R(c)$.  Foata \cite{fo,folo} gave a bijective proof using his \emph{second fundamental transformation}.  A statistic equidistributed with $\inv$ (or $\maj$) is called \emph{mahonian}.

Let $a, b\in\mathcal{X}$.  The {\it cyclic interval}  $\il a,b\ir$ has been defined by Han \cite{han} as 
$$\il a,b\ir=\begin{cases}(a,b],&\text{if }a\le b;\\
                    \mathcal{X}\setminus(b,a],&\text{otherwise}.\end{cases}$$
In particular, $\il a,a\ir=\emptyset$.

Han has redefined the statistics $\maj$ and $\inv$ in terms of cyclic intervals as follows.   If $1\le j\le n$, define the \emph{$j$-factor} of $w$ as $\Fact_j w=w_1w_2\dots w_{j-1}$.  Write $w_{n+1}=\infty$.  Then
\begin{align*}
\inv w&=\sum_{j=2}^n\left|\Fact_j w\cap\il w_j,\infty\ir\right|,\\
\maj w&=\sum_{j=2}^n\left|\Fact_j w\cap\il w_j,w_{j+1}\ir\right|.
\end{align*}

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL BOB CLARKE}{\SMALL A NOTE ON SOME MAHONIAN STATISTICS}
%
%

We define the partial statistics $s_j$ and $t_j$ by
\begin{align*}
s_j&=s_j(w)=\left|\Fact_j w\cap\il w_j,w_{j+1}\ir\right|,\\
t_j&=t_j(w)=\left|\Fact_j w\cap\il w_j,\infty\ir\right|,
\end{align*}
$2\le j\le n$.  Then $s_n=t_n$ and 
\begin{align*}
\inv w&=t_2(w)+\cdots+t_n(w),\\
\maj w&=s_2(w)+\cdots+s_n(w).
\end{align*}

Our main result is the following.
\begin{thm}  Let $\mathbf{e}=(e_2,\dots,e_{n-1})=\mathbb{Z}_2^{n-2}$.  For each $j$, $1<j\le n$, let 
$$u_j=\begin{cases} s_j,&\text{ if }e_j=0;\\
t_j,&\text{ if }e_j=1.\end{cases}$$
Put $u_n=s_n=t_n$.  Then the statistic
$$\inmaj_{\mathbf{e}} w=u_2+\cdots+u_n$$
is mahonian.  
\end{thm}

Note that $\maj w=\inmaj_{(0,\dots,0)} w$, $\inv w=\inmaj_{(1,\dots,1)} w$.  This theorem defines 
$2^{n-2}$ mahonian statistics, all but two of which seem to be new (although implicit in Foata's second fundamental transformation).

Although this result suggests that for each $j$, the partial
statistics $s_j$ and $t_j$ are equidistributed, this is not in general
true --- on the rearrangement class $R(1\,1\,2\,3)$, the statistics
$s_3$ and $t_3$ are differently distributed. 

\section{Foata's second fundamental transformation}
Let $w=w_1w_2\dots w_n$ be a word on $\mathcal{X}$ and let $a\in\mathcal{X}$.  If $w_n\le a$, the \emph{$a$-factorization} of $w$ is $w=v_1b_1\dots v_pb_p$, where each $b_i$ is a letter less than or equal to $a$, and each $v_i$ is a word (possibly empty), all of whose letters are greater than $a$.  Similarly, if $w_n>a$, the \emph{$a$-factorization} of $w$ is $w=v_1b_1\dots v_pb_p$, where each $b_i$ is a letter greater than $a$, and each $v_i$ is a word (possibly empty), all of whose letters are less than or equal to $a$.  In each case we define 
$$\gamma_a(w)=b_1v_1\dots b_pv_p.$$

With the above notations, let $a=w_n$ and let $w'=w_1\dots w_{n-1}$.  The second fundamental transformation $\Phi$ is defined recursively by $\Phi(w)=w$, if $w$ has length 1, and
$$\Phi(w)=\gamma_a(\Phi(w'))a,$$
if $w$ has length $n>1$.  Then 
$$\inv\Phi(w)=\maj w,$$
see \cite{folo}.

Let us define the mapping $\Phi_1$ as the juxtaposition product
$$\Phi_1(w)=\gamma_a(w')a.$$
The following result follows easily from the proof of the result in \cite{folo}.
\begin{lem}  With the above notation,
\begin{align*}
\inv\Phi_1(w)&=\begin{cases}\inv w'&\text{if $w_{n-1}\le w_n$,}\\
\inv w'+n-1&\text{if $w_{n-1}>w_n$}\end{cases}\\
&=\inv w'+\maj w-\maj w'.
\end{align*}
\end{lem}
\qed

Since $\Phi_1$ is a bijection, this shows that the statistic
$$\inv w'+\maj w-\maj w'$$
is mahonian.  Now it is routine to verify that, in the notation of the previous section,
\begin{align*}
\inv w'+\maj w-\maj w'&=t_2+\cdots+t_{n-2}+s_{n-1}+s_n\\
&=\inmaj_{(1,\dots,1,0)}w.
\end{align*}
Hence $\inmaj_{(1,\dots,1,0)}$ is mahonian.

More generally, let $1\le j\le n$.  Write $w=u_1u_2$, where $u_1$ is a word of length $j$.  Then we can show in the same way as before that there is a bijection $\Phi'$ satisfying
\begin{align*}
\inv\Phi'(w)=\inv u_1+\maj w-\maj u_1&=t_2+\cdots+t_{j-1}+s_j+\cdots+s_n\\
&=\inmaj_{(1,\dots,1,0,\dots,0)}
\end{align*}
for all words $w$ on $n$ letters.  Hence the statistic $\inmaj_{(1,\dots,1,0,\dots,0)}$ is mahonian (where the subscript contains $j-2$ ones and $n-j$ zeros).


\begin{proof}[Proof of Theorem 1] Let
$\mathbf{e}=(e_2,\dots,e_{n-1})\in\mathbb{Z}^{n-1}$ as before.  We
will show that $\inmaj_{\mathbf{e}}$ is mahonian, by showing that
there is a bijection $\Phi_{\mathbf{e}}$ satisfying
$\inv\Phi_{\mathbf{e}}(w)=\inmaj_{\mathbf{e}}w$.  We have shown this
above for $\mathbf{e}$ of the form $(1,\dots,1,0,\dots,0)$. 

We use induction on the number of zeros in the vector $\mathbf{e}$.  The result is true if $\mathbf{e}$ contains no zeros, as in this case $\inmaj_{\mathbf{e}}=\inv$.

Suppose the result is true for all vectors $\mathbf{e'}$ containing fewer zeros than $\mathbf{e}$.  Let $k$ be the smallest index such that $e_k=0$ and let $j$ be the largest index such that $e_i=0$ for $k\le i\le j$.  If $j=n-1$ then the result follows, so suppose that $j<n-1$.  Then $e_{j+1}=1$.  Thus
$$\inmaj_{\mathbf{e}}w=t_2+\cdots+t_{k-1}+s_k+\cdots+s_j+t_{j+1}+u_{j+2}+\cdots+u_n,$$
where $u_i=t_i$ or $s_i$.

Let $\mathbf{f}$ be the vector of length $j-1$ whose components are $e_2, \dots, e_j$, i.e., $\mathbf{f}=(1,\dots,1,0,\dots,0)$ (with $k-2$ ones).  Then there is a bijection $\Phi_{\mathbf{f}}$ satisfying
$$\inv\Phi_{\mathbf{f}}v=\inmaj_{\mathbf{f}}v$$
for all words $v$ of length $j+1$.  Define a bijection $\theta$ on words of length $n$ by
$$\theta(v_1v_2)=\Phi_{\mathbf{f}}(v_1)v_2,$$
where $v_1$ and $v_2$ are words of lengths $j+1$ and $n-j-1$ respectively.  Let $\mathbf{g}=(g_i)$ be the vector defined by
$$g_i=\begin{cases}1,&\text{ if }2\le i\le j;\\
                                     e_i,&\text{ if }i>j.\end{cases}$$  Then
\begin{align*}
\inmaj_{\mathbf{g}}\theta(v_1v_2)&=(t_2+\cdots+t_{j+1})\Phi_{\mathbf{f}}(v_1)+(u_{j+2}+\cdots+u_n)\Phi_{\mathbf{f}}(v_1)v_2\\
&=(u_2+\cdots+u_{j+1})v_1+(u_{j+2}+\cdots+u_n)v_1v_2\\
&=\inmaj_{\mathbf{e}}v_1v_2.
\end{align*}

Now, as $\mathbf{g}$ contains fewer zeros than $\mathbf{e}$, there is a bijection $\Phi_{\mathbf{g}}$ such that
$$\inv\Phi_{\mathbf{g}}(w)=\inmaj_{g}w$$
for all words $w$ on $n$ letters.  Hence, putting $\Phi_{\mathbf{e}}=\Phi_{\mathbf{g}}\circ\theta$,
$$\inv\Phi_{\mathbf{e}}(w)=\inv\Phi_{\mathbf{g}}(\theta(w))=\inmaj_{\mathbf{g}}\theta(w)=\inmaj_{\mathbf{e}}w.$$
\end{proof}                                     

Finally, we refer the reader to \cite{bo} for a rather different application of Foata's second fundamental transformation.

\begin{thebibliography}{9}

\bibitem{bo} A. Bj\"orner and M. Wachs, \textsl{Permutation statistics and linear extensions of posets}, J. Combin.\ Theory Ser.~A {\bf 58} (1991),
 85--114.

\bibitem{fo} D. Foata, \textsl{On the Netto inversion number of a
sequence}, Proc.\ Amer.\ Math.\ Soc.\ {\bf 19} (1968), 236--240.


\bibitem{folo} D. Foata, \textsl{Rearrangements of Words}, 
in M.~Lothaire, \textsl{Combinatorics on Words}, Cambridge University
Press, Cambridge, 1997.

\bibitem{han} Guo-Niu Han, \textsl{Une transformation fondamentale sur
les r\'earrangements de mots}, Advances in Math.\ {\bf 105} (1994), 
26--41.

\bibitem{mac} (Major) P.A. MacMahon, Combinatory Analysis, {\rm
vol.~1}, Cambridge, Cambridge University Press, 1915. (Reprinted by
Chelsea, New York, 1955.)
 
\end{thebibliography}
\end{document}