Séminaire Lotharingien de Combinatoire 69 (2013), Article B69b

CYCLIC SIEVING PHENOMENA ON ANNULAR NONCROSSING PERMUTATIONS

JANG SOO KIM

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.

1. Introduction

Let π be a permutation of [n] = {1, 2, …, n}. One can represent π inside a disk as shown in Figure 1. If the arrows of the diagram of π are noncrossing and if every cycle of π is oriented clockwise, then π is called a 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.

1 2 3 4 5 6 7 8 9 10

Figure 1. A representation of the permutation (1, 3, 4, 5)(2)(6, 10)(7, 8, 9)

inside a disk.

It is well known that the number of noncrossing permutations of [n] is the Catalan number

Cat(n) = \frac{1}{n + 1}\binom{2n}{n},

and the number of noncrossing permutations of [n] with k cycles is the Narayana number

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} , [n]_{q}! = [1]_{q}[2]_{q} ⋯ [n]_{q},

\left[{n_{1} + ⋯ + n_{k} \atop n_{1}, …, n_{k}}\right]_{q} = \frac{[n_{1} + ⋯ + n_{k}]_{q}!}{[n_{1}]_{q}! ⋯ [n_{k}]_{q}!}, \left[{n \atop k}\right]_{q} = \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 λ has m_{i} parts of size i for i = 1, 2, …, ℓ with largest part ℓ, then we also write λ = (1^{m_{1}}, 2^{m_{2}}, …, ℓ^{m_{ℓ}}). If λ = (1^{m_{1}}, 2^{m_{2}}, …, ℓ^{m_{ℓ}}) has k parts, i.e., m_{1} + m_{2} + ⋯ + m_{ℓ} = k, we define

\binom{k}{λ} = \binom{k}{m_{1}, m_{2}, …, m_{ℓ}}, \left[{k \atop λ}\right]_{q} = \left[{k \atop m_{1}, m_{2}, …, m_{ℓ}}\right]_{q},

The cycle type of a permutation π is the partition λ = (1^{m_{1}}, 2^{m_{2}}, …), where m_{i} is the number of cycles with i elements. Kreweras [11] showed that the number of noncrossing permutations (noncrossing partitions in the original paper) of [n] with cycle type λ = (1^{m_{1}}, 2^{m_{2}}, …) ∈ Par(n, k) is equal to the Kreweras number

Kre(λ) := \frac{1}{k}\binom{n}{k − 1}\binom{k}{λ}.

Bessis and Reiner [4, Theorem 6.2] showed that if X is the set of noncrossing permutations (noncrossing partitions in the original paper) of [n] with type λ = (1^{m_{1}}, 2^{m_{2}}, …) ∈ Par(n, k),

X(q) = \frac{1}{[k]_{q}} \left[{n \atop k − 1}\right]_{q}\left[{k \atop λ}\right]_{q},

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 [14] defined the q-Kreweras number for λ = (1^{m_{1}}, 2^{m_{2}}, …) ∈ Par(n, k) by

Kre_{q}(λ) = \frac{q^{(n+1)(n−k)−τ(λ)}}{[k]_{q}} \left[{n \atop k − 1}\right]_{q}\left[{k \atop λ}\right]_{q},

where τ(λ) = ∑_{i≥1} λ′_{i}λ′_{i+1}, and the q-Narayana number by

Nara_{q}(n, k) = \frac{q^{(n−k)(n+1−k)}}{[n]_{q}} \left[{n \atop k − 1}\right]_{q}\left[{n \atop k}\right]_{q},

and showed that

∑_{λ∈Par(n,k)} Kre_{q}(λ) = Nara_{q}(n, k)

and

∑_{k=0}^{n} Nara_{q}(n, k) = Cat_{q}(n),

where Cat_{q}(n) is the q-Catalan number defined by

Cat_{q}(n) = \frac{1}{[n + 1]_{q}} \left[{2n \atop n}\right]_{q}.

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 2.1 for more details about their difference.

Annular noncrossing partitions were introduced by King [10] in the study of a statistical physics model. Annular noncrossing permutations were considered by Mingo and Nica [12] and studied further in [7, 13]. Recently Kim, Seo, and Shin [9] used annular noncrossing permutations to give a combinatorial proof of Goulden and Jackson’s formula [6] for the number of minimal transitive factorizations of a product of two cycles.

This paper is organized as follows. In Section 2 we define annular noncrossing permutations and state the main result Theorem 2.2 which gives cyclic sieving phenomena on annular noncrossing permutations. In Section 3 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 4 these numbers multiplied by 2 are shown to be polynomials in q with nonnegative integer coefficients. In Section 5 we prove Theorem 2.2. In Section 6 we enumerate annular noncrossing matchings.

2. Cyclic sieving phenomena

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

Let (a_{1}, …, 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, … k, where a_{k+1} = a_{1}. An interior cycle (respectively exterior cycle) is a cycle all of whose elements are on the interior (respectively exterior) circle. A 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} < ⋯ < e_{u}} = {a_{1}, …, a_{k}}∩[n] and {i_{1} < i_{2} < ⋯ < i_{v}} = {a_{1}, …, a_{k}}∩

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Figure 2. A representation of the annular noncrossing permutation (1, 2, 3, 6, 15, 10, 11)(4, 5)(7, 8, 9, 13, 14)(12).

{n + 1, n + 2, …, n + m}. Then we say that the cycle (a_{1}, …, a_{k}) is oriented clockwise if we can express

(a_{1}, …, a_{k}) = (e_{r}, e_{r+1}, …, e_{u}, e_{1}, e_{2}, …, e_{r−1}, i_{s}, i_{s+1}, …, i_{v}, i_{1}, i_{2}, …, i_{s−1})

for some integers 1 ≤ r ≤ u and 1 ≤ s ≤ v. In this case we say that the cycle (a_{1}, …, a_{k}) is of size k, of exterior size u and of interior size v.

