NONCROSSING PARTITIONS FOR THE GROUP D_{n}

CHRISTOS A. ATHANASIADIS AND VICTOR REINER

Dedicated to the memory of Rodica Simion

Abstract. The poset of noncrossing partitions can be naturally defined for any finite Coxeter group W. It is a self-dual, graded lattice which reduces to the classical lattice of noncrossing partitions of {1, 2, …, n} defined by Kreweras in 1972 when W is the symmetric group S_{n}, and to its type B analogue defined by the second author in 1997 when W is the hyperoctahedral group. We give a combinatorial description of this lattice in terms of noncrossing planar graphs in the case of the Coxeter group of type D_{n}, thus answering a question of Bessis. Using this description, we compute a number of fundamental enumerative invariants of this lattice, such as the rank sizes, number of maximal chains and Möbius function.

We also extend to the type D case the statement that noncrossing partitions are equidistributed to nonnesting partitions by block sizes, previously known for types A, B and C. This leads to a (case-by-case) proof of a theorem valid for all root systems: the noncrossing and nonnesting subspaces within the intersection lattice of the Coxeter hyperplane arrangement have the same distribution according to W - orbits.

1. Introduction and results

The lattice NC^{A}(n) of noncrossing partitions is a well-behaved and wellstudied subposet inside the lattice Π(n) of partitions of the set [n] := {1, 2, …, n}. It consists of all set partitions π of [n] such that if a < b < c < d and a, c are contained in a block B of π, while b, d are contained in a block B′ of π, then B = B′. The lattice of noncrossing partitions arises naturally in such diverse areas of mathematics as combinatorics, discrete geometry, representation theory, group theory, probability, combinatorial topology and mathematical biology; see the survey [21] by Simion. This paper concerns analogues of this lattice for Coxeter groups and, specifically, for the Coxeter group of type D_{n}.

Such analogues were suggested for the Coxeter groups of types B_{n} and D_{n} in [20] and were shown to have similar enumerative and order theoretic

Date: July 24, 2003; revised April 19, 2004. Key words and phrases. Noncrossing partition, nonnesting partition, reflection group,

root poset, antichain, Catalan number, Narayana numbers, Type D, Garside structure.

2000 Mathematics Subject Classification. Primary 06A07; Secondary 05A18, 05E15, 20F55.

properties to those of NC^{A}(n). Reiner [20, Section 6] asked for a natural definition of the lattice of noncrossing partitions for any finite Coxeter group W. Although the main idea may be described as folklore (cf. [7]), only fairly recently, and in particular after the work of Bessis [4] and Brady and Watt [12], it became apparent that such a definition is both available and useful. More precisely, for u, w ∈ W, let u ≤ w if there is a shortest factorization of u as a product of reflections in W which is a prefix of such a shortest factorization of w. This partial order turns W into a graded poset T^{W} having the identity 1 as its unique minimal element, where the rank of w is the length of the shortest factorization of w into reflections. Let γ be a Coxeter element of W. Since all Coxeter elements in W are conjugate to each other, the interval [1, γ] in T^{W} is independent, up to isomorphism, of the choice of γ. We denote this interval by NC^{W} or by NC^{X_{n}}, where X_{n} is the Cartan-Killing type of W. The poset NC^{W} plays a crucial role in the construction of new monoid structures and K(π, 1) spaces for Artin groups associated with finite Coxeter groups [4, 11, 12] and shares many of the fundamental properties of NC^{A}(n). For instance, it is self-dual [4, Section 2.3], graded and has been verified case-by-case to be a lattice [4, Fact 2.3.1]; see also [12, Section 4].

In the case of the symmetric group it is known that the poset NC^{A_{n−1}} is isomorphic to the lattice NC^{A}(n) of noncrossing partitions; see, for instance, [6, 7, 11]. Similarly, in the case of the hyperoctahedral group the poset NC^{B_{n}} is isomorphic to the type B analogue NC^{B}(n) of NC^{A}(n) proposed in [20]; see [4, 9, 12]. However, it was observed in [12, Section 4] that NC^{D_{n}} is not isomorphic to the type D analogue of NC^{A}(n) suggested in [20]. Bessis [4, Section 4.2] asked for an explicit description of the elements of NC^{D_{n}} as noncrossing planar graphs, similar to those which appear in the definition of NC^{B}(n). We give such a description in Section 3. Using a construction similar to that of NC^{B}(n), we define a poset NC^{D}(n) which we suggest as the type D analogue of NC^{A}(n) and prove the following theorem.

Theorem 1.1. The poset NC^{D_{n}} is isomorphic to NC^{D}(n).

In particular, this gives a different proof that the poset NC^{D_{n}} is indeed a lattice [12, Theorem 4.14]; see Proposition 3.1. We should mention that, independently, Bessis and Corran [5] have generalized this construction to a class of complex reflection groups that contains D_{n}.

In our next main result we compute some basic enumerative invariants of NC^{D_{n}}. We use throughout the convention that \binom{n}{k} = 0 unless k ∈ {0, 1, 2, …, n}.

TYPE D NONCROSSING PARTITIONS 3

Theorem 1.2. (i) The number of elements of NC^{D_{n}} of rank k is equal to the type D Narayana number

\begin{aligned}Nar(D_{n}, k) & = \binom{n}{k}^{2} − \frac{n}{n − 1}\binom{n − 1}{k}\binom{n − 1}{k − 1} \\ & = \binom{n}{k} (\binom{n − 1}{k} + \binom{n − 2}{k − 2}) . \end{aligned}

In particular, the total number of elements of NC^{D_{n}} is equal to the type D Catalan number

Cat (D_{n}) = \binom{2n}{n} − \binom{2n − 2}{n − 1}.

(ii) More generally, for any composition s = (s_{1}, s_{2}, …, s_{m}) of the number n, the number of chains from the minimum to the maximum element in NC^{D_{n}} with successive rank jumps s_{1}, s_{2}, …, s_{m} is equal to

2\binom{n − 1}{s_{1}} ⋯ \binom{n − 1}{s_{m}} + ∑_{i=1}^{m} \binom{n − 1}{s_{1}} ⋯ \binom{n − 2}{s_{i} − 2} ⋯ \binom{n − 1}{s_{m}}.

(iii) The zeta polynomial of NC^{D_{n}} is given by

Z(NC^{D_{n}}, m) = 2\binom{m(n − 1)}{n} + \binom{m(n − 1)}{n − 1}.

(iv) In particular, NC^{D_{n}} has 2(n − 1)^{n} maximal chains, and has Möbius function between the minimum and maximum element equal to

(−1)^{n} (2\binom{2n − 2}{n} − \binom{2n − 3}{n − 1}) .

The Narayana and Catalan numbers which appear in part (i) of Theorem 1.2 can be defined for any finite Coxeter group; see [2, 3] for a number of interesting combinatorial and algebraic-geometric interpretations. It is known [16, 20] that the number of elements of a given rank in NC^{W} and the total number of elements are equal to the corresponding Narayana and Catalan numbers, respectively, in the cases of types A and B. Thus part (i) of the theorem extends this fact to the case of type D. The statement on the cardinality of NC^{D_{n}} is also claimed to have been checked by Picantin [19]. We note that the type D analogue of NC^{A}(n) suggested in [20] has the same cardinality and rank sizes as NC^{D_{n}} [20, Corollary 10] but different zeta polynomial, number of maximal chains and Möbius function.

Our definition of the poset NC^{D}(n) leads naturally to a notion of “block sizes” for noncrossing partitions of type D (see Section 2). Such a notion was already suggested in [1] for nonnesting partitions for the classical root systems, which are other families of combinatorial objects counted by the corresponding Catalan numbers; see [1], [20, Remark 2], [25, Exercise 6.19 (uu)] and Section 2. Our next result refines Theorem 1.2 (i) and extends to the case of type D the main result of [1], stating that noncrossing and nonnesting partitions are equidistributed by block sizes for each of the classical root systems of types A, B and C. Theorem 1.3. Let λ be a partition of n − m with k parts, where m ≥ 0, and let m_{λ} = r_{1}! · r_{2}! ⋯, where r_{i} is the number of parts of λ equal to i. The numbers of noncrossing or nonnesting partitions of type D_{n} with block sizes λ are equal to each other and are given by the formula

