Séminaire Lotharingien de Combinatoire 81 (2020), Article B81d

k-INDIVISIBLE NONCROSSING PARTITIONS

HENRI M � UHLE, PHILIPPE NADEAU, AND NATHAN WILLIAMS

Dedicated to Christian Krattenthaler on the occasion of his 60th birthday.

Abstract. For a �xed integer k, we consider the set of noncrossing partitions, where both the block sizes and the di�erence between adjacent elements in a block is 1 mod k. We show that these k-indivisible noncrossing partitions can be recovered in the setting of subgroups of the symmetric group generated by (k+ 1)- cycles, and that the poset of k-indivisible noncrossing partitions under re�nement order has many beautiful enumerative and structural properties. We encounter k-parking functions and some special Cambrian lattices on the way, and show that a special class of lattice paths constitutes a nonnesting analogue.

1. Introduction

1.1. Classical noncrossing partitions. For an integer n ≥ 0, a (classical) noncrossing partition of the set [n+ 1] =^{def} {1, 2, …, n+ 1} is a set partition whose blocks have pairwise disjoint convex hulls when drawn on a regular (n+ 1)-gon with vertices labeled clockwise by [n+ 1] (Figure 1 illustrates some examples).

1 2 3 4 5 6 7 8 9 10 11 12  1 \overline{1} 2 \overline{2} 3 \overline{3} 4 \overline{4} 5 \overline{5} 6 \overline{6} 7 \overline{7} 8 \overline{8} 9 \overline{9} 10 \overline{10} 11 \overline{11} 12 \overline{12}  \overline{1} \overline{2} \overline{3} \overline{4} \overline{5} \overline{6} \overline{7} \overline{8} \overline{9} \overline{10} \overline{11} \overline{12}

Figure 1. The leftmost image represents the noncrossing partition (1 2 7)(3 4 5 6)(8)(9 11)(10)(12). The middle image then illustrates the computation of its Kreweras complement (1)(2 6)(7 8 11 12)(3)(4)(5)(9 10), shown on the right.

Recall that the symmetric group 𝔖_{n+ 1} is generated by the set of transpositions {(i j)}_{1≤i<j≤n+ 1} , and the noncrossing partitions NC_{n+ 1} are naturally identi�ed (by sending blocks to cycles) with the elements occurring as pre�xes of reduced factorizations of the long cycle (1 2 … n+ 1) into transpositions [5]. Noncrossing partitions lie at the intersection of many seemingly unrelated areas of mathematics�for more information, we refer to the surveys [3, 23, 27].

Key words and phrases. noncrossing partition, Hurwitz action, parking function, Cambrian lattice, nonnesting partition.

1.2. k-Indivisible noncrossing partitions. Fix integers k, n ≥ 1. Throughout this article we write

N =^{def} kn + 1,

and we denote by 𝔖_{N;k} the subgroup of 𝔖_{N} generated by the set of all (k+ 1)- cycles.

The previous construction of noncrossing partitions as pre�xes of reduced factorizations of the long cycle into transpositions naturally generalizes to 𝔖_{N;k} as the set NC_{N;k} of elements occurring as pre�xes of reduced factorizations of the

cycle c_{N} =^{def} (1 2 … N) into (k+ 1)-cycles. In reference to Edelman and Armstrong’s k-divisible noncrossing partitions (noncrossing partitions whose block sizes are all divisible by k) [1, 10], we call the elements of NC_{N;k} the k-indivisible noncrossing partitions. Our �rst result characterizes NC_{N;k} as a condition on block sizes, explaining the nomenclature �k-indivisible.�

Recall that the Kreweras complement of a noncrossing partition w ∈ NC_{N} is de�ned as the coarsest noncrossing partition Krew(w) ∈ NC_{N} that can be drawn on the dual N-gon without intersecting w (see Figure 1 for an illustration).

Theorem 1.1. Fix k, n ≥ 1 and write N = nk + 1. The following are equivalent. (i) w is a k-indivisible noncrossing partition on [N]. (ii) w is a noncrossing partition on [N] and all cycles in both w and its Kreweras

complement Krew(w) have lengths 1 mod k. (iii) w is a noncrossing partition on [N], all its cycles have lengths 1 mod k, and if i < j

are consecutive in a cycle of w, then j − i ≡ 1 (mod k).

We prove Theorem 1.1 in Section 3.3. Note that the k-indivisible noncrossing partitions recover the ordinary noncrossing partitions when k = 1 (so that the congruence constraint on the lengths of blocks is trivially satis�ed), and the constructions of [25] when k = 2.

This combinatorial description allows us to enumerate NC_{N;k}.

Theorem 1.2. The cardinality of NC_{N;k} is

\frac{2}{N + 1} \binom{N + n}{n} .

1.3. The k-indivisible noncrossing partition poset. As with the classical noncrossing partitions, the set of k-indivisible noncrossing partitions is naturally ordered by re�nement. We denote this poset by NC_{N;k}. In contrast to when k = 1, NC_{N;k} is generally not a lattice. Nevertheless, we prove the following formula for its zeta polynomial at the end of Section 4.

Theorem 1.3. For k, n ≥ 1, the number of q-multichains of NC_{N;k} is

Z_{N;k}(q + 1) = \frac{q + 1}{Nq + 1} \binom{Nq + n}{n} .

The remainder of the paper is devoted to generalizing enumerative results, objects, and bijections from the classical noncrossing partition lattice (obtained by specializing k to 1) to NC_{N;k}.

k-INDIVISIBLE NONCROSSING PARTITIONS 3

1.4. k-Parking functions. In Section 5, we give a bijection from the maximal chains of NC_{N;k} to k-parking functions, generalizing [30, Theorem 5.1].

1.5. Cambrian lattices. In Section 6, we give a bijection from the maximal chains of NC_{N;k} up to commutation equivalence, to (2k+ 2)-angulations of a convex 2Ngon following [24]. This construction recovers an instance of a 2k-Cambrian lattice from [32].

1.6. Nonnesting partitions. In Section 7 we construct the k-indivisible nonnesting partitions as the order ideals of a subposet of a triangular poset. These are shown to be in bijection with the k-indivisible noncrossing partitions.

1.7. Open problems. We conclude in Section 8 with some open problems: we conjecture that NC_{N;k} is EL-shellable, and we conjecture many enumerative properties of a certain poset whose elements are the q-multichains of NC_{N;k}.

2. Preliminaries

2.1. Hurwitz Action. Let G be a group and let n ≥ 1. The i-th standard generator σ_{i} of the braid group 𝔅_{n} sends (g_{1}, g_{2}, …, g_{n}) ∈ G^{n} to

(g_{1}, g_{2}, …, g_{i−1} , g_{i+1} , g_{i+1}^{−1} g_{i}g_{i+1} , g_{i+2} , …, g_{n}) ∈ G^{n}.

Its inverse σ_{i}^{−1} sends (g_{1}, g_{2}, …, g_{n}) ∈ G^{n} to

(g_{1}, g_{2}, …, g_{i−1} , g_{i}g_{i+1} g_{i}^{−1} , g_{i}, g_{i+2} , …, g_{n}) ∈ G^{n}.

This is a group action of 𝔅_{n} on G^{n}, and it is clear that it does not change the product of such a tuple. We call this the Hurwitz action.

2.2. k-Absolute order. Let K ≥ 1 be an integer, and let 𝔖_{K} be the symmetric group on [K]. For k ≥ 1 let C_{K;k} be the set of all (k+ 1)-cycles of 𝔖_{K} and let 𝔖_{K;k} ≤ 𝔖_{K} denote the subgroup generated by C_{K;k}. If k is odd, then 𝔖_{K;k} = 𝔖_{K}; if k is even, then 𝔖_{K;k} is the alternating group 𝔄_{K} on [K].

It will be useful to have some notation regarding multiplication by cycles. Let (i j) be a transposition. If w ∈ 𝔖_{K} has two distinct cycles containing i and j, we may write w = w′(s_{i})(s_{j}) where s_{i} and s_{j} are sequences ending with i and j, respectively. Then w · (i j) = w′(s_{i} s_{j}), and we say that we join the two cycles. More generally, given m disjoint cycles of w, we may join them in a new cycle by multiplying by an m-cycle having exactly one element in common with each of them. The inverse operation is called cutting a cycle.

Let ℓ_{k}: 𝔖_{K;k} → be the map that assigns to w ∈ 𝔖_{K;k} the minimum length of a factorization of w into (k+ 1)-cycles. The k-absolute order is the following partial order on 𝔖_{K;k}:

w ≤_{k} w′ if and only if ℓ_{k}(w) + ℓ_{k}(w^{−1} w′) = ℓ_{k}(w′).

Since the set of (k+ 1)-cycles is a full 𝔖_{K}-conjugacy class, the map ℓ_{k} is invariant under 𝔖_{K}-conjugation by [25, Proposition 2.3]. We are only aware of simple formulas for ℓ_{k} for k ∈ {1, 2, 3}. For example, for k = 1, if we let cyc(w) denote the number of cycles of w ∈ 𝔖_{K}, then ℓ_{1}(w) = K − cyc(w). For k = 2, we have ℓ_{2}(w) = K − ocyc(w) where ocyc(w) denotes the number of odd cycles of w ∈ 𝔄_{K} [25]. Some general bounds for ℓ_{k} are given in [16].

2.3. (1 mod k)-Permutations. There is a subset of elements of 𝔖_{K;k} for which ℓ_{k} has a similarly simple form.

De�nition 2.1. A permutation w ∈ 𝔖_{K;k}is 1 mod k if�when written as a product of disjoint cycles�all cycles of w have length 1 mod k. We denote by 𝔖_{K;k}^{(1)} the set of all (1 mod k)-permutations.

Lemma 2.2. A permutation w ∈ 𝔖_{K} is 1 mod k if and only if ℓ_{k}(w) = \frac{K−cyc(w)}{k} .

In particular this specializes to the above mentioned well-known fact that ℓ_{1}(w) = K − cyc(w) for any permutation w.

Proof. Let w ∈ 𝔖_{K;k}, and let t be a (k+ 1)-cycle. Note that t can be written as a product of k transpositions, and so by analyzing the cut and join possibilities, we obtain that cyc(wt) ≥ cyc(w) − k. Furthermore, equality holds if and only if t has at most one element in common with each cycle of w�in this case wt is obtained from w by joining the k+ 1 cycles of w that have a common element with t. Now �x a minimal factorization of w into (k+ 1)-cycles. By induction, starting from the fact that the identity permutation has K cycles of length 1, the previous inequality implies that any w ∈ 𝔖_{K;k} satis�es cyc(w) ≥ K − kℓ_{k}(w), and equality occurs if and only if w was built by joining k+ 1 cycles at a time, as described above.

In the case of equality, w is 1 mod k since joining k + 1 cycles of length 1 mod k gives back another cycle of length 1 mod k. Conversely, every 1 mod k permutation can be written as a product of \frac{K−cyc(w)}{k} elements of C_{K;k}, for instance by factoring each of its cycles as follows:

(a_{1} a_{2} … a_{sk+1} ) = (a_{1} … a_{k+1} ) · (a_{k+1} … a_{2k+1} ) ⋯(a_{(s−1)k+1} … a_{sk+1} ). □

The covering relations ⋖_{k} of the partial order ≤_{k} in which the top element belongs to 𝔖_{K;k}^{(1)} are particularly simple to describe.

Corollary 2.3. Let w ∈ 𝔖_{K;k}^{(1)} and u ∈ 𝔖_{K;k}. Then one has u ⋖_{k} w if and only if u can be obtained from w by cutting one cycle of w into k + 1 cycles of length 1 mod k.

Proof. This is an immediate corollary of the proof of Lemma 2.2. □

Corollary 2.4. If w ∈ 𝔖_{K;k}^{(1)}and u ≤_{k} w, then u ∈ 𝔖_{K;k}^{(1)}, u^{−1} w ≤_{k} w and u^{−1} w ∈ 𝔖_{K;k}^{(1)}.

Proof. That u ∈ 𝔖_{K;k}^{(1)} follows from Corollary 2.3 by induction. So �x a reduced factorization w = t_{1} · t_{2} ⋯t_{l} with t_{i} ∈ C_{K;k} for i ∈ [l] such that u = t_{1}t_{2} ⋯t_{s} for some s ∈ [l]. Now, t_{s+1} t_{s+2} ⋯t_{l} = u^{−1} w. The Hurwitz action allows us to write w = t_{s+1} ⋯t_{l}t′_{1}t′_{2} ⋯t′_{s} for certain t′_{i}∈ C_{K;k}, so that u^{−1} w ≤_{k} w as well. □

3. k-Indivisible noncrossing partitions

3.1. k-Indivisible noncrossing partitions. For k, n ≥ 1 and N = kn + 1, we �x the long cycle c_{N} =^{def} (1 2 … N). Notice that c_{N} ∈ 𝔖_{N,k}^{(1)}, so that ℓ_{k}(c_{N}) = n by Lemma 2.2.

De�nition 3.1. The k-indivisible noncrossing partitions are the elements of

NC_{N;k} =^{def} {w ∈ 𝔖_{N,k} | w ≤_{k} c_{N}}.

We denote the corresponding poset by NC_{N;k} =^{def} (NC_{N;k}, ≤_{k}). For k = 1, the poset NC_{n+ 1;1} = NC_{n+ 1} is isomorphic to the lattice of noncrossing partitions of [n+ 1] [5]. Figure 2 illustrates NC_{N;k} for n = 3 and k = 2.

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7

Figure 2. The poset NC_{7;2}.

Remark 3.2. Let Π_{K;k}^{(i)} be de�ned as the poset of all partitions of [K] with block sizes congruent to i mod k. Some history and results regarding these posets is summarized in [35, Examples 4.3.4 and 4.3.5, Exercise 4.3.6, and Remark 4.3.7]� and we are not aware of any substantive results beyond i = 0, 1.

The lattices Π_{K;k}^{(0)}�rst appeared in [33], and were subsequently studied by Stanley and Sagan in [26, 29]. The corresponding noncrossing partitions were considered by Edelman [10], and extended to �nite Coxeter groups by Armstrong [1].

The posets Π_{K;k}^{(1)} were studied in [9]. However, as far as we know, the corresponding noncrossing partitions have not previously been considered. On the other hand, the study of the maximal chains in NC_{N;k} is a classical problem, for example when phrased in the language of transitive factorizations and cacti. We revisit some of the combinatorics related to these maximal chains in Sections 5 and 6.

3.2. The Kreweras complement. As in Section 1.1, we graphically represent w ∈ NC_{N} as the convex hull of the cycles of w on a regular N-gon whose vertices are labeled clockwise by [N]. The terminology �noncrossing partition� is justi�ed by the fact that no two convex hulls intersect in this representation.

The Kreweras complement of w ∈ NC_{N} is the noncrossing partition Krew(w) =^{def} w^{−1} c_{N}. In the graphical representation, this can be visualized by drawing the convex hulls of w on a 2N-gon labeled clockwise by \{1, ¯1, 2, ¯2, …, N, \overline{N}\}, where the blocks of w use only the non-barred vertices. Then Krew(w) corresponds to the coarsest noncrossing partition that can be drawn using the barred vertices without intersecting the blocks of w (see Figure 1). The following is immediate from Corollary 2.4.

Corollary 3.3. For any w ∈ 𝔖_{N;k}, w ≤_{k} c_{N} implies Krew(w) ≤_{k} c_{N}; that is, NC_{N;k} is stable under Kreweras complementation.

3.3. Combinatorial characterization of k-indivisible noncrossing partitions.

Theorem 1.1. Fix k, n ≥ 1 and write N = nk + 1. The following are equivalent. (i) w is a k-indivisible noncrossing partition on [N]. (ii) w is a noncrossing partition on [N], and w and Krew(w) are 1 mod k. (iii) w is a noncrossing partition on [N], w is 1 mod k, and if i < j are consecutive in

a cycle of w, then j − i ≡ 1 (mod k).

Observe that the additional conditions on cycles in (ii) and (iii) are vacuous if k = 1, so the claim is trivial in this case.

Proof. (i) ⟹ (ii). We assume w ≤_{k} c_{N}. Since c_{N} ∈ 𝔖_{N;k}^{(1)}, by Corollary 2.4, we

have w, Krew(w) ∈ 𝔖_{N;k}^{(1)}. Now ℓ_{k}(w) + ℓ_{k}(Krew(w)) = n which can be written as ℓ_{1}(w) + ℓ_{1}(Krew(w)) = nk by Lemma 2.2. This means that w ≤_{1} c_{N}, that is, w is a noncrossing partition.

