%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[revision]{FPSAC2019}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

\articlenumber{21}
\addbibresource{21.bib}

%% note that the class file already loads {amsmath, amsthm, amssymb}
\usepackage{amscd}


\newtheorem{lem}{Lemma}[section]
\newtheorem{thm}[lem]{Theorem}
\newtheorem{pro}[lem]{Proposition}
\newtheorem{cor}[lem]{Corollary}
\newtheorem{exa}[lem]{Example}
\newtheorem{conj}[lem]{Conjecture}
\newtheorem{rem}[lem]{Remark}
\newtheorem{defi}[lem]{Definition}
\usepackage{lipsum}

\newcommand{\A}{{\mathscr{A}}}
\newcommand{\B}{{\mathscr{B}}}
\newcommand{\C}{{\mathscr{C}}}
\newcommand{\G}{{\mathscr{G}}}
\newcommand{\I}{{\mathscr{I}}}
\renewcommand{\H}{{\mathscr{H}}}
\newcommand{\K}{{\mathscr{K}}}

\newcommand{\Des}{{\textsf{Des}}}
\newcommand{\des}{{\textsf{des}}}
\newcommand{\Asc}{{\textsf{Asc}}}
\newcommand{\asc}{{\textsf{asc}}}
\newcommand{\inv}{{\textsf{inv}}}
\newcommand{\exc}{{\textsf{exc}}}
\newcommand{\fix}{{\textsf{fix}}}
\newcommand{\maj}{{\textsf{maj}}}
\newcommand{\comaj}{{\textsf{comaj}}}
\newcommand{\fmaj}{{\textsf{fmaj}}}
\newcommand{\nega}{{\textsf{neg}}}
\newcommand{\sign}{{\textsf{sign}}}

\renewcommand{\P}{{\mathscr{P}}}
\newcommand{\D}{{\mathscr{D}}}
\newcommand{\F}{{\mathscr{F}}}
% \newcommand{\R}{{\mathcal{R}}}
\newcommand{\T}{{\mathscr{T}}}
\newcommand{\Q}{{\mathcal{Q}}}


\newcommand{\W}{{\mathcal{W}}}




%% define your title in the usual way
\title[Signed Mahonian Identities on Permutations]{Signed Mahonian Identities on Permutations with Subsequence Restrictions}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[Sen-Peng Eu et al.]{Sen-Peng Eu\thanks{\href{mailto:speu@math.ntnu.edu.tw}{speu@math.ntnu.edu.tw}.}\addressmark{1}, Tung-Shan Fu\addressmark{2}, Hsiang-Chun Hsu\addressmark{3}, Hsin-Chieh Liao\addressmark{4}, \and Wei-Liang Sun\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, National Taiwan Normal University, Taipei 11677, Taiwan, ROC \\ \addressmark{2}Department of Applied Mathematics, National Pingtung University, Pingtung 90003, \\Taiwan, ROC \\ \addressmark{3}Department of Mathematics, Tamkang University, New Taipei City  25137, Taiwan, ROC \\ \addressmark{4}Department of Mathematics, University of Miami, Coral Gables, FL 33124, USA}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)

\abstract{In this paper, we present a number of results surrounding Caselli's conjecture on the equidistribution of the major index with sign over the two subsets of permutations of $\{1,2,\dots,n\}$ containing respectively the word $1\,2\cdots k$ and the word $(n-k+1)\cdots n$ as a subsequence, under a parity condition of $n$ and $k$. We derive broader bijective results on permutations containing varied subsequences. As a consequence, we obtain the signed mahonian identities on families of restricted permutations, in the spirit of a well-known formula of Gessel and Simion, covering a combinatorial proof of Caselli's conjecture. We also derive an extension of the insertion lemma of Haglund, Loehr, and Remmel which allows us to obtain a signed enumerator of the major-index increments resulting from the insertion of a pair of consecutive numbers in any place of a given permutation. 
}

%% put your French abstract here, or comment this out if you don't have one
%% \resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Signed mahonian statistics, major index with sign, subsequence restrictions}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
%\usepackage[backend=bibtex]{biblatex}
%\addbibresource{Abstract-signed-mahonian-identities-REFERENCE.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}
\subsection{Signed mahonians} Let $\mathfrak{S}_n$ be the set of permutations of $\{1,2\dots, n\}$. 
The inversion number and the major
index are two well-known mahonian statistics of permutations. Let $\sigma=\sigma_1\sigma_2\cdots\sigma_n$ be a permutation in $\mathfrak{S}_n$, where $\sigma_i=\sigma(i)$ for $1\le i\le n$. An \emph{inversion} of $\sigma$ is a pair $(\sigma_i,\sigma_j)$, $1\le i<j\le n$ such that $\sigma_i>\sigma_j$. The \emph{inversion number} $\inv(\sigma)$ of $\sigma$ is defined to be the number of inversions of $\sigma$. A \emph{descent} of $\sigma$ is an integer $i$, $1\le i\le n-1$ such that $\sigma_i>\sigma_{i+1}$. Let $\Des(\sigma)$ denote the set of descents of $\sigma$. The \emph{descent number} ($\des$) and \emph{major index} ($\maj$) of $\sigma$ are defined by
$\des(\sigma)=|\Des(\sigma)|$ and $\maj(\sigma) = \sum_{i\in\Des(\sigma)} i$.

Percy MacMahon \cite{MacMahon} proved that the major index statistic is equidistributed with the inversion number statistic over $\mathfrak{S}_n$, i.e.,
\begin{equation} \label{eq:MacMahon}
\sum_{\sigma\in\mathfrak{S}_n} q^{\maj(\sigma)}=\sum_{\sigma\in\mathfrak{S}_n} q^{\inv(\sigma)}=[2]_q[3]_q\cdots [n]_q,
\end{equation}
where $[j]_q=1+q+\cdots+q^{j-1}$ for any positive integer $j$.  This result was extended to the group $B_n$ of signed permutations with respect to the \emph{flag major index} statistic by Adin--Roichman \cite{AR}.

