\documentclass[12pt]{amsart}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{hyperref}
\usepackage{pstricks,pst-node,multido,pst-coil}
\usepackage{a4wide}
 

%-------- Meta Data ------------------------------------------
\title{Cyclic sieving phenomena on annular noncrossing permutations}
\author{Jang Soo Kim}

\date{}


%-------- theorems ------------------------------------------
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\theoremstyle{definition}
\newtheorem{example}{Example}[section]
\newtheorem{defn}{Definition}[section]
\newtheorem{conj}{Conjecture}[section]
\newtheorem{question}{Question}[section]
\theoremstyle{remark}
\newtheorem{remark}{Remark}[section]
\newtheorem*{note}{Note}

\numberwithin{equation}{section}

%-------- macros ------------------------------------------

\newcommand\flr[1]{\left\lfloor #1\right\rfloor}
\newcommand\ceil[1]{\left\lceil #1\right\rceil}
\newcommand\qint[1]{\left[ #1\right]_q}
\newcommand\yqint[1]{\left[ #1\right]_{y,q}}
\newcommand\yiqint[1]{\left[ #1\right]_{y^{-1},q}}
\newcommand\Qbinom[3]{\genfrac{[}{]}{0pt}{}{#1}{#2}_{#3}}
\newcommand\qbinom[2]{\Qbinom{#1}{#2}{q}}
\newcommand\A{\mathcal{A}}
\newcommand\B{\mathcal{B}}
\newcommand\F{\mathcal{F}}
\newcommand\G{\mathcal{G}}
\newcommand\K{\mathcal{K}}
\newcommand\J{\mathcal{J}}
\newcommand\M{\mathcal{M}}
\newcommand\X{\mathcal{X}}
\newcommand\Y{\mathcal{Y}}

\newcommand\wn{\widehat{n}}
\newcommand\wm{\widehat{m}}

\newcommand\nc{\operatorname{NC}}
\newcommand\anc{\operatorname{ANC}}
\newcommand\Par{\operatorname{Par}}
\newcommand\Kre{\operatorname{Kre}^{\mathrm{ann}}}
\newcommand\Nara{\operatorname{Nara}^{\mathrm{ann}}}
\newcommand\Cat{\operatorname{Cat}^{\mathrm{ann}}}

\newcommand\divi{\;|\;}

\newcommand\N{\mathbb{N}}
\newcommand\Z{\mathbb{Z}}

\newcommand{\qhyper}[5]{{_{#1}\phi_{#2}}\left[\genfrac{}{}{0pt}{}{#3}{#4};q,#5\right]}

\newcommand\cmt[1]{\textbf{\red #1}}

%-------- pstricks ------------------------------------------
\psset{gridlabels=0pt,subgriddiv=1, gridwidth=.1pt,gridcolor=gray}
\psset{linewidth=1pt, unit=.6cm}
\psset{unit=12pt}

% #1: radius, #2: angle, #3: node name, #4: label
\def\evput#1#2#3#4{\rput(#1;#2){\cnode*(0,0){2pt}{#3}} 
\uput{#1.5}[#2](0,0){#4}}
\def\ivput#1#2#3#4{\rput(#1;#2){\cnode*(0,0){2pt}{#3}} 
\uput{#1}[#2](0,0){\rput(-.8;#2){#4}}}
\def\edge#1#2{\ncline{->}{#1}{#2}}

%-------- start here ------------------------------------------

\begin{document}

\begin{abstract}
  We show cyclic sieving phenomena on annular noncrossing permutations with
  given cycle types.  We define annular $q$-Kreweras numbers, annular
  $q$-Narayana numbers, and annular $q$-Catalan numbers, and show that a sum of
  annular $q$-Kreweras numbers becomes an annular $q$-Narayana number and a sum
  of annular $q$-Narayana numbers becomes an annular $q$-Catalan number. We also
  show that these polynomials are closely related to the cyclic sieving
  phenomena on annular noncrossing permutations.
\end{abstract}

\maketitle
\thispagestyle{myheadings}
\font\rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8

\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 69 \rms (2013), Article~B69b\hfill}
\def\thepage{}


\section{Introduction}

Let $\pi$ be a permutation of $[n]=\{1,2,\dots,n\}$. One can represent $\pi$
inside a disk as shown in Figure~\ref{fig:disk}.  If the arrows of the diagram
of $\pi$ are noncrossing and if every cycle of $\pi$ is oriented clockwise, then
$\pi$ is called a \emph{noncrossing permutation}. If we replace each cycle by a
block, then we get a bijection from noncrossing permutations to noncrossing
partitions. Thus, as far as enumeration is concerned, one can use ``noncrossing
permutation'' and ``noncrossing partition'' interchangeably.  In fact,
``noncrossing partition'' is more commonly used than ``noncrossing
permutation''. However in this paper we use ``noncrossing permutation'' because
we will consider annular noncrossing permutations which are different from
annular noncrossing partitions.

\begin{figure}
  \centering
\begin{pspicture}(-6,-6)(6,6) 
\psset{linewidth=1.5pt, nodesep =2pt}
\pscircle[linecolor=gray](0,0){5}
\multido{\n=90+-36,\i=1+1}{10}{\evput{5}{\n}{\i}{\i}}
\edge13 \edge34 \edge45 \edge51
\edge97 \edge78 \edge89
\nccircle[angleA=150]{<-}{2}{4pt}
\ncarc[arcangle=20]{->}{10}{6}
\ncarc[arcangle=20]{->}{6}{10}
\end{pspicture}  
\caption{A representation of the permutation $(1,3,4,5)(2)(6,10)(7,8,9)$ inside
  a disk.}
  \label{fig:disk}
\end{figure}

It is well known that the number of noncrossing permutations of $[n]$ is the
\emph{Catalan number}
\[
\mathrm{Cat}(n) = \frac{1}{n+1} \binom{2n}{n},
\]
and the number of noncrossing permutations of $[n]$ with $k$ cycles is the
\emph{Narayana number}
\[
\mathrm{Nara}(n,k) = \frac{1}{n} \binom{n}{k-1} \binom{n}{k}.
\]

We use the standard notations
\[
[n]_q = \frac{1-q^n}{1-q}, \qquad [n]_q! = [1]_q [2]_q \cdots [n]_q,
\]
\[
\qbinom{n_1+\cdots+n_k}{n_1,\dots,n_k}
=\frac{[n_1+\cdots+n_k]_q!}{[n_1]_q! \cdots [n_k]_q!},
\qquad \qbinom{n}{k} = \frac{[n]_q!}{[k]_q! [n-k]_q!}.
\]

We denote by $\Par(n,k)$ the set of integer partitions of $n$ with $k$ parts.
If $\lambda$ has $m_i$ parts of size $i$ for $i=1,2,\dots,\ell$ with largest
part $\ell$, then we also write $\lambda=(1^{m_1},
2^{m_2},\dots,\ell^{m_\ell})$. If $\lambda=(1^{m_1},
2^{m_2},\dots,\ell^{m_{\ell}} )$ has $k$ parts, i.e., $m_1+m_2+\cdots+m_\ell=k$,
we define
\[
\binom{k}{\lambda} = \binom{k}{m_1,m_2,\dots,m_\ell}, \qquad
\qbinom{k}{\lambda} = \qbinom{k}{m_1,m_2,\dots,m_\ell},
\]

The \emph{cycle type} of a permutation $\pi$ is the partition $\lambda=(1^{m_1},
2^{m_2},\dots)$, where $m_i$ is the number of cycles with $i$ elements. Kreweras
\cite{Kreweras} showed that the number of noncrossing permutations (noncrossing
partitions in the original paper) of $[n]$ with cycle type $\lambda=(1^{m_1},
2^{m_2},\dots)\in \Par(n,k)$ is equal to the \emph{Kreweras number}
\[
\mathrm{Kre}(\lambda): = \frac{1}{k} \binom{n}{k-1} \binom{k}{\lambda}.
\]

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL JANG SOO~KIM}{\SMALL 
CYCLIC SIEVING PHENOMENA ON ANNULAR NONCROSSING PERMUTATIONS}
%
%

Bessis and Reiner \cite[Theorem 6.2]{Bessis2011} showed that if $X$ is the set
of noncrossing permutations (noncrossing partitions in the original paper) of
$[n]$ with type $\lambda=(1^{m_1}, 2^{m_2},\dots)\in \Par(n,k)$,
\[
X(q) = \frac{1}{[k]_q} \qbinom{n}{k-1} \qbinom{k}{\lambda},
\]
and $C$ is the cyclic group of rotations acting on $X$, then $(X,X(q),C)$
exhibits the cyclic sieving phenomenon, see Section~2 for the definition.

Reiner and Sommers \cite{ReinerSommers} defined the \emph{$q$-Kreweras number}
for $\lambda=(1^{m_1}, 2^{m_2},\dots)\in \Par(n,k)$ by
\[
\mathrm{Kre}_q(\lambda) = \frac{q^{(n+1)(n-k)-\tau(\lambda)}}{[k]_q} \qbinom{n}{k-1}
  \qbinom{k}{\lambda},
\]
where $\tau(\lambda)=\sum_{i\ge1}{\lambda_i' \lambda_{i+1}'}$, and the
\emph{$q$-Narayana number} by
\[
\mathrm{Nara}_q(n,k) = \frac{q^{(n-k)(n+1-k)}} {[n]_q} \qbinom{n}{k-1}
  \qbinom{n}{k},
\]
and showed that
\[
\sum_{\lambda\in \Par(n,k)} \mathrm{Kre}_q(\lambda) = \mathrm{Nara}_q(n,k)
\]
and
\[
\sum_{k=0}^n \mathrm{Nara}_q(n,k) = \mathrm{Cat}_q(n),
\]
where $\mathrm{Cat}_q(n)$ is the \emph{$q$-Catalan number} defined by 
\[
\mathrm{Cat}_q(n) = \frac{1}{[n+1]_q} \qbinom{2n}{n}.
\]

In this paper we prove analogous results for annular noncrossing permutations.

Annular noncrossing permutations (respectively~partitions) are an annulus-analog
of noncrossing permutations (respectively~partitions). It should be noted that
annular noncrossing permutations are not in bijection with annular noncrossing
partitions. However, these two objects can be identified in most cases. See
Remark~\ref{remark} for more details about their difference.

Annular noncrossing partitions were introduced by King \cite{King} in the study
of a statistical physics model.  Annular noncrossing permutations were
considered by Mingo and Nica \cite{Mingo2004} and studied further in \cite{GNO,
  Nica2009}. Recently Kim, Seo, and Shin \cite{KSS_ANP} used annular noncrossing
permutations to give a combinatorial proof of Goulden and Jackson's formula
\cite{Goulden1997} for the number of minimal transitive factorizations of a
product of two cycles.

This paper is organized as follows.  In Section~\ref{sec:CSP} we define annular
noncrossing permutations and state the main result Theorem~\ref{thm:CSP} which
gives cyclic sieving phenomena on annular noncrossing permutations.  In
Section~\ref{sec:annular-q-kreweras} we define annular $q$-Kreweras numbers,
three types of annular $q$-Narayana numbers, and annular $q$-Catalan numbers and
show that a sum of annular $q$-Kreweras numbers becomes an annular $q$-Narayana
number, and a sum of annular $q$-Narayana numbers becomes an annular $q$-Catalan
numbers. In Section~\ref{sec:polyn-nonn} these numbers multiplied by 2 are shown
to be polynomials in $q$ with nonnegative integer coefficients.  In
Section~\ref{Proof of CSP} we prove Theorem~\ref{thm:CSP}.  In
Section~\ref{sec:annul-noncr-match} we enumerate annular noncrossing matchings.

\section{Cyclic sieving phenomena}
\label{sec:CSP}

Let $n$ and $m$ be positive integers.  An \emph{$(n,m)$-annulus} is an annulus
in which $1,2,\dots,n$ are arranged in clockwise order on the exterior circle
and $n+1,n+2,\dots,n+m$ are arranged in counter-clockwise order on the interior
circle. 

Let $(a_1,\dots,a_k)$ be a cycle whose elements are contained in $[n+m]$.  We
will represent this cycle inside an $(n,m)$-annulus by drawing an arrow from
$a_i$ to $a_{i+1}$ for each $i=1,2,\dots k$, where $a_{k+1}=a_1$.  An
\emph{interior cycle} (respectively~\emph{exterior cycle}) is a cycle all of
whose elements are on the interior (respectively~exterior) circle. A
\emph{connected cycle} is a cycle which contains both an element in the interior
circle and an element in the exterior cycle.  Suppose
$\{e_1<e_2<\dots<e_u\}=\{a_1,\dots,a_k\} \cap [n]$ and
$\{i_1<i_2<\dots<i_v\}=\{a_1,\dots,a_k\} \cap \{n+1,n+2,\dots,n+m\}$.  Then we
say that the cycle $(a_1,\dots,a_k)$ is \emph{oriented clockwise} if we can
express
\[
(a_1,\dots,a_k)=(e_r,e_{r+1},\dots,e_u,e_1,e_2,\dots,e_{r-1},
i_s,i_{s+1},\dots,i_v,i_1,i_2,\dots,i_{s-1})
\]
for some integers $1\le r\le u$ and $1\le s\le v$.  In this case we say that the
cycle $(a_1,\dots,a_k)$ is of \emph{size} $k$, of \emph{exterior size} $u$ and
of \emph{interior size} $v$.

\begin{figure}
  \centering
\begin{pspicture}(-6,-6)(6,6) 
\psset{linewidth=1.5pt, nodesep =2pt}
\pscircle[linecolor=gray](0,0){5}
\pscircle[linecolor=gray](0,0){2}
\multido{\n=90+-40,\i=1+1}{9}{\evput{5}{\n}{\i}{\i}}
\multido{\n=0+60,\i=10+1}{6}{\ivput{2}{\n}{\i}{\i}}
\edge 12 \edge 23 
\edge6{15} \ncarc[arcangle=-50]{->}{15}{10}
\edge6{15} \ncarc[arcangle=-50]{->}{10}{11}
\edge6{15} \ncarc[arcangle=-50]{->}{13}{14}
\edge{11}1
\ncarc[arcangle=10]{->}{3}{6}
\nccircle[angleA=40]{<-}{12}{4pt}
\ncarc[arcangle=0]{->}{4}{5}
\ncarc[arcangle=50]{->}{5}{4}
\edge{14}7 \edge78 \edge89 \edge9{13}
\end{pspicture}  
\caption{A representation of the annular noncrossing permutation
  $(1,2,3,6,15,10,11)(4,5)(7,8,9,13,14)(12)$.}
  \label{fig:ex}
\end{figure}

A permutation of $[n+m]$ is called an \emph{$(n,m)$-annular noncrossing
  permutation} if we can draw its cycles inside an $(n,m)$-annulus in such a way
that every cycle is oriented clockwise and there are no crossing arrows, see
Figure~\ref{fig:ex}. 

\begin{remark}\label{remark}
  Unlike noncrossing permutations, the map changing each cycle to a block is not
  a one-to-one correspondence between annular noncrossing permutations and
  annular noncrossing partitions. For instance the two $(2,1)$-annular
  noncrossing permutations $(1,2,3)$ and $(2,1,3)$ get sent to the
  $(2,1)$-annular noncrossing partition with only one block $\{1,2,3\}$.
  However, as is shown in \cite[Proposition~4.4]{Mingo2004}, if there are at
  least two connected cycles, then this map becomes a bijection. Thus every
  result in this paper on annular noncrossing permutations with at least two
  connected cycles works as well for annular noncrossing partitions.
\end{remark}

If an $(n,m)$-annular noncrossing permutation has a connected cycle, it is
called \emph{connected}. Since a disconnected annular noncrossing permutation is
essentially a disjoint union of two noncrossing permutations, in this paper we
will only consider connected annular noncrossing permutations.

We denote by $\anc(n,m)$ the set of connected $(n,m)$-annular noncrossing
permutations.  For $\pi\in\anc(n,m)$, the \emph{exterior cycle type}
(respectively~\emph{interior cycle type}) of $\pi$ is the partition
$(1^{m_1},2^{m_2},\dots)$ where $m_i$ is the number of exterior cycles
(respectively~interior cycles) of size $i$.  The \emph{connected exterior cycle type}
(respectively~\emph{connected interior cycle type}) of $\pi$ is the partition
$(1^{m_1},2^{m_2},\dots)$ where $m_i$ is the number of connected cycles of
exterior size (respectively~interior size) $i$.


For integers $n,m,c,r,s,R,S\ge0$ and $\alpha\in \Par(R,r)$,
$\beta\in \Par(S,s)$, $\lambda\in \Par(n-R,c)$, and $\mu\in \Par(m-S,c)$, we
define the following:
\begin{itemize}
\item $\anc(n,m;c)$ is the set of $\pi\in\anc(n,m)$ with $c$ connected cycles. 
\item $\anc(n,m;c,r,s)$ is the set of $\pi\in\anc(n,m;c)$ with $r$ exterior
  cycles and $s$ interior cycles.
\item $\anc(n,m;c,r,s,R,S)$ is the set of $\pi\in\anc(n,m;c,r,s)$ such that the
  total size of exterior cycles is $R$ and the total size of interior cycles is
  $S$.
\item $\anc(n,m;c,r,s,R,S;\alpha,\beta,\lambda,\mu)$ is the set of
  $\pi\in\anc(n,m)$ with exterior cycle type $\alpha\in \Par(R,r)$, interior
  cycle type $\beta\in \Par(S,s)$, connected exterior cycle type
  $\lambda\in \Par(n-R,c)$, and connected interior cycle type
  $\mu\in \Par(m-S,c)$.
\end{itemize}

\begin{defn} 
  Suppose a cyclic group $C$ of order $n$ acts on a finite set $X$.  Let $X(q)$
  be a polynomial in $q$ with nonnegative integer coefficients.  We say that
  $(X,X(q),C)$ exhibits the \emph{cyclic sieving phenomenon} (CSP) if $X(\omega(c)) =
  |\{x\in X: c(x)=x\}|$ for all $c\in C$. Here, $\omega:C\to \mathbb C^\times$ is a
  group homomorphism of $C$ into the multiplicative group $\mathbb C^\times$ of
  nonzero complex numbers sending a cyclic generator of $C$ to a primitive $n$th
  root of unity.
\end{defn}

The CSP was first introduced by Reiner, Stanton, and White \cite{CSP}.  Recently
many instances of the CSP have been found.  In \cite{SaganCSP}, Sagan gives a
nice survey on the CSP. 

The goal of this section is to find cyclic sieving phenomena for $\anc(n,m)$. To
this end, let $C_1\times C_2$ be the product of two cyclic groups $C_1$ acting
on the exterior circle and $C_2$ acting on the interior circle.  Then $C_1\times
C_2$ gives a bicyclic action on $\anc(n,m)$ by $(c_1,c_2)\pi =
c_1(c_2(\pi))=c_2(c_1(\pi))$. One may wonder if this bicyclic action gives a
``bicyclic sieving phenomenon'' as in \cite{BRS}. However, this is not the case
because of the next proposition.

\begin{prop}
  Let $(c_1,c_2)\in C_1\times C_2$. Then $(c_1,c_2)$ has no fixed points in
  $\anc(n,m)$ unless $c_1$ and $c_2$ have the same order. 
\end{prop}
\begin{proof}
  Let $d_1$ and $d_2$ be the orders of $c_1$ and $c_2$, respectively. Suppose
  $\pi\in \anc(n,m)$ is a fixed point, i.e., $(c_1,c_2)\pi = \pi$.  Let
  $k_1=n/d_1$ and $k_2=m/d_2$.  We can assume that $c_1$ is the map sending
  $i\in [n]$ to $j\in [n]$ with $j\equiv i+k_1 \bmod n$, and $c_2$ is the map
  sending $n+i\in \{n+1,\dots,n+m\}$ to $n+j\in \{n+1,\dots,n+m\}$ with $j\equiv
  i-k_2 \bmod m$.  Note that for each $i\in[n]$, $c_1^{(t)}(i) = i$ implies that
  $t$ is divisible by $d_1$ because if $t=s\cdot d_1 + r$ with $0<r<d_1$, then
\[
c_1^{(t)}(i) \equiv i+k_1\cdot t\equiv i+n\cdot \frac{r}{d_1} \not\equiv i \bmod n.
\]
Similarly for each $i\in\{n+1,\dots,n+m\}$, 
$c_2^{(t)}(i) = i$ implies that $t$ is divisible by $d_2$.

  Consider a connected cycle
  $\gamma=(a_1,\dots,a_u,b_1,\dots,b_v)$ of $\pi$ where $a_1,\dots,a_u\in [n]$
  and $b_1,\dots,b_v\in \{n+1,\dots,n+m\}$. Note that $u>0$ and $v>0$.  Since
  $(c_1,c_2)^{(d_1)}(\pi) = \pi$ and
  $(c_1,c_2)^{(d_1)}(\gamma)=(a_1,\dots,a_u,c_2^{(d_1)}(b_1) ,\dots,
  c_2^{(d_1)}(b_v))$, we have $(c_1,c_2)^{(d_1)}(\gamma) = \gamma$. In
  particular, $c_2^{(d_1)}(b_1) = b_1$, which implies that $d_1$ is divisible by
  $d_2$. Similarly we get that $d_2$ is divisible by $d_1$. Thus $d_1=d_2$.
\end{proof}

Thus we will only consider the elements $(c_1,c_2)$ for which $c_1$ and $c_2$
have the same order. We call such pair $(c_1,c_2)$ an \emph{$(n,m)$-annular
  rotation}, or simply an \emph{annular rotation}.  Note that if $(c_1,c_2)$ is
an $(n,m)$-annular rotation, then the order $d$ of this action divides both $n$
and $m$.


Now we state the main theorem of this paper. The proof is given in
Section~\ref{Proof of CSP}.

\begin{thm}\label{thm:CSP}
  Let $n,m,c,r,s,R,S$ be nonnegative integers and $\alpha\in \Par(R,r)$,
  $\beta\in \Par(S,s)$, $\lambda\in \Par(n-R,c)$, and $\mu\in \Par(m-S,c)$.  Let
  $C$ be the cyclic group of $(n,m)$-annular rotations.  Then the following
  exhibit the cyclic sieving phenomenon:
  \begin{equation}
    \label{eq:kre}
\left(\anc(n,m;c,r,s,R,S;\alpha,\beta,\lambda,\mu), 
\frac{[(n-R)(m-S)]_q}{[c]_q} \qbinom{n}{r}\qbinom{m}{s}
\qbinom{r}{\alpha} \qbinom{s}{\beta} \qbinom{c}{\lambda} \qbinom{c}{\mu},
C\right),
  \end{equation}
  \begin{equation}
    \label{eq:nara1}
\left(\anc(n,m;c,r,s,R,S), 
c \qbinom{n}{r}\qbinom{m}{s}
\qbinom{R-1}{r-1} \qbinom{S-1}{s-1} \qbinom{n-R}{c} \qbinom{m-S}{c}, C
\right),
  \end{equation}
  \begin{equation}
    \label{eq:nara2}
\left(\anc(n,m;c,r,s), 
c\qbinom{n}{r}\qbinom{m}{s} \qbinom{n}{r+c} \qbinom{m}{s+c},C
\right),
  \end{equation}
  \begin{equation}
    \label{eq:nara3}
\left(\anc(n,m;c), c \qbinom{2n}{n-c} \qbinom{2m}{m-c},C\right), 
  \end{equation}
  \begin{equation}
    \label{eq:cat}
\left(\anc(n,m), 
\frac{[2nm]_q}{[m+n]_q} \qbinom{2n-1}{n} \qbinom{2m-1}{m}, C
\right).
  \end{equation}
\end{thm}

Considering the annular rotation of order $1$ in Theorem~\ref{thm:CSP},
i.e., the identity action, we obtain the following enumeration results.

\begin{cor}
We have
\begin{align}
\label{eq:anc}
\#\anc(n,m;c,r,s,R,S;\alpha,\beta,\lambda,\mu)
&=\frac{(n-R)(m-S)}{c}  \binom{n}{r}\binom{m}{s} 
\binom{r}{\alpha} \binom{s}{\beta} \binom{c}{\lambda} \binom{c}{\mu},\\
\#\anc(n,m;c,r,s,R,S)
&=c \binom{n}{r}\binom{m}{s}
\binom{R-1}{r-1} \binom{S-1}{s-1} \binom{n-R}{c} \binom{m-S}{c},\\
\#\anc(n,m;c,r,s)
&= c \binom{n}{r}\binom{m}{s} \binom{n}{r+c} \binom{m}{s+c},\\
\#\anc(n,m;c)
&= c \binom{2n}{n-c} \binom{2m}{m-c},\\
\label{eq:anc_cat}
\#\anc(n,m)
&= \frac{2nm}{m+n} \binom{2n-1}{n} \binom{2m-1}{m}.
\end{align}
\end{cor}

If an annular noncrossing permutation is invariant under an annular rotation of
order $2$, it is called an \emph{annular noncrossing permutation of type $B$}.
We define $\anc_B(n,m)$ to be the set of connected $(2n,2m)$-annular noncrossing
permutations of type $B$.  We then define
\begin{align*}
\anc_B(n,m;c) &= \anc_B(n,m) \cap \anc(2n,2m;2c),\\
\anc_B(n,m;c,r,s) &= \anc_B(n,m) \cap \anc(2n,2m;2c,2r,2s),\\
\anc_B(n,m;c,r,s,R,S) &= \anc_B(n,m) \cap \anc(2n,2m;2c,2r,2s,2R,2S),\\
\anc_B(n,m;c,r,s,R,S;\alpha,\beta,\lambda,\mu)
&=\anc_B(n,m) \\
&\qquad \cap \anc(2n,2m;2c,2r,2s,2R,2S;2\alpha,2\beta,2\lambda,2\mu),
\end{align*}
where $2\lambda = (2\lambda_1,2\lambda_2,\dots)$.

Notice that every connected annular noncrossing permutation of type $B$ contains
at least two connected cycles.  Thus annular noncrossing permutations of type
$B$ are in bijection with annular noncrossing partitions of type $B$.

Considering an annular rotation of order $2$ in Theorem~\ref{thm:CSP} we obtain
the enumeration results below.

\begin{cor}
We have
\begin{align}
\#\anc_B(n,m;c,r,s,R,S;\alpha,\beta,\lambda,\mu)
&=\frac{2(n-R)(m-S)}{c}  \binom{n}{r}\binom{m}{s} 
\binom{r}{\alpha} \binom{s}{\beta} \binom{c}{\lambda} \binom{c}{\mu},\\
\#\anc_B(n,m;c,r,s,R,S)
&=2c \binom{n}{r}\binom{m}{s}
\binom{R-1}{r-1} \binom{S-1}{s-1} \binom{n-R}{c} \binom{m-S}{c},\\
\label{eq:b1}
\#\anc_B(n,m;c,r,s)
&= 2c \binom{n}{r}\binom{m}{s} \binom{n}{r+c} \binom{m}{s+c},\\
\label{eq:b2}
\#\anc_B(n,m;c)
&= 2c \binom{2n}{n-c} \binom{2m}{m-c},\\
\label{eq:b3}
\#\anc_B(n,m)
&= \frac{nm}{m+n} \binom{2n}{n} \binom{2m}{m}.
\end{align}
\end{cor}

We note that \eqref{eq:anc_cat} was first proved by Mingo and Nica
\cite[Corollary~6.7]{Mingo2004} and \eqref{eq:b1}, \eqref{eq:b2}, and
\eqref{eq:b3} were first proved by Goulden, Nica and Oancea \cite[Equations
(4.6), (4.7), (4.9)]{GNO}.

\section{Annular $q$-Kreweras numbers}
\label{sec:annular-q-kreweras}

In this section we define annular versions of $q$-analogs of Kreweras, Narayana,
and Catalan numbers, and evaluate their sums. These numbers are closely related
to the polynomials in Theorem~\ref{thm:CSP}.

For brevity we will use the following abbreviations throughout this section:
\begin{align*}
  X &= {c(c-1)},  \\
  Y &= {r(c+r)+s(c+s)},  \\
  Z &= {r(n-c-R)+s(m-c-S)},  \\
  W &=
  {r(R-r)+s(S-s)+c(n-R-c)+c(m-S-c)-\tau(\alpha)-\tau(\beta)-\tau(\lambda)-\tau(\mu)}.
\end{align*}

\begin{defn}
The \emph{annular $q$-Kreweras number
   $$\Kre=\Kre(n,m;c,r,s,R,S;\alpha,\beta,\lambda,\mu)$$} is defined by
\[
\Kre = q^X q^Y q^Z q^W \frac{[nm]_q}{[n]_q[m]_q} \frac{[2c]_q}{2} 
\frac{[n-R]_q[m-S]_q}{[c]_q^2}  \qbinom{n}{r}\qbinom{m}{s} 
\qbinom{r}{\alpha} \qbinom{s}{\beta} \qbinom{c}{\lambda} \qbinom{c}{\mu}.
\]
The \emph{annular $q$-Narayana number $\Nara_1=\Nara_1(n,m;c,r,s,R,S)$ of type
  $1$} is defined by
\[
\Nara_1 =  q^X q^Y q^Z \frac{[nm]_q}{[n]_q[m]_q} \frac{[2c]_{q}}{2}
\qbinom{n}{r}\qbinom{m}{s}
\qbinom{R-1}{r-1} \qbinom{S-1}{s-1} \qbinom{n-R}{c} \qbinom{m-S}{c}.
\]
The \emph{annular $q$-Narayana number $\Nara_2=\Nara_2(n,m;c,r,s)$ of type $2$}
is defined by
\[
\Nara_2 = q^X q^Y  \frac{[nm]_q}{[n]_q[m]_q} \frac{[2c]_{q}}{2} 
\qbinom{n}{r}\qbinom{m}{s} \qbinom{n}{r+c} \qbinom{m}{s+c}.
\]
The \emph{annular $q$-Narayana number
    $\Nara_3=\Nara_3(n,m;c)$ of type $3$} is defined by
\[
\Nara_3 = q^X \frac{[nm]_q}{[n]_q[m]_q} \frac{[2c]_{q}}{2} 
\qbinom{2n}{n-c} \qbinom{2m}{m-c}.
\]
The \emph{annular $q$-Catalan number $\Cat=\Cat(n,m)$} is defined by
\[
\Cat = \frac{[nm]_q}{2[m+n]_q} \qbinom{2n}{n} \qbinom{2m}{m}.
\]
\end{defn}

In the introduction we saw that the sum of $q$-Kreweras numbers is equal to the
$q$-Narayana number, and the sum of $q$-Narayana numbers is equal to the
$q$-Catalan number. We show that annular versions of these numbers have similar
properties. In order to do this, we prove three lemmas.

The first lemma is due to Reiner and Sommers \cite{ReinerSommers}.  We
include their elegant proof as well.
\begin{lem}\cite{ReinerSommers}\label{lem:sum2}
  Let $\tau(\lambda) = \sum_{i\ge1} \lambda_i' \lambda_{i+1}'$, where $\lambda'$
  is the transpose of $\lambda$. Then
\[
\sum_{\lambda\in \Par(n,k)}q^{k(n-k)-\tau(\lambda)} \qbinom{k}{\lambda}
=\qbinom{n-1}{k-1}.
\]
\end{lem}
\begin{proof}
Let $\lambda=(1^{m_1},2^{m_2},\dots)$. Then $m_1+2m_2+\dots=n$ and 
$m_1+m_2+\dots=k$. Since $\lambda'_i=m_i+m_{i+1}+\cdots$, we have
\[
q^{k(n-k)-\tau(\lambda)} \qbinom{k}{\lambda}
= q^{(k-\lambda'_1)\lambda'_{2}} \qbinom{\lambda'_1}{\lambda'_2}
q^{(k-\lambda'_2)\lambda'_{3}} \qbinom{\lambda'_2}{\lambda'_3} \cdots . 
\]
Thus we can rewrite the identity as follows.
\begin{equation}
  \label{eq:2}
\qbinom{n-1}{k-1} = \sum_{\mu\in \Par(n), \mu_1=k} 
q^{(k-\mu_1)\mu_{2}} \qbinom{\mu_1}{\mu_2}
q^{(k-\mu_2)\mu_{3}} \qbinom{\mu_2}{\mu_3} \cdots . 
\end{equation}
The left hand side of \eqref{eq:2} is the sum of $q^{|\nu|}$ for all partitions
$\nu$ contained in a $k\times(n-k)$ rectangle where the $k$th part of $\nu$ is
$0$.  For such a partition $\nu$ we define points $Q_1,P_1,Q_2,P_2,\dots$ as
follows.  Let $Q_1$ be the upper right corner of the rectangle. When $Q_i$ is
defined, let $P_i$ be the point on the base of the rectangle which is vertically
below $Q_i$. When $P_i$ is defined, let $Q_{i+1}$ be the intersection of the
border of $\nu$ and the northwest diagonal ray starting from $P_i$. We define
the sequence of points until we reach the bottom-left corner of the
rectangle. Since $\nu$ has no cells in the $k$th row of the rectangle, we can
always complete this sequence.  Let $\mu$ be the partition whose $i$th part is
equal to the length of the segment $P_{i-1}P_i$, where $P_0=Q_1$. Then
$\mu\in \Par(n)$ and $\mu_1=k$.  It is easy to see that the sum of $q^{|\nu|}$
for partitions $\nu$ which give $\mu$ is equal to the summand in \eqref{eq:2},
see Figure~\ref{fig:decomp}.  This proves \eqref{eq:2}.
\end{proof}

\begin{figure}
  \centering
\psset{unit=25pt}
\begin{pspicture}(0,-1)(10,9)
\psframe(0,0)(10,8)
\psline[linestyle=dotted](0,2)(2,0)
\psline[linestyle=dotted](2,3)(5,0)
\psline[linestyle=dotted](5,5)(10,0)
\psline[linestyle=dotted](5,0)(5,8)
\psline[linestyle=dotted](2,5)(10,5)
\psline[linestyle=dotted](2,0)(2,8)
\psline[linestyle=dotted](0,2)(2,2)
\psline[linestyle=dotted](0,3)(5,3)
\psline[linewidth=2pt](0,0)(0,2)(1,2)(1,2.5)(2,2.5)(2,3.5)(3,3.5)(3,4)(4,4)(4,5)
(6,5)(6,6)(9,6)(9,7)(10,7)(10,8)
\rput(5,8.5){\psscaleboxto(9.8,.5){\rotateright{\{}}} \rput(5,9){$n-k$}
\rput(10.5,4){\psscaleboxto(.5,7.8){\}}} \rput[l](11,4){$k=\mu_1$}
\rput(1,-.5){\psscaleboxto(1.8,-.5){\rotateright{\{}}} \rput(1,-1){$\mu_4$}
\rput(3.5,-.5){\psscaleboxto(2.8,-.5){\rotateright{\{}}} \rput(3.5,-1){$\mu_3$}
\rput(7.5,-.5){\psscaleboxto(4.8,-.5){\rotateright{\{}}} \rput(7.5,-1){$\mu_2$}
\rput(.5,.5){$P_4$} \rput(2.5,.5){$P_3$} \rput(5.5,.5){$P_2$}
\rput(10.5,-.5){$P_1$}
\rput(-.5,2){$Q_4$} \rput(1.5,3.5){$Q_3$}
\rput(4.5,5.5){$Q_2$}  \rput[lt](10.2,8.5){$Q_1=P_0$}
\rput(1,5.5){$q^{(k-\mu_3)\mu_4}$}
\rput(3.5,6.5){$q^{(k-\mu_2)\mu_3}$}
\rput(7,7){$\qbinom{\mu_1}{\mu_2}$}
\rput(3,4.5){$\qbinom{\mu_2}{\mu_3}$}
\rput(.5,2.5){$\qbinom{\mu_3}{\mu_4}$}
\end{pspicture}
  \caption{We decompose $\nu$ and get $\mu$.}
  \label{fig:decomp}
\end{figure}



\begin{lem}\label{lem:sum3}
For fixed integers $n,r,c$, we have
\[
\sum_{R\ge0} q^{r(n-c-R)} \qbinom{R-1}{r-1} \qbinom{n-R}{c}
= \qbinom{n}{r+c}.
\]
\end{lem}
\begin{proof}
  This can be proved by a standard technique considering the largest rectangle
  with width $r$ contained in partitions inside an $(n-r-c)\times(r+c)$
  rectangle. This can also be proved by using the $q$-Chu-Vandermonde theorem
\cite[II.7]{GR}.
\end{proof}


\begin{lem}\label{lem:sum1}
Let $n$, $m$, and $k$ be nonnegative integers. Then 
\[
\sum_{c\ge0} q^{c(c-1+k)} [2c+k]_q 
\qbinom{2n+k}{n-c}\qbinom{2m+k}{m-c}
=\frac{[n+k]_q [m+k]_q}{[n+m+k]_q}
\qbinom{2n+k}{n+k} \qbinom{2m+k}{m+k}.
\]
\end{lem}
\begin{proof}
  It is straightforward to check that
\begin{equation}
  \label{eq:5}
q^{c(c-1+k)} [n+m+k]_q [2c+k]_q =
q^{c(c-1+k)} [n+c+k]_q [m+c+k]_q - q^{(c+1)(c+k)}[n-c]_q[m-c]_q. 
\end{equation}
Let $\sigma(c) = c(c-1+k)$. Then by \eqref{eq:5} the left hand side is equal
to
\begin{align*}
&\frac{1}{[n+m+k]_q} \\
&\qquad \times\sum_{c\ge0} \big( 
q^{\sigma(c)} [n+c+k]_q [m+c+k]_q 
- q^{\sigma(c+1)}[n-c]_q[m-c]_q \big)
\qbinom{2n+k}{n-c}\qbinom{2m+k}{m-c}\\
&= \frac{[2n+k]_q [2m+k]_q}{[n+m+k]_q} \\
&\qquad \times\sum_{c\ge0} \left( 
q^{\sigma(c)} 
\qbinom{2n+k-1}{n-c} \qbinom{2m+k-1}{m-c} 
- q^{\sigma(c+1)}
\qbinom{2n+k-1}{n-c-1} \qbinom{2m+k-1}{m-c-1}
\right)\\
&= \frac{[2n+k]_q [2m+k]_q}{[n+m+k]_q} 
\qbinom{2n+k-1}{n} \qbinom{2m+k-1}{m}\\
&=\frac{[n+k]_q [m+k]_q}{[n+m+k]_q}
\qbinom{2n+k}{n+k} \qbinom{2m+k}{m+k}. 
\end{align*}
We note that this can also be proved by using the very-well-poised $_6\phi_5$
summation formula \cite[II.21]{GR} with $c=aq^{n+1}$.
\end{proof}



\begin{thm}\label{thm:kreweras sum}
We have
\begin{align*}
  \sum_{\substack{\alpha\in \Par(R,r)\\
\beta\in \Par(S,s)\\
\lambda\in \Par(n-R,c)\\
\mu\in \Par(m-S,c)}}
\Kre(n,m;c,r,s,R,S;\alpha,\beta,\lambda,\mu)
& = \Nara_1(n,m;c,r,s,R,S),\\
\sum_{R,S\ge0} \Nara_1(n,m;c,r,s,R,S) &= \Nara_2(n,m;c,r,s),\\
\sum_{r,s\ge0} \Nara_2(n,m;c,r,s) &= \Nara_3(n,m;c),\\
\sum_{c\ge0} \Nara_3(n,m;c) &= \Cat(n,m).
\end{align*}
\end{thm}
\begin{proof}
  The first, second, and fourth identities follow from Lemmas~\ref{lem:sum2},
  \ref{lem:sum3}, and \ref{lem:sum1}, respectively.  The third identity follows
  from the $q$-Chu--Vandermonde identity:
\[
\sum_{i\ge0} q^{i(m-k+i)} \qbinom{m}{k-i} \qbinom{n}{i} 
=\qbinom{m+n}{k}.
\]
\end{proof}

In the next section we show that the annular $q$-Kreweras numbers, the three
types of annular $q$-Narayana numbers, and the annular $q$-Catalan numbers, when
multiplied by 2, are polynomials in $q$ with nonnegative integer coefficients.
See Proposition~\ref{prop:polynomiality}. Unfortunately, these numbers are not
polynomials with integer coefficients. For instance, $\Cat(1,1) = (1+q)/2$.


\section{Polynomiality and nonnegativity}
\label{sec:polyn-nonn}

A polynomial $f(x)=a_0+a_1x+\cdots+a_nx^n$ is called \emph{symmetric} if
$a_i=a_{n-i}$ for $i=0,1,\dots,n$, and \emph{unimodal} if $a_0\le a_1\le
\cdots\le a_j \ge a_{j+1}\ge\cdots\ge a_n$ for some $j$.  We denote by $\Z[q]$
(respectively $\N[q]$) the set of polynomials in $q$ with integer coefficients
(respectively nonnegative integer coefficients).

We will use the following three lemmas.

\begin{lem}\cite[Theorem~3.9]{Andrews} \label{lem:andrews}
 If $f(x)$ and $g(x)$ are symmetric,
  unimodal polynomials, then so is $f(x)g(x)$. 
\end{lem}

\begin{lem}\cite[Proposition~10.1 (iii)]{CSP}\label{lem:RSW}
  If $f(q) = h(q)/[k]_q \in\Z[q]$, and $h(q)\in \N[q]$ has a symmetric, unimodal
  coefficient sequence, then $f(q)\in \N[q]$.
\end{lem}

As is mentioned in \cite{CSP}, the above lemma is also derived implicitly in
\cite{Andrews2004}.

\begin{lem}\label{lem:polynomial}
  For nonnegative integers $N,n,k$ with $N\ge n$ and a partition
  $\lambda\in \Par(n,k)$, we have
\[
\frac{[n]_q}{[k]_q} \qbinom{k}{\lambda}\in \N[q], \qquad
\frac{[N-n]_q}{[N]_q} \qbinom{N}{k} \qbinom{k}{\lambda}\in \N[q].
\]
\end{lem}
\begin{proof}
We claim that
\begin{equation}
  \label{eq:3}
\frac{[n]_q}{[k]_q} \qbinom{k}{\lambda}
=\frac{1-q^n}{1-q^k} \qbinom{k}{\lambda}\in \Z[q].
\end{equation}
Assuming the claim let us show the lemma.  By \eqref{eq:3} and the fact
$[N]_q=[N-n]_q+q^{N-n}[n]_q$ we also have
\begin{align*}
\frac{[N-n]_q}{[N]_q} \qbinom{N}{k} \qbinom{k}{\lambda}
&=\frac{[N]_q-q^{N-n}[n]_q}{[N]_q} \qbinom{N}{k} \qbinom{k}{\lambda}\\
&=\qbinom{N}{k} \qbinom{k}{\lambda} - 
q^{N-n} \qbinom{N-1}{k-1} \cdot 
\frac{[n]_q}{[k]_q} \qbinom{k}{\lambda} \in \Z[q].
\end{align*}
It is known that $q$-multinomial coefficients
$\qbinom{m_1+\cdots+m_\ell}{m_1,\dots,m_\ell}$ are symmetric and unimodal.  See
for instance \cite{Stanley1980}. Thus by Lemmas~\ref{lem:andrews} and
\ref{lem:RSW} we get $\frac{[n]_q}{[k]_q} \qbinom{k}{\lambda}\in \N[q]$ and
$\frac{[N-n]_q}{[N]_q} \qbinom{N}{k} \qbinom{k}{\lambda}\in \N[q]$.

We now show \eqref{eq:3}. We will use the $q$-Pochhammer symbol 
\[
(q;q)_r = (1-q)(1-q^2)\cdots(1-q^r).
 \]
 Note that $\qbinom{n}{k} = \frac{(q;q)_n}{(q;q)_k(q;q)_{n-k}}$.

 Since
\[
q^k-1 = \prod_{j=1}^k (q-\omega_j),
\]
where $\omega_1,\omega_2,\dots,\omega_k$ are the $k$th roots of unity, in order
to prove \eqref{eq:3}, it is sufficient to show that $q-\omega_j$ divides
$(1-q^n) \qbinom{k}{\lambda}$ for all $j=1,2,\dots,k$. Fix an integer $j$ and
suppose $\omega_j$ is a primitive $r$th root of unity. Then $r$ divides
$k$. Note that $q-\omega_j$ divides $q^s-1$ if and only if $r$ divides $s$.
Note also that the multiplicity of $q-\omega_j$ as a factor of $q^s-1$ is at
most $1$. Thus the multiplicity of the factor $q-\omega_j$ in $(q;q)_s$ is equal
to $\flr{s/r}$.  We have two cases as follows. 

\textsc{Case 1}: $r$ divides $n$. Then $q-\omega_j$ divides $q^n-1$ and we
are done. 

\textsc{Case 2}: $r$ does not divide $n$.  Let $\lambda=(1^{m_1},2^{m_2},\dots,
\ell^{m_{\ell}})$. Then we have $n = \sum_{i=1}^\ell i \cdot m_i$, $k =
\sum_{i=1}^\ell m_i$, and 
\begin{equation}
  \label{eq:4}
\qbinom{k}{\lambda} = \frac{(q;q)_{m_1+m_2+\cdots+m_\ell}}
{(q;q)_{m_1} (q;q)_{m_2} \cdots (q;q)_{m_\ell}}. 
\end{equation}
The multiplicities of the factor $q-\omega_j$ in the numerator and denominator
of \eqref{eq:4} are $\flr{k/r}$ and $\flr{m_1/r} + \flr{m_2/r} +
\cdots + \flr{m_\ell/r}$, respectively. Since $r$ does not divide $n$, at least one of
$m_1,m_2,\dots, m_\ell$ is not a multiple of $r$. Thus we have
\[
\flr{\frac{m_1}{r}} + \flr{\frac{m_2}r} + \cdots + \flr{\frac{m_\ell}r}
< \frac{m_1}{r} + \frac{m_2}r + \cdots + \frac{m_\ell}r = 
\frac{k}{r} = \flr{\frac{k}{r}},
\]
which implies that $q-\omega_j$ divides $\qbinom{k}{\lambda}$. This finishes the
proof of \eqref{eq:3}.
\end{proof}

\begin{prop}\label{prop:polynomiality}
We have
\begin{align*}
2\Kre(n,m;c,r,s,R,S;\alpha,\beta,\lambda,\mu) \in \N[q],\\
2\Nara_1(n,m;c,r,s,R,S) \in \N[q],\\
2\Nara_2(n,m;c,r,s) \in \N[q],\\
2\Nara_3(n,m;c) \in \N[q],\\
2\Cat(n,m) \in \N[q].
\end{align*}
\end{prop}
\begin{proof}
By Theorem~\ref{thm:kreweras sum}, it is sufficient to show the first statement
for the annular $q$-Kreweras numbers. 
Since $2\Kre(n,m;c,r,s,R,S;\alpha,\beta,\lambda,\mu)$ is equal to 
\[
q^X q^Y q^Z q^W \frac{[2c]_q}{[c]_q} 
\left( \frac{[n-R]_q}{[n]_q} \qbinom{n}{r}\qbinom{r}{\alpha} \right)
\left( \frac{[m-S]_q}{[c]_q} \qbinom{c}{\mu} \right)
\left( \frac{[nm]_q}{[m]_q} \qbinom{m}{s}
\qbinom{s}{\beta} \qbinom{c}{\lambda} \right),
\]
we are done by Lemma~\ref{lem:polynomial}. 
\end{proof}

We now prove that the rational functions in Theorem~\ref{thm:CSP} are actually
polynomials in $q$ with nonnegative integer coefficients.

\begin{prop}
We have
\[
\frac{[(n-R)(m-S)]_q}{[c]_q} \qbinom{n}{r}\qbinom{m}{s}
\qbinom{r}{\alpha} \qbinom{s}{\beta} \qbinom{c}{\lambda} \qbinom{c}{\mu}
\in\N[q],
\]
\[
\frac{[2nm]_q}{[m+n]_q} \qbinom{2n-1}{n} \qbinom{2m-1}{m}\in\N[q].
\]
\end{prop}
\begin{proof}
By Lemma~\ref{lem:polynomial}, $\frac{[m-S]_q}{[c]_q} \qbinom{c}{\mu}$ is a
polynomial. Since
\begin{equation}
  \label{eq:11}
\frac{[(n-R)(m-S)]_q}{[m-S]_q} \qbinom{n}{r}\qbinom{m}{s}
\qbinom{r}{\alpha} \qbinom{s}{\beta} \qbinom{c}{\lambda} 
\frac{[m-S]_q}{[c]_q} \qbinom{c}{\mu},
\end{equation}
and $[ab]_q = [a]_q [b]_{q^a} = [b]_q[a]_{q^b}$, we obtain the first statement.

For the second statement, by Lemmas~\ref{lem:andrews} and \ref{lem:RSW}, it is
sufficient to show that
\[
\frac{[2nm]_q}{[m+n]_q} \qbinom{2n-1}{n} \qbinom{2m-1}{m}
= \frac{1-q^{2nm}}{1-q^{n+m}} \qbinom{2n-1}{n} \qbinom{2m-1}{m}
\in\Z[q].
\]
We will use the same idea as in the proof of Lemma~\ref{lem:polynomial}.  Let
$\omega_1,\omega_2,\dots,\omega_{n+m}$ be the $(n+m)$th roots of unity.  We
need to show that $(q-\omega_j)$ divides $(1-q^{2nm}) \qbinom{2n-1}{n}
\qbinom{2m-1}{m}$ for $j=1,2,\dots,n+m$. Fix $j$ and suppose $\omega_j$ is a
primitive $p$th root of unity. If $p$ divides $nm$, then $q-\omega_j$ divides
$1-q^{2nm}$. Suppose $p$ does not divide $nm$. Then we can write
$n = A_1p+B_1$ and $m=A_2p+B_2$, where $0<B_1,B_2<p$. Since $p$ divides $n+m$,
we must have $B_1+B_2=p$. Without loss of generality we can assume that $B_1\ge
\frac p2$. Since
\[
(1-q^{2nm}) \qbinom{2n-1}{n} \qbinom{2m-1}{m}
= \frac{1-q^{2nm}}{1-q^{2n}} (1-q^n) \qbinom{2n}{n} \qbinom{2m-1}{m},
\]
and the multiplicity of $q-\omega_j$ in $\qbinom{2n}{n}$ is $\flr{\frac {2n}p} -
\flr{\frac np} - \flr{\frac np} = 2A_1+1-A_1-A_1=1$, we obtain that $q-\omega_j$
divides $(1-q^{2nm}) \qbinom{2n-1}{n} \qbinom{2m-1}{m}$. This finishes the proof
of the second statement.
\end{proof}


\section{Proof of cyclic sieving phenomena}
\label{Proof of CSP}



For a partition $\lambda=(1^{m_1},2^{m_2},\dots)$ we denote by $\mathfrak
S(\lambda)$ the set of rearrangements of the sequence
\[
\overbrace{1,\dots,1}^{m_1},\overbrace{2,\dots,2}^{m_2},\dots.
\]
 In other words,
each element in $\mathfrak S(\lambda)$ is a sequence $(a_1,a_2,\dots)$ where
each integer $i$ appears exactly $m_i$ times.  If each $m_i$ is divisible by
$d$, we define $\lambda/d=(1^{m_1/d}, 2^{m_2/d},\dots)$. In this case we say
that $\lambda$ is \emph{divisible} by $d$.

\begin{lem}\label{lem:div}
  If there is a permutation $\pi\in
  \anc(n,m;c,r,s,R,S;\alpha,\beta,\lambda,\mu)$ invariant under an annular
  rotation of order $d$, then all of $n,m,c,r,s,R,S,\alpha,\beta,\lambda,\mu$
  are divisible by $d$. 
\end{lem}
\begin{proof}
  Since this is obvious when $d=1$, we can assume that $d\ge2$.  Suppose that $\pi$
  is invariant under an annular rotation $(c_1,c_2)$ of order $d$. It suffices
  to show the following claim. 

  \textbf{Claim}: for every cycle $\gamma$ of $\pi$, we have
  $(c_1,c_2)^{(i)}(\gamma)\ne \gamma$ for all $i=1,2,\dots, d-1$.

  We first consider a connected cycle $\gamma=(a_1,\dots,a_u,b_1,\dots,b_v)$
  with $a_1,\dots,a_u\in [n]$ and $b_1,\dots,b_v\in \{n+1,\dots,n+m\}$.  Suppose
  for contradiction that $(c_1,c_2)^{(i)}(\gamma) = \gamma$ for some $1\le i\le
  d-1$.  Then we get
\[
\gamma=(c_1,c_2)^{(i)}(\gamma) =
  ((c_1,c_2)^{(i)}(a_1),\dots,(c_1,c_2)^{(i)} (a_u),(c_1,c_2)^{(i)}
  (b_1),\dots,(c_1,c_2)^{(i)} (b_v)).
\] 
Since the expression $\gamma=(a_1,\dots,a_u,b_1,\dots,b_v)$ is unique, we have
$(c_1,c_2)^{(i)} (a_1)=a_1$, which is impossible because $1\le i\le d-1$.  Thus
$(c_1,c_2)^{(i)}(\gamma)$ are distinct for all $i=0,1,2\dots,d-1$.  In the
diagram of $\pi$ we have $d$ distinct arrows from $(c_1,c_2)^{(i)}(a_u)$ to
$(c_1,c_2)^{(i)}(b_1)$ for $i=0,1,2\dots,d-1$. These arrows then divide the
annulus into $d$ regions. By the noncrossing property, we obtain the claim. 
\end{proof}

Now we are ready to enumerate annular noncrossing permutations with given cycle
types. 

\begin{thm}\label{thm:rot_inv}
  The number of permutations $\pi\in
  \anc(n,m;c,r,s,R,S;\alpha,\beta,\lambda,\mu)$ invariant under an annular
  rotation of order $d$ is equal to
\[
d\cdot \frac{(\widehat{n}-\widehat{R})(\widehat{m}-\widehat{S})}{\widehat{c}}
\binom{\widehat{n}}{\widehat{r}}\binom{\widehat{m}}{\widehat{s}}
\binom{\widehat{r}}{\widehat{\alpha}} \binom{\widehat{s}}{\widehat{\beta}}
\binom{\widehat{c}}{\widehat{\lambda}} \binom{\widehat{c}}{\widehat{\mu}},
\]
if all of $n,m,c,r,s,R,S,\alpha,\beta,\lambda,\mu$ are divisible by $d$, and $0$
otherwise.  Here $\widehat Z$ means $Z/d$.
\end{thm}
\begin{proof}[Sketch of Proof]
  Since the proof is similar to those in \cite[Proposition~4.2]{GNO} and in
  \cite[Proposition~4.1]{Kim}, we will only give a sketch with an example.

  By Lemma~\ref{lem:div} we can assume that all of
  $n,m,c,r,s,R,S,\alpha,\beta,\lambda,\mu$ are divisible by $d$.

  Let $(c_1,c_2)$ be an annular rotation of order $d$.  We will find a bijection
  between the set
\[
\A=\left\{(\gamma,\pi)\left| 
    \begin{array}{l}
\pi\in \anc(n,m;c,r,s,R,S;\alpha,\beta,\lambda,\mu), 
(c_1,c_2)\pi = \pi,\\
\mbox{$\gamma$ is a connected cycle of $\pi$}
    \end{array}
\right.\right\}
\]
and the set
\[
\B = \left\{(a,b,R^E,R^I,V^E,V^I,V^{CE},V^{CI}) \left| 
\begin{array}{l}
a\in[n - R], 
b\in[m - S], \\
R^E\subset[\widehat n],
R^I\subset[\widehat m],
|R^E|=\widehat r, |R^I|=\widehat s,
\\
V^E\in \mathfrak S(\widehat \alpha), 
V^I\in \mathfrak S(\widehat \beta),\\ 
V^{CE}\in \mathfrak S(\widehat \lambda), 
V^{CI}\in \mathfrak S(\widehat \mu)
\end{array}
\right.
\right\}.
\]

\begin{figure}
  \centering
\psset{unit=1cm, dotsize=5pt, linewidth=0.1pt}
\psset{linewidth=1.5pt, nodesep =2pt}
\def\vput#1{\pnode(#1,1){#1} \pscircle*(#1,1){.1} \rput(#1,.5){$#1$}}
\def\vvput#1#2{\pnode(#1,1){#1} \pscircle*(#1,1){.1} \rput(#1,.5){$#2$}}
\def\edge#1#2{\ncarc[arcangle=50]{#1}{#2}}
\def\activevertex#1{\pscircle[linecolor=red](#1,1){.2}}

\def\cput#1#2#3#4{\pnode(#1){#4} \pscircle*(#1){2pt} \uput[#2](#1){$#3$}}
\def\dotcput#1#2#3#4{\pnode(#1){#4} \pscircle*(#1){2pt}}
\def\labelcput#1#2#3#4{\uput[#2](#1){$#3$}}

\def\cedge#1#2{\ncline{->}{#1}{#2}}

\begin{pspicture}(-6,-5.5)(6,5.5) 
\small
\cput{0.5226,4.973}{84.00}{1}{1}
\cput{1.545,4.755}{72.00}{2}{2}
\cput{2.500,4.330}{60.00}{3}{3}
\cput{3.346,3.716}{48.00}{4}{4}
\cput{4.045,2.939}{36.00}{5}{5}
\cput{4.568,2.034}{24.00}{6}{6}
\cput{4.891,1.040}{12.00}{7}{7}
\cput{5.000,0.0000}{0.0000}{8}{8}
\cput{4.891,-1.040}{-12.00}{9}{9}
\cput{4.568,-2.034}{-24.00}{10}{10}
\cput{4.045,-2.939}{-36.00}{11}{11}
\cput{3.346,-3.716}{-48.00}{12}{12}
\cput{2.500,-4.330}{-60.00}{13}{13}
\cput{1.545,-4.755}{-72.00}{14}{14}
\cput{0.5226,-4.973}{-84.00}{15}{15}
\cput{-0.5227,-4.973}{-96.00}{16}{16}
\cput{-1.545,-4.755}{-108.0}{17}{17}
\cput{-2.500,-4.330}{-120.0}{18}{18}
\cput{-3.346,-3.716}{-132.0}{19}{19}
\cput{-4.045,-2.939}{-144.0}{20}{20}
\cput{-4.568,-2.034}{-156.0}{21}{21}
\cput{-4.891,-1.040}{-168.0}{22}{22}
\cput{-5.000,0.0000}{-180.0}{23}{23}
\cput{-4.891,1.040}{-192.0}{24}{24}
\cput{-4.568,2.034}{-204.0}{25}{25}
\cput{-4.045,2.939}{-216.0}{26}{26}
\cput{-3.346,3.716}{-228.0}{27}{27}
\cput{-2.500,4.330}{-240.0}{28}{28}
\cput{-1.545,4.755}{-252.0}{29}{29}
\cput{-0.5227,4.973}{-264.0}{30}{30}

\cput{1.414,-1.414}{135.0}{31}{31}
\cput{1.813,-0.8452}{155.0}{32}{32}
\cput{1.992,-0.1742}{175.0}{33}{33}
\cput{1.932,0.5176}{195.0}{34}{34}
\cput{1.638,1.147}{215.0}{35}{35}
\cput{1.147,1.638}{235.0}{36}{36}
\cput{0.5176,1.932}{255.0}{37}{37}
\cput{-0.1743,1.992}{275.0}{38}{38}
\cput{-0.8452,1.813}{295.0}{39}{39}
\cput{-1.414,1.414}{315.0}{40}{40}
\cput{-1.813,0.8451}{335.0}{41}{41}
\cput{-1.992,0.1743}{355.0}{42}{42}
\cput{-1.932,-0.5176}{375.0}{43}{43}
\cput{-1.638,-1.147}{395.0}{44}{44}
\cput{-1.147,-1.638}{415.0}{45}{45}
\cput{-0.5176,-1.932}{435.0}{46}{46}
\cput{0.1744,-1.992}{455.0}{47}{47}
\cput{0.8452,-1.813}{475.0}{48}{48}

\psline[linearc=.5]{->}(0.5176,1.932)(0.4,3)(-1.4,2.5)(-1.414,1.414 )
\psline{->}(3.346,3.716)(0.5176,1.932)
\psline[linearc=.5]{->}(-2.500,4.330)(3.346,3.716)
\psline{->}(-3.346,3.716)(-2.500,4.330)
\psline{->}(-1.414,1.414)(-3.346,3.716)
\psline{->}(-1.545,4.755)(1.545,4.755)
\psline{->}(1.545,4.755)(2.500,4.330)
\psline{->}(2.500,4.330)(-1.545,4.755)
\psline{->}(4.045,2.939)(4.568,2.034)
\psline{->}(4.568,2.034)(1.147,1.638)
\psline{->}(1.147,1.638)(4.045,2.939)
\rput(0,.07){\psline{->}(-0.5227,4.973)(0.5226,4.973)}
\rput(0,-.07){\psline{<-}(-0.5227,4.973)(0.5226,4.973)}
\rput(0,.07){\psline{<-}(-0.1743,1.992)(-0.8452,1.813)}
\rput(0,-.07){\psline{->}(-0.1743,1.992)(-0.8452,1.813)}

\nccircle[angleA=-60]{<-}{35}{4pt}
\nccircle[angleA=60,linestyle=dashed]{<-}{41}{4pt}
\nccircle[angleA=180,linestyle=dotted]{<-}{47}{4pt}

\rput{120}(0,0){\psset{linestyle=dashed}
\psline[linearc=.5]{->}(0.5176,1.932)(0.4,3)(-1.4,2.5)(-1.414,1.414 )
\psline{->}(3.346,3.716)(0.5176,1.932)
\psline[linearc=.5]{->}(-2.500,4.330)(3.346,3.716)
\psline{->}(-3.346,3.716)(-2.500,4.330)
\psline{->}(-1.414,1.414)(-3.346,3.716)
\psline{->}(-1.545,4.755)(1.545,4.755)
\psline{->}(1.545,4.755)(2.500,4.330)
\psline{->}(2.500,4.330)(-1.545,4.755)
\psline{->}(4.045,2.939)(4.568,2.034)
\psline{->}(4.568,2.034)(1.147,1.638)
\psline{->}(1.147,1.638)(4.045,2.939)
\rput(0,.07){\psline{->}(-0.5227,4.973)(0.5226,4.973)}
\rput(0,-.07){\psline{<-}(-0.5227,4.973)(0.5226,4.973)}
\rput(0,.07){\psline{<-}(-0.1743,1.992)(-0.8452,1.813)}
\rput(0,-.07){\psline{->}(-0.1743,1.992)(-0.8452,1.813)}
}

\rput{-120}(0,0){\psset{linestyle=dotted}
\psline[linearc=.5]{->}(0.5176,1.932)(0.4,3)(-1.4,2.5)(-1.414,1.414 )
\psline{->}(3.346,3.716)(0.5176,1.932)
\psline[linearc=.5]{->}(-2.500,4.330)(3.346,3.716)
\psline{->}(-3.346,3.716)(-2.500,4.330)
\psline{->}(-1.414,1.414)(-3.346,3.716)
\psline{->}(-1.545,4.755)(1.545,4.755)
\psline{->}(1.545,4.755)(2.500,4.330)
\psline{->}(2.500,4.330)(-1.545,4.755)
\psline{->}(4.045,2.939)(4.568,2.034)
\psline{->}(4.568,2.034)(1.147,1.638)
\psline{->}(1.147,1.638)(4.045,2.939)
\rput(0,.07){\psline{->}(-0.5227,4.973)(0.5226,4.973)}
\rput(0,-.07){\psline{<-}(-0.5227,4.973)(0.5226,4.973)}
\rput(0,.07){\psline{<-}(-0.1743,1.992)(-0.8452,1.813)}
\rput(0,-.07){\psline{->}(-0.1743,1.992)(-0.8452,1.813)}
}
\end{pspicture}  


\caption{The annular noncrossing permutation $\pi$ in the proof of
  Theorem~\ref{thm:rot_inv}. Here, $n=30$, $m=18$, and $\pi$ is invariant under
  an annular rotation of order $d=3$. Each orbit of the annular rotation
  consists of one cycle with solid arrows, one cycle of dashed arrows, and one
  cycle of dotted arrows.}
\label{fig:pi}
\end{figure}


Suppose $(\gamma,\pi)\in \A$. As a running example we will consider
$(\gamma,\pi)$, where $\pi$ is the annular noncrossing permutation in
Figure~\ref{fig:pi} and $\gamma=(27,28,4,37,40)$.

Let $\gamma=(a_1,\dots,a_u,b_1,\dots,b_v)$ with $a_1,\dots,a_u\in [n]$ and
$b_1,\dots,b_v\in \{n+1,\dots,n+m\}$.  We define $a=a_1$ and $b=b_v$.  Let
$A_1,A_2,\dots,A_{\wn}$ be the $\wn$ consecutive numbers on the exterior circle
in clockwise order starting with $A_1=a$.  Let $B_1,B_2,\dots,B_{\wm}$ be the
$\wm$ consecutive numbers on the interior circle in counter-clockwise order
ending with $B_{\wm}=b$.  In our example, we have $a=27$, $b=40$, and
\begin{align*}
A_1,A_2,\dots,A_{\wn} &= 27,28,29,30,1,2,3,4,5,6,\\  
B_1,B_2,\dots,B_{\wm} &= 35,36,37,38,39,40.
\end{align*}

By symmetry, $\pi$ is determined by the cycles whose
elements are contained in the sequence
\begin{equation}
  \label{eq:1}
A_1,A_2,\dots,A_{\wn}, B_1,B_2,\dots,B_{\wm}.
 \end{equation}

 From now on we consider only those cycles.  For each exterior or interior cycle
 of size $t$, we place a right parenthesis $)_t$ labeled by $t$ after the
 rightmost integer in the sequence \eqref{eq:1} which is an element of the
 cycle.  We define $R^E$ (respectively~$R^I$) to be the set of integers $i$ for
 which $A_i$ (respectively~ $B_i$) has a right parenthesis. In our example, we
 have
\begin{align*}
A_1&,&A_2&,&A_3&,&A_4&,&A_5)_2&,&A_6&,&A_7)_3&,&A_8&,&A_9&,&A_{10}&,&
B_1)_1&,&B_2&,&B_3&,&B_4&,&B_5)_2&,&B_6\\
27&,&28&,&29&,&30&,&1)_2&,&2&,&3)_3&,&4&,&5&,&6&,&
35)_1&,&36&,&37&,&38&,&39)_2&,&40.
\end{align*}
Hence, $R^E=\{5,7\}$ and $R^I=\{1,5\}$.

Then we have $|R^E|=\widehat r$
 and $|R^I|=\widehat s$. Let $i_1<i_2<\dots<i_{\widehat r}$ be the elements of
 $R^E$.  We define $V^E$ to be the sequence $(\ell_1,\ell_2,\dots,\ell_{\widehat
   r})$ where $\ell_j$ is the label of the right parenthesis after $A_{i_j}$.
 The sequence $V^I$ is defined similarly. In our example, 
$V^E=(2,3)$ and $V^I=(1,2)$. 

Now remove the integers contained in an exterior or an interior cycle from the
sequence \eqref{eq:1}.  For each connected cycle, we place a left
(respectively~right) parenthesis before (respectively~after) the leftmost
(respectively~rightmost) integer in the remaining sequence which is an element
of the cycle. In our example, we have
\[
(27, 28, 4, (5,6, 36),37,40).
\]
Then the $c$ left parentheses divide the first part of the remaining sequence
consisting of integers at most $n$ into $c$ subsequences.  Let $V^{CE}$ be the
sequence of sizes of the $c$ subsequences.  Similarly, the $c$ right parentheses
divide the second part of the remaining sequence consisting of integers greater
than $n$ into $c$ subsequences. We define $V^{CI}$ to be the sequence of sizes
of the $c$ subsequences. In our example, we have
$V^{CE}=(3,2)$ and $V^{CI}=(1,2)$.

 We have just constructed the map
$(\gamma,\pi)\mapsto(a,b,R^E,R^I,V^E,V^I,V^{CE},V^{CI})$.  Using the ideas of
\cite[Proposition~4.2]{GNO} and \cite[Proposition~4.1]{Kim} , one can show that
this gives a bijection from $\A$ to $\B$.

Thus the number of $\pi\in \anc(n,m;c,r,s,R,S;\alpha,\beta,\lambda,\mu)$
invariant under an annular rotation of order $d$ is $|\A|/c =|\B|/c$, which is
easily seen to be equal to the number in the theorem.
\end{proof}

The following evaluations of $q$-binomial coefficients at a root of unity are
well known. See for instance \cite[Exercise~96 in Chapter 1]{EC1}.

\begin{lem} \label{lem:eval}
  Suppose $\omega$ is a primitive $d$th root of unity and $n$ is divisible by
  $d$. Then we have
  \begin{align*}
[n]_{q=\omega} &= n/d,\\
\Qbinom{n}{k}{q=\omega} &= \left\{
  \begin{array}{ll}
    \binom{n/d}{k/d} & \mbox{if $k$ is divisible
      by $d$,}\\
    0 & \mbox{otherwise,}
  \end{array}\right.\\
\Qbinom{n-1}{k}{q=\omega} &= \left\{
  \begin{array}{ll}
    \binom{n/d-1}{k/d} & \mbox{if $k$ is divisible
      by $d$,}\\
    0 & \mbox{otherwise.}
  \end{array}\right.
\end{align*}
\end{lem}

Now we are ready to prove Theorem~\ref{thm:CSP}. 

\begin{proof}[Proof of Theorem~\ref{thm:CSP}]
  We will only show that \eqref{eq:kre} exhibits the cyclic sieving phenomenon.
  Then \eqref{eq:nara1}, \eqref{eq:nara2}, \eqref{eq:nara3}, and \eqref{eq:cat}
  follow from Theorem~\ref{thm:kreweras sum} and the fact that if $q$ is equal
  to $\omega$ a primitive $d$th root of unity for a common divisor $d$ of $n$
  and $m$, then
\[
\Kre(n,m;c,r,s,R,S;\alpha,\beta,\lambda,\mu)=
\frac{[(n-R)(m-S)]_q}{[c]_q} \qbinom{n}{r}\qbinom{m}{s}
\qbinom{r}{\alpha} \qbinom{s}{\beta} \qbinom{c}{\lambda} \qbinom{c}{\mu},
\]
\[
\Nara_1(n,m;c,r,s,R,S) =
c \qbinom{n}{r}\qbinom{m}{s}
\qbinom{R-1}{r-1} \qbinom{S-1}{s-1} \qbinom{n-R}{c} \qbinom{m-S}{c},
\]
\[
\Nara_2(n,m;c,r,s)=c\qbinom{n}{r}\qbinom{m}{s} \qbinom{n}{r+c} \qbinom{m}{s+c},
\]
\[
\Nara_3(n,m;c)=c \qbinom{2n}{n-c} \qbinom{2m}{m-c},
\]
\[
\Cat(n,m)=\frac{[2nm]_q}{[m+n]_q} \qbinom{2n-1}{n} \qbinom{2m-1}{m}.
\]

  Suppose $(c_1,c_2)$ is an $(n,m)$-annular rotation of order $d$. Then $d$
  divides both $n$ and $m$.  By Theorem~\ref{thm:rot_inv} it is sufficient to
  show that for $\omega$ a primitive $d$th root of unity, we have
  \begin{equation}
    \label{eq:9}
X(\omega) =     d\cdot \frac{(\widehat{n}-\widehat{R})(\widehat{m}-\widehat{S})}{\widehat{c}}
\binom{\widehat{n}}{\widehat{r}}\binom{\widehat{m}}{\widehat{s}}
\binom{\widehat{r}}{\widehat{\alpha}} \binom{\widehat{s}}{\widehat{\beta}}
\binom{\widehat{c}}{\widehat{\lambda}} \binom{\widehat{c}}{\widehat{\mu}},
  \end{equation}
  if all of $n,m,c,r,s,R,S,\alpha,\beta,\lambda,\mu$ are divisible by $d$, and
  $X(\omega)=0$ otherwise. By Lem\-ma~\ref{lem:eval} we get~\eqref{eq:9} when
  all of $n,m,c,r,s,R,S,\alpha,\beta,\lambda,\mu$ are divisible by $d$.  

  It remains to show that if at least one of
  $n,m,c,r,s,R,S,\alpha,\beta,\lambda,\mu$ is not divisible by $d$, then
  $X(\omega)=0$.  Since $d$ divides both $n$ and $m$, we have the following cases.

  \textsc{Case 1}: $r$ or $s$ is not divisible by $d$. By \eqref{eq:11}, $X(q)$
  is a polynomial divisible by $\qbinom{n}{r}\qbinom{m}{s}$. Thus, by
  Lemma~\ref{lem:eval}, we get $X(\omega)=0$. 

  \textsc{Case 2}: Both $r$ and $s$ are divisible by $d$, but $\alpha$ or
  $\beta$ is not. Suppose $\alpha=(1^{a_1},2^{a_2},\dots)$ is not divisible by
  $d$. Suppose moreover that $a_j$ is not divisible by $d$. Again by
  \eqref{eq:11}, $X(q)$ is divisible by 
\[
\qbinom{r}{\alpha} = \qbinom{r}{a_j}\qbinom{r-a_j}{a_1,\dots,a_{j-1},a_{j+1},\dots}.
\]
Thus, by Lemma~\ref{lem:eval}, we get $X(\omega)=0$. If $\beta$ is not divisible by
$d$, by the same arguments, we get $X(\omega)=0$. 

\textsc{Case 3}: All of $r,s,\alpha,\beta$ are divisible by $d$, but $c$ is
not. Note that since $\alpha$ and $\beta$ are divisible by $d$, so are $R$ and
$S$. By \eqref{eq:11}, we can write
\[
X(q)=\frac{1-q^{m-S}}{1-q^c} Y(q)
\]
for a polynomial $Y(q)$. Since $m-S$ is divisible by $d$, but $c$ is not,
$\frac{1-\omega^{m-S}}{1-\omega^c}=0$ and we get $X(\omega)=0$.

\textsc{Case 4}: All of $r,s,\alpha,\beta,R,S,c$ are divisible by $d$, but
$\lambda$ or $\mu$ is not. Suppose $\lambda$ is not divisible by $d$. By
\eqref{eq:11}, $X(q)$ is divisible by $\qbinom{c}{\lambda}$. By the same
argument as in \textsc{Case 2} we obtain that $X(\omega)=0$. If $\mu$ is not
divisible by $d$, we can do the same thing using the expression 
\[
X(q) = 
\frac{[(n-R)(m-S)]_q}{[n-R]_q} \qbinom{n}{r}\qbinom{m}{s}
\qbinom{r}{\alpha} \qbinom{s}{\beta} \qbinom{c}{\mu}
\frac{[n-R]_q}{[c]_q}\qbinom{c}{\lambda} .
\]

Thus in all cases we have $X(\omega)=0$, which finishes the proof. 
\end{proof}


\section{Annular noncrossing matchings} 
\label{sec:annul-noncr-match}

An \emph{$(n,m)$-annular noncrossing matching} is a complete matching on $[n+m]$
which can be drawn in an $(n,m)$-annulus without crossing.  By considering each
matching pair $(i,j)$ as a cycle of size $2$, one can identify an annular
noncrossing matching with an annular noncrossing permutation consisting of cycles
of size $2$ only.

\begin{thm}\label{thm:ANM}
  Suppose $n\equiv m\equiv c \mod 2$.  The number of $(n,m)$-annular noncrossing
  matchings with exactly $c$ connected matching pairs is
\[
c \binom{n}{\frac{n-c}{2}} \binom{m}{\frac{m-c}{2}}.
\]
\end{thm}
\begin{proof}
  Such an annular noncrossing matching can be considered as an annular
  noncrossing permutation with $\alpha=(2^R)\in \Par(2R,R)$,
  $\beta=(2^S)\in \Par(2S,S)$, $\lambda=\mu=(1^c)\in \Par(c,c)$, and
  $n-2R=m-2S=c$.  Thus, we obtain the formula immediately from \eqref{eq:anc}.
\end{proof}

We can also obtain a closed formula for the total number of connected annular
noncrossing matchings.

\begin{thm}
  For $n\equiv m\mod 2$, the number of connected $(n,m)$-annular noncrossing
  matchings is
\[
\frac{2\ceil{\frac n2}\ceil{\frac m2}}{n+m}
\binom{n}{\ceil{\frac n2}} \binom{m}{\ceil{\frac m2}}.
\]
\end{thm}
\begin{proof}
  We will prove the equivalent statement: for $k\in \{0,1\}$, the number
  of connected $(2n+k,2m+k)$-annular noncrossing matchings is
\[
\frac{(n+k)(m+k)}{n+m+k}
\binom{2n+k}{n+k} \binom{2m+k}{m+k}.
\]
By Theorem~\ref{thm:ANM}, the number is equal to 
\[
\sum_{c\ge0} (2c+k) \binom{2n+k}{n-c}\binom{2m+k}{m-c}. 
\]
Then we are done by Lemma~\ref{lem:sum1} for $q=1$.
\end{proof}


\section*{Acknowledgement}
The author would like to thank Vic Reiner for providing his paper with Sommers
\cite{ReinerSommers}, suggesting the problem of finding a bicyclic sieving
phenomenon on annular noncrossing permutations, and for fruitful comments. He
also thanks Dennis Stanton for helpful discussion and Christian Krattenthaler
for his careful reading of the first version of this paper and helpful comments.

\begin{thebibliography}{10}

\bibitem{Andrews}
G.~E. Andrews.
\newblock {\em The theory of partitions}.
\newblock Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1976.
\newblock Encyclopedia of Mathematics and its Applications, Vol. 2.

\bibitem{Andrews2004}
G.~E. Andrews.
\newblock {\em The {F}riedman-{J}oichi-{S}tanton monotonicity conjecture at
  primes}. volume~64 of {\em DIMACS Ser. Discrete Math. Theoret. Comput. Sci.}
\newblock Amer. Math. Soc., Providence, RI, 2004.

\bibitem{BRS}
H.~Barcelo, V.~Reiner, and D.~Stanton.
\newblock Bimahonian distributions.
\newblock {\em J. Lond. Math. Soc. (2)}, 77(3):627--646, 2008.

\bibitem{Bessis2011}
D.~Bessis and V.~Reiner.
\newblock Cyclic sieving of noncrossing partitions for complex reflection
  groups.
\newblock {\em Ann. Comb.}, 15(2):197--222, 2011.

\bibitem{GR}
G.~Gasper and M.~Rahman.
\newblock {\em Basic hypergeometric series}. volume~96 of {\em Encyclopedia of
  Mathematics and its Applications}.
\newblock Cambridge University Press, Cambridge, second edition, 2004.
\newblock With a foreword by Richard Askey.

\bibitem{Goulden1997}
I.~P. Goulden and D.~M. Jackson.
\newblock Transitive factorizations into transpositions and holomorphic
  mappings of the sphere.
\newblock {\em Proc. Amer. Math. Soc.}, 125:51--60, 1997.

\bibitem{GNO}
I.~P. Goulden, A.~Nica, and I.~Oancea.
\newblock Enumerative properties of {$NC^{(B)}(p,q)$}.
\newblock {\em Ann. Comb.}, 15(2):277--303, 2011.

\bibitem{Kim}
J.~S. Kim.
\newblock Chain enumeration of {$k$}-divisible noncrossing partitions of
  classical types.
\newblock {\em J. Combin. Theory Ser. A}, 118(3):879--898, 2011.

\bibitem{KSS_ANP}
J.~S. Kim, S.~Seo, and H.~Shin.
\newblock Annular noncrossing permutations and minimal transitive
  factorizations.
\newblock \url{http://arxiv.org/abs/1201.5703}.

\bibitem{King}
C.~King.
\newblock Two-dimensional {P}otts model and annular partitions.
\newblock {\em J. Statist. Phys.}, 96(5-6):1071--1089, 1999.

\bibitem{Kreweras}
G.~Kreweras.
\newblock Sur les partitions non crois{\'e}es d'un cycle.
\newblock {\em Discrete Math.}, 1:333--350, 1972.

\bibitem{Mingo2004}
J.~A. Mingo and A.~Nica.
\newblock Annular noncrossing permutations and partitions, and second-order
  asymptotics for random matrices.
\newblock {\em Int. Math. Res. Not.}, (28):1413--1460, 2004.

\bibitem{Nica2009}
A.~Nica and I.~Oancea.
\newblock Posets of annular non-crossing partitions of types {$B$} and {$D$}.
\newblock {\em Discrete Math.}, 309(6):1443--1466, 2009.

\bibitem{ReinerSommers}
V.~Reiner and E.~Sommers.
\newblock $q$-analogues of {W}eyl group {N}arayana and {K}reweras numbers.
\newblock preprint.

\bibitem{CSP}
V.~Reiner, D.~Stanton, and D.~White.
\newblock The cyclic sieving phenomenon.
\newblock {\em J. Combin. Theory Ser. A}, 108(1):17--50, 2004.

\bibitem{SaganCSP}
B.~E. Sagan.
\newblock {\em The cyclic sieving phenomenon: a survey}. volume 392 of {\em
  London Math. Soc. Lecture Note Ser.}
\newblock Cambridge Univ. Press, Cambridge, 2011.

\bibitem{Stanley1980}
R.~P. Stanley.
\newblock {W}eyl groups, the hard {L}efschetz theorem, and the {S}perner
  property.
\newblock {\em SIAM Journal on Algebraic Discrete Methods}, 1(2):168--184,
  1980.

\bibitem{EC1}
R.~P. Stanley.
\newblock {\em Enumerative Combinatorics. {V}ol. 1, second ed.}
\newblock Cambridge University Press, New York/Cambridge, 2011.

\end{thebibliography}

\end{document}