(ii) ⟹ (iii). Let w ∈ NC_{N;1} such that both w and Krew(w) are 1 mod k. Let i, j be two consecutive entries in a cycle of w with i < j. We want to show that j − i ≡ 1 (mod k). This is trivial if j = i + 1, and we will assume by induction that this holds for any consecutive entries i_{1} < j_{1} in a cycle of w such that j_{1} − i_{1} < j − i. Consider the maximal (with respect to nesting) cycles of w that are between i and j: their number is a multiple of k because this number is one less than the length of a cycle of Krew(w), which is 1 mod k. Order these cycles ζ_{1}, ζ_{2}, …, ζ_{mk} so that max(ζ_{p}) < min(ζ_{p+1} ). In fact, if a_{p} = min(ζ_{p}) and b_{p} = max(ζ_{p}), we have b_{p} = a_{p+1} − 1 for p = 1, …, mk − 1, with boundary conditions a_{1} = i + 1 and b_{mk} = j − 1. We can therefore write

j − i = ∑_{p=1}^{mk}(b_{p} − a_{p}) + 1 + mk.

By induction each ζ_{p} satis�es the cycle conditions in (iii), which immediately implies b_{p} − a_{p} ≡ 0 (mod k). Therefore the expression above for j − i is 1 mod k as desired.

(iii) ⟹ (i). Given w a noncrossing partition satisfying the mod k conditions of (iii), we want to prove w ≤_{k} c_{N}. If w = c_{N} we are done, so we suppose that w ≠ c_{N}. We will construct a w′ ∈ 𝔖_{N;k} such that w ⋖_{k} w′ and w′ also satis�es

Consider the cycle ζ_{0} of w containing 1, ζ_{0} = (u_{1} < u_{2} < ⋯< u_{kr_{1}+1} ) with u_{1} = 1. Since w ≠ c_{N}, either there exists q ∈ [kr_{1}] such that u_{q+1} − u_{q} > 1, or u_{i} = i for all i, in which case pick q = u_{q} = kr_{1} + 1 < N and set u_{q+1} = N + 1. Now consider the maximal cycles from left to right ζ_{1}, …, ζ_{d} between u_{q} and u_{q+1} , so d ≥ 1 by our choice of q . For 1 ≤ p ≤ d, write a_{p}, b_{p} for the minimal and maximal elements of ζ_{p}, so that we get

u_{q+1} − u_{q} = ∑_{p=1}^{d} (b_{p} − a_{p}) + 1 + d.

Now we have b_{p} − a_{p} ≡ 0 (mod k) as above. Since u_{q+1} − u_{q} ≡ 1 (mod k), it follows that d is a multiple of k, and so d ≥ k because d ≥ 1. Now ζ_{0}ζ_{1} ⋯ζ_{k} · (u_{p} b_{1} … b_{k}) is an increasing cycle that is derived from joining ζ_{0}, ζ_{1}, …, ζ_{k}. Thus w′ = w · (u_{p} b_{1} … b_{k}) satis�es all conditions in (iii), so by induction we have w′≤_{k} c_{N}. Moreover, we have w ⋖_{k} w′by Corollary 2.3, so that w ≤_{k} c_{N}. □

Remark 3.4. Theorem 1.1 implies that the name �k-indivisible noncrossing partition� for the elements of NC_{N;k} is indeed justi�ed: every such element corresponds to a noncrossing partition of [N]. This property is not a priori clear from De�nition 3.1.

As such, each cycle of w ∈ NC_{N;k} can be written such that its entries form an increasing sequence of integers.

Theorem 1.1 implies that NC_{N;k} is an interval in (𝔖_{N;k}, ≤_{k}) .

Corollary 3.5. The poset NC_{N;k} is an induced subposet of NC_{N;1}: for all w, w′∈ NC_{N;k}, w ≤_{k} w′if and only if w ≤_{1} w′.

Proof. The reader may �nd it helpful to consider the graphical representation of Krew given in Figure 1. Let w, w′ ∈ NC_{N;k}. By Theorem 1.1, each of w, w′, Krew(w), Krew(w′) is 1 mod k.

Assume �rst that w ≤_{k} w′, that is, ℓ_{k}(w) + ℓ_{k}(w^{−1} w′) = ℓ_{k}(w′). Then by Theorem 1.1 which applies to all three permutations due to Corollary 2.4, we get \frac{ℓ_{1}(w)}{k} + \frac{ℓ_{1}(w^{−1} w′)}{k} = \frac{ℓ_{1}(w′)}{k}, which after multiplying by k tells us precisely w ≤_{1} w′.

Conversely, assume w ≤_{1} w′. Because w, w′ ∈ NC_{N;k}, this simply means that the supports of the cycles of w are included in those of w′. We can thus assume without loss of generality that w′ consists of a single cycle. Moreover, because of the invariance of ℓ_{k} under conjugation, we can even assume w′ = c_{N′} = (1 2 … N′) for N′ = mk + 1 with m ≤ n. So we have w ≤_{1} c′_{N} and w is a noncrossing partition on [N′]. By Theorem 1.1, using the characterization (ii), it follows that w ≤_{k} c_{N′}, which achieves the proof. □

4. Enumerative properties of k-indivisible noncrossing partitions

For integers n, p, r ≥ 1, let us de�ne the Raney number by

Ran(n, p, r) =^{def} \frac{r}{np + r} \binom{np + r}{n} .

The specialization Ran(n, 2, 1) recovers the Catalan number \frac{1}{n+1} \binom{2n}{n}, while Ran(n, p, 1) recovers the Fu��Catalan number \frac{1}{(p−1)n+1} \binom{pn}{n}.

The Raney numbers satisfy the following Catalan-like recurrence.

Lemma 4.1 ([15, p. 202, Equation (5.63)]). For integers n, p, r, s ≥ 1 we have

Ran(n, p, r + s) = ∑_{i=0}^{n} Ran(i, p, r) · Ran(n − i, p, s) .

Remark 4.2. Let us say that a plane rooted tree is k-divisible if each vertex has 0 mod k-many children. It is (k+ 1)-ary if every non-leaf vertex has exactly k + 1 children.

It is well known that k-divisible trees with kn + 1 vertices are enumerated by the Fu��Catalan number Ran(n, k + 1, 1). Such trees T are in bijection with (k+ 1)- ary trees T′ with n non-leaf vertices. Indeed, start at the root of T. If it has no children, it must be that n = 0, and we set T′ = T. Otherwise, by assumption, the root of T has ik children. We keep the �rst k of them, and add a new root child to which we attach all the remaining (i − 1)k root children. We now proceed inductively, until we obtain the desired tree T′. This process is clearly reversible (and thus bijective), by contracting along right-most children.

4.1. Cardinality.

Theorem 1.2. The cardinality of NC_{N;k} is

Ran(n, k + 1, 2) = \frac{2}{N + 1} \binom{N + n}{n} .

Proof. We will prove this bijectively (see Corollary 4.8 for another proof); the reader is invited to look at Figure 3 which illustrates the bijection.

We �rst map w ∈ NC_{N;k} to the factorization c_{N} = w · Krew(w) and apply a classical bijection due to Goulden and Jackson [13, Theorem 2.1]. Since they are reduced, factorizations of the form w · Krew(w) are in bijection with the set of plane edge-rooted trees with N edges and N + 1 vertices each of degree 1 mod k, with vertices alternately colored white and black. The white vertices correspond to cycles in w, and the black vertices to the cycles in Krew(w) as follows. Starting from the root edge (moving from white to black), we walk around the tree (keeping the tree to our right). Each of the N edges of the tree is encountered twice, and we label them by the order in which they are visited when moving from a white to a black vertex. Reading the cyclic sequence of edge labels clockwise around the white vertices recovers the cycles of w; and similarly for the black vertices and Krew(w).

Break this tree into two by deleting the root edge, and root both of the resulting trees using the vertex adjacent to the deleted root edge. Since both w and Krew(w) are 1 mod k, each of the vertices in the resulting pair of trees has a multiple of k many children. By Remark 4.2, the resulting trees are counted by an appropriate Fu��Catalan number, from which we conclude that

(1)  |NC_{N;k}| = ∑_{i=0}^{n} Ran(i, k + 1, 1) · Ran(n − i, k + 1, 1) .

Hence, |NC_{N;k}| satis�es the recursion given in Lemma 4.1, and by checking the initial condition, we see that |NC_{N;k}| = Ran(n, k + 1, 2) as desired. □

17 18 19 15 14 20 21 22 16 1 23 24 25 13 12 11 2 3 4 5 9 10 6 7 8

Figure 3. Illustration of the bijection from Theorem 1.2 for n = 8, k = 3, and w = (1 14 15 16 20 21 22)(2 3 4 5 9 10 11) ∈ NC_{25;3}. On the left is the plane, edge-rooted bicolored tree corresponding to w · Krew(w), in the middle the pair of 3-divisible trees with a total of 26 vertices, and on the right the pair of 4-ary trees with a total of 8 non-leaf vertices.

