Combinatorial statistics on type-B analogues of noncrossing partitions and restricted permutations

Rodica Simion^{∗} Department of Mathematics The George Washington University Washington, DC 20052

Submitted: September 5, 1999; Accepted: January 5, 2000

Abstract

We define type-B analogues of combinatorial statistics previously studied on noncrossing partitions and show that analogous equidistribution and symmetry properties hold in the case of type-B noncrossing partitions. We also identify pattern-avoiding classes of elements in the hyperoctahedral group which parallel known classes of restricted permutations with respect to their relations to noncrossing partitions.

Key words: restricted permutations, pattern-avoidance, noncrossing partitions, signed permutations, permutation statistics, partition statistics, q-analogue

AMS Classification: 05

This paper was dedicated by the author to George Andrews on the occasion of his 60th birthday. We are very sad to report that Rodica Simion died on January 7, 2000, just two days after the acceptance of this paper. We have made the few minor changes requested by the referee and are honored to present her paper here. – The Editors

∗Partially supported by the National Science Foundation, award DMS-9970957.

1 Introduction

The goal of this paper is to give type-B analogues of enumerative results concerning combinatorial statistics defined on (type-A) noncrossing partitions and on certain classes of permutations characterized by pattern-avoidance. To this end, we need B-analogues of the combinatorial objects in question. As type-B noncrossing partitions we use those studied by Reiner [20]. In the hyperoctahedral group, the natural B-analogue of the symmetric group, we identify classes of restricted signed permutations with enumerative properties analogous to those of the 132- and 321-avoiding permutations in the symmetric group. We also propose definitions for four partition statistics (ls^{B}, lb^{B}, rs^{B}, and rb^{B}) as type-B analogues, for noncrossing partitions, of the established statistics ls, lb, rs, rb for type A. We show that these choices yield B-analogues of results which hold for type A. In the remainder of this section we give a brief account of earlier work which motivated our investigation, summarize the main results, and establish the basic definitions and notation used throughout the paper.

The lattice NC_{n}^{A} of (type-A) noncrossing partitions of an n-element set, whose investigation was initiated by Kreweras [16], turns out to support and to be related to a remarkable range of interesting topics. As a poset, it enjoys elegant enumerative and structural properties (see, e.g., [7], [8], [9], [16], [18], [23]), and properties of interest in algebraic combinatorics (e.g., [17], [30]). The natural connection between noncrossing partitions and other combinatorial objects counted by the Catalan numbers leads to relations of NC_{n}^{A} with many aspects of enumerative combinatorics, as well as problems arising in geometric combinatorics, probability theory, topology, and mathematical biology (a brief account and references appear in [25]).

Type-B noncrossing partitions of an n-element set, whose collection we denote by NC_{n}^{B}, were first considered by Montenegro [17] and systematically studied by Reiner [20]. They enjoy a wealth of interesting properties which parallel those for type A, from the standpoint of order structure, enumerative combinatorics, algebraic combinatorics and geometric combinatorics (see [13], [20], [26]).

Here we extend the analogies between NC_{n}^{A} and NC_{n}^{B} in the context of enumeration, by exploring three topics.

1. Four combinatorial statistics defined on type-B noncrossing partitions, how their distributions compare, and how they relate to the order relation on NC_{n}^{B}. Four combinatorial statistics rb^{A}, rs^{A}, lb^{A}, ls^{A} defined for type-A set partitions in terms of restricted growth functions have interesting equidistribution properties, [36], on the entire set partition lattice Π_{n}^{A}, which also hold on type-A noncrossing partitions [24], [38]. In fact, the distributions of these statistics on NC_{n}^{A} yield q-analogues of the Catalan and Narayana numbers which reflect nicely the rank-symmetry and rank-unimodality of NC_{n}^{A}. In Section 2 we propose and establish properties of type-B analogues of these four statistics, applicable to NC_{n}^{B}. Our definitions of rb^{B}, rs^{B}, lb^{B}, ls^{B} on NC_{n}^{B} are modeled on descriptions given in [24] for the values of the type-A statistics on NC_{n}^{A}. We show that, as in the case of type-A, rs^{B} and lb^{B} are equidistributed on each rank of NC_{n}^{B}. The same holds for ls^{B} and rb^{B}. The two q-analogues of the Whitney numbers \binom{n}{k}_{k}^{2} of NC_{n}^{B} obtained from these two pairs of statistics, NC_{n,k}^{B}(q) and NC_{n,k}^{∗B}(q), reflect the rank-symmetry and unimodality of NC_{n}^{B}:

\frac{1}{q^{k}} NC_{n,k}^{B}(q) = \frac{1}{q^{n−k}} NC_{n,n−k}^{B}(q),  (1)
\frac{1}{q^{\binom{k}{2}}} NC_{n,k}^{∗B}(q) = \frac{1}{q^{\binom{n−k}{2}}} NC_{n,n−k}^{∗B}(q).  (2)

The rank-symmetry of these distributions is apparent from their expressions (corollaries 1 and 2), and can be seen directly combinatorially. Also analogously to type A, finer distribution properties hold in relation to the order structure on NC_{n}^{B}: we exhibit a decomposition of NC_{n}^{B} into symmetrically embedded boolean lattices, such that the second pair of statistics is essentially constant on each boolean lattice occurring in the decomposition. A by-product of our explicit decomposition of NC_{n}^{B} into symmetrically embedded boolean lattices (different from those considered in [13], [20]), is a type-B analogue of Touchard’s formula for the Catalan numbers,

\binom{2n}{n} = ∑_{k=0}^{n} \binom{n}{2k}\binom{2k}{k}2^{n−2k},  (3)

along with a combinatorial, order-theoretic, proof.

2. Subsets of the hyperoctahedral group characterized by pattern-avoidance conditions. In the symmetric group, for every 3-letter pattern ρ the number of ρ-avoiding permutations is given by the Catalan number [15]; hence, the same as the number of type-A noncrossing partitions. Other enumeration questions, for permutations which avoid simultaneously several 3-letter patterns, are treated in [22]. Are there similar results for the hyperoctahedral group? In Section 3 we investigate enumerative properties of several classes of restricted signed permutations. The pattern restrictions consist of avoiding 2-letter signed patterns. We show that every 2-letter pattern is avoided by equally many signed permutations in the hyperoctahedral group. These are more numerous than the type-B noncrossing partitions, namely, ∑_{k=0}^{n} \binom{n}{k}^{2}k! in the hyperoctahedral group B_{n}. A q-analogue of this expression appears in work of Solomon [28], in connection with a Bruhat-like decomposition of the monoid of n×n matrices over a field with q elements. Solomon defines a length function on the orbit monoid such that its distribution over rank-k matrices is given by \left[{n \atop k}\right]_{q}^{2} [k]_{q}!. This same expression can be viewed in our context as the distribution of a combinatorial statistic on a class of pattern-avoiding signed permutations. We treat also the enumeration of signed permutations avoiding two 2-letter patterns at the same time. Among such double pattern restrictions we identify four classes whose cardinality is equal to \binom{2n}{n} = #NC_{n}^{B}. They are the signed permutations which avoid simultaneously the patterns 21 and \overline{2} \overline{1}, and three additional classes readily related to this one by means of reversal and barring operations. We note that a different class of \binom{2n}{n} elements of the hyperoctahedral group B_{n}, the set of top fully commutative elements, appears in work of Stembridge including [34].

3. Partition statistics applied to NC_{n}^{B} vs. permutation statistics applied to patternavoiding signed permutations. In type-A, the classes S_{n}(132) and S_{n}(321) of 132and 321-avoiding permutations in the symmetric group S_{n} are not only equinumerous with NC_{n}^{A}, but we have equidistribution results [24] relating permutation and set partition statistics (the definitions of these statistics are given in the next subsection):

∑_{σ∈S_{n}(132)} p^{des^{A}(σ)+1}q^{maj^{A}(σ)} = ∑_{σ∈S_{n}(321)} p^{exc^{A}(σ)+1}q^{Den^{A}(σ)} = ∑_{π∈NC_{n}^{A}} p^{bk^{A}(π)}q^{rb^{A}(π)}.

(4)

In Section 4 we establish a type-B counterpart of (4) relating partition statistics applied to NC_{n}^{B} and permutation statistics applied to B_{n}(21, \overline{2} \overline{1}).

The proofs rely on direct combinatorial methods and explicit bijections. The final section of the paper consists of remarks and problems for further investigation.

1.1 Definitions and notation

We will write [n] for the set {1, 2, …, n} and #X for the cardinality of a set X. In a partially ordered set, we will write x <· y if x is covered by y (i.e., x < y and there is no element t such that x < t < y). The q-analogue of the integer m ≥ 1 is [m]_{q}: = 1 + q + q^{2} + ⋯ + q^{m−1}. The q-analogue of the factorial is then [m]_{q}!: = [1]_{q}[2]_{q} ⋯ [m]_{q} for m ≥ 1, integer, and [0]_{q}!: = 1. Finally, the q-binomial coefficient is \left[{m \atop k}\right]_{q}: = \frac{[m]_{q}!}{[k]_{q}![m−k]_{q}!}.

