ON NONCROSSING AND NONNESTING PARTITIONS FOR CLASSICAL REFLECTION GROUPS

CHRISTOS A. ATHANASIADIS

Abstract. The number of noncrossing partitions of {1, 2, …, n} with fixed block sizes has a simple closed form, given by Kreweras, and coincides with the corresponding number for nonnesting partitions. We show that a similar statement is true for the analogues of such partitions for root systems B and C, defined recently by Reiner in the noncrossing case and Postnikov in the nonnesting case. Some of our tools come from the theory of hyperplane arrangements.

Submitted: January 30, 1998; Accepted: September 10, 1998

1. Introduction

A noncrossing partition of the set [n] = {1, 2, …, n} is a set partition π 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′. Noncrossing partitions are classical combinatorial objects with an extensive literature, see [7, 9, 11, 12, 13, 17, 18, 19, 22]. Natural analogues of noncrossing partitions for the classical reflection groups of type B, C and D were introduced by Reiner [16] and were shown to have similar enumerative and structural properties with those of the noncrossing partitions, which are associated to the reflection groups of type A.

Nonnesting partitions were recently defined by Postnikov (see [16, Remark 2]) in a uniform way for all irreducible root systems associated to Weyl groups. Let Φ be such a root system and Φ^{+} be a choice of positive roots. Define the root order on Φ^{+} by α ≤ β if α, β ∈ Φ^{+} and β − α is a linear combination of positive roots with nonnegative coefficients. A nonnesting partition on Φ is simply an antichain in the root order of Φ. Postnikov observed that the nonnesting partitions on Φ are in bijection with certain regions of an affine hyperplane arrangement related to the Coxeter arrangement associated to Φ. For Φ = A_{n−1}, nonnesting partitions are naturally in bijection with set partitions π of [n] such that if a < b < c < d and a, d are consecutive elements of a block B of π, then b, c are not both contained in a block B′ of π. This concept has reappeared in a geometric context in [3].

A number of striking similarities between noncrossing and nonnesting partitions were pointed out by Postnikov and recorded by Reiner [16, Remark 2]. For the case of the root system A_{n−1}, the number of both noncrossing and nonnesting partitions is the nth Catalan number and their distribution according to the number of blocks is the same. Moreover, it follows from Postnikov’s observation and one of the results in [1] [2, Part II] that, for Φ = B_{n}, C_{n} or D_{n}, as well as A_{n−1}, the number of nonnesting partitions on Φ coincides with that of noncrossing partitions, as computed in [16].

The present research was carried out while the author was a Hans Rademacher Instructor at the University of Pennsylvania.

In this paper we strengthen these observations by fixing the block sizes. Our motivation comes from a simple formula of Kreweras [11] for the number of noncrossing partitions of [n] of a fixed type λ, the integer partition of n whose parts are the sizes of the blocks. It is not hard to prove (see e.g. [3, §4]) that the number of nonnesting partitions of [n] of type λ is given by the same formula. We prove similar formulas for the root systems B_{n} and C_{n} which again coincide in the noncrossing and nonnesting case.

The paper is structured as follows. In Section 2 we give some more background and definitions and state our results, after we extend the notion of type λ to nonnesting partitions on B_{n}, C_{n} and D_{n}. In Section 3 we discuss the case of A_{n−1} and provide an explicit bijection between noncrossing and nonnesting partitions which preserves the type λ. In Section 4 we prove the analogue of the result of Kreweras for noncrossing partitions for the other classical reflection groups. In Section 5 we show that the number of nonnesting partitions on B_{n} and C_{n} of type λ is given by the same formula as the corresponding number of noncrossing partitions. Our arguments exploit the connections between nonnesting partitions and hyperplane arrangements and use the “finite field method” of [1] [2, Part II]. Section 6 contains some concluding remarks and related questions.

2. Background and results

Noncrossing partitions. We first recall the definition of noncrossing partitions for the classical reflection groups from [16]. In this section, Φ denotes a root system in one of the infinite families A_{n−1}, B_{n}, C_{n} and D_{n}.

Partitions of [n] are naturally in bijection with intersections of the reflecting hyperplanes x_{i} − x_{j} = 0 in ℝ^{n} of the Coxeter group of type A_{n−1} and are refered to as A_{n−1}-partitions. Φ-partitions are defined by analogy. The reflecting hyperplanes in the case of the Coxeter group of type B_{n} are

x_{i} = 0 for 1 ≤ i ≤ n,
x_{i} − x_{j} = 0 for 1 ≤ i < j ≤ n,
x_{i} + x_{j} = 0 for 1 ≤ i < j ≤ n.

(1)

The subspace of ℝ^{8}

{x ∈ ℝ^{8} : x_{1} = −x_{5} = −x_{8}, x_{2} = x_{3}, x_{6} = x_{7}, x_{4} = 0}