A permutation of [n + m] is called an (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 2.

Remark 2.1. 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 [12, Proposition 4.4], 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.

If an (n, m)-annular noncrossing permutation has a connected cycle, it is called 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 π ∈ ANC(n, m), the exterior cycle type (respectively interior cycle type) of π is the partition (1^{m_{1}}, 2^{m_{2}}, …) where m_{i} is the number of exterior cycles (respectively interior cycles) of size i. The connected exterior cycle type (respectively connected interior cycle type) of π is the partition (1^{m_{1}}, 2^{m_{2}}, …) 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 ≥ 0 and α ∈ Par(R, r), β ∈ Par(S, s), λ ∈ Par(n − R, c), and μ ∈ Par(m − S, c), we define the following:

• ANC(n, m; c) is the set of π ∈ ANC(n, m) with c connected cycles.

• ANC(n, m; c, r, s) is the set of π ∈ ANC(n, m; c) with r exterior cycles and s interior cycles.

• ANC(n, m; c, r, s, R, S) is the set of π ∈ 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.

• ANC(n, m; c, r, s, R, S; α, β, λ, μ) is the set of π ∈ ANC(n, m) with exterior cycle type α ∈ Par(R, r), interior cycle type β ∈ Par(S, s), connected exterior cycle type λ ∈ Par(n − R, c), and connected interior cycle type μ ∈ Par(m − S, c).

Definition 2.1. 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 cyclic sieving phenomenon (CSP) if X(ω(c)) = |{x ∈ X : c(x) = x}| for all c ∈ C. Here, ω : C → ℂ^{×} is a group homomorphism of C into the multiplicative group ℂ^{×} of nonzero complex numbers sending a cyclic generator of C to a primitive nth root of unity.

The CSP was first introduced by Reiner, Stanton, and White [15]. Recently many instances of the CSP have been found. In [16], 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} × 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} × C_{2} gives a bicyclic action on ANC(n, m) by (c_{1}, c_{2})π = c_{1}(c_{2}(π)) = c_{2}(c_{1}(π)). One may wonder if this bicyclic action gives a “bicyclic sieving phenomenon” as in [3]. However, this is not the case because of the next proposition.

Proposition 2.1. Let (c_{1}, c_{2}) ∈ C_{1} × 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.

Proof. Let d_{1} and d_{2} be the orders of c_{1} and c_{2}, respectively. Suppose π ∈ ANC(n, m) is a fixed point, i.e., (c_{1}, c_{2})π = π. Let k_{1} = n/d_{1} and k_{2} = m/d_{2}. We can assume that c_{1} is the map sending i ∈ [n] to j ∈ [n] with j ≡ i + k_{1} mod n, and c_{2} is the map sending n + i ∈ {n + 1, …, n + m} to n + j ∈ {n + 1, …, n + m} with j ≡ i − k_{2} mod m. Note that for each i ∈ [n], c_{1}^{(t)}(i) = i implies that t is divisible by d_{1} because if t = s · d_{1} + r with 0 < r < d_{1}, then

c_{1}^{(t)}(i) ≡ i + k_{1} · t ≡ i + n · \frac{r}{d_{1}} ≢ i mod n.

Similarly for each i ∈ {n + 1, …, n + m}, c_{2}^{(t)}(i) = i implies that t is divisible by d_{2}.

Consider a connected cycle γ = (a_{1}, …, a_{u}, b_{1}, …, b_{v}) of π where a_{1}, …, a_{u} ∈ [n] and b_{1}, …, b_{v} ∈ {n + 1, …, n + m}. Note that u > 0 and v > 0. Since (c_{1}, c_{2})^{(d_{1})}(π) = π and (c_{1}, c_{2})^{(d_{1})}(γ) = (a_{1}, …, a_{u}, c_{2}^{(d_{1})}(b_{1}), …, c_{2}^{(d_{1})}(b_{v})), we have (c_{1}, c_{2})^{(d_{1})}(γ) = γ. 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}. □

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 (n, m)-annular rotation, or simply an 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 5.

Theorem 2.2. Let n, m, c, r, s, R, S be nonnegative integers and α ∈ Par(R, r), β ∈ Par(S, s), λ ∈ Par(n − R, c), and μ ∈ Par(m − S, c). Let C be the cyclic group of (n, m)- annular rotations. Then the following exhibit the cyclic sieving phenomenon: (2.1)

(ANC(n, m; c, r, s, R, S; α, β, λ, μ), \frac{[(n − R)(m − S)]_{q}}{[c]_{q}} \left[{n \atop r}\right]_{q}\left[{m \atop s}\right]_{q}\left[{r \atop α}\right]_{q}\left[{s \atop β}\right]_{q}\left[{c \atop λ}\right]_{q}\left[{c \atop μ}\right]_{q}, C) ,

(2.2) (ANC(n, m; c, r, s, R, S), c\left[{n \atop r}\right]_{q}\left[{m \atop s}\right]_{q}\left[{R − 1 \atop r − 1}\right]_{q}\left[{S − 1 \atop s − 1}\right]_{q}\left[{n − R \atop c}\right]_{q}\left[{m − S \atop c}\right]_{q}, C) ,

(2.3)  (ANC(n, m; c, r, s), c\left[{n \atop r}\right]_{q}\left[{m \atop s}\right]_{q}\left[{n \atop r + c}\right]_{q}\left[{m \atop s + c}\right]_{q}, C) ,

(2.4)  (ANC(n, m; c), c\left[{2n \atop n − c}\right]_{q}\left[{2m \atop m − c}\right]_{q}, C) ,

(2.5)  (ANC(n, m), \frac{[2nm]_{q}}{[m + n]_{q}} \left[{2n − 1 \atop n}\right]_{q}\left[{2m − 1 \atop m}\right]_{q}, C) .

Considering the annular rotation of order 1 in Theorem 2.2, i.e., the identity action, we obtain the following enumeration results.

Corollary 2.3. We have

# ANC(n, m; c, r, s, R, S; α, β, λ, μ) = \frac{(n − R)(m − S)}{c}\binom{n}{r}\binom{m}{s}\binom{r}{α}\binom{s}{β}\binom{c}{λ}\binom{c}{μ}, (2.6)
(2.7)  # 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},
(2.8)  # ANC(n, m; c, r, s) = c\binom{n}{r}\binom{m}{s}\binom{n}{r + c}\binom{m}{s + c},
(2.9)  # ANC(n, m; c) = c\binom{2n}{n − c}\binom{2m}{m − c},
(2.10)  # ANC(n, m) = \frac{2nm}{m + n}\binom{2n − 1}{n}\binom{2m − 1}{m}.