\begin{cases}\frac{(n − 1)!}{m_{λ} (n − k − 1)!}, & if m ≥ 2 \\ (r_{1} + 2(n − k)) \frac{(n − 1)!}{m_{λ} (n − k)!}, & if m = 0. \end{cases}

Note that the type D analogue of NC^{A}(n) proposed in [20] fails to preserve this similarity between noncrossing and nonnesting partitions [1, Section 6].

Finally, we show that this equidistribution of noncrossing and nonnesting partitions for the classical types A, B, C, D leads to a case-by-case proof of a result (Theorem 6.3) valid for all (finite, crystallographic) root systems: there are embeddings of the sets of noncrossing and nonnesting partitions into the intersection lattice Π^{W} of the Coxeter hyperplane arrangement and the two distributions according to W -orbits coincide.

This paper is organized as follows. Section 2 collects the necessary background and definitions related to the Coxeter group of type D_{n}, noncrossing partitions and nonnesting partitions. In particular, the poset NC^{D_{n}} is explicitly described. We also include a few enumerative results from [1] which are used in the following sections. Theorem 1.1 is proved in Section 3 after the poset NC^{D}(n) is defined. Theorem 1.2 is proved in Section 4 using Theorem 1.1 and bijective methods similar to those employed in [13, 20] in the case of NC^{A}(n) and NC^{B}(n). Theorem 1.3 is proved in Section 5. Section 6 describes the embeddings of the sets of noncrossing and nonnesting partitions into the intersection lattice Π^{W} and proves Theorem 6.3 on the equidistribution of their W -orbits. Section 7 concludes with a few remarks.

2. Background and definitions

This section includes notation, definitions and some basic background related to Coxeter groups as well as noncrossing and nonnesting partitions of types B and D.

We will mostly follow notation introduced in [1, 12, 20]. We refer the reader to the texts by Humphreys [15] and Stanley [24] for any undefined terminology related to Coxeter groups and partially ordered sets, respectively. Throughout the paper we let

\begin{aligned}[n] & := \{1, 2, …, n\} \\ [n]^{±} & := \{−1, −2, …, −n, 1, 2, …, n\} \end{aligned}

for any positive integer n.

The Coxeter group D_{n}. Let S_{2n} denote the symmetric group on the set [n]^{±}. For any cycle c = (i_{1}, i_{2}, …, i_{k}) in S_{2n} we let c̄ = (−i_{1}, −i_{2}, …, −i_{k}). If c is the transposition (i, j) and i ≠ −j we denote by ((i, j)) the product cc̄ = (i, j)(−i, −j) and call ((i, j)) a D_{n}-reflection, or simply a reflection. The Coxeter group W^{D_{n}} is the subgroup of S_{2n} generated by the reflections ((i, j)). Any element of W^{D_{n}} can be expressed uniquely (up to reordering) as a product of disjoint cycles

(1)  c_{1}c̄_{1} ⋯ c_{k}c̄_{k} d_{1} ⋯ d_{r},

each having at least two elements, where d̄_{j} = d_{j} for j = 1, 2, …, r and r is even; see, for instance, [12, Proposition 3.1]. Following [12], for a cycle c = (i_{1}, i_{2}, …, i_{k}) in S_{2n} we write

((i_{1}, i_{2}, …, i_{k})) = cc̄ = (i_{1}, i_{2}, …, i_{k})(−i_{1}, −i_{2}, …, −i_{k})

and call cc̄ a paired cycle if c is disjoint from c̄. We also write

c = [i_{1}, i_{2}, …, i_{k}]

if c = c̄ = (i_{1}, …, i_{k}, −i_{1}, …, −i_{k}) and call c a balanced cycle. Note that [i] denotes both the balanced cycle (i, −i) and the set {1, 2, …, i}. We will leave it to the reader to decide which notation is meant each time, hoping that no confusion will arise.

For w ∈ W^{D_{n}} we denote by l(w) the minimum number r for which w can be written as a product of r reflections and call it the length of w. (Note: this is not the usual Coxeter group length function, which is defined with respect to the simple reflections as generating set). The cycle ((i_{1}, i_{2}, …, i_{k})) has length k − 1. The length of any element of W^{D_{n}} in the form (1) can be written as a sum over its paired and balanced cycles, where the contribution of ((i_{1}, i_{2}, …, i_{k})) and [i_{1}, i_{2}, …, i_{k}] to this sum is k − 1 and k, respectively [12, Section 3]. We denote by T^{D_{n}} the partial order on the set W^{D_{n}} defined by letting u ≤ w if l(w) = l(u) + l(u^{−1}w). The poset T^{D_{n}} is graded by length and has the identity element 1 as its unique minimal element. For a choice γ of a Coxeter element of W^{D_{n}}, which we fix as γ = [1, 2, …, n−1][n] for convenience, we denote by NC^{D_{n}} the interval [1, γ] in the poset T^{D_{n}}. The poset NC^{D_{n}} is a self-dual, graded lattice of rank n [4, Section 2] [12, Section 4], where the rank function is the restriction of the rank function from T^{D_{n}}.

Noncrossing partitions. A B_{n}-partition is a partition π of the set [n]^{±} into blocks such that (i) if B is a block of π then its negative −B is also a block of π, and (ii) there is at most one block, called the zero block if present, which contains both i and −i for some i. The type of π is the integer partition λ which has a part equal to the cardinality of B for each pair {B, −B} of nonzero blocks of π. Thus λ is a partition of n − m, where m is half the size of the zero block of π, if present, and m = 0 otherwise. We refer to the parts of λ as the block sizes of π. A D_{n}-partition is a B_{n}-partition π with the additional property that the zero block of π, if present, does not consist of a single pair {i, −i}. The set of all B_{n}-partitions, ordered by refinement, is denoted by Π^{B}(n). Its subposet consisting of all D_{n}-partitions is denoted by Π^{D}(n). The posets Π^{B}(n) and Π^{D}(n) are geometric lattices which are isomorphic to the intersection lattices of the B_{n} and D_{n} Coxeter hyperplane arrangements, respectively, and hence they can be considered as type B and D analogues of the partition lattice Π(n). In particular they are graded of rank n and the corank of an element π in either poset is the number of pairs {B, −B} of nonzero blocks of π.

Figure 1. Two elements of NC^{B}(n) for n = 6 with blocks (a) {3, 4, 5}, {−3, −4, −5}, {1, 2, 6, −1, −2, −6} and (b) {3, 4, −5}, {−3, −4, 5}, {2, −6}, {−2, 6}, {1}, {−1}.

Let us label the vertices of a convex 2n-gon as 1, 2, …, n, −1, −2, …, −n clockwise, in this order. Given a B_{n}-partition π and a block B of π, let ρ(B) denote the convex hull of the set of vertices labeled with the elements of B. We call π noncrossing if ρ(B) and ρ(B′) have void intersection for any two distinct blocks B and B′ of π. Two noncrossing partitions are depicted in Figure 1 for n = 6. The subposet of Π^{B}(n) consisting of the noncrossing B_{n}-partitions is a self-dual, graded lattice of rank n which is denoted by NC^{B}(n) [20, Section 2].

Nonnesting partitions. Let e_{1}, e_{2}, …, e_{n} be the unit coordinate vectors in ℝ^{n} and Φ be a root system of one of the types B_{n}, C_{n} or D_{n}. In what follows, we identify Φ with its type X_{n} and fix the choices

Φ^{+} = \begin{cases}\{e_{i} ± e_{j} : 1 ≤ i < j ≤ n\}, & if Φ = D_{n}, \\ D_{n}^{+} ∪ \{e_{i} : 1 ≤ i ≤ n\}, & if Φ = B_{n}, \\ D_{n}^{+} ∪ \{2e_{i} : 1 ≤ i ≤ n\}, & if Φ = C_{n} \end{cases}

of positive roots for Φ. The root poset of Φ is the set Φ^{+} of positive roots partially ordered by letting α ≤ β if β−α is a nonnegative linear combination of the elements of Φ^{+}. An antichain in Φ^{+} is a subset of Φ^{+} consisting of pairwise incomparable elements.