is a typical intersection of such hyperplanes when n = 8 which is encoded by the partition having blocks {1, −5, −8}, {−1, 5, 8}, {2, 3}, {−2, −3}, {6, 7}, {−6, −7} and {4, −4}. A B_{n}-partition is a partition π of the set {1, 2, …, n, −1, −2, …, −n} which has at most one block (called the zero block, if present) containing both i and −i for some i and is such that for any block B of π, the set −B, obtained by negating the elements of B, is also a block of π. It follows that the zero block, if present in π, is a union of pairs {i, −i}.

The same hyperplanes as in (1) are the reflecting hyperplanes in the case of C_{n} and those of the second and third kind are the ones in the case of D_{n}. Thus the notion of a C_{n}-partition coincides with that of a B_{n}-partition while a D_{n}-partition is defined as a B_{n}-partition in which the zero block does not consist of a single pair {i, −i}, if present. The partition with blocks {1, −3, 5}, {−1, 3, −5}, {4}, {−4} and {2, 6, −2, −6} is a D_{6}-partition which corresponds to the intersection of hyperplanes

{x ∈ ℝ^{6} : x_{1} = −x_{3} = x_{5}, x_{2} = x_{6}, x_{2} = −x_{6}}

in ℝ^{6}.

A Φ-partition π can be represented pictorially by placing the integers 1, 2, …, n, if Φ = A_{n−1}, and 1, 2, …, n, −1, −2, …, −n otherwise, in this order, along a line and drawing arcs above the line between i and j whenever i and j lie in the same block B of π and no other element between them does so. We call π noncrossing if no two of the arcs cross. This is equivalent to the definition given in the Introduction in the case of A_{n−1}. Note that the notions of B_{n} and C_{n} noncrossing partitions coincide. Figure 1 shows that the B_{8}-partition with blocks {1, −5, −8}, {−1, 5, 8}, {2, 3}, {−2, −3}, {6, 7}, {−6, −7} and {4, −4}, discussed earlier, is noncrossing.

Figure 1. A B_{8}-noncrossing partition

The following theorem was proved by Kreweras [11] in the case Φ = A_{n−1} and by Reiner [16] in the remaining cases.

Theorem 2.1. ([11, 16]) The number of noncrossing Φ-partitions is the nth Catalan number \frac{1}{n+1} \binom{2n}{n} if Φ = A_{n−1}, \binom{2n}{n} if Φ = B_{n} or C_{n} and \binom{2n}{n} − \binom{2(n−1)}{n−1} if Φ = D_{n}.

The type of a Φ-partition π is the integer partition λ whose parts are the sizes of the nonzero blocks of π, including one part for each pair of blocks {B, −B} if Φ = B_{n}, C_{n} or D_{n}. Thus if λ is a partition of the nonnegative integer k, then k = n if Φ = A_{n−1} and k ≤ n if Φ = B_{n}, C_{n} or D_{n}, with k ≠ n − 1 if Φ = D_{n}. The type of the partition of Figure 1 is (3, 2, 2). The number of noncrossing partitions of [n] with fixed type was given by Kreweras [11]. For any integer partition λ we let m_{λ} = r_{1}!r_{2}! ⋯, where r_{i} denotes the number of parts of λ equal to i.

Theorem 2.2. (Kreweras [11, Theorem 4]) The number of noncrossing partitions of [n] of type λ is equal to

\frac{n!}{m_{λ} (n − d + 1)!},

where d is the number of parts of λ.

Let λ be a partition of k ≤ n. Recall that there are no D_{n}-partitions of type λ if k = n − 1. The following analogue of the previous theorem will be proved in Section 4.

Theorem 2.3. The number of noncrossing B_{n}-partitions of type λ (equivalently C_{n}, or D_{n} if λ is not a partition of n − 1) is equal to

\frac{n!}{m_{λ} (n − d)!},

where d is the number of parts of λ.

Nonnesting partitions. From now and on we choose Φ and Φ^{+} explicitly as in [10, 2.10], so that positive roots are of the form e_{i}, 2e_{i} and e_{i} ± e_{j} for i < j, where the e_{i} denote standard coordinate vectors. We rely on [10] for any undefined terminology on root systems. Recall from the introduction that a nonnesting partition π on Φ is an antichain in the root order on Φ^{+}. Such a partition π determines a Φ-partition in a way that we describe next.

For Φ = A_{n−1} we have Φ^{+} = {e_{i} − e_{j}}_{1≤i<j≤n}. The A_{n−1}-partition which is associated to π is the one whose diagram contains an arc between i and j, with i < j, if and only if e_{i}−e_{j} is in π. It follows that nonnesting partitions of A_{n−1} are in bijection with partitions of [n] whose diagrams have no two arcs “nested” one within the other. Equivalently, if a < b < c < d, a, d are contained in a block B and no m with a < m < d is in B, then b, c are not both contained in a block B′. This is the alternative description given in the introduction and becomes the definition of a nonnesting permutation of a multiset [3, §2] if the blocks are labeled. Figure 2 shows the diagram of the A_{10}-partition associated to π = {e_{1} − e_{4}, e_{2} − e_{5}, e_{3} − e_{6}, e_{5} − e_{7}, e_{7} − e_{9}}.

