# Chain enumeration of k-divisible noncrossing partitions of classical types

Jang Soo Kim†

LIAFA, Université Paris Diderot, 175 rue du Chevaleret, 75013 Paris, France

**Abstract.** We give combinatorial proofs of the formulas for the number of multichains in the *k*-divisible noncrossing partitions of classical types with certain conditions on the rank and the block size due to Krattenthaler and Müller. We also prove Armstrong's conjecture on the zeta polynomial of the poset of *k*-divisible noncrossing partitions of type *A* invariant under the 180° rotation in the cyclic representation.

**Résumé.** Nous donnons une preuve combinatoire de la formule pour le nombre de multichaînes dans les partitions *k*-divisibles non-croisées de type classique avec certaines conditions sur le rang et la taille du bloc due à Krattenthaler et Müller. Nous prouvons aussi la conjecture d'Amstrong sur le polynôme zeta du poset des partitions *k*-divisibles non-croisées de type *A* invariantes par la rotation de 180° dans la représentation cyclique.

**Keywords:** noncrossing partitions, chain enumeration

## 1 Introduction

For a finite set $X$, a *partition* of $X$ is a collection of mutually disjoint nonempty subsets, called *blocks*, of $X$ whose union is $X$. Let $\Pi(n)$ denote the poset of partitions of $[n] = \{1, 2, \dots, n\}$ ordered by refinement, i.e. $\pi \le \sigma$ if each block of $\sigma$ is a union of blocks of $\pi$. There is a natural way to identify $\pi \in \Pi(n)$ with an intersection of reflecting hyperplanes of the Coxeter group $A_{n-1}$. For this reason, we will call $\pi \in \Pi(n)$ a *partition of type* $A_{n-1}$. With this observation Reiner [12] defined partitions of type $B_n$ and type $D_n$ as follows. A *partition of type* $B_n$ is a partition $\pi$ of $[\pm n] = \{1, 2, \dots, n, -1, -2, \dots, -n\}$ such that if $B$ is a block of $\pi$ then $-B = \{-x : x \in B\}$ is also a block of $\pi$, and there is at most one block, called *zero block*, which satisfies $B = -B$. A *partition of type* $D_n$ is a partition of type $B_n$ such that its zero block, if exists, has more than two elements. Let $\Pi_B(n)$ (resp. $\Pi_D(n)$) denote the poset of type $B_n$ (resp. type $D_n$) partitions ordered by refinement.

A *noncrossing partition of type* $A_{n-1}$, or simply a noncrossing partition, is a partition $\pi \in \Pi(n)$ with the following property: if integers $a, b, c$ and $d$ with $a < b < c < d$ satisfy $a, c \in B$ and $b, d \in B'$ for some blocks $B$ and $B'$ of $\pi$, then $B = B'$.

Let $k$ be a positive integer. A noncrossing partition is called *k-divisible* if the size of each block is divisible by $k$. Let $\text{NC}(n)$ (resp. $\text{NC}^{(k)}(n)$) denote the subposet of $\Pi(n)$ (resp. $\Pi(kn)$) consisting of the noncrossing partitions (resp. *k*-divisible noncrossing partitions).

<footnote>†The author was supported by the grant ANR08-JCJC-0011.</footnote>
Bessis [4], Brady and Watt [5] defined the generalized noncrossing partition poset NC(W) for each finite Coxeter group W, which satisfies NC(A$_{n}$$_{−}$$_{1}$) ≅ NC(n). Armstrong [1] defined the poset NC$^{(k)}$(W) of generalized k-divisible noncrossing partitions for each finite Coxeter group W, which reduces to NC(W) for k = 1 and satisfies NC$^{(k)}$(A$_{n}$$_{−}$$_{1}$) ≅ NC$^{(k)}$(n).

For each classical Coxeter group W, we have a combinatorial realization of NC$^{(k)}$(W). In other words, similar to NC(n) and NC$^{(k)}$(n), there are combinatorial posets NC$_{B}$(n) ⊂ Π$_{B}$(n), NC$^{(k)}$_{B}$(n) ⊂ Π$_{B}$(kn), NC$_{D}$(n) ⊂ Π$_{D}$(n) and NC$^{(k)}$_{D}$(n) ⊂ Π$_{D}$(kn), which are isomorphic to NC(B$_{n}$), NC$^{(k)}$(B$_{n}$), NC(D$_{n}$) and NC$^{(k)}$(D$_{n}$) respectively. Reiner [12] defined the poset NC$_{B}$(n) of noncrossing partitions of type B$_{n}$, which turned out to be isomorphic to NC(B$_{n}$). This poset is naturally generalized to the poset NC$^{(k)}$_{B}$(n) of k-divisible noncrossing partitions of type B$_{n}$. Armstrong [1] showed that NC$^{(k)}$_{B}$(n) ≅ NC$^{(k)}$(B$_{n}$). Athanasiadis and Reiner [3] defined the poset NC$_{D}$(n) of noncrossing partitions of type D$_{n}$ and showed that NC$_{D}$(n) ≅ NC(D$_{n}$). Krattenthaler [10] defined the poset NC$^{(k)}$_{D}$(n) of the k-divisible noncrossing partitions of type D$_{n}$ using annulus and showed that NC$^{(k)}$_{D}$(n) ≅ NC$^{(k)}$(D$_{n}$); see also [9].

In this paper we are mainly interested in the number of multichains in NC$^{(k)}$(n), NC$^{(k)}$_{B}$(n) and NC$^{(k)}$_{D}$(n) with some conditions on the rank and the block size.

**Definition 1.** For a multichain $\pi_1 \le \pi_2 \le \dots \le \pi_\ell$ in a graded poset $P$ with the maximum element $\hat{1}$, the rank jump vector of this multichain is the vector $(s_1, s_2, \dots, s_{\ell+1})$, where $s_1 = \text{rank}(\pi_1)$, $s_{\ell+1} = \text{rank}(\hat{1}) - \text{rank}(\pi_\ell)$ and $s_i = \text{rank}(\pi_i) - \text{rank}(\pi_{i-1})$ for $2 \le i \le \ell$.