Noncrossing partitions of type A, NC_{n}^{A}. A partition π of the set [n] is, as usual, an unordered family of nonempty, pairwise disjoint sets B_{1}, B_{2}, ⋯, B_{k} called blocks, whose union is [n]. Ordered by refinement (i.e., π ≤ π′ if each block of π′ is a union of blocks of π), the partitions of [n] form a partially ordered set which is one of the classical examples of a geometric lattice. We denote the set of partitions of [n] by Π_{n}^{A} since it is isomorphic to the lattice of intersections of the type-A hyperplane arrangement in R^{n} (consisting of the hyperplanes x_{i} = x_{j} for 1 ≤ i < j ≤ n). The set of partitions of [n] having k blocks is denoted by Π_{n,k}^{A}.

A partition π ∈ Π_{n}^{A} is a (type-A) noncrossing partition if there are no four elements 1 ≤ a < b < c < d ≤ n so that a, c ∈ B_{i} and b, d ∈ B_{j} for any distinct blocks B_{i} and B_{j}. We denote the set of noncrossing partitions of [n] as NC_{n}^{A}. With the refinement order induced from Π_{n}^{A}, this is a lattice (though only a sub-meet-semilattice of Π_{n}^{A}). It is ranked, with rank function rk^{A}(π) = n−bk^{A}(π), where bk^{A}(π) denotes the number of blocks of the partition π. Further order-related properties established in [16] are that the poset NC_{n}^{A} is rank-symmetric and rank-unimodal with rank sizes given by the Narayana numbers. Writing NC_{n,k}^{A} for the number of noncrossing partitions of [n] into k blocks, we have

#NC_{n,k}^{A} = \frac{1}{n}\binom{n}{k}\binom{n}{k − 1},  (5)

for 1 ≤ k ≤ n. Furthermore, NC_{n}^{A} is self-dual [16], and admits a symmetric chain decomposition [23]. A still stronger property is established in [23] for NC_{n}^{A}: it admits a symmetric boolean decomposition (SBD); that is, its elements can be partitioned into subposets each of which is a boolean lattice whose maximum and minimum elements are placed in NC_{n}^{A} symmetrically with respect to rank.

Noncrossing partitions of type B, NC_{n}^{B}. The hyperplane arrangement of the root system of type B_{n} consists of the hyperplanes in R^{n} with equations x_{i} = ±x_{j} for 1 ≤ i < j ≤ n and the coordinate hyperplanes x_{i} = 0, for 1 ≤ i ≤ n. The subspaces arising as intersections of hyperplanes from among these can be encoded by partitions of \{1, 2, …, n, \overline{1}, \overline{2}, …, \overline{n}\} satisfying the following properties: i) if B = \{a_{1}, …, a_{k}\} is a block, then \overline{B}: = \{\overline{a_{1}}, …, \overline{a_{k}}\} is also a block, where the bar operation is an involution; and ii) there is at most one block, called the zero-block, which is invariant under the bar operation. The collection of such partitions, denoted Π_{n}^{B}, is the set of type-B partitions of [n]. If 1, 2, …, n, \overline{1}, \overline{2}, …, \overline{n} are placed around a circle, clockwise in this order, and if cyclically successive elements of the same block are joined by chords drawn inside the circle, then, following [20], the class of type-B noncrossing partitions, denoted NC_{n}^{B}, is the class of type-B partitions of [n] which admit a cyclic diagram with no crossing chords. Alternatively, a type-B partition is noncrossing if there are no four elements a, b, c, d in clockwise order around the circle, so that a, c lie in one block and b, d lie in another block of the partition.

As in the case of type A, the refinement order on type-B partitions yields a geometric lattice (in fact, isomorphic to a Dowling lattice with an order-2 group), and the noncrossing partitions constitute a sub-meet-semilattice as well as a lattice in its own right. As a poset under the refinement order, NC_{n}^{B} is ranked. Writing bk^{B}(π) for the number of pairs of non-zero blocks of π, the rank is given by rk^{B}(π) = n − bk^{B}(π). For example, π = \{1, \overline{3}, \overline{5}\}, \{\overline{1}, 3, 5\}, \{4\}, \{\overline{4}\}, \{2, \overline{2}\} is an element of NC_{5}^{B} having bk^{B}(π) = 2 and rk^{B}(π) = 3. If NC_{n,k}^{B} denotes the type-B noncrossing partitions of [n] having k pairs of non-zero blocks, then (see [20])

#NC_{n,k}^{B} = \binom{n}{k}^{2}, for 0 ≤ k ≤ n,  (6)

and the total number of type-B noncrossing partitions of [n] is \binom{2n}{n}.

Like its type-A counterpart, NC_{n}^{B} is rank-symmetric and unimodal (readily apparent from the rank-size formulae in (6)). It is also self-dual and it admits a symmetric chain decomposition [20], [13].

It is useful to recall from [20] a bijection between type-B noncrossing partitions and ordered pairs of sets of equal cardinality,