If Φ = B_{n} we have the extra positive roots e_{i}, for 1 ≤ i ≤ n and e_{i} + e_{j}, for 1 ≤ i < j ≤ n. A diagram representing π can be drawn by placing the integers 1, 2, …, n, 0, −n, …, −2, −1, in this order, along a line and arcs between them. For i, j ∈ [n], we include arcs between i and j and between −i and −j if π contains e_{i}−e_{j}, an arc between i and −j if π contains e_{i} + e_{j} and arcs between i and 0 and between

Figure 2. A nonnesting partition of [9]

0 and −i if π contains e_{i}. The chains of successive arcs in the diagram become the blocks of a B_{n}-partition, after dropping 0, which is the partition we associate to π. This map defines a bijection between nonnesting partitions on B_{n} and B_{n}-partitions whose diagrams, in the above sense, contain no two arcs nested one within the other. We call this diagram the nonnesting diagram of π, to distinguish it from the diagram of the B_{n}-partition associated to π. Figure 3 shows the nonnesting diagram of the B_{6}-partition associated to π = {e_{4}, e_{1} − e_{3}, e_{2} − e_{5}, e_{5} + e_{6}}. The blocks are {1, 3}, {−1, −3}, {2, 5, −6}, {6, −5, −2} and {4, −4}.

Figure 3. A B_{6}-nonnesting partition

The positive roots of C_{n} are obtained from those of B_{n} by replacing e_{i} by 2e_{i}, for 1 ≤ i ≤ n. The C_{n}-partition and nonnesting diagram associated to π in this case are determined as before, except that i and −i are connected by an arc if π contains 2e_{i} and that 0 does not appear in the diagram. Again, the diagrams obtained in this way contain no two arcs nested one within the other. Figure 4 shows the nonnesting diagram of the C_{6}-partition associated to π = {2e_{5}, e_{1} − e_{4}, e_{3} − e_{5}, e_{4} − e_{6}} with blocks {1, 4, 6}, {−6, −4, −1}, {2}, {−2} and {3, 5, −5, −3}.

Figure 4. A C_{6}-nonnesting partition

The positive roots of D_{n} are those of B_{n} other than e_{i}, 1 ≤ i ≤ n. The same rules as before determine the diagram of a nonnesting partition π on D_{n}. However, nestings can occur in the diagram, e.g. if e_{i} − e_{n} and e_{i} + e_{n} are both in π for some i < n (see Figure 6). Note that these two elements are related in the root order of B_{n} and C_{n} but not of D_{n}. The chains in the diagram, which we still call the nonnesting diagram, determine the nonzero blocks of the D_{n}-partition associated to π and the zero block is formed by the connected component which contains n if a nesting {e_{i} − e_{n}, e_{i} + e_{n}} appears in π.

We will usually not distinguish between a nonnesting partition π and its associated Φ-partition or nonnesting diagram. In particular, the type of π is the type λ of the associated Φ-partition. The partition of Figure 3 has type (3, 2) and that of Figure 4 has type (3, 1).

Recall that a hyperplane arrangement A is a finite set of affine hyperplanes in ℝ^{n}. The regions of A are the connected components of the space obtained from ℝ^{n} by removing the hyperplanes of A. The Catalan arrangement associated to Φ (see [1, §5] [2, Chapter 7] [8, §3] and [21, §2] [3, §1] [15, §7] for the A_{n−1} case) consists of the hyperplanes

α · x = k for α ∈ Φ^{+} and k = −1, 0, 1.

It was observed by Postnikov (see Section 6 and [16, Remark 2]) that the nonnesting partitions on Φ are in bijection with the regions of the Φ-Catalan arrangement which lie inside the fundamental chamber of the underlying Coxeter arrangement. The next theorem follows from this observation and a special case of [1, Theorem 5.5] [2, Corollary 7.2.3] and is stated in [16, Remark 2].

Theorem 2.4. For Φ = A_{n}, B_{n}, C_{n} or D_{n}, the number of nonnesting partitions on Φ is equal to

∏_{i=1}^{n} \frac{e_{i} + h + 1}{e_{i} + 1},

where e_{1}, e_{2}, …, e_{n} are the exponents of Φ and h is its Coxeter number.

This quantity coincides with the number of noncrossing partitions on Φ given in Theorem 2.1 and is denoted by Catalan(Φ). The similarity between the enumerative properties of noncrossing and nonnesting partitions is further demonstrated by the next theorem, which follows e.g. from [3, Corollary 4.3].

Theorem 2.5. ([3]) The number of nonnesting partitions of [n] of type λ is equal to

\frac{n!}{m_{λ} (n − d + 1)!},

where d is the number of parts of λ.

In Section 3 we give an explicit bijection between noncrossing and nonnesting partitions of [n] which preserves type. The following analogue of Theorem 2.5 is proved in Section 5.