Remark 4.3. Recall from [10] that k-divisible noncrossing partitions are counted by Fu��Catalan numbers, too. Therefore, (1)essentially states that any k-indivisible noncrossing partition can be broken into a pair of k-divisible noncrossing partitions.

4.2. Multichains. A q-multichain in NC_{N;k} is a tuple (w_{1}, w_{2}, …, w_{q}) ∈ (𝔖_{N;k})^{q} with w_{1} ≤_{k} w_{2} ≤_{k} ⋯≤_{k} w_{q} ≤_{k} c_{N}.

Lemma 4.4. Each q-multichain (u_{1}, u_{2}, …, u_{q}) in NC_{N;k} corresponds bijectively to a factorization v_{1}v_{2} ⋯v_{q+1} = c_{N} such that

ℓ_{1}(v_{1}) + ℓ_{1}(v_{2}) + ⋯+ ℓ_{1}(v_{q+1} ) = kn,

and v_{i} ∈ 𝔖_{N;k}^{(1)} for i ∈ [q + 1].

Proof. Let u_{0} = id and u_{q+1} = c_{N}, and de�ne v_{i} = u_{i−1}^{−1} u_{i} for i ∈ [q + 1]. We immediately see that v_{1}v_{2} ⋯v_{q+1} = c_{N}. Moreover, since u_{i} ≤_{k} u_{i+1} we conclude from the de�nition that ℓ_{k}(v_{i+1} ) = ℓ_{k}(u_{i+1} ) − ℓ_{k}(u_{i}). We obtain

∑_{i=1}^{q+1} ℓ_{k}(v_{i}) = ∑_{i=1}^{q+1} (ℓ_{k}(u_{i}) − ℓ_{k}(u_{i−1} )) = ℓ_{k}(u_{q+1} ) − ℓ_{k}(u_{0}) = ℓ_{k}(c_{N}) − ℓ_{k}(id) = n.

We conclude from Corollary 2.4 that v_{i} ∈ 𝔖_{N;k}^{(1)} and the �nal claim follows then from Lemma 2.2. Conversely, given a factorization v_{1}v_{2} ⋯v_{q+1} = c_{N}, it is easily checked that setting u_{m} := v_{1} ⋯v_{m} for m ∈ [q] gives the desired q-multichain (u_{1}, u_{2}, …, u_{q}). □

Let C = (w_{1}, w_{2}, …, w_{q}) be a q-multichain in NC_{N;k}, and let w_{0} = id, w_{q+1} =

c_{N}. We de�ne the rank jump vector of C by r(C) =^{def} (r_{1}, r_{2}, …, r_{q+1} ), where r_{i} = ℓ_{k}(w_{i}) − ℓ_{k}(w_{i−1} ) for i ∈ [q + 1]. We write Z_{N;k}(q + 1) for the number of qmultichains of NC_{N;k}.

Theorem 4.5. The number of q-multichains of NC_{N;k} that have the rank jump vector (r_{1}, r_{2}, …, r_{q+1} ) is

\frac{1}{N} ∏_{i=1}^{q+1} Ran(r_{i}, 1 − k, N) = \frac{1}{N} ∏_{i=1}^{q+1} \frac{N}{N − (k − 1)r_{i}} \binom{N − (k − 1)r_{i}}{r_{i}} .

Proof. Let C = (w_{1}, w_{2}, …, w_{q}) be a q-multichain with rank jump vector r(C) = (r_{1}, r_{2}, …, r_{q+1} ), where r_{i} = ℓ_{k}(w_{i}) − ℓ_{k}(w_{i−1} ). By Lemma 4.4, C corresponds to

a factorization v_{1}v_{2} ⋯v_{q+1} = c_{N}, where v_{i} ∈ 𝔖_{N;k}^{(1)} and r_{i} = ℓ_{k}(v_{i}) for i ∈ [q + 1].

By Lemma 2.2 we have r_{i} = ℓ_{1}(v_{i})/k. If we suppose that v_{i} has exactly p_{j}^{(i)} cycles of size kj + 1, for j ≥ 1, then [20, Theorem 5] implies that the number of factorizations is

N^{q} ∏_{i=1}^{q+1} \frac{1}{kn − kr_{i} + 1} \binom{kn − kr_{i} + 1}{p_{1}^{(i)}, p_{2}^{(i)}, …} ,

where r_{i} = ∑ _{j} jp_{j}^{(i)}. We now sum over all such sequences (p_{1}^{(i)}, p_{2}^{(i)}, …) by using [20, Lemma 4] and �nd that the number of all such factorizations is

N^{q} ∏_{i=1}^{q+1} \frac{1}{kn − kr_{i} + 1} \binom{kn − (k − 1)r_{i}}{r_{i}} = \frac{1}{N} ∏_{i=1}^{q+1} \frac{N}{N − kr_{i}} \binom{N − 1 − (k − 1)r_{i}}{r_{i}} .

This formula is equivalent to the formula in the statement. □

Corollary 4.6. The number of maximal chains of NC_{N;k} is N^{n−1} , and the number of elements of NC_{N;k} of rank l is

\frac{N}{(N − (k − 1)l)(N − (k − 1)(n − l))} \binom{N − (k − 1)l}{l} \binom{N − (k − 1)(n − l)}{n − l} .

Proof. Maximal chains of NC_{N;k} correspond by de�nition to (n − 1)-multichains with rank jump vector (1, 1, …, 1), while elements of rank l correspond to 1multichains with rank jump vector (l, n − l). The result now follows from Theorem 4.5. □

Remark 4.7. The result on the number of maximal chains of NC_{N;k} has been obtained before by Goulden and Jackson in [14, Corollary 5.1], and was later extended by Biane in [4, Theorem 1].

4.3. Zeta polynomial and M�obius function. We may now conclude Theorem 1.3.

Theorem 1.3. For k, n ≥ 1, the number of q-multichains of NC_{N;k} is

Z_{N;k}(q + 1) = \frac{q + 1}{Nq + 1} \binom{Nq + n}{n} .

Proof. In order to determine Z_{N;k}(q + 1), we have to sum the formula from Theorem 4.5 over all possible rank jump vectors. Recall from [25, Lemma 5.5] that for integers a, a_{1}, a_{2}, …, a_{r}, b, n with a = a_{1} + a_{2} + ⋯+ a_{r} we have

∑_{n_{1}+n_{2}+··· +n_{r}=n} ∏_{i=1}^{r} Ran(n_{i}, b, a_{i}) = Ran(n, b, a).

We obtain

Z_{N;k}(q + 1) = ∑_{r_{1}+r_{2}+··· +r_{q+1} =n} \frac{1}{N} ∏_{i=1}^{q+1} Ran(r_{i}, 1 − k, N)

= \frac{1}{N} ( ∑_{r_{1}+r_{2}+··· +r_{q+1} =n} ∏_{i=1}^{q+1} Ran(r_{i}, 1 − k, N) )

= \frac{Ran(n, 1 − k, (q + 1)N)}{N}

= Ran(n, qk + 1, q + 1)

= \frac{q + 1}{Nq + 1} \binom{Nq + n}{n} .  □

Specializing Theorem 1.3 at q = 1 gives a second (non-bijective) proof of Theorem 1.2.

Corollary 4.8. The cardinality of NC_{N;k} is Ran(n, k + 1, 2).

Proof. Every element of NC_{N;k} can be regarded as a 1-multichain of NC_{N;k}. The claim thus follows by plugging in q = 1 into Theorem 1.3. □

Since NC_{N;k} is a poset with a least and a greatest element, we can de�ne the M�obius invariant of NC_{N;k}; which is the value μ(NC_{N;k}) of the M� obius function of NC_{N;k} applied to id and c_{N}. See also [31, Sections 3.8 and 3.12].

Corollary 4.9. The M�obius invariant of NC_{N;k} is

μ(NC_{N;k}) = (−1)^{n}Ran(n, 2k, 1) = \frac{(−1)^{n}}{2nk + 1} \binom{2nk + 1}{n} .

Proof. The numbers Z_{N;k}(q) can be regarded as evaluations of a polynomial over the integers. It follows for instance from [31, Proposition 3.12.1(c)] that μ(NC_{N;k}) = Z_{N;k}(−1). The claim follows from application of Theorem 1.3, by using the equality \binom{−a}{b} = (−1)^{b}\binom{a+b−1}{b} for positive integers a, b. □