NC_{n}^{B} ↔ {(L, R) : L, R ⊆ [n], #L = #R}.  (7)

It is defined as follows. If n = 0 or if π ∈ NC_{n}^{B} consists of just the zero-block, the corresponding pair is (L(π), R(π)) = (∅, ∅). Otherwise, π has some non-zero block B consisting of elements j_{1}, j_{2}, …, j_{m} which are contiguous clockwise around the circle, in the cyclic diagram of π. Then |j_{1}| ∈ L(π) and |j_{k}| ∈ R(π) (the absolute value sign means that the bar is removed from a barred symbol; an unbarred symbol is unaffected). Remove the elements of this block and of \overline{B}, and repeat this process until no elements or only the zeroblock remain in the diagram. For example, if π = \{1, \overline{6}\}, \{\overline{1}, 6\}, \{2, 3, \overline{5}\}, \{\overline{2}, \overline{3}, 5\}, \{4, \overline{4}\}, then (L(π), R(π)) = ({5, 6}, {1, 3}). We will refer to L(π) and R(π) as the Left-set and Right-set of π. Clearly, we have #L(π) = #R(π) = bk^{B}(π).

Restricted permutations. Let σ = σ_{1}σ_{2} ⋯ σ_{n} be a permutation in the symmetric group S_{n}, and ρ = ρ_{1}ρ_{2} ⋯ ρ_{k} ∈ S_{k}. We say that σ avoids the pattern ρ if there is no sequence of k indices 1 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n such that (σ_{i_{p}} − σ_{i_{q}})(ρ_{p} − ρ_{q}) > 0 for every choice of 1 ≤ p < q ≤ k. In other words, σ avoids the pattern ρ if it contains no subsequence of k values among which the magnitude relation is, pairwise, the same as for the corresponding values in ρ. We will write S_{n}(ρ) for the set of ρ-avoiding permutations in S_{n}, and |ρ| = k to indicate that the length of the pattern ρ is k.

For example, σ = 34125 belongs to S_{5}(321) ∩ S_{5}(132), and contains every other 3letter pattern; for example, it contains the pattern ρ = 213 (in fact, four occurrences of it: 315, 325, 415, 425).

Classes of restricted permutations arise naturally in theoretical computer science in connection with sorting problems (e.g., [15], [35]), as well as in the context of combinatorics related to geometry (e.g., the theory of Kazhdan-Lusztig polynomials [4] and Schubert varieties [12],[2]). Recent work on pattern-avoiding permutations from an enumerative and algorithmic point of view includes [1], [3], [5], [6], [19], [37].

Trivially, if |ρ| = 2 then S_{n}(ρ) consists of only one permutation (either the identity or its reversal). For length-3 patterns, it turns out that S_{n}(ρ) has the same cardinality, independently of the choice of ρ ∈ S_{3} (see [15], [22]). The common cardinality is the nth Catalan number,

#S_{n}(ρ) = C_{n} = \frac{1}{n + 1}\binom{2n}{n} for every ρ ∈ S_{3}.  (8)

That is, #S_{n}(ρ) = #NC_{n}^{A} for each pattern ρ ∈ S_{3} and every n.

Restricted signed permutations. We will view the elements of the hyperoctahedral group B_{n} as signed permutations written as words of the form b = b_{1}b_{2} … b_{n} in which each of the symbols 1, 2, …, n appears, possibly barred. Thus, the cardinality of B_{n} is n!2^{n}. The barring operation represents a sign-change, so it is an involution, and the absolute value notation (as earlier for type-B partitions) means |b_{j}| = b_{j} if the symbol b_{j} is not barred, and |b_{j}| = \overline{b_{j}} if b_{j} is barred.

Let ρ ∈ B_{k}. The set B_{n}(ρ) of ρ-avoiding signed permutations in B_{n} consists of those b ∈ B_{n} for which there is no sequence of k indices, 1 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n such that two conditions hold: (1) b with all bars removed contains the pattern ρ with all bars removed, i.e., (|b_{i_{p}}| − |b_{i_{q}}|)(|ρ_{p}| − |ρ_{q}|) > 0 for all 1 ≤ p < q ≤ k; and (2) for each j, 1 ≤ j ≤ k, the symbol b_{i_{j}} is barred in b if and only if ρ_{j} is barred in ρ. For example, b = 3\overline{4}1\overline{2}5 ∈ B_{5} avoids the signed pattern ρ = \overline{1} \overline{2} and contains all the other seven signed patterns of length 2; among the length-3 signed patterns, it contains only ρ = 213, 2\overline{3}1, 1\overline{2}3, 31\overline{2}, 2\overline{3} \overline{1}, \overline{3}1\overline{2}, and \overline{2} \overline{1}3.

Combinatorial statistics for type-A set partitions. We recall the definitions of four statistics of combinatorial interest defined for set partitions (see [36] and its bibliography for earlier related work). Given a partition π ∈ Π_{n}^{A}, index its blocks in increasing order of their minimum elements and define the restricted growth function of π to be the n-tuple w(π) = w_{1}w_{2} ⋯ w_{n} in which the value of w_{i} is the index of the block of π which contains the element i. Thus, if π = {1, 5, 6}{2, 3, 8}{4, 7}, then its restricted growth function is w(π) = 12231132. Let ls^{A}(π, i) denote the number of distinct values occurring in w(π) to the left of w_{i} and which are smaller than w_{i},

ls^{A}(π, i): = #{w_{j}: 1 ≤ j < i, w_{j} < w_{i}}.  (9)

Similarly, “left bigger,” “right smaller,” and “right bigger” are defined for each index 1 ≤ i ≤ n:

lb^{A}(π, i): = #{w_{j}: 1 ≤ j < i, w_{j} > w_{i}},  (10)
rs^{A}(π, i): = #{w_{j}: i < j ≤ n, w_{j} < w_{i}},  (11)

rb^{A}(π, i): = #{w_{j}: i < j ≤ n, w_{j} > w_{i}}.  (12)

Now the statistics of interest are obtained by summing the contributions of the individual entries in the restricted growth function of π:

ls^{A}(π): = ∑_{i=1}^{n} ls^{A}(π, i), lb^{A}(π): = ∑_{i=1}^{n} lb^{A}(π, i),  (13)

rs^{A}(π): = ∑_{i=1}^{n} rs^{A}(π, i), rb^{A}(π): = ∑_{i=1}^{n} rb^{A}(π, i).  (14)

The distributions of these statistics over Π_{n}^{A} and Π_{n,k}^{A} give q-analogues of the nth Bell number and of the Stirling numbers of the second kind. One of the interesting properties established combinatorially in [36] is that the four statistics fall into two pairs, {ls^{A}, rb^{A}} and {lb^{A}, rs^{A}}, with equal distributions on Π_{n,k}^{A}, for every n, k.

In establishing similar results about the distributions over just noncrossing partitions, the following alternative expressions were useful in [24] (Lemmas 1.1, 1.2, 2.1, 2.2). Later in this paper, we will define type-B analogues of the four statistics, modeled after these expressions.

For any partition π ∈ Π_{n,k}^{A},

ls^{A}(π) = ∑_{i=1}^{k} (i − 1)#B_{i},  (15)

lb^{A}(π) = k(n + 1) − ∑_{i=1}^{k} i#B_{i} − ∑_{i=1}^{k} m_{i}.  (16)

For any noncrossing partition π ∈ NC_{n,k}^{A},

rs^{A}(π) = ∑_{i=1}^{k} M_{i} − ∑_{i=1}^{k} m_{i} − n + k,  (17)

rb^{A}(π) = ∑_{i=1}^{k} m_{i} − k.  (18)

In these expressions, the blocks are indexed in increasing order of their minima, and m_{i}, M_{i} denote the minimum and the maximum elements of the ith block.

Combinatorial statistics for permutations and signed permutations. Two classical permutation statistics are the number of descents and the major index of a permutation (see, e.g., [31]). We recall their definitions. If σ = σ_{1}σ_{2} ⋯ σ_{n} ∈ S_{n}, then its descent set is Des^{A}(σ): = {i ∈ [n − 1] : σ_{i} > σ_{i+1}}. The descent statistic and the major index statistic of σ are

des^{A}(σ): = #Des^{A}(σ), maj^{A}(σ): = ∑_{i∈Des^{A}(σ)} i.  (19)

Pairs of permutation statistics whose joint distribution over S_{n} coincides with that of des^{A} and maj^{A}, ∑_{σ∈S_{n}} p^{des^{A}(σ)}q^{maj^{A}(σ)}, are called Euler-Mahonian. A celebrated Euler-Mahonian pair is that obtained from excedences and Denert’s statistic (see, e.g., [10]), which are defined as follows. The set of excedences of σ ∈ S_{n} is Exc^{A}(σ): = {i ∈ [n] : σ_{i} > i} and the excedence statistic is given by

exc^{A}(σ): = #Exc^{A}(σ).  (20)

The original definition of Denert’s statistic was given a compact equivalent form by Foata and Zeilberger. Write σ_{Exc} for the word σ_{i_{1}}σ_{i_{2}} ⋯ σ_{i_{exc^{A}(σ)}}, where each i_{j} ∈ Exc^{A}(σ). That is, the subsequence in σ consisting of the values which produce excedences. Similarly write σ_{NExc} for the complementary subsequence in σ. For example, if σ = 42153, then Exc^{A}(σ) = {1, 4}, σ_{Exc} = 45 and σ_{NExc} = 213. Then, based on [10], the Denert statistic is given by

Den^{A}(σ): = inv^{A}(σ_{Exc}) + inv^{A}(σ_{NExc}) + ∑_{i∈Exc^{A}(σ)} i,  (21)

where inv denotes the number of inversions. In our earlier example, we obtain Den^{A}(42153) = 0 + 1 + (1 + 4) = 6.

We will be interested in type-B analogues of these permutation statistics. We say that b = b_{1}b_{2} … b_{n} ∈ B_{n} has a descent at i, for 1 ≤ i ≤ n − 1, if b_{i} > b_{i+1} with respect to the total ordering 1 < 2 < ⋯ < n < \overline{n} < ⋯ < \overline{2} < \overline{1}, and that it has a descent at n if b_{n} is barred. As usual, the descent set of b, denoted Des^{B}(b), is the set of all i ∈ [n] such that b has a descent at i. For example, for b = 2\overline{1}\overline{3}547\overline{6} we have Des^{B}(b) = \{2, 3, 4, 7\}. The type-B descent and major index statistics are

des^{B}(b): = #Des^{B}(b), maj^{B}(b): = ∑_{i∈Des^{B}(b)} i.  (22)

For signed permutations, more than one notion of excedence appears in the literature (see [33]), from which we will use the following. Given b = b_{1}b_{2} ⋯ b_{n} ∈ B_{n}, let k be the number of symbols in b which are not barred. Consider the permutation σ^{b} ∈ S_{n+1} defined by σ_{n+1}^{b} = k + 1 and, for each 1 ≤ i ≤ n, σ_{i}^{b} = j if b_{i} is the jth smallest element in the ordering 1 < 2 < ⋯ < n < n + 1 < \overline{1} < \overline{2} < ⋯ < \overline{n}. Then, following [33],

Exc^{B}(b): = Exc^{A}(σ^{b}), exc^{B}(b) = #Exc^{B}(b),  (23)

and we define

Den^{B}(b) = Den^{A}(σ^{b}).  (24)

2 Statistics on type-B noncrossing partitions

We begin by defining B-analogues of the set partition statistics described in section 1.1, valid for noncrossing partitions of type B.

2.1 The statistics ls^{B}, lb^{B}, rs^{B}, rb^{B}

In the correspondence π ↔ (L(π), R(π)) between NC_{n}^{B} and pairs of equal-size subsets of [n], the elements of L(π) and R(π) indicate the Left and Right delimiters of the non-zero blocks. Hence, they can be viewed as analogous to the minimum and maximum elements of the blocks of a type-A noncrossing partition. This suggests the following adaptation of the definitions (15)-(18), to obtain type-B analogues of the four statistics applicable to NC_{n}^{B}:

ls^{B}(π): = ∑_{i=1}^{bk^{B}(π)+1} (i − 1)#B_{i},  (25)

lb^{B}(π): = (n + 1)bk^{B}(π) − ∑_{i=1}^{bk^{B}(π)+1} i#B_{i} − ∑_{l∈L(π)} l,  (26)
rs^{B}(π): = ∑_{r∈R(π)} r − ∑_{l∈L(π)} l − n + bk^{B}(π),  (27)
rb^{B}(π): = ∑_{l∈L(π)} l − bk^{B}(π),  (28)

where B_{i} is the block of π containing the ith smallest element of L(π), and B_{bk^{B}(π)+1} is the set of unbarred symbols in the zero-block.

For example, for π = \{1\}\{\overline{1}\}\{2, 3, \overline{8}\}\{\overline{2}, \overline{3}, 8\}\{4, 5\}\{\overline{4}, \overline{5}\}\{9\}\{\overline{9}\}\{6, \overline{6}, 7, \overline{7}\}, we have (L(π), R(π)) = ({1, 4, 8, 9}, {1, 3, 5, 9}), and bk^{B}(π) = 4. The indexed blocks are B_{1} = \{1\}, B_{2} = \{4, 5\}, B_{3} = \{8, \overline{2}, \overline{3}\}, B_{4} = \{9\}, and from the zero-block we obtain B_{5} = {6, 7}. Therefore, rs^{B}(π) = 18 − 22 − 9 + 4 = −9, rb^{B}(π) = 22 − 4 = 18, ls^{B}(π) = 0 + 2 + 6 + 3 + 8 = 19, and lb^{B}(π) = 10 · 4 − (1 + 4 + 9 + 4 + 10) − 22 = −10.

Note that rs^{B} and lb^{B} may assume negative values. It is easy to see that rs^{B} assumes the values between −(k+1)(n−k) and (k−1)(n−k). As we will see in the next subsection, lb^{B} has the same distribution as rs^{B} on every rank of NC_{n}^{B}, so this is its range as well. The definitions of these statistics could be easily modified to produce only nonnegative values.

2.2 Two equidistribution results

As in the type-A case, we have two pairs of statistics – (lb^{B}, rs^{B}) and (ls^{B}, rb^{B}) – which are equidistributed on each rank of NC_{n}^{B}. The results of this subsection show that each of the two pairs of statistics satisfy finer distribution properties with respect to the order relation on NC_{n}^{B}.

Theorem 1 For each n > 0 and 0 ≤ k ≤ n, there is a bijection φ: NC_{n,k}^{B} → NC_{n,k}^{B} such that lb^{B}(π) = rs^{B}(φ(π)) and L(π) = L(φ(π)). Therefore, for every L ⊆ [n], we have

∑_{π∈NC_{n,k}^{B}(L)} q^{lb^{B}(π)} = ∑_{π∈NC_{n,k}^{B}(L)} q^{rs^{B}(π)},  (29)

where NC_{n,k}^{B}(L) is the collection of type-B noncrossing partitions of [n] having k pairs of non-zero blocks and Left-set L.

Proof: Given π ∈ NC_{n}^{B} with k pairs of non-zero blocks, we will define the desired partition φ(π) by specifying its Left- and Right-sets. The Left-set is the same as for π, L(φ(π)) = L(π). The Right-set R(φ(π)) consists of the partial sums of the sizes of the (non-zero) blocks of π which contain the elements of L: R(φ(π)): = {∑_{j=1}^{i} #B_{j}, 1 ≤ i ≤ bk^{B}(π)}. For the partition in the preceding example (end of subsection 2.1), we obtain R(φ(π)) = \{1, 3, 6, 7\} and φ(π) = \{1\}\{\overline{1}\}\{2, 3, \overline{9}\}\{\overline{2}, \overline{3}, 9\}\{4, 5, 6\}\{\overline{4}, \overline{5}, \overline{6}\}\{7, \overline{8}\}\{\overline{7}, 8\}.

To check that rs^{B}(φ(π)) = lb^{B}(π), note that if, given n, we prescribe the Left-set L, and thus the number bk^{B} of non-zero blocks, then by the definitions (26) and (27), it suffices to show that (bk^{B}(π) + 1)n − ∑_{i=1}^{bk^{B}(π)+1} i#B_{i} = ∑_{r∈R(φ(π))} r. This can be easily verified by a direct calculation.

It remains to verify that φ is invertible. We consider a partition π′ ∈ NC_{n,k}^{B}(L) and we construct a partition π ∈ NC_{n,k}^{B}(L) such that φ(π) = π′. Let the elements of L(π′) = L and R(π′) be 1 ≤ l_{1} < l_{2} < ⋯ < l_{k} ≤ n and 1 ≤ r_{1} < r_{2} < ⋯ < r_{k} ≤ n, respectively. Define b_{1}: = r_{1} and b_{i} = r_{i} − r_{i−1} for i = 2, …, k. Note that there exists at least one index i such that b_{i} ≤ l_{i+1} − l_{i}, where we set l_{k+1} = n + l_{1}, since otherwise we would have r_{k} = b_{1} + b_{2} + ⋯ + b_{k} > n. For such an index i, let a total of b_{i} clockwise consecutive elements beginning with l_{i} constitute a block of the partition π. Since each b_{i} is no larger than n, this is a non-zero block. Apply the bar operation to obtain the required pair of non-zero blocks in π. Now this process is repeated, with suitable adjustments: elements of \{1, …, n, \overline{1}, …, \overline{n}\} which have already been assigned to some block of π are skipped when checking for clockwise consecutive elements. It is easy to see that the partition π whose non-zero blocks are produced in this way lies in NC_{n,k}^{B}(L) and φ(π) = π′. ◇

Consequently, for each n, k, the statistics lb^{B} and rs^{B} give rise to the same q-analogue of \binom{n}{k}^{2}.

Corollary 1 The common distribution of the statistics lb^{B} and rs^{B} over type-B noncrossing partitions of [n] having k pairs of non-zero blocks is given by:

NC_{n,k}^{B}(q) : = ∑_{π∈NC_{n,k}^{B}} q^{lb^{B}(π)} = ∑_{π∈NC_{n,k}^{B}} q^{rs^{B}(π)} = q^{−(k+1)(n−k)} \left[{n \atop k}\right]_{q}^{2} .  (30)

Proof: The preceding theorem implies the equidistribution of lb^{B} and rs^{B} on each rank of NC_{n}^{B}. The definition (27) of rs^{B} is especially convenient for calculating the polynomial NC_{n,k}^{B}(q):

NC_{n,k}^{B}(q) = ∑_{π∈NC_{n,k}^{B}} q^{rs^{B}(π)}
= q^{−n+k} ∑_{{L,R∈[n] \atop #L=#R=k}} q^{∑_{r∈R} r−∑_{l∈L} l}

= q^{−n+k} (\left[{n \atop k}\right]_{q} q^{\binom{k+1}{2}}) (\left[{n \atop k}\right]_{q^{−1}} q^{−\binom{k+1}{2}}) .

The last equality follows from the independence of L and R, and standard properties of q-binomial coefficients. We can take advantage of the well-known fact that \left[{n \atop k}\right]_{q} is a polynomial in q of degree k(n − k), with non-zero constant term, and whose coefficients form a symmetric sequence, to write \left[{n \atop k}\right]_{q^{−1}} in terms of (the reciprocal of) \left[{n \atop k}\right]_{q}. This

leads to the desired formula for NC_{n,k}^{B}(q). ◇

The other two statistics are equidistributed on each rank of NC_{n}^{B} in an even stronger sense: we can exhibit an involution which preserves rank and interchanges the values of ls^{B} and rb^{B}.

Theorem 2 For each n > 0 and 0 ≤ k ≤ n, there is a bijection ψ: NC_{n,k}^{B} → NC_{n,k}^{B} such that ls^{B}(π) = rb^{B}(ψ(π)) and rb^{B}(π) = ls^{B}(ψ(π)).

Proof: First note that if k = 0, then we have all elements in the zero-block. For this partition, both ls^{B} and rb^{B} vanish, and we let ψ fix it. Consider now the case when there are k > 0 pairs of non-zero blocks, i.e., let π ∈ NC_{n,k}^{B}. Let l_{1} < l_{2} < ⋯ < l_{k} be the elements of L(π), and b_{i} be the cardinality of the (non-zero) block containing l_{i}, for i = 1, …, k. Let also b_{k+1} be the number of unbarred elements in the zero-block of π. Thus, ∑_{i=1}^{k+1} b_{i} = n. Define two sequences, ℓ′ and b′ whose entries are:

ℓ′_{1} : = 1 + b_{k+1}
ℓ′_{2} : = 1 + b_{k+1} + b_{k}
⋮
ℓ′_{k} : = 1 + b_{k+1} + b_{k} + ⋯ + b_{2}
ℓ′_{k+1} : = n + 1 + b_{k+1}

and

b′_{1} : = n + 1 − l_{k}
b′_{2} : = l_{k} − l_{k−1}
⋮
b′_{k} : = l_{2} − l_{1}
b′_{k+1} : = l_{1} − 1.

We claim that there is a unique partition in NC_{n,k}^{B} whose Left-set is {ℓ′_{i} : 1 ≤ i ≤ k} and such that the non-zero block containing ℓ′_{i} has cardinality b′_{i} for each i = 1, …, k. Indeed, every type-B noncrossing partition at rank n − k < n has some non-zero block consisting of contiguous elements in the circular diagram. It is easy to see that there exists at least one index i ∈ [k] for which we have

b′_{i} ≤ ℓ′_{i+1} − ℓ′_{i},  (31)

since (by adding the relevant expressions above) we have b′_{1} + b′_{2} + ⋯ + b′_{k} = n + 1 − l_{1} ≤ n, and ∑_{i=1}^{k} (ℓ′_{i+1} − ℓ′_{i}) = n. For such an index i we can make a block of b′_{i} contiguous elements starting at ℓ′_{i} and moving clockwise. Delete the elements of this block and their images under barring; remove b′_{i} from the sequence b′; remove ℓ′_{i} from the sequence ℓ′; finally, replace ℓ′_{m} with ℓ′_{m} − ℓ′_{i} for each m > i. With these updated sequences replacing ℓ′ and b′, it is easy to check that some inequality of the form (31) holds again, and another pair of non-zero blocks is obtained. The process terminates with a partition π′ ∈ NC_{n,k}^{B} and we set ψ(π) = π′. For example, if n = 10 and k = 5 and if π = \{2\}\{\overline{2}\}\{3, 5, \overline{9}\}\{\overline{3}, \overline{5}, 9\}\{4\}\{\overline{4}\}\{10, \overline{1}\}\{\overline{10}, 1\}\{6, 8, \overline{6}, \overline{8}\}, then for π we have (l_{1}, …, l_{5}) = (2, 4, 7, 9, 10) and (b_{1}, …, b_{5}, b_{6}) = (1, 1, 1, 3, 2, 2). We obtain (ℓ′_{1}, …, ℓ′_{5}, ℓ′_{6}) = (3, 5, 8, 9, 10, 13) and (b′_{1}, …, b′_{5}, b′_{6}) = (1, 1, 2, 3, 2, 1). This leads to ψ(π) = π′ = \{3\}\{\overline{3}\}\{5\}\{\overline{5}\}\{8, \overline{6}\}\{\overline{8}, 6\}\{9, \overline{2}, \overline{4}\}\{\overline{9}, 2, 4\}\{10, \overline{1}\}\{\overline{10}, 1\}\{7, \overline{7}\}.

It is easy to verify that ψ(ψ(π)) = π and that rb^{B}(ψ(π)) = ls^{B}(π) and ls^{B}(π) = rb^{B}(ψ(π)). In the example, we have rb^{B}(π) = ls^{B}(ψ(π)) = 27 and ls^{B}(π) = rb^{B}(ψ(π)) = 30. ◇ Corollary 2 For every n, the statistics ls^{B} and rb^{B} are equidistributed on each rank of NC_{n}^{B}. The common distribution on partitions having k pairs of non-zero blocks is

NC_{n,k}^{∗B}(q) = ∑_{π∈NC_{n,k}^{B}} q^{ls^{B}(π)} = ∑_{π∈NC_{n,k}^{B}} q^{rb^{B}(π)} = \binom{n}{k} \left[{n \atop k}\right]_{q} q^{\binom{k}{2}}.  (32)

Proof: The equidistribution on each rank follows from Theorem 2 and NC_{n,k}^{∗B}(q) can be readily determined using the definition (28) of rb^{B}:

NC_{n,k}^{∗B}(q) = ∑_{π∈NC_{n,k}^{B}} q^{rb^{B}(π)}
= q^{−k} ∑_{{L,R⊆[n] \atop #L=#R=k}} q^{∑_{l∈L} l}

= q^{−k}\binom{n}{k} ∑_{L⊆[n],#L=k} q^{∑_{l∈L} l},

which can be rewritten as claimed. ◇

2.3 Relations with poset symmetry properties of NC_{n}^{B}

The distributions of the statistics lb^{B}, rs^{B}, ls^{B}, rb^{B} enjoy several properties which reflect order-theoretic symmetry in the structure of the lattice NC_{n}^{B}.

Proposition 1 The rank-symmetry of NC_{n}^{B} is respected by the distribution NC_{n,k}^{B}(q) of lb^{B}, rs^{B}, and by the distribution NC_{n,k}^{∗B}(q) of ls^{B}, rb^{B} on type-B noncrossing partitions of [n] with k pairs of non-zero blocks:

\frac{1}{q^{k}} NC_{n,k}^{B}(q) = \frac{1}{q^{n−k}} NC_{n,n−k}^{B}(q),  \frac{1}{q^{\binom{k}{2}}} NC_{n,k}^{∗B}(q) = \frac{1}{q^{\binom{n−k}{2}}} NC_{n,n−k}^{∗B}(q). (33)

Each of these distributions is symmetric and unimodal.

Proof: The internal symmetry and unimodality as well as the external symmetry relations follow immediately from the expressions (30) and (32) and classical properties of q-binomial coefficients. Combinatorially, the bijection β: NC_{n,k}^{B} → NC_{n,n−k}^{B} mapping π to π′ so that L(π′) = [n] − L(π) and R(π′) = [n] − R(π) has the property that rs^{B}(π′) = rs^{B}(π) − n + 2k, implying the external symmetry relation for NC_{n,k}^{B}(q) claimed in (33). It also has the property that rb^{B}(π′) = rb^{B}(π) + \binom{k}{2} − \binom{n−k}{2}, implying the external symmetry relation for NC_{n,k}^{∗B}(q). ◇

The symmetry of the distributions within each rank NC_{n,k}^{B} can be made combinatorially explicit. For rb^{B} and ls^{B} (next corollary) the argument is an immediate adaptation of the standard combinatorial proof of the symmetry of the coefficients of \left[{n \atop k}\right]_{q}. For rs^{B}

and lb^{B} it is a consequence of how rs^{B} relates to an order-theoretic property of NC_{n}^{B} (Theorem 3 and Corollary 4).

Corollary 3 On each rank of NC_{n}^{B}, the statistics rb^{B} and ls^{B} are distributed symmetrically.

Proof: It suffices to verify that this is the case for rb^{B}. Let c: [n] → [n] be the map defined by c(i) = n + 1 − i. Given π ∈ NC_{n,k}^{B}, let π′ be the partition in NC_{n,k}^{B} whose Left- and Right-sets are L(π′) = c(L(π)) and R(π′) = c(R(π)). This gives an involution on NC_{n,k}^{B} with the property that rb^{B}(π) + rb^{B}(π′) = k(n − 1). But this is equal to the sum of the minimum and maximum values assumed by rb^{B} on NC_{n,k}^{B}, and the symmetry of the distribution is established. ◇

We now turn to a stronger symmetry property of NC_{n}^{B} and its relation to the statistic rs^{B}. The lattice NC_{n}^{B} admits a symmetric boolean decomposition (SBD). That is, it is possible to partition the elements of NC_{n}^{B} into pairwise disjoint subposets having two properties: 1) for each subposet there is a value r such that its elements lie at ranks r, r + 1, …, n − r in NC_{n}^{B}, and the cover relations in the subposet are covering relations in NC_{n}^{B}, and 2) each subposet is isomorphic to a boolean lattice. Such a decomposition is obtained for NC_{n}^{B} in [20], by means analogous to those used in [23] to establish a SBD for NC_{n}^{A}; related facts for NC_{n}^{B} appears in [13]. Here we give an explicit SBD of NC_{n}^{B}, different from the earlier ones, having the property that the statistic rs^{B} is essentially constant on each boolean lattice. This is a refinement of the rank-symmetry of NC_{n}^{B}, which parallels the property (see [24]) of NC_{n}^{A} that rs^{A} is constant on each boolean lattice of the SBD constructed in [23]. Two enumerative consequences are given as corollaries.

Theorem 3 The lattice NC_{n}^{B} admits a symmetric boolean decomposition with the property that rs^{B}(π) + rk^{B}(π) = rs^{B}(π′) + rk^{B}(π′) if π, π′ belong to the same boolean lattice.

Proof: Let L_{1}, R_{1} be two disjoint subsets of [n] of equal cardinality, say, #L_{1} = #R_{1} = k. Consider all the pairs (L_{1} ∪ S, R_{1} ∪ S) where S ranges over all subsets of [n] − (L_{1} ∪ R_{1}). Clearly, these pairs ordered by componentwise reverse containment form a poset isomorphic to a boolean lattice of height n − #L_{1} − #R_{1} = n − 2k. Denote this boolean lattice by B(L_{1}, R_{1}). Thus, (L_{1}, R_{1}) is its maximum element and (L_{0}, R_{0}): = ([n] − R_{1}, [n] − L_{1}) is its minimum element.

We claim that the image of B(L_{1}, R_{1}) under the bijection (7) is a boolean lattice symmetrically embedded in NC_{n}^{B}, and that the collection of these boolean lattices, as (L_{1}, R_{1}) range over all pairs of disjoint subsets of equal cardinality, constitutes a SBD of NC_{n}^{B}.

Using the bijection (7), let the noncrossing partitions corresponding to the maximum and minimum of B(L_{1}, R_{1}) be π_{1} ↔ (L_{1}, R_{1}) and π_{0} ↔ (L_{0}, R_{0}). It is clear that we have rk^{B}(π_{0}) + rk^{B}(π_{1}) = n, as desired for a boolean lattice in a SBD. We verify that the bijection (7) maps a covering (L_{1} ∪ S ∪ {s}, R_{1} ∪ S ∪ {s}) <· (L_{1} ∪ S, R_{1} ∪ S) of B(L_{1}, R_{1}) to a covering π <· π′ in NC_{n}^{B}. Indeed, the elements s and \overline{s} appear as singleton blocks in π but not in π′; the remaining elements of the Left- and Right-sets are the same in π and π′. It follows that π is covered by π′ in NC_{n}^{B}.

Finally, the images in NC_{n}^{B} of the boolean lattices of the form B(L_{1}, R_{1}) constitute a partition of the elements of NC_{n}^{B}. This follows from the observation that an element π ∈ NC_{n}^{B} which is encoded by a pair (L(π), R(π)) belongs to a well-defined boolean lattice B(L_{1}, R_{1}). Namely, the boolean lattice arising from the pair of sets L_{1} = L(π)−R(π) and R_{1} = R(π)−L(π). Indeed, in every boolean lattice of the form B(L_{1}, R_{1}), the differences (L_{1} ∪ S) − (R_{1} ∪ S) and (R_{1} ∪ S) − (L_{1} ∪ S) are equal to L_{1} and R_{1}, respectively, for every S.

The relation of this SBD to the rs^{B} statistic is now obvious: the value of ∑_{r∈R(π)} r − ∑_{l∈L(π)} l is constant for all π in the same boolean lattice of our SBD. Comparing this difference with the definition (27) of rs^{B}(π), it follows that rs^{B}(π) + rk^{B}(π) = ∑_{r∈R_{1}} r − ∑_{l∈L_{1}} l has the same value for every π in the embedding of B(L_{1}, R_{1}) into NC_{n}^{B}. ◇

Several consequences follow now readily. First, we obtain an alternative combinatorial proof of the external symmetry of the polynomials NC_{n,k}^{B}(q) stated in (33). Compared to the proof of Proposition 1, here we see the compatibility of the statistic rs^{B} with the order structure of NC_{n}^{B}.

Corollary 4 Let 0 ≤ k ≤ \frac{n}{2}. There is a bijection γ: NC_{n,k}^{B} → NC_{n,n−k}^{B} such that π ≤ γ(π) and rs^{B}(π) + rk^{B}(π) = rs^{B}(γ(π)) + rk^{B}(γ(π)) for each π ∈ NC_{n,k}^{B}.

Proof: Consider the SBD of NC_{n}^{B} constructed in Theorem 3, and a symmetric chain decomposition of each of the boolean lattices B(L_{1}, R_{1}) defined in the proof of the theorem. Let γ(π) be the element in NC_{n,n−k}^{B} which lies in the same boolean lattice as π, and on the same chain in the symmetric chain decomposition of this boolean lattice. It is then clear that γ has the desired properties. ◇

We also obtain a further refinement of the rank-symmetry and rank-unimodality of NC_{n}^{B}.

Corollary 5 For any given value v, the distribution by rank of the type-B noncrossing partitions of [n] for which the rs^{B} + rk^{B} statistic is equal to v,

∑_{{π∈NC^{B}_{n} \atop rs^{B} (π)+rk^{B} (π)=v}} q^{rk^{B}(π)}  (34)

has symmetric and unimodal coefficients.

Proof: By Theorem 3, the range of summation in (34) is a disjoint union of boolean lattices, themselves rank-symmetric and rank-unimodal posets. Since each of these boolean lattices is embedded in NC_{n}^{B} on consecutive ranks and symmetrically with respect to rank, the desired conclusion follows. ◇

One of the consequences of the SBD of NC_{n}^{A} described in [23] is a combinatorial proof of Touchard’s identity

C_{n} = ∑_{k=0}^{n−1} \binom{n − 1}{2k}C_{k} 2^{n−1−2k}.  (35)

We close this section with a “type-B Touchard identity” which arises, along with an order-theoretic combinatorial proof, from Theorem 3.

Corollary 6 For every n ≥ 0,

#NC_{n}^{B} = ∑_{k=0}^{n} \binom{n}{2k}#NC_{k}^{B} 2^{n−2k}.  (36)

More explicitly,

\binom{2n}{n} = ∑_{k=0}^{n} \binom{n}{2k}\binom{2k}{k} 2^{n−2k}.  (37)

Proof: The total number of elements of NC_{n}^{B} is obtained as the sum of the cardinalities of the boolean lattices in the SBD of Theorem 3. There are \binom{n}{2k}\binom{2k}{k} choices for an ordered pair (L_{1}, R_{1}) of disjoint k-subsets of [n]. Such a choice yields a boolean lattice of height n − 2k, as seen in the proof of Theorem 3. ◇

3 Restricted signed permutations

In the symmetric group, patterns of length 2 are uninterestingly restrictive, while length-3 patterns have the interesting property of leading to the same number of restricted permutations in S_{n}, for all n, namely the nth Catalan number. Counterparts of these cases for the hyperoctahedral group arise here from restrictions by patterns of lengths 1 and 2, respectively. The restricted classes B_{n}(1) and B_{n}(\overline{1}) consist, obviously, of the n! signed permutations in which all – respectively none – of the symbols are barred. The eight length-2 signed patterns give rise to some enumeratively interesting classes of signed permutations, which we examine in this section.

3.1 Single restrictions by 2-letter patterns

Divide the 2-letter signed patterns into two classes, S and D, according to whether the two symbols are simultaneously barred or not,

S = \{12, 21, \overline{1} \overline{2}, \overline{2} \overline{1}\} and D = \{1\overline{2}, \overline{1}2, 2\overline{1}, \overline{2}1\}.  (38)

Observation 1 It is immediately apparent that reversal (i.e., reading the permutation right-to-left: b_{1}b_{2} ⋯ b_{n} ↦ b_{n}b_{n−1} ⋯ b_{1}) and barring (that is, b_{1}b_{2} ⋯ b_{n} ↦ \overline{b_{1}} \overline{b_{2}} ⋯ \overline{b_{n}}) give bijections which show that if ρ and ρ′ are both in S or both in D, then #B_{n}(ρ) = #B_{n}(ρ′).

In fact, like the length-3 patterns for the symmetric group, all the length-2 signed patterns give rise to the same number of restricted signed permutations.

Proposition 2 If ρ and ρ′ are any 2-letter signed patterns, then for every n

#B_{n}(ρ) = #B_{n}(ρ′).  (39)

Proof: Let β_{n}(ρ): = #B_{n}(ρ). By Observation 1, it suffices to show that β_{n}(12) = β_{n}(1\overline{2}). This is trivially true for n = 0 and we claim that the sequences (β_{n}(12))_{n≥0} and (β_{n}(1\overline{2}))_{n≥0} satisfy the same recurrence relation for n ≥ 1.

Let b = b_{1}b_{2} … b_{n} ∈ B_{n}(12) and consider the symbol b_{1}. Suppose first that b_{1} is not barred, say, b_{1} = i. Since b is 12-avoiding, i + 1, …, n must appear barred in b, in arbitrary order. Also, 1, …, i − 1 can be arbitrarily barred or not, and can be placed in any i − 1 positions from among positions 2, …, n, subject to the condition that they themselves form a 12-avoiding signed permutation. Consequently, the number of b ∈ B_{n}(12) which begin with an unbarred symbol is

∑_{i=1}^{n} \binom{n − 1}{i − 1}(n − i)!β_{i−1}(12).  (40)

If b_{1} = \overline{i} for some i, then b ∈ B_{n}(12) if and only if b_{2} … b_{n} is a 12-avoiding signed permutation. This case contributes

nβ_{n−1}(12)  (41)

further elements of B_{n}(12). Adding the expressions in (40) and (41) one obtains a recurrence relation satisfied by β_{n}(12) for n ≥ 1:

β_{n}(12) = (n + 1)β_{n−1}(12) + (n − 1)! ∑_{j=0}^{n−2} \frac{β_{j}(12)}{j!}.  (42)

Similarly, if b ∈ B_{n}(1\overline{2}), suppose first that b_{1} = i for some i. To avoid the pattern 1\overline{2}, it is necessary and sufficient that: i) the symbols larger than i be unbarred, ii) the symbols smaller than i form a 1\overline{2}-avoiding signed permutation. Next, if b_{1} = \overline{i} for some i, then b_{2} ⋯ b_{n} is an arbitrary 1\overline{2}-avoiding signed permutation of [n] − \{i\}. Thus, β_{n}(1\overline{2}) satisfies a recurrence relation identical to (42), and the proof is complete. ◇

The common cardinality of all restricted classes B_{n}(ρ) for length-2 patterns is now easy to determine.

Proposition 3 If ρ is any signed pattern of length 2, then for each n,

#B_{n}(ρ) = ∑_{k=0}^{n} \binom{n}{k}^{2} · k!.  (43)

Proof: By Proposition 2, it suffices to show that formula (43) holds for ρ = 12. This follows readily since each element of B_{n}(12) is a shuffle of an arbitrary permutation of, say, k barred symbols and the decreasing sequence formed by the remaining, not barred, symbols. Summing over k yields the formula. ◇

In fact, finer enumerative results hold.

Observation 2 Fix n and any choice of a letter x ∈ \{1, 2, …, n, \overline{1}, \overline{2}, …, \overline{n}\}. Then the number of signed permutations b whose first entry is b_{1} = x is the same in B_{n}(12) as in B_{n}(1\overline{2}).

This is apparent in the proof of Proposition 2. It is analogous to the fact [22] that in S_{n}(123) and in S_{n}(132) there are equally many permutations with a prescribed first entry.

Other enumerative relations hold between subclasses of B_{n}(12) and B_{n}(1\overline{2}). For example, essentially by iterating the preceding observation, one has:

Observation 3 For each n, the number of signed permutations whose leftmost unbarred symbol occurs in position p is the same in the classes of restricted signed permutations B_{n}(12) and B_{n}(1\overline{2}). We convene to set p = n + 1 if all symbols are barred.

We close with a q-analogue of the expression (3), based on combinatorial statistics on signed permutations. This q-analogue arises in a different context in [28].

Observation 4 For a signed permutation b ∈ B_{n}, define the statistics suv(b): = the sum of the values which are not barred in b, sup(b): = the sum of the positions of the symbols which are not barred in b, uinv(b): = the number of inversions in the subword of b consisting of the unbarred

symbols. Now define

s(b): = suv(b) + sup(b) + uinv(b) − k(k + 1),  (44)

where k denotes the number of barred symbols in b. Then

∑_{b∈B_{n}(\overline{1} \overline{2})} q^{s(b)} = ∑_{k=0}^{n} \left[{n \atop k}\right]_{q}^{2} [k]_{q}!.  (45)

Indeed, in a signed permutation b ∈ B_{n}(\overline{1} \overline{2}), the values, order, and positions of the unbarred symbols are arbitrary, while the ordering of the barred symbols is forced, and (45) follows readily. We note that alternative descriptions of the value of s(b) and other choices of the pattern-restriction are possible.

3.2 Double restrictions by 2-letter patterns

By taking advantage of the operations of reversal, barring, and complementation (the last one means b_{i} is replaced with the value n + 1 − |b_{i}|, which we bar if and only if b_{i} is a barred symbol), the question of determining the cardinality of B_{n}(ρ, ρ′) for the 28 choices of two 2-letter signed patterns, reduces to 7 cases.

Proposition 4 Given n and two length-2 signed patterns ρ, ρ′, let β_{n}(ρ, ρ′) = #B_{n}(ρ, ρ′), the number of signed permutations in B_{n} which avoid simultaneously ρ and ρ′. The value of β_{n}(ρ, ρ′) satisfies one of the following relations, according to which orbit (under reversal, barring, complementation) contains the pair ρ, ρ′:

β_{n}(12, 21) = 2 · n!,  (46)
β_{n}(2\overline{1}, \overline{1}2) = β_{n}(2\overline{1}, 1\overline{2}) = β_{n}(1\overline{2}, \overline{1}2) = β_{n}(12, 1\overline{2}) = (n + 1)!,  (47)
n! < β_{n}(12, \overline{2}1) < (n + 1)! for n ≥ 3,  (48)
β_{n}(21, \overline{2} \overline{1}) = \binom{2n}{n}.  (49)

Proof: Each relation can be established by examining the form of the restricted signed permutations in question and resorting, as needed, to a recurrence relation and induction.

To verify (46) note that b ∈ B_{n}(12, 21) has either no unbarred symbol (in which case it is one of the n! permutations of \overline{1}, …, \overline{n}), or it has just one unbarred symbol i inserted in any position in an arbitrary permutation of \overline{1}, …, \overline{i − 1}, \overline{i + 1}, …, \overline{n}. This gives β_{n}(12, 21) = n! + n(n − 1)!, as claimed in (46).

Consider now b ∈ B_{n}(2\overline{1}, \overline{1}2). If b_{1} = i, then the smaller values 1, …, i − 1 must be unbarred in b and can be permuted arbitrarily and placed in any of the positions 2 through n; the larger values i + 1, …, n must constitute a (2\overline{1}, \overline{1}2)-avoiding signed permutation. If b_{1} = \overline{i}, then the discussion is similar. This leads to the recurrence relation

\frac{β_{n}(2\overline{1}, \overline{1}2)}{(n − 1)!} = 2 · ∑_{j=0}^{n−1} \frac{β_{j}(2\overline{1}, \overline{1}2)}{j!}  (50)

for n ≥ 1, and β_{0}(2\overline{1}, \overline{1}2) = 1. We omit the simple exercise of solving for β_{n}(2\overline{1}, \overline{1}2), as well as the similar argument for finding β_{n}(2\overline{1}, 1\overline{2}) and β_{n}(1\overline{2}, \overline{1}2).

In the last case of (47), B_{n}(12, 1\overline{2}), note that if b_{1} is an unbarred symbol, then the pattern restriction forces b_{1} = n and that if b_{1} is a barred symbol, it may have any value. In both cases, b_{2} ⋯ b_{n} is a (12, 1\overline{2})-avoiding signed permutation on [n] − \{|b_{1}|\}. This yields β_{n}(12, 1\overline{2}) = (n + 1)β_{n−1}(12, 1\overline{2}).

Concerning (48), a similar analysis leads to the recurrence relation β_{n}(12, \overline{2}1) = nβ_{n−1}(12, \overline{2}1) + (n − 1)! ∑_{j=0}^{n−1} \frac{1}{j!} for n ≥ 1, with β_{0}(12, \overline{2}1) = 1. From this the inequalities can be established by induction. The first few values are (β_{n}(12, \overline{2}1))_{n≥0} = (1, 2, 6, 23, 108, …). An expression for β_{n}(12, \overline{2}1) can be obtained by iterating the recurrence relation. From the recurrence relation one can also deduce β_{n}(12, \overline{2}1) = 2nβ_{n−1}(12, \overline{2}1) − (n^{2} − 2)β_{n−2}(12, \overline{2}1) + (n − 2)^{2}β_{n−3}(12, \overline{2}1) for n ≥ 3.

Finally, to verify (49), we observe that if b ∈ B_{n}(21, \overline{2} \overline{1}) then b is determined by the choice of which symbols in it are barred and where they are located. It is a shuffle of the barred and unbarred symbols, each of which are ordered increasingly by absolute value. For each 0 ≤ k ≤ n, there are \binom{n}{k} choices of the values to be barred, and again

\binom{n}{k} choices for their placement in b. Thus (49) follows by direct counting. ◇

The last class of restrictions, which gives \binom{2n}{n} = #NC_{n}^{B} pattern-avoiding signed permutations, is of special interest here and is further considered in Section 4.

4 Relations between statistics on type-B noncrossing partitions and restricted signed permutations

Considering the set of type-B noncrossing partitions NC_{n}^{B} and the elements of B_{n} which avoid simultaneously the patterns 21 and \overline{2} \overline{1}, we obtain a B-analogue of the type-A result of [24] stated in equation (4).

Theorem 4 For every n ≥ 1, there is a bijection γ: B_{n}(21, \overline{2} \overline{1}) → NC_{n}^{B} such that des^{B}(b) = bk^{B}(γ(b)) and maj^{B}(b) = rb^{B}(γ(b)) + bk^{B}(γ(b)). As a consequence,

∑_{b∈B_{n}(21,\overline{2} \overline{1})} p^{des^{B}(b)}q^{maj^{B}(b)} = ∑_{π∈NC_{n}^{B}} (pq)^{bk^{B}(π)}q^{rb^{B}(π)}  (51)

and the common expression for these joint distributions is

∑_{k=0}^{n} \binom{n}{k} \left[{n \atop k}\right]_{q} p^{k}q^{\binom{k+1}{2}}.  (52)

Proof: Based on their characterization used in the proof of Proposition 4, the permutations in B_{n}(21, \overline{2} \overline{1}) are in bijection with the ordered pairs of subsets of [n] having equal cardinality, b ↔ (P (b), B(b)). The subset B(b) is the set of values which are barred in b and the subset P (b) is the set of their positions in b. Recalling from subsection 1.1 the definition of the descent statistic for the hyperoctahedral group, we have P (b) = Des(b).

Let γ(b) be the type-B noncrossing partition whose encoding by its pair of Left- and Right-sets is (Des(b), B(b)). Then, by the definitions of the statistics, it is clear that (51) holds. The expression (52) is immediate from (32). ◇

The expression (52) is a p, q-analogue of ∑_{k=0}^{n} \binom{n}{k}^{2} = \binom{2n}{n} in which one of the

binomial coefficients \binom{n}{k} is replaced by a q-binomial coefficient. George Andrews asked whether it is possible to derive a p, q-analogue in which the other binomial coefficient becomes a p-binomial coefficient.

Proposition 5 For n ≥ 1, the joint distribution of the statistics rs^{B} and rb^{B} on type-B noncrossing partitions satisfies the relation

p^{n} ∑_{π∈NC_{n}^{B}} p^{rs^{B}(π)}(pq)^{rb^{B}(π)} = ∑_{k=0}^{n} \left[{n \atop k}\right]_{p} \left[{n \atop k}\right]_{q} p^{\binom{k+1}{2}}q^{\binom{k}{2}}.  (53)

Proof: By the correspondence π ↔ (L(π), R(π)) and the definitions of rs^{B} and rb^{B}, the left hand side of (53) equals

p^{n} ∑_{k=0}^{n} ∑_{{L,R⊆[n] \atop #L=#R=k}} p^{(∑_{r∈R} r)−n} q^{(∑_{l∈L} l)−k},  (54)

which can be written as the right-hand-side of (53). ◇

We consider now the excedence and Denert statistics defined for type B in (23) and (24).

Proposition 6 For every n, the joint distribution of the excedence and Denert statistics on the (21, \overline{2} \overline{1})-avoiding signed permutations in B_{n} agrees with the joint distribution of the statistics bk^{B} and rb^{B} + bk^{B} on the noncrossing partitions in NC_{n}^{B}:

∑_{b∈B_{n}(21,\overline{2} \overline{1})} p^{exc^{B}(b)}q^{Den^{B}(b)} = ∑_{π∈NC_{n}^{B}} (pq)^{bk^{B}(π)}q^{rb^{B}(π)}.  (55)

Proof: For signed permutations in the class B_{n}(21, \overline{2} \overline{1}) the excedences defined via (23) coincide with the descents, as was observed by Galovich [11], so maj^{B} and Den^{B} agree as well. Thus the conclusion follows from the preceding result. ◇

5 Further questions

1. Signed permutations restricted by 2-letter patterns. In view of Proposition 2, we may write β_{n} for the common cardinality of B_{n}(ρ) for all signed 2-letter patterns ρ. For n ≥ 0, this sequence begins with the values 1, 2, 7, 34, 209, 1546, .... A sequence beginning with the same values appears in [27]. The reference is [21] and the sequence is described by the recurrence relation

a_{0} = 1, a_{n} = 2na_{n−1} − (n − 1)^{2}a_{n−2} for n ≥ 1.  (56)

One can verify that this and the recurrence (42) produce the same sequence. Indeed, a_{0} = β_{0} = 1, and assuming inductively that a_{i} = β_{i} for i < n, we have a_{n} = β_{n} if and only if

2na_{n−1} − (n − 1)^{2}a_{n−2} = (n + 1)a_{n−1} + (n − 1)! ∑_{i=0}^{n−2} \frac{a_{i}}{i!} ,  (57)

which can be rewritten as

(n − 1)a_{n−1} = n(n − 1)a_{n−2} + (n − 1)! ∑_{i=0}^{n−3} \frac{a_{i}}{i!} .  (58)

But this is equivalent to the recurrence (42) satisfied by β_{n}.

Thus, for each 2-letter signed pattern ρ, the cardinality β_{n} of the class of restricted signed permutations B_{n}(ρ) satisfies the recurrence (56). It would be interesting to find a combinatorial explanation for this recurrence for the numbers β_{n}. Similarly, it would be interesting to find a combinatorial proof of the 3-term recurrence for β_{n}(12, \overline{2}1) stated in the proof of Proposition 4.

2. Bijections among classes of restricted signed permutations.

In enumerating signed permutations which avoid simultaneously two 2-letter patterns (Proposition 4), we found in equation (47) that #B_{n}(2\overline{1}, \overline{1}2) = #B_{n}(2\overline{1}, 1\overline{2}) = #B_{n}(1\overline{2}, \overline{1}2) = #B_{n}(12, 1\overline{2}) = (n + 1)!. The first three cases are representatives of size-2 orbits of double restrictions, while the fourth case is in an orbit of size 4. This, as well as the difference in the natural recurrence relations used in the proof of (47), raise the question of finding explicit bijections among these classes of restricted signed permutations.

3. Combinatorial statistics on (unrestricted) type-B set partitions. How might the definitions (25)-(28) of statistics for type-B noncrossing partitions be extended to the entire lattice Π_{n}^{B} of type-B partitions? Do analogues of the properties for type-A partitions statistics in [36] hold?

the electronic journal of combinatorics 7 (2000), #R9 25

References

[1] E. Barcucci, A. Del Lungo, and E. Pergola, Permutations with one forbidden subsequence of increasing length, Extended Abstracts, Proc. 9th Conf. Formal Power Series and Algebr. Combin. (Vienna), 1997.

[2] S.C. Billey, Pattern avoidance and rational smoothness of Schubert varieties, Adv. in Math. 139 (1998) 141-156.

[3] M. Bóna, Permutations avoiding certain patterns: the case of length 4 and some generalizations, Discrete Math. 175 (1997) 55-67.

[4] F. Brenti, Combinatorial properties of the Kazhdan-Lusztig R-polynomials for S_{n}, Adv. in Math. 126 (1997) 21-51.

[5] T. Chow and J. West, Forbidden sequences and Chebysheff polynomials, Discrete Math., to appear.

[6] S. Dulucq, S. Gire, and J. West, Permutations with forbidden subsequences and nonseparable planar maps, Proc. 5th Conf. Formal Power Series and Algebr. Combin. (Florence, 1993), Discrete Math. 153 (1996) 85-103.

[7] P. Edelman, Chain enumeration and noncrossing partitions, Discrete Math. 31 (1980) 171-180.

[8] P. Edelman, Multichains, noncrossing partitions and trees, Discrete Math. 40 (1982) 171-179.

[9] P. Edelman and R. Simion, Chains in the lattice of noncrossing partitions. Discrete Math. 126 (1994), no. 1-3, 107–119.

[10] D. Foata and D. Zeilberger, Denert’s permutation statistic is indeed Euler-Mahonian, Stud. Appl. Math. 83 (1990) 31–59.

[11] J. Galovich, personal communication, February 1999.

[12] V. Gasharov, Factoring the Poincare polynomials for the Bruhat order on S_{n}, J. Combin. Theory Ser. A 83 (1998), 159-164.

[13] P. Hersh, Deformation of chains via a local symmetric group action, Electronic J. Combin. 27 (1999).

[14] B. Jacquard and G. Schaeffer, A bijective census of nonseparable planar maps. J. Combin. Theory Ser. A 83 (1998), no. 1, 1–20.

[15] D. Knuth, “The Art of Computer Programming,” vol. 3, Addison-Wesley, Reading, MA, 1973.

[16] G. Kreweras, Sur les partitions non croisées d’un cycle, Discrete Math. 1 (1972), no. 4, 333–350.

[17] C. Montenegro, The fixed point non-crossing partition lattices, manuscript, 1993.

[18] A. Nica and R. Speicher, A “Fourier transform” for multiplicative functions on noncrossing partitions, J. Algebraic Combin. 6 (1997) 141-160.

[19] J. Noonan and D. Zeilberger, The enumeration of permutations with a prescribed number of “forbidden” patterns, Adv. in Appl. Math. 17 (1996) 381-407.

[20] V. Reiner, Non-crossing partitions for classical reflection groups. Discrete Math. 177 (1997), no. 1-3, 195–222.

[21] J. Ser, “Les Calculs Formels des Séries Factorielles,” Gauthiers-Villars, Paris, 1933.

[22] R. Simion, F. W. Schmidt, Restricted permutations, European Journal of Combinatorics, 6 (1985), 383-406.

[23] R. Simion, D. Ullman, On the structure of the lattice of noncrossing partitions, Discrete Math. 98 (1991), no. 3, 193–206.

[24] R. Simion, Combinatorial statistics on noncrossing partitions, J. Combin. Theory Ser. A 66 (1994) 270-301.

[25] R. Simion, Noncrossing partitions, Discrete Math., to appear.

[26] R. Simion, A type-B analogue of the associahedron, in preparation.

[27] N.J.A. Sloane and S. Plouffe, “The Encyclopedia of Integer Sequences,” Academic Press, Inc., San Diego, CA, 1995.

[28] L. Solomon, The Bruhat decomposition, Tits system and Iwahori ring for the monoid of matrices over a finite field, Geom. Dedicata 36 (1990) 15-49.

[29] R. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry. Graph theory and its applications: East and West (Jinan, 1986), 500–535, Ann. New York Acad. Sci., 576, New York Acad. Sci., New York, 1989.

[30] R. Stanley, Parking functions and noncrossing partitions, Electronic J. Combin. 4 (1997) R20, 14pp.

[31] R. Stanley, “Enumerative Combinatorics,” vol. 1, second edition, Cambridge Studies in Adv. Math., 49, Cambridge Univ. Press, Cambridge, 1997.

[32] R. Stanley, “Enumerative Combinatorics,” vol. 2, Cambridge University Press, New York/Cambridge, 1999.

[33] E. Steingrímsson, Permutations statistics of indexed permutations, European J. Combin. 15 (1994) 187-205.

[34] J. Stembridge, The enumeration of fully commutative elements of Coxeter groups, J. Algebraic Combin. 7 (1998) 291–320.

[35] R. Tarjan, Sorting using networks of queues and stacks, J. Assoc. Comput. Mach. 19 (1972) 341-346.

[36] M. Wachs and D. White, p, q-Stirling numbers and set partition statistics, J. Combin. Theory Ser. A 56 (1991) 27-46.

[37] J. West, Generating trees and forbidden subsequences, Proc. 6th Conf. Formal Power Series and Algebr. Combin. (New Brunswick, NJ, 1994), Discrete Math. 157 (1996) 363-374.

[38] D. White, Interpolating set partition statistics, J. Combin. Theory Ser. A 68 (1994) 262-295.

[39] D. Zeilberger, A proof of Julian West’s conjecture that the number of two-stack-sortable permutations of length n is 2(3n)!/((n + 1)!(2n + 1)!), Discrete Math. 102 (1992), no. 1, 85–93.