Given an antichain A in Φ^{+} we define an equivalence relation on the set [n]^{±} ∪ {0} if Φ = B_{n} or C_{n}, and the set [n]^{±} if Φ = D_{n}, as follows. For 1 ≤ i < j ≤ n let

i ∼ j and − i ∼ −j if e_{i} − e_{j} ∈ A
i ∼ −j and − i ∼ j  if e_{i} + e_{j} ∈ A.

Moreover, in the cases Φ = B_{n} or C_{n}, let

i ∼ 0 ∼ −i if e_{i} ∈ A or 2e_{i} ∈ A, respectively.

Let π_{0}(A) be the set of equivalence classes of the transitive closure of ∼. Let π(A) be the partition of [n]^{±} obtained from π_{0}(A) by removing 0 from its class, if Φ = B_{n} or C_{n}, and π(A) = π_{0}(A) if Φ = D_{n}. Observe that π(A) is a B_{n}-partition. Moreover, in the case Φ = D_{n}, π(A) has a zero block if and only if A contains both e_{i} − e_{n} and e_{i} + e_{n} for some i < n and hence, in this event, the zero block contains {n, −n} and at least one more pair {i, −i}. Thus in general π(A) is a Φ-partition, where by a C_{n}-partition we mean a B_{n}-partition. A Φ-nonnesting partition is a Φ-partition of the form π(A) for some antichain A in Φ^{+}. We denote by NN^{Φ} the set of Φnonnesting partitions and refer the reader to [1, Section 2] and Figures 2 and 3 for the motivation behind the terminology “nonnesting”, suggested by Postnikov [1], [20, Remark 2]. By definition, NN^{Φ} is in bijection with the set of antichains in the root poset Φ^{+}.

Figure 2. A picture of the B_{6}-nonnesting partition with blocks {1, 3}, {−1, −3}, {2, 5, −6}, {−2, −5, 6} and {4, −4}.

Figure 3. A picture of the D_{5}-nonnesting partition with blocks {2, 4}, {−2, −4} and {1, 3, 5, −1, −3, −5}.

Block size enumeration. For an integer partition λ, we denote by NC_{λ}^{B}(n) the set of elements of NC^{B}(n) of type λ. Similarly, for Φ = B_{n}, C_{n} or D_{n} we denote by NN_{λ}^{Φ} the set of Φ-nonnesting partitions of type λ. The following theorem is the main result of [1].

Theorem 2.1. ([1]) Let λ be a partition of n−m with k parts, where m ≥ 0, and m_{λ} = r_{1}! · r_{2}! ⋯, where r_{i} is the number of parts of λ equal to i.

(i)

#NC_{λ}^{B}(n) = \frac{n!}{m_{λ} (n − k)!}.

(ii) The same formula holds for Φ-nonnesting partitions if Φ = B_{n} or C_{n}:

#NN_{λ}^{B_{n}} = #NN_{λ}^{C_{n}} = \frac{n!}{m_{λ} (n − k)!}.

(iii) For m ≥ 2,

#NN_{λ}^{D_{n}} = \frac{(n − 1)!}{m_{λ} (n − k − 1)!}.

3. Noncrossing partitions of type D

In this section we define our type D analogue of the noncrossing partition lattice NC^{A}(n) and prove Theorem 1.1. Let us label the vertices of a regular (2n − 2)-gon as 1, 2, …, n − 1, −1, −2, …, −(n − 1) clockwise, in this order, and label its centroid with both n and −n. Given a D_{n}-partition π and a block B of π, let ρ(B) denote the convex hull of the set of points labeled with the elements of B. Two distinct blocks B and B′ of π are said to cross if ρ(B) and ρ(B′) do not coincide and one of them contains a point of the other in its relative interior. Observe that the case ρ(B) = ρ(B′), which we have allowed, can occur only when B and B′ are the singletons {n} and {−n}, and that if π has a zero block B then B and the block containing n cross unless {n, −n} ⊆ B.

Figure 4. Two elements of NC^{D}(n) for n = 7 with blocks

(a) {3, 4, 5, 6}, {−3, −4, −5, −6}, {1, 2, 7, −1, −2, −7} and (b) {1, 4, 7}, {−1, −4, −7}, {2, 3}, {−2, −3}, {5, 6}, {−5, −6}.

The poset NC^{D}(n) is defined as the subposet of Π^{D}(n) consisting of those D_{n}-partitions π with the property that no two blocks of π cross. Figure 4 shows two elements of NC^{D}(n) for n = 7, one with a zero block and one with no zero block. Figure 5 shows the Hasse diagram of NC^{D}(n) for n = 3.

Figure 5. The lattice NC^{D}(n) for n = 3.

Proposition 3.1. The poset NC^{D}(n) is a graded lattice of rank n in which the corank of π is equal to the number of pairs {B, −B} of nonzero blocks of π.

Proof. Since NC^{D}(n) is finite with a maximum and minimum element, to prove that it is a lattice it suffices to show that meets in NC^{D}(n) exist. Indeed, given elements x, y of NC^{D}(n), one can check that the meet z of x and y in Π^{D}(n) is an element of NC^{D}(n) and hence z is also the meet of x and y in NC^{D}(n).

As was the case for NC^{B}(n) [20, Proposition 2], the rest of the proposition follows from the observation that given any two elements π_{1} ≤ π_{2} of NC^{D}(n), there exists a maximal chain in the interval [π_{1}, π_{2}] of Π^{D}(n) which passes only through elements of NC^{D}(n), so that the grading of NC^{D}(n) is inherited from that of Π^{D}(n). □

To prove Theorem 1.1 we need to describe the covering relations in the posets T^{D_{n}} and NC^{D}(n). In the case of T^{D_{n}}, the result of multiplying any element of D_{n} with a reflection ((i, j)) is described explicitly in [12, Example 3.6]. From the computations given there we can conclude that y covers x in T^{D_{n}} if and only if x can be obtained from y by replacing one or two balanced cycles of y or one paired cycle of y with one or more cycles as follows:

(2)  \begin{matrix}[i_{1}, i_{2}, …, i_{k}] ⟶ [i_{1}, …, i_{j}] ((i_{j+1}, …, i_{k})) \\ ((i_{1}, i_{2}, …, i_{k})) ⟶ ((i_{1}, …, i_{j})) ((i_{j+1}, …, i_{k})) \\ [i_{1}, …, i_{j}] [i_{j+1}, …, i_{k}] ⟶ ((i_{1}, i_{2} …, i_{k})). \end{matrix}

In the case of NC^{D}(n), it follows directly from the definition that y covers x in NC^{D}(n) if and only if x can be obtained from y by:

(i) splitting the zero block of y into the zero block of x and a pair {B, −B} of nonzero blocks,

(ii) splitting a pair of nonzero blocks {B, −B} of y into two such pairs

of x, or (iii) splitting the zero block of y into one pair {B, −B} of nonzero blocks

of x (so that one of B, −B contains n and the other contains −n).

Proof of Theorem 1.1. For x ∈ NC^{D_{n}} let f(x) denote the partition of [n]^{±} whose nonzero blocks are formed by the paired cycles of x, and whose zero block is the union of the elements of all balanced cycles of x, if such exist. We first observe that f(x) ∈ NC^{D}(n). Indeed, this is clear if x is the top element γ = [1, 2, …, n − 1] [n] of NC^{D_{n}}. If not then x is covered by some element y of NC^{D_{n}} and we may assume, by induction on the corank of x, that y has either zero or two balanced cycles, one of which must be [n] in the latter case, and that f(y) ∈ NC^{D}(n). Since x can be obtained from y by one of the moves in the list (2), it follows with a case-by-case check that x has zero or two balanced cycles as well, one of which must be [n] in the latter case, and that f(x) ∈ NC^{D}(n). The map

f : NC^{D_{n}} → NC^{D}(n)

is thus well-defined and order-preserving, since f(x) ≤ f(y) in NC^{D}(n) follows from (2) when x is covered by y in NC^{D_{n}}.

To define the inverse map, for x ∈ NC^{D}(n) let g(x) be the element of NC^{D_{n}}