Theorem 2.6. The number of nonnesting partitions either on B_{n} or on C_{n} of type λ is equal to

\frac{n!}{m_{λ} (n − d)!},

where d is the number of parts of λ. If λ is a partition of an integer less than n − 1 then the number of nonnesting partitions on D_{n} of type λ is equal to

\frac{(n − 1)!}{m_{λ} (n − d − 1)!}.

We do not know of a uniform formula for the number of nonnesting partitions on D_{n} of type λ if λ is a partition of n.

3. The case Φ = A_{n−1}

In this section we discuss further the case Φ = A_{n−1}. We give a simple bijection between noncrossing and nonnesting partitions of [n] which preserves type and explains directly the fact that the two quantities of Theorems 2.2 and 2.5 are identical. We do not know of such a bijection for the case Φ = B_{n} or C_{n}. To be self-containt, we also include a proof of Theorems 2.2 and 2.5.

Given a partition π of [n] of type λ, let B_{1}, B_{2}, …, B_{d} be the blocks of π, numbered so that if a_{i} is the least element of B_{i} then 1 = a_{1} < a_{2} < ⋯ < a_{d}. We write a = a(π) = (a_{1}, a_{2}, …, a_{d}) and μ = μ(π) = (μ_{1}, μ_{2}, …, μ_{d}), where μ_{i} is the cardinality of B_{i}, so that μ is a permutation of λ. For the partition of Figure 2 we have a = (1, 2, 3, 8) and μ = (2, 4, 2, 1).

Theorem 3.1. Given a nonnesting partition π of [n], there is a unique noncrossing partition π′ := σ_{n}(π) such that a(π′) = a(π) and μ(π′) = μ(π). The map σ_{n} is a bijection between nonnesting and noncrossing partitions of [n] which preserves type.

Proof. Let π be nonnesting and a_{i}, μ_{i}, B_{i} for 1 ≤ i ≤ d be as before. Let C_{i} be a chain of μ_{i} − 1 successive arcs for each i. We refer to the μ_{i} endpoints of these arcs as the elements of C_{i}. To construct the diagram of π′, we place successively the chains C_{i} relative to each other as follows. Assume that we have already placed the chains C_{i} for i < j. Note that the total number μ_{1} +μ_{2} +⋯+μ_{j−1} of elements of the chains already placed is at least a_{j} − 1. We insert the leftmost element of C_{j} in position a_{j}, counting from the left, relative to the elements of C_{1}, …, C_{j−1}. There is a unique way to place the other elements of the chain to the right without forming any pair of crossing arcs. The resulting diagram determines a noncrossing partition π′ with the desired properties. The inverse of σ_{n} is defined in the same way except that, for each j, we place the elements of C_{j} to the right of the leftmost one in the unique way in which no pair of nesting arcs is formed.

Figure 5 shows the diagram of the noncrossing partition which corresponds under the bijection σ_{9} to the nonnesting partition of Figure 2. Its blocks are {1, 9}, {2, 5, 6, 7}, {3, 4} and {8}.

Figure 5. A noncrossing partition of [9]

The proof of Theorems 2.2 and 2.5 that follows was outlined in Remark 1 of [3, §5] for the nonnesting case. We will need the following version of the Cycle Lemma [6] (see also [5], the references cited there and Lemmas 3.6 and 3.7 in [23, Chapter 5]).

Lemma 3.2. ([6]) Let b_{1}, b_{2}, …, b_{m} be integers which sum to −1 and set b_{m+i} = b_{i} for 1 ≤ i ≤ m − 1. There is a unique j ∈ [m] such that the cyclic permutation b_{j}, b_{j+1}, …, b_{j+m−1} has its partial sums S_{1}, S_{2}, …, S_{m−1} nonnegative, where S_{r} = b_{j} + b_{j+1} + ⋯ + b_{j+r−1}.

Proof of Theorems 2.2 and 2.5. A labeled partition π of [n] of type λ = (λ_{1}, λ_{2}, …, λ_{d}) is a set partition of [n] of type λ whose blocks are labeled with the integers 1, 2, …, d so that the block labeled with i has cardinality λ_{i}. We show that the number of nonnesting, as well as noncrossing, labeled partitions of [n] of type λ is equal to \frac{n!}{(n−d+1)!}. This implies the results since any partition of [n] of type λ can be labeled in m_{λ} ways. For 1 ≤ i ≤ d, let j_{i} be the least element of the block of π labeled with i. It follows from the proof of Theorem 3.1 that the map π ↦ (j_{1}, j_{2}, …, j_{d}) induces a bijection between either nonnesting or noncrossing labeled partitions of type λ with sequences (j_{1}, j_{2}, …, j_{d}) of distinct elements of [n] such that for all 1 ≤ k ≤ n,

∑_{j_{r}≤ k} λ_{r} ≥ k.