If an annular noncrossing permutation is invariant under an annular rotation of order 2, it is called an 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

ANC_{B}(n, m; c) = ANC_{B}(n, m) ∩ ANC(2n, 2m; 2c),
ANC_{B}(n, m; c, r, s) = ANC_{B}(n, m) ∩ ANC(2n, 2m; 2c, 2r, 2s),
ANC_{B}(n, m; c, r, s, R, S) = ANC_{B}(n, m) ∩ ANC(2n, 2m; 2c, 2r, 2s, 2R, 2S),
ANC_{B}(n, m; c, r, s, R, S; α, β, λ, μ) = ANC_{B}(n, m)
∩ ANC(2n, 2m; 2c, 2r, 2s, 2R, 2S; 2α, 2β, 2λ, 2μ),

where 2λ = (2λ_{1}, 2λ_{2}, …).

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 2.2 we obtain the enumeration results below.

Corollary 2.4. We have

# ANC_{B}(n, m; c, r, s, R, S; α, β, λ, μ) = \frac{2(n − R)(m − S)}{c}\binom{n}{r}\binom{m}{s}\binom{r}{α}\binom{s}{β}\binom{c}{λ}\binom{c}{μ}, (2.11)
(2.12) # 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},
(2.13)  # ANC_{B}(n, m; c, r, s) = 2c\binom{n}{r}\binom{m}{s}\binom{n}{r + c}\binom{m}{s + c},
(2.14)  # ANC_{B}(n, m; c) = 2c\binom{2n}{n − c}\binom{2m}{m − c},
(2.15)  # ANC_{B}(n, m) = \frac{nm}{m + n}\binom{2n}{n}\binom{2m}{m}.

We note that (2.10) was first proved by Mingo and Nica [12, Corollary 6.7] and (2.13), (2.14), and (2.15) were first proved by Goulden, Nica and Oancea [7, Equations (4.6), (4.7), (4.9)].

3. Annular q-Kreweras numbers

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 2.2.

For brevity we will use the following abbreviations throughout this section:

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) − τ(α) − τ(β) − τ(λ) − τ(μ).

Definition 3.1. The annular q-Kreweras number

Kre^{ann} = Kre^{ann}(n, m; c, r, s, R, S; α, β, λ, μ)

is defined by

Kre^{ann} = 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}} \left[{n \atop r}\right]_{q}\left[{m \atop s}\right]_{q}\left[{r \atop α}\right]_{q}\left[{s \atop β}\right]_{q}\left[{c \atop λ}\right]_{q}\left[{c \atop μ}\right]_{q}.

The annular q-Narayana number Nara_{1}^{ann} = Nara_{1}^{ann}(n, m; c, r, s, R, S) of type 1 is defined by

Nara_{1}^{ann} = q^{X}q^{Y} q^{Z} \frac{[nm]_{q}}{[n]_{q}[m]_{q}} \frac{[2c]_{q}}{2} \left[{n \atop r}\right]_{q}\left[{m \atop s}\right]_{q}\left[{R − 1 \atop r − 1}\right]_{q}\left[{S − 1 \atop s − 1}\right]_{q}\left[{n − R \atop c}\right]_{q}\left[{m − S \atop c}\right]_{q}.

The annular q-Narayana number Nara_{2}^{ann} = Nara_{2}^{ann}(n, m; c, r, s) of type 2 is defined by

Nara_{2}^{ann} = q^{X}q^{Y} \frac{[nm]_{q}}{[n]_{q}[m]_{q}} \frac{[2c]_{q}}{2} \left[{n \atop r}\right]_{q}\left[{m \atop s}\right]_{q}\left[{n \atop r + c}\right]_{q}\left[{m \atop s + c}\right]_{q}.

The annular q-Narayana number Nara_{3}^{ann} = Nara_{3}^{ann}(n, m; c) of type 3 is defined by

Nara_{3}^{ann} = q^{X} \frac{[nm]_{q}}{[n]_{q}[m]_{q}} \frac{[2c]_{q}}{2} \left[{2n \atop n − c}\right]_{q}\left[{2m \atop m − c}\right]_{q}.

The annular q-Catalan number Cat^{ann} = Cat^{ann}(n, m) is defined by

Cat^{ann} = \frac{[nm]_{q}}{2[m + n]_{q}} \left[{2n \atop n}\right]_{q}\left[{2m \atop m}\right]_{q}.

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 [14]. We include their elegant proof as well.

Lemma 3.1. [14] Let τ(λ) = ∑_{i≥1} λ′_{i}λ′_{i+1}, where λ′ is the transpose of λ. Then

∑_{λ∈Par(n,k)} q^{k(n−k)−τ(λ)}\left[{k \atop λ}\right]_{q} = \left[{n − 1 \atop k − 1}\right]_{q}.