• whose paired cycles are formed by the nonzero blocks of x, each ordered with respect to the cyclic order

−1, −2, …, −n, 1, 2, …, n, −1

and

• whose balanced cycles are [n] and the cycle formed by the entries of the zero block of x other than n and −n, ordered in the same way, if the zero block is present in x.

We claim that g(x) ∈ NC^{D_{n}}. This is clear if x is the top element of NC^{D}(n). If not let y be any element of NC^{D}(n) which covers x. We may assume, by induction on the corank of x, that g(y) ∈ NC^{D_{n}}, in other words that g(y) ≤ γ holds in T^{D_{n}}. It follows from the possible types of covering relations in the posets NC^{D}(n) and T^{D_{n}} that g(y) covers g(x) in T^{D_{n}}. This implies that g(x) ≤ γ holds in T^{D_{n}} or, equivalently, that g(x) ∈ NC^{D_{n}}. Thus the map

g : NC^{D}(n) → NC^{D_{n}}

is well-defined and order preserving, since g(x) ≤ g(y) in NC^{D_{n}} follows from (2) when x is covered by y in NC^{D}(n). Since f and g are clearly inverses of each other, they are poset isomorphisms. □

4. The zeta polynomial and chain enumeration

In this section we use bijective methods similar to those employed in [13, 20] for NC^{A}(n) and NC^{B}(n) to prove Theorem 1.2. We first recall a few constructions from [20, Section 3]. Setting

P_{n}^{B} := {(L, R) : L, R ⊆ [n], #L = #R}

then a map τ^{B} : P_{n}^{B} → NC^{B}(n) is constructed in [20, Section 3] as follows. Given x = (L, R) ∈ P_{n}^{B}, place a left parenthesis before each occurrence of i and −i in the infinite cyclic sequence

(3)  … − 1, −2, …, −n, 1, 2, …, n, −1, −2, …

for i ∈ L and a right parenthesis after each occurrence of i and −i for i ∈ R. Let the strings of integers inside the lowest level matching pairs of parentheses form blocks of τ^{B}(x). Remove these lowest level parentheses from (3) and the integers they enclose and continue similarly with the remaining parenthesization until all parentheses have been removed. The remaining integers, if any, form the zero block of τ^{B}(x). We have the following proposition.

Proposition 4.1. ([20, Proposition 6]) The map τ^{B} is a bijection from the set P_{n}^{B} to NC^{B}(n). Moreover, for any pair x = (L, R) ∈ P_{n}^{B} the number of pairs {B, −B} of nonzero blocks of τ^{B}(x) is equal to #R.

To extend the previous proposition to the type D case, let

P_{n}^{D} = P_{n−1}^{B} ∪ {(L, R, ε) : L, R ⊆ [n − 1], #R = #L + 1, ε = ±1} .

For x ∈ P_{n}^{D} we define a partition π = τ^{D}(x) ∈ Π^{D}(n) as follows. If x ∈ P_{n−1}^{B} then π is the partition obtained from τ^{B}(x) by adding n and −n to the zero block of τ^{B}(x), if such a block exists, and by adding the singletons {n} and {−n} to τ^{B}(x) otherwise. Suppose that x is not in P_{n−1}^{B}, say x = (L, R, ε). We parenthesize the infinite cyclic sequence

(4)  … − 1, −2, …, −(n − 1), 1, 2, …, n − 1, −1, −2, …

as in the type B case and form blocks of π with the same procedure, until a right parenthesis remains after each occurrence of i and −i for a unique i ∈ [n − 1]. Then let B and −B be blocks of π, where B consists of the integers in {−i−1, …, −n+1, 1, 2, …, i} which have not been removed from the infinite sequence together with n or −n, if ε = 1 or ε = −1, respectively.

For instance, if n = 9, L = {2, 5, 6}, R = {1, 3, 7, 8} and ε = −1, then π has blocks {2, 3}, {5, 8}, {6, 7}, {1, −4, −9} and their negatives.

It is clear from the previous construction that π ∈ NC^{D}(n), so we have a well-defined map τ^{D} : P_{n}^{D} → NC^{D}(n).

Proposition 4.2. The map τ^{D} is a bijection from the set P_{n}^{D} to NC^{D}(n). Moreover, for any x ∈ P_{n}^{D} the number of pairs {B, −B} of nonzero blocks of τ^{D}(x) is equal to

#R,  if x ∈ P_{n−1}^{B} and τ^{B}(x) has a zero block
#R + 1, if x ∈ P_{n−1}^{B} and τ^{B}(x) has no zero block
#R,  if x ∉ P_{n−1}^{B}.

Proof. The inverse of τ^{D} can be defined as in the proof of [20, Proposition 6] for the map τ^{B}. More precisely, given π ∈ NC^{D}(n), find a nonzero block B of π such that the elements of B\{n, −n} form a nonempty, consecutive string of integers in the sequence (4). If B does not contain n or −n then place the absolute values of the first and last element of B, with respect to (4), in L and R, respectively. If it does then place the absolute value i of the last element of B\{n, −n}, with respect to (4), in R and let ε = 1 or ε = −1 if n or −n is in the same block as i, respectively. Remove the elements of B and −B from π and (4) and continue similarly until the zero block, or the singletons {n} and {−n} or no block of π remains. We leave it to the reader to check that this map is indeed the inverse of τ^{D}. The second statement is obvious. □

It is shown in [20, Proposition 7] that the bijection τ^{B} of Proposition 4.1 extends to a bijection from the set

P_{n,m}^{B} = {(L, R_{1}, …, R_{m−1}) : L, R_{j} ⊆ [n], ∑_{j=1}^{m−1} #R_{j} = #L}

to the set of multi-chains π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{m−1} in NC^{B}(n). This bijection is defined as follows. Given (L, R_{1}, …, R_{m−1}) ∈ P_{n,m}^{B}, place a left parenthesis before each occurrence of i and −i in the infinite cyclic sequence (3) for i ∈ L and a right parenthesis labeled )^{j} after each occurrence of i and −i for i ∈ R_{j}. Observe that more than one right parentheses with different labels may have been placed after some integers in (3). In this case order these right parentheses as

)^{j_{1}} )^{j_{2}} ⋯)^{j_{t}}

where j_{1} < j_{2} < ⋯ < j_{t}. Read this parenthesization as in the case of the map τ^{B} to obtain π_{1} ∈ NC^{B}(n). Next, remove from the parenthesization all right parentheses labeled )^{1} and their matching left parentheses to obtain π_{2} ∈ NC^{B}(n), and continue the process until all parentheses have been removed to obtain the multi-chain π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{m−1}.

The type D analogue of this construction is given in the following proposition. To state it we introduce the following notation. Think of a multi-chain π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{m−1} in Π^{B}(n) as a multi-chain from ˆ0 to ˆ1 which has m steps, in other words set π_{0} := ˆ0 and π_{m} := ˆ1. The rank jump vector for such a multi-chain c is the composition s = (s_{1}, …, s_{m}) of the number n (denoted s ⊧ n) defined by s_{i} := r(π_{i}) − r(π_{i−1}). There is a unique step i at which a zero block is first created, meaning that π_{i−1} has no zero block but π_{i} does. Define ind(c) to be this index i.

Proposition 4.3. The bijection τ^{D} extends to a bijection from the union P_{n,m}^{D} of P_{n−1,m}^{B} with the set