Gessel and Simion obtained the following formula of the distribution of the major index with sign over $\mathfrak{S}_n$ (see \cite
[Corollary 2]{Wachs} for an interesting bijective proof)
\begin{equation} \label{eq:Gessel-Simion}
\sum_{\sigma\in\mathfrak{S}_n} (-1)^{\inv(\sigma)}q^{\maj(\sigma)}=[2]_{-q}[3]_q\cdots [n]_{(-1)^{n-1}q}.
\end{equation}
A type-B analogue of (\ref{eq:Gessel-Simion}) was obtained by Adin--Gessel--Roichman \cite[Theorem 1.5]{AGR}.

A \emph{word} $W$ on a set $X$ is a finite sequence of elements in $X$. Unless specified otherwise, we consider only the words without repeated elements. The word $W$ is a permutation of $X$ if $W$ consists of all elements of $X$. 
Given a word $W=w_1w_2\cdots w_k$ on the set $\{1,2,\dots,n\}$, we say that a permutation $\sigma\in\mathfrak{S}_n$ contains the word $W$ as a \emph{subsequence} if there exists a sequence of indices $1\le i_1<i_2<\cdots<i_k\le n$ such that $\sigma_{i_j}=w_j$ for all $j$, $1\le j\le k$. Let $\mathfrak{S}_n(W)$ denote the subset of $\mathfrak{S}_n$ consisting of the permutations containing the word $W$ as a subsequence, i.e.,
\[
 \mathfrak{S}_n(W) :=\{\sigma\in\mathfrak{S}_n : \sigma^{-1}(w_1)<\sigma^{-1}(w_2)<\cdots\sigma^{-1}(w_k)\}.
\]
In particular, for
two integers $a, b\in\{1,2,\dots,n\}$, $a<b$, let $\mathfrak{S}_n(a:b)$ denote the subset of permutations containing the word $a(a+1)\cdots b$ as a subsequence. For example, $\mathfrak{S}_4(2:4)=\{1234, 2134, 2314, 2341\}$.

By a classical result of Stanley \cite{Stanley} and Foata--Sch\"utzenberger \cite{FS}, the statistics $\maj$ and $\inv$ remain equidistributed on all permutations in $\mathfrak{S}_n$ containing the word $(n-k+1)\cdots n$ as a subsequence, for $1\le k\le n-1$, i.e.,
\begin{equation} \label{eq:Foata-Schu}
\sum_{\sigma\in\mathfrak{S}_n(n-k+1:n)} q^{\maj(\sigma)}=\sum_{\sigma\in\mathfrak{S}_n(n-k+1:n)} q^{\inv(\sigma)}=[k+1]_q[k+2]_q\cdots [n]_q.
\end{equation}

Arising from the study of signed mahonians in parabolic quotients of Coxeter groups, 
Caselli \cite[Corollary 3.4]{Caselli} obtained the following product formula for the distribution of the major index with sign over $\mathfrak{S}_n(n-k+1:n)$, which includes the formula in (\ref{eq:Gessel-Simion}) as a special case.
%  Throughout this paper, let $\epsilon$ denote $-1$.
\begin{equation} \label{eqn:Caselli}
\sum_{\sigma\in\mathfrak{S}_n(n-k+1:n)} (-1)^{\inv(\sigma)}q^{\maj(\sigma)}
= [k+1]_{(-1)^{nk+n+k}q}[k+2]_{(-1)^{k+1}q}\cdots [n]_{(-1)^{n-1}q}.
\end{equation}
Caselli remarked that the proof of (\ref{eqn:Caselli}) is quite involved, without algebraic or combinatorial insight. He also raised a question \cite[Problem 5.8]{Caselli} about giving a bijective proof of the following observation. 

\begin{conj} \label{con:Conjecture} If $n$ is even or $k$ is odd then
\[
\sum_{\sigma\in\mathfrak{S}_n(1:k)} (-1)^{\inv(\sigma)}q^{\maj(\sigma)}
= \sum_{\sigma\in\mathfrak{S}_n(n-k+1:n)} (-1)^{\inv(\sigma)}q^{\maj(\sigma)}.
\]
\end{conj}

It is curious that the above equidistribution of signed major index depends on the parities of $n$ and $k$. The motivation of this paper is to solve Caselli's problem. We prove much broader results on permutations with varied subsequence restrictions.

\subsection{Main results} Given a word $W=w_1w_2\cdots w_k$ on the set $\{1,2,\dots,n\}$ and
an integer $t$, let $W+t$ denote the word $w'_1w'_2\cdots w'_k$ on
the set $\{t+1,t+2,\dots,t+n\}$ obtained from $W$ by incrementing
each element by $t$, i.e., $w'_j=w_j+t$. Our first main result gives a
sign-preserving and descent set-preserving bijection between the two subsets of permutations containing respectively the word $W$ and the word $W+2$ as a subsequence.


\begin{thm} \label{thm:main-result-I}
For any word $W$ on the set $\{1,2,\dots,n-2\}$, there is a
bijection $\phi:\sigma\rightarrow\sigma'$ of $\mathfrak{S}_n(W)$
onto $\mathfrak{S}_n(W+2)$ such that
$$
\Des(\sigma')=\Des(\sigma) \quad \mbox{and} \quad \inv(\sigma')\equiv\inv(\sigma) \pmod{2}.
$$
Hence we have the following identity
$$
\sum_{\sigma\in\mathfrak{S}_n(W)} (-1)^{\inv(\sigma)}t^{\des(\sigma)}q^{\maj(\sigma)}
= \sum_{\sigma\in\mathfrak{S}_n(W+2)} (-1)^{\inv(\sigma)}t^{\des(\sigma)}q^{\maj(\sigma)}.
$$
\end{thm}

An immediate consequence of this result is that it proves
the case of \cref{con:Conjecture} when $n$ and $k$ have
the same parity.

Our next result establishes a connection between the two parts of the symmetric difference of $\mathfrak{S}_n(W)$ and $\mathfrak{S}_n(W+1)$ when the word $W$ is an increasing sequence of consecutive numbers. 