\{  n − k \}k = μ_{1} \{ μ_{4} \{ μ_{3} \{  μ_{2} P_{4} P_{3} P_{2} P_{1} Q_{4} Q_{3} Q_{2} Q_{1} = P_{0} q^{(k−μ_{3})μ_{4}} q^{(k−μ_{2})μ_{3}} \left[{μ_{1} \atop μ_{2}}\right]_{q} \left[{μ_{2} \atop μ_{3}}\right]_{q} \left[{μ_{3} \atop μ_{4}}\right]_{q}

Figure 3. We decompose ν and get μ.

Proof. Let λ = (1^{m_{1}}, 2^{m_{2}}, …). Then m_{1} + 2m_{2} + ⋯ = n and m_{1} + m_{2} + ⋯ = k. Since λ′_{i} = m_{i} + m_{i+1} + ⋯, we have

q^{k(n−k)−τ(λ)}\left[{k \atop λ}\right]_{q} = q^{(k−λ′_{1})λ′_{2}} \left[{λ′_{1} \atop λ′_{2}}\right]_{q}q^{(k−λ′_{2})λ′_{3}} \left[{λ′_{2} \atop λ′_{3}}\right]_{q} · · · .

Thus we can rewrite the identity as follows.

(3.1)  \left[{n − 1 \atop k − 1}\right]_{q} = ∑_{μ∈Par(n),μ_{1}=k} q^{(k−μ_{1})μ_{2}} \left[{μ_{1} \atop μ_{2}}\right]_{q}q^{(k−μ_{2})μ_{3}} \left[{μ_{2} \atop μ_{3}}\right]_{q} · · · .

The left hand side of (3.1) is the sum of q^{|ν|} for all partitions ν contained in a k×(n−k) rectangle where the kth part of ν is 0. For such a partition ν we define points Q_{1}, P_{1}, Q_{2}, P_{2}, … 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 ν 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 ν has no cells in the kth row of the rectangle, we can always complete this sequence. Let μ be the partition whose ith part is equal to the length of the segment P_{i−1}P_{i}, where P_{0} = Q_{1}. Then μ ∈ Par(n) and μ_{1} = k. It is easy to see that the sum of q^{|ν|} for partitions ν which give μ is equal to the summand in (3.1), see Figure 3. This proves (3.1). □

Lemma 3.2. For fixed integers n, r, c, we have

∑_{R≥0} q^{r(n−c−R)}\left[{R − 1 \atop r − 1}\right]_{q}\left[{n − R \atop c}\right]_{q} = \left[{n \atop r + c}\right]_{q}.

Proof. This can be proved by a standard technique considering the largest rectangle with width r contained in partitions inside an (n − r − c) × (r + c) rectangle. This can also be proved by using the q-Chu-Vandermonde theorem [5, II.7]. □

Lemma 3.3. Let n, m, and k be nonnegative integers. Then

∑_{c≥0} q^{c(c−1+k)}[2c + k]_{q}\left[{2n + k \atop n − c}\right]_{q}\left[{2m + k \atop m − c}\right]_{q} = \frac{[n + k]_{q}[m + k]_{q}}{[n + m + k]_{q}} \left[{2n + k \atop n + k}\right]_{q}\left[{2m + k \atop m + k}\right]_{q}.

Proof. It is straightforward to check that

(3.2) 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}.

Let σ(c) = c(c − 1 + k). Then by (3.2) the left hand side is equal to

\frac{1}{[n + m + k]_{q}}

× ∑_{c≥0} (q^{σ(c)}[n + c + k]_{q}[m + c + k]_{q} − q^{σ(c+1)}[n − c]_{q}[m − c]_{q})\left[{2n + k \atop n − c}\right]_{q}\left[{2m + k \atop m − c}\right]_{q}

= \frac{[2n + k]_{q}[2m + k]_{q}}{[n + m + k]_{q}}

× ∑_{c≥0} (q^{σ(c)}\left[{2n + k − 1 \atop n − c}\right]_{q}\left[{2m + k − 1 \atop m − c}\right]_{q} − q^{σ(c+1)}\left[{2n + k − 1 \atop n − c − 1}\right]_{q}\left[{2m + k − 1 \atop m − c − 1}\right]_{q})

= \frac{[2n + k]_{q}[2m + k]_{q}}{[n + m + k]_{q}} \left[{2n + k − 1 \atop n}\right]_{q}\left[{2m + k − 1 \atop m}\right]_{q}

= \frac{[n + k]_{q}[m + k]_{q}}{[n + m + k]_{q}} \left[{2n + k \atop n + k}\right]_{q}\left[{2m + k \atop m + k}\right]_{q}.

We note that this can also be proved by using the very-well-poised _{6}ϕ_{5} summation formula [5, II.21] with c = aq^{n+1}. □

Theorem 3.4. We have

∑_{α∈Par(R,r) β∈Par(S,s) λ∈Par(n−R,c) μ∈Par(m−S,c)} Kre^{ann}(n, m; c, r, s, R, S; α, β, λ, μ) = Nara_{1}^{ann}(n, m; c, r, s, R, S),

∑_{R,S≥0} Nara_{1}^{ann}(n, m; c, r, s, R, S) = Nara_{2}^{ann}(n, m; c, r, s),
∑_{r,s≥0} Nara_{2}^{ann}(n, m; c, r, s) = Nara_{3}^{ann}(n, m; c),
∑_{c≥0} Nara_{3}^{ann}(n, m; c) = Cat^{ann}(n, m).

Proof. The first, second, and fourth identities follow from Lemmas 3.1, 3.2, and 3.3, respectively. The third identity follows from the q-Chu–Vandermonde identity:

∑_{i≥0} q^{i(m−k+i)}\left[{m \atop k − i}\right]_{q}\left[{n \atop i}\right]_{q} = \left[{m + n \atop k}\right]_{q}.

□

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 4.4. Unfortunately, these numbers are not polynomials with integer coefficients. For instance, Cat^{ann}(1, 1) = (1 + q)/2.

4. Polynomiality and nonnegativity

A polynomial f(x) = a_{0} + a_{1}x + ⋯ + a_{n}x^{n} is called symmetric if a_{i} = a_{n−i} for i = 0, 1, …, n, and unimodal if a_{0} ≤ a_{1} ≤ ⋯ ≤ a_{j} ≥ a_{j+1} ≥ ⋯ ≥ a_{n} for some j. We denote by ℤ[q] (respectively ℕ[q]) the set of polynomials in q with integer coefficients (respectively nonnegative integer coefficients).

We will use the following three lemmas.

Lemma 4.1. [1, Theorem 3.9] If f(x) and g(x) are symmetric, unimodal polynomials, then so is f(x)g(x).

Lemma 4.2. [15, Proposition 10.1 (iii)] If f(q) = h(q)/[k]_{q} ∈ ℤ[q], and h(q) ∈ ℕ[q] has a symmetric, unimodal coefficient sequence, then f(q) ∈ ℕ[q].

As is mentioned in [15], the above lemma is also derived implicitly in [2].

Lemma 4.3. For nonnegative integers N, n, k with N ≥ n and a partition λ ∈ Par(n, k), we have

\frac{[n]_{q}}{[k]_{q}} \left[{k \atop λ}\right]_{q} ∈ ℕ[q], \frac{[N − n]_{q}}{[N]_{q}} \left[{N \atop k}\right]_{q}\left[{k \atop λ}\right]_{q} ∈ ℕ[q].

Proof. We claim that

(4.1)  \frac{[n]_{q}}{[k]_{q}} \left[{k \atop λ}\right]_{q} = \frac{1 − q^{n}}{1 − q^{k}} \left[{k \atop λ}\right]_{q} ∈ ℤ[q].

Assuming the claim let us show the lemma. By (4.1) and the fact [N]_{q} = [N −n]_{q}+q^{N−n}[n]_{q} we also have

\frac{[N − n]_{q}}{[N]_{q}} \left[{N \atop k}\right]_{q}\left[{k \atop λ}\right]_{q} = \frac{[N]_{q} − q^{N−n}[n]_{q}}{[N]_{q}} \left[{N \atop k}\right]_{q}\left[{k \atop λ}\right]_{q}

= \left[{N \atop k}\right]_{q}\left[{k \atop λ}\right]_{q} − q^{N−n}\left[{N − 1 \atop k − 1}\right]_{q} · \frac{[n]_{q}}{[k]_{q}} \left[{k \atop λ}\right]_{q} ∈ ℤ[q].

It is known that q-multinomial coefficients \left[{m_{1}+···+m_{ℓ} \atop m_{1},...,m_{ℓ}}\right]_{q} are symmetric and unimodal. See for

instance [17]. Thus by Lemmas 4.1 and 4.2 we get \frac{[n]_{q}}{[k]_{q}} \left[{k \atop λ}\right]_{q} ∈ ℕ[q] and \frac{[N−n]_{q}}{[N]_{q}} \left[{N \atop k}\right]_{q}\left[{k \atop λ}\right]_{q} ∈ ℕ[q]. We now show (4.1). We will use the q-Pochhammer symbol

(q; q)_{r} = (1 − q)(1 − q^{2}) ⋯ (1 − q^{r}).

Note that \left[{n \atop k}\right]_{q} = \frac{(q;q)_{n}}{(q;q)_{k}(q;q)_{n−k}}.

Since

q^{k} − 1 = ∏_{j=1}^{k}(q − ω_{j}),

where ω_{1}, ω_{2}, …, ω_{k} are the kth roots of unity, in order to prove (4.1), it is sufficient to show that q − ω_{j} divides (1 − q^{n})\left[{k \atop λ}\right]_{q} for all j = 1, 2, …, k. Fix an integer j and suppose ω_{j} is a primitive rth root of unity. Then r divides k. Note that q − ω_{j} divides q^{s} − 1 if and only if r divides s. Note also that the multiplicity of q − ω_{j} as a factor of q^{s} − 1 is at most 1. Thus the multiplicity of the factor q − ω_{j} in (q; q)_{s} is equal to ⌊s/r⌋. We have two cases as follows.

Case 1: r divides n. Then q − ω_{j} divides q^{n} − 1 and we are done.

Case 2: r does not divide n. Let λ = (1^{m_{1}}, 2^{m_{2}}, …, ℓ^{m_{ℓ}}). Then we have n = ∑_{i=1}^{ℓ} i·m_{i}, k = ∑_{i=1}^{ℓ} m_{i}, and

(4.2)  \left[{k \atop λ}\right]_{q} = \frac{(q; q)_{m_{1}+m_{2}+···+m_{ℓ}}}{(q; q)_{m_{1}}(q; q)_{m_{2}} ⋯ (q; q)_{m_{ℓ}}} .

The multiplicities of the factor q −ω_{j} in the numerator and denominator of (4.2) are ⌊k/r⌋ and ⌊m_{1}/r⌋ + ⌊m_{2}/r⌋ + ⋯ + ⌊m_{ℓ}/r⌋, respectively. Since r does not divide n, at least one of m_{1}, m_{2}, …, m_{ℓ} is not a multiple of r. Thus we have

⌊\frac{m_{1}}{r} ⌋ + ⌊\frac{m_{2}}{r} ⌋ + ⋯ + ⌊\frac{m_{ℓ}}{r} ⌋ < \frac{m_{1}}{r} + \frac{m_{2}}{r} + ⋯ + \frac{m_{ℓ}}{r} = \frac{k}{r} = ⌊\frac{k}{r} ⌋ ,

which implies that q − ω_{j} divides \left[{k \atop λ}\right]_{q}. This finishes the proof of (4.1). □

Proposition 4.4. We have

2 Kre^{ann}(n, m; c, r, s, R, S; α, β, λ, μ) ∈ ℕ[q],
2 Nara_{1}^{ann}(n, m; c, r, s, R, S) ∈ ℕ[q],
2 Nara_{2}^{ann}(n, m; c, r, s) ∈ ℕ[q],
2 Nara_{3}^{ann}(n, m; c) ∈ ℕ[q],
2 Cat^{ann}(n, m) ∈ ℕ[q].

Proof. By Theorem 3.4, it is sufficient to show the first statement for the annular q-Kreweras numbers. Since 2 Kre^{ann}(n, m; c, r, s, R, S; α, β, λ, μ) is equal to

q^{X}q^{Y} q^{Z}q^{W} \frac{[2c]_{q}}{[c]_{q}} (\frac{[n − R]_{q}}{[n]_{q}} \left[{n \atop r}\right]_{q}\left[{r \atop α}\right]_{q}) (\frac{[m − S]_{q}}{[c]_{q}} \left[{c \atop μ}\right]_{q}) (\frac{[nm]_{q}}{[m]_{q}} \left[{m \atop s}\right]_{q}\left[{s \atop β}\right]_{q}\left[{c \atop λ}\right]_{q}) ,

we are done by Lemma 4.3. □

We now prove that the rational functions in Theorem 2.2 are actually polynomials in q with nonnegative integer coefficients.

Proposition 4.5. We have

\frac{[(n − R)(m − S)]_{q}}{[c]_{q}} \left[{n \atop r}\right]_{q}\left[{m \atop s}\right]_{q}\left[{r \atop α}\right]_{q}\left[{s \atop β}\right]_{q}\left[{c \atop λ}\right]_{q}\left[{c \atop μ}\right]_{q} ∈ ℕ[q],

\frac{[2nm]_{q}}{[m + n]_{q}} \left[{2n − 1 \atop n}\right]_{q}\left[{2m − 1 \atop m}\right]_{q} ∈ ℕ[q].

Proof. By Lemma 4.3, \frac{[m−S]_{q}}{[c]_{q}} \left[{c \atop μ}\right]_{q} is a polynomial. Since

(4.3)  \frac{[(n − R)(m − S)]_{q}}{[m − S]_{q}} \left[{n \atop r}\right]_{q}\left[{m \atop s}\right]_{q}\left[{r \atop α}\right]_{q}\left[{s \atop β}\right]_{q}\left[{c \atop λ}\right]_{q} \frac{[m − S]_{q}}{[c]_{q}} \left[{c \atop μ}\right]_{q},

and [ab]_{q} = [a]_{q}[b]_{q^{a}} = [b]_{q}[a]_{q^{b}}, we obtain the first statement.

For the second statement, by Lemmas 4.1 and 4.2, it is sufficient to show that

\frac{[2nm]_{q}}{[m + n]_{q}} \left[{2n − 1 \atop n}\right]_{q}\left[{2m − 1 \atop m}\right]_{q} = \frac{1 − q^{2nm}}{1 − q^{n+m}} \left[{2n − 1 \atop n}\right]_{q}\left[{2m − 1 \atop m}\right]_{q} ∈ ℤ[q].

We will use the same idea as in the proof of Lemma 4.3. Let ω_{1}, ω_{2}, …, ω_{n+m} be the (n + m)th roots of unity. We need to show that (q − ω_{j}) divides (1 − q^{2nm})\left[{2n−1 \atop n}\right]_{q}\left[{2m−1 \atop m}\right]_{q} for j = 1, 2, …, n + m. Fix j and suppose ω_{j} is a primitive pth root of unity. If p divides nm, then q − ω_{j} divides 1 − q^{2nm}. Suppose p does not divide nm. Then we can write n = A_{1}p + B_{1} and m = A_{2}p + 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} ≥ \frac{p}{2}. Since

(1 − q^{2nm})\left[{2n − 1 \atop n}\right]_{q}\left[{2m − 1 \atop m}\right]_{q} = \frac{1 − q^{2nm}}{1 − q^{2n}} (1 − q^{n})\left[{2n \atop n}\right]_{q}\left[{2m − 1 \atop m}\right]_{q},

and the multiplicity of q − ω_{j} in \left[{2n \atop n}\right]_{q} is ⌊\frac{2n}{p}⌋ − ⌊\frac{n}{p}⌋ − ⌊\frac{n}{p}⌋ = 2A_{1} + 1 − A_{1} − A_{1} = 1, we

obtain that q − ω_{j} divides (1 − q^{2nm})\left[{2n−1 \atop n}\right]_{q}\left[{2m−1 \atop m}\right]_{q}. This finishes the proof of the second statement. □

5. Proof of cyclic sieving phenomena

For a partition λ = (1^{m_{1}}, 2^{m_{2}}, …) we denote by 𝔖(λ) the set of rearrangements of the sequence

\overbrace{1, …, 1}^{m_{1}}, \overbrace{2, …, 2}^{m_{2}}, ….

In other words, each element in 𝔖(λ) is a sequence (a_{1}, a_{2}, …) where each integer i appears exactly m_{i} times. If each m_{i} is divisible by d, we define λ/d = (1^{m_{1}/d}, 2^{m_{2}/d}, …). In this case we say that λ is divisible by d.

Lemma 5.1. If there is a permutation π ∈ ANC(n, m; c, r, s, R, S; α, β, λ, μ) invariant under an annular rotation of order d, then all of n, m, c, r, s, R, S, α, β, λ, μ are divisible by d.

Proof. Since this is obvious when d = 1, we can assume that d ≥ 2. Suppose that π is invariant under an annular rotation (c_{1}, c_{2}) of order d. It suffices to show the following claim.

Claim: for every cycle γ of π, we have (c_{1}, c_{2})^{(i)}(γ) ≠ γ for all i = 1, 2, …, d − 1.

We first consider a connected cycle γ = (a_{1}, …, a_{u}, b_{1}, …, b_{v}) with a_{1}, …, a_{u} ∈ [n] and b_{1}, …, b_{v} ∈ {n + 1, …, n + m}. Suppose for contradiction that (c_{1}, c_{2})^{(i)}(γ) = γ for some 1 ≤ i ≤ d − 1. Then we get

γ = (c_{1}, c_{2})^{(i)}(γ) = ((c_{1}, c_{2})^{(i)}(a_{1}), …, (c_{1}, c_{2})^{(i)}(a_{u}), (c_{1}, c_{2})^{(i)}(b_{1}), …, (c_{1}, c_{2})^{(i)}(b_{v})).

Since the expression γ = (a_{1}, …, a_{u}, b_{1}, …, b_{v}) is unique, we have (c_{1}, c_{2})^{(i)}(a_{1}) = a_{1}, which is impossible because 1 ≤ i ≤ d−1. Thus (c_{1}, c_{2})^{(i)}(γ) are distinct for all i = 0, 1, 2 …, d−1. In the diagram of π 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 …, d − 1. These arrows then divide the annulus into d regions. By the noncrossing property, we obtain the claim. □

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

Theorem 5.2. The number of permutations π ∈ ANC(n, m; c, r, s, R, S; α, β, λ, μ) invariant under an annular rotation of order d is equal to

d · \frac{(n̂ − R̂)(m̂ − Ŝ)}{ĉ}(n̂ ; r̂)(m̂ ; ŝ)(r̂ ; α̂)(ŝ ; β̂)(ĉ ; λ̂)(ĉ ; μ̂),

if all of n, m, c, r, s, R, S, α, β, λ, μ are divisible by d, and 0 otherwise. Here Ẑ means Z/d.

Sketch of Proof. Since the proof is similar to those in [7, Proposition 4.2] and in [8, Proposition 4.1], we will only give a sketch with an example.

By Lemma 5.1 we can assume that all of n, m, c, r, s, R, S, α, β, λ, μ are divisible by d.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

Figure 4. The annular noncrossing permutation π in the proof of Theorem 5.2. Here, n = 30, m = 18, and π 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.

Let (c_{1}, c_{2}) be an annular rotation of order d. We will find a bijection between the set

A = \{(γ, π) | \begin{matrix}π ∈ ANC(n, m; c, r, s, R, S; α, β, λ, μ), (c_{1}, c_{2})π = π, \\ γ is a connected cycle of π \end{matrix} \}

and the set

B = \{(a, b, R^{E}, R^{I}, V^{E}, V^{I}, V^{CE}, V^{CI}) | \begin{matrix}a ∈ [n − R], b ∈ [m − S], \\ R^{E} ⊂ [n̂], R^{I} ⊂ [m̂], |R^{E}| = r̂, |R^{I}| = ŝ, \\ V^{E} ∈ 𝔖(α̂), V^{I} ∈ 𝔖(β̂), \\ V^{CE} ∈ 𝔖(λ̂), V^{CI} ∈ 𝔖(μ̂) \end{matrix} \} .

Suppose (γ, π) ∈ A. As a running example we will consider (γ, π), where π is the annular noncrossing permutation in Figure 4 and γ = (27, 28, 4, 37, 40).

Let γ = (a_{1}, …, a_{u}, b_{1}, …, b_{v}) with a_{1}, …, a_{u} ∈ [n] and b_{1}, …, b_{v} ∈ {n + 1, …, n + m}. We define a = a_{1} and b = b_{v}. Let A_{1}, A_{2}, …, An̂ be the n̂ consecutive numbers on the exterior circle in clockwise order starting with A_{1} = a. Let B_{1}, B_{2}, …, Bm̂ be the m̂ consecutive numbers on the interior circle in counter-clockwise order ending with Bm̂ = b. In our example, we have a = 27, b = 40, and

A_{1}, A_{2}, …, An̂ = 27, 28, 29, 30, 1, 2, 3, 4, 5, 6,
B_{1}, B_{2}, …, Bm̂ = 35, 36, 37, 38, 39, 40.

By symmetry, π is determined by the cycles whose elements are contained in the sequence

(5.1)  A_{1}, A_{2}, …, An̂, B_{1}, B_{2}, …, Bm̂.

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 (5.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

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.

Hence, R^{E} = {5, 7} and R^{I} = {1, 5}.

Then we have |R^{E}| = r̂ and |R^{I}| = ŝ. Let i_{1} < i_{2} < ⋯ < ir̂ be the elements of R^{E}. We define V^{E} to be the sequence (ℓ_{1}, ℓ_{2}, …, ℓr̂) where ℓ_{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 (5.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 (γ, π) ↦ (a, b, R^{E}, R^{I}, V^{E}, V^{I}, V^{CE}, V^{CI}). Using the ideas of [7, Proposition 4.2] and [8, Proposition 4.1] , one can show that this gives a bijection from A to B.

Thus the number of π ∈ ANC(n, m; c, r, s, R, S; α, β, λ, μ) 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. □

The following evaluations of q-binomial coefficients at a root of unity are well known. See for instance [18, Exercise 96 in Chapter 1].

Lemma 5.3. Suppose ω is a primitive dth root of unity and n is divisible by d. Then we have

[n]_{q=ω} = n/d,
\left[{n \atop k}\right]_{q=ω} = \{ \begin{matrix}\binom{n/d}{k/d} & if k is divisible by d, \\ 0 & otherwise, \end{matrix}

\left[{n − 1 \atop k}\right]_{q=ω} = \{ \begin{matrix}\binom{n/d−1}{k/d} & if k is divisible by d, \\ 0 & otherwise. \end{matrix}

Now we are ready to prove Theorem 2.2.

Proof of Theorem 2.2. We will only show that (2.1) exhibits the cyclic sieving phenomenon. Then (2.2), (2.3), (2.4), and (2.5) follow from Theorem 3.4 and the fact that if q is equal to ω a primitive dth root of unity for a common divisor d of n and m, then

Kre^{ann}(n, m; c, r, s, R, S; α, β, λ, μ) = \frac{[(n − R)(m − S)]_{q}}{[c]_{q}} \left[{n \atop r}\right]_{q}\left[{m \atop s}\right]_{q}\left[{r \atop α}\right]_{q}\left[{s \atop β}\right]_{q}\left[{c \atop λ}\right]_{q}\left[{c \atop μ}\right]_{q},

Nara_{1}^{ann}(n, m; c, r, s, R, S) = c\left[{n \atop r}\right]_{q}\left[{m \atop s}\right]_{q}\left[{R − 1 \atop r − 1}\right]_{q}\left[{S − 1 \atop s − 1}\right]_{q}\left[{n − R \atop c}\right]_{q}\left[{m − S \atop c}\right]_{q},

Nara_{2}^{ann}(n, m; c, r, s) = c\left[{n \atop r}\right]_{q}\left[{m \atop s}\right]_{q}\left[{n \atop r + c}\right]_{q}\left[{m \atop s + c}\right]_{q},

Nara_{3}^{ann}(n, m; c) = c\left[{2n \atop n − c}\right]_{q}\left[{2m \atop m − c}\right]_{q},

Cat^{ann}(n, m) = \frac{[2nm]_{q}}{[m + n]_{q}} \left[{2n − 1 \atop n}\right]_{q}\left[{2m − 1 \atop m}\right]_{q}.

Suppose (c_{1}, c_{2}) is an (n, m)-annular rotation of order d. Then d divides both n and m. By Theorem 5.2 it is sufficient to show that for ω a primitive dth root of unity, we have

(5.2)  X(ω) = d · \frac{(n̂ − R̂)(m̂ − Ŝ)}{ĉ}(n̂ ; r̂)(m̂ ; ŝ)(r̂ ; α̂)(ŝ ; β̂)(ĉ ; λ̂)(ĉ ; μ̂),

if all of n, m, c, r, s, R, S, α, β, λ, μ are divisible by d, and X(ω) = 0 otherwise. By Lemma 5.3 we get (5.2) when all of n, m, c, r, s, R, S, α, β, λ, μ are divisible by d.

It remains to show that if at least one of n, m, c, r, s, R, S, α, β, λ, μ is not divisible by d, then X(ω) = 0. Since d divides both n and m, we have the following cases.

Case 1: r or s is not divisible by d. By (4.3), X(q) is a polynomial divisible by \left[{n \atop r}\right]_{q}\left[{m \atop s}\right]_{q}. Thus, by Lemma 5.3, we get X(ω) = 0.

Case 2: Both r and s are divisible by d, but α or β is not. Suppose α = (1^{a_{1}}, 2^{a_{2}}, …) is not divisible by d. Suppose moreover that a_{j} is not divisible by d. Again by (4.3), X(q) is divisible by

\left[{r \atop α}\right]_{q} = \left[{r \atop a_{j}}\right]_{q}\left[{r − a_{j} \atop a_{1}, …, a_{j−1}, a_{j+1}, …}\right]_{q}.

Thus, by Lemma 5.3, we get X(ω) = 0. If β is not divisible by d, by the same arguments, we get X(ω) = 0.

Case 3: All of r, s, α, β are divisible by d, but c is not. Note that since α and β are divisible by d, so are R and S. By (4.3), 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−ω^{m−S}}{1−ω^{c}} = 0 and we get X(ω) = 0.

Case 4: All of r, s, α, β, R, S, c are divisible by d, but λ or μ is not. Suppose λ is not divisible by d. By (4.3), X(q) is divisible by \left[{c \atop λ}\right]_{q}. By the same argument as in Case 2 we obtain that X(ω) = 0. If μ 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}} \left[{n \atop r}\right]_{q}\left[{m \atop s}\right]_{q}\left[{r \atop α}\right]_{q}\left[{s \atop β}\right]_{q}\left[{c \atop μ}\right]_{q} \frac{[n − R]_{q}}{[c]_{q}} \left[{c \atop λ}\right]_{q}.

Thus in all cases we have X(ω) = 0, which finishes the proof. □

6. Annular noncrossing matchings

An (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.

Theorem 6.1. Suppose n ≡ m ≡ 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}}.

Proof. Such an annular noncrossing matching can be considered as an annular noncrossing permutation with α = (2^{R}) ∈ Par(2R, R), β = (2^{S}) ∈ Par(2S, S), λ = μ = (1^{c}) ∈ Par(c, c), and n − 2R = m − 2S = c. Thus, we obtain the formula immediately from (2.6). □

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

Theorem 6.2. For n ≡ m mod 2, the number of connected (n, m)-annular noncrossing matchings is

\frac{2 ⌈\frac{n}{2}⌉ ⌈\frac{m}{2}⌉}{n + m}\binom{n}{⌈\frac{n}{2}⌉}\binom{m}{⌈\frac{m}{2}⌉}.

Proof. We will prove the equivalent statement: for k ∈ {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 6.1, the number is equal to

∑_{c≥0}(2c + k)\binom{2n + k}{n − c}\binom{2m + k}{m − c}.

Then we are done by Lemma 3.3 for q = 1. □

Acknowledgement

The author would like to thank Vic Reiner for providing his paper with Sommers [14], 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.

References

[1] G. E. Andrews. The theory of partitions. Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1976. Encyclopedia of Mathematics and its Applications, Vol. 2.

[2] G. E. Andrews. The Friedman-Joichi-Stanton monotonicity conjecture at primes. volume 64 of DI-MACS Ser. Discrete Math. Theoret. Comput. Sci. Amer. Math. Soc., Providence, RI, 2004.

[3] H. Barcelo, V. Reiner, and D. Stanton. Bimahonian distributions. J. Lond. Math. Soc. (2), 77(3):627– 646, 2008.

[4] D. Bessis and V. Reiner. Cyclic sieving of noncrossing partitions for complex reflection groups. Ann. Comb., 15(2):197–222, 2011.

[5] G. Gasper and M. Rahman. Basic hypergeometric series. volume 96 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, second edition, 2004. With a foreword by Richard Askey.

[6] I. P. Goulden and D. M. Jackson. Transitive factorizations into transpositions and holomorphic mappings of the sphere. Proc. Amer. Math. Soc., 125:51–60, 1997.

[7] I. P. Goulden, A. Nica, and I. Oancea. Enumerative properties of NC^{(B)}(p, q). Ann. Comb., 15(2):277– 303, 2011.

[8] J. S. Kim. Chain enumeration of k-divisible noncrossing partitions of classical types. J. Combin. Theory Ser. A, 118(3):879–898, 2011.

[9] J. S. Kim, S. Seo, and H. Shin. Annular noncrossing permutations and minimal transitive factoriza-

tions. http://arxiv.org/abs/1201.5703.

[10] C. King. Two-dimensional Potts model and annular partitions. J. Statist. Phys., 96(5-6):1071–1089, 1999.

[11] G. Kreweras. Sur les partitions non croisées d’un cycle. Discrete Math., 1:333–350, 1972.

[12] J. A. Mingo and A. Nica. Annular noncrossing permutations and partitions, and second-order asymptotics for random matrices. Int. Math. Res. Not., (28):1413–1460, 2004.

[13] A. Nica and I. Oancea. Posets of annular non-crossing partitions of types B and D. Discrete Math., 309(6):1443–1466, 2009.

[14] V. Reiner and E. Sommers. q-analogues of Weyl group Narayana and Kreweras numbers. preprint.

[15] V. Reiner, D. Stanton, and D. White. The cyclic sieving phenomenon. J. Combin. Theory Ser. A, 108(1):17–50, 2004.

[16] B. E. Sagan. The cyclic sieving phenomenon: a survey. volume 392 of London Math. Soc. Lecture Note Ser. Cambridge Univ. Press, Cambridge, 2011.

[17] R. P. Stanley. Weyl groups, the hard Lefschetz theorem, and the Sperner property. SIAM Journal on Algebraic Discrete Methods, 1(2):168–184, 1980.

[18] R. P. Stanley. Enumerative Combinatorics. Vol. 1, second ed. Cambridge University Press, New York/Cambridge, 2011.