{(L, R_{1}, …, R_{m−1}, ε) : L, R_{j} ⊆ [n − 1], ∑_{j=1}^{m−1} #R_{j} = #L + 1, ε = ±1}

to the set of multi-chains π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{m−1} in NC^{D}(n). Moreover, for x ∈ P_{n,m}^{D} one has

• if x ∉ P_{n−1,m}^{B} and x = (L, R_{1}, …, R_{m−1}, ε) then the multi-chain in NC^{D}(n) corresponding to x has rank jump vector

s = (n − 1 − #L, #R_{1}, …, #R_{m−1}),

• if x ∈ P_{n−1,m}^{B} and the multi-chain c in NC^{B}(n − 1) corresponding to x under the generalized map τ^{B} has rank jump vector s = (s_{1}, …, s_{m}) and ind(c) = i, then the multi-chain in NC^{D}(n) corresponding to x has rank jump vector

(s_{1}, …, s_{i−1}, s_{i} + 1, s_{i+1}, …, s_{m}).

Proof. Given x ∈ P_{n,m}^{D} we construct a multi-chain π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{m−1} in NC^{D}(n) as follows. If x ∈ P_{n−1,m}^{B} let π′_{1} ≤ π′_{2} ≤ ⋯ ≤ π′_{m−1} be the multi-chain in NC^{B}(n − 1) corresponding to x under the bijection of [20, Proposition 7]. Let π_{i} be the partition obtained from π′_{i} by adding n and −n to the zero block of π′_{i} if such a block exists, and by adding the singletons {n} and {−n} to π′_{i} otherwise. It is then clear that π_{i} ∈ NC^{D}(n) and that π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{m−1} is a multi-chain in NC^{D}(n). Suppose now that x is not in P_{n−1,m}^{B}, say x = (L, R_{1}, …, R_{m−1}, ε). Place a left parenthesis before each occurrence of i and −i in the infinite cyclic sequence (4) for i ∈ L and a right parenthesis labeled )^{j} after each occurrence of i and −i for i ∈ R_{j} using the same rules as in the type B case described earlier for placing multiple right parentheses. Read this parenthesization as in the case of the map τ^{D} to obtain π_{1} ∈ NC^{D}(n). Observe that the singletons {n} and {−n} may be blocks of π_{1} if m − 1 ≥ 2. Next, remove from the parenthesization all right parentheses labeled )^{1} and their matching left parentheses, if any, to obtain π_{2} ∈ NC^{D}(n) and continue the process until all parentheses have been removed. This results in a multi-chain π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{m−1} in NC^{D}(n) in which n belongs to a nonsingleton, nonzero block of π_{j} for at least one index j.

To define the inverse of this map, let π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{m−1} be a multichain in NC^{D}(n). Parenthesize the sequence (4) by applying the inverse of τ^{D} to π_{m−1} and label all right parentheses by )^{m−1}. Repeat the process with π_{m−2} and label all right parentheses by )^{m−2}, but include neither the new pairs of parentheses that would produce more than one left parenthesis before the occurrence of a single integer in (4), nor a new unmatched right parenthesis, if there exists one already. Continue similarly with the remaining elements of the multi-chain to get an element of P_{n,m}^{D}. We leave it again to the reader to check that this map is well-defined and that the two maps are indeed inverses of each other. The “moreover” statement is obvious from the construction. □

In [20, Proposition 7], the bijection from P_{n,m}^{B} to multi-chains in NC^{B}(n) was used to deduce that there are \binom{n}{s_{1}} ⋯ \binom{n}{s_{m}} chains in NC^{B}(n) with rank jump vector s = (s_{1}, …, s_{m}). In order to perform the analogous chain enumeration for NC^{D}(n), we will need the following refinement of this type B result, keeping track of the extra statistic ind(c).

Lemma 4.4. Let s = (s_{1}, …, s_{m}) ⊧ n. Then among the \binom{n}{s_{1}} ⋯ \binom{n}{s_{m}} chains c in NC^{B}(n) having rank jump vector s, the fraction of those having ind(c) = i is equal to \frac{s_{i}}{n}.

Unlike our other enumerative results, our proof of Lemma 4.4 is not bijective. For this reason, we have relegated it to the Appendix.

Proof of Theorem 1.2. In view of Theorem 1.1, it suffices to prove the theorem for the poset NC^{D}(n) instead.

(i) Clearly, the set P_{n}^{D} has

\binom{2n − 2}{n − 1} + 2\binom{2n − 2}{n} = \binom{2n}{n} − \binom{2n − 2}{n − 1}

elements. Hence the statement on the total number of elements of NC^{D}(n) follows from the first statement in Proposition 4.2. By an easy computation, the statement on the number of elements of rank k is equivalent to the case m = 2 in (ii).

(ii) This follows from from Proposition 4.3 and Lemma 4.4. The summand 2\binom{n−1}{s_{1}} ⋯ \binom{n−1}{s_{m}} counts the chains coming from x ∈ P_{n,m}^{D} − P_{n−1,m}^{B}. Within the summation, the i^{th} term

\begin{matrix}\binom{n − 1}{s_{1}} & ⋯ & \binom{n − 2}{s_{i} − 2} & ⋯ & \binom{n − 1}{s_{m}} \\ = \frac{s_{i} − 1}{n − 1}\binom{n − 1}{s_{1}} ⋯ \binom{n − 1}{s_{i} − 1} ⋯ \binom{n − 1}{s_{m}} \end{matrix}

counts the chains coming from x ∈ P_{n−1,m}^{B} that correspond to chains c in NC^{B}(n − 1) with rank jump vector (s_{1}, …, s_{i−1}, s_{i} − 1, s_{i+1}, …, s_{m}) and ind(c) = i.

(iii) Observe (as for P_{n,m}^{B} in the proof of [20, Proposition 7]) that the set P_{n,m}^{D} has

2\binom{m(n − 1)}{n} + \binom{m(n − 1)}{n − 1}

elements, and recall that the value Z(P, m) of the zeta polynomial for a poset P is defined to be the number of multi-chains in P of cardinality m − 1. The formula in (iii) for the zeta polynomial of NC^{D}(n) then follows from Proposition 4.3.

(iv) Both assertions follow from the zeta polynomial calculated in (iii), via [24, Proposition 3.11.1]. □

Finally we briefly discuss how Theorem 1.2 (ii) leads to a nice expression for F_{NC^{D}(n)}, where F_{P} denotes Ehrenborg’s quasisymmetric function associated with a ranked poset P; we refer the reader to [14, 26] for the definitions.

As mentioned in Section 1, the posets NC^{A}(n), NC^{B}(n) and NC^{D}(n) are self-dual by virtue of a result of Bessis [4, Section 2.3], stating that the poset NC^{W} is always self-dual. A case-free proof of a stronger statement, namely that all intervals of NC^{W} are self-dual, was outlined by McCammond [17, Section 3]. Alternatively, it is easy to check from the explicit descriptions of NC^{A}(n), NC^{B}(n) and NC^{D}(n) that any interval in one of these posets is isomorphic to a Cartesian product of posets lying in the union of these three families; see also [18], [20, Remark 1] and the Appendix. Hence their intervals are also self-dual, which implies that the posets themselves are locally rank-symmetric and their quasisymmetric functions are actually symmetric functions.

In [27], Stanley used the known explicit expressions for the numbers of chains in NC^{A}(n) and NC^{B}(n) with given rank jump vector to compute nice formulas for F_{NC^{A}(n)} and F_{NC^{B}(n)} (and to connect them with symmetric group actions on parking functions of types A and B; see also Biane [8]). He proved that

F_{NC^{A}(n)} = \frac{1}{n} [t^{n−1}] E(t)^{n}

and

F_{NC^{B}(n)} = [t^{n}] E(t)^{n},

where E(t) := ∏_{i≥1}(1 + x_{i}t), and [t^{n}] ψ(t) denotes the coefficient of t^{n} in a formal power series ψ(t) in the variable t. An equally easy computation (which we omit) shows that Theorem 1.2 (ii) is equivalent to the following proposition.

Proposition 4.5. We have

F_{NC^{D}(n)} = [t^{n}] E(t)^{n−1} (2 + ∑_{i≥1} \frac{x_{i}^{2}t^{2}}{1 + x_{i}t}) .

5. Enumeration by block sizes

For an integer partition λ let NC_{λ}^{D}(n) denote the set of elements of NC^{D}(n) with block sizes λ. To enumerate the elements of NC^{D}(n) by block sizes we define a map

τ : NC^{D}(n) → NC^{B}(n − 1)

as follows. Let π ∈ NC^{D}(n). If π has a zero block B then simply remove n and −n from B to obtain τ(π). Otherwise n and −n are in distinct blocks B and −B of π. Then either remove B and −B from π if they are singletons, or replace them with the zero block B ∪ (−B) \ {n, −n} if not, to obtain τ(π). It should be clear that τ(π) ∈ NC^{B}(n − 1).