We note that all the posets considered in this paper are graded with the maximum element, however, they do not necessarily have the minimum element. We also note that the results in this introduction have certain ‘obvious’ conditions on the rank jump vector or the block size, which we will omit for simplicity.

Edelman [6, Theorem 4.2] showed that the number of multichains in NC$^{(k)}$(n) with rank jump vector $(s_1, s_2, \dots, s_{\ell+1})$ is equal to

$$ \frac{1}{n} \binom{n}{s_1} \binom{kn}{s_2} \cdots \binom{kn}{s_{\ell+1}}. \qquad (1) $$

Modifying Edelman’s idea of the proof of (1), Reiner found an analogous formula for the number of multichains in NC$_{B}$(n) with given rank jump vector. Later, Armstrong generalized Reiner’s idea to find the following formula [1, Theorem 4.5.7] for the number of multichains in NC$^{(k)}$_{B}$(n) with rank jump vector $(s_1, s_2, \dots, s_{\ell+1})$:

$$ \binom{n}{s_1} \binom{kn}{s_2} \cdots \binom{kn}{s_{\ell+1}}. \qquad (2) $$

Athanasiadis and Reiner [3, Theorem 1.2] proved that the number of multichains in NC$_{D}$(n) with rank jump vector $(s_1, s_2, \dots, s_{\ell+1})$ is equal to

$$ 2 \binom{n-1}{s_1} \binom{n-1}{s_2} \cdots \binom{n-1}{s_{\ell+1}} + \sum_{i=1}^{\ell+1} \binom{n-1}{s_1} \cdots \binom{n-2}{s_i-2} \cdots \binom{n-1}{s_{\ell+1}}. \qquad (3) $$

To prove (3), they [3, Lemma 4.4] showed the following using incidence algebras and the Lagrange inversion formula: the number of multichains $\pi_1 \le \pi_2 \le \dots \le \pi_\ell$ in NC$_{B}$(n) with rank jump vector
$(s_1, s_2, \dots, s_{\ell+1})$ such that $i$ is the smallest integer for which $\pi_i$ has a zero block is equal to

$$ \frac{s_i}{n} \binom{n}{s_1} \binom{n}{s_2} \cdots \binom{n}{s_{\ell+1}}. \qquad (4) $$

Since (4) is quite simple and elegant, it deserves a combinatorial proof. In this paper we prove a generalization of (4) combinatorially; see Lemma 11.

The number of noncrossing partitions with given block sizes has been studied as well. In the literature, for instance [1, 2, 3], type($\pi$) for $\pi \in \Pi(n)$ is defined to be the integer partition $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_\ell)$ where the number of parts of size $i$ is equal to the number of blocks of size $i$ of $\pi$. However, to state the results in a uniform way, we will use the following different definition of type($\pi$).

**Definition 2.** The type of a partition $\pi \in \Pi(n)$, denoted by type($\pi$), is the sequence $(b; b_1, b_2, \dots, b_n)$ where $b_i$ is the number of blocks of $\pi$ of size $i$ and $b = b_1 + b_2 + \dots + b_n$. The type of $\pi \in \Pi_B(n)$ (or $\pi \in \Pi_D(n)$), denoted by type($\pi$), is the sequence $(b; b_1, b_2, \dots, b_n)$ where $b_i$ is the number of unordered pairs $(B, -B)$ of nonzero blocks of $\pi$ of size $i$ and $b = b_1 + b_2 + \dots + b_n$. For a partition $\pi$ in either $\Pi(kn)$, $\Pi_B(kn)$ or $\Pi_D(kn)$, if the size of each block of $\pi$ is divisible by $k$, then we define the k-type type$^{(k)}$(\pi) of $\pi$ to be $(b; b_k, b_{2k}, \dots, b_{kn})$ where type($\pi$) = $(b; b_1, b_2, \dots, b_{kn})$.

Kreweras [11, Theorem 4] proved that the number of $\pi \in \text{NC}(n)$ with type($\pi$) = $(b; b_1, b_2, \dots, b_n)$ is equal to

$$ \frac{n!}{b_1!b_2!\cdots b_n!(n-b+1)!} = \frac{1}{b} \binom{b}{b_1, b_2, \dots, b_n} \binom{n}{b-1}. \qquad (5) $$

Athanasiadis [2, Theorem 2.3] proved that the number of $\pi \in \text{NC}_B(n)$ with type($\pi$) = $(b; b_1, b_2, \dots, b_n)$ is equal to

$$ \frac{n!}{b_1!b_2!\cdots b_n!(n-b)!} = \binom{b}{b_1, b_2, \dots, b_n} \binom{n}{b-1}. \qquad (6) $$

Athanasiadis and Reiner [3, Theorem 1.3] proved that the number of $\pi \in \text{NC}_D(n)$ with type($\pi$) = $(b; b_1, b_2, \dots, b_n)$ is equal to

$$ \frac{(n-1)!}{b_1!b_2!\cdots b_n!(n-1-b)!} = \binom{b}{b_1, b_2, \dots, b_n} \binom{n-1}{b-1}, \qquad (7) $$

if $b_1 + 2b_2 + \dots + nb_n \le n-2$, and

$$ \begin{aligned} & (2(n-b) + b_1) \frac{(n-1)!}{b_1!b_2!\cdots b_n!(n-b)!} \\ & = 2 \binom{b}{b_1, b_2, \dots, b_n} \binom{n-1}{b} + \binom{b-1}{b_1-1, b_2, \dots, b_n} \binom{n-1}{b-1}, \end{aligned} \qquad (8) $$

if $b_1 + 2b_2 + \dots + nb_n = n$.

Armstrong [1, Theorem 4.4.4 and Theorem 4.5.11] generalized (5) and (6) as follows: the number of multichains $\pi_1 \le \pi_2 \le \dots \le \pi_\ell$ in $\text{NC}^{(k)}(n)$ and in $\text{NC}_B^{(k)}(n)$ with type$^{(k)}$(\pi_1) = (b; b_1, b_2, \dots, b_n)$ are equal to, respectively,

