%%%%%%%%%%%%%% Latex file, produces 22pp manuscript
%% El-JC submission, ftp-ed to ftp.cis.upenn.edu pub/e-jc/incoming
%% with email to Herb Wilf, Sept. 3, 1999
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%---------------------------------------------------------------------
\documentclass[12pt]{article}
\usepackage{latexsym}
\usepackage[dvips]{epsfig}
\newcommand{\Bbb}{\bf}
\newcommand{\C}{\bf C}
\newcommand{\N}{\bf N}
\newcommand{\Q}{\bf Q}
\newcommand{\R}{\bf R}
\setlength{\topmargin}{0cm}
\setlength{\oddsidemargin}{-0.2cm}
\setlength{\evensidemargin}{-0.2cm}
\textwidth 6.2in
\textheight 8.6in
\newcommand{\Nnn}{{\Bbb N}}
\newcommand{\Cnn}{{\Bbb C}}
\renewcommand{\baselinestretch}{1.0}
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 7 (2000), \#R9\hfill}
\thispagestyle{empty}
\newcommand{\bigcenter}[1]{\begin{center} {\Large\bf #1} \end{center}}
\newcommand{\qed}{\mbox{$\Diamond$}\vspace{\baselineskip}}
\newcommand{\ler}{left-to-right }
\newcommand{\ril}{right-to-left }
\newtheorem{theorem}{Theorem}
\newtheorem{conjecture}{Conjecture}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{definition}{Definition}
\newtheorem{corollary}{Corollary}
\newtheorem{example}{Example}
\newtheorem{observation}{Observation}
\newenvironment{proof}{\noindent {\bf Proof:}}{{\qed}}
\newcommand{\df}{\stackrel{\mbox{\rm def }}{=}}
\newcommand{\di}{\displaystyle}
%\newcommand{\bigtimes}[1]{{{\large\times}\atop {#1}}}
\newcommand{\bl}[2]{{\left\langle #1 \:\: \vrule \:\: #2 \right\rangle}}
\newcommand{\fact}[2]{{^{\di #1}\left/ _{\di #2}\right.} }
% \newcommand{\rest}[2] {#1\left| {_{#2}}\right. }
\newcommand{\vanish}[1]{}
\newcommand{\prek}{$P$-recursive }
\newcommand{\cov}{<\!\!\!\!\cdot\ }
\parskip=12pt
\begin{document}
\title{Combinatorial statistics on type-B analogues\\
of noncrossing partitions and restricted permutations}
\author{Rodica Simion\thanks
{Partially supported by the National Science Foundation,
award DMS-9970957.}
\\
Department of Mathematics\\
The George Washington University\\
Washington, DC 20052}
%%%\thanks
%%%{Partially supported by the National Science Foundation,
%%%award DMS-9970957.}
\date{Submitted: September 5, 1999; Accepted: January 5, 2000}
\maketitle
\bigskip
\begin{abstract}
We define type-B analogues of combinatorial statistics previously studied on
noncrossing partitions and show that analogous equidistribution and symmetry
properties hold in the case of type-B noncrossing partitions. We also
identify pattern-avoiding classes of elements in the hyperoctahedral group
which parallel known classes of restricted permutations with respect to
their relations to noncrossing partitions.
\smallskip
{\bf Key words:} restricted permutations, pattern-avoidance,
noncrossing partitions, signed permutations, permutation statistics,
partition statistics, $q$-analogue
\smallskip
{\bf AMS Classification:} 05
\end{abstract}
\vfill
\noindent\textit
{This paper was dedicated by the author to George Andrews on the occasion of
his 60th birthday. We are very sad to report that Rodica Simion died
on January 7, 2000, just two days after the acceptance of this paper.
We have made the few minor changes \hbox{requested} by the referee and
are honored to present her paper~here. -- The Editors\\
}
\newpage
\section{Introduction}\label{sec-Intro}
The goal of this paper is to give type-B analogues of enumerative
results concerning combinatorial statistics defined on (type-A)
noncrossing partitions and on certain classes of permutations characterized
by pattern-avoidance. To this end, we need B-analogues of the combinatorial
objects in question. As type-B noncrossing partitions we use those studied
by Reiner \cite{Reiner-NCB}. In the hyperoctahedral group, the natural
B-analogue of the symmetric group, we identify classes of restricted signed
permutations with enumerative properties analogous to those
of the 132- and 321-avoiding
permutations in the symmetric group. We also propose definitions for four
partition statistics (${\rm ls}^B, {\rm lb}^B, {\rm rs}^B$, and ${\rm
rb}^B$) as type-B analogues, for noncrossing partitions, of the established
statistics ${\rm ls}, {\rm lb}, {\rm rs}, {\rm rb}$ for type A. We show
that these choices yield B-analogues of results which hold for type A.
In the remainder of this section we give a brief account of earlier work which
motivated our investigation, summarize the main results,
and establish the basic definitions and
notation used throughout the paper.
The lattice $NC^A_n$ of (type-A) noncrossing partitions of an $n$-element
set, whose investigation was
initiated by Kreweras \cite{kreweras}, turns out to support and to be
related to a remarkable range of interesting topics.
As a poset, it enjoys elegant enumerative and structural properties
(see, e.g., \cite{Ed1}, \cite{Ed2}, \cite{EdSi}, \cite{kreweras},
\cite{NicaSpei}, \cite{SiU}),
and properties of interest in algebraic combinatorics
(e.g., \cite{Montenegro}, \cite{St-NCact}).
The natural connection between noncrossing partitions and other
combinatorial objects counted by the Catalan numbers leads to relations of
$NC^A_n$ with many aspects of enumerative combinatorics, as well as problems
arising in geometric combinatorics, probability theory, topology,
and mathematical biology (a brief account and references appear in
\cite{Si-NCsurvey}).
Type-B noncrossing partitions of an $n$-element set, whose collection we
denote by $NC^B_n$, were first considered by Montenegro \cite{Montenegro} and
systematically studied by Reiner \cite{Reiner-NCB}.
They enjoy a wealth of interesting properties which parallel those
for type A, from the standpoint of order structure, enumerative
combinatorics, algebraic combinatorics and geometric combinatorics
(see \cite{Hersh-NC}, \cite{Reiner-NCB}, \cite{Si-Bassoc}).
Here we extend the analogies between
$NC^A_n$ and $NC^B_n$ in the context of enumeration,
by exploring three topics.
\begin{enumerate}
\item{
{\em
Four combinatorial statistics defined on
type-B noncrossing partitions, how their distributions compare, and how they
relate to the order relation on $NC^B_n$.
}
Four combinatorial statistics ${\rm rb}^A, {\rm rs}^A, {\rm lb}^A, {\rm ls}^A$
defined for type-A set partitions in terms of restricted growth functions
have interesting equidistribution properties, \cite{WaWh},
on the entire set partition lattice $\Pi^A_n$, which also
hold on type-A noncrossing partitions \cite{Si-ncstats}, \cite{White-interp}.
In fact, the distributions of these statistics on $NC^A_n$ yield
$q$-analogues of the Catalan and Narayana numbers which reflect nicely
the rank-symmetry and rank-unimodality of $NC^A_n$.
In Section \ref{sec-NCBstats} we propose and establish properties of
type-B analogues of these four statistics, applicable to $NC^B_n$.
Our definitions of
${\rm rb}^B, {\rm rs}^B, {\rm lb}^B, {\rm ls}^B$ on $NC^B_n$
are modeled on descriptions given in \cite{Si-ncstats} for the values
of the type-A statistics on $NC^A_n$. We show that, as in the case of
type-A, ${\rm rs}^B$ and ${\rm lb}^B$ are equidistributed on each rank of
$NC^B_n$. The same holds for ${\rm ls}^B$ and ${\rm rb}^B$. The two
$q$-analogues of the Whitney numbers ${n \choose k}^2_k$ of $NC^B_n$
obtained from these two pairs of statistics,
$NC^B_{n,k}(q)$ and $NC^{*B}_{n,k}(q)$, reflect the rank-symmetry and
unimodality of $NC^B_n$:
\begin{eqnarray}
{1 \over {q^k}} NC^B_{n,k}(q)
\ = \ {1 \over {q^{n-k}}} NC^B_{n,n-k}(q), \\
{1 \over {q^{k\choose 2}}} NC^{*B}_{n,k}(q)
\ = \ {1 \over {q^{{n-k} \choose 2}}} NC^{*B}_{n,n-k}(q).
\end{eqnarray}
The rank-symmetry of these distributions is apparent from their expressions
(corollaries \ref{cor-lbrs-form} and \ref{cor-lsrb-form}),
and can be seen directly combinatorially. Also analogously to type A,
finer distribution properties
hold in relation to the order structure on $NC^B_n$:
we exhibit a decomposition of $NC^B_n$ into symmetrically embedded
boolean lattices, such that
the second pair of statistics is essentially constant on each boolean
lattice occurring in the decomposition.
A by-product of our explicit decomposition of $NC^B_n$ into
symmetrically embedded boolean lattices (different from those considered
in \cite{Hersh-NC}, \cite{Reiner-NCB}), is a type-B analogue
of Touchard's formula for the Catalan numbers,
\begin{equation}
{ {2n} \choose n } \ = \ \sum_{k=0}^n
{ {n \choose {2k}} {{2k} \choose k} 2^{n-2k} },
\end{equation}
along with a combinatorial, order-theoretic, proof.
}
\item{
{\em
Subsets of the hyperoctahedral group characterized by pattern-avoidance
conditions.
}
In the symmetric group, for every 3-letter pattern $\rho$ the number of
$\rho$-avoiding permutations is given by the Catalan number \cite{Knuth};
hence, the same as the number of type-A noncrossing partitions. Other
enumeration questions, for permutations which avoid simultaneously several
3-letter patterns, are treated in \cite{SiSch}. Are there similar results
for the hyperoctahedral group?
In Section \ref{sec-Brhos} we investigate enumerative properties of
several classes of restricted signed permutations. The pattern restrictions
consist of avoiding 2-letter signed patterns.
We show that every 2-letter pattern is avoided by equally many signed
permutations in the hyperoctahedral group. These are more numerous than
the type-B noncrossing partitions, namely,
$\sum_{k=0}^n{ {n \choose k}^2 k! }$ in the hyperoctahedral group $B_n$.
A $q$-analogue of this expression appears in work of Solomon \cite{Sol},
in connection with a Bruhat-like decomposition of the monoid of $n \times n$
matrices over a field with $q$ elements.
Solomon defines a length function on
the orbit monoid such that its distribution over rank-$k$
matrices is given by
$\left[ {n \atop k} \right]^2_q [k]_q!$.
This same expression can be viewed in our context as the distribution of a
combinatorial statistic on a class of pattern-avoiding signed permutations.
We treat also the enumeration of signed permutations avoiding two
2-letter patterns at the same time.
Among such double pattern restrictions
we identify four classes whose cardinality is equal to
${{2n}\choose n} = \# NC^B_n$. They are the signed permutations which avoid
simultaneously the patterns $21$ and ${\overline{2}}\ {\overline{1}}$, and
three additional classes readily related to this one by means of reversal and
barring operations.
We note that a different class of ${2n} \choose n$ elements of the
hyperoctahedral group $B_n$, the set of top fully commutative elements,
appears in work of Stembridge including \cite{Stemb-FC3}.
}
\item{
{\em
Partition statistics applied to $NC^B_n$
vs. permutation statistics applied to pattern-avoiding signed permutations.
}
In type-A, the classes $S_n(132)$ and $S_n(321)$ of $132$- and
$321$-avoiding permutations in the symmetric group $S_n$
are not only equinumerous with
$NC^A_n$, but we have equidistribution results \cite{Si-ncstats}
relating permutation and set partition statistics (the definitions of
these statistics are given in the next subsection):
\begin{equation}\label{eq-NCAroA}
\sum_{\sigma\in S_n(132)}{p^{ {\rm des}^A(\sigma) +1} q^{{\rm maj}^A(\sigma)}}
\ = \
\sum_{\sigma\in S_n(321)}{p^{ {\rm exc}^A(\sigma) +1} q^{{\rm Den}^A(\sigma)}}
\ = \
\sum_{\pi \in NC^A_n}{ p^{ {\rm bk}^A(\pi)} q^{ {\rm rb}^A(\pi)}}.
\end{equation}
In Section \ref{sec-NCBroB} we establish a type-B counterpart of
(\ref{eq-NCAroA}) relating partition statistics applied to $NC^B_n$ and
permutation statistics applied to $B_n(21, {\overline{2}}\ {\overline{1}})$.
}
\end{enumerate}
The proofs rely on direct combinatorial methods and explicit
bijections.
The final section of the paper consists of remarks and problems for further
investigation.
\subsection{Definitions and notation}\label{subsec-def}
We will write $[n]$ for the set $\{ 1, 2, \dots , n \}$ and
$\# X$ for the cardinality of a set $X$.
In a partially ordered set, we will write $x \cov y$ if $x$ is covered by
$y$ (i.e., $x < y$ and there is no element $t$ such that $x < t < y$).
The $q$-analogue of the integer $m \ge 1$ is
$ [m]_q \colon = 1 + q + q^2 + \cdots + q^{m-1}$.
The $q$-analogue of the factorial is then
$[m]_q! \colon = [1]_q [2]_q \cdots [m]_q$ for $m \ge 1$, integer,
and $[0]_q! \colon = 1$. Finally, the $q$-binomial coefficient is
$\left[ {m \atop k} \right]_q \colon =
{ { [m]_q! }\over { [k]_q! [m-k]_q! }}$.
\paragraph{Noncrossing partitions of type A, $NC^A_n$.}\label{par-NCA}
A partition $\pi$ of the set $[n]$ is, as usual,
an unordered family of nonempty, pairwise disjoint sets
$B_1,B_2,\cdots ,B_k$ called {\em blocks}, whose union is $[n]$.
Ordered by refinement (i.e., $\pi \leq \pi'$ if each block of $\pi'$ is a
union of blocks of $\pi$), the partitions of $[n]$ form a partially ordered
set which is one of the classical examples of a geometric lattice.
We denote the set of partitions of $[n]$ by $\Pi^A_n$ since it is isomorphic
to the lattice of intersections of the type-A hyperplane arrangement in
${\bf R}^n$ (consisting of the hyperplanes $x_i = x_j$ for $1 \leq i < j
\leq n$). The set of partitions of $[n]$ having $k$ blocks is denoted by
$\Pi^A_{n,k}$.
A partition $\pi \in \Pi^A_n$ is a {\em (type-A) noncrossing
partition} if there are no four elements $1 \leq a** 0$ for every
choice of $1 \leq p < q \leq k$. In other words, $\sigma$ avoids the
pattern $\rho$ if it contains no subsequence of $k$ values among which the
magnitude relation is, pairwise, the same as for the corresponding values in
$\rho$.
We will write $S_n(\rho)$ for the set of $\rho$-avoiding permutations in
$S_n$, and $|\rho|=k$ to indicate that the {\em length of the pattern}
$\rho$ is $k$.
For example, $\sigma = 3 4 1 2 5$ belongs to $S_5(321) \cap S_5(132)$,
and contains every other 3-letter pattern; for example,
it contains the pattern $\rho = 213$ (in fact,
four occurrences of it: $315, 325, 415, 425$).
Classes of restricted permutations arise naturally in theoretical
computer science in connection with sorting problems (e.g., \cite{Knuth},
\cite{Tarjan}), as well as in the context of combinatorics related to
geometry (e.g., the theory of Kazhdan-Lusztig polynomials \cite{Brenti-KL}
and Schubert varieties \cite{Gash},\cite{Billey}).
Recent work on pattern-avoiding
permutations from an enumerative and algorithmic point of view includes
\cite{Barc}, \cite{Bona}, \cite{ChowWest}, \cite{DuGiWe},
\cite{NoonanZeil}, \cite{West}.
Trivially, if $|\rho|=2$ then $S_n(\rho)$ consists of only one permutation
(either the identity or its reversal). For length-3 patterns, it turns out
that $S_n(\rho)$ has the same cardinality, independently of the choice of
$\rho \in S_3$ (see \cite{Knuth}, \cite{SiSch}). The common cardinality
is the $n$th Catalan number,
\begin{equation}\label{eq-Snrho}
\# S_n(\rho) = C_n = {1 \over {n+1}}{{2n} \choose n} \ \
{\rm \ for \ every \ } \rho \in S_3.
\end{equation}
That is, $\# S_n(\rho) = \# NC^A_n$ for each pattern $\rho \in S_3$ and
every $n$.
\paragraph{Restricted signed permutations.}
We will view the elements of the hyperoctahedral group $B_n$ as signed
permutations written as words of
the form $b = b_1 b_2 \dots b_n$ in which each of the symbols $1, 2, \dots,
n$ appears, possibly barred. Thus, the cardinality of $B_n$ is
$n! 2^n$. The barring operation represents a sign-change, so it is an
involution, and the absolute value notation (as earlier for type-B
partitions) means $|b_j| = b_j$ if the symbol $b_j$ is not barred, and
$|b_j| = {\overline{b_j}}$ if $b_j$ is barred.
Let $\rho \in B_k$.
The set $B_n(\rho)$ of {\em $\rho$-avoiding signed permutations} in $B_n$
consists of those $b \in B_n$ for which there is no sequence of $k$ indices,
$1 \leq i_1 < i_2 < \cdots < i_k \leq n$ such that two conditions hold:
(1) $b$ with all bars removed contains the pattern $\rho$ with all bars
removed, i.e.,
$( |b_{i_p}| - |b_{i_q}|)(|\rho_{p}| - |\rho_{q}|) > 0$ for all $1
\leq p < q \leq k$; and
(2) for each $j$, $1 \leq j \leq k$, the symbol
$b_{i_j}$ is barred in $b$ if and only if $\rho_{j}$ is barred in $\rho$.
For example, $b = 3 {\overline{4}} 1 {\overline{2}} 5 \in B_5$
avoids the signed pattern $\rho = {\overline{1}}\ {\overline{2}}$
and contains all the other seven signed patterns of length 2;
among the length-3 signed patterns, it contains only
$\rho = 213,\ 2 {\overline{3}} 1,\ 1 {\overline{2}} 3,\
3 1 {\overline{2}}, \ 2 {\overline{3}}\ {\overline{1}}, \
{\overline{3}} 1 {\overline{2}}$, and ${\overline{2}}\ {\overline{1}} 3$.
\paragraph{Combinatorial statistics for type-A set partitions.}
We recall the definitions of four statistics of combinatorial
interest defined for set partitions
(see \cite{WaWh} and its bibliography for earlier related work).
Given a partition $\pi \in \Pi^A_n$, index its blocks in increasing order of
their minimum elements and define the {\em restricted growth function} of
$\pi$ to be the $n$-tuple $w(\pi) = w_1 w_2 \cdots w_n$ in which the value of
$w_i$ is the index of the block of $\pi$ which contains the element $i$.
Thus, if $\pi = \{ 1, 5, 6 \} \{ 2, 3, 8 \} \{ 4, 7 \}$, then
its restricted growth function is $w(\pi) = 1 2 2 3 1 1 3 2$.
Let ${\rm ls}^A(\pi, i)$ denote the number of distinct values occurring
in $w(\pi)$ to the left of $w_i$ and which are smaller than $w_i$,
\begin{equation}\label{eq-lsi}
{\rm ls}^A(\pi, i) \colon = \# \{ w_j \colon \ 1 \leq j < i, w_j < w_i \}.
\end{equation}
Similarly, ``left bigger,'' ``right smaller,'' and ``right bigger'' are
defined for each index $1 \leq i \leq n$:
\begin{equation}\label{eq-lbi}
{\rm lb}^A(\pi, i) \colon = \# \{ w_j \colon \ 1 \leq j < i, w_j > w_i \},
\end{equation}
\begin{equation}\label{eq-rsi}
{\rm rs}^A(\pi, i) \colon = \# \{ w_j \colon \ i < j \leq n, w_j < w_i \},
\end{equation}
\begin{equation}\label{eq-rbi}
{\rm rb}^A(\pi, i) \colon = \# \{ w_j \colon \ i < j \leq n, w_j > w_i \}.
\end{equation}
Now the statistics of interest are obtained by summing the
contributions of the individual entries in the restricted growth function of
$\pi$:
\begin{equation}\label{eq-lslbA}
{\rm ls}^A(\pi) \colon = \sum_{i=1}^n { {\rm ls}^A(\pi, i) }, \ \ \
{\rm lb}^A(\pi) \colon = \sum_{i=1}^n { {\rm lb}^A(\pi, i) },
\end{equation}
\begin{equation}\label{eq-rsrbA}
{\rm rs}^A(\pi) \colon = \sum_{i=1}^n { {\rm rs}^A(\pi, i) }, \ \ \
{\rm rb}^A(\pi) \colon = \sum_{i=1}^n { {\rm rb}^A(\pi, i) }.
\end{equation}
The distributions of these statistics over $\Pi^A_n$ and
$\Pi^A_{n,k}$ give $q$-analogues of the $n$th Bell number and
of the Stirling numbers of the second kind. One of the interesting
properties established combinatorially in \cite{WaWh} is that
the four statistics fall into two pairs,
$\{ {\rm ls}^A, {\rm rb}^A \}$ and
$\{ {\rm lb}^A, {\rm rs}^A \}$, with equal distributions on
$\Pi^A_{n,k}$, for every $n, k$.
In establishing similar results about the distributions over just
noncrossing partitions, the following alternative expressions
were useful in \cite{Si-ncstats} (Lemmas 1.1, 1.2, 2.1, 2.2).
Later in this paper, we will define type-B analogues of the four
statistics, modeled after these expressions.
\hfil\break\indent
For any partition $\pi \in \Pi^A_{n,k}$,
\begin{equation}\label{eq-lsA-alt}
{\rm ls}^A(\pi) = \sum_{i=1}^k{ (i-1) \# B_i},
\end{equation}
\begin{equation}\label{eq-lbA-alt}
{\rm lb}^A(\pi) = k(n+1) - \sum_{i=1}^k{ i \# B_i} - \sum_{i=1}^k{ m_i }.
\end{equation}
For any noncrossing partition $\pi \in NC^A_{n,k}$,
\begin{equation}\label{eq-rsA-alt}
{\rm rs}^A(\pi) = \sum_{i=1}^k{M_i} - \sum_{i=1}^k{m_i} - n + k,
\end{equation}
\begin{equation}\label{eq-rbA-alt}
{\rm rb}^A(\pi) = \sum_{i=1}^k{m_i} - k.
\end{equation}
In these expressions, the blocks are indexed in increasing order of their
minima, and $m_i, M_i$ denote the minimum and the maximum elements of
the $i$th block.
\paragraph{Combinatorial statistics for permutations and signed
permutations.}
Two classical permutation statistics are the number of descents and the
major index of a permutation (see, e.g., \cite{EC1}).
We recall their definitions.
If $\sigma = \sigma_1 \sigma_2 \cdots \sigma_n \in S_n$,
then its {\em descent set} is ${\rm Des}^A(\sigma) \colon =
\{ i \in [n-1] \ \colon \ \sigma_i > \sigma_{i+1} \}$.
The {\em descent statistic} and the {\em major index statistic} of $\sigma$
are
\begin{equation}\label{eq-des-maj-A}
{\rm des}^A(\sigma) \colon = \# {\rm Des}^A(\sigma),
\ \ \ \
{\rm maj}^A(\sigma) \colon = \sum_{i \in {\rm Des}^A(\sigma)} {i}.
\end{equation}
Pairs of permutation statistics whose joint distribution over $S_n$
coincides with that of ${\rm des}^A$ and ${\rm maj}^A$,
$\sum_{\sigma \in S_n}{p^{{\rm des}^A(\sigma)} q^{{\rm maj}^A(\sigma)}}$,
are called Euler-Mahonian. A celebrated Euler-Mahonian pair is
that obtained from excedences and Denert's statistic (see, e.g.,
\cite{FoZeil}), which are defined as follows.
The {\em set of excedences} of $\sigma \in S_n$ is
${\rm Exc}^A(\sigma) \colon = \{ i \in [n] \ \colon \ \sigma_i > i \}$
and the {\em excedence statistic} is given by
\begin{equation}\label{eq-excA}
{\rm exc}^A(\sigma) \colon = \# {\rm Exc}^A(\sigma).
\end{equation}
The original definition of Denert's statistic was given a compact equivalent
form by Foata and Zeilberger. Write $\sigma_{\rm Exc}$ for the
word $\sigma_{i_1} \sigma_{i_2} \cdots \sigma_{i_{{\rm exc}^A(\sigma)}}$,
where each $i_j \in {\rm Exc}^A(\sigma)$. That is, the subsequence in
$\sigma$ consisting of the values which produce excedences.
Similarly write $\sigma_{\rm NExc}$ for the complementary subsequence in
$\sigma$. For example, if $\sigma = 4 2 1 5 3$,
then ${\rm Exc}^A(\sigma) = \{ 1, 4 \}$,
$\sigma_{\rm Exc} = 4 5$ and $\sigma_{\rm NExc} = 2 1 3$.
Then, based on \cite{FoZeil}, the {\em Denert statistic} is given by
\begin{equation}\label{eq-DenA}
{\rm Den}^A(\sigma) \colon = {\rm inv}^A(\sigma_{{\rm Exc}})
+ {\rm inv}^A(\sigma_{{\rm NExc}}) + \sum_{i \in {\rm Exc}^A(\sigma)}{i},
\end{equation}
where ${\rm inv}$ denotes the number of inversions.
In our earlier example, we obtain
${\rm Den}^A(4 2 1 5 3) = 0 + 1 + (1 + 4) = 6$.
We will be interested in type-B analogues of these permutation statistics.
We say that $b = b_1 b_2 \dots b_n \in B_n$
has a {\em descent} at $i$, for $1 \leq i \leq n-1$, if $b_i > b_{i+1}$ with
respect to the total ordering
$1 < 2 < \cdots < n < {\overline{n}} < \cdots < {\overline{2}} <
{\overline{1}}$, and that it has a descent at $n$ if $b_n$ is barred.
As usual, the {\em descent set} of $b$, denoted ${\rm Des}^B(b)$, is the set
of all $i \in [n]$ such that $b$ has a descent at $i$.
For example, for
$b = 2 {\overline{ 1}} {\overline{3}} 5 4 7 {\overline{ 6}}$
we have ${\rm Des}^B(b) = \{ 2, 3, 4, 7 \}$.
The type-B descent and major index statistics are
\begin{equation}\label{eq-des-maj-B}
{\rm des}^B(b) \colon = \# {\rm Des}^B(b), \ \ \
{\rm maj}^B(b) \colon = \sum_{i \in {\rm Des}^B(b)}{i}.
\end{equation}
For signed permutations, more than one notion of excedence appears in the
literature (see \cite{Stein}), from which we will use the following.
Given $b = b_1 b_2 \cdots b_n \in B_n$, let $k$ be the number of
symbols in $b$ which are not barred. Consider the permutation
$\sigma^b \in S_{n+1}$ defined by
$\sigma^b_{n+1} = k+1$ and, for each $1 \leq i \leq n$,
$\sigma^b_i = j$ if $b_i$ is the $j$th smallest element in the ordering
$1 < 2 < \cdots < n < n+1 < {\overline{1}} < {\overline{2}} < \cdots <
{\overline{n}}$.
Then, following \cite{Stein},
\begin{equation}\label{eq-BExc-def}
{\rm Exc}^B(b) \colon =
{\rm Exc}^A(\sigma^b), \ \ \ {\rm exc}^B(b) = \# {\rm Exc}^B(b),
\end{equation}
and we define
\begin{equation}\label{eq-BDen-def}
{\rm Den}^B(b) = {\rm Den}^A(\sigma^b).
\end{equation}
\newpage
\section{Statistics on type-B noncrossing partitions}\label{sec-NCBstats}
We begin by defining B-analogues of the set partition statistics described
in section \ref{subsec-def}, valid for noncrossing partitions of type B.
\subsection{The statistics ${\rm ls}^B, {\rm lb}^B, {\rm rs}^B, {\rm rb}^B$}
\label{subsec-stats-def}
In the correspondence $\pi \leftrightarrow (L(\pi), R(\pi))$
between $NC^B_n$ and pairs of equal-size subsets of $[n]$,
the elements of $L(\pi)$ and $R(\pi)$ indicate the Left and Right delimiters of
the non-zero blocks. Hence, they can be viewed as analogous to the minimum
and maximum elements of the blocks of a type-A noncrossing partition.
This suggests the following adaptation of the definitions
(\ref{eq-lsA-alt})-(\ref{eq-rbA-alt}), to obtain type-B analogues of
the four statistics applicable to $NC^B_n$:
\begin{equation}\label{eq-lsB}
{\rm ls}^B(\pi) \colon =
\sum_{i=1}^{{\rm bk}^B(\pi)+1}{(i-1) \# B_i},
\end{equation}
\begin{equation}\label{eq-lbB}
{\rm lb}^B(\pi) \colon = (n+1) {\rm bk}^B(\pi)
- \sum_{i=1}^{{\rm bk}^B(\pi)+1}{ i \# B_i }
- \sum_{l \in L(\pi)} {l},
\end{equation}
\begin{equation}\label{eq-rsB}
{\rm rs}^B(\pi) \colon = \sum_{r \in R(\pi)}{r} - \sum_{l \in L(\pi)}{l} - n
+ {\rm bk}^B(\pi),
\end{equation}
\begin{equation}\label{eq-rbB}
{\rm rb}^B(\pi) \colon = \sum_{l \in L(\pi)}{l} - {\rm bk}^B(\pi),
\end{equation}
where $B_i$ is the block of $\pi$ containing the $i$th smallest element of
$L(\pi)$, and $B_{{\rm bk}^B(\pi) + 1}$ is the set of unbarred symbols in
the zero-block.
For example, for $\pi = \{ 1 \} \{ {\overline{1}} \}
\{ 2, 3, {\overline{8}} \} \{ {\overline{2}}, {\overline{3}}, 8 \}
\{ 4, 5 \} \{ {\overline{4}}, {\overline{5}} \}
\{ 9 \} \{ {\overline{9}} \} \{ 6, {\overline{6}}, 7, {\overline{7}} \}$,
we have $(L(\pi), R(\pi)) = (\{ 1, 4, 8, 9 \}, \{ 1, 3, 5, 9 \})$, and
${\rm bk}^B(\pi) = 4$. The indexed blocks are
$B_1 = \{ 1 \}, B_2 = \{ 4, 5 \}, B_3 = \{ 8, {\overline{2}},
{\overline{3}}\}, B_4 = \{ 9 \}$, and from the zero-block we obtain
$B_5 = \{ 6, 7 \}$.
Therefore,
${\rm rs}^B(\pi) = 18 - 22 - 9 + 4 = -9$,
${\rm rb}^B(\pi) = 22 - 4 = 18$,
${\rm ls}^B(\pi) = 0 + 2 + 6 + 3 + 8 = 19$, and
${\rm lb}^B(\pi) = 10 \cdot 4 - (1 + 4 + 9 + 4 + 10) - 22 = -10$.
Note that ${\rm rs}^B$ and ${\rm lb}^B$ may assume negative values.
It is easy to see that ${\rm rs}^B$ assumes the values between $-(k+1)(n-k)$
and $(k-1)(n-k)$. As we will see in the next subsection, ${\rm lb}^B$ has the
same distribution as ${\rm rs}^B$ on every rank of $NC^B_n$,
so this is its range as well.
The definitions of these statistics could be easily modified
to produce only nonnegative values.
\subsection{Two equidistribution results}\label{subsec-NCBequi}
As in the type-A case, we have two pairs of statistics
-- $({\rm lb}^B, {\rm rs}^B)$ and $({\rm ls}^B, {\rm rb}^B)$ --
which are equidistributed on each rank of $NC^B_n$. The results of this
subsection show that each of the two pairs of statistics satisfy finer
distribution properties with respect to the order relation on $NC^B_n$.
\begin{theorem}\label{thm-lbrsBequi}
For each $n >0$ and $0 \leq k \leq n$, there is
a bijection $\varphi \colon NC^B_{n,k} \to NC^B_{n,k}$
such that ${\rm lb}^B(\pi) = {\rm rs}^B(\varphi(\pi))$ and
$L(\pi) = L(\varphi(\pi))$. Therefore, for every $L \subseteq [n]$,
we have
\begin{equation}
\sum_{\pi \in NC^B_{n,k}(L)}{q^{ {\rm lb}^B(\pi)}} \ = \
\sum_{\pi \in NC^B_{n,k}(L)}{q^{ {\rm rs}^B(\pi)}},
\end{equation}
where $NC^B_{n,k}(L)$ is the collection of type-B noncrossing partitions of
$[n]$ having $k$ pairs of non-zero blocks and Left-set $L$.
\end{theorem}
\begin{proof}
Given $\pi \in NC^B_n$ with $k$ pairs of non-zero blocks,
we will define the desired partition $\varphi(\pi)$ by specifying its
Left- and Right-sets.
The Left-set is the same as for $\pi$,
$L(\varphi(\pi)) = L(\pi)$. The Right-set $R(\varphi(\pi))$
consists of the partial sums of the sizes of the (non-zero) blocks of $\pi$
which contain the elements of $L$:
$R(\varphi(\pi)) \colon =
\{ \sum_{j=1}^{i}{\# B_j}, \ 1 \leq i \leq {\rm bk}^B(\pi) \}$.
For the partition in the preceding example
(end of subsection \ref{subsec-stats-def}), we obtain
$R(\varphi(\pi)) = \{ 1, 3, 6, 7 \}$ and
$\varphi(\pi) = \{ 1 \} \{ {\overline{1}} \}
\{ 2, 3, {\overline{9}} \} \{ {\overline{2}}, {\overline{3}}, 9 \}
\{ 4, 5, 6 \} \{ {\overline{4}}, {\overline{5}}, {\overline{6}} \}
\{ 7, {\overline{8}} \} \{ {\overline{7}}, 8 \}$.
To check that ${\rm rs}^B(\varphi(\pi)) = {\rm lb}^B(\pi)$, note
that if, given $n$, we prescribe the Left-set $L$,
and thus the number ${\rm bk}^B$ of non-zero blocks, then by the
definitions (\ref{eq-lbB}) and (\ref{eq-rsB}), it suffices to show that
$( {\rm bk}^B(\pi) + 1) n - \sum_{i=1}^{{\rm bk}^B(\pi) + 1}{i \# B_i} =
\sum_{r \in R(\varphi(\pi))}{r}$. This can be easily verified by a direct
calculation.
It remains to verify that $\varphi$ is invertible.
We consider a partition $\pi' \in NC^B_{n,k}(L)$ and we
construct a partition $\pi \in NC^B_{n,k}(L)$ such that
$\varphi(\pi) = \pi'$.
Let the elements of $L(\pi') = L$ and $R(\pi')$ be
$1 \leq l_1 < l_2 < \cdots < l_k \le n$
and $1 \leq r_1 < r_2 < \cdots < r_k \leq n$, respectively.
Define $b_1 \colon = r_1$ and $b_i = r_i - r_{i-1}$ for $i=2, \dots, k$.
Note that there exists at least one index $i$ such that
$b_i \leq l_{i+1} - l_i$, where we set $l_{k+1} = n + l_1$, since
otherwise we would have $r_k = b_1 + b_2 + \cdots + b_k > n$.
For such an index $i$, let a total of $b_i$ clockwise consecutive elements
beginning with $l_i$ constitute a block of the partition $\pi$. Since each
$b_i$ is no larger than $n$, this is a non-zero block.
Apply the bar operation to obtain the required pair of non-zero blocks
in $\pi$.
Now this process is repeated, with suitable adjustments:
elements of $\{ 1, \dots, n,
{\overline{1}}, \dots, {\overline{n}} \}$ which have already been assigned
to some block of $\pi$ are skipped when checking for clockwise consecutive
elements.
It is easy to see that the partition $\pi$ whose non-zero blocks are produced
in this way lies in $NC^B_{n,k}(L)$ and $\varphi(\pi) = \pi'$.
\end{proof}
Consequently, for each $n, k$,
the statistics ${\rm lb}^B$ and ${\rm rs}^B$ give rise to the
same $q$-analogue of ${n \choose k}^2$.
\begin{corollary}\label{cor-lbrs-form}
The common distribution of the statistics ${\rm lb}^B$ and ${\rm rs}^B$
over type-B noncrossing partitions of $[n]$ having $k$ pairs of
non-zero blocks is given by:
\begin{equation}\label{eq-lbrsBform}
NC^B_{n,k}(q) \ \colon = \
\sum_{\pi \in NC^B_{n,k}}{q^{ {\rm lb}^B(\pi)}} \ = \
\sum_{\pi \in NC^B_{n,k}}{q^{ {\rm rs}^B(\pi)}} \ = \
q^{-(k+1)(n-k)} \left[ {n \atop k} \right]^2_q.
\end{equation}
\end{corollary}
\begin{proof}
The preceding theorem implies the equidistribution of
${\rm lb}^B$ and ${\rm rs}^B$ on each rank of $NC^B_n$. The definition
(\ref{eq-rsB}) of ${\rm rs}^B$ is especially convenient for
calculating the polynomial $NC^B_{n,k}(q)$:
\begin{eqnarray*}
NC^B_{n,k}(q)
& = & \sum_{\pi \in NC^B_{n,k}}{q^{ {\rm rs}^B(\pi)}} \\
& = & q^{-n + k} \sum_{ { L,R \in [n]}\atop{\# L = \# R = k}}
{ q^{\sum_{r\in R}{r} - \sum_{l\in L}{l}} } \\
& = & q^{-n +k} \left( \left[ {n \atop k} \right]_q q^{ {k+1}\choose 2}
\right)
\left( \left[ {n \atop k} \right]_{q^{-1}}
q^{- { {k+1}\choose 2}} \right).
\end{eqnarray*}
The last equality follows from the independence of $L$ and $R$,
and standard properties of $q$-binomial coefficients.
We can take advantage of the well-known fact that
$\left[ {n \atop k} \right]_q$ is a polynomial in $q$ of degree $k(n-k)$,
with non-zero constant term, and whose coefficients form a symmetric
sequence, to write $\left[ {n \atop k} \right]_{q^{-1}}$ in terms of (the
reciprocal of) $\left[ {n \atop k} \right]_q$. This leads to the desired
formula for $NC^B_{n,k}(q)$.
\end{proof}
The other two statistics are equidistributed on each rank of
$NC^B_n$ in an even stronger sense: we can exhibit an involution which
preserves rank and interchanges the values of ${\rm ls}^B$ and
${\rm rb}^B$.
\begin{theorem}\label{thm-lsrbBequi}
For each $n >0$ and $0 \leq k \leq n$, there is
a bijection $\psi \colon NC^B_{n,k} \to NC^B_{n,k}$
such that ${\rm ls}^B(\pi) = {\rm rb}^B(\psi(\pi))$ and
${\rm rb}^B(\pi) = {\rm ls}^B(\psi(\pi))$.
\end{theorem}
\begin{proof}
First note that if $k=0$, then we have
all elements in the zero-block. For this partition, both
${\rm ls}^B$ and ${\rm rb}^B$ vanish, and we let $\psi$ fix it.
Consider now the case when there are $k >0$ pairs of non-zero blocks, i.e.,
let $\pi \in NC^B_{n,k}$. Let
$l_1 < l_2 < \cdots < l_k$ be the elements of $L(\pi)$, and
$b_i$ be the cardinality of the (non-zero) block containing $l_i$, for $i =
1, \dots, k$. Let also $b_{k+1}$ be the number of unbarred elements in the
zero-block of $\pi$. Thus, $\sum_{i=1}^{k+1}{b_i} = n$.
Define two sequences, $\ell'$ and $b'$ whose entries are:
\begin{eqnarray*}\label{eq-lprime}
\ell'_1 & \colon = & 1 + b_{k+1} \\
\ell'_2 & \colon = & 1 + b_{k+1} + b_k \\
\vdots \\
\ell'_k & \colon = & 1 + b_{k+1} + b_k + \cdots + b_2 \\
\ell'_{k+1} & \colon = & n + 1 + b_{k+1}
\end{eqnarray*}
and
\begin{eqnarray*}\label{eq-bprime}
b'_1 & \colon = & n +1 - l_k \\
b'_2 & \colon = & l_k - l_{k-1} \\
\vdots \\
b'_k & \colon = & l_2 - l_1 \\
b'_{k+1} & \colon = & l_1 - 1.
\end{eqnarray*}
We claim that there is a unique partition in $NC^B_{n, k}$
whose Left-set is $\{ \ell'_i\ \colon \ 1 \leq i \leq k \}$
and such that the non-zero
block containing $\ell'_i$ has cardinality $b'_i$ for each $i=1, \dots, k$.
Indeed, every type-B noncrossing partition at rank $n-k < n$ has some non-zero
block consisting of contiguous elements in the circular diagram.
It is easy to see that there exists at least one index $i \in [k]$ for which
we have
\begin{equation}\label{eq-lbprime-inequ}
b'_i \leq \ell'_{i+1} - \ell'_i,
\end{equation}
since (by adding the relevant expressions above)
we have $b'_1 + b'_2 + \cdots + b'_k = n + 1 - l_1 \leq n$,
and
$\sum_{i=1}^{k}{ (\ell'_{i+1} - \ell'_i )} = n$.
For such an index $i$
we can make a block of $b'_i$ contiguous elements starting at
$\ell'_i$ and moving clockwise. Delete the elements of this block and
their images under
barring; remove $b'_i$ from the sequence $b'$; remove $\ell'_i$ from the
sequence $\ell'$; finally, replace $\ell'_m$ with
$\ell'_m - \ell'_i$ for each $m > i$. With these updated sequences replacing
$\ell'$ and $b'$, it is easy to check that some inequality of the form
(\ref{eq-lbprime-inequ}) holds again, and another pair of non-zero blocks is
obtained. The process terminates with a partition $\pi' \in NC^B_{n, k}$
and we set $\psi(\pi) = \pi'$.
For example, if $n=10$ and $k=5$ and if
$\pi = \{ 2 \} \{ {\overline{2}} \}
\{ 3, 5, {\overline{9}} \} \{ {\overline{3}}, {\overline{5}}, 9 \}
\{ 4 \} \{ {\overline{4}} \}
\{ 10, {\overline{1}} \} \{ {\overline{10}}, 1 \}
\{ 6, 8, {\overline{6}}, {\overline{8}} \}$,
then for $\pi$ we have
$(l_1, \dots, l_5) = (2, 4, 7, 9, 10)$ and
$(b_1, \dots, b_5, b_6) = (1, 1, 1, 3, 2, 2)$.
We obtain
$(\ell'_1, \dots, \ell'_5, \ell'_6) = (3, 5, 8, 9, 10, 13)$ and
$(b'_1, \dots, b'_5, b'_6) = (1, 1, 2, 3, 2, 1)$.
This leads to $\psi(\pi) = \pi' =
\{ 3 \} \{ {\overline{3}} \}
\{ 5 \} \{ {\overline{5}} \}
\{ 8, {\overline{6}} \} \{ {\overline{8}}, 6 \}
\{ 9, {\overline{2}}, {\overline{4}} \}
\{ {\overline{9}}, 2, 4 \}
\{ 10, {\overline{1}} \} \{ {\overline{10}}, 1 \}
\{ 7, {\overline{7}} \}$.
It is easy to verify that $\psi(\psi(\pi)) = \pi$ and that
${\rm rb}^B(\psi(\pi)) = {\rm ls}^B(\pi)$
and ${\rm ls}^B(\pi) = {\rm rb}^B(\psi(\pi))$.
In the example, we have
${\rm rb}^B(\pi) = {\rm ls}^B(\psi(\pi)) = 27$ and
${\rm ls}^B(\pi) = {\rm rb}^B(\psi(\pi)) = 30$.
\end{proof}
\begin{corollary}\label{cor-lsrb-form}
For every $n$, the statistics ${\rm ls}^B$ and ${\rm rb}^B$ are
equidistributed on each rank of $NC^B_n$. The common distribution
on partitions having $k$ pairs of non-zero blocks is
\begin{equation}\label{eq-lsrbBform}
NC^{*B}_{n,k}(q) \ = \
\sum_{\pi \in NC^B_{n,k}}{q^{ {\rm ls}^B(\pi)}} \ = \
\sum_{\pi \in NC^B_{n,k}}{q^{ {\rm rb}^B(\pi)}} \ = \
{n \choose k} \left[ {n \atop k} \right]_q q^{k \choose 2}.
\end{equation}
\end{corollary}
\begin{proof}
The equidistribution on each rank follows from Theorem \ref{thm-lsrbBequi}
and $NC^{*B}_{n,k}(q)$ can be readily determined using the definition
(\ref{eq-rbB}) of ${\rm rb}^B$:
\begin{eqnarray*}
NC^{*B}_{n,k}(q) & = &
\sum_{\pi \in NC^B_{n,k}}{q^{ {\rm rb}^B(\pi)}} \\
& = & q^{-k} \sum_{ {L,R \subseteq [n]} \atop {\# L = \# R = k}}
{q^{ \sum_{l\in L}{l}}} \\
& = & q^{-k} {n \choose k} \sum_{L \subseteq [n], \# L = k}
{q^{ \sum_{l\in L}{l}}},
\end{eqnarray*}
which can be rewritten as claimed.
\end{proof}
\subsection{Relations with poset symmetry properties of $NC^B_n$}
\label{subsec-symm}
The distributions of the statistics
${\rm lb}^B, {\rm rs}^B, {\rm ls}^B, {\rm rb}^B$ enjoy several
properties which reflect order-theoretic symmetry in the structure of
the lattice $NC^B_n$.
\begin{proposition}\label{prop-q-rksymm}
The rank-symmetry of $NC^B_n$ is respected by the distribution
$NC^B_{n,k}(q)$ of ${\rm lb}^B, {\rm rs}^B$,
and by the distribution $NC^{*B}_{n,k}(q)$ of ${\rm ls}^B, {\rm rb}^B$
on type-B noncrossing partitions of $[n]$ with $k$ pairs of
non-zero blocks:
\begin{equation}\label{eq-Bextsymm}
{1 \over {q^k}} NC^B_{n,k}(q)
\ =\ {1 \over {q^{n-k}}} NC^B_{n,n-k}(q), \ \ \ \ \
{1 \over {q^{k\choose 2}}} NC^{*B}_{n,k}(q)
\ = \ {1 \over {q^{{n-k} \choose 2}}} NC^{*B}_{n,n-k}(q).
\end{equation}
Each of these distributions is symmetric and unimodal.
\end{proposition}
\begin{proof}
The internal symmetry and unimodality as well as the
external symmetry relations follow immediately from the expressions
(\ref{eq-lbrsBform}) and (\ref{eq-lsrbBform}) and classical properties
of $q$-binomial coefficients.
Combinatorially, the bijection $\beta \colon NC^B_{n,k} \to NC^B_{n,n-k}$
mapping $\pi$ to $\pi'$ so that
$L(\pi') = [n] - L(\pi)$ and $R(\pi') = [n] - R(\pi)$
has the property that ${\rm rs}^B(\pi') = {\rm rs}^B(\pi) -n +2k$,
implying the external symmetry relation for $NC^B_{n,k}(q)$ claimed in
(\ref{eq-Bextsymm}).
It also has the property that
${\rm rb}^B(\pi') = {\rm rb}^B(\pi) + {k\choose 2} - {{n-k}\choose 2}$,
implying the external symmetry relation for $NC^{*B}_{n,k}(q)$.
\end{proof}
The symmetry of the distributions within each rank $NC^B_{n,k}$
can be made combinatorially explicit. For ${\rm rb}^B$ and ${\rm ls}^B$
(next corollary) the argument is an immediate adaptation of the standard
combinatorial proof of the symmetry of the coefficients of
$\left[ {n \atop k} \right]_q$. For ${\rm rs}^B$ and ${\rm lb}^B$
it is a consequence of how ${\rm rs}^B$ relates to an order-theoretic
property of $NC^B_n$ (Theorem \ref{thm-rs-bool} and
Corollary \ref{cor-vert-symm}).
\begin{corollary}\label{cor-rb-coeffs}
On each rank of $NC^B_n$, the statistics
${\rm rb}^B$ and ${\rm ls}^B$ are distributed symmetrically.
\end{corollary}
\begin{proof}
It suffices to verify that this is the case for ${\rm rb}^B$.
Let $c \colon [n] \to [n]$ be the map defined by
$c(i) = n+1-i$.
Given $\pi \in NC^B_{n,k}$, let $\pi'$ be the partition in $NC^B_{n,k}$
whose Left- and Right-sets are
$L(\pi') = c(L(\pi))$ and $R(\pi') = c(R(\pi))$.
This gives an involution on $NC^B_{n,k}$ with the property that
${\rm rb}^B(\pi) + {\rm rb}^B(\pi') = k(n-1)$. But this is equal to
the sum of the minimum and maximum values assumed by ${\rm rb}^B$
on $NC^B_{n,k}$, and the symmetry of the distribution is established.
\end{proof}
We now turn to a stronger symmetry property of $NC^B_n$ and
its relation to the statistic ${\rm rs}^B$.
The lattice $NC^B_n$ admits a {\em symmetric boolean decomposition (SBD)}.
That is, it is possible to partition the elements of
$NC^B_n$ into pairwise disjoint subposets having two properties:
1) for each subposet there is a value $r$ such that its elements
lie at ranks $r, r+1, \dots, n-r$ in $NC^B_n$, and the cover relations in the
subposet are covering relations in $NC^B_n$, and
2) each subposet is isomorphic to a boolean lattice.
Such a decomposition is obtained for $NC^B_n$ in \cite{Reiner-NCB},
by means analogous to those used in \cite{SiU} to establish a SBD for $NC^A_n$;
related facts for $NC^B_n$ appears in \cite{Hersh-NC}.
Here we give an explicit SBD of $NC^B_n$, different from the earlier ones,
having the property that the statistic ${\rm rs}^B$ is essentially constant on
each boolean lattice.
This is a refinement of the rank-symmetry of $NC^B_n$, which parallels
the property (see \cite{Si-ncstats}) of $NC^A_n$ that ${\rm rs}^A$ is constant
on each boolean lattice of the SBD constructed in \cite{SiU}.
Two enumerative consequences are given as corollaries.
\begin{theorem}\label{thm-rs-bool}
The lattice $NC^B_n$ admits a symmetric boolean decomposition with the
property that ${\rm rs}^B(\pi) + {\rm rk}^B(\pi) =
{\rm rs}^B(\pi') + {\rm rk}^B(\pi')$ if $\pi, \pi'$ belong to the same boolean
lattice.
\end{theorem}
\begin{proof}
Let $L_1, R_1$ be two disjoint subsets of $[n]$ of equal cardinality,
say, $\# L_1 = \# R_1 = k$.
Consider all the pairs $(L_1 \cup S, R_1 \cup S)$ where
$S$ ranges over all subsets of $[n] - (L_1 \cup R_1)$. Clearly, these pairs
ordered by componentwise {\em reverse} containment form a poset isomorphic to
a boolean lattice of height $n- \# L_1 - \# R_1 = n - 2k$.
Denote this boolean lattice by ${\cal B}(L_1, R_1)$.
Thus, $(L_1, R_1)$ is its maximum
element and $(L_0, R_0) \colon = ( [n] - R_1, [n] - L_1 )$ is its
minimum element.
We claim that the image of ${\cal B}(L_1,R_1)$
under the bijection (\ref{eq-Reiner-LRbij}) is a boolean lattice
symmetrically embedded in $NC^B_n$, and that the collection of these boolean
lattices, as $(L_1,R_1)$ range over all pairs of disjoint subsets of equal
cardinality, constitutes a SBD of $NC^B_n$.
Using the bijection (\ref{eq-Reiner-LRbij}), let the noncrossing partitions
corresponding to the maximum and minimum of ${\cal B}(L_1,R_1)$ be
$\pi_1 \leftrightarrow (L_1,R_1)$ and
$\pi_0 \leftrightarrow (L_0,R_0)$.
It is clear that we have ${\rm rk}^B(\pi_0) + {\rm rk}^B(\pi_1) = n$, as
desired for a boolean lattice in a SBD.
We verify that the bijection (\ref{eq-Reiner-LRbij}) maps a covering
$(L_1 \cup S \cup \{ s \}, R_1 \cup S \cup \{ s \}) \cov
(L_1 \cup S, R_1 \cup S)$ of ${\cal B}(L_1, R_1)$
to a covering $\pi \cov \pi'$ in $NC^B_n$.
Indeed, the elements $s$ and ${\overline{s}}$ appear as singleton blocks
in $\pi$ but not in $\pi'$; the remaining elements of the
Left- and Right-sets are the same in $\pi$ and $\pi'$.
It follows that $\pi$ is covered by $\pi'$ in $NC^B_n$.
Finally, the images in $NC^B_n$ of the
boolean lattices of the form ${\cal B}(L_1,R_1)$ constitute a partition of
the elements of $NC^B_n$.
This follows from the observation that an element $\pi \in NC^B_n$
which is encoded by a pair $(L(\pi), R(\pi))$ belongs to a well-defined
boolean lattice ${\cal B}(L_1,R_1)$. Namely, the boolean lattice arising from
the pair of sets $L_1 = L(\pi) - R(\pi)$ and $R_1 = R(\pi) - L(\pi)$.
Indeed, in every boolean lattice of the form ${\cal B}(L_1, R_1)$, the
differences $(L_1 \cup S) - (R_1 \cup S)$ and
$(R_1 \cup S) - (L_1 \cup S)$ are equal to $L_1$ and $R_1$, respectively,
for every $S$.
The relation of this SBD to the ${\rm rs}^B$ statistic is now obvious:
the value of $\sum_{r\in R(\pi)}{r} - \sum_{l \in L(\pi)}{l}$
is constant for all $\pi$ in the same boolean lattice of our SBD.
Comparing this difference with the definition (\ref{eq-rsB}) of
${\rm rs}^B(\pi)$, it follows that ${\rm rs}^B(\pi) + {\rm rk}^B(\pi) =
\sum_{r \in R_1}{r} - \sum_{l \in L_1}{l}$ has the same value
for every $\pi$ in the embedding of ${\cal B}(L_1, R_1)$ into $NC^B_n$.
\end{proof}
Several consequences follow now readily.
First, we obtain an alternative combinatorial proof of the external
symmetry of the polynomials $NC^B_{n,k}(q)$ stated in (\ref{eq-Bextsymm}).
Compared to the proof of Proposition \ref{prop-q-rksymm}, here we see
the compatibility of the statistic ${\rm rs}^B$ with the order structure of
$NC^B_n$.
\begin{corollary}\label{cor-vert-symm}
Let $0 \leq k \leq {n \over 2}$.
There is a bijection $\gamma \colon NC^B_{n,k} \to NC^B_{n,n-k}$
such that $\pi \leq \gamma(\pi)$ and ${\rm rs}^B(\pi) + {\rm rk}^B(\pi) =
{\rm rs}^B(\gamma(\pi)) + {\rm rk}^B(\gamma(\pi))$ for each
$\pi \in NC^B_{n,k}$.
\end{corollary}
\begin{proof}
Consider the SBD of $NC^B_n$ constructed in Theorem \ref{thm-rs-bool}, and
a symmetric chain decomposition of each of the boolean lattices
${\cal B}(L_1, R_1)$ defined in the proof of the theorem.
Let $\gamma(\pi)$ be the element in $NC^B_{n,n-k}$ which lies in
the same boolean lattice as $\pi$, and on the same chain in the symmetric
chain decomposition of this boolean lattice. It is then clear that
$\gamma$ has the desired properties.
\end{proof}
We also obtain a further refinement of the rank-symmetry and rank-unimodality
of $NC^B_n$.
\begin{corollary}\label{cor-fixrs}
For any given value $v$, the distribution by rank of the type-B noncrossing
partitions of $[n]$ for which the ${\rm rs}^B + {\rm rk}^B$ statistic is
equal to $v$,
\begin{equation}\label{eq-rsv}
\sum_{{\pi \in NC^B_n}\atop{{\rm rs}^B(\pi) + {\rm rk}^B(\pi) = v}}
{q^{{\rm rk}^B(\pi)}}
\end{equation}
has symmetric and unimodal coefficients.
\end{corollary}
\begin{proof}
By Theorem \ref{thm-rs-bool}, the range of summation in (\ref{eq-rsv})
is a disjoint union of boolean lattices, themselves rank-symmetric
and rank-unimodal posets. Since each of these boolean lattices
is embedded in
$NC^B_n$ on consecutive ranks and symmetrically with respect to rank,
the desired conclusion follows.
\end{proof}
One of the consequences of the SBD of $NC^A_n$ described in \cite{SiU} is a
combinatorial proof of Touchard's identity
\begin{equation}\label{eq-ATouchard}
C_n = \sum_{k=0}^{n-1} {{{n-1} \choose {2k}} C_k\ 2^{n-1-2k}}.
\end{equation}
We close this section with a ``type-B Touchard identity'' which arises,
along with an order-theoretic combinatorial proof,
from Theorem \ref{thm-rs-bool}.
\begin{corollary}\label{cor-BTouchard}
For every $n \ge 0$,
\begin{equation}
\# NC^B_n = \sum_{k=0}^n {{n \choose {2k}} \# NC^B_k\ 2^{n-2k}}.
\end{equation}
More explicitly,
\begin{equation}
{{2n} \choose n} =
\sum_{k=0}^n {{n \choose {2k}} {{2k} \choose k}\ 2^{n-2k}}.
\end{equation}
\end{corollary}
\begin{proof}
The total number of elements of $NC^B_n$ is obtained as the sum of the
cardinalities of the boolean lattices in the SBD of Theorem
\ref{thm-rs-bool}. There are ${n \choose {2k}}{{2k} \choose k}$ choices for
an ordered pair $(L_1, R_1)$ of disjoint $k$-subsets of $[n]$. Such a
choice yields a boolean lattice of height $n-2k$, as seen in the proof of
Theorem \ref{thm-rs-bool}.
\end{proof}
\section{Restricted signed permutations}\label{sec-Brhos}
In the symmetric group, patterns of length 2 are uninterestingly
restrictive, while length-3 patterns have the interesting property of
leading to the same number of restricted permutations in $S_n$, for all $n$,
namely the $n$th Catalan number. Counterparts of these cases
for the hyperoctahedral group arise here from restrictions by
patterns of lengths 1 and 2, respectively. The restricted classes
$B_n(1)$ and $B_n({\overline{1}})$ consist, obviously, of the $n!$ signed
permutations in which all -- respectively none -- of the symbols are barred.
The eight length-2 signed patterns give rise to some enumeratively
interesting classes of signed permutations, which we examine in this
section.
\subsection{Single restrictions by 2-letter patterns}\label{subsec-1roB}
Divide the 2-letter signed patterns into two classes,
$S$ and $D$, according to whether the two
symbols are simultaneously barred or not,
\begin{equation}\label{eq-SD1}
S = \{ 12, 21, {\overline{1}}\ {\overline{2}}, {\overline{2}}\
{\overline{1}} \}
{\rm \ \ and \ \ }
D = \{ 1{\overline{2}}, {\overline{1}} 2, 2 {\overline{1}},
{\overline{2}} 1 \}.
\end{equation}
\begin{observation}\label{obs-rho-classes}
It is immediately apparent that reversal (i.e., reading the permutation
right-to-left: $b_1 b_2 \cdots b_n \mapsto b_n b_{n-1} \cdots b_1$)
and barring (that is, $b_1 b_2 \cdots b_n \mapsto
{\overline{b_1}}\ {\overline{b_2}}\ \cdots\ {\overline{b_n}}$)
give bijections which show that
if $\rho$ and $ \rho' $ are both in $S$ or both in $D$,
then $\# B_n(\rho) = \# B_n(\rho')$.
\end{observation}
In fact, like the length-3 patterns for the symmetric group,
all the length-2 signed patterns give rise to the same number of restricted
signed permutations.
\begin{proposition}\label{prop-rho-equal}
If $\rho$ and $\rho'$ are any 2-letter signed patterns, then for every $n$
\begin{equation}
\# B_n(\rho) \ = \ \# B_n(\rho').
\end{equation}
\end{proposition}
\begin{proof}
Let $\beta_n(\rho) \colon = \# B_n(\rho)$.
By Observation \ref{obs-rho-classes}, it suffices to show that
$\beta_n(12) = \beta_n(1 {\overline{2}})$.
This is trivially true for $n=0$ and we claim that
the sequences $\left( \beta_n(12) \right)_{n \ge 0}$ and
$\left( \beta_n(1 {\overline{2}}) \right)_{n \ge 0}$ satisfy the same
recurrence relation for $n \ge 1$.
Let $b = b_1 b_2 \dots b_n \in B_n(12)$ and consider the symbol $b_1$.
Suppose first that $b_1$ is not barred, say, $b_1 = i$.
Since $b$ is $12$-avoiding, $i+1, \dots, n$ must appear barred in
$b$, in arbitrary order.
Also, $1, \dots, i-1$ can be arbitrarily barred or not, and can be
placed in any $i-1$ positions from among positions $2, \dots, n$,
subject to the condition that they themselves form a $12$-avoiding
signed permutation. Consequently, the number of
$b \in B_n(12)$ which begin with an unbarred symbol is
\begin{equation}\label{eq-rho-i}
\sum_{i=1}^{n}{ {{n-1} \choose {i-1}} (n-i)! \beta_{i-1}(12)}.
\end{equation}
If $b_1 = {\overline{i}}$ for some $i$,
then $b \in B_n(12)$ if and only if $b_2 \dots b_n$ is a $12$-avoiding
signed permutation.
This case contributes
\begin{equation}\label{eq-rho-ibar}
n \beta_{n-1}(12)
\end{equation}
further elements of $B_n(12)$.
Adding the expressions in (\ref{eq-rho-i}) and (\ref{eq-rho-ibar})
one obtains a recurrence relation satisfied by $\beta_n(12)$ for $n \ge 1$:
\begin{equation}\label{eq-rec12}
\beta_n(12) \ = \ (n+1) \beta_{n-1}(12)
+ (n-1)! \sum_{j=0}^{n-2}{ {\beta_j(12)}\over{j!}}.
\end{equation}
Similarly, if $b\in B_n(1 {\overline{2}})$, suppose first that
$b_1 = i$ for some $i$. To avoid the pattern
$1{\overline{2}}$, it is necessary and sufficient that:
i) the symbols larger than $i$ be unbarred,
ii) the symbols smaller than $i$ form a $1{\overline{2}}$-avoiding signed
permutation. Next, if $b_1 = {\overline{i}}$ for some $i$,
then $b_2 \cdots b_n$ is an arbitrary $1{\overline{2}}$-avoiding signed
permutation of $[n] - \{ i \}$.
Thus, $\beta_n(1{\overline{2}})$ satisfies a recurrence relation
identical to (\ref{eq-rec12}), and the proof is complete.
\end{proof}
The common cardinality of all restricted classes $B_n(\rho)$ for
length-2 patterns is now easy to determine.
\begin{proposition}\label{prop-rho-formula}
If $\rho$ is any signed pattern of length 2,
then for each $n$,
\begin{equation}\label{eq-rho-expr}
\# B_n(\rho) \ = \sum_{k=0}^{n}{ {n \choose k}^2 \cdot k!}.
\end{equation}
\end{proposition}
\begin{proof}
By Proposition \ref{prop-rho-equal}, it suffices to show that
formula (\ref{eq-rho-expr}) holds for $\rho = 12$.
This follows readily since each element of $B_n(12)$ is a shuffle of an
arbitrary permutation of, say, $k$ barred symbols and the decreasing sequence
formed by the remaining, not barred, symbols. Summing over $k$ yields the
formula.
\end{proof}
In fact, finer enumerative results hold.
\begin{observation}\label{obs-same-first}
Fix $n$ and any choice of a letter
$x \in \{ 1, 2, \dots, n, {\overline{1}}, {\overline{2}}, \dots,
{\overline{n}} \}$. Then the number of signed permutations $b$
whose first entry is $b_1 = x$ is the same in $B_n(12)$
as in $B_n(1{\overline{2}})$.
\end{observation}
This is apparent in the proof of Proposition \ref{prop-rho-equal}.
It is analogous to the fact \cite{SiSch} that in $S_n(123)$ and
in $S_n(132)$ there are equally many permutations with a prescribed
first entry.
Other enumerative relations hold between subclasses of $B_n(12)$
and $B_n(1 {\overline{2}})$. For example, essentially by iterating the
preceding observation, one has:
\begin{observation}\label{obs-genTree}
For each $n$, the number of signed permutations whose
leftmost unbarred symbol occurs in position $p$ is the same in the classes
of restricted signed permutations $B_n(12)$ and $B_n(1{\overline{2}})$.
We convene to set $p=n+1$ if all symbols are barred.
\end{observation}
We close with a $q$-analogue of the expression (\ref{prop-rho-formula}),
based on combinatorial statistics on signed permutations. This $q$-analogue
arises in a different context in \cite{Sol}.
\begin{observation}\label{obs-Sol}
For a signed permutation $b \in B_n$, define the statistics
\hfil\break\indent
${\rm suv}(b) \colon =$ the sum of the values which are not
barred in $b$,
\hfil\break\indent
${\rm sup}(b) \colon =$ the sum of the positions of the
symbols which are not barred in $b$,
\hfil\break\indent
${\rm uinv}(b) \colon =$ the number of inversions in the subword of $b$
consisting of the unbarred symbols.
\hfil\break
Now define
\begin{equation}
s(b) \colon = {\rm suv}(b) + {\rm sup}(b) + {\rm uinv}(b) - k(k+1),
\end{equation}
where $k$ denotes the number of barred symbols in $b$.
Then
\begin{equation}\label{equ-qSol}
\sum_{b \in B_n( {\overline{1}} \ {\overline{2}} )}
{ q^{s(b)} } \ = \ \sum_{k=0}^n
{ \left[ {n \atop k} \right]^2_q [k]_q! }.
\end{equation}
\end{observation}
Indeed, in a signed permutation $b \in B_n( {\overline{1}} \ {\overline{2}} )$,
the values, order, and positions of the unbarred symbols are arbitrary,
while the ordering of the barred symbols is forced, and (\ref{equ-qSol})
follows readily.
We note that alternative descriptions of the value of $s(b)$
and other choices of the pattern-restriction are possible.
\subsection{Double restrictions by 2-letter patterns}\label{subsec-2roB}
By taking advantage of the operations of
reversal, barring, and complementation (the last one means
$b_i$ is replaced with the value $n+1-|b_i|$, which we bar if and only if
$b_i$ is a barred symbol), the question of determining the cardinality of
$B_n(\rho, \rho')$ for the 28 choices of two 2-letter signed patterns,
reduces to 7 cases.
\begin{proposition}\label{prop-2rhos}
Given $n$ and two length-2 signed patterns $\rho, \rho'$,
let $\beta_n(\rho, \rho') = \# B_n(\rho, \rho')$,
the number of signed permutations in $B_n$ which avoid
simultaneously $\rho$ and $\rho'$.
The value of $\beta_n(\rho, \rho')$ satisfies one of the following
relations, according to which orbit (under reversal, barring, complementation)
contains the pair $\rho, \rho'$:
\begin{equation}\label{eq-2rhos-2fact}
\beta_n(12, 21) = 2\cdot n!,
\end{equation}
\begin{equation}\label{eq-2rhos-fact}
\beta_n(2{\overline{1}}, {\overline{1}}2) =
\beta_n(2{\overline{1}}, 1{\overline{2}}) =
\beta_n(1{\overline{2}}, {\overline{1}}2) =
\beta_n(12, 1{\overline{2}}) = (n+1)!,
\end{equation}
\begin{equation}\label{eq-2rhos-xxx}
n! < \beta_n(12, {\overline{2}}1) < (n+1)! \ \ \ {\rm for} \ \ n \ge 3,
\end{equation}
\begin{equation}\label{eq-2rhos-ncb}
\beta_n(21, {\overline{2}}\ {\overline{1}}) = { {2n} \choose n}.
\end{equation}
\end{proposition}
\begin{proof}
Each relation can be established by examining the form of the restricted
signed permutations in question and resorting, as needed, to a recurrence
relation and induction.
To verify (\ref{eq-2rhos-2fact}) note that $b \in B_n(12, 21)$ has either no
unbarred symbol (in which case it is one of the $n!$ permutations of
${\overline{1}}, \dots, {\overline{n}}$), or it has just one unbarred symbol
$i$ inserted in any position in an arbitrary permutation of
${\overline{1}}, \dots, {\overline{i-1}}, {\overline{i+1}}, \dots,
{\overline{n}}$. This gives $\beta_n(12, 21) = n! + n (n-1)!$,
as claimed in (\ref{eq-2rhos-2fact}).
Consider now $b \in B_n(2{\overline{1}}, {\overline{1}}2)$.
If $b_1 = i$, then the smaller values $1, \dots, i-1$ must be unbarred in
$b$ and can be permuted arbitrarily and placed in any of the positions
$2$ through $n$; the larger values $i+1, \dots, n$ must constitute a
$(2{\overline{1}}, {\overline{1}}2)$-avoiding signed permutation.
If $b_1 = {\overline{i}}$, then the discussion is similar. This leads to
the recurrence relation
\begin{equation}
{ {\beta_n(2{\overline{1}}, {\overline{1}}2)} \over{(n-1)!}} \ = \
2 \cdot \sum_{j=0}^{n-1}{
{\beta_j(2{\overline{1}}, {\overline{1}}2)}\over{j!}}
\end{equation}
for $n \ge 1$, and $ \beta_0(2{\overline{1}}, {\overline{1}}2) = 1$.
We omit the simple exercise of solving for
$ \beta_n(2{\overline{1}}, {\overline{1}}2)$, as well as the similar argument
for finding $\beta_n(2{\overline{1}}, 1{\overline{2}})$ and
$\beta_n(1{\overline{2}}, {\overline{1}}2)$.
In the last case of (\ref{eq-2rhos-fact}), $B_n(12, 1{\overline{2}})$,
note that if $b_1$ is an unbarred symbol, then
the pattern restriction forces $b_1 = n$ and
that if $b_1$ is a barred symbol, it may have any value.
In both cases, $b_2 \cdots b_n$ is a $(12, 1{\overline{2}})$-avoiding signed
permutation on $[n] - \{ |b_1| \}$. This yields
$\beta_n(12, 1{\overline{2}}) = (n+1)\beta_{n-1}(12, 1{\overline{2}})$.
Concerning (\ref{eq-2rhos-xxx}), a similar analysis leads to the
recurrence relation
$\beta_n(12, {\overline{2}}1) = n \beta_{n-1}(12, {\overline{2}}1)
+ (n-1)! \sum_{j=0}^{n-1}{ 1 \over {j!} }$ for $n \ge 1$,
with $\beta_0(12, {\overline{2}}1) = 1$. From this the inequalities
can be established by induction. The first few values are
$(\beta_n(12, {\overline{2}} 1) )_{n \ge 0} = (1, 2, 6, 23, 108, \dots )$.
An expression for $\beta_n(12, {\overline{2}} 1)$ can be obtained by
iterating the recurrence relation. From the recurrence relation one can
also deduce
$\beta_n(12, {\overline{2}} 1) = 2n \beta_{n-1}(12, {\overline{2}}1)
- (n^2 -2) \beta_{n-2}(12, {\overline{2}} 1)
+ (n-2)^2 \beta_{n-3}(12, {\overline{2}} 1)$ for $n \ge 3$.
Finally, to verify (\ref{eq-2rhos-ncb}), we observe that
if $b \in B_n(21, {\overline{2}}\ {\overline{1}})$ then $b$ is determined
by the choice of which symbols in it are barred and where
they are located. It is a shuffle of the barred and unbarred symbols, each
of which are ordered increasingly by absolute value.
For each $0 \leq k \leq n$, there are $n \choose k$ choices of the values to
be barred, and again $n \choose k$ choices for their placement in $b$.
Thus (\ref{eq-2rhos-ncb}) follows by direct counting.
\end{proof}
The last class of restrictions, which gives ${{2n}\choose n} = \# NC^B_n$
pattern-avoiding signed permutations, is of special interest here and
is further considered in Section \ref{sec-NCBroB}.
\section{Relations between statistics on type-B noncrossing partitions and
restricted signed permutations}\label{sec-NCBroB}
Considering the set of type-B noncrossing partitions $NC^B_n$ and
the elements of $B_n$ which avoid simultaneously the patterns $21$
and ${\overline{2}}\ {\overline{1}}$, we obtain a B-analogue of
the type-A result of \cite{Si-ncstats} stated in equation
(\ref{eq-NCAroA}).
\begin{theorem}\label{thm-desmaj-bkrb-B}
For every $n \ge 1$, there is a bijection
$\gamma \colon B_n(21, {\overline{2}}\ {\overline{1}}) \to NC^B_n$
such that ${\rm des}^B(b) = {\rm bk}^B(\gamma(b))$ and
${\rm maj}^B(b) = {\rm rb}^B(\gamma(b)) + {\rm bk}^B(\gamma(b))$.
As a consequence,
\begin{equation}\label{eq-desmaj-bkrb-B}
\sum_{b \in B_n(21, {\overline{2}}\ {\overline{1}})}
{ p^{{\rm des}^B(b)} q^{{\rm maj}^B(b)} } \ = \
\sum_{\pi \in NC^B_n}
{ (pq)^{{\rm bk}^B(\pi)} q^{{\rm rb}^B(\pi)} }
\end{equation}
and the common expression for these joint distributions is
\begin{equation}\label{eq-qbc}
\sum_{k=0}^n { {n \choose k} \left[ {n \atop k} \right]_q
p^k q^{{k+1} \choose 2}}.
\end{equation}
\end{theorem}
\begin{proof}
Based on their characterization used in the proof of
Proposition \ref{prop-2rhos}, the permutations in
$B_n(21, {\overline{2}}\ {\overline{1}})$ are in bijection with the
ordered pairs of subsets of $[n]$ having equal cardinality,
$b \leftrightarrow (P(b), B(b))$.
The subset $B(b)$ is the set of values which are barred in $b$
and the subset $P(b)$ is the set of their positions in $b$.
Recalling from subsection \ref{subsec-def} the
definition of the descent statistic for the hyperoctahedral group,
we have $P(b) = {\rm Des}(b)$.
Let $\gamma(b)$ be the type-B noncrossing partition whose encoding
by its pair of Left- and Right-sets is $({\rm Des}(b), B(b))$.
Then, by the definitions of the statistics, it is clear
that (\ref{eq-desmaj-bkrb-B}) holds.
The expression (\ref{eq-qbc}) is immediate from (\ref{eq-lsrbBform}).
\end{proof}
The expression (\ref{eq-qbc}) is a $p,q$-analogue of
$\sum_{k=0}^n{ {n \choose k}^2 } = { {2n}\choose n }$ in which one of the
binomial coefficients $n \choose k$ is replaced by a $q$-binomial coefficient.
George Andrews asked whether it is possible to derive a
$p,q$-analogue in which the other binomial coefficient becomes a
$p$-binomial coefficient.
\begin{proposition}\label{prop-pqbc}
For $n \ge 1$, the joint distribution of the statistics ${\rm rs}^B$ and
${\rm rb}^B$ on type-B noncrossing partitions satisfies the relation
\begin{equation}\label{eq-pqbc}
p^n \sum_{\pi \in NC^B_n}
{ p^{ {\rm rs}^B(\pi)}
(pq)^{ {\rm rb}^B(\pi)} } \ = \
\sum_{k=0}^n { \left[ {n \atop k } \right]_p
\left[ {n \atop k } \right]_q
p^{ { {k+1}\choose 2}} q^{ k \choose 2} }.
\end{equation}
\end{proposition}
\begin{proof}
By the correspondence $\pi \leftrightarrow (L(\pi), R(\pi))$
and the definitions of ${\rm rs}^B$ and ${\rm rb}^B$,
the left hand side of (\ref{eq-pqbc}) equals
\begin{equation}
p^n \sum_{k=0}^n { \sum_{{L,R \subseteq [n]}\atop{\# L = \# R = k}}
{ p^{ (\sum_{r \in R}{r}) - n}\
q^{(\sum_{l \in L}{l}) -k} }},
\end{equation}
which can be written as the right-hand-side of (\ref{eq-pqbc}).
\end{proof}
We consider now the excedence and Denert statistics
defined for type B in (\ref{eq-BExc-def}) and (\ref{eq-BDen-def}).
\begin{proposition}\label{prop-BexcDen}
For every $n$, the joint distribution of the excedence and Denert
statistics on the $(21, {\overline{2}}\ {\overline{1}})$-avoiding
signed permutations in $B_n$ agrees with the
joint distribution of the statistics
${\rm bk}^B$ and ${\rm rb}^B + {\rm bk}^B$
on the noncrossing partitions in $NC^B_n$:
\begin{equation}\label{eq-distr-Bden}
\sum_{b \in B_n(21, {\overline{2}}\ {\overline{1}})}
{ p^{{\rm exc}^B(b)} q^{{\rm Den}^B(b)} } \ = \
\sum_{\pi \in NC^B_n}
{(pq)^{{\rm bk}^B(\pi)} q^{{\rm rb}^B(\pi)} }.
\end{equation}
\end{proposition}
\begin{proof}
For signed permutations in the class
$B_n(21, {\overline{2}}\ {\overline{1}})$
the excedences defined via (\ref{eq-BExc-def}) coincide with the
descents, as was observed by Galovich \cite{Gal-pers}, so
${\rm maj}^B$ and ${\rm Den}^B$ agree as well.
Thus the conclusion follows from the preceding result.
\end{proof}
\newpage
\section{Further questions}\label{sec-Further}
\begin{enumerate}
\item{ {\em Signed permutations restricted by 2-letter patterns.}
In view of Proposition \ref{prop-rho-equal}, we may write
$\beta_n$ for the common cardinality of
$B_n(\rho)$ for all signed 2-letter patterns $\rho$.
For $n \ge 0$, this sequence begins with the values
$1, 2, 7, 34, 209, 1546, ...$.
A sequence beginning with the same values appears in \cite{Sloane}.
The reference is \cite{Ser} and the sequence is described by the
recurrence relation
\begin{equation}\label{eq-rec-Sloane}
a_0 = 1, \ \ \ a_n = 2 n a_{n-1} - (n-1)^2 a_{n-2} {\rm \ \ for \ } n \ge 1.
\end{equation}
One can verify that this and the recurrence (\ref{eq-rec12})
produce the same sequence.
Indeed, $a_0 = \beta_0 = 1$, and assuming inductively that $a_{i} = \beta_i$
for $i < n$, we have $a_n = \beta_n$ if and only if
\begin{equation}
2 n a_{n-1} - (n-1)^2 a_{n-2} = (n+1) a_{n-1} +
(n-1)! \sum_{i=0}^{n-2} { {a_{i} }\over{i!}},
\end{equation}
which can be rewritten as
\begin{equation}
(n-1) a_{n-1} = n (n-1) a_{n-2} +
(n-1)! \sum_{i=0}^{n-3}{ {a_{i}}\over{i!}}.
\end{equation}
But this is equivalent to the recurrence (\ref{eq-rec12}) satisfied by
$\beta_n$.
Thus, for each 2-letter signed pattern $\rho$,
the cardinality $\beta_n$ of the
class of restricted signed permutations $B_n(\rho)$
satisfies the recurrence (\ref{eq-rec-Sloane}).
It would be interesting to find a combinatorial explanation for
this recurrence for the numbers $\beta_n$.
Similarly, it would be interesting to find a combinatorial proof of the
3-term recurrence for $\beta_n(12, {\overline{2}} 1)$ stated in the proof of
Proposition \ref{prop-2rhos}.
}
\item{ {\em Bijections among classes of restricted signed permutations.}
In enumerating signed permutations which avoid simultaneously two
2-letter patterns (Proposition \ref{prop-2rhos}), we found in equation
(\ref{eq-2rhos-fact}) that
$\# B_n(2{\overline{1}}, {\overline{1}}2) =
\# B_n(2{\overline{1}}, 1{\overline{2}}) =
\# B_n(1{\overline{2}}, {\overline{1}}2) =
\# B_n(12, 1{\overline{2}}) = (n+1)!$.
The first three cases are representatives of size-2 orbits of double
restrictions, while the fourth case is in an orbit of size 4.
This, as well as the difference in the natural recurrence relations
used in the proof of (\ref{eq-2rhos-fact}), raise the question of
finding explicit bijections among these classes of
restricted signed permutations.
}
\item{ {\em Combinatorial statistics on (unrestricted) type-B set
partitions.}
How might the definitions (\ref{eq-lsB})-(\ref{eq-rbB}) of statistics
for type-B noncrossing partitions be extended to the entire lattice
$\Pi^B_n$ of type-B partitions? Do analogues of the properties
for type-A partitions statistics in \cite{WaWh} hold?
}
\end{enumerate}
\begin{thebibliography}{99} {\small
\bibitem{Barc} E. Barcucci, A. Del Lungo, and E. Pergola,
Permutations with one forbidden subsequence of increasing length,
Extended Abstracts, Proc. 9th Conf. Formal Power Series and Algebr. Combin.
(Vienna), 1997.
\bibitem{Billey} S.C. Billey,
Pattern avoidance and rational smoothness of Schubert varieties,
Adv. in Math. {\bf 139} (1998) 141-156.
\bibitem{Bona} M. B\'ona,
Permutations avoiding certain patterns: the case of length 4 and some
generalizations, Discrete Math. {\bf 175} (1997) 55-67.
\bibitem{Brenti-KL} F. Brenti,
Combinatorial properties of the Kazhdan-Lusztig $R$-polynomials for $S_n$,
Adv. in Math. {\bf 126} (1997) 21-51.
\bibitem{ChowWest} T. Chow and J. West, Forbidden sequences and Chebysheff
polynomials, Discrete Math., to appear.
\bibitem{DuGiWe} S. Dulucq, S. Gire, and J. West,
Permutations with forbidden subsequences and nonseparable planar maps,
Proc. 5th Conf. Formal Power Series and Algebr. Combin. (Florence, 1993),
Discrete Math. {\bf 153} (1996) 85-103.
\bibitem{Ed1} P. Edelman, Chain enumeration and noncrossing partitions,
Discrete Math. {\bf 31} (1980) 171-180.
\bibitem{Ed2} P. Edelman, Multichains, noncrossing partitions and trees,
Discrete Math. {\bf 40} (1982) 171-179.
\bibitem{EdSi} P. Edelman and R. Simion, Chains in the lattice of
noncrossing partitions. Discrete Math. {\bf 126} (1994), no. 1-3, 107--119.
\bibitem{FoZeil} D. Foata and D. Zeilberger,
Denert's permutation statistic is indeed Euler-Mahonian,
Stud. Appl. Math. {\bf 83} (1990) 31--59.
\bibitem{Gal-pers} J. Galovich, personal communication, February 1999.
\bibitem{Gash} V. Gasharov, Factoring the Poincare polynomials for the
Bruhat order on $S_n$, J. Combin. Theory Ser. A {\bf 83} (1998), 159-164.
\bibitem{Hersh-NC} P. Hersh, Deformation of chains via a local symmetric
group action, Electronic J. Combin. {\bf 27} (1999).
\bibitem{schaeffer} B. Jacquard and G. Schaeffer, A bijective census of
nonseparable planar maps. J. Combin. Theory Ser. A {\bf 83}
(1998), no. 1, 1--20.
\bibitem{Knuth} D. Knuth, ``The Art of Computer Programming,'' vol. 3,
Addison-Wesley, Reading, MA, 1973.
\bibitem{kreweras} G.\ Kreweras, Sur les partitions non crois\'ees
d'un cycle, {\it Discrete Math.} {\bf 1} (1972), no. 4, 333--350.
\bibitem{Montenegro} C. Montenegro, The fixed point non-crossing partition
lattices, manuscript, 1993.
\bibitem{NicaSpei} A. Nica and R. Speicher,
A ``Fourier transform'' for multiplicative functions on non-crossing
partitions,
J. Algebraic Combin. {\bf 6} (1997) 141-160.
\bibitem{NoonanZeil} J. Noonan and D. Zeilberger,
The enumeration of permutations with a prescribed number of ``forbidden''
patterns, Adv. in Appl. Math. {\bf 17} (1996) 381-407.
\bibitem{Reiner-NCB} V. Reiner, Non-crossing partitions for classical
reflection groups. Discrete Math. {\bf 177} (1997), no. 1-3, 195--222.
\bibitem{Ser} J. Ser,
``Les Calculs Formels des S\'eries Factorielles,''
Gauthiers-Villars, Paris, 1933.
\bibitem{SiSch} R. Simion, F. W.\ Schmidt, Restricted permutations,
{\it European Journal of Combinatorics}, {\bf 6} (1985), 383-406.
\bibitem{SiU} R. Simion, D. Ullman,
On the structure of the lattice of noncrossing partitions,
{\it Discrete Math.} {\bf 98} (1991), no. 3, 193--206.
\bibitem{Si-ncstats} R. Simion, Combinatorial statistics on noncrossing
partitions, J. Combin. Theory Ser. A {\bf 66} (1994) 270-301.
\bibitem{Si-NCsurvey} R. Simion, Noncrossing partitions, Discrete Math., to
appear.
\bibitem{Si-Bassoc} R. Simion, A type-B analogue of the associahedron, in
preparation.
\bibitem{Sloane} N.J.A. Sloane and S. Plouffe,
``The Encyclopedia of Integer Sequences,''
Academic Press, Inc., San Diego, CA, 1995.
%% p. 557.
\bibitem{Sol} L. Solomon,
The Bruhat decomposition, Tits system and Iwahori ring for the monoid of
matrices over a finite field,
Geom. Dedicata {\bf 36} (1990) 15-49.
\bibitem{stanley} R. Stanley, Log-concave and unimodal sequences in algebra,
combinatorics, and geometry. Graph theory and its applications: East and West
(Jinan, 1986),
500--535, Ann. New York Acad. Sci., 576, New York Acad. Sci., New York, 1989.
\bibitem{St-NCact} R. Stanley,
Parking functions and noncrossing partitions,
Electronic J. Combin. {\bf 4} (1997) R20, 14pp.
\bibitem{EC1} R. Stanley, ``Enumerative Combinatorics,'' vol. 1,
second edition, Cambridge Studies in Adv. Math., 49,
Cambridge Univ. Press, Cambridge, 1997.
\bibitem{EC2} R. Stanley, ``Enumerative Combinatorics,'' vol. 2,
Cambridge University Press, New York/Cambridge, 1999.
\bibitem{Stein} E. Steingr\'imsson,
Permutations statistics of indexed permutations,
European J. Combin. {\bf 15} (1994) 187-205.
\bibitem{Stemb-FC3} J. Stembridge,
The enumeration of fully commutative elements of Coxeter groups,
J. Algebraic Combin. {\bf 7} (1998) 291--320.
\bibitem{Tarjan} R. Tarjan, Sorting using networks of queues and stacks, J.
Assoc. Comput. Mach. {\bf 19} (1972) 341-346.
\bibitem{WaWh} M. Wachs and D. White,
$p,q$-Stirling numbers and set partition statistics,
J. Combin. Theory Ser. A {\bf 56} (1991) 27-46.
\bibitem{West} J. West, Generating trees and forbidden subsequences,
Proc. 6th Conf. Formal Power Series and Algebr. Combin. (New Brunswick, NJ,
1994), Discrete Math. {\bf 157} (1996) 363-374.
\bibitem{White-interp} D. White,
Interpolating set partition statistics,
J. Combin. Theory Ser. A {\bf 68} (1994) 262-295.
\bibitem{doron} D. Zeilberger, A proof of Julian West's conjecture that
the number of two-stack-sortable
permutations of length $n$ is $2(3n)!/((n+1)!(2n+1)!)$,
Discrete Math. {\bf 102} (1992), no. 1, 85--93. }
\end{thebibliography}
\end{document}
**