\begin{thm} \label{thm:W+1} For $2\le k\le n-1$ and $1\le b\le n-k$, let $U$ and $V$ be the words of $k$ consecutive numbers respectively given by
\[
U = b(b+1)\cdots (b+k-1)  \qquad\mbox{ and }\qquad
V = (b+1)(b+2)\cdots (b+k).
\]
Then there is a bijection $\gamma:\sigma\rightarrow\sigma'$ of  $\mathfrak{S}_n(U)-\mathfrak{S}_n(V)$ onto
$\mathfrak{S}_n(V)-\mathfrak{S}_n(U)$  such that
$$\Des(\sigma')=\Des(\sigma) \quad \mbox{and} \quad \inv(\sigma')-\inv(\sigma)\equiv k-1  \pmod{2}.$$
\end{thm}


This result explains the case of \cref{con:Conjecture} when $n$ and $k$ have the opposite parities. Notice that \cref{thm:main-result-I} and \cref{thm:W+1} lead to the following analogous results of (\ref{eqn:Caselli}) for families of the permutations. This gives a complete picture of the \cref{con:Conjecture} for all parity cases of $n$ and $k$.


\begin{cor} \label{cor:whole-result} For $2\le k\le n-1$ and $1\le b\le n-k+1$, the following results hold.
\begin{enumerate}
\item If $k$ is odd then we have
\[
\sum_{\sigma\in\mathfrak{S}_n(b:b+k-1)} (-1)^{\inv(\sigma)}q^{\maj(\sigma)} =
 [k+1]_{-q}[k+2]_{q}\cdots [n]_{(-1)^{n-1}q}.
\]
\item If $k$ is even and $n$ is even then  we have
\[
\sum_{\sigma\in\mathfrak{S}_n(b:b+k-1)} (-1)^{\inv(\sigma)}q^{\maj(\sigma)} 
= \begin{cases}
           [k+1]_{q}[k+2]_{-q}[k+3]_{q}\cdots [n]_{-q} & \mbox{for $b$  odd} \\
           \big(2-[k+1]_{q}\big)[k+2]_{-q}[k+3]_{q}\cdots [n]_{-q} & \mbox{for $b$ even.}
  \end{cases}
\]
\item If $k$ is even and $n$ is odd then we have
\[
\sum_{\sigma\in\mathfrak{S}_n(b:b+k-1)} (-1)^{\inv(\sigma)}q^{\maj(\sigma)} 
= \begin{cases}
           \big(2-[k+1]_{-q}\big)[k+2]_{-q}[k+3]_{q}\cdots [n]_{q} & \mbox{for $b$ odd} \\
           [k+1]_{-q}[k+2]_{-q}[k+3]_{q}\cdots [n]_{q} & \mbox{for $b$  even.}          
  \end{cases}
\]
\end{enumerate}
\end{cor}



 

For any element $r\in\{1,2,\dots,n\}$ and any permutation $W$ of the
set $\{1,2,\dots,n\}-\{r\}$, Haglund--Loehr--Remmel \cite{HLR}
derived an insertion lemma which describes the increment of major
index resulting from the insertion of the element $r$ in $W$, and
proved that no matter what the element $r$ is with respect to other
elements
\begin{equation} \label{eqn:maj-increment}
\sum_{\sigma\in\mathfrak{S}_n(W)} q^{\maj(\sigma)}= q^{\maj(W)} [n]_q.
\end{equation}
We derive an extension of the insertion lemma which allows us to
obtain the following signed analogue.

\begin{thm}  \label{thm:(r-1)(r+2)}
For $1\le r\le n-1$ and any permutation $W$ of the set $\{1,2,\dots,n\}-\{r,r+1\}$, we have
\[
\sum_{\sigma\in\mathfrak{S}_n(W)} (-1)^{\inv(\sigma)}q^{\maj(\sigma)} = (-1)^{\inv(W)}q^{\maj(W)} [n-1]_{(-1)^{n}q}[n]_{(-1)^{n-1}q}.
\]
\end{thm}


We derive some extended results from our main results, over the permutations with subsequence restrictions defined by an injective labeling of a poset, and by an
pattern-avoiding condition within a given underlying set.


\section{A proof of \cref{thm:main-result-I}}
In this section, we shall establish a sign-preserving and descent set-preserving map $\phi:\mathfrak{S}_n(W)\rightarrow\mathfrak{S}_n(W+2)$ for any word $W$ on the set $\{1,2,\dots,n-2\}$.

\subsection{The construction of the map $\phi:\mathfrak{S}_n(W)\rightarrow\mathfrak{S}_n(W+2)$.}
Given a permutation $\sigma=\sigma_1\sigma_2\cdots\sigma_n\in\mathfrak{S}_n(W)$, we shall construct the corresponding permutation $\phi(\sigma)$ by
removing the elements $n-1,n$ from $\sigma$, increment each of the remaining elements by 2, and then insert the elements $1,2$ at appropriate positions so that $\phi(\sigma)$ satisfies the requested conditions. Let $y_1,y_2$ denote the entries for the elements $1,2$ in $\phi(\sigma)$, i.e., $\{y_1, y_2\}=\{1,2\}$, where $y_2$ appears to the right of $y_1$.
 Described in algorithm A, the construction of $\phi(\sigma)$ is given by case analysis, where the cases I, II, III, and IV describe the construction when the elements $n-1, n$ of $\sigma$ are not adjacent, and the cases V and VI describe the construction when $n-1, n$ of $\sigma$ are adjacent.   
 
In the following algorithm, we assume $\sigma_0=\sigma_{n+1}=0$,   and let $\sigma_j^{+}$ denote the entry $\sigma_j$ incremented by 2. 

%\medskip
\noindent
{\bf Algorithm A.}     

Find the elements $n-1, n$ of $\sigma$. Let $\{\sigma_a,\sigma_b\}=\{n-1,n\}$ for some integers $a, b$ with $1\le a<b\le n$. 
We construct the permutation $\phi(\sigma)$ according to the following cases.