Lemma 3.2, applied with m = n + 1, b_{j_{i}} = λ_{i} − 1 and b_{j} = −1 for the other values of j, implies that these sequences are in bijection with elements (j_{1}, j_{2}, …, j_{d}) + H of the quotient of the abelian group ℤ_{n+1}^{d} by the cyclic subgroup H generated by (1, 1, …, 1) for which all j_{i} are mutually distinct. Clearly, the number of such cosets is n(n − 1) ⋯ (n − d + 2).

4. Noncrossing partitions of fixed type

In this section we prove Theorem 2.3 bijectively.

Proof of Theorem 2.3. It suffices to prove the statement in the case of B_{n}. We describe a bijection between noncrossing B_{n}-partitions of type λ and pairs (S, f), where S is a subset of [n] with d elements and f is a map which assigns to each element of S a part of λ so that each part is hit by f as many times as its multiplicity in λ. The number of such pairs is

\binom{n}{d} \frac{d!}{m_{λ}} = \frac{n!}{m_{λ} (n − d)!}.

Let π be a noncrossing B_{n}-partition of type λ = (λ_{1}, …, λ_{d}). To construct (S, f), choose for each pair {B, −B} of blocks of π the leftmost element of the block which either lies entirely to the left or is nested within its negative in the diagram of π. The d elements thus chosen are the elements of S and for s ∈ S, f(s) is defined to be the cardinality of the block of π which contains s. For example, for the partition whose diagram is shown in Figure 1 we have S = {2, 5, 6}, f(2) = 2, f(5) = 3 and f(6) = 2.

To show that this correspondence is a bijection we describe the inverse. We may assume that λ is not the empty partition, i.e. d ≥ 1. We first place the integers 1, …, n, −1, …, −n, in this order, along a line. Given (S, f) as above, we call an element s of S admissible if none of the f(s) − 1 integers on the line immediately to its right are in S or −S. We claim that admissible elements exist. Indeed, for s ∈ S let g(s) − 1 be the number of integers strictly between s and the next element of S or −S to its right. Since there are exactly n integers between the smallest integer i in S and its negative −i, including i, the numbers g(s) sum to n. On the other hand, the sum of the parts f(s) of λ is at most n. Hence we have f(s) ≤ g(s) for at least one s in S, which means that s is admissible.

For each admissible element s, let s and the f(s) − 1 integers immediately to its right form a block B and let −B be another block. We now remove from the picture the blocks already constructed and continue similarly, until all elements of S are removed. The remaining elements, if any, form the zero block. This proceedure defines a noncrossing B_{n}-partition of type λ. If n = 8, S = {2, 5, 6}, f(2) = 2, f(5) = 3 and f(6) = 2 then the blocks {2, 3} and {6, 7} are constructed first, along with their negatives. The resulting partition is the one in Figure 1.

We leave it to the reader to check that the two maps are indeed inverses of each other. Note that the blocks constructed from the admissible elements of S by the second map, along with their negatives, correspond to the blocks B of π which have no other block nested within B, along with their negatives.

The argument in the previous proof refines the one given by Reiner in the proof of the following result.

Corollary 4.1. ([16, Proposition 6]) The number of noncrossing B_{n}-partitions whose type has d parts is equal to \binom{n}{d}^{2}. The total number of noncrossing B_{n}-partitions is \binom{2n}{n}.

5. Nonnesting partitions of fixed type

To prove Theorem 2.6 we need some more background from the theory of hyperplane arrangements [14] (see also Section 2). The characteristic polynomial [14, §2.3] of a hyperplane arrangement A in ℝ^{d} is defined as

χ(A, q) = ∑_{x∈L_{A}} μ(ˆ0, x) q^{dim x},

where L_{A} is the poset of all affine subspaces of ℝ^{d} which can be written as intersections of some of the hyperplanes of A, ˆ0 = ℝ^{d} is the unique minimal element of L_{A} and μ stands for its Möbius function [20, §3.7]. The characteristic polynomial will be important for us because of the following theorem of Zaslavsky.

Theorem 5.1. (Zaslavsky [24]) The number of regions into which the hyperplanes of A dissect ℝ^{d} is given by

r(A) = (−1)^{d} χ(A, −1).

Our strategy towards Theorem 2.6 is to find hyperplane arrangements whose regions are in bijection with appropriately labeled nonnesting partitions of various types. We then use the finite field method of [1] [2, Part II] to compute the characteristic polynomials and Theorem 5.1 to derive the number of regions of the arrangements. A similar proof was given in [3, §4] for Theorem 2.5.

For the rest of this section let λ = (λ_{1}, …, λ_{d}) be a partition with λ_{1} + ⋯ + λ_{d} = n − m, for some nonnegative integer m.

The case of B_{n}. A labeled nonnesting partition π on B_{n} of type λ is a nonnesting partition on B_{n} of type λ whose pairs of nonzero blocks {B, −B} are labeled with the integers 1, 2, …, d so that if {B, −B} is labeled with i then B has cardinality λ_{i}. We say that π is signed if a sign + or − is assigned to each nonzero block of π so that the sign of −B is the negative of that of B.