Lemma 5.1. The map τ : NC^{D}(n) → NC^{B}(n − 1) has the following property: if x ∈ NC_{λ}^{B}(n − 1), with λ ⊢ n − m − 1, then the set τ^{−1}(x) consists of 2m + 1 elements. Moreover, 2m of these have type λ ⊎ {m + 1} and the remaining element has type

\begin{cases}λ ⊎ \{1\}, & if m = 0 \\ λ, & if m ≥ 1. \end{cases}

Proof. If x ∈ NC_{λ}^{B}(n − 1) has no zero block then τ^{−1}(x) consists of a single element π, obtained from x by adding the singletons {n} and {−n}. Suppose that x has a zero block B of size 2m. A partition in τ^{−1}(x) is obtained by either adding n, −n to the zero block B, or by splitting B in two parts C and −C and replacing B with the pair of blocks C ∪ {n} and −C ∪ {−n}. There are 2m ways to do the latter so that the resulting partition is in NC^{D}(n). □

Corollary 5.2. If λ is a partition of n − m, where m ≥ 0, then #NC_{λ}^{D}(n) is given by the formula in Theorem 1.3.

Proof. Lemma 5.1 implies that

\begin{matrix}#NC_{λ}^{D}(n) & = \\ \{ & \begin{matrix}#NC_{λ}^{B}(n − 1), & if m ≥ 2 \\ #NC_{λ\1}^{B}(n − 1) + ∑_{p≥2} (2p − 2) #NC_{λ\p}^{B}(n − 1), & if m = 0 \end{matrix} \end{matrix}

and the result follows from Theorem 2.1 (i). Note that, in the above formula, we interpret NC_{λ\p}^{B}(n − 1) as empty for any integer p ≥ 1 that does not appear as a part of λ. □

In the remainder of this section we show that nonnesting partitions of type D have the same distribution by block sizes as noncrossing partitions of the same type.

Assume that λ ⊢ n, so that NN_{λ}^{B_{n}} ⊆ NN_{λ}^{D_{n}}, and observe that the inclusion is strict for n ≥ 3 since {e_{i} + e_{n}, e_{j} − e_{n}} is an antichain in D_{n}^{+} for i < j < n but not in B_{n}^{+}. Let π ∈ NN_{λ}^{D_{n}}. Since π does not have a zero block, n and −n belong to distinct blocks B and −B of π, respectively. Let π′ denote the partition obtained from π by exchanging n and −n in the blocks B and −B and let

σ : NN_{λ}^{D_{n}} → NN_{λ}^{B_{n}}

be defined by

σ(π) = \begin{cases}π, & if π ∈ NN^{B_{n}} \\ π′, & otherwise. \end{cases}

One can check directly from the definitions that σ is well-defined. Let T_{λ}(n) be the set of partitions π ∈ NN_{λ}^{B_{n}} such that if B is the block of π containing n then B \ {n} contains both positive and negative elements, and T_{λ}^{+}(n), T_{λ}^{−}(n) be the sets of those π ∈ NN_{λ}^{B_{n}} for which B \ {n}, if nonempty, contains only positive elements and only negative elements, respectively.

Lemma 5.3. Let λ ⊢ n.

(i) The map σ : NN_{λ}^{D_{n}} → NN_{λ}^{B_{n}} induces a bijection between NN_{λ}^{D_{n}} \ NN_{λ}^{B_{n}} and T_{λ}(n).

(ii) We have

#T_{λ}^{+}(n) = #T_{λ}^{−}(n) = ∑_{p≥1} #NN_{λ\p}^{B_{n−1}}

and

#(T_{λ}^{+}(n) ∩ T_{λ}^{−}(n)) = #NN_{λ\1}^{B_{n−1}}.

Proof. (i) If π ∈ NN_{λ}^{D_{n}}\ NN_{λ}^{B_{n}} then there exist integers i < j < n such that j and n are in a block B of π while i and −n are in a different block, which must be −B. Thus {i, −j, −n} is contained in a block of π and hence {i, −j, n} is contained in a block of σ(π). This implies that σ(π) ∈ T_{λ}(n), so that the map σ : NN_{λ}^{D_{n}}\ NN_{λ}^{B_{n}} → T_{λ}(n) is well-defined. The inverse map switches again n and −n in a partition in T_{λ}(n) and is checked to be well-defined by reversing the previous argument.

(ii) The first two equalities follow from the fact that either of T_{λ}^{+}(n) or T_{λ}^{−}(n) is in bijection with the set of B_{n−1}-nonnesting partitions whose type is obtained from λ by removing one of its parts, where the bijection removes the blocks B and −B containing n and −n of an element in T_{λ}^{+}(n) or T_{λ}^{−}(n), if these blocks are singletons, or replaces them with the zero block B ∪ (−B)\{n, −n}, if not. The last equality is obvious. □

Corollary 5.4. If λ is as in Corollary 5.2 then #NN_{λ}^{D_{n}} = #NC_{λ}^{D_{n}}, that is, #NN_{λ}^{D_{n}} is given by the formula of Theorem 1.3.

Proof. For m ≥ 2 the statement is the content of Theorem 2.1 (iii). Suppose that m = 0, i.e. λ ⊢ n. Lemma 5.3 (i) implies that

#NN_{λ}^{D_{n}} = #NN_{λ}^{B_{n}} + #T_{λ}(n).

Since T_{λ}(n) = NN_{λ}^{B_{n}} \ (T_{λ}^{+}(n) ∪ T_{λ}^{−}(n)), part (ii) of the same lemma gives

#T_{λ}(n) = #NN_{λ}^{B_{n}} − #NN_{λ\1}^{B_{n−1}} − 2 ∑_{p≥2} #NN_{λ\p}^{B_{n−1}}

and the result follows from Theorem 2.1 (ii). □

The next corollary also follows from the main result of [3] and the computations in the type D case carried out there in Section 5.

Corollary 5.5. ([3, Section 5]) The number of elements of NN^{D_{n}} with k pairs {B, −B} of nonzero blocks is equal to

\binom{n}{k}^{2} − \frac{n}{n − 1}\binom{n − 1}{k}\binom{n − 1}{k − 1}.

Proof. This follows from Corollary 5.4 and Theorem 1.2 (i). □

6. Block sizes and root systems

The goal of this section is to generalize the results of [1] and Theorem 1.3 on the classical root systems to an arbitrary (finite, crystallographic) root system (Theorem 6.3). To this end we begin by recalling some facts about noncrossing and nonnesting partitions for arbitrary finite Coxeter groups and root systems.

For a finite Coxeter group (W, S), acting with its natural reflection representation on a Euclidean space V, we denote by Π^{W} the poset of all subspaces of V which are intersections of reflecting hyperplanes of W, ordered by reverse inclusion. Thus Π^{W} is a graded (geometric) lattice of rank # S which is isomorphic to the lattice Π(n), Π^{B}(n) or Π^{D}(n), defined in the first two sections, when W has type A_{n−1}, B_{n} or D_{n}, respectively.

There is a natural embedding of the lattice of noncrossing partitions NC^{W} into Π^{W}. Recall from Section 1 that NC^{W} is defined to be the interval [1, γ] in a certain partial order T^{W} on the group W, where γ is any Coxeter element of W. It follows from results of Brady and Watt (see [4, Proposition 1.6.4]) that the map

\begin{aligned}NC^{W} & → Π^{W} \\ w & ↦ V^{w} & := \{v ∈ V : w(v) = v\} \end{aligned}

is a rank and order-preserving embedding.

Now assume that W is the finite Weyl group associated to a crystallographic root system Φ. Let Φ^{+} be a choice of positive roots, equipped with the standard root order, and Π be the corresponding set of simple roots. Let A^{Φ} be the collection of all antichains in Φ^{+}, meaning subsets of pairwise incomparable elements. It turns out that, like NC^{W}, the set A^{Φ} has a natural embedding into Π^{W}, endowing it with a poset structure. The crucial fact needed is a recent result of Sommers [23].

Theorem 6.1. ([23, page 1]) Given an antichain A of positive roots, there exists w ∈ W such that w(A) ⊆ Π.