\noindent  
{\bf I.} $\sigma_{a-1}>\sigma_{a+1}$ and $\sigma_{b-1}>\sigma_{b+1}$ for $a>1$ and $a+1<b\le n$.

Starting with $\sigma_a$ ($\sigma_b$, respectively), search to the left and find the maximal increasing sequence of consecutive entries $\sigma_t<\sigma_{t+1}<\cdots<\sigma_a$ ($\sigma_s<\sigma_{s+1}<\cdots<\sigma_b$, respectively). Then remove the elements $\sigma_a,\sigma_b$ from $\sigma$, increment each of the remaining elements by 2, and insert $y_1$ ($y_2$, respectively) on the immediate left of $\sigma_t^{+}$ ($\sigma_s^{+}$, respectively). Note that if $s= a+1$ then $y_2$ is between $\sigma^{+}_{a-1}$ and $\sigma^{+}_{a+1}$ is on the right of $y_2$. 

%\smallskip
\noindent
{\bf II.} $\sigma_{a-1}<\sigma_{a+1}$ and $\sigma_{b-1}<\sigma_{b+1}$ for $a\ge 1$ and $a+1<b< n$.

Starting with $\sigma_a$ ($\sigma_b$, respectively), search to the right and find the maximal decreasing sequence of consecutive entries $\sigma_a>\sigma_{a+1}>\cdots>\sigma_t$ ($\sigma_b>\sigma_{b+1}>\cdots>\sigma_s$, respectively). Then remove the elements $\sigma_a,\sigma_b$ from $\sigma$, increment each of the remaining elements by 2, and insert $y_1$ ($y_2$, respectively) on the immediate right of $\sigma_t^{+}$ (after $\sigma_s^{+}$, respectively). Note that if $t= b-1$ then $y_1$ is between $\sigma^{+}_{b-1}$ and $\sigma^{+}_{b+1}$. 


%\smallskip
\noindent
{\bf III.} $\sigma_{a-1}>\sigma_{a+1}$ and $\sigma_{b-1}<\sigma_{b+1}$ for $a>1$ and $a+1<b<n$.

Starting with $\sigma_a$ ($\sigma_b$, respectively), search to the left (right, respectively) and find the maximal increasing (decreasing, respectively) sequence of consecutive entries $\sigma_t<\sigma_{t+1}<\cdots<\sigma_a$ ($\sigma_b>\sigma_{b+1}>\cdots>\sigma_s$, respectively). Then remove the elements $\sigma_a,\sigma_b$ from $\sigma$, increment each of the remaining elements by 2, and insert $y_1$ ($y_2$, respectively) immediately before $\sigma_t^{+}$ (after $\sigma_s^{+}$, respectively). 

Notice that in the above three cases the elements $y_1,y_2$ are not adjacent.  Choose either $(y_1,y_2)=(1,2)$ or $(y_1,y_2)=(2,1)$ such that $\inv(\phi(\sigma))\equiv\inv(\sigma) \pmod{2}$. 

%\smallskip
\noindent
{\bf IV.} $\sigma_{a-1}<\sigma_{a+1}$ and $\sigma_{b-1}>\sigma_{b+1}$ for $1\le a<b\le n$.

Starting with $\sigma_a$ ($\sigma_b$, respectively), search to the right (left, respectively) and find the maximal decreasing (increasing, respectively) sequence of consecutive entries $\sigma_a>\sigma_{a+1}>\cdots>\sigma_t$ ($\sigma_s<\sigma_{s+1}<\cdots<\sigma_b$, respectively).
Then remove the elements $\sigma_a,\sigma_b$ from $\sigma$, increment each of the remaining elements by 2. To preserve the descent set and the parity of the inversion number, the insertion of $y_1,y_2$ is determined as follows.

If $t\neq s$ then there exists at least one element between $\sigma_t$ and $\sigma_s$. We insert $y_1$ ($y_2$, respectively) immediately after $\sigma_t^{+}$ (before $\sigma_s^{+}$, respectively). Since $y_1,y_2$ are not adjacent, choose either $(y_1,y_2)=(1,2)$ or $(y_1,y_2)=(2,1)$ such that $\inv(\phi(\sigma))\equiv\inv(\sigma) \pmod{2}$.

Otherwise, $t=s$. The insertion and assignment of $y_1,y_2$ are determined according the following possibilities. 

\begin{enumerate}
\item[(i)] $a+1<t<b-1$. If $(\sigma_a,\sigma_b)=(n-1,n)$ and  $a+b$ is odd, or $(\sigma_a,\sigma_b)=(n,n-1)$ and  $a+b$ is even then insert $(y_1, y_2)=(1,2)$ adjacently on the immediate right of $\sigma_t^{+}$; otherwise, insert $(y_1, y_2)=(2,1)$ adjacently on the immediate left of $\sigma_t^{+}$.

\item[(ii)] $a+1=t<b-1$. If $(\sigma_a,\sigma_b)=(n-1,n)$ and  $a+b$ is odd, or $(\sigma_a,\sigma_b)=(n,n-1)$ and  $a+b$ is even then insert $(y_1, y_2)=(1,2)$ adjacently on the immediate right of $\sigma_t^{+}$. Otherwise, find the maximal increasing sequence of consecutive entries $\sigma_r<\sigma_{r+1}<\cdots<\sigma_a$ (set $r=1$ if $a=1$). We insert $y_1$ ($y_2$, respectively) immediately before $\sigma_r^{+}$ ($\sigma_t^{+}$, respectively), where $(y_1,y_2)=(2,1)$ if $a+r$ is even, and $(y_1,y_2)=(1,2)$ if $a+r$ is odd.