We associate a region in ℝ^{d} to a signed labeled nonnesting partition π on B_{n} of type λ as follows. If B is the nonzero block of π labeled with i, we write the variables x_{i}, x_{i} + 1, …, x_{i} + λ_{i} − 1, if the sign of B is +, and −x_{i} − λ_{i} + 1, …, −x_{i} − 1, −x_{i}, if the sign of B is −, in this order, from left to right in place of the elements of B in the nonnesting diagram of π. We also write the numbers −m, …, −1, 0, 1, …, m, in this order, from left to right in place of the elements of the zero block, so that a 0 is written again in place of 0 in the middle. If τ_{1}, τ_{2}, …, τ_{2n+1} are the quantities that appear from left to right in the modified nonnesting diagram of π then the region of ℝ^{d} which we associate to π is the one defined by the inequalities

τ_{1} < τ_{2} < ⋯ < τ_{2n+1}. (2)

For the partition of Figure 3, if the blocks {2, 5, −6}, {1, 3}, labeled with 1 and 2, respectively, have the sign + then the associated region of ℝ^{2} is defined by x_{2} < x_{1} < x_{2} +1 < −1 < x_{1} +1 < −x_{1} −2 < 0 < x_{1} +2 < −x_{1} −1 < 1 < −x_{2} −1 < −x_{1} < −x_{2}.

Since (2) are linear in the x_{i}’s, they define a region of a hyperplane arrangement. To be more precise, let B_{n}(λ) denote the arrangement which consists of the hyperplanes in ℝ^{d} of the form α_{i}(x) = α_{j}(x) for i ≠ j, where α_{i} are the affine forms

\begin{matrix}x_{i}, x_{i} + 1, …, x_{i} + λ_{i} − 1 for 1 ≤ i ≤ d, \\ −x_{i}, −x_{i} − 1, …, −x_{i} − λ_{i} + 1 for 1 ≤ i ≤ d, \\ −m, …, −1, 0, 1, …, m. \end{matrix} (3)

Lemma 5.2. The signed, labeled nonnesting partitions on B_{n} of type λ are in bijection with the regions of the arrangement B_{n}(λ).

Proof. In view of the above discussion we only need to check that the region defined by (2) is nonempty. This is equivalent to the statement that we can draw the nonnesting diagram of π on the real line symmetrically around the origin so that all arcs have length 1. This follows by induction on the number of arcs after we assume that π has no singleton blocks, as we may, and remove the two extreme arcs to get the nonesting diagram of a partition π′ with two arcs less.

Proposition 5.3. We have

χ(B_{n}(λ), q) = ∏_{j=n−d}^{n−1}(q − 2j − 1).

Proof. Let q be a large prime number and 𝔽_{q} denote the finite field of integers mod q. Theorem 2.2 in [1] (see also [14, Theorem 2.69] and the original formulation in [4, §16]) implies that χ(B_{n}(λ), q) counts the number of d-tuples (x_{1}, x_{2}, …, x_{d}) ∈ 𝔽_{q}^{d} for which (3) are distinct as classes mod q. To count these d-tuples we first note that for each i, exactly one of the strings

\begin{matrix}x_{i}, x_{i} + 1, …, x_{i} + λ_{i} − 1, 1 ≤ i ≤ d, \\ −x_{i} − λ_{i} + 1, …, −x_{i} − 1, −x_{i}, 1 ≤ i ≤ d \end{matrix}

will have its values within the classes 1, 2, …, t mod q, where t = \frac{q−1}{2}. There are 2^{d} ways to choose these strings. We first permute the d strings in d! ways and place them along a line. Then we place the class 0 mod q first from the left and m indistinguishable boxes immediately to its right and distribute t − n more boxes in the d + 1 spaces between successive strings as well as to the left of the leftmost string and to the right of the rightmost one in \binom{t−n+d}{d} ways. Finally we naturally assign to the t objects to the right of 0 (which are either boxes or elements of the form x_{i} + r) the values 1, 2, …, t ∈ 𝔽_{q}, in this order, to get appropriate tuples (x_{1}, x_{2}, …, x_{d}).

The product

2^{d} d! \binom{\frac{q−1}{2} − n + d}{d}

is the expression for χ(B_{n}(λ), q) we have claimed.

Corollary 5.4. The number of nonnesting partitions on B_{n} of type λ is equal to

\frac{n!}{m_{λ} (n − d)!}.

Proof. It follows from Theorem 5.1 and Proposition 5.3 that the number of regions of B_{n}(λ) is 2^{d} \frac{n!}{(n−d)!}. By Lemma 5.2, this is also the number of signed, labeled nonnesting partitions on B_{n} of type λ, which is clearly 2^{d} m_{λ} times the number of nonnesting partitions on B_{n} of type λ.