4.4. m-Divisible k-indivisible noncrossing partitions. In the spirit of [1, 10] we de�ne a partial order on the set of multichains of NC_{N;k}. For an m-multichain C = (x_{1}, x_{2}, …, x_{m}) of NC_{N;k} we de�ne the delta sequence δ_{o}(C) = (d_{0}; d_{1}, …, d_{m}), where d_{i} = x_{i}^{−1} x_{i+1} for 0 ≤ i ≤ m, and where we denote by x_{0} the identity and by x_{m+1} the long cycle c_{N}.

For two such multichains C, C′ with δ_{o}(C) = (d_{0}; d_{1}, …, d_{m}) and δ_{o}(C′) = (d′_{0}; d′_{1}, …, d′_{m}) set C ≤_{k} C′ if and only if d_{i} ≥_{k} d′_{i} for 1 ≤ i ≤ m. Let NC_{N;k}^{(m)} denote the corresponding poset.

An earlier version of this article contained Corollaries 4.11�4.13 as conjectures. C. Krattenthaler has suggested the following generalization of Theorem 4.5 to us.

Theorem 4.10 (C. Krattenthaler). The number of q-multichains of NC_{N;k}^{(m)} that have the rank jump vector (r_{1}, r_{2}, …, r_{q+1} ) is

\frac{1}{N} Ran(r_{1}, 1 − k, N) ∏_{i=2}^{q+1} Ran(r_{i}, 1 − k, mN)

= \frac{1}{N − (k − 1)r_{1}} \binom{N − (k − 1)r_{1}}{r_{1}} ∏_{i=2}^{q+1} \frac{mN}{mN − (k − 1)r_{i}} \binom{mN − (k − 1)r_{i}}{r_{i}} .

Proof. Following [20, Corollary 12], any such multichain corresponds to a unique factorization

(2) c_{N} = u_{0}^{(1)}(v_{1}^{(2)}v_{1}^{(3)} ⋯v_{1}^{(q+1)} )(v_{2}^{(2)}v_{2}^{(3)} ⋯v_{2}^{(q+1)} ) ⋯(v_{m}^{(2)}v_{m}^{(3)} ⋯v_{m}^{(q+1)} )

into elements from NC_{N;k}^{(m)}, where

ℓ_{1}(u_{0}^{(1)}) + ∑_{i,j} ℓ_{1}(v_{j}^{(i)}) = kn

with ℓ_{1}(u_{0}^{(1)}) = kr_{1} and

ℓ_{1}(v_{1}^{(i)}) + ℓ_{1}(v_{2}^{(i)}) + ⋯+ ℓ_{1}(v_{m}^{(i)}) = kr_{i}

for i ∈ {2, 3, …, q + 1}.

First suppose that ℓ_{1}(v_{j}^{(i)}) = ks_{j}^{(i)}, with the s_{j}^{(i)}’s �xed, such that

(3)  s_{1}^{(i)} + s_{2}^{(i)} + ⋯+ s_{m}^{(i)} = r_{i}

for i ∈ {2, 3, …, q + 1}. The number of factorizations (2)satisfying (3)is according to Theorem 4.5 precisely

(4)  \frac{1}{N} Ran(r_{1}, 1 − k, N) ∏_{i=2}^{q+1} ∏_{j=1}^{m} Ran(s_{j}^{(i)}, 1 − k, N).

The desired number of multichains is now obtained by summing (4) over all possible s_{j}^{(i)}’s for which (3) holds. In view of Lemma 4.1 we conclude that this number is

\frac{1}{N} Ran(r_{1}, 1 − k, N) ∏_{i=2}^{q+1} Ran(r_{i}, 1 − k, mN).  □

We obtain the following corollaries.

Corollary 4.11. For k, m, m ≥ 1, the number of q-multichains of NC_{N;k}^{(m)} is

Z_{NC{(m) \atop N;k}}(q + 1) = Ran(n, mkq + 1, mq + 1) = \frac{mq + 1}{mNq + 1} \binom{mNq + n}{n} .

Proof. We need to sum the formula from Theorem 4.10 over all possible rank jump vectors using Lemma 4.1, and obtain

Z_{NC{(m) \atop N;k}}(q + 1) = \frac{1}{N} Ran(n, 1 − k, N + qmN).

This formula is equivalent to the formula in the statement. □

Corollary 4.12. For k, m, n ≥ 1, the number of maximal chains in NC_{N;k}^{(m)} is m^{n}N^{n−1} .

Proof. This follows from Theorem 4.10 by setting q = n and r_{1} = 0 and r_{2} = r_{3} = ⋯= r_{n+1} = 1. □

Observe that NC_{N;k}^{(m)} has several minimal elements when m > 1. Let N̂C_{N;k}^{(m)}

denote the poset that is created from NC_{N;k}^{(m)} by adding a least element. Let \overline{NC}_{N;k}^{(m)}

denote the poset that is created from NC_{N;k}^{(m)} by merging all minimal elements into one.

Corollary 4.13. We have

μ(N̂C_{N;k}^{(m)}) = (−1)^{n−1} Ran(n, km, m − 1) = (−1)^{n−1} \frac{m − 1}{Nm − 1} \binom{Nm − 1}{n} ,

as well as

μ(\overline{NC}_{N;k}^{(m)}) = (−1)^{n}( Ran(n, k(m + 1), m) − Ran(n, km, m − 1))

= (−1)^{n} ( \frac{m}{N(m + 1) − 1} \binom{N(m + 1) − 1}{n} − \frac{m − 1}{Nm − 1} \binom{Nm − 1}{n} ) .

Proof. As explained in the proof of [1, Theorem 3.7.7], we have μ(N̂C_{N;k}^{(m)}) = Z_{NC{(m) \atop N;k}}(0), and the claimed formula follows from Corollary 4.11. The formula

for μ(\overline{NC}_{N;k}^{(m)}) follows also from Corollary 4.11 using an argument verbatim to the one in [2, Section 3]. □

For k = 1, the �rst equality in Corollary 4.13 is [1, Theorem 3.7.7], and the second equality is [2, Theorem 3].

Remark 4.14. Corollary 12 of [20] can be used to further re�ne Theorem 4.10 by prescribing the block structure of the �rst element of such a chain.

5. Maximal chains of NC_{N;k} and k-parking functions

5.1. Maximal chains and the Hurwitz action. Let us denote the set of reduced factorizations of c_{N} = (1 2 … N) into (k+ 1)-cycles by Fact_{k}(c_{N}); by construction, these are in bijection with maximal chains in NC_{N;k}; see also Lemma 4.4. Since C_{N;k} is invariant under 𝔖_{N}-conjugation, the Hurwitz action is a bijection on the set of reduced factorizations of w ∈ 𝔖_{N;k} into (k+ 1)-cycles.

Theorem 5.1. For k, n ≥ 1 the braid group 𝔅_{n} acts transitively on Fact_{k}(c_{N}).

Proof. This is a special case of [21, Theorem 5.4.11]. One may also give a direct inductive proof as in [25, Proposition 6.2] for the case k = 2. □

We write the entries of a cycle in a factorization t = t_{1}t_{2} ⋯t_{n} ∈ Fact_{k}(c_{N}) in increasing order as t_{i} = (t_{i,1} < t_{i,2} < ⋯< t_{i,k+ 1}), which is well de�ned by Remark 3.4. A factorization t ∈ Fact_{k}(c_{N}) is non-decreasing if t_{1,1} ≤ t_{2,1} ≤ ⋯≤ t_{n,1}.

Lemma 5.2. For k, n ≥ 1 there is an action of the symmetric group 𝔖_{n} on Fact_{k}(c_{N}) which restricts to the permutation action on the set of smallest elements of each factor {t_{i,1}}_{i=1}^{n} .

Proof. Such an action is known to exist for k = 1, see [6,30]; we generalize it here. Consider the simple transposition s_{i} = (i i + 1), and a factorization t = t_{1}t_{2} ⋯t_{n} in Fact_{k}(c_{N}). The action of s_{i} on t is de�ned as follows: it acts as the Hurwitz operator σ_{i} if t_{i,1} < t_{i+1,1} ; as the inverse Hurwitz operator σ_{i}^{−1} if t_{i,1} > t_{i+1,1} ; and as the identity if t_{i,1} = t_{i+1,1} .

One veri�es that s_{i} transposes the values of t_{i,1} and t_{i+1,1} : this uses the fact that the product t_{i}t_{i+1} is an increasing cycle. From this, one easily checks that one can extend this to an action of the symmetric group by showing that the de�ning relations of 𝔖_{n} hold. □