Corollary 6.2. If Φ is a crystallographic root system with Weyl group W then the map

\begin{matrix}A^{Φ} & → Π^{W} \\ A & ↦ ⋂_{α∈A} α^{⊥} \end{matrix}

is an injection, sending A to an element of rank #A.

Proof. The image of A has rank #A because Theorem 6.1 implies that any antichain in A^{Φ} is linearly independent (since so is Π). That the map is injective will follow from a stronger assertion about the interaction between the linear independence and convexity structure of Φ^{+}. Given B ⊆ Φ^{+}, let \overline{B} denote the matroid closure of B, meaning the subset of vectors in Φ^{+} lying in the linear span of B. Let ext(B) denote the set of extreme vectors within the convex cone spanned by B. We then claim that for an antichain A in Φ^{+},

A = ext(\overline{A}).

This will show that the map is injective, since one has the alternate characterization of \overline{A} as

\overline{A} = \{β ∈ Φ^{+} : ⋂_{α∈A} α^{⊥} ⊆ β^{⊥}\} .

To prove the claim note that, since A is linearly independent, ext(\overline{A}) has at least as many element as A. Consequently it suffices to show the inclusion ext(\overline{A}) ⊆ A. To this end, given β ∈ ext(\overline{A}), express β (uniquely) as

(5)  β = ∑_{α∈A} c_{α}α.

Since β and all elements of A are positive roots, at least one of the coefficients c_{α} must be positive. Using Theorem 6.1 again, one can find w ∈ W so that w(A) ⊂ Π. As w(β) lies in Φ, it has a unique expression in terms of simple roots with all coefficients of the same sign. Hence the expression

w(β) = ∑_{α∈A} c_{α}w(α),

obtained by applying w to (5), forces all of the other coefficients c_{α} to be nonnegative. Therefore (5) shows that β lies in the convex cone spanned by A. Since β is an extreme vector of the larger cone spanned by \overline{A}, it is extreme in this smaller cone, so it must lie in A. □

We require a notion that generalizes the “block sizes” of a type A, B or D partition to an arbitrary intersection subspace in Π^{W}. This is supplied by the orbit map, sending a subspace to its W -orbit:

\begin{aligned}Π^{W} & → & Π^{W} / W \\ U & ↦ & W · U & := \{w(U) : w ∈ W \}. \end{aligned}

We can now state the main result of this section.

Theorem 6.3. Let W be the Weyl group of a crystallographic root system Φ and consider the two composite maps

\begin{matrix}f : NC^{W} ↪ & Π^{W} → Π^{W} /W, \\ g : A^{Φ} ↪ & Π^{W} → Π^{W} /W. \end{matrix}

Then for each W -orbit x ∈ Π^{W} /W we have

# f^{−1}(x) = # g^{−1}(x).

Proof. The general statement follows from the corresponding statement for irreducible root systems, so one may proceed case-by-case via the classification.

For types A, B and C the statement follows from the results of [1] and the fact that the W -orbits of Π^{W} are precisely the sets of intersection subspaces whose corresponding type A or B partition has given block sizes. In the type D case a slight complication arises due to the fact that the W -orbit of an intersection subspace is not always determined by the nonzero block sizes λ of its associated D_{n}-partition. In fact this occurs exactly when λ is a partition of n having only even parts (so that, in particular, n must be even). In this case the set of intersection subspaces in Π^{W} whose corresponding D_{n}- partitions have block sizes λ decomposes further into exactly two W -orbits, determined by one extra (parity) piece of data: pick arbitrarily one block B out of each pair {B, −B} of blocks in the partition and compute the parity (even or odd) of the total number of negative elements in the union of these blocks. We claim, however, that the preimages under either f or g of two such parity orbits have the same number of elements, so that the result follows from Corollaries 5.2 and 5.4. To check the claim simply observe that, for a partition λ of n with even parts, the swap of n and −n gives rise to fixed-point free involutions on both NC_{λ}^{D}(n) and NN_{λ}^{D_{n}} which switch parity. This is obvious in the case of NC_{λ}^{D}(n) and should be clear from the discussion preceding Lemma 5.3 in the case of NN_{λ}^{D_{n}}.

The exceptional types E_{6}, E_{7}, E_{8}, F_{4}, G_{2} have been checked one by one with computer calculations, using software in Mathematica available from the second author. □

7. Remarks

1. It would be interesting to find a conceptual, case-free proof of Theorem 6.3.

2. The set of maximal chains in the poset NC^{W} is in bijection with the set of factorizations of shortest possible length, henceforth called minimal factorizations, of a Coxeter element of W into reflections. Hence Theorem 1.2 (iv) implies the following statement.

Corollary 7.1. The number of minimal factorizations of a Coxeter element of the group W^{D_{n}} into reflections is equal to 2(n − 1)^{n}.

A direct proof of this fact, analogous to the proofs of the corresponding statements by Biane [8] for the symmetric and hyperoctahedral group, is possible. More precisely, let γ = [1, 2, …, n − 1] [n] be as in Section 2 and M_{n} be the set of tuples (t_{1}, t_{2}, …, t_{n}) of reflections in W^{D_{n}} such that γ = t_{1}t_{2} ⋯ t_{n}. Let us label the reflections in W^{D_{n}} as follows:

ℓ(t) = \begin{cases}i, & if t = ((i, ±n)) and 1 ≤ i ≤ n − 1 \\ i, & if t = ((i, j)) and 1 ≤ i < j ≤ n − 1 \\ j, & if t = ((i, −j)) and 1 ≤ i < j ≤ n − 1. \end{cases}

It has been shown by the first author that the map which assigns to any element (t_{1}, t_{2}, …, t_{n}) of M_{n} the sequence of labels (ℓ(t_{1}), ℓ(t_{2}), …, ℓ(t_{n})) is a two to one map from the set M_{n} to [n − 1]^{n}.

3. It is natural to conjecture that the poset NC^{D}(n) is shellable. However, the EL-labellings given by Edelman and Björner [10] in the case of NC^{A}(n) and Reiner [20] in the case of NC^{B}(n) do not seem to extend to that of NC^{D}(n).

4. It has been shown by Eleni Tzanaki (private communication) that the poset NC^{D}(n) has a symmetric chain decomposition analogous to those of NC^{A}(n) [22, Theorem 2] and NC^{B}(n) [20, Theorem 13].

Appendix: proof of Lemma 4.4

We recall the statement of the lemma.

Lemma 4.4. Let s = (s_{1}, …, s_{m}) ⊧ n. Then among the \binom{n}{s_{1}} ⋯ \binom{n}{s_{m}} chains c in NC^{B}(n) having rank jump vector s, the fraction of those having ind(c) = i is equal to \frac{s_{i}}{n}.

The proof will utilize the type B generalization [20, Theorem 16] of a result of Nica and Speicher [18] on incidence algebras, which we recall here.

Let R be any ring with unit and P be a poset. The (R-valued) incidence algebra for P consists of R-valued functions f on the set of intervals [a, b] of P, with pointwise addition and multiplication by convolution:

(f ∗ g)[a, c] := ∑_{b∈P: a≤b≤c} f[a, b] g[b, c].

In [20, Remark 1] a certain multiplicative subgroup I_{mult}^{0}(NC^{B}; R) of the union of all R-valued incidence algebras of type A and B noncrossing partition lattices was defined. As observed in [18, 20], every interval [a, b] in NC^{A}(n) or NC^{B}(n) has a canonical isomorphism to a Cartesian product

NC^{B}(n_{0}) × NC^{A}(n_{1}) × NC^{A}(n_{2}) × ⋯ × NC^{A}(n_{r})

for some integers n_{0}, n_{1}, …, n_{r}, where the factor NC^{B}(n_{0}) need not be present. The multiplicative subgroup I_{mult}^{0}(NC^{B}; R) consists of those elements f in the incidence algebra which take the value 1 on NC^{A}(1) and which are multiplicative, in the sense that

f[a, b] = f(NC^{B}(n_{0})) ∏_{i=1}^{r} f(NC^{A}(n_{i})).

Define a map