The case of C_{n}. Signed, labeled nonnesting partitions on C_{n} of type λ are defined exactly as in the case of B_{n}. Recall that 0 does not appear in the nonnesting diagram of such a partition π. We associate a region of ℝ^{d} to π as in the case of B_{n}, except that we write the numbers −m + 1/2, …, −3/2, −1/2, 1/2, 3/2, …, m − 1/2 in place of the elements of the zero block, so the number of the τ_{i} in (2) is now 2n.

For the partition of Figure 4, if the blocks {1, 4, 6}, {2}, labeled with 1 and 2, respectively, have the sign + then the associated region of ℝ^{2} is defined by x_{1} < x_{2} < −\frac{3}{2} < x_{1} + 1 < −\frac{1}{2} < x_{1} + 2 < −x_{1} − 2 < \frac{1}{2} < −x_{1} − 1 < \frac{3}{2} < −x_{2} < −x_{1}.

Let C_{n}(λ) denote the arrangement which consists of the hyperplanes in ℝ^{d} of the form β_{i}(x) = β_{j}(x) for i ≠ j, where β_{i} are the affine forms

\begin{matrix}x_{i}, x_{i} + 1, …, x_{i} + λ_{i} − 1 for 1 ≤ i ≤ d, \\ −x_{i}, −x_{i} − 1, …, −x_{i} − λ_{i} + 1 for 1 ≤ i ≤ d, \\ −m + \frac{1}{2}, …, −\frac{3}{2}, −\frac{1}{2}, \frac{1}{2}, \frac{3}{2}, …, m − \frac{1}{2}. \end{matrix} (4)

The following lemma can be proved as Lemma 5.2.

Lemma 5.5. The signed, labeled nonnesting partitions on C_{n} of type λ are in bijection with the regions of the arrangement C_{n}(λ).

Proposition 5.6. We have

χ(C_{n}(λ), q) = ∏_{j=n−d}^{n−1}(q − 2j − 1).

Proof. Let y_{i} denote any of the forms x_{i} + r or −x_{i} − r. The equations y_{i} = k − 1/2 for k ∈ ℤ can be written as 2y_{i} = 2k − 1, so C_{n}(λ) can be defined over the integers. Hence [1, Theorem 2.2] applies again and χ(C_{n}(λ), q) counts the number of d-tuples (x_{1}, x_{2}, …, x_{d}) ∈ 𝔽_{q}^{d} for which (4) are distinct as classes mod q. Note that the conditions y_{i} ≠ −y_{i} mod q imply y_{i} ≠ 0 mod q and the ones of the form y_{i} ≠ k − 1/2 can be written as y_{i} ≠ k + \frac{q−1}{2} mod q. The rest of the proof follows the one of Proposition 5.3 except that we now place the m boxes to the right of the rightmost string, instead of to the right of 0 mod q, to guarantee that the forms y_{i} will be assigned values mod q different from t, t − 1, …, t − m + 1, where t = \frac{q−1}{2}.

The following corollary is obtained as in the case of B_{n}.

Corollary 5.7. The number of nonnesting partitions on C_{n} of type λ is equal to

\frac{n!}{m_{λ} (n − d)!}.

The following is the analogue of Corollary 4.1 for nonnesting partitions on B_{n} and C_{n}.

Corollary 5.8. The number of nonnesting partitions on B_{n} whose type has d parts is equal to \binom{n}{d}^{2}. The total number of nonnesting partitions on B_{n} is \binom{2n}{n}. The same is true if B_{n} is replaced by C_{n}.

The case of D_{n}. Recall that a nonnesting partition π on D_{n} has a zero block if e_{i} −e_{n} and e_{i} + e_{n} are both in π for some i < n. The zero block is formed by the connected component of the nonnesting diagram which contains n. Figure 6 shows a nonnesting partition on D_{5} with zero block {1, 3, 5, −1, −3, −5}.

Figure 6. A D_{5}-nonnesting partition

We now complete the proof of Theorem 2.6.

Proposition 5.9. If λ is a partition of an integer less than n − 1 then the number of nonnesting partitions on D_{n} of type λ is equal to

\frac{(n − 1)!}{m_{λ} (n − d − 1)!}.

Proof. Let π be a nonnesting partition on D_{n} of type λ. By the assumption on λ, π has a zero block which contains {n, −n} and at least one more pair {i, −i}. Merge n and −n in the nonnesting diagram of π to a single element, labeled 0, to get the diagram of a nonnesting partition on B_{n−1} of type λ. For example, the partition of Figure 6 becomes the B_{4}-nonnesting partition with nonzero blocks {2, 4} and {−2, −4}. This correspondence is a bijection between nonnesting partitions on D_{n} of type λ and nonnesting partitions on B_{n−1} of type λ, so the result follows from Corollary 5.4.

6. Remarks