5.2. k-Parking functions. We proved in Corollary 4.6 that the maximal chains of NC_{N;k} are enumerated by N^{n−1} . In this section, we generalize Stanley’s bijection in [30] between maximal chains in the noncrossing partition lattice and parking functions. In recent work, J. Irving and A. Rattan found the same generalization of Stanley’s bijection. We thank them for bringing [17, 18] to our attention at CanaDAM 2019.

For k, n ≥ 1 de�ne a k-parking function of length n to be any permutation of an integer tuple (a_{1}, a_{2}, …, a_{n}) satisfying 1 ≤ a_{i} ≤ k(i − 1) + 1 for i ∈ [n]. We write P_{N;k} for the set of all k-parking functions. We call (a_{1}, a_{2}, …, a_{n}) ∈ P_{N;k} non-decreasing if a_{1} ≤ a_{2} ≤ ⋯≤ a_{n}.

It is a routine application of the cycle lemma (and follows from [36, Theorem 1]) that the number of k-parking functions of length n is N^{n−1} . Note also that there is an obvious 𝔖_{n}-action on P_{N;k}, obtained by permuting the entries.

Theorem 5.3. For k, n ≥ 1, the map from maximal chains in NC_{N;k} to k-parking functions

ϕ: Fact_{k}(c_{N}) → P_{N;k}
t_{1}t_{2} ⋯t_{n} ↦ (t_{1,1}, t_{2,1}, …, t_{n,1})

is a bijection.

Proof. We give a proof based on the k = 1 case from [6]. It is enough to show that ϕ is a bijection between non-decreasing factorizations of c_{N} and non-decreasing kparking functions�indeed the map is clearly equivariant with respect to the symmetric group actions on parking functions and on factorizations from Lemma 5.2.

We show by induction on n that, if t_{1}t_{2} ⋯t_{n} ∈ Fact_{k}(c_{N}) is non-decreasing, then (t_{1,1}, t_{2,1}, …, t_{n,1}) is a non-decreasing k-parking function. To prove this, we �rst claim that if t_{1}t_{2} ⋯t_{n} ∈ Fact_{k}(c_{N}) with t_{1,1} ≤ t_{2,1} ≤ ⋯≤ t_{n,1}, then we must have

t_{n,1} = t_{n,2} − 1 = ⋯= t_{n,k+ 1} − k.

Since we may write the factorization

t_{1}t_{2} ⋯t_{n−1} = c_{N}t_{n}^{−1}
= (1 2 … N)(t_{n,k+ 1} … t_{n,2} t_{n,1})
= (1 2 … t_{n,1} t_{n,k+ 1}+ 1 … N)(t_{n,1}+ 1 … t_{n,2}) ⋯(t_{n,k}+ 1 … t_{n,k+ 1}),

where the last factorization is into disjoint cycles, each of t_{1}, t_{2}, …, t_{n−1} must have support in the set {1, 2, …, t_{n,1}, t_{n,k+ 1} + 1, …, N} (by [6, (F)]). Therefore, each cycle (t_{n,i}+ 1 … t_{n,i+1} ) is trivial, from which the claim follows.

By induction, (t_{1,1}, t_{2,1}, …, t_{n− 1,1}) is a non-decreasing k-parking function of length n − 1. By assumption we have t_{n− 1,1} ≤ t_{n,1}, and since t_{n,1} + k = t_{n,k+ 1} ≤ kn + 1 we conclude t_{n,1} ≤ k(n − 1) + 1. Thus, (t_{1,1}, t_{2,1}, …, t_{n,1}) is a non-decreasing k-parking function of length n. □

6. Cambrian Lattices

Let u = u_{1}u_{2} ⋯u_{n} and v = v_{1}v_{2} ⋯v_{n} be two reduced factorizations of c_{N} into (k+ 1)-cycles. We say that u and v are commutation equivalent if u can be obtained from v by a sequence of Hurwitz moves on adjacent cycles with disjoint support (so that each move acts as a commutation).

Theorem 6.1 ([14, Theorem 5.5]). The number of reduced factorizations of c_{N} into (k+ 1)-cycles up to commutation equivalence is the Fu��Catalan number Ran(n, 2k+ 1, 1).

Remark 6.2. This result was proven for k = 1 by Eidswick and Longyear [11, 22], while Springer solved a more general factorization problem in [28].

More recently, such factorizations for k = 1 were considered in the context of the associahedron by McCammond [24], which led us to develop the combinatorics of this section.

There is another well-known set with this same cardinality.

Theorem 6.3 ([34]). The number of (2k+ 2)-angulations of a convex 2N-gon is given by Ran(n, 2k+ 1, 1).

Following [24, Section 3], we now describe a bijection between the objects of Theorem 6.3 and Theorem 6.1.

Theorem 6.4. For k, n ≥ 1, there is a bijection Θ between the commutation equivalence classes of reduced factorizations of (1 2 … N) into (k+ 1)-cycles, and the set of (2k+ 2)- angulations of a convex 2N-gon.

Proof. Let t = t_{1}t_{2} ⋯t_{n} ∈ Fact_{k}(c_{N}). We visualize t by drawing the convex hulls of the factors t_{1}, t_{2}, …, t_{n} on a convex polygon with N labeled vertices. Since t is a minimal factorization of c_{N}, these convex hulls intersect pairwise in at most one vertex, and every vertex is contained in at least one convex hull. If we were to label these hulls with the order in which the factor appeared this would be a bijection�forgoing these labels records only the commutation class of the factorization: for every vertex at which at least two convex hulls meet, we can determine the order of the corresponding factors by taking the order

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Θ Θ inverse Hurwitz move

clockwise diagonal move

Figure 4. Illustration of the bijection Θ from Theorem 6.4 for n = 5 and k = 3.

counterclockwise around the vertex inside the polygon. This produces a partial order on the convex hulls, every linear extension of this partial order is a reduced factorization of c_{N}, and any two linear extensions di�er only by a commutation of letters.

We now perform a procedure very similar to the Kreweras complement on these unlabeled convex hulls. Insert a vertex labeled ā in between a and a + 1 (where we identify N + 1 and 1). When two convex hulls intersect in a vertex a, there is a unique vertex b̄ that lies �opposite� to a between the convex hulls intersecting in a. Connect a and b̄ by a line segment, which we call a diagonal. Two diagonals are adjacent if they intersect a common convex hull. Removing the convex hulls leaves only the diagonals, which by construction form a (2k+ 2)- angulation Θ(t) of a 2N-gon.

Conversely, any diagonal connects an even and an odd node in a (2k+ 2)- angulation of a convex 2N-gon. The convex hulls of the odd vertices in each (2k+ 2)-gon now give the factors in a commutation class of a factorization from Fact_{k}(c_{N}). □

Proposition 6.5. A Hurwitz move on a commutation-class of a reduced factorization corresponds to rotating a diagonal in the corresponding (2k+ 2)-angulation one step.

Proof. Let t = t_{1}t_{2} ⋯t_{n} ∈ Fact_{k}(c_{N}), and choose i ∈ [n − 1] such that t_{i} and t_{i+1} do not commute. Then there is a unique integer a which belongs to both t_{i} and t_{i+1} . Let b̄ be the unique vertex in between the convex hulls of t_{i} and t_{i+1} visible from a. Moreover, let b_{i} denote the smallest element of t_{i} greater or equal to b + 1, and let b_{i+1} denote the biggest element of t_{i+1} less or equal to b.

Now, σ_{i} is obtained by removing a from t_{i} and adding b_{i+1} in the appropriate position (thus obtaining t_{i+1}^{−1} t_{i}t_{i+1} ), and by exchanging the order of these two factors. Analogously, σ_{i}^{−1} is obtained by removing a from t_{i+1} and adding b_{i} in the appropriate position (thus obtaining t_{i}t_{i+1} t_{i}^{−1} ), and by exchanging the order of these two factors.

In view of the bijection Θ from Theorem 6.4 the (2k+ 2)-angulations Θ(t) and Θ(σ_{i}t) (respectively Θ(σ_{i}^{−1} t)) di�er by only shifting a unique diagonal. More precisely, the diagonal connecting a and b̄ in Θ(t) is replaced by the diagonal connecting b_{i+1} and ā− 1 in Θ(σ_{i}t) (respectively by the diagonal connecting b_{i} and ā in Θ(σ_{i}^{−1} t)). Hence, the action of σ_{i} (respectively σ_{i}^{−1} ) corresponds to shifting a diagonal in counterclockwise (respectively clockwise) direction under Θ. □