\begin{matrix}I_{mult}^{0}(NC^{B}; R) & →^{F} & R[[t, u]]/(u^{2}) & (≅ R[u]/(u^{2})[[t]]) \\ f & ↦ & F(f) := ^{\frac{ϕ_{f}^{⟨−1⟩}}{t}} , \end{matrix}

where

(6)  ϕ_{f} := ∑_{n≥1} f(NC^{A}(n))t^{n} + f(NC^{B}(n))t^{n}u

and ϕ_{f}^{⟨−1⟩} denotes the compositional inverse of ϕ_{f} with respect to the variable t. This map gives an isomorphism of I_{mult}^{0}(NC^{B}; R) onto the multiplicative subgroup of power series in R[[t, u]]/(u^{2}) whose coefficient of t^{0} equals 1 [20, Theorem 16].

Proof of Lemma 4.4. We will perform generating function calculations in these rings, choosing

R = ℤ[[x_{1}, x_{2}, …, y_{1}, y_{2}, …]].

Define f ∈ I_{mult}^{0}(NC^{B}; R) by

(7)

f(NC^{A}(n)) := ∑_{s⊧n−1} ∑_{chains in NC^{A}(n) with rank jump vector s} x^{s}

f(NC^{B}(n)) := ∑_{s⊧n} ∑_{chains c in NC^{B}(n) with rank jump vector s} x^{s} \frac{y_{ind(c)}}{x_{ind(c)}} ,

where x^{s} := x_{1}^{s_{1}} ⋯ x_{m}^{s_{m}}. A little thought shows that f coincides with the convolution f = f_{1} ∗ f_{2} ∗ ⋯, where

\begin{aligned}f_{i}(NC^{A}(n)) & := x_{i}^{n−1} \\ f_{i}(NC^{B}(n)) & := x_{i}^{n−1}y_{i}. \end{aligned}

¿From this one calculates that

ϕ_{f_{i}} = ∑_{n≥1} x_{i}^{n−1}t^{n} + x_{i}^{n−1}y_{i}t^{n}u = \frac{t(1 + y_{i}u)}{1 − tx_{i}}

and hence by computing the compositional inverse,

\begin{aligned}ϕ_{f_{i}}^{⟨−1⟩} & = \frac{t}{1 + tx_{i} + uy_{i}} , \\ F(f_{i}) & = \frac{ϕ_{f_{i}}^{⟨−1⟩}}{t} = \frac{1}{1 + tx_{i} + uy_{i}} . \end{aligned}

Therefore

\begin{aligned}F(f) & = ∏_{i≥1} F(f_{i}) & = ∏_{i≥1} \frac{1}{1+tx_{i}+uy_{i}} , \\ ϕ_{f}^{⟨−1⟩} & = tF(f) & = \frac{t}{∏_{i≥1}(1+tx_{i}+uy_{i})}. \end{aligned}

One can apply the Lagrange Inversion Formula [25, Theorem 5.4.2] to this last expression. Letting [t^{k}] ψ(t) denote the coefficient of t^{k} in any formal power series ψ(t) in a variable t, one has that

[t^{n}] ϕ_{f} = \frac{1}{n}[T^{n−1}] ∏_{i≥1}(1 + x_{i}T + y_{i}u)^{n}

= \frac{1}{n}[T^{n−1}] ∏_{i≥1} ∑_{k=0}^{n} \binom{n}{k}(x_{i}T + y_{i}u)^{k}

= \frac{1}{n}[T^{n−1}] ∏_{i≥1} ∑_{k=0}^{n} \binom{n}{k}(x_{i}^{k}T^{k} + k · x_{i}^{k−1}y_{i}T^{k−1}u)

= ∑_{s⊧n−1} \frac{1}{n}\binom{n}{s_{1}} ⋯ \binom{n}{s_{m}}x^{s} + u ∑_{s⊧n} \binom{n}{s_{1}} ⋯ \binom{n}{s_{m}} ∑_{i=1}^{m} \frac{s_{i}}{n} x^{s} \frac{y_{i}}{x_{i}} .

Comparing (6), (7) with this last expression gives the result. □

The proof of the lemma gives an alternative derivation for [13, Theorem 3.2] and, by setting y_{i} = x_{i} for all i, also one for [20, Proposition 7].

Acknowledgements. The authors thank Jon McCammond for helpful conversations, and for originally bringing the references [4, 11, 12] to their attention.

References

[1] C.A. Athanasiadis, On noncrossing and nonnesting partitions for classical reflection groups, Electron. J. Combin. 5 (1998), Research Paper 42, 16 pp (electronic).

[2] C.A. Athanasiadis, Generalized Catalan numbers, Weyl groups and arrangements of hyperplanes, Bull. London Math. Soc. 36 (2004), xx–xx.

[3] C.A. Athanasiadis, On a refinement of the generalized Catalan numbers for Weyl groups, Trans. Amer. Math. Soc. (to appear).

[4] D. Bessis, The dual braid monoid, Ann. Sci. Ecole Norm. Sup. 36 (2003), 647–683.

[5] D. Bessis and R. Corran, Non-crossing partitions of type (e, e, r), preprint 2004

(arXiv:math.GR/0403400).

[6] D. Bessis, F. Digne and J. Michel, Springer theory in braid groups and the Birman-Ko-Lee monoid, Pacific J. Math. 205 (2002), 287–309.

[7] P. Biane, Some properties of crossings and partitions, Discrete Math. 175 (1997), 41–53.

[8] P. Biane, Parking functions of types A and B, Electron. J. Combin. 9 (2002), Note 7, 5 pp (electronic).

[9] P. Biane, F. Goodman and A. Nica, Non-crossing cumulants of type B, Trans. Amer. Math. Soc. 355 (2003), 2263–2303.

[10] A. Björner, Shellable and Cohen-Macaulay partially ordered sets, Trans. Amer. Math. Soc. 260 (1980), 159–183.

[11] T. Brady, A partial order on the symmetric group and new K(π, 1)’s for the braid groups, Adv. Math. 161 (2001), 20–40.

[12] T. Brady and C. Watt, K(π, 1)’s for Artin groups of finite type, in “Proceedings of the Conference on Geometric and Combinatorial group theory, Part I (Haifa 2000)” Geom. Dedicata 94 (2002), 225–250.

[13] P.H. Edelman, Chain enumeration and noncrossing partitions. Discrete Math. 31 (1980), 171–180.

[14] R. Ehrenborg, On posets and Hopf algebras, Adv. Math. 119 (1996), 1–25.

[15] J.E. Humphreys, Reflection groups and Coxeter groups, Cambridge Studies in Advanced Mathematics 29, Cambridge University Press, Cambridge, England, 1990.

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

[17] J. McCammond, Noncrossing partitions in surprising locations, preprint, 2003, 14 pages.

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

[19] M. Picantin, Explicit presentations for the dual braid monoids, C. R. Math. Acad. Sci. Paris 334 (2002), 843–848.

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

[21] R. Simion, Noncrossing partitions, Discrete Math. 217 (2000), 367–409.

[22] R. Simion and D. Ullman, On the stucture of the lattice of non-crossing partitions, Discrete Math. 98 (1991), 193–206.

[23] E. Sommers, B-stable ideals in the nilradical of a Borel subalgebra, Canad. Math. Bull. (to appear).

[24] R.P. Stanley, Enumerative Combinatorics, vol. 1, Wadsworth & Brooks/Cole, Pacific Grove, CA, 1986; second printing, Cambridge University Press, Cambridge, 1996.

[25] R.P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge Studies in Advanced Mathematics 62, Cambridge University Press, Cambridge, 1999.

[26] R.P. Stanley, Flag-symmetric and locally rank-symmetric partially ordered sets, Electron. J. Combin. 3 (1996), Research Paper 6, 22 pp (electronic).

[27] R.P Stanley, Parking functions and noncrossing partitions, Electron. J. Combin. 4 (1997), Research Paper 20, 14 pp (electronic).

Department of Mathematics, University of Crete, 71409 Heraklion, Crete, Greece

E-mail address, C.A. Athanasiadis: caa@math.uoc.gr

School of Mathematics, University of Minnesota, Minneapolis, MN 55455, USA

E-mail address, V. Reiner: reiner@math.umn.edu