\item[(iii)] $a+1<t=b-1$. If  $(\sigma_a,\sigma_b)=(n-1,n)$ and  $a+b$ is even, or $(\sigma_a,\sigma_b)=(n,n-1)$ and  $a+b$ is odd then insert $(y_1, y_2)=(2,1)$ adjacently on the immediate left of  $\sigma_t^{+}$. Otherwise, find the maximal decreasing sequence of consecutive entries $\sigma_b>\sigma_{b+1}>\cdots>\sigma_r$ (set $r=n$ if $b=n$). We insert $y_1$ ($y_2$, respectively) immediately after $\sigma_t^{+}$ ($\sigma_r^{+}$, respectively), where $(y_1,y_2)=(1,2)$ if  $b+r$ is even, and $(y_1,y_2)=(2,1)$ if $b+r$ is odd.

\item[(iv)] $a+1=t=b-1$. If $(\sigma_a,\sigma_b)=(n,n-1)$ then to the right of $\sigma_b$ find the maximal decreasing sequence of consecutive entries $\sigma_b>\sigma_{b+1}>\cdots>\sigma_r$ (set $r=n$ if $b=n$). We insert $y_1$ ($y_2$, respectively) immediately after $\sigma_t^{+}$ ($\sigma_r^{+}$, respectively), where $(y_1,y_2)=(1,2)$ if $b+r$ is even, and $(y_1,y_2)=(2,1)$ if $b+r$ is odd.

Otherwise, $(\sigma_a,\sigma_b)=(n-1,n)$. Then to the left of $\sigma_a$ find the maximal increasing sequence of consecutive entries $\sigma_r<\sigma_{r+1}<\cdots<\sigma_a$ (set $t=1$ if $a=1$). We insert $y_1$ ($y_2$, respectively) immediately before $\sigma_r^{+}$ ($\sigma_t^{+}$, respectively), where $(y_1,y_2)=(2,1)$ if $a+r$ is even, and $(y_1,y_2)=(1,2)$ if $a+r$ is odd.
\end{enumerate}


%\smallskip
\noindent
{\bf V.} $b=a+1$ and $(\sigma_a,\sigma_b)=(n-1,n)$ for $1\le a<n$. 

Starting with $\sigma_b$, find the maximal increasing sequence of consecutive entries $\sigma_t<\sigma_{t+1}<\cdots<\sigma_a<\sigma_b$ to the left (set $t=1$ if $a=1$), and find the maximal decreasing sequence of consecutive entries $\sigma_b>\sigma_{b+1}>\cdots>\sigma_s$ to the right (set $s=n$ if $b=n$). Then remove the elements $\sigma_a,\sigma_b$ from $\sigma$, increment each of the remaining elements by 2.
\begin{enumerate}
\item[(i)] If $\sigma_{a-1}>\sigma_{b+1}$ then $a\neq 1$ and we insert  $(y_1,y_2)=(1,2)$ adjacently on the immediate left of $\sigma_t^{+}$. 
\item[(ii)] Otherwise, $\sigma_{a-1}<\sigma_{b+1}$. We insert $y_1$ ($y_2$, respectively) immediately before $\sigma_t^{+}$ (after $\sigma_s^{+}$, respectively), where $(y_1,y_2)=(1,2)$ if $t+s$ is odd, and $(y_1,y_2)=(2,1)$ otherwise.
\end{enumerate}

%\smallskip
\noindent
{\bf VI.} $b=a+1$ and $(\sigma_a,\sigma_b)=(n,n-1)$ for $1\le a<n$. 

Starting with $\sigma_a$, find the maximal increasing sequence of consecutive entries $\sigma_t<\sigma_{t+1}<\cdots<\sigma_a$ to the left (set $t=1$ if $a=1$), and find the maximal decreasing sequence of consecutive entries $\sigma_a>\sigma_b>\sigma_{b+1}>\cdots>\sigma_s$ to the right (set $s=n$ if $b=n$). Then remove the elements $\sigma_a,\sigma_b$ from $\sigma$, increment each of the remaining elements by 2. 
\begin{enumerate}
\item[(i)] If $\sigma_{a-1}<\sigma_{b+1}$ then $b\neq n$ and we insert $(y_1,y_2)=(2,1)$ adjacently on the immediate right of $\sigma_s^{+}$. 
\item[(ii)] Otherwise, $\sigma_{a-1}>\sigma_{b+1}$. We insert $y_1$ ($y_2$, respectively) immediately before $\sigma_t^{+}$ (after $\sigma_s^{+}$, respectively), where $(y_1,y_2)=(1,2)$ if $t+s$ is even, and $(y_1,y_2)=(2,1)$ otherwise.
\end{enumerate}


\begin{pro} \label{pro:sign-preserving} The map $\phi:\mathfrak{S}_n(W)\rightarrow\mathfrak{S}_n(W+2)$ constructed by algorithm A preserves the descent set and the parity of the inversion number of a permutation.
\end{pro}


\begin{exa} \label{exa:V-VI} {\rm In the following, we demonstrate the construction of the map $\phi$ in  case VI, using some permutations in $\mathfrak{S}_9$ containing the word $W=3\, 1\, 7\, 5$.

Let $\sigma= 3\, 1\, 9\, 8\, 6\, 4\, 2\, 7\, 5\in\mathfrak{S}_9(W)$. We have $\inv(\sigma)=18$ and $(\sigma_3,\sigma_4)=(9,8)$.  By case VI, to the left of $\sigma_3$ find the maximal increasing sequence of consecutive entries $(1,9)$, and to the right of $\sigma_3$ find the maximal decreasing sequence of consecutive entries $(9,8,6,4,2)$. Remove the elements $8,9$ from $\sigma$ and increment the other elements by 2. Since $\sigma_2<\sigma_5$, by V(i) with $(y_1,y_2)=(2,1)$ inserted, we obtain $\phi(\sigma)= 5\, 3\, 8\, 6\, 4\, 2\, 1\, 9\, 7\in\mathfrak{S}_9(W+2)$ with $\inv(\phi(\sigma))=18$.

Moreover, if $\sigma'= 3\, 6\, 9\, 8\, 4\, 2\, 1\, 7\, 5\in\mathfrak{S}_9(W)$, we have $\inv(\sigma')=21$ and $(\sigma'_3,\sigma'_4)=(9,8)$.   Since $\sigma_2>\sigma_5$, by VI(ii) with $(y_1,y_2)=(1,2)$ inserted, we obtain $\phi(\sigma')= 1\, 5\, 8\, 6\, 4\, 3\, 2\, 9\, 7\in\mathfrak{S}_9(W+2)$ with $\inv(\phi(\sigma'))=15$.

}
\end{exa}