In [32, Section 6.6], a lattice was constructed parametrized by a Coxeter group W, a Coxeter element c ∈ W, and an integer m; the m-Cambrian lattice of W with respect to the orientation c. In the case where W = 𝔖_{n}, and c is given as the product of the simple transpositions in lexicographic order, the corresponding m-Cambrian lattice was realized combinatorially in [12, Chapter 3] as a lattice on (m+ 2)-angulations of a convex (mn+ 2)-gon, where the cover relations are given by rotating a diagonal one step clockwise. Let us refer to this lattice as the (m, n)-Cambrian lattice.

Corollary 6.6. The (2k, n)-Cambrian lattice is isomorphic to the poset whose elements are the reduced factorizations of c_{N} up to commutation equivalence, with the cover relations given by Hurwitz moves.

Proof. Consider the (2kn + 2)-gon from the proof of Theorem 6.4, labeled clockwise by the numbers 1, ¯1, 2, ¯2, …, N, N̄. We replace these labels as described in [12, Section 3.2] starting from N̄. Under this substitution, the reduced factorization

(1, 2, …, k+ 1) · (k+ 1, k+ 2, …, 2k+ 1) ⋯(N− k, N− k+ 1, …, N)

corresponds to the (2k+ 2)-angulation of the (2kn + 2)-gon that is minimal in the (2k, n)-Cambrian lattice, and the reduced factorization

(k+ 1, k+ 2, …, 2k+ 1) · (2k+ 1, 2k+ 2, …, 3k+ 1) ⋯(1, 2, …, k, N)

corresponds to the (2k+ 2)-angulation of the (2kn + 2)-gon that is maximal. The claim then follows by Theorem 6.4 and Proposition 6.5. □

Figure 5 illustrates Corollary 6.6 for n = 3 and k = 1.

7. Nonnesting Partitions

We also �nd analogues of the above construction in the world of nonnesting partitions. Consider the triangular poset de�ned by

Δ_{K} =^{def} ( {(a, b) | 1 ≤ a < b ≤ K}, ⪯),

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

Figure 5. For k = 1 and n = 3, the (2, 3)-Cambrian lattice realized as a lattice of reduced factorizations of (1 2 3 4) up to commutation equivalence (left), and realized as a lattice of quadrangulations of an 8-gon (right).

where (a, b) ⪯ (c, d) if and only if a ≥ c and b ≤ d.

We de�ne Δ_{N;k} to be the induced subposet of Δ_{N−(k−1)} that consists of all pairs (a, b) with a ≡ 1 (mod k). For k = 3 and n = 4 the poset Δ_{13;3} is shown in Figure 6.

We call an order ideal of Δ_{N;k} a k-indivisible nonnesting partition, and we write NN_{N;k} for their set; for k = 1 we get the usual nonnesting partitions. We may equivalently view k-indivisible nonnesting partitions as north-east paths from (0, 0) to (N, n + 1) that stay above the boundary path 𝔟_{N,k} =^{def} UR(UR^{k})^{n}. Here we use the letter U to indicate north-steps (U for up), and the letter R to indicate east-steps (R for right).

Let P_{N;k} denote the set of all such paths. Recall that a k-Dyck path of height n is a north-east path from (0, 0) to (kn, n) that stays weakly above the boundary path (UR^{k})^{n}. Let us write D_{n}^{(k)} to denote the set of all k-Dyck paths. It follows from [7] that the cardinality of D_{n}^{(k)} is the Fu��Catalan number Ran(n, k + 1, 1).

Theorem 7.1. For k, n ≥ 1, the set of order ideals of Δ_{N;k} is in bijection with the set of pairs of k-Dyck paths whose heights sum to n. Consequently, we have |NN_{N;k}| = Ran(n, k + 1, 2).

Proof. In terms of paths, this bijection is a standard decomposition that we detail here for completeness. For 𝔭 ∈ P_{N;k} we say that 𝔭 touches 𝔟_{N;k} at step i, if the

(1,2) (1,3) (1,4) (1,5) (1,6) (1,7) (1,8) (1,9) (1,10) (1,11) (2,3) (2,4) (2,5) (2,6) (2,7) (2,8) (2,9) (2,10) (2,11) (3,4) (3,5) (3,6) (3,7) (3,8) (3,9) (3,10) (3,11) (4,5) (4,6) (4,7) (4,8) (4,9) (4,10) (4,11) (5,6) (5,7) (5,8) (5,9) (5,10) (5,11) (6,7) (6,8) (6,9) (6,10) (6,11) (7,8) (7,9) (7,10) (7,11) (8,9) (8,10) (8,11) (9,10) (9,11) (10,11)

Figure 6. The poset Δ_{13;3} inside Δ_{11}. It has 340 = Ran(4, 4, 2) order ideals.

i-th east steps of 𝔭 and 𝔟_{N;k} agree. Every path in P_{N;k} touches 𝔟_{N;k} at steps N − k + 1, N − k + 2, …, N.

Now let 𝔭 ∈ P_{N;k} and �x the smallest i ∈ {0, 1, …, n} such that 𝔭 touches 𝔟_{N;k} at step ik + 1. We break 𝔭 in two pieces, by removing the �rst north-step and the (ik+ 1)-st east-step. Let 𝔭_{1} and 𝔭_{2} denote the resulting paths. Clearly, 𝔭_{1} is a northeast path from (0, 1) to (ik, i + 1) that stays weakly above R(UR^{k})^{(i−1)} UR^{(k−1)} , and 𝔭_{2} is a north-east path from (ik + 1, i + 1) to (N, n + 1) that stays weakly above (UR^{k})^{n−i} . Since i was chosen minimal 𝔭_{1} does not touch 𝔟_{N;k} at jk + 1 for j < i, which means that 𝔭_{1} in fact stays above (UR^{k})^{i}. Thus, 𝔭_{1} ∈ D_{i}^{(k)} and 𝔭_{2} ∈ D_{n−i}^{(k)} . We have just established

|P_{N;k}| = ∑_{i=0}^{n} |D_{i}^{(k)}| · |D_{n−i}^{(k)} |

= ∑_{i=0}^{n} Ran(i, k + 1, 1) · Ran(n − i, k + 1, 1) .

Moreover, it is easily checked that for n = 1 we have

|P_{k+1;k} | = 2 = Ran(1, k + 1, 2).

By Lemma 4.1, we �nd that the numbers |P_{N;k}| and Ran(n, k + 1, 2) satisfy the same recurrence relation with the same initial conditions, and must therefore be equal. □

Figure 7 illustrates the decomposition from the proof of Theorem 7.1.

𝔭 ∈ P_{31;5} 𝔭_{1} ∈ D_{4}^{(5)} 𝔭_{2} ∈ D_{2}^{(5)}

Figure 7. Illustration of the decomposition in the proof of Theorem 7.1 for n = 6 and k = 5. By construction, the path 𝔭_{1} never enters the light-gray boxes.

Corollary 7.2. For n > 2 and k ≥ 1 we have

Ran(n, k + 1, 2) = ∑_{i=1}^{n−1} (−1)^{(i+1)} \binom{(n − i)k + 2}{i} Ran(n − i, k + 1, 2) .

Proof. We have argued in Theorem 7.1 that the order ideals of Δ_{N;k} are in bijection with north-east paths weakly above the boundary path UR(UR^{k})^{n}. If we �ip such a path together with the boundary path along the bottom border and rotate it by 90 degrees clockwise, we see that order ideals of Δ_{N;k} are in bijection with northeast paths weakly above (U^{k}R)^{n}UR. Note that for such a path, the �rst k steps must be north-steps, and the last step must be an east-step, so that we can forget these steps. Consequently, the order ideals of Δ_{N;k} are in bijection with north-east paths weakly above R(U^{k}R)^{n−1} U.

In view of [19, Theorem 10.7.1] the number of such paths is given by the determinant of the matrix

M_{n;k} = ( \binom{(n − j)k + 2}{j − i + 1} ) _{1≤i,j≤n} .

By Laplace expansion we see that for n > 2 the determinant of M_{n,k} satis�es the recursion given in the statement, and from Theorem 7.1 we conclude the result. □

Remark 7.3. The set of k-Dyck paths of height n is classically in bijection with the set of (k+ 1)-ary trees with n non-leaf vertices. The bijections described in Theorem 1.2 and Theorem 7.1 thus extend to a bijection from NC_{N;k} to NN_{N;k}.

8. Open Problems

8.1. EL-shellability. From a topological point of view, the lattice NC_{N;1} of noncrossing partitions is particularly interesting: its order complex is a wedge of Catalan-many spheres. This was established by Bj� orner and Edelman [8, Remark 2] by showing that NC_{N;1} admits a particular edge-labeling. Such an ELlabeling induces a shelling of the order complex, from which the mentioned property follows.