$$ \frac{(\ell kn)!}{b_1!b_2!\cdots b_n!(\ell kn - b + 1)!} = \frac{1}{b} \binom{b}{b_1, b_2, \dots, b_n} \binom{\ell kn}{b-1}, \qquad (9) $$
and

$$ \frac{(\ell kn)!}{b_1! b_2! \cdots b_n!(\ell kn - b)!} = \binom{b}{b_1, b_2, \ldots, b_n} \binom{\ell kn}{b} \quad (10) $$

Krattenthaler and Müller [9] generalized all the above known results except (4) in the following three theorems.

**Theorem 1.** [9, Corollary 12] Let $b, b_1, b_2, \ldots, b_n$ and $s_1, s_2, \ldots, s_{\ell+1}$ be nonnegative integers satisfying $\sum_{i=1}^n b_i = b$, $\sum_{i=1}^n i \cdot b_i = n$, $\sum_{i=1}^{\ell+1} s_i = n-1$ and $s_1 = n-b$. Then the number of multichains $\pi_1 \le \pi_2 \le \cdots \le \pi_\ell$ in $\text{NC}^{(k)}(n)$ with rank jump vector $(s_1, s_2, \ldots, s_{\ell+1})$ and type$^{(k)}(\pi_1) = (b; b_1, b_2, \ldots, b_n)$ is equal to

$$ \frac{1}{b} \binom{b}{b_1, b_2, \ldots, b_n} \binom{kn}{s_2} \cdots \binom{kn}{s_{\ell+1}} $$

**Theorem 2.** [9, Corollary 14] Let $b, b_1, b_2, \ldots, b_n$ and $s_1, s_2, \ldots, s_{\ell+1}$ be nonnegative integers satisfying $\sum_{i=1}^n b_i = b$, $\sum_{i=1}^n i \cdot b_i \le n$, $\sum_{i=1}^{\ell+1} s_i = n$ and $s_1 = n-b$. Then the number of multichains $\pi_1 \le \pi_2 \le \cdots \le \pi_\ell$ in $\text{NC}_B^{(k)}(n)$ with rank jump vector $(s_1, s_2, \ldots, s_{\ell+1})$ and type$^{(k)}(\pi_1) = (b; b_1, b_2, \ldots, b_n)$ is equal to

$$ \binom{b}{b_1, b_2, \ldots, b_n} \binom{kn}{s_2} \cdots \binom{kn}{s_{\ell+1}} $$

**Theorem 3.** [9, Corollary 16] Let $b, b_1, b_2, \ldots, b_n$ and $s_1, s_2, \ldots, s_{\ell+1}$ be nonnegative integers satisfying $\sum_{i=1}^n b_i = b$, $\sum_{i=1}^n i \cdot b_i \le n$, $\sum_{i=1}^n i \cdot b_i \ne n-1$, $\sum_{i=1}^{\ell+1} s_i = n$ and $s_1 = n-b$. Then the number of multichains $\pi_1 \le \pi_2 \le \cdots \le \pi_\ell$ in $\text{NC}_D^{(k)}(n)$ with rank jump vector $(s_1, s_2, \ldots, s_{\ell+1})$ and type$^{(k)}(\pi_1) = (b; b_1, b_2, \ldots, b_n)$ is equal to

$$ \binom{b}{b_1, b_2, \ldots, b_n} \binom{k(n-1)}{s_2} \cdots \binom{k(n-1)}{s_{\ell+1}} $$

if $b_1 + 2b_2 + \cdots + nb_n \le n-2$, and

$$ 2 \binom{b}{b_1, b_2, \ldots, b_n} \binom{k(n-1)}{s_2} \cdots \binom{k(n-1)}{s_{\ell+1}} \\ + \frac{s_i-1}{b-1} \binom{b-1}{b_1-1, b_2, \ldots, b_n} \sum_{i=2}^{\ell+1} \binom{k(n-1)}{s_2} \cdots \binom{k(n-1)}{s_i-1} \cdots \binom{k(n-1)}{s_{\ell+1}} $$

if $b_1 + 2b_2 + \cdots + nb_n = n$.

Krattenthaler and Müller's proofs of Theorems 1, 2 and 3 were not combinatorial. Especially, in the introduction, they wrote that Theorems 1 and 2 seem amenable to combinatorial proofs, however, to find a combinatorial proof of Theorem 3 seems rather hopeless. In this paper, we will give combinatorial proofs of Theorems 1 and 2. For a combinatorial proof of Theorem 3, see the full version [8] of this paper.

This paper is organized as follows. In Section 2 we recall the definition of $\text{NC}_B(n)$ and $\text{NC}_D(n)$. In Section 3 we recall the bijection $\psi$ in [7] between $\text{NC}_B(n)$ and the set of pairs $(\sigma, x)$, where $\sigma \in \text{NC}(n)$ and $x$ is either $\emptyset$, an edge or a block of $\sigma$. Then we find a necessary and sufficient condition for the two
<figure><img src="image_1.png" /><figcaption>Fig. 1: The circular representation of {{1, 2, 5, 10}, {3, 4}, {6, 7, 9}, {8}}.</figcaption></figure>

pairs $(\sigma_1, x_1)$ and $(\sigma_2, x_2)$ to be $\psi^{-1}(\sigma_1, x_1) \le \psi^{-1}(\sigma_2, x_2)$ in the poset $NC_B(n)$. This property will play a crucial role to prove Theorem 3. In Section 4 we prove Theorem 1 by modifying the argument of Edelman [6]. For $0 < r < k$, we consider the subposet $NC^{(k)}(n; r)$ of $NC(nk + r)$ consisting of the partitions $\pi$ such that all but one blocks of $\pi$ have sizes divisible by $k$. Then we prove similar chain enumeration results for $NC^{(k)}(n; r)$. We also prove that the poset $\widetilde{NC}^{(2k)}(2n + 1)$ suggested by Armstrong is isomorphic to $NC^{(2k)}(n; k)$. With this, we prove Armstrong's conjecture on the zeta polynomial of $\widetilde{NC}^{(2k)}(2n + 1)$ and answer the question on rank-, type-selection formulas [1, Conjecture 4.5.14 and Open Problem 4.5.15]. In Section 5 we prove a generalization of (4) and Theorem 2. All the arguments in this paper are purely combinatorial.