\subsection{The construction of the map $\phi^{-1}:\mathfrak{S}_n(W+2)\rightarrow\mathfrak{S}_n(W)$.}
For a word $V=v_1v_2\cdots v_d$ on the set $\{1,2,\dots,n\}$, let $\tau_n(V)$ denote the $n$-\emph{complement} of $V$ defined by $\tau_n(V)=(n+1-v_1)(n+1-v_2)\cdots(n+1-v_d)$. For any word $W$ on the set $\{1,2,\dots,n-2\}$, we observe that the $n$-complement of the word $W+2$, say $W'=\tau_n(W+2)$, is also a word on the set $\{1,2,\dots,n-2\}$ and, moreover, $W=\tau_n(W'+2)$.

To find $\phi^{-1}$, given a permutation $\sigma=\sigma_1\sigma_2\cdots\sigma_n\in\mathfrak{S}_n(W+2)$, we shall construct the corresponding permutation $\phi^{-1}(\sigma)$ by
removing the elements $1,2$ from $\sigma$, decrement each of the remaining elements by 2, and then insert the elements $n-1,n$ at appropriate positions so that $\phi^{-1}(\sigma)$ satisfies the requested conditions.
 The construction of the map $\phi^{-1}$ is exactly the reverse operation of $\phi$, which is essentially established from $\phi$ by $\phi^{-1}=\tau_n\circ\phi\circ \tau_n$. We omit a detailed construction.
 \[
 \begin{CD}
 \mathfrak{S}_n(W) @>\phi>> \mathfrak{S}_n(W+2)\\
 @A\tau_nAA @VV\tau_nV\\
 \mathfrak{S}_n(W'+2) @<\phi<< \mathfrak{S}_n(W')
 \end{CD}
 \]




\section{A proof of \cref{thm:W+1}}
 

In the following, we shall establish a bijection between the two parts of the symmetric difference of $\mathfrak{S}_n(U)$ and $\mathfrak{S}_n(V)$, where $U = b(b+1)\cdots (b+k-1)$ and $V = (b+1)(b+2)\cdots (b+k)$ for $2\le k\le n-1$ and $1\le b\le n-k$. 

Notice that the set $\mathfrak{S}_n(U)\cap\mathfrak{S}_n(V)$ consists of all permutations containing the word $b(b+1)\cdots (b+k)$ as a subsequence.

%\subsection{Proof of Theorem \ref{thm:W+1}.}
Given a $\sigma\in\mathfrak{S}_n(U)-\mathfrak{S}_n(V)$, notice that the element $b+k$ appears to the left of the element $b+k-1$ in $\sigma$, i.e., $\sigma^{-1}(b+k)<\sigma^{-1}(b+k-1)$.  We shall rearrange the elements $b, b+1,\dots, b+k$ of $\sigma$ to construct a permutation $\sigma'\in\mathfrak{S}_n(V)-\mathfrak{S}_n(U)$ satisfying the requested conditions. The construction is given in algorithm C below. In the following algorithm,  we compose permutations right to left.

%\smallskip
\noindent
{\bf Algorithm C.}  
\begin{enumerate}
\item[(C1)] If $b+k$ appears to the left of $b$ in $\sigma$, then set
\[
\sigma' = \left(\begin{array}{ccccc}
                        b+k & b & b+1  & \cdots & b+k-1 \\ 
                        b+1 & b & b+2  & \cdots & b+k
                       \end{array}
                 \right)\sigma.
\]
Notice that $\inv(\sigma')-\inv(\sigma)=1-k$.

\item[(C2)] Otherwise, $b+k$ appears between $b+j-1$ and $b+j$ for some $j$ ($1\le j\le k-1)$. Then if in particular $j=k-1$ then set
\[
\sigma' = \left(\begin{array}{ccccc}
                        b    & \cdots & b+k-2 & b+k  & b+k-1   \\ 
                        b+1  & \cdots & b+k-1 & b+k  & b
                       \end{array}
                 \right)\sigma,
\]
otherwise, $1\le j\le k-2$ and set 
\[
\sigma' = \left(\begin{array}{cccccccc}
                 b   & \cdots & b+j-1 & b+k   &  b+j & b+j+1  & \cdots & b+k-1 \\ 
                 b+1 & \cdots & b+j   & b+j+1 &  b   & b+j+2  & \cdots & b+k
                \end{array}
                \right)\sigma.
\]
Notice that in the former case $\inv(\sigma')-\inv(\sigma)= k-1$, while in the latter case $\inv(\sigma')-\inv(\sigma)= 2j-k+1$. 
\end{enumerate}

We observe that $\Des(\sigma')=\Des(\sigma)$ and $\inv(\sigma')-\inv(\sigma)\equiv k-1  \pmod{2}$. 
On the other hand, it is straightforward to construct the inverse map by the reverse operation.





\section{A proof of \cref{thm:(r-1)(r+2)}}
For a fixed $r\in\{1,2,\dots,n-1\}$, let $W=w_1w_2\cdots w_{n-2}$ be a permutation of the set $\{1,2,\dots, r-1,r+2,\dots,n\}$. Let $\mathfrak{S}_n^*(W)\subset \mathfrak{S}_n(W)$ denote the subset consisting of the permutations in which the elements $r,r+1$ are adjacent. Note that
interchanging the elements $r, r+1$ is a sign-reversing involution on the difference set $\mathfrak{S}_n(W)-\mathfrak{S}_n^*(W)$ which preserves descent sets. Hence
\begin{equation} \label{eqn:W=W*} 
\sum_{\sigma\in\mathfrak{S}_n(W)} (-1)^{\inv(\sigma)}q^{\maj(\sigma)}
=\sum_{\sigma\in\mathfrak{S}_n^*(W)} (-1)^{\inv(\sigma)}q^{\maj(\sigma)}.
\end{equation} 