We have attempted to extend this result to NC_{N;k}, but many natural choices for such a labeling did not have the desired properties. Nevertheless, we still pose the following conjecture.

Conjecture 8.1. The poset NC_{N;k} admits an EL-labeling. Consequently, the order complex of NC_{N;k} with least and greatest elements removed is homotopic to a wedge of spheres.

8.2. Other types. We give some conjectures for extending the combinatorics of this article to type B. Fix simple re�ections s_{0}, s_{1}, …, s_{kn−1} in the hyperoctahedral group of type B_{kn} with (s_{0}s_{1})^{4} = 1. Analogously to the symmetric group, we group the transpositions of the factorization c = s_{0}s_{1} ⋯s_{kn−1} of the linear Coxeter element as

t = (s_{0} ⋯s_{k−1} ) · (s_{k}⋯s_{2k−1} ) ⋯(s_{kn−k} ⋯s_{kn−1} ).

Conjecture 8.2. The Hurwitz orbit of t contains k^{n−1} n^{n} elements.

We can take elements that occur as pre�xes of the factorizations in the Hurwitz orbit of t to form the type B_{n} k-indivisible noncrossing partitions.

Conjecture 8.3. There are 2\binom{nk+n−1}{n−1} type B_{n} k-indivisible noncrossing partitions. The zeta function of the restriction of the absolute order to those elements is q\binom{nk(q−1)+n−1}{n−1}.

Acknowledgements

We thank an anonymous reviewer for a careful reading of the manuscript and many insightful comments and suggestions. We thank Christian Krattenthaler for providing a proof of Theorem 4.10, and suggesting to include it in this article. N.W. thanks Jon McCammond for pointing him to [24], Louis-Franc�ois Pr� eville-Ratelle and Guillaume Chapuy for helpful conversations, and Christian Stump for providing TikZ code to draw noncrossing partitions.

N.W. was partially supported by a Simons collaboration grant.

References

[1] Drew Armstrong, Generalized Noncrossing Partitions and Combinatorics of Coxeter Groups, Memoirs of the American Mathematical Society 202 (2009).

[2] Drew Armstrong and Christian Krattenthaler, Euler Characteristic of the Truncated Order Complex of Generalized Noncrossing Partitions, The Electronic Journal of Combinatorics 16 (2009).

[3] Barbara Baumeister, Kai-Uwe Bux, Friedrich G� otze, Dawid Kielak, and Henning Krause, Non-Crossing Partitions, Spectral Structures and Topological Methods in Mathematics (Michael Baake, Friedrich G� otze, and Werner Ho�mann, eds.), to appear, available at arXiv:1903.01146.

[4] Philippe Biane, Minimal Factorizations of a Cycle and Central Multiplicative Functions on the In�nite Symmetric Group, Journal of Combinatorial Theory (Series A) 76 (1996), 197�212.

[5] Philippe Biane, Some Properties of Crossings and Partitions, Discrete Mathematics 175 (1997), 41�53.

[6] Philippe Biane, Parking Functions of Types A and B, The Electronic Journal of Combinatorics 9 [7] Michael T. L. Bizley, Derivation of a New Formula for the Number of Minimal Lattice Paths from (0, 0)

to (km, kn) Having just t Contacts with the Line my = nx and Having no Points above this Line; and a Proof of Grossman’s Formula for the Number of Paths which May Touch but Do not Rise above this Line, Journal for the Institute of Actuaries 80 (1954), 55�62.

[8] Anders Bj� orner, Shellable and Cohen�Macaulay Partially Ordered Sets, Transactions of the American Mathematical Society 260 (1980), 159�183.

[9] A. Robert Calderbank, Philipp J. Hanlon, and Robert W. Robinson, Partitions into even and odd Block Size and some unusual Characters of the Symmetric Groups, Proceedings of the London Mathematical Society 3 (1986), no. 2, 288�320.

[10] Paul H. Edelman, Chain Enumeration and Non-Crossing Partitions, Discrete Mathematics 31 (1980), 171�180.

[11] Jennifer A. Eidswick, Short Factorizations of Permutations into Transpositions, Discrete Mathematics 73 (1989), no. 3, 239�243.

[12] Mike Freeze, Combinatorial Descriptions of the m-Cambrian Lattices, Master’s Thesis, The University of New Brunswick, 2016.

[13] Ian P. Goulden and David M. Jackson, The Combinatorial Relationship between Trees, Cacti and Certain Connection Coe�cients for the Symmetric Group, European Journal of Combinatorics 13 (1992), 357�365.

[14] Ian P. Goulden and David M. Jackson, Symmetrical Functions and Macdonald’s Result for Top Connexion Coe�cients in the Symmetrical Group, Journal of Algebra 166 (1994), no. 2, 364�378.

[15] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994.

[16] Marcel Herzog and Kenneth B. Reid, Representation of Permutations as Products of Cycles of Fixed Length, Journal of the Australian Mathematical Society (Series A) 22 (1976), 321�331.

[17] John Irving and Amarpreet Rattan, Trees, Parking Functions and Factorizations of Full Cycles (2019),

available at arXiv:1907.10123.

[18] John Irving and Amarpreet Rattan, Parking Functions, Tree Depth and Factorizations of the Full Cycle into Transpositions, Proceedings of the 28th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC), Simon Fraser University, Vancouver, 2016, pp. 647�658.

[19] Christian Krattenthaler, Lattice Path Enumeration, Handbook of Enumerative Combinatorics (Mikl� os B� ona, ed.), CRC Press, Boca Raton-London-New York, 2015, pp. 589�678.

[20] Christian Krattenthaler and Thomas W. M � uller, Decomposition Numbers for Finite Coxeter Groups and Generalised Non-Crossing Partitions, Transactions of the American Mathematical Society 362 (2010), 2723�2787.

[21] Sergei K. Lando and Alexander K. Zvonkin, Graphs on Surfaces and their Applications, Vol. 141, Springer, Berlin, 2004.

[22] Judith Q. Longyear, A Peculiar Partition Formula, Discrete Mathematics 78 (1989), no. 1-2, 115�118.

[23] Jon McCammond, Noncrossing Partitions in Surprising Locations, American Mathematical Monthly 113 (2006), 598�610.

[24] Jon McCammond, Noncrossing Hypertrees (2017), available at arXiv:1707.06634.

[25] Henri M � uhle and Philippe Nadeau, A Poset Structure on the Alternating Group Generated by 3-Cycles, Algebraic Combinatorics 2 (2019), 1285�1310.

[26] Bruce E. Sagan, Shellability of Exponential Structures, Order 3 (1986), no. 1, 47�54.

[27] Rodica Simion, Noncrossing Partitions, Discrete Mathematics 217 (2000), 397�409.

[28] Colin Springer, Factorizations, Trees, and Cacti, Proceedings of the Eighth International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC), University of Minnesota, 1996, pp. 427�438.

[29] Richard P. Stanley, Exponential Structures, Studies in Applied Mathematics 59 (1978), no. 1, 73�82.

[30] Richard P. Stanley, Parking Functions and Noncrossing Partitions, The Electronic Journal of Combinatorics 4 (1997).

[31] Richard P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd ed., Cambridge University Press, Cambridge, 2011.

[32] Christian Stump, Hugh Thomas, and Nathan Williams, Cataland: Why the Fu�? (2018), available

at arXiv:1503.00710.

[33] Garrett S. Sylvester, Continuous-Spin Ising Ferromagnets, Ph.D. Thesis, Massachusetts Institute of Technology, 1976.

[34] Nikolaus von Fu�, Solutio Quaestionis quot Modis Polygonum n Laterum in Polygona m Laterum per Diagonales Resolvi queat, Nova Acta Academiae Scientiarum Imperialis Petropolitanae IX (1791), 243�251.

[35] Michelle L. Wachs, Poset Topology: Tools and Applications, Geometric Combinatorics (Ezra Miller, Victor Reiner, and Bernd Sturmfels, eds.), American Mathematical Society, Providence, RI, 2007, pp. 497�615.

[36] Catherine H. Yan, Generalized Parking Functions, Tree Inversions, and Multicolored Graphs, Advances in Applied Mathematics 27 (2001), 641�670.

Technische Universit � at Dresden, Institut f � ur Algebra, Zellescher Weg 12�14, 01069 Dresden, Germany

   Email address: henri.muehle@tu-dresden.de

Universit� e de Lyon, CNRS, UMR5208, Institut Camille Jordan, F-69622 Villeurbanne, France

   Email address: nadeau@math.univ-lyon1.fr

University of Texas at Dallas, USA

   Email address: nathan.f.williams@gmail.com