1. Let Φ be an irreducible root system in ℝ^{n} associated to a Weyl group W, as in the introduction. Let Φ^{+} be a choice of positive roots and C_{Φ} denote the corresponding fundamental alcove in ℝ^{n}, defined by the inequalities α · x > 0 for α ∈ Φ^{+}. The bijection that we refered to before Theorem 2.4 sends a nonnesting partition π on Φ to the region in C_{Φ} defined by β · x > 1, if β ≥ α in the root order of Φ for some α ∈ π and β · x < 1, if otherwise. It follows that the number of nonnesting partitions on Φ is equal to the number of regions of the Φ-Catalan arrangement, divided by the order of the group W.

2. One can naturally try to carry structural properties of noncrossing partitions over to nonnesting partitions. However, the set of nonnesting partitions of [n] partially ordered by refinement will typically not be a lattice, as is the case for noncrossing partitions. Already for n = 6, the partitions {1, 3, 6}{2, 5}{4} and {1, 4, 6}{2, 5}{3} do not have a meet in this poset.

3. We do not know of a more direct proof of Theorem 2.6. In particular, we do not know of any bijections between noncrossing and nonnesting partitions in the cases of the root systems B, C or D, similar to the one in Theorem 3.1.

4. We do not know of a formula for the number of nonnesting partitions on D_{n} of type λ when λ is a partition of n. This number is equal to the number of noncrossing D_{n}-partitions (or B_{n}) of type λ if λ has no part greater than 2 but not otherwise. For example, there are 3 noncrossing D_{3}-partitions of type (3) but 4 nonnesting partitions of the same kind, namely the 3 nonnesting partitions on B_{3} of type (3) and the one with blocks {1, −2, −3} and {2, 3, −1}. Table 1 shows the number of nonnesting partitions on D_{n} of type λ for the partitions λ of n ≤ 6 with at least one part greater than 2.

Acknowledgement. I thank Paul Edelman for bringing to my attention Theorem 2.1.

References

[1] C.A. Athanasiadis, Characteristic polynomials of subspace arrangements and finite fields, Advances in Math. 122 (1996), 193–233.

[2] C.A. Athanasiadis, Algebraic combinatorics of graph spectra, subspace arrangements and Tutte polynomials, Ph.D. thesis, MIT, 1996.

[3] C.A. Athanasiadis, Piles of cubes, monotone path polytopes and hyperplane arrangements, Discrete Comput. Geom., to appear.

type  number of nonnesting partitions on D_{3}
(3)  4
type  number of nonnesting partitions on D_{4}
(4)  6
(3, 1)  15
type  number of nonnesting partitions on D_{5}
(5)  8
(4, 1)  28
(3, 2)  24
(3, 1, 1) 36
type  number of nonnesting partitions on D_{6}
(6)  10
(5, 1)  45
(4, 2)  40
(4, 1, 1) 80
(3, 3)  20
(3, 2, 1) 140
(3, 1, 1, 1) 70

Table 1. Nonnesting partitions on D_{n} by type

[4] H. Crapo and G.-C. Rota, On the Foundations of Combinatorial Theory: Combinatorial Geometries, preliminary edition, M.I.T. press, Cambridge, MA, 1970.

[5] A. Dershowits and S. Zaks, The cycle lemma and some applications, European J. Combin. 11 (1990), 35–40.

[6] A. Dvoretzky and T. Motzkin, A problem of arrangements, Duke Math. J. 14 (1947), 305–313.

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

[8] P.H. Edelman and V. Reiner, Free arrangements and rhombic tilings, Discrete Comput. Geom. 15 (1996), 307–340.

[9] P.H. Edelman and R. Simion, Chains in the lattice of non-crossing partitions, Discrete Math. 126 (1994), 107–119.

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

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

[12] C. Montenegro, The fixed point non-crossing partition lattices, Preprint, 1993.

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

[14] P. Orlik and H. Terao, Arrangements of Hyperplanes, Grundlehren 300, Springer-Verlag, New York, NY, 1992.

[15] A. Postnikov and R. Stanley, Deformations of Coxeter hyperplane arrangements, Preprint dated April 14, 1997.

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

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

[18] R. Simion and D. Ullman, On the structure of the lattice of noncrossing partitions, Discrete Math. 98 (1991), 63–68.

[19] R. Speicher, Multiplicative functions on the lattice of noncrossing partitions and free convolution, Math. Ann. 298 (1994), 611–628.

[20] R. Stanley, Enumerative Combinatorics, vol. 1, Wadsworth & Brooks/Cole, Belmont, CA, 1992.

[21] R. Stanley, Hyperplane arrangements, interval orders and trees, Proc. Nat. Acad. Sci. 93 (1996), 2620–2625.

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

[23] R. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1998.

[24] T. Zaslavsky, Facing up to arrangements: face-count formulas for partitions of space by hyperplanes, Mem. Amer. Math. Soc. vol. 1, no. 154, (1975).

Christos A. Athanasiadis, Department of Mathematics, University of Pennsylvania, 209 South 33rd Street, Philadelphia, PA 19104-6395, USA

  E-mail address: athana@math.upenn.edu