Any permutation $\sigma\in\mathfrak{S}_n^*(W)$ can be obtained from $W$ by inserting the elements $r,r+1$ adjacently to the left of $W$, between two elements of $W$, or to the right of $W$, i.e., one of the $n-1$ \emph{spaces} of $W$. These spaces are indexed by $0,1,\dots,n-2$ from left to right. We shall study the major-index increment of such an insertion by extending the insertion lemma of Haglund--Loehr--Remmel \cite[Lemma 4.1]{HLR}.

Assume $w_0=0$ and $w_{n-1}=n+1$. For $0\le j\le n-2$, the $j$th space, which is between $w_j$ and $w_{j+1}$, is called an $RL$-\emph{space of $W$ relative to $r$} if it satisfies one of the following conditions:
\begin{itemize}
\item $w_j>w_{j+1}>r$,
\item $r>w_j>w_{j+1}$, or
\item $w_j<r<w_{j+1}$.
\end{itemize} 
Notice that the space to the left (right, respectively) of $W$ is an $RL$-space if $r< w_1$ ($w_{n-2}<r$, respectively).
Any space which is not an $RL$-space is called an $LR$-\emph{space} (relative to $r$). In fact, an $RL$-space is a space where the insertion of $r$ in $W$ creates no `new descent', while an $LR$-space is one where a new descent is created. Suppose there are $d$ $RL$-spaces of $W$ relative to $r$, we label the $RL$-spaces from right to left with $0,1,\dots,d-1$ and label the $LR$-spaces from left to right with $d,d+1,\dots,n-2$, called the \emph{canonical labeling} of $W$. Let $\alpha(W)=(a_0,a_1,\dots,a_{n-2})$ denote the vector of the labeling, where $a_j$ is the label the $j$th space receives. 

\begin{exa} \label{exa:permutation} {\rm Suppose $r=4$ and $W$ is the permutation $W=8\, 3\, 6\, 1\, 2 \,9\, 7$ of the set $\{1,2,\dots,9\}-\{4,5\}$. As shown below, the $RL$-spaces of $W$ relative to $4$ are the spaces with labels $a_0,a_2,a_5,a_6$ and the $LR$-spaces are the ones with labels $a_1,a_3,a_4,a_7$. The vector of the canonical labeling of $W$ is $\alpha(W)=(3,4,2,5,6,1,0,7)$. 
\[
\begin{array}{lcccr}
       _{a_0}\,8\,_{a_1}\,3\,_{a_2}\,6\,_{a_3}\,1\,_{a_4}\,2\,_{a_5}\,9\,_{a_6}\,7\,_{a_7} & & \longrightarrow & &\alpha(W)=(3,4,2,5,6,1,0,7) 
\end{array}
\]
}
\end{exa}

%\medskip
The result of Haglund--Loehr--Remmel \cite[Lemma 4.1]{HLR} can be expressed as follows.

\begin{lem} {\rm\bf (Insertion Lemma \cite{HLR}) } \label{lem:insertion} If $\pi$ is the word obtained from $W$ by inserting the element $r$ at the $j$th space of $W$ then we have
\[
\maj(\pi)=\maj(W)+a_j.
\]
\end{lem}

We associate $W$ with another vector $\beta(W)=(b_0,b_1,\dots,b_{n-2})$, where $b_j$ is the number of $RL$-spaces of $W$ relative to $r$ appearing to the right of the $j$th space for $0\le j\le n-2$. For example, given $r=4$ and the word $W=8\, 3\, 6\, 1\, 2 \,9\, 7$ in \cref{exa:permutation}, the associated vector is $\beta(W)=(3,3,2,2,2,1,0,0)$.
\[
\begin{array}{lcccr}
       _{b_0}\,8\,_{b_1}\,3\,_{b_2}\,6\,_{b_3}\,1\,_{b_4}\,2\,_{b_5}\,9\,_{b_6}\,7\,_{b_7} & & \longrightarrow & &\beta(W)=(3,3,2,2,2,1,0,0) \\ 
\end{array}
\]

%\medskip
We derive the following extension of the \cref{lem:insertion}. 


\begin{lem} \label{lem:a+b} If $\sigma$ is the word obtained from $W$ by inserting the word $z_1z_2$ at the $j$th space of $W$, where $z_1z_2$ is either $r(r+1)$ or $(r+1)r$, then we have
\[
\maj(\sigma)=\begin{cases}
\maj(W)+a_j+b_j & \mbox{if $z_1z_2=r\,(r+1)$}\\
\maj(W)+a_j+b_j+j+1 & \mbox{if $z_1z_2=(r+1)\,r$.}
             \end{cases}
\]
\end{lem}




Notice that $\sigma$ has the same (opposite, respectively) sign of $W$ if $z_1z_2=r(r+1)$ ($z_1z_2=(r+1)r$, respectively). 
By \cref{lem:a+b} and (\ref{eqn:W=W*}), we have the following result.

\begin{cor} \label{cor:q-polynomial} For any element $r\in\{1,2,\dots,n-1\}$ and any permutation $W$ of the set $\{1,2,\dots,n\}-\{r,r+1\}$ with the associated vectors $\alpha(W)=(a_0,\dots,a_{n-2})$ and $\beta(W)=(b_0,\dots,b_{n-2})$, we have
\[
\sum_{\sigma\in\mathfrak{S}_n(W)} (-1)^{\inv(\sigma)}q^{\maj(\sigma)}=(-1)^{\inv(W)}q^{\maj(W)}\left(\sum_{j=0}^{n-2} q^{a_j+b_j}\big(1-q^{j+1}\big) \right).
\]
\end{cor}

To prove \cref{thm:(r-1)(r+2)}, we prove the following result:
\begin{equation} \label{eqn:f(W,q)}
f(W;q):=\sum_{j=0}^{n-2} q^{a_j+b_j}\big(1-q^{j+1}\big)=[n-1]_{(-1)^{n}q}[n]_{(-1)^{n-1}q}.
\end{equation}

\section{Applications} 
% In this section, we  shall derive some extended results from our main results.

\subsection{An extended result of \cref{thm:(r-1)(r+2)}} We derive a product formula of the signed enumerator of the major index over the permutations in $\mathfrak{S}_n$ containing a permutation $W$ of the set $\{2k+1,2k+2,\dots,n\}$ as a subsequence, in the spirit of \cref{thm:(r-1)(r+2)}.

\begin{thm} \label{thm:2k+1:n} For $k\ge 1$ and any permutation $W$ of the set $\{2k+1,2k+2,\dots,n\}$, we have
\begin{align*}
\sum_{\sigma\in\mathfrak{S}_n(W)} (-1)^{\inv(\sigma)}q^{\maj(\sigma)} 
 &= (-1)^{\inv(W)}q^{\maj(W)} \sum_{\sigma\in\mathfrak{S}_n(2k+1:n)} (-1)^{\inv(\sigma)}q^{\maj(\sigma)}  \\
 &=  (-1)^{\inv(W)}q^{\maj(W)} [n-2k+1]_{(-1)^{n-2k}q}\cdots[n]_{(-1)^{n-1}q}.
\end{align*}
\end{thm}



\subsection{Labelings of a poset} Given a poset $(P,<)$ on a set $P=\{x_1,x_2,\dots,x_{k}\}$ with $k\le n-2$, by an \emph{injective labeling} of $(P,<)$ we mean an injection $f:P\rightarrow\{1,2,\dots,n-2\}$. Let $f+2$ be the labeling of $(P,<)$ obtained from $f$ by incrementing the label of each element by 2, which is an injection $P\rightarrow\{3,4,\dots,n\}$. Define
\[
\mathfrak{S}_n(f):=\{\sigma\in\mathfrak{S}_n: \sigma^{-1}(f(x_i))<\sigma^{-1}(f(x_j)), \mbox{ for $x_i<x_j$ in $(P,<)$}\}.
\]
We prove the following result.

\begin{thm} \label{thm:labeling-poset} For any poset $(P,<)$ with at most $n-2$ elements and any injective labeling $f:P\rightarrow\{1,2,\dots,n-2\}$, we have
\[
\sum_{\sigma\in\mathfrak{S}_n(f)} (-1)^{\inv(\sigma)}q^{\maj(\sigma)}
= \sum_{\sigma\in\mathfrak{S}_n(f+2)} (-1)^{\inv(\sigma)}q^{\maj(\sigma)}.
\]
\end{thm}

\subsection{Pattern avoidance}

Putting \cref{thm:main-result-I} in the realm of pattern-avoidance, one can consider the $\pi$-avoiding words of a given underlying set $S\subseteq\{1,2,\dots,n-2\}$ for a certain pattern $\pi$. 
Let $\mathfrak{S}_n(\pi;S)$ be the set consisting of the permutations $\sigma\in\mathfrak{S}_n$ containing no $\pi$-pattern restricted to the elements of $S$. Let $S+2:=\{z+2|z\in S\}\subset\{3,4,\dots,n\}$. For example, for $n=4$, consider a pattern $\pi=2\,1$ and a set $S=\{1,2\}$. Then $S+2=\{3,4\}$ and we have 
\begin{align*}
\mathfrak{S}_4(\pi;S) &=\{1234, 1243, 1324, 1342, 1423, 1432, 3124, 3142, 3412, 4123, 4132, 4312\}, \\
\mathfrak{S}_4(\pi;S+2) &=\{1234, 1324, 1342, 2134, 2314, 2341, 3124, 3142, 3214, 3241, 3412, 3421\}.
\end{align*}
\[
\sum_{\sigma\in\mathfrak{S}_4(\pi;S)} (-1)^{\inv(\sigma)}q^{\maj(\sigma)}
= \sum_{\sigma\in\mathfrak{S}_4(\pi;S+2)} (-1)^{\inv(\sigma)}q^{\maj(\sigma)}=1+q^2-q^3-q^5.
\]

Making use of the map $\phi$ in \cref{thm:main-result-I}, we have the following result.

\begin{thm} \label{thm:pattern-avoidance} For a pattern $\pi$ and an underlying set $S\subseteq\{1,2,\dots,n-2\}$, we have
\[
\sum_{\sigma\in\mathfrak{S}_n(\pi;S)} (-1)^{\inv(\sigma)}q^{\maj(\sigma)}
= \sum_{\sigma\in\mathfrak{S}_n(\pi;S+2)} (-1)^{\inv(\sigma)}q^{\maj(\sigma)}.
\]
\end{thm}



\section{Concluding remarks}
In this paper, we study the signed distributions of the major index on  permutations with subsequence restrictions.  Recall that a signed permutation in the group $B_n$ is a bijection $\sigma$ of the set $\{-n,-n+1,\dots,-1,1,2,\dots,n\}$ onto itself such that $\sigma(-i)=-\sigma(i)$ for all $1\le i\le n$. The flag major index of $\sigma$, denoted by $\fmaj$, is defined as $\fmaj(\sigma):=2\maj(\sigma)+\nega(\sigma)$, where $\maj(\sigma)$ is the major index of the sequence $(\sigma(1),\dots,\sigma(n))$ with respect to the order $-1<\cdots<-n<1<\cdots<n$, and $\nega(\sigma)$ is the number negative elements in the sequence.  Adin--Gessel--Roichman obtained the following type-B analogue of (\ref{eq:Gessel-Simion})
\begin{equation} \label{eqn:AGR}
\sum_{\sigma\in B_n} \sign(\sigma)q^{\fmaj(\sigma)} =[2]_{-q}[4]_q\cdots [2n]_{(-1)^{n}q}. 
\end{equation} 
In the realm of parabolic quotients of Coxeter groups, we are interested in whether our main results can be extended to the signed permutations in $B_n$ with subsequence restrictions, on the basis of (\ref{eqn:AGR}).






% \section*{Appendix}

%----------------------------------------------------






% \section*{Acknowledgements.}


\printbibliography



\end{document}