## 2 Noncrossing partitions of classical types

Recall that $\Pi(n)$ denotes the poset of partitions of $[n]$ and $\Pi_B(n)$ (resp. $\Pi_D(n)$) denotes the poset of partitions of type $B_n$ (resp. $D_n$). For simplicity, we will write a partition of type $B_n$ or $D_n$ in the following way:

$$ \{\pm\{1, -3, 6\}, \{2, 4, -2, -4\}, \pm\{5, 8\}, \pm\{7\}\}, $$

which means

$$ \{\{1, -3, 6\}, \{-1, 3, -6\}, \{2, 4, -2, -4\}, \{5, 8\}, \{-5, -8\}, \{7\}, \{-7\}\}. $$

The circular representation of $\pi \in \Pi(n)$ is the drawing obtained as follows. Arrange $n$ vertices around a circle which are labeled with the integers $1, 2, \dots, n$. For each block $B$ of $\pi$, draw the convex hull of the vertices whose labels are the integers in $B$. For example, see Figure 1. It is easy to see that the following definition coincides with the definition of a noncrossing partition in the introduction: $\pi$ is a *noncrossing partition* if the convex hulls in the circular representation of $\pi$ do not intersect.

Let $\pi \in \Pi_B(n)$. The circular representation of $\pi$ is the drawing obtained as follows. Arrange $2n$ vertices in a circle which are labeled with the integers $1, 2, \dots, n, -1, -2, \dots, -n$. For each block $B$ of $\pi$, draw the convex hull of the vertices whose labels are the integers in $B$. For example, see Figure 2. Note that the circular representation of $\pi \in \Pi_B(n)$ is invariant, if we do not concern the labels, under the $180^\circ$ rotation, and the zero block of $\pi$, if exists, corresponds to the convex hull containing the center. Then $\pi$ is a *noncrossing partition of type $B_n$* if the convex hulls do not intersect.

Let $\pi \in \Pi_D(n)$. The circular representation of $\pi$ is the drawing obtained as follows. Arrange $2n - 2$ vertices labeled with $1, 2, \dots, n - 1, -1, -2, \dots, -(n - 1)$ in a circle and put a vertex labeled with $\pm n$
<figure><img src="image_2.png" /><figcaption>Fig. 2: The circular representations of {$\pm\{1, 4, -5\}, \pm\{2, 3\}$} and {$\{1, 4, 5, -1, -4, -5\}, \pm\{2, 3\}$}.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Fig. 3: The type D circular representations of {$\pm\{1, -5, -6\}, \pm\{2, 4, -7\}, \pm\{3\}$} and {$\{1, 6, -1, -6\}, \pm\{2, 4, 5\}, \pm\{3\}$}.</figcaption></figure>

at the center. For each block $B$ of $\pi$, draw the convex hull of the vertices whose labels are in $B$. Then $\pi$ is a noncrossing partition of type $D_n$ if the convex hulls do not intersect in their interiors. For example, see Figure 3.

Let $\pi \in \Pi(n)$. An edge of $\pi$ is a pair $(i, j)$ of integers with $i < j$ such that $i, j \in B$ for a block $B$ of $\pi$ and there is no other integer $k$ in $B$ with $i < k < j$. The standard representation of $\pi$ is the drawing obtained as follows. Arrange the integers $1, 2, \dots, n$ in a horizontal line. For each edge $(i, j)$ of $\pi$, connect the integers $i$ and $j$ with an arc above the horizontal line. For example, see Figure 4. Then $\pi$ is a noncrossing partition if and only if the arcs in the standard representation do not intersect.

Let $\pi \in \Pi_B(n)$. The standard representation of $\pi$ is the drawing obtained as follows. Arrange the integers $1, 2, \dots, n, -1, -2, \dots, -n$ in a horizontal line. Then connect the integers $i$ and $j$ with an arc above the horizontal line for each pair $(i, j)$ of integers such that $i, j$ are in the same block $B$ of $\pi$ and there is no other integer in $B$ between $i$ and $j$ in the horizontal line. For example, see Figure 5. Then $\pi$ is a noncrossing partition of type $B_n$ if and only if the arcs in the standard representation do not intersect.

Let $\text{NC}_B(n)$ denote the subposet of $\Pi_B(n)$ consisting of the noncrossing partitions of type $B_n$. Note

<figure><img src="image_4.png" /><figcaption>Fig. 4: The standard representation of {$\{1, 2, 5, 10\}, \{3, 4\}, \{6, 7, 9\}, \{8\}, \{11\}, \{12, 14\}, \{13\}$}.</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>Fig. 5: The standard representation of {$\pm\{1, 2, -8\}, \pm\{3, -7\}, \pm\{4, 5\}, \pm\{6\}$}.</figcaption></figure>

<figure><img src="image_6.png" /></figure>

**Fig. 6:** The partition $\tau$ obtained from the partition $\pi$ in Figure 5 by removing all the negative integers. Then $X = \{{\{1, 2\}, \{3\}, \{7\}, \{8\}\}}$ is the set of blocks of $\tau$ which are not blocks of $\pi$.

that for $\pi \in \text{NC}_B(n)$, $\text{rank}(\pi) = n - \text{nz}(\pi)$, where $\text{nz}(\pi)$ denotes the number of unordered pairs $(B, -B)$ of nonzero blocks of $\pi$.

### 3 Interpretation of noncrossing partitions of type $B_n$

Let $\mathfrak{B}(n)$ denote the set of pairs $(\sigma, x)$, where $\sigma \in \text{NC}(n)$ and $x$ is either $\emptyset$, an edge or a block of $\sigma$. Note that since for each $\sigma \in \text{NC}(n)$, we have $n+1$ choices for $x$ with $(\sigma, x) \in \mathfrak{B}(n)$, one may consider $\mathfrak{B}(n)$ as $\text{NC}(n) \times [n+1]$.

Let us recall the bijection $\psi: \text{NC}_B(n) \to \mathfrak{B}(n)$ in [7].

Let $\pi \in \text{NC}_B(n)$. Then let $\tau$ be the partition of $[n]$ obtained from $\pi$ by removing all the negative integers and let $X$ be the set of blocks of $\tau$ which are not blocks of $\pi$. For example, see Figure 6. Now assume that $X$ has $k$ blocks $A_1, A_2, \dots, A_k$ with $\max(A_1) < \max(A_2) < \dots < \max(A_k)$. Let $\sigma$ be the partition obtained from $\tau$ by unioning $A_r$ and $A_{k+1-r}$ for all $r = 1, 2, \dots, \lfloor(k-1)/2\rfloor$. Let

$$x = \begin{cases} \emptyset, & \text{if } k = 0; \\ (\min(A_{k/2}), \max(A_{k/2+1})), & \text{if } k \neq 0 \text{ and } k \text{ is even}; \\ A_{(k+1)/2}, & \text{if } k \text{ is odd.} \end{cases}$$

Then we define $\psi(\pi)$ to be the pair $(\sigma, x)$. For example, see Figure 7.

**Theorem 4.** [7] The map $\psi: \text{NC}_B(n) \to \mathfrak{B}(n)$ is a bijection. Moreover, for $\pi \in \text{NC}_B(n)$ with type($\pi$) = $(b; b_1, b_2, \dots, b_n)$ and $\psi(\pi) = (\sigma, x)$, we have type($\sigma$) = type($\pi$) if $\pi$ does not have a zero block; and type($\sigma$) = $(b+1; b_1, \dots, b_i+1, \dots, b_n)$ if $\pi$ has a zero block of size $2i$.

Now we will find a necessary and sufficient condition for $(\sigma_1, x_1), (\sigma_2, x_2) \in \mathfrak{B}(n)$ to be $\psi^{-1}(\sigma_1, x_1) \le \psi^{-1}(\sigma_2, x_2)$ in $\text{NC}_B(n)$.

<figure><img src="image_7.png" /></figure>

Fig. 7: The partition $\sigma$ obtained from the partition $\tau$ in Figure 5 by unioning $\{1, 2\}, \{8\}$ and $\{3\}, \{7\}$ which are the blocks in $X = \{{\{1, 2\}, \{3\}, \{7\}, \{8\}\}}$. Since $X$ has even number of blocks, $x$ is the edge (3, 7). Then $\psi(\pi) = (\sigma, x)$ for the partition $\pi$ in Figure 5.
For a partition $\pi$ (either in $\Pi(n)$ or in $\Pi_B(n)$), we write $i \stackrel{\pi}{\sim} j$ if $i$ and $j$ are in the same block of $\pi$ and $i \not\stackrel{\pi}{\sim} j$ otherwise. Note that if $\psi(\pi) = (\sigma, x)$, then we have $i \stackrel{\sigma}{\sim} j$ if and only if $i \stackrel{\pi}{\sim} j$ or $i \stackrel{\pi}{\sim} -j$. The following lemmas are clear from the construction of $\psi$.

**Proposition 5.** Let $\psi(\pi_1) = (\sigma_1, x_1)$ and $\psi(\pi_2) = (\sigma_2, x_2)$. Then $\pi_1 \le \pi_2$ if and only if $\sigma_1 \le \sigma_2$ and one of the following holds:

1. $x_1 = x_2 = \emptyset$,

2. $x_2$ is an edge (a, b) of $\sigma_2$ and $x_1$ is the unique minimal length edge (i, j) of $\sigma_1$ with $i \le a < b \le j$ if such an edge exists; and $x_1 = \emptyset$ otherwise.

3. $x_2$ is a block of $\sigma_2$, and $x_1$ is a block of $\sigma_1$ with $x_1 \subset x_2$,

4. $x_2$ is a block of $\sigma_2$ and $x_1$ is an edge (i, j) of $\sigma_1$ with $i, j \in x_2$.

5. $x_2$ is a block of $\sigma_2$ and $x_1$ is the minimal length edge (i, j) of $\sigma_1$ with $i < \min(x_2) \le \max(x_2) < j$ if such an edge exists; and $x_1 = \emptyset$ otherwise.

# 4 k-divisible noncrossing partitions of type A

Let $k$ be a positive integer. A noncrossing partition $\pi \in \text{NC}(kn)$ is k-divisible if the size of each block is divisible by $k$. Let $\text{NC}^{(k)}(n)$ denote the subposet of $\text{NC}(kn)$ consisting of k-divisible noncrossing partitions. Then $\text{NC}^{(k)}(n)$ is a graded poset with the rank function $\text{rank}(\pi) = n - \text{bk}(\pi)$, where $\text{bk}(\pi)$ is the number of blocks of $\pi$.

To prove (1), Edelman [6] found a bijection between the set of pairs $(c, a)$ of a multichain $c : \pi_1 \le \pi_2 \le \dots \le \pi_{\ell+1}$ in $\text{NC}^{(k)}(n)$ with rank jump vector $(s_1, s_2, \dots, s_{\ell+1})$ and an integer $a \in [n]$ and the set of $(\ell+1)$-tuples $(L, R_1, R_2, \dots, R_\ell)$ with $L \subset [n], |L| = n - s_1, R_i \subset [kn], \text{ and } |R_i| = s_i \text{ for } i \in [\ell]$. This bijection has been extended to the noncrossing partitions of type $B_n$ [1, 12] and type $D_n$ [3].

In this section we prove Theorem 1 by modifying the idea of Edelman. Let us first introduce several notations.

## 4.1 The cyclic parenthesization

Let $P(n)$ denote the set of pairs $(L, R)$ of subsets $L, R \subset [n]$ with the same cardinality. Let $(L, R) \in P(n)$. We can identify $(L, R)$ with the cyclic parenthesization of $(L, R)$ defined as follows. We place a left parenthesis before the occurrence of $i$ for each $i \in L$ and a right parenthesis after the occurrence of $i$ for each $i \in R$ in the sequence 1, 2, ..., $n$. We consider this sequence in cyclic order.

For $x \in R$, the size of $x$ is defined to be the number of integers enclosed by $x$ and its corresponding left parenthesis, which are not enclosed by any other matching pair of parentheses. The type of $(L, R)$, denoted by $\text{type}(L, R)$, is defined to be $(b; b_1, b_2, \dots, b_n)$, where $b_i$ is the number of $x \in R$ whose sizes are equal to $i$ and $b = b_1 + b_2 + \dots + b_n$.

**Example 1.** Let $(L, R) = (\{2, 3, 9, 11, 15, 16\}, \{1, 4, 5, 8, 9, 12\}) \in P(16)$. Then the cyclic parenthesization is the following:

$$1) (2 \ (3 \ 4) \ 5) \ 6 \ 7 \ 8) (9) \ 10 \ (11 \ 12) \ 13 \ 14 \ (15 \ (16 \quad (11))$$
Since we consider (11) in the cyclic order, the right parenthesis of 1 is matched with the left parenthesis of 16 and the right parenthesis of 8 is matched with the left parenthesis of 15. The sizes of 5 and 8 in $R$ are 2 and 4 respectively. We have type$(L, R) = (6; 1, 4, 0, 1, 0, \dots, 0)$.

Let $\overline{P}(n)$ denote the set of elements $(L, R) \in P(n)$ such that the type $(b; b_1, b_2, \dots, b_n)$ of $(L, R)$ satisfies $\sum_{i=1}^n ib_i < n$. Thus we have $(L, R) \in \overline{P}(n)$ if and only if there is at least one integer in the cyclic parenthesization of $(L, R)$ which is not enclosed by any matching pair of parentheses.

We define a map $\tau$ from $\overline{P}(n)$ to the set of pairs $(B, \pi)$, where $\pi \in \text{NC}(n)$ and $B$ is a block of $\pi$ as follows. Let $(L, R) \in \overline{P}(n)$. Find a matching pair of parentheses in the cyclic parenthesization of $(L, R)$ which do not enclose any other parenthesis. Remove the integers enclosed by these parentheses, and make a block of $\pi$ with there integers. Repeat this procedure until there is no parenthesis. Since $(L, R) \in \overline{P}(n)$, we have several remaining integers after removing all the parentheses. These integers also form a block of $\pi$ and $B$ is defined to be this block.

**Example 2.** Let $(L, R)$ be the pair in Example 1 represented by (11). Note that $(L, R) \in \overline{P}(16)$. Then $\tau(L, R) = (B, \pi)$, where $\pi$ consists of the blocks $\{1, 16\}, \{2, 5\}, \{3, 4\}, \{6, 7, 8, 15\}, \{9\}, \{11, 12\}$ and $\{10, 13, 14\}$, and $B = \{10, 13, 14\}$.

**Proposition 6.** The map $\tau$ is a bijection between $\overline{P}(n)$ and the set of pairs $(B, \pi)$, where $\pi \in \text{NC}(n)$ and $B$ is a block of $\pi$. Moreover, if $\tau(L, R) = (B, \pi)$, type$(\pi) = (b; b_1, b_2, \dots, b_n)$ and $|B| = j$, then type$(L, R) = (b-1, b_1, \dots, b_j-1, \dots, b_n)$.

We define $P(n, \ell)$ to be the set of $(\ell+1)$-tuples $(L, R_1, R_2, \dots, R_\ell)$ such that $L, R_1, R_2, \dots, R_\ell \subset [n]$ and $|L| = |R_1| + |R_2| + \dots + |R_\ell|$. Similarly, we can consider the labeled cyclic parenthesization of $(L, R_1, R_2, \dots, R_\ell)$ by placing a left parenthesis before $i$ for each $i \in L$ and right parentheses $)_{j_1})_{j_2} \dots)_{j_t}$ labeled with $j_1 < j_2 < \dots < j_t$ after $i$ if $R_{j_1}, R_{j_2}, \dots, R_{j_t}$ are the sets containing $i$ among $R_1, R_2, \dots, R_\ell$. For each element $x \in R_i$, the size of $x$ is defined in the same way as in the case of $(L, R)$. We define the type of $(L, R_1, R_2, \dots, R_\ell)$ similarly to the type of $(L, R)$.

**Example 3.** Let $T = (L, R_1, R_2) = (\{2, 4, 5\}, \{2\}, \{2, 6\}) \in P(7, 2)$. Then the labeled cyclic parenthesization of $T$ is the following:

$$1 \ (2)_1 \ 2 \ 3 \ (4 \ (5 \ 6)_2 \ 7 \qquad (12)$$

Then the size of $2 \in R_1$ is 1, the size of $2 \in R_2$ is 3 and the size of $6 \in R_2$ is 2. Thus the type of $T$ is $(3; 1, 1, 1, 0, \dots, 0)$.

**Lemma 7.** Let $b, b_1, b_2, \dots, b_n$ and $c_1, c_2, \dots, c_\ell$ be nonnegative integers with $b = b_1 + b_2 + \dots + b_n = c_1+c_2+\dots+c_\ell$. Then the number of elements $(L, R_1, R_2, \dots, R_\ell)$ in $P(n, \ell)$ with type $(b; b_1, b_2, \dots, b_n)$ and $|R_i| = c_i$ for $i \in [\ell]$ is equal to

$$\binom{b}{b_1, b_2, \dots, b_n} \binom{n}{c_1} \binom{n}{c_2} \dots \binom{n}{c_\ell}.$$

Let $\overline{P}(n, \ell)$ denote the set of $(L, R_1, R_2, \dots, R_\ell) \in P(n, \ell)$ such that the type $(b; b_1, b_2, \dots, b_n)$ of $(L, R_1, R_2, \dots, R_\ell)$ satisfies $\sum_{i=1}^n ib_i < n$.

Using $\tau$, we define a map $\tau'$ from $\overline{P}(n, \ell)$ to the set of pairs $(B, c)$, where $c: \pi_1 \le \pi_2 \le \dots \le \pi_\ell$ is a multichain in $\text{NC}(n)$ and $B$ is a block of $\pi_1$ as follows. Let $P = (L, R_1, R_2, \dots, R_\ell) \in \overline{P}(n, \ell)$. Applying the same argument as in the case of $\tau$ to the labeled cyclic parenthesization of $P$, we get $(B_1, \pi_1)$. Then remove all the right parentheses in $R_1$ from the cyclic parenthesization and their corresponding left parentheses in $R_2, \dots, R_\ell$.
parentheses. By repeating this procedure, we get $(B_i, \pi_i)$ for $i = 2, 3, \dots, \ell$. Then we obtain a multichain $\mathbf{c} : \pi_1 \le \pi_2 \le \dots \le \pi_\ell$ in $\text{NC}(n)$. We define $\tau'(P) = (B_1, \mathbf{c})$.

**Proposition 8.** The map $\tau'$ is a bijection between $\overline{P}(n, \ell)$ and the set of pairs $(B, \mathbf{c})$ where $\mathbf{c} : \pi_1 \le \pi_2 \le \dots \le \pi_\ell$ is a multichain in $\text{NC}(n)$ and $B$ is a block of $\pi_1$. Moreover, if $\tau'(L, R_1, R_2, \dots, R_\ell) = (B, \mathbf{c})$, the rank jump vector of $\mathbf{c}$ is $(s_1, s_2, \dots, s_{\ell+1})$, $\text{type}(\pi_1) = (b; b_1, b_2, \dots, b_n)$ and $|B| = j$, then the type of $(L, R_1, R_2, \dots, R_\ell)$ is $(b-1; b_1, \dots, b_j - 1, \dots, b_n)$ and $(|R_1|, |R_2|, \dots, |R_\ell|) = (s_2, s_3, \dots, s_{\ell+1})$.

**Theorem 9.** Let $b, b_1, b_2, \dots, b_n$ and $s_1, s_2, \dots, s_{\ell+1}$ be nonnegative integers satisfying $\sum_{i=1}^n b_i = b$, $\sum_{i=1}^n i \cdot b_i = n$, $\sum_{i=1}^{\ell+1} s_i = n-1$ and $s_1 = n-b$. Then the number of multichains $\pi_1 \le \pi_2 \le \dots \le \pi_\ell$ in $\text{NC}(n)$ with rank jump vector $(s_1, s_2, \dots, s_{\ell+1})$, $\text{type}(\pi_1) = (b; b_1, b_2, \dots, b_n)$ is equal to

$$ \frac{1}{b} \binom{b}{b_1, b_2, \dots, b_n} \binom{n}{s_2} \cdots \binom{n}{s_{\ell+1}}. $$

*Proof.* By Lemma 7 and Proposition 8, the number of pairs $(B, \mathbf{c})$, where $\mathbf{c}$ is a multichain satisfying the conditions and $B$ is a block of $\pi_1$, is equal to

$$ \sum_{j=1}^{n} \binom{b-1}{b_1, \dots, b_j-1, \dots, b_n} \binom{n}{s_2} \cdots \binom{n}{s_{\ell+1}} = \binom{b}{b_1, b_2, \dots, b_n} \binom{n}{s_2} \cdots \binom{n}{s_{\ell+1}}. $$

Since there are $b = \text{bk}(\pi_1)$ choices of $B$ for each $\mathbf{c}$, we get the theorem. Note that Lemma 7 states the number of elements in $P(n, \ell)$. However, by the condition on the type, all the elements in consideration are in $\overline{P}(n, \ell)$. $\square$

Now we can prove Theorem 1.

*Proof of Theorem 1.* Let $\pi_1 \le \pi_2 \le \dots \le \pi_\ell$ be a multichain in $\text{NC}^{(k)}(n)$ with rank jump vector $(s_1, s_2, \dots, s_{\ell+1})$ and $\text{type}^{(k)}(\pi_1) = (b; b_1, b_2, \dots, b_n)$. Then this is a multichain in $\text{NC}(kn)$ with rank jump vector $(kn-1-b, s_2, \dots, s_{\ell+1})$ and $\text{type}(\pi_1) = (b; b'_1, b'_2, \dots, b'_{kn})$ where $b'_{ki} = b_i$ for $i \in [n]$ and $b'_j = 0$ if $j$ is not divisible by $k$. By Theorem 9, the number of such multichains is equal to

$$ \frac{1}{b} \binom{b}{b'_1, b'_2, \dots, b'_{kn}} \binom{kn}{s_2} \cdots \binom{kn}{s_{\ell+1}} = \frac{1}{b} \binom{b}{b_1, b_2, \dots, b_n} \binom{kn}{s_2} \cdots \binom{kn}{s_{\ell+1}}. $$

<figure><img src="image_8.png" /></figure>

## 4.2 Augmented $k$-divisible noncrossing partitions of type A

If all the block sizes of a partition $\pi$ are divisible by $k$ then the size of $\pi$ must be divisible by $k$. Thus $k$-divisible partitions can be defined only on $[kn]$. We extend this definition to partitions of size not divisible by $k$ as follows.

Let $k$ and $r$ be integers with $0 < r < k$. A partition $\pi$ of $[kn + r]$ is augmented $k$-divisible if the sizes of all but one of the blocks are divisible by $k$.

Let $\text{NC}^{(k)}(n; r)$ denote the subposet of $\text{NC}(kn + r)$ consisting of the augmented $k$-divisible non-crossing partitions. Then $\text{NC}^{(k)}(n; r)$ is a graded poset with the rank function $\text{rank}(\pi) = n - \text{bk}'(\pi)$, where $\text{bk}'(\pi)$ is the number of blocks of $\pi$ whose sizes are divisible by $k$. We define $\text{type}^{(k)}(\pi)$ to be $(b; b_1, b_2, \dots, b_n)$ where $b_i$ is the number of blocks $B$ of size $ki$ and $b = b_1 + b_2 + \dots + b_n$.
**Theorem 10.** Let $0 < r < k$. Let $b, b_1, b_2, \dots, b_n$ and $s_1, s_2, \dots, s_{\ell+1}$ be nonnegative integers satisfying $\sum_{i=1}^n b_i = b$, $\sum_{i=1}^n i \cdot b_i \le n$, $\sum_{i=1}^{\ell+1} s_i = n$ and $s_1 = n - b$. Then the number of multichains $\mathbf{c} : \pi_1 \le \pi_2 \le \dots \le \pi_\ell$ in $\mathrm{NC}^{(k)}(n; r)$ with rank jump vector $(s_1, s_2, \dots, s_{\ell+1})$ and type$^{(k)}(\pi_1) = (b; b_1, b_2, \dots, b_n)$ is equal to

$$ \binom{b}{b_1, b_2, \dots, b_n} \binom{kn+r}{s_2} \cdots \binom{kn+r}{s_{\ell+1}}. $$

# 5 k-divisible noncrossing partitions of type B

Let $\pi \in \mathrm{NC}_B(kn)$. We say that $\pi$ is a k-divisible noncrossing partition of type $B_n$ if the size of each block of $\pi$ is divisible by $k$.

Let $\mathrm{NC}_B^{(k)}(n)$ denote the subposet of $\mathrm{NC}_B(kn)$ consisting of k-divisible noncrossing partitions of type $B_n$. Then $\mathrm{NC}_B^{(k)}(n)$ is a graded poset with the rank function $\mathrm{rank}(\pi) = n - \mathrm{nz}(\pi)$, where $\mathrm{nz}(\pi)$ denotes the number of unordered pairs $(B, -B)$ of nonzero blocks of $\pi$.

We can prove Theorem 2 using a similar method in the proof of Theorem 1. Instead of doing this, we will prove the following lemma which implies Theorem 2. Note that the following lemma is also a generalization of (4).

For a multichain $\mathbf{c} : \pi_1 \le \pi_2 \le \dots \le \pi_\ell$ in $\mathrm{NC}_B^{(k)}(n)$, the index $\mathrm{ind}(\mathbf{c})$ of $\mathbf{c}$ is the smallest integer $i$ such that $\pi_i$ has a zero block. If there is no such integer $i$, then $\mathrm{ind}(\mathbf{c}) = \ell + 1$.

**Lemma 11.** Let $b, b_1, b_2, \dots, b_n$ and $s_1, s_2, \dots, s_{\ell+1}$ be nonnegative integers satisfying $\sum_{i=1}^n b_i = b$, $\sum_{i=1}^n i \cdot b_i \le n$, $\sum_{i=1}^{\ell+1} s_i = n$ and $s_1 = n - b$. Then the number of multichains $\mathbf{c} : \pi_1 \le \pi_2 \le \dots \le \pi_\ell$ in $\mathrm{NC}_B^{(k)}(n)$ with rank jump vector $(s_1, s_2, \dots, s_{\ell+1})$, type$^{(k)}(\pi_1) = (b; b_1, b_2, \dots, b_n)$ and $\mathrm{ind}(\mathbf{c}) = i$ is equal to

$$ \binom{b}{b_1, b_2, \dots, b_n} \binom{kn}{s_2} \cdots \binom{kn}{s_{\ell+1}}, $$

if $i=1$, and

$$ \frac{s_i}{b} \binom{b}{b_1, b_2, \dots, b_n} \binom{kn}{s_2} \cdots \binom{kn}{s_{\ell+1}}, $$

if $i \ge 2$.

## 5.1 Armstrong's conjecture

Let $\widetilde{\mathrm{NC}}^{(k)}(n)$ denote the subposet of $\mathrm{NC}^{(k)}(n)$ whose elements are fixed under the $180^\circ$ rotation in the circular representation.

Armstrong [1, Conjecture 4.5.14] conjectured the following. Let $n$ and $k$ be integers such that $n$ is even and $k$ is arbitrary, or $n$ is odd and $k$ is even. Then

$$ Z(\widetilde{\mathrm{NC}}^{(k)}(n), \ell) = \binom{\lfloor (k\ell + 1)n/2 \rfloor}{\lfloor n/2 \rfloor}. $$

If $n$ is even then $\widetilde{\mathrm{NC}}^{(k)}(n)$ is isomorphic to $\mathrm{NC}_B^{(k)}(n/2)$, whose zeta polynomial is already known. If both $n$ and $k$ are odd, then $\widetilde{\mathrm{NC}}^{(k)}(n)$ is empty. Thus the conjecture is only for $n$ and $k$ such that $n$ is odd and $k$ is even.
Armstrong's conjecture is a consequence from the following theorem and Theorem 10.

**Theorem 12.** Let $n$ and $k$ be positive integers. Then

$$ \widetilde{NC}^{(2k)}(2n+1) \cong NC^{(2k)}(n; k). $$

## References

[1] Drew Armstrong, *Generalized noncrossing partitions and combinatorics of Coxeter groups*, Mem. Amer. Math. Soc. **2002** (2009), no. 949.

[2] Christos A. Athanasiadis, *On noncrossing and nonnesting partitions for classical reflection groups*, Electron. J. Combin. **5** (1998), R42.

[3] Christos A. Athanasiadis and Victor Reiner, *Noncrossing partitions for the group $D_n$*, SIAM J. Discrete Math. **18** (2005), no. 2, 397-417.

[4] David Bessis, *The dual braid monoid*, Annales scientifiques de l'Ecole normale supérieure **36** (2003), 647-683.

[5] T. Brady and C. Watt, *Non-crossing partition lattices in finite reflection groups*, Trans. Amer. Math. Soc. **360** (2008), 1983-2005.

[6] Paul H. Edelman, *Chain enumeration and non-crossing partitions*, Discrete Math. **31** (1980), 171-180.

[7] Jang Soo Kim, *New interpretations for noncrossing partitions of classical types*, http://arxiv.org/abs/0910.2036.

[8] Jang Soo Kim, *Chain enumeration of k-divisible noncrossing partitions of classical types*, http://arxiv.org/abs/0908.2641.

[9] C. Krattenthaler and T.W. Müller, *Decomposition numbers for finite Coxeter groups and generalised non-crossing partitions*, http://arxiv.org/abs/0704.0199.

[10] Christian Krattenthaler, *Non-crossing partitions on an annulus*, in preparation.

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

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