DECOMPOSITION NUMBERS FOR FINITE COXETER GROUPS AND GENERALISED NON-CROSSING PARTITIONS

C. KRATTENTHALER^{†} AND T. W. MÜLLER

Abstract. Given a finite irreducible Coxeter group W, a positive integer d, and types T_{1}, T_{2}, …, T_{d} (in the sense of the classification of finite Coxeter groups), we compute the number of decompositions c = σ_{1}σ_{2} ⋯ σ_{d} of a Coxeter element c of W, such that σ_{i} is a Coxeter element in a subgroup of type T_{i} in W, i = 1, 2, …, d, and such that the factorisation is “minimal” in the sense that the sum of the ranks of the T_{i}’s, i = 1, 2, …, d, equals the rank of W. For the exceptional types, these decomposition numbers have been computed by the first author in [“Topics in Discrete Mathematics,” M. Klazar et al. (eds.), Springer–Verlag, Berlin, New York, 2006, pp. 93–126] and [Séminaire Lotharingien Combin. 54 (2006), Article B54l]. The type A_{n} decomposition numbers have been computed by Goulden and Jackson in [Europ. J. Combin. 13 (1992), 357–365], albeit using a somewhat different language. We explain how to extract the type B_{n} decomposition numbers from results of Bóna, Bousquet, Labelle and Leroux [Adv. Appl. Math. 24 (2000), 22–56] on map enumeration. Our formula for the type D_{n} decomposition numbers is new. These results are then used to determine, for a fixed positive integer l and fixed integers r_{1} ≤ r_{2} ≤ ⋯ ≤ r_{l}, the number of multi-chains π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{l} in Armstrong’s generalised non-crossing partitions poset, where the poset rank of π_{i} equals r_{i}, and where the “block structure” of π_{1} is prescribed. We demonstrate that this result implies all known enumerative results on ordinary and generalised non-crossing partitions via appropriate summations. Surprisingly, this result on multi-chain enumeration is new even for the original noncrossing partitions of Kreweras. Moreover, the result allows one to solve the problem of rank-selected chain enumeration in the type D_{n} generalised non-crossing partitions poset, which, in turn, leads to a proof of Armstrong’s F = M Conjecture in type D_{n}, thus completing a computational proof of the F = M Conjecture for all types. It also allows to address another conjecture of Armstrong on maximal intervals containing a random multichain in the generalised non-crossing partitions poset.

1. Introduction

The introduction of non-crossing partitions for finite reflection groups (finite Coxeter groups) by Bessis [8] and Brady and Watt [15] marks the creation of a new, exciting subject of combinatorial theory, namely the study of these new combinatorial objects which possess numerous beautiful properties, and seem to relate to several other objects of combinatorics and algebra, most notably to the cluster complex of Fomin and

2000 Mathematics Subject Classification. Primary 05E15; Secondary 05A05 05A10 05A15 05A18 06A07 20F55 33C05.

Key words and phrases. root systems, reflection groups, Coxeter groups, generalised non-crossing partitions, annular non-crossing partitions, chain enumeration, Möbius function, M-triangle, generalised cluster complex, face numbers, F -triangle, Chu–Vandermonde summation.

†Research partially supported by the Austrian Science Foundation FWF, grant S9607-N13, in the framework of the National Research Network “Analytic Combinatorics and Probabilistic Number Theory”.

Zelevinsky [21] (cf. [2, 3, 5, 4, 8, 9, 14, 15, 16, 17, 20]). They reduce to the classical non-crossing partitions of Kreweras [30] for the irreducible reflection groups of type A_{n} (i.e., the symmetric groups), and to Reiner’s [32] type B_{n} non-crossing partitions for the irreducible reflections groups of type B_{n}. (They differ, however, from the type D_{n} non-crossing partitions of [32].) The subject has been enriched by Armstrong through introduction of his generalised non-crossing partitions for reflection groups in [1]. In the symmetric group case, these reduce to the m-divisible non-crossing partitions of Edelman [18], while they produce new combinatorial objects already for the reflection groups of type B_{n}. Again, these generalised non-crossing partitions possess numerous beautiful properties, and seem to relate to several other objects of combinatorics and algebra, most notably to the generalised cluster complex of Fomin and Reading [19] (cf. [1, 6, 7, 20, 27, 28, 29, 36, 37, 38]).

From a technical point of view, the main subject matter of the present paper is the computation of the number of certain factorisations of the Coxeter element of a reflection group. These decomposition numbers, as we shall call them from now on (see Section 2 for the precise definition), arose in [27, 28], where it was shown that they play a crucial role in the computation of enumerative invariants of (generalised) non-crossing partitions. Moreover, in these two papers the decomposition numbers for the exceptional reflection groups have been computed, and it was pointed out that the decomposition numbers in type A_{n} (i.e., the decomposition numbers for the symmetric groups) had been earlier computed by Goulden and Jackson in [23]. Here, we explain how the decomposition numbers in type B_{n} can be extracted from results of Bóna, Bousquet, Labelle and Leroux [12] on the enumeration of certain planar maps, and we find formulae for the decomposition numbers in type D_{n}, thus completing the project of computing the decomposition numbers for all the irreducible reflection groups.

The main goal of the present paper, however, is to access the enumerative theory of the generalised non-crossing partitions of Armstrong via these decomposition numbers. Indeed, one finds numerous enumerative results on ordinary and generalised non-crossing partitions in the literature (cf. [1, 2, 4, 8, 9, 18, 30, 32, 37]): results on the total number of (generalised) non-crossing partitions of a given size, of those with a fixed number of blocks, of those with a given block structure, results on the number of (multi-)chains of a given length in a given poset of (generalised) non-crossing partitions, results on rank-selected chain enumeration (that is, results on the number of chains in which the ranks of the elements of the chains have been fixed), etc. We show that not only can all these results be rederived from our decomposition numbers, we are also able to find several new enumerative results. In this regard, the most general type of result that we find is formulae for the number of (multi-)chains π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{l−1} in the poset of non-crossing partitions of type A_{n}, B_{n}, respectively D_{n}, in which the block structure of π_{1} is fixed as well as the ranks of π_{2}, …, π_{l−1}. Even the corresponding result in type A_{n}, for the non-crossing partitions of Kreweras, is new. Furthermore, from the result in type D_{n}, by a suitable summation, we are able to find a formula for the rank-selected chain enumeration in the poset of generalised non-crossing partitions of type D_{n}, thus generalising the earlier formula of Athanasiadis and Reiner [4] for the rank-selected chain enumeration of “ordinary” non-crossing partitions of type D_{n}. In conjunction with the results from [27, 28], this generalisation in turn allows us to complete a computational case-by-case proof of Armstrong’s “F = M Conjecture” [1, Conjecture 5.3.2] predicting a surprising relationship between a certain face count in the generalised cluster complex of Fomin and Reading and the Möbius function in the poset of generalised non-crossing partitions of Armstrong. (A case-free proof had been found earlier by Tzanaki in [38].) Our results allow us also to address another conjecture of Armstrong [1, Conj. 3.5.13] on maximal intervals containing a random multichain in the poset of generalised non-crossing partitions. We show that the conjecture is indeed true for types A_{n} and B_{n}, but that it fails for type D_{n} (and we suspect that it will also fail for most of the exceptional types).

We remark that a totally different approach to the enumerative theory of (generalised) non-crossing partitions is proposed in [29]. This approach is, however, completely combinatorial and avoids, in particular, reflection groups. It is, therefore, not capable of computing our decomposition numbers nor anything else which is intrinsic to the combinatorics of reflection groups. A similar remark applies to [31, Theorem 4.1], where a remarkable uniform recurrence is found for rank-selected chain enumeration in the generalised non-crossing partitions of any type. It could be used, for example, for verifying our result in Corollary 19 on the rank-selected chain enumeration in the generalised non-crossing partitions of type D_{n}, but it is not capable of computing our decomposition numbers nor of verifying results with restrictions on block structure.

Our paper is organised as follows. In the next section we define the decomposition numbers for finite reflection groups from [27, 28], the central objects in our paper, together with a combinatorial variant, which depends on combinatorial realisations of non-crossing partitions, which we also explain in the same section. This is followed by an intermediate section in which we collect together some auxiliary results that will be needed later on. In Section 4, we recall Goulden and Jackson’s formula [23] for the full rank decomposition numbers of type A_{n}, together with the formula from [28, Theorem 10] that it implies for the decomposition numbers of type A_{n} of arbitrary rank. The purpose of Section 5 is to explain how formulae for the decomposition numbers of type B_{n} can be extracted from results of Bóna, Bousquet, Labelle and Leroux in [12]. The type D_{n} decomposition numbers are computed in Section 6. The approach that we follow is, essentially, the approach of Goulden and Jackson in [23]: we translate the counting problem into the problem of enumerating certain maps. This problem is then solved by a combinatorial decomposition of these maps, translating the decomposition into a system of equations for corresponding generating functions, and finally solving this system with the help of the multidimensional Lagrange inversion formula of Good. Sections 7–11 form the “applications part” of the paper. In the preparatory Section 7, we recall the definition of the generalised non-crossing partitions of Armstrong, and we explain the combinatorial realisations of the generalised non-crossing partitions for the types A_{n}, B_{n}, and D_{n} from [1] and [29]. The bulk of the applications is contained in Section 8, where we present three theorems, Theorems 11, 13, and 15, on the number of factorisations of a Coxeter element of type A_{n}, B_{n}, respectively D_{n}, with less stringent restrictions on the factors than for the decomposition numbers. These theorems result from our formulae for the (combinatorial) decomposition numbers upon appropriate summations. Subsequently, it is shown that the corresponding formulae imply all known enumeration results on non-crossing partitions and generalised non-crossing partitions, plus several new ones, see Corollaries 12, 14, 16–19 and the accompanying remarks. Section 9 presents the announced computational proof of the F = M (ex-)Conjecture for type D_{n}, based on our formula in Corollary 19 for the rank-selected chain enumeration in the poset of generalised non-crossing partitions of type D_{n}, while Section 10 addresses Conjecture 3.5.13 from [1], showing that it does not hold in general since it fails in type D_{n}. In the final Section 11 we point out that the decomposition numbers do not only allow one to derive enumerative results for the generalised non-crossing partitions of the classical types, they also provide all the means for doing this for the exceptional types. For the convenience of the reader, we list the values of the decomposition numbers for the exceptional types that have been computed in [27, 28] in an appendix.

In concluding the introduction, we want to attract the reader’s attention to the fact that many of the formulae presented here are very combinatorial in nature (see Sections 4, 5, 8). This raises the natural question as to whether it is possible to find combinatorial proofs for them. Indeed, a combinatorial (and, in fact, almost bijective) proof of the formula of Goulden and Jackson, presented here in Theorem 5, has been given by Bousquet, Chauve and Schaeffer in [13]. Moreover, most of the proofs for the known enumeration results on (generalised) non-crossing partitions presented in [1, 2, 4, 18, 32] are combinatorial. On the other hand, to our knowledge so far nobody has given a combinatorial proof for Theorem 7, the formula for the decomposition numbers of type B_{n}, essentially due to Bóna, Bousquet, Labelle and Leroux [12], although we believe that this should be possible by modifying the ideas from [13]. There are also other formulae in our paper (see e.g. Corollaries 12 and 14, Eqs. (6.1) and (8.33)) which seem amenable to combinatorial proofs. However, to find combinatorial proofs for our type D_{n} results (cf. in particular Theorem 9.(ii) and Corollaries 16–19) seems rather hopeless to us.

2. Decomposition numbers for finite Coxeter groups

In this section, we introduce the decomposition numbers from [27, 28], which are (Coxeter) group-theoretical in nature, plus combinatorial variants for Coxeter groups of types B_{n} and D_{n}, which will be important in combinatorial applications. These variants depend on the combinatorial realisation of these Coxeter groups, which we also explain here.

Let Φ be a finite root system of rank n. (We refer the reader to [24] for all terminology on root systems.) For an element α ∈ Φ, let t_{α} denote the corresponding reflection in the central hyperplane perpendicular to α. Let W = W (Φ) be the group generated by these reflections. As is well-known (cf. e.g. [24, Sec. 6.4]), any such reflection group is at the same time a finite Coxeter group, and all finite Coxeter groups can be realised in this way. By definition, any element w of W can be represented as a product w = t_{1}t_{2} ⋯ t_{ℓ}, where the t_{i}’s are reflections. We call the minimal number of reflections which is needed for such a product representation the absolute length of w, and we denote it by ℓ_{T} (w). We then define the absolute order on W, denoted by ≤_{T}, via

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

As is well-known and easy to see, this is equivalent to the statement that every shortest representation of u by reflections occurs as an initial segment in some shortest product representation of w by reflections.

Now, for a finite root system Φ of rank n, types T_{1}, T_{2}, …, T_{d} (in the sense of the classification of finite Coxeter groups), and a Coxeter element c, the decomposition number N_{Φ}(T_{1}, T_{2}, …, T_{d}) is defined as the number of “minimal” products c_{1}c_{2} ⋯ c_{d} less than or equal to c in absolute order, “minimal” meaning that ℓ_{T} (c_{1}) + ℓ_{T} (c_{2}) + ⋯ + ℓ_{T} (c_{d}) = ℓ_{T} (c_{1}c_{2} ⋯ c_{d}), such that, for i = 1, 2, …, d, the type of c_{i} as a parabolic Coxeter element is T_{i}. (Here, the term “parabolic Coxeter element” means a Coxeter element in some parabolic subgroup. The reader should recall that it follows from [8, Lemma 1.4.3] that any element c_{i} is indeed a Coxeter element in a parabolic subgroup of W = W (Φ). By definition, the type of c_{i} is the type of this parabolic subgroup. The reader should also note that, because of the rewriting

c_{1}c_{2} ⋯ c_{d} = c_{i}(c_{i}^{−1}c_{1}c_{i})(c_{i}^{−1}c_{2}c_{i}) ⋯ (c_{i}^{−1}c_{i−1}c_{i})c_{i+1} ⋯ c_{d},  (2.1)

any c_{i} in such a minimal product c_{1}c_{2} ⋯ c_{d} ≤_{T} c is itself ≤_{T} c.) It is easy to see that the decomposition numbers are independent of the choice of the Coxeter element c. (This follows from the well-known fact that any two Coxeter elements are conjugate to each other; cf. [24, Sec. 3.16].)

The decomposition numbers satisfy several linear relations between themselves. First of all, the number N_{Φ}(T_{1}, T_{2}, …, T_{d}) is independent of the order of the types T_{1}, T_{2}, …, T_{d}; that is, we have

N_{Φ}(T_{σ(1)}, T_{σ(2)}, …, T_{σ(d)}) = N_{Φ}(T_{1}, T_{2}, …, T_{d})  (2.2)

for every permutation σ of {1, 2, …, d}. This is, in fact, a consequence of the rewriting (2.1). Furthermore, by the definition of these numbers, those of “lower rank” can be computed from those of “full rank.” To be precise, we have

N_{Φ}(T_{1}, T_{2}, …, T_{d}) = ∑_{T} N_{Φ}(T_{1}, T_{2}, …, T_{d}, T),  (2.3)

where the sum is taken over all types T of rank n − rk T_{1} − rk T_{2} − ⋯ − rk T_{d} (with rk T denoting the rank of the root system Ψ of type T, and n still denoting the rank of the fixed root system Φ; for later use we record that

ℓ_{T} (w_{0}) = rk T_{0}  (2.4)

for any parabolic Coxeter element w_{0} of type T_{0}).

The decomposition numbers for the exceptional types have been computed in [27, 28]. For the benefit of the reader, we reproduce these numbers in the appendix. The decomposition numbers for type A_{n} are given in Section 4, the ones for type B_{n} are computed in Section 5, while the ones for type D_{n} are computed in Section 6.

Next we introduce variants of the above decomposition numbers for the types B_{n} and D_{n}, which depend on the combinatorial realisation of the Coxeter groups of these types.

As is well-known, the reflection group W (A_{n}) can be realised as the symmetric group S_{n+1} on {1, 2, …, n + 1}. The reflection groups W (B_{n}) and W (D_{n}), on the other hand, can be realised as subgroups of the symmetric group on 2n elements. (See e.g. [11, Sections 8.1 and 8.2].) Namely, the reflection group W (B_{n}) can be realised as the subgroup of the group of all permutations π of

{1, 2, …, n, ¯1, ¯2, …, n̄}

satisfying the property

π(ī) = \overline{π(i)}.  (2.5)

(Here, and in what follows, ¯ ī is identified with i for all i.) In this realisation, there is an analogue of the disjoint cycle decomposition of permutations. Namely, every π ∈ W (B_{n}) can be decomposed as

π = κ_{1}κ_{2} ⋯ κ_{s},  (2.6)

where, for i = 1, 2, …, s, κ_{i} is of one of two possible types of “cycles”: a type A cycle, by which we mean a permutation of the form

((a_{1}, a_{2}, …, a_{k})) := (a_{1}, a_{2}, …, a_{k}) (\overline{a_{1}}, \overline{a_{2}}, …, \overline{a_{k}}),  (2.7)

or a type B cycle, by which we mean a permutation of the form

[a_{1}, a_{2}, …, a_{k}] := (a_{1}, a_{2}, …, a_{k}, \overline{a_{1}}, \overline{a_{2}}, …, \overline{a_{k}}),  (2.8)

a_{1}, a_{2}, …, a_{k} ∈ {1, 2, …, n, ¯1, ¯2, …, n̄}. (Here we adopt notation from [15].) In both cases, we call k the length of the “cycle.” The decomposition (2.6) is unique up to a reordering of the κ_{i}’s.

We call a type A cycle of length k of combinatorial type A_{k−1}, while we call a type B cycle of length k of combinatorial type B_{k}, k = 1, 2, . . .. The reader should observe that, when regarded as a parabolic Coxeter element, for k ≥ 2 a type A cycle of length k has type A_{k−1}, while a type B cycle of length k has type B_{k}. However, a type B cycle of length 1, that is, a permutation of the form (i, ī), has type A_{1} when regarded as a parabolic Coxeter element, while we say that it has combinatorial type B_{1}. (The reader should recall that, in the classification of finite Coxeter groups, the type B_{1} does not occur, respectively, that sometimes B_{1} is identified with A_{1}. Here, when we speak of “combinatorial type,” then we do distinguish between A_{1} and B_{1}. For example, the “cycles” ((1, 2)) = (1, 2) (¯1, ¯2) or ((¯1, 2)) = (¯1, 2) (1, ¯2) have combinatorial type A_{1}, whereas the cycles [1] = (1, ¯1) or [2] = (2, ¯2) have combinatorial type B_{1}.)

As Coxeter element for W (B_{n}), we choose

c = (1, 2, …, n, ¯1, ¯2, …, n̄) = [1, 2, …, n].

Now, given combinatorial types T_{1}, T_{2}, …, T_{d}, each of which being a product of A_{k}’s and B_{k}’s, k = 1, 2, …, the combinatorial decomposition number N_{B_{n}}^{comb}(T_{1}, T_{2}, …, T_{d}) is defined as the number of minimal products c_{1}c_{2} ⋯ c_{d} less than or equal to c in absolute order, where “minimal” has the same meaning as above, such that for i = 1, 2, …, d the combinatorial type of c_{i} is T_{i}. Because of (2.1), the combinatorial decomposition numbers N_{B_{n}}^{comb}(T_{1}, T_{2}, …, T_{d}) satisfy also (2.2) and (2.3).

The reflection group W (D_{n}) can be realised as the subgroup of the group of all permutations π of {1, 2, …, n, ¯1, ¯2, …, n̄} satisfying (2.5) and the property that an even number of elements from {1, 2, …, n} is mapped to an element of negative sign. (Here, the elements 1, 2, …, n are considered to have sign +, while the elements ¯1, ¯2, …, n̄ are considered to have sign −.) Since W (D_{n}) is a subgroup of W (B_{n}), and since the above realisation of W (D_{n}) is contained as a subset in the realisation of W (B_{n}) that we just described, any π ∈ W (D_{n}) can be decomposed as in (2.6), where, for i = 1, 2, …, d, κ_{i} is either a type A or a type B cycle. Requiring that π is in the subgroup W (D_{n}) of W (B_{n}) is equivalent to requiring that there is an even number of type B cycles in the decomposition (2.6). Again, the decomposition (2.6) for π ∈ W (D_{n}) is unique up to a reordering of the κ_{i}’s.

As Coxeter element, we choose

c = (1, 2, …, n − 1, ¯1, ¯2, …, \overline{n − 1}) (n, n̄) = [1, 2, …, n − 1] [n].

We shall be entirely concerned with elements π of W (D_{n}) which are less than or equal to c. It is not difficult to see (and it is shown in [4, Sec. 3]) that the unique factorisation of any such element π has either 0 or 2 type B cycles, and in the latter case one of the type B cycles is [n] = (n, n̄). In this latter case, in abuse of terminology, we call the product of these two type B cycles, [a_{1}, a_{2}, …, a_{k−1}] [n] say, a “cycle” of combinatorial type D_{k}. More generally, we shall say for any product of two disjoint type B cycles of the form

[a_{1}, a_{2}, …, a_{k−1}] [a_{k}]  (2.9)

that it is a “cycle” of combinatorial type D_{k}. The reader should observe that, when regarded as parabolic Coxeter element, for k ≥ 4 an element of the form (2.9) has type D_{k}. However, if k = 3, it has type A_{3} when regarded as parabolic Coxeter element, while we say that it has combinatorial type D_{3}, and, if k = 2, it has type A_{1}^{2} when regarded as parabolic Coxeter element, while we say that it has combinatorial type D_{2}. (The reader should recall that, in the classification of finite Coxeter groups, the types D_{3} and D_{2} do not occur, respectively, that sometimes D_{3} is identified with A_{3}, D_{2} being identified with A_{1}^{2}. Here, when we speak of “combinatorial type,” then we do distinguish between D_{3} and A_{3}, and between D_{2} and A_{1}^{2}.)

Now, given combinatorial types T_{1}, T_{2}, …, T_{d}, each of which being a product of A_{k}’s and D_{k}’s, k = 1, 2, …, the combinatorial decomposition number N_{B_{n}}^{comb}(T_{1}, T_{2}, …, T_{d}) is defined as the number of minimal products c_{1}c_{2} ⋯ c_{d} less than or equal to c in absolute order, where “minimal” has the same meaning as above, such that for i = 1, 2, …, d the combinatorial type of c_{i} is T_{i}. Because of (2.1), the combinatorial decomposition numbers N_{D_{n}}^{comb}(T_{1}, T_{2}, …, T_{d}) satisfy also (2.2) and (2.3).

3. Auxiliary results

In our computations in the proof of Theorem 9, leading to the determination of the decomposition numbers of type D_{n}, we need to apply the Lagrange–Good inversion formula [22] (see also [26, Sec. 5] and the references cited therein). We recall it here for the convenience of the reader. In doing so, we use standard multi-index notation. Namely, given a positive integer d, and vectors z = (z_{1}, z_{2}, …, z_{d}) and n = (n_{1}, n_{2}, …, n_{d}), we write z^{n} for z_{1}^{n_{1}}z_{2}^{n_{2}} ⋯ z_{d}^{n_{d}}. Furthermore, in abuse of notation, given a formal power series f in d variables, f(z) stands for f(z_{1}, z_{2}, …, z_{d}). Moreover, given d formal power series f_{1}, f_{2}, …, f_{d} in d variables, f^{n}(z) is short for

f_{1}^{n_{1}}(z_{1}, z_{2}, …, z_{d})f_{2}^{n_{2}}(z_{1}, z_{2}, …, z_{d}) ⋯ f_{d}^{n_{d}}(z_{1}, z_{2}, …, z_{d}).

Finally, if m = (m_{1}, m_{2}, …, m_{d}) is another vector, then m + n is short for (m_{1} + n_{1}, m_{2} + n_{2}, …, m_{d} + n_{d}). Notation such as m − n has to be interpreted in a similar way.

Theorem 1 (Lagrange–Good inversion). Let d be a positive integer, and let f_{1}(z), f_{2}(z), …, f_{d}(z) be formal power series in z = (z_{1}, z_{2}, …, z_{d}) with the property that, for all i, f_{i}(z) is of the form z_{i}/φ_{i}(z) for some formal power series φ_{i}(z) with φ_{i}(0, 0, …, 0) ≠ 0. Then, if we expand a formal power series g(z) in terms of powers of the f_{i}(z),

g(z) = ∑_{n} γ_{n}f^{n}(z),  (3.1)

the coefficients γ_{n} are given by

γ_{n} = ⟨z^{−e}⟩ g(z)f^{−n−e}(z) det_{1≤i,j≤d} (\frac{∂f_{i}}{∂z_{j}} (z)) ,

where e = (1, 1, …, 1), where the sum in (3.1) runs over all d-tuples n of non-negative integers, and where ⟨z^{m}⟩ h(z) denotes the coefficient of z^{m} in the formal Laurent series h(z).

Next, we prove a determinant lemma and a corollary, both of which will also be used in the proof of Theorem 9.

Lemma 2. Let d be a positive integer, and let X_{1}, X_{2}, …, X_{d}, Y_{2}, Y_{3}, …, Y_{d} be indeterminates. Then

det_{1≤i,j≤d} (\begin{cases}1 − χ(1 ≠ j)\frac{Y_{j}}{X_{1}} , & i = 1 \\ 1 − χ(i ≠ j)\frac{Y_{i}}{X_{i}} , & i ≥ 2 \end{cases}\}) = \frac{(∑_{i=1}^{d} X_{i} − ∑_{i=2}^{d} Y_{i}) Y_{2}Y_{3} ⋯ Y_{d}}{X_{1}X_{2} ⋯ X_{d}} ,  (3.2)

where χ(S) = 1 if S is true and χ(S) = 0 otherwise.

Proof. By using multilinearity in the rows, we rewrite the determinant on the left-hand side of (3.2) as

\frac{1}{X_{1}X_{2} ⋯ X_{d}} det_{1≤i,j≤d} (\begin{cases}X_{1} − χ(1 ≠ j)Y_{j}, & i = 1 \\ X_{i} − χ(i ≠ j)Y_{i}, & i ≥ 2 \end{cases}\}) .

Next, we subtract the first column from all other columns. As a result, we obtain the determinant

\frac{1}{X_{1}X_{2} ⋯ X_{d}} det_{1≤i,j≤d} (\begin{cases}X_{1}, & i = j = 1 \\ −Y_{j}, & i = 1 and j ≥ 2 \\ X_{i} − Y_{i}, & i ≥ 2 and j = 1 \\ χ(i = j)Y_{i}, & i, j ≥ 2 \end{cases}\}) .

Now we add rows 2, 3, …, d to the first row. After that, our determinant becomes lower triangular, with the entry in the first row and column equal to ∑_{i=1}^{d} X_{i} − ∑_{i=2}^{d} Y_{i}, and the diagonal entry in row i, i ≥ 2, equal to Y_{i}. Hence, we obtain the claimed result. □

Corollary 3. Let d and r be positive integers, 1 ≤ r ≤ d, and let X_{1}, X_{2}, …, X_{d}, Y and Z be indeterminates. Then, with notation as in Lemma 2,

det_{1≤i,j≤d} (\begin{cases}1 − χ(r ≠ j)\frac{Z}{X_{r}} , & i = r \\ 1 − χ(i ≠ j)\frac{Y}{X_{i}} , & i ≠ r \end{cases}\})

= \frac{Y^{d−2}(Z ∑_{i=1}^{d} X_{i} + (Y − Z)X_{r} − (d − 1)Y Z)}{X_{1}X_{2} ⋯ X_{d}}. (3.3)

Proof. We write the diagonal entry in the r-th row of the determinant in (3.3) as

1 = \frac{X_{r} + Y − Z}{X_{r}} − \frac{Y − Z}{X_{r}} ,

and then use linearity of the determinant in the r-th row to decompose the determinant as

\frac{X_{r} + Y − Z}{X_{r}} D_{1} − \frac{Y − Z}{X_{r}} D_{2},

where D_{1} is the determinant in (3.2) with X_{r} replaced by X_{r} + Y − Z, and with Y_{i} = Y for all i, and where D_{2} is the determinant in (3.2) with d replaced by d−1, with Y_{i} = Y for all i, and with X_{i} replaced by X_{i−1} for i = r +1, r +2, …, d. Hence, using Lemma 2, we deduce that the determinant in (3.3) is equal to

\frac{Y^{d−1}( ∑_{i=1}^{d} X_{i} + Y − Z − (d − 1)Y )}{X_{1}X_{2} ⋯ X_{d}} − \frac{(Y − Z)Y^{d−2}( ∑_{i=1}^{d} X_{i} − X_{r} − (d − 2)Y )}{X_{1}X_{2} ⋯ X_{d}}.

Little simplification then leads to (3.3). □

We end this section with a summation lemma, which we shall need in Sections 5 and 6 in order to compute the B_{n}, respectively D_{n}, decomposition numbers of arbitrary rank from those of full rank, and in Section 8 to derive enumerative results for (generalised) non-crossing partitions from our formulae for the decomposition numbers.

Lemma 4. Let M and r be non-negative integers. Then

∑_{m_{1}+2m_{2}+···+rm_{r}=r} \binom{M}{m_{1}, m_{2}, …, m_{r}} = \binom{M + r − 1}{r},  (3.4)

where the multinomial coefficient is defined by

\binom{M}{m_{1}, m_{2}, …, m_{r}} = \frac{M!}{m_{1}! m_{2}! ⋯ m_{r}! (M − m_{1} − m_{2} − ⋯ − m_{r})!}.

Proof. The identity results directly by comparing coefficients of z^{r} on both sides of the identity

(1 + z + z^{2} + z^{3} + ⋯)^{M} = (1 − z)^{−M}.

□

4. Decomposition numbers for type A

As was already pointed out in [28, Sec. 10], the decomposition numbers for type A_{n} have already been computed by Goulden and Jackson in [23, Theorem 3.2], albeit using a somewhat different language. (The condition on the sum l(α_{1}) + l(α_{2}) + ⋯ + l(α_{m}) is misstated throughout the latter paper. It should be replaced by l(α_{1}) + l(α_{2}) + ⋯ + l(α_{m}) = (m − 1)n + 1.) In our terminology, their result reads as follows.

Theorem 5. Let T_{1}, T_{2}, …, T_{d} be types with rk T_{1} + rk T_{2} + ⋯ + rk T_{d} = n, where

T_{i} = A_{1}^{m_{1}^{(i)}} ∗ A_{2}^{m_{2}^{(i)}} ∗ ⋯ ∗ A_{n}^{m_{n}^{(i)}}, i = 1, 2, …, d.

Then

N_{A_{n}}(T_{1}, T_{2}, …, T_{d}) = (n + 1)^{d−1} ∏_{i=1}^{d} \frac{1}{n − rk T_{i} + 1}\binom{n − rk T_{i} + 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}},  (4.1)

where the multinomial coefficient is defined as in Lemma 4.

Here we have used Stembridge’s [35] notation for the decomposition of types into a product of irreducibles; for example, the equation T = A_{2}^{3} ∗ A_{5} means that the root system of type T decomposes into the orthogonal product of 3 copies of root systems of type A_{2} and one copy of the root system of type A_{5}.

It was shown in [28, Theorem 10] that, upon applying the summation formula in Lemma 4 to the result in Theorem 5 in a suitable manner, one obtains a compact formula for all type A_{n} decomposition numbers.

Theorem 6. Let the types T_{1}, T_{2}, …, T_{d} be given, where

T_{i} = A_{1}^{m_{1}^{(i)}} ∗ A_{2}^{m_{2}^{(i)}} ∗ ⋯ ∗ A_{n}^{m_{n}^{(i)}}, i = 1, 2, …, d.

Then

N_{A_{n}}(T_{1}, T_{2}, …, T_{d}) = (n + 1)^{d−1}\binom{n + 1}{rk T_{1} + rk T_{2} + ⋯ + rk T_{d} + 1}

× ∏_{i=1}^{d} \frac{1}{n − rk T_{i} + 1}\binom{n − rk T_{i} + 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}, (4.2)

where the multinomial coefficient is defined as in Lemma 4. All other decomposition numbers N_{A_{n}}(T_{1}, T_{2}, …, T_{d}) are zero.

5. Decomposition numbers for type B

In this section we compute the decomposition numbers in type B_{n}. We show that one can extract the corresponding formulae from results of Bóna, Bousquet, Labelle and Leroux [12] on the enumeration of certain planar maps, which they call m-ary cacti. While reading the statement of the theorem, the reader should recall from Section 2 the distinction between group-theoretic and combinatorial decomposition numbers.

Theorem 7. (i) If T_{1}, T_{2}, …, T_{d} are types with rk T_{1} + rk T_{2} + ⋯ + rk T_{d} = n, where

T_{i} = A_{1}^{m_{1}^{(i)}} ∗ A_{2}^{m_{2}^{(i)}} ∗ ⋯ ∗ A_{n}^{m_{n}^{(i)}}, i = 1, 2, …, j − 1, j + 1, …, d,

and

T_{j} = B_{α} ∗ A_{1}^{m_{1}^{(j)}} ∗ A_{2}^{m_{2}^{(j)}} ∗ ⋯ ∗ A_{n}^{m_{n}^{(j)}},

for some α ≥ 1, then

N_{B_{n}}^{comb}(T_{1}, T_{2}, …, T_{d}) = n^{d−1}\binom{n − rk T_{j}}{m_{1}^{(j)}, m_{2}^{(j)}, …, m_{n}^{(j)}}_{∏_{i=1}^{d} ; i≠j} \frac{1}{n − rk T_{i}} \binom{n − rk T_{i}}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}},

(5.1)

where the multinomial coefficient is defined as in Lemma 4. For α ≥ 2, the number N_{B_{n}}(T_{1}, T_{2}, …, T_{d}) is given by the same formula.

(ii) If T_{1}, T_{2}, …, T_{d} are types with rk T_{1} + rk T_{2} + ⋯ + rk T_{d} = n, where then

N_{B_{n}}(T_{1}, T_{2}, …, T_{d}) = n^{d−1}( ∏_{i=1}^{d} \frac{1}{n − rk T_{i}} \binom{n − rk T_{i}}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}) ∑_{j=1}^{d} \frac{m_{1}^{(j)}(n − rk T_{j})}{m_{0}^{(j)} + 1},

(5.2)

where m_{0}^{(j)} = n − rk T_{j} − ∑_{s=1}^{n} m_{s}^{(j)}.

(iii) All other decomposition numbers N_{B_{n}}(T_{1}, T_{2}, …, T_{d}) and N_{B_{n}}^{comb}(T_{1}, T_{2}, …, T_{d}) with rk T_{1} + rk T_{2} + ⋯ + rk T_{d} = n are zero.

Proof. Determining the decomposition numbers

N_{B_{n}}(T_{1}, T_{2}, …, T_{d}) = N_{B_{n}}(T_{d}, …, T_{2}, T_{1})

(recall (2.2)), respectively

N_{B_{n}}^{comb}(T_{1}, T_{2}, …, T_{d}) = N_{B_{n}}^{comb}(T_{d}, …, T_{2}, T_{1}),

amounts to counting all possible factorisations

[1, 2, …, n] = σ_{d} ⋯ σ_{2}σ_{1},  (5.3)

where σ_{i} has type T_{i} as a parabolic Coxeter element, respectively has combinatorial type T_{i}. The reader should observe that the factorisation (5.3) is minimal, in the sense that

n = ℓ_{T} ([1, 2, …, n]) = ℓ_{T} (σ_{1}) + ℓ_{T} (σ_{2}) + ⋯ + ℓ_{T} (σ_{d}),

since ℓ_{T} (σ_{i}) = rk T_{i}, and since, by our assumption, the sum of the ranks of the T_{i}’s equals n. A further observation is that, in a factorisation (5.3), there must be at least one factor σ_{i} which contains a type B cycle in its (type B) disjoint cycle decomposition, because the sign of [1, 2, …, n] as an element of the group S_{2n} of all permutations of {1, 2, …, n, ¯1, ¯2, …, n̄} is −1, while the sign of any type A cycle is +1.

We first prove Claim (iii). Let us assume, by contradiction, that there is a minimal decomposition (5.3) in which, altogether, we find at least two type B cycles in the (type B) disjoint cycle decompositions of the σ_{i}’s. In that case, (5.3) has the form

[1, 2, …, n] = u_{1}κ_{1}u_{2}κ_{2}u_{3},  (5.4)

where κ_{1} and κ_{2} are two type B cycles, and u_{1}, u_{2}, u_{3} are the factors in between. Moreover, the factorisation (5.4) is minimal, meaning that

n = ℓ_{T} (u_{1}) + ℓ_{T} (κ_{1}) + ℓ_{T} (u_{2}) + ℓ_{T} (κ_{2}) + ℓ_{T} (u_{3}).  (5.5)

We may rewrite (5.4) as

[1, 2, …, n] = κ_{1}κ_{2}(κ_{2}^{−1}κ_{1}^{−1}u_{1}κ_{1}κ_{2})(κ_{2}^{−1}u_{2}κ_{2})u_{3},

or, setting u′_{1} = κ_{2}^{−1}κ_{1}^{−1}u_{1}κ_{1}κ_{2} and u′_{2} = κ_{2}^{−1}u_{2}κ_{2}, as

[1, 2, …, n] = κ_{1}κ_{2}u′_{1}u′_{2}u_{3}.  (5.6)

This factorisation is still minimal since u′_{1} is conjugate to u_{1} and u′_{2} is conjugate to u_{2}. At this point, we observe that κ_{1} must be a cycle of the form (2.8) with a_{1} < a_{2} < ⋯ < a_{k} < \overline{a_{1}} < \overline{a_{2}} < ⋯ < \overline{a_{k}} in the order 1 < 2 < ⋯ < n < ¯1 < ¯2 < ⋯ < n̄, because otherwise κ_{1} ≰_{T} [1, 2, …, n], which would contradict (5.6). A similar argument

2 _{1}^{1}  _{2}^{2}  ^{1}_{1}  _{3}^{3}  ^{2}_{2}  ^{3}_{3}  _{3} ^{3}_{3}^{3}  _{1} _{3}^{1}^{3}  _{1}^{1} _{3}^{3}_{1}_{2}  ^{1} ^{2}  ^{1}^{3}_{1} _{3}  _{1} ^{3}_{1}_{3}  ^{2}^{3}  _{2}_{3}^{1}_{¯1}  _{2}^{¯2}  _{3} ¯3  _{4}^{¯4}  _{5}^{¯5}  _{6} ^{¯6}_{7}  ^{¯7}_{8}  ¯8_{9}  ^{¯9}_{10}  \overline{10}

Figure 1. The 3-cactus corresponding to the factorisation (5.7)

applies to κ_{2}. Now, if κ_{1} and κ_{2} are not disjoint, then it is easy to see that ℓ_{T} (κ_{1}κ_{2}) < ℓ_{T} (κ_{1}) + ℓ_{T} (κ_{2}), whence

n = ℓ_{T} ([1, 2, …, n])
= ℓ_{T} (κ_{1}κ_{2}u′_{1}u′_{2}u_{3})
≤ ℓ_{T} (κ_{1}κ_{2}) + ℓ_{T} (u′_{1}) + ℓ_{T} (u′_{2}) + ℓ_{T} (u_{3})
≤ ℓ_{T} (κ_{1}κ_{2}) + ℓ_{T} (u_{1}) + ℓ_{T} (u_{2}) + ℓ_{T} (u_{3})
< ℓ_{T} (κ_{1}) + ℓ_{T} (κ_{2}) + ℓ_{T} (u_{1}) + ℓ_{T} (u_{2}) + ℓ_{T} (u_{3}),

a contradiction to (5.5). If, on the other hand, κ_{1} and κ_{2} are disjoint, then we can find i, j ∈ {1, 2, …, n, ¯1, ¯2, …, n̄}, such that i < j < κ_{1}(i) < κ_{2}(j) (in the above order of {1, 2, …, n, ¯1, ¯2, …, n̄}). In other words, if we represent κ_{1} and κ_{2} in the obvious way in a cyclic diagram (cf. [32, Sec. 2]), then they cross each other. However, in that case we have

κ_{1}κ_{2} ≰_{T} [1, 2, …, n],

contradicting the fact that (5.6) is a minimal factorisation. (This is one of the consequences of Biane’s group-theoretic characterisation [10, Theorem 1] of non-crossing partitions.)

We turn now to Claims (i) and (ii). In what follows, we shall show that the formulae (5.1) and (5.2) follow from results of Bóna, Bousquet, Labelle and Leroux [12] on the enumeration of m-ary cacti with a rotational symmetry. In order to explain this, we must first define a bijection between minimal factorisations (5.3) and certain planar maps. By a map, we mean a connected graph embedded in the plane such that edges do not intersect except in vertices. The maps which are of relevance here are maps in which faces different from the outer face intersect only in vertices, and are coloured with colours from {1, 2, …, d}. Such maps will be referred to as d-cacti from now on.^{1} Examples of 3-cacti can be found in Figures 1 and 2. In the figures, the faces different from the outer face are the shaded ones. Their colours are indicated by the numbers 1, 2, respectively 3, placed in the centre of the faces. Figure 1 shows a 3-cactus in which the vertices are labelled, while Figure 2 shows one in which the vertices are not labelled. (That one of the vertices in Figure 2 is marked by a bold dot should be ignored for the moment.)

In what follows, we need the concept of the rotator around a vertex v in a dcactus, which, by definition, is the cyclic list of colours of faces encountered in a clockwise journey around v. If, while travelling around v, we encounter the colours b_{1}, b_{2}, …, b_{k}, in this order, then we will write (b_{1}, b_{2}, …, b_{k})^{O} for the rotator, meaning that (b_{1}, b_{2}, …, b_{k})^{O} = (b_{2}, …, b_{k}, b_{1})^{O}, etc. For example, the rotator of all the vertices in the map in Figure 1 is (1, 2, 3)^{O}.

We illustrate the bijection between minimal factorisations (5.3) and d-cacti with an example. Take n = 10 and d = 3, and consider the factorisation

[1, 2, …, 10] = σ_{3}σ_{2}σ_{1},  (5.7)

where σ_{3} = ((7, 8)), σ_{2} = [2, 6, 8] ((1, ¯9, \overline{10})) ((4, 5)), and σ_{1} = ((1, ¯8)) ((2, 3, 5)). For each cycle (a_{1}, a_{2}, …, a_{k}) (sic!) of σ_{i}, we create a k-gon coloured i, and label its vertices a_{1}, a_{2}, …, a_{k} in clockwise order. (The warning “sic!” is there to avoid misunderstandings: for each type A “cycle” ((b_{1}, b_{2}, …, b_{k})) we create two k-gons, the vertices of one being labelled b_{1}, b_{2}, …, b_{k}, and the vertices of the other being labelled \overline{b_{1}}, \overline{b_{2}}, …, \overline{b_{k}}, while for each type B “cycle” [b_{1}, b_{2}, …, b_{k}] we create one 2k-gon with vertices labelled b_{1}, b_{2}, …, b_{k}, \overline{b_{1}}, \overline{b_{2}}, …, \overline{b_{k}}.) We glue these polygons into a d-cactus, the faces of which are these polygons plus the outer face, by identifying equally labelled vertices such that the rotator of each vertex is (1, 2, …, d). Figure 1 shows the outcome of this procedure for the factorisation (5.7).

The fact that the result of the procedure can be realised as a d-cactus follows from Euler’s formula. Namely, the number of faces corresponding to the polygons is 1 + 2∑_{i=1}^{d} ∑_{k=0}^{n} m_{k}^{(i)} (the 1 coming from the polygon corresponding to the type B cycle), the number of edges is 2α + 2 ∑_{i=1}^{d} ∑_{k=0}^{n} m_{k}^{(i)}(k + 1), and the number of vertices is 2n. Hence, if we include the outer face, the number of vertices minus the number of edges

1We warn the reader that our terminology deviates from the one in [12, 23]. We follow loosely the conventions in [25]. To be precise, our d-cacti in which the rotator around every vertex is (1, 2, …, d)^{O} are dual to the coloured d-cacti in [23], respectively d-ary cacti in [12], in the following sense: one is obtained from the other by “interchanging” the roles of vertices and faces, that is, given a d-cactus in our sense, one obtains a d-cactus in the sense of Goulden and Jackson by shrinking faces to vertices and blowing up vertices of degree δ to faces with δ vertices, keeping the incidence relations between faces and vertices. Another minor difference is that colours are arranged in counter-clockwise order in [12, 23], while we arrange colours in clockwise order.

2 _{1}^{1}  _{2}^{2}  ^{1}_{1}  _{3}^{3}  ^{2}_{2}  ^{3}_{3}  _{3} ^{3}_{3}^{3}  _{1} _{3}^{1}^{3}  _{1}^{1} _{3}^{3}_{1}_{2}  ^{1} ^{2}  ^{1}^{3}_{1} _{3}  _{1} ^{3}_{1}_{3}  ^{2}^{3}  _{2}_{3}

Figure 2. A rotation-symmetric 3-cactus with a marked vertex

plus the number of faces is

2n − 2α − 2 ∑_{i=1}^{d} ∑_{k=0}^{n} m_{k}^{(i)}(k + 1) + 2 ∑_{i=1}^{d} ∑_{k=0}^{n} m_{k}^{(i)} + 2

= 2n + 2 − 2α − 2 ∑_{i=1}^{d} ∑_{k=0}^{n} k · m_{k}^{(i)}

= 2n + 2 − 2 rk T_{1} − 2 rk T_{2} − ⋯ − 2 rk T_{d}

= 2,  (5.8)

according to our assumption concerning the sum of the ranks of the types T_{i}.

We may further simplify this geometric representation of a minimal factorisation (5.3) by deleting all vertex labels and marking the vertex which had label 1. If this simplification is applied to the 3-cactus in Figure 1, we obtain the 3-cactus in Figure 2. Indeed, the knowledge of which vertex carries label 1 allows us to reconstruct all other vertex labels as follows: starting from the vertex labelled 1, we travel clockwise along the boundary of the face coloured 1 until we reach the next vertex (that is, we traverse only a single edge); from there, we travel clockwise along the boundary of the face coloured 2 until we reach the next vertex; etc., until we have travelled along an edge bounding a face of colour d. The vertex that we have reached must carry label 2. Etc. Clearly, if drawn appropriately into the plane, a d-cactus resulting from an application of the above procedure to a minimal factorisation (5.3) is symmetric with respect to a rotation by 180^{∘}, the centre of the rotation being the centre of the regular 2α-gon corresponding to the unique type B cycle of σ_{j}; cf. Figure 2. In what follows, we shall abbreviate this property as rotation-symmetric.

In summary, under the assumptions of Claim (i), the decomposition number N_{B_{n}}^{comb}(T_{1}, T_{2}, …, T_{d}), respectively, if α ≥ 2, the decomposition number N_{B_{n}}(T_{1}, T_{2}, …, T_{d}) also, equals the number of all rotation-symmetric d-cacti on 2n vertices in which one vertex is marked and all vertices have rotator (1, 2, …, d)^{O}, with exactly m_{k}^{(i)} pairs of faces of colour i having k + 1 vertices, arranged symmetrically around a central face of colour j with 2α vertices.

Aside from the marking of one vertex, equivalent objects are counted in [12, Theorem 25]. In our language, modulo the “dualisation” described in Footnote 1, and upon replacing m by d, the objects which are counted in the cited theorem are d-cacti in which all vertices have rotator (1, 2, …, d)^{O}, and which are invariant under a rotation (not necessarily by 180^{∘}). To be precise, from the proof of [12, (81)] (not given in full detail in [12]) it can be extracted that the number of d-cacti on 2n vertices, in which all vertices have rotator (1, 2, …, d)^{O}, which are invariant under a rotation by (360/s)^{∘}, s being maximal with this property, and which have exactly 2m_{k}^{(i)} faces of colour i having k + 1 vertices arranged around a central face of colour j with 2α vertices, equals

(2n)^{d−2}s∑_{t}′μ(t/s)\binom{2(n − rk T_{j})/t}{2m_{1}^{(j)}/t, 2m_{2}^{(j)}/t, …, 2m_{n}^{(j)}/t}

·_{∏_{i=1}^{d} ; i≠j} \frac{1}{2(n − rk T_{i})}\binom{2(n − rk T_{i})/t}{2m_{1}^{(i)}/t, 2m_{2}^{(i)}/t, …, 2m_{n}^{(i)}/t}, (5.9)

where the sum extends over all t with s | t, t | 2α, and t | 2m_{k}^{(i)} for all i = 1, 2, …, d and k = 1, 2, …, n. Here, μ(·) is the Möbius function from number theory.^{2} In presenting the formula in the above form, we have also used the observation that, for all i (including i = j !), the number of type A cycles of σ_{i} is n − rk T_{i}.

As we said above, the d-cacti that we want to enumerate have one marked vertex, whereas the d-cacti counted by (5.9) have no marked vertex. However, given a d-cactus counted by (5.9), we have exactly 2n/s inequivalent ways of marking a vertex. Hence, recalling that the d-cacti that we want to count are invariant under a rotation by 180^{∘}, we must multiply the expression (5.9) by 2n/s, and then sum the result over all even s. Since, by definition of the Möbius function, we have

∑_{2|s|t} μ(t/s) = ∑_{s′| \frac{t}{2}} μ(t/2s′) = \begin{cases}1 & if \frac{t}{2} = 1, \\ 0 & otherwise, \end{cases}

the result of this summation is exactly the right-hand side of (5.1).

2Formula (81) in [12] does not distinguish the colour or the size of the central face (that is, in the language of [12]: the colour or the degree of the central vertex), therefore it is in fact a sum over all possible colours and sizes, represented there by the summations over i and h, respectively.

Finally, we prove Claim (ii). From what we already know, in a minimal factorisation (5.3) exactly one of the factors on the right-hand side must contain a type B cycle of length 1 in its (type B) disjoint cycle decomposition, σ_{j} say. As a parabolic Coxeter element, a type B cycle of length 1 has type A_{1}. Since all considerations in the proof of Claim (i) are also valid for α = 1, we may use Formula (5.1) with α = 1, and with m_{1}^{(j)} replaced by m_{1}^{(j)} − 1, to count the number of these factorisations, to obtain

n^{d−1}\binom{n − rk T_{j}}{m_{1}^{(j)} − 1, m_{2}^{(j)}, …, m_{n}^{(j)}}_{∏_{i=1}^{d} ; i≠j} \frac{1}{n − rk T_{i}} \binom{n − rk T_{i}}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}.

This has to be summed over j = 1, 2, …, d. The result is exactly (5.2).

The proof of the theorem is now complete. □

Combining the previous theorem with the summation formula of Lemma 4, we can now derive compact formulae for all type B_{n} decomposition numbers.

Theorem 8. (i) Let the types T_{1}, T_{2}, …, T_{d} be given, where

T_{i} = A_{1}^{m_{1}^{(i)}} ∗ A_{2}^{m_{2}^{(i)}} ∗ ⋯ ∗ A_{n}^{m_{n}^{(i)}}, i = 1, 2, …, j − 1, j + 1, …, d,

and

T_{j} = B_{α} ∗ A_{1}^{m_{1}^{(j)}} ∗ A_{2}^{m_{2}^{(j)}} ∗ ⋯ ∗ A_{n}^{m_{n}^{(j)}},

for some α ≥ 1. Then

N_{B_{n}}^{comb}(T_{1}, T_{2}, …, T_{d}) = n^{d−1}\binom{n}{rk T_{1} + rk T_{2} + ⋯ + rk T_{d}}

× \binom{n − rk T_{j}}{m_{1}^{(j)}, m_{2}^{(j)}, …, m_{n}^{(j)}}_{∏_{i=1}^{d} ; i≠j} \frac{1}{n − rk T_{i}} \binom{n − rk T_{i}}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}, (5.10)

where the multinomial coefficient is defined as in Lemma 4. For α ≥ 2, the number N_{B_{n}}(T_{1}, T_{2}, …, T_{d}) is given by the same formula.

(ii) Let the types T_{1}, T_{2}, …, T_{d} be given, where

T_{i} = A_{1}^{m_{1}^{(i)}} ∗ A_{2}^{m_{2}^{(i)}} ∗ ⋯ ∗ A_{n}^{m_{n}^{(i)}}, i = 1, 2, …, d.

Then

N_{B_{n}}^{comb}(T_{1}, T_{2}, …, T_{d})

= n^{d}\binom{n − 1}{rk T_{1} + rk T_{2} + ⋯ + rk T_{d}}( ∏_{i=1}^{d} \frac{1}{n − rk T_{i}} \binom{n − rk T_{i}}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}), (5.11)

whereas

N_{B_{n}}(T_{1}, T_{2}, …, T_{d})

= n^{d−1}\binom{n}{rk T_{1} + rk T_{2} + ⋯ + rk T_{d}}( ∏_{i=1}^{d} \frac{1}{n − rk T_{i}} \binom{n − rk T_{i}}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}})

× (n − rk T_{1} − rk T_{2} − ⋯ − rk T_{d} + ∑_{j=1}^{d} \frac{m_{1}^{(j)}(n − rk T_{j})}{m_{0}^{(j)} + 1}) , (5.12)

with m_{0}^{(j)} = n − rk T_{j} − ∑_{s=1}^{n} m_{s}^{(j)}.

(iii) All other decomposition numbers N_{B_{n}}(T_{1}, T_{2}, …, T_{d}) and N_{B_{n}}^{comb}(T_{1}, T_{2}, …, T_{d}) are zero.

Proof. If we write r for n − rk T_{1} − rk T_{2} − ⋯ − rk T_{d}, then for Φ = B_{n} the relation (2.3) becomes

N_{B_{n}}(T_{1}, T_{2}, …, T_{d}) = ∑_{T:rk T =r}N_{B_{n}}(T_{1}, T_{2}, …, T_{d}, T),  (5.13)

with the same relation holding for N_{B_{n}}^{comb} in place of N_{B_{n}}.

In order to prove (5.10), we let T = A_{1}^{m_{1}} ∗ A_{2}^{m_{2}} ∗ ⋯ ∗ A_{n}^{m_{n}} and use (5.1) in (5.13), to obtain

N_{B_{n}}^{comb}(T_{1}, T_{2}, …, T_{d}) = ∑_{m_{1}+2m_{2}+···+nm_{n}=r} n^{d} \frac{1}{n − r}\binom{n − r}{m_{1}, m_{2}, …, m_{n}}

· \binom{n − rk T_{j}}{m_{1}^{(j)}, m_{2}^{(j)}, …, m_{n}^{(j)}}_{∏_{i=1}^{d} ; i≠j} \frac{1}{n − rk T_{i}} \binom{n − rk T_{i}}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}.

If we use (3.4) with M = n − r, we arrive at our claim after little simplification.

In order to prove (5.11), we let T = B_{α} ∗ A_{1}^{m_{1}} ∗ A_{2}^{m_{2}} ∗ ⋯ ∗ A_{n}^{m_{n}} in (5.13). The important point to be observed here is that, in contrast to the previous argument, in the present case T must have a factor B_{α}. Subsequently, use of (5.1) in (5.13) yields

N_{B_{n}}^{comb}(T_{1}, T_{2}, …, T_{d}) = ∑_{α=1}^{n} ∑_{m_{1}+2m_{2}+···+nm_{n}=r−α} n^{d}\binom{n − r}{m_{1}, m_{2}, …, m_{n}}

· ∏_{i=1}^{d} \frac{1}{n − rk T_{i}} \binom{n − rk T_{i}}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}. (5.14)

Now we use (3.4) with r replaced by r − α and M = n − r, and subsequently the elementary summation formula

∑_{α=1}^{n} \binom{n − α − 1}{r − α} = ∑_{α=1}^{n} \binom{n − α − 1}{n − r − 1} = \binom{n − 1}{n − r} = \binom{n − 1}{r − 1}.  (5.15)

Then, after little rewriting, we arrive at our claim.

To establish (5.12), we must recall that the group-theoretic type A_{1} does not distinguish between a type A cycle ((i, j)) = (i, j) (ī, j̄) and a type B cycle [i] = (i, ī). Hence, to obtain N_{B_{n}}(T_{1}, T_{2}, …, T_{d}) in the case that no T_{i} contains a B_{α} for α ≥ 2, we must add the expression (5.11) and the expressions (5.10) with m_{1}^{(j)} replaced by m_{1}^{(j)} −1 over j = 1, 2, …, d. As is not difficult to see, this sum is indeed equal to (5.12). □

6. Decomposition numbers for type D

In this section we compute the decomposition numbers for the type D_{n}. Theorem 9 gives the formulae for the full rank decomposition numbers, while Theorem 10 presents the implied formulae for the decomposition numbers of arbitrary rank. To our knowledge, these are new results, which did not appear earlier in the literature on map enumeration or on the connection coefficients in the symmetric group or other Coxeter groups. Nevertheless, the proof of Theorem 9 is entirely in the spirit of the fundamental paper [23], in that the problem of counting factorisations is translated into a problem of map enumeration, which is then solved by a generating function approach that requires the use of the Lagrange–Good formula for coefficient extraction.

We begin with the result concerning the full rank decomposition numbers in type D_{n}. While reading the statement of the theorem below, the reader should again recall from Section 2 the distinction between group-theoretic and combinatorial decomposition numbers.

Theorem 9. (i) If T_{1}, T_{2}, …, T_{d} are types with rk T_{1} + rk T_{2} + ⋯ + rk T_{d} = n, where

T_{i} = A_{1}^{m_{1}^{(i)}} ∗ A_{2}^{m_{2}^{(i)}} ∗ ⋯ ∗ A_{n}^{m_{n}^{(i)}}, i = 1, 2, …, j − 1, j + 1, …, d,

and

T_{j} = D_{α} ∗ A_{1}^{m_{1}^{(j)}} ∗ A_{2}^{m_{2}^{(j)}} ∗ ⋯ ∗ A_{n}^{m_{n}^{(j)}},

for some α ≥ 2, then

N_{D_{n}}^{comb}(T_{1}, T_{2}, …, T_{d}) = (n − 1)^{d−1}\binom{n − rk T_{j}}{m_{1}^{(j)}, m_{2}^{(j)}, …, m_{n}^{(j)}}

×_{∏_{i=1}^{d} ; i≠j} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}, (6.1)

where the multinomial coefficient is defined as in Lemma 4. For α ≥ 4, the number N_{D_{n}}(T_{1}, T_{2}, …, T_{d}) is given by the same formula.

(ii) If T_{1}, T_{2}, …, T_{d} are types with rk T_{1} + rk T_{2} + ⋯ + rk T_{d} = n, where then

N_{D_{n}}^{comb}(T_{1}, T_{2}, …, T_{d})

= (n − 1)^{d−1} (2 ∑_{j=1}^{d} \binom{n − rk T_{j}}{m_{1}^{(j)}, m_{2}^{(j)}, …, m_{n}^{(j)}}_{∏_{i=1}^{d} ; i≠j} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}

−2(d − 1)(n − 1)∏_{i=1}^{d} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}) , (6.2)

while N_{D_{n}}(T_{1}, T_{2}, …, T_{d})

= (n − 1)^{d−1} (∑_{j=1}^{d} (_{∏_{i=1}^{d} ; i≠j} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}})(2\binom{n − rk T_{j}}{m_{1}^{(j)}, m_{2}^{(j)}, …, m_{n}^{(j)}}

+ \binom{n − rk T_{j}}{m_{1}^{(j)}, m_{2}^{(j)}, m_{3}^{(j)} − 1, m_{4}^{(j)}, …, m_{n}^{(j)}} + \binom{n − rk T_{j}}{m_{1}^{(j)} − 2, m_{2}^{(j)}, …, m_{n}^{(j)}})

−2(d − 1)(n − 1)∏_{i=1}^{d} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}) . (6.3)

(iii) All other decomposition numbers N_{D_{n}}(T_{1}, T_{2}, …, T_{d}) and N_{D_{n}}^{comb}(T_{1}, T_{2}, …, T_{d}) with rk T_{1} + rk T_{2} + ⋯ + rk T_{d} = n are zero. Remark. These formulae must be correctly interpreted when T_{i} contains no D_{α} and rk T_{i} = n − 1. In that case, because of n − 1 = rk T_{i} = m_{1}^{(i)} + 2m_{2}^{(i)} + ⋯ + nm_{n}^{(i)}, there must be an ℓ, 1 ≤ ℓ ≤ n − 1, with m_{ℓ}^{(i)} ≥ 1. We then interpret the term

\frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}

as

\frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}} = \frac{1}{m_{ℓ}^{(i)}} \binom{n − rk T_{i} − 2}{m_{1}^{(i)}, …, m_{ℓ}^{(i)} − 1, …, m_{n}^{(i)}},

where the multinomial coefficient is zero whenever

−1 = n − rk T_{i} − 2 < m_{1}^{(i)} + ⋯ + (m_{ℓ}^{(i)} − 1) + ⋯ + m_{n}^{(i)},

except when all of m_{1}^{(i)}, …, m_{ℓ}^{(i)} − 1, …, m_{n}^{(i)} are zero. Explicitly, one must read

\frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}} = 0

if rk T_{i} = n − 1 but T_{i} ≠ A_{n−1}, and

\frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}} = 1

if T_{i} = A_{n−1}.

Proof of Theorem 9. Determining the decomposition number

N_{D_{n}}(T_{1}, T_{2}, …, T_{d}) = N_{D_{n}}(T_{d}, …, T_{2}, T_{1})

(recall (2.2)), respectively

N_{D_{n}}^{comb}(T_{1}, T_{2}, …, T_{d}) = N_{D_{n}}^{comb}(T_{d}, …, T_{2}, T_{1}),

amounts to counting all possible factorisations

(1, 2, …, n − 1, ¯1, ¯2, …, \overline{n − 1}) (n, n̄) = σ_{d} ⋯ σ_{2}σ_{1},  (6.4)

where σ_{i} has type T_{i} as a parabolic Coxeter element, respectively has combinatorial type T_{i}. Here also, the factorisation (6.4) is minimal in the sense that

n = ℓ_{T} ((1, 2, …, n − 1, ¯1, ¯2, …, \overline{n − 1}) (n, n̄)) = ℓ_{T} (σ_{1}) + ℓ_{T} (σ_{2}) + ⋯ + ℓ_{T} (σ_{d}),

since ℓ_{T} (σ_{i}) = rk T_{i}, and since, by our assumption, the sum of the ranks of the T_{i}’s equals n.

We first prove Claim (iii). Let us assume, for contradiction, that there is a minimal factorisation (6.4), in which, altogether, we find at least two type B cycles of length ≥ 2 in the (type B) disjoint cycle decompositions of the σ_{i}’s. It can then be shown by arguments similar to those in the proof of Claim (iii) in Theorem 7 that this leads to a contradiction. Hence, “at worst,” we may find a type B cycle of length 1, (a, ā) say, and another type B cycle, κ say. Both of them must be contained in the disjoint cycle decomposition of one of the σ_{i}’s since all the σ_{i}’s are elements of W (D_{n}). Given that κ has length α − 1, the product of both, (a, ā) κ, is of combinatorial type D_{α}, α ≥ 2, whereas, as a parabolic Coxeter element, it is of type D_{α} only if α ≥ 4. If α = 3, then it is a parabolic Coxeter element of type A_{3}, and if α = 2 it is of type A_{1}^{2}. Thus, we are actually in the cases to which Claims (i) and (ii) apply.

To prove Claim (i), we continue this line of argument. By a variation of the conjugation argument (5.4)–(5.6), we may assume that these two type B cycles are contained in σ_{d}, σ_{d} = (a, ā) κ σ′_{d} say, where, as above, (a, ā) is the type B cycle of length 1 and κ is the other type B cycle, and where σ′_{d} is free of type B cycles. In that case, (6.4) takes the form

c = (1, 2, …, n − 1, ¯1, ¯2, …, \overline{n − 1}) (n, n̄) = (a, ā) κ σ′_{d} ⋯ σ_{1}.  (6.5)

If a ≠ n, κ ≠ (n, n̄), and if κ does not fix n, then (a, ā)κ ≰_{T} c, a contradiction. Likewise, if a ≠ n, κ = [b_{1}, b_{2}, …, b_{k}] with n ∉ {b_{1}, b_{2}, …, b_{k}}, then (a, ā) κ ≰_{T} [1, 2, …, n − 1], again a contradiction. Hence, we may assume that a = n, whence (a, ā) κ = κ (n, n̄) forms a parabolic Coxeter element of type D_{α}, given that κ has length α − 1. We are then in the position to determine all possible factorisations of the form (6.5), which reduces to

(1, 2, …, n − 1, ¯1, ¯2, …, \overline{n − 1}) = [1, 2, …, n − 1] = κσ′_{d} ⋯ σ_{1}.  (6.6)

This is now a minimal type B factorisation of the form (5.3) with n replaced by n − 1. We may therefore use Formula (5.1) with n replaced by n − 1, and with rk T_{j} replaced by rk T_{j} − 1. These substitutions lead exactly to (6.1).

Finally, we turn to Claim (ii). First we discuss two degenerate cases which come from the identifications D_{3} ∼ A_{3}, respectively D_{2} ∼ A_{1}^{2}, and which only occur for N_{D_{n}}(T_{1}, T_{2}, …, T_{d}) (but not for the combinatorial decomposition numbers N_{D_{n}}^{comb}(T_{1}, T_{2}, …, T_{d})). It may happen that one of the factors in (6.4), let us say, without loss of generality, σ_{d}, contains a type B cycle of length 1 and one of length 2 in its disjoint cycle decomposition; that is, σ_{d} may contain

(n, n̄) [a, b] = (n, n̄) (a, b, ā, b̄) = [a, b] [b, n] [b, n̄].

As a parabolic Coxeter element, this is of type A_{3}. By the reduction (6.5)–(6.6), we may count the number of these possibilities by Formula (5.1) with n replaced by n − 1, rk T_{j} replaced by rk T_{j} −1, and m_{3}^{(j)} replaced by m_{3}^{(j)} −1. This explains the second term in the factor in big parentheses on the right-hand side of (6.3). On the other hand, it may happen that one of the factors in (6.4), let us say again, without loss of generality, σ_{d}, contains two type B cycles of length 1 in its disjoint cycle decomposition; that is, σ_{d} may contain (n, n̄) (a, ā). As a parabolic Coxeter element, this is of type A_{1}^{2}. By the reduction (6.5)–(6.6), we may count the number of these possibilities by Formula (5.1) with n replaced by n − 1, rk T_{j} replaced by rk T_{j} − 1, and m_{1}^{(j)} replaced by m_{1}^{(j)} − 2. This explains the third term in the factor in big parentheses on the right-hand side of (6.3).

From now on we may assume that none of the σ_{i}’s contains a type B cycle in its (type B) disjoint cycle decomposition. To determine the number of minimal factorisations (6.4) in this case, we construct again a bijection between these factorisations and certain maps. In what follows, we will still use the concept of a rotator, introduced in the proof of Theorem 7. We apply again the procedure described in that proof. That is, for each (ordinary) cycle (a_{1}, a_{2}, …, a_{k}) of σ_{i}, we create a k-gon coloured i, label its vertices a_{1}, a_{2}, …, a_{k} in clockwise order, and glue these polygons into a map by identifying equally labelled vertices such that the rotator of each vertex is (1, 2, …, d). However, this map can be embedded in the plane only if we allow the creation of an inner face corresponding to the cycle (n, n̄) on the left-hand side of (6.4) (the outer face corresponding to the large cycle (1, 2, …, n − 1, ¯1, ¯2, …, \overline{n − 1})). Moreover, this inner face must be bounded by 2d edges. We call such a map, in which all faces except the outer face and an inner face intersect only in vertices, and are coloured with colours from {1, 2, …, d}, and in which the inner face is bounded by 2d edges, a d-atoll. For example, if we take n = 10 and d = 3, and consider the factorisation

(1, 2, …, 9, ¯1, ¯2, …, ¯9) (10, \overline{10}) = σ_{3}σ_{2}σ_{1},  (6.7)

where σ_{3} = ((1, 4, \overline{10}, ¯7)), σ_{2} = ((1, 3)) ((4, 6, 10)) ((7, 8, 9)), and σ_{1} = ((1, 2)) ((4, 5)), and apply this procedure, we obtain the 3-atoll in Figure 3. In the figure, the faces corresponding to cycles are shaded. As in Figures 1 and 2, the outer face is not shaded. Here, there is in addition an inner face which is not shaded, the face formed by the vertices 4, 10, ¯4, \overline{10}. Again, the colours of the shaded faces are indicated by the numbers 1, 2, respectively 3, placed in the centre of the faces.

3 3 2 2 ^{2}_{2}  ^{1}_{1}  ^{1}_{1}  ^{1}^{3}_{1}_{3}  ^{3}^{1}_{1}_{3}  _{1} _{3} ^{1}^{3} _{1}^{1}  _{2}^{2}  _{3} _{2} _{1} _{3}^{3}^{2}^{1}^{3}  _{1}_{2}_{3}^{1}^{3}^{2}  _{1}^{¯1}  _{2}^{¯2}  _{3}^{¯3}  _{4}^{¯4}  _{5}^{¯5}  _{6}^{¯6}_{7}  ^{¯7}_{8}  ^{¯8}_{9}  ^{¯9}_{10}  ^{\overline{10}}

Figure 3. The 3-atoll corresponding to the factorisation (6.7)

Unsurprisingly, the fact that the result of the procedure can be realised as a d-atoll follows again from Euler’s formula. More precisely, the number of faces corresponding to the polygons is 2∑_{i=1}^{d} ∑_{k=0}^{n} m_{k}^{(i)}, the number of edges is 2 ∑_{i=1}^{d} ∑_{k=0}^{n} m_{k}^{(i)}(k + 1), and the number of vertices is 2n. Hence, if we include the outer face and the inner face, the number of vertices minus the number of edges plus the number of faces is

2n − 2 ∑_{i=1}^{d} ∑_{k=0}^{n} m_{k}^{(i)}(k + 1) + 2 ∑_{i=1}^{d} ∑_{k=0}^{n} m_{k}^{(i)} + 2 = 2n + 2 − 2 ∑_{i=1}^{d} ∑_{k=0}^{n} k · m_{k}^{(i)}
= 2n + 2 − 2 rk T_{1} − 2 rk T_{2} − ⋯ − 2 rk T_{d}
= 2,  (6.8)

according to our assumption concerning the sum of the ranks of the types T_{i}.

Again, we may further simplify this geometric representation of a minimal factorisation (6.4) by deleting all vertex labels, marking the vertex which had label 1 with •, and marking the vertex that had label n with ■. If this simplification is applied to the 3-atoll in Figure 3, we obtain the 3-atoll in Figure 4. Clearly, if drawn appropriately into the plane, a d-atoll resulting from an application of the above procedure to a minimal factorisation (6.4) is symmetric with respect to a rotation by 180^{∘}, the centre of the rotation being the centre of the inner face; cf. Figure 4. As earlier, we shall abbreviate

3 3 2 2 ^{2}_{2}  ^{1}_{1}  ^{1}_{1}  ^{1}^{3}_{1}_{3}  ^{3}^{1}_{1}_{3}  _{1} _{3} ^{1}^{3} _{1}^{1}  _{2}^{2}  _{3} _{2} _{1} _{3}^{3}^{2}^{1}^{3}  _{1}_{2}_{3}^{1}^{3}^{2}  _{■}

Figure 4. A rotation-symmetric 3-atoll with two marked vertices

this property as rotation-symmetric. In fact, there is not much freedom for the choice of the vertex marked by ■ once a vertex has been marked by •. Clearly, if we run through the vertex labelling process described in the proof of Theorem 7, labelling 1 the vertex which is marked by •, we shall reconstruct the labels 1, 2, …, n − 1, ¯1, ¯2, …, \overline{n − 1}. This leaves only 2 vertices incident to the inner face unlabelled, one of which will have to carry the mark ■.

In summary, under the assumptions of Claim (ii), the number of minimal factorisations (6.4), in which none of the σ_{i}’s contains a type B cycle in its disjoint cycle decomposition, equals twice the number of all rotation-symmetric d-atolls on 2n vertices, in which one vertex is marked by •, all vertices have rotator (1, 2, …, d)^{O}, and with exactly m_{k}^{(i)} pairs of faces of colour i having k + 1 vertices, arranged symmetrically around the inner face (which is not coloured). Let us denote the number of these d-atolls by N′_{D_{n}}(T_{1}, T_{2}, …, T_{d}).

We must now enumerate these d-atolls. First of all, introducing a figure of speech, we shall refer to coloured faces of a d-atoll which share an edge with the inner face but not with the outer face as faces “inside the d-atoll,” and all others as faces “outside the d-atoll.” For example, in Figure 4 we find two faces inside the 3-atoll, namely the two loop faces attached to the vertices labelled 10, respectively \overline{10}, in Figure 3. Since, in a d-atoll, the inner face is bounded by exactly 2d edges, inside the d-atoll, we find only coloured faces containing exactly one vertex. Next, we travel counter-clockwise around the inner face and record the coloured faces sharing an edge with both the inner and outer faces. Thus we obtain a list of the form

F_{1}, F_{2}, …, F_{ℓ}, F_{ℓ+1}, …, F_{2ℓ},

where, except possibly for the marking, F_{h+ℓ} is an identical copy of F_{h}, h = 1, 2, …, ℓ. In Figure 4, this list contains four faces, F̃_{1}, F̃_{2}, F̃_{3}, F̃_{4}, where F̃_{1} and F̃_{3} are the two quadrangles of colour 3, and where F̃_{2} and F̃_{4} are the two triangles of colour 2 connecting the two quadrangles.

Continuing the general argument, let the colour of F_{h} be i_{h}. Inside the d-atoll, because of the rotator condition, there must be {i_{h+1}−i_{h}−1}_{d} faces (containing just one vertex) incident to the common vertex of F_{h} and F_{h+1} coloured {i_{h}+1}_{d}, …, {i_{h+1}−1}_{d}, where, by definition,

\{x\}_{d} := \begin{cases}x, & if 0 ≤ x ≤ d \\ x + d, & if x < 0 \\ x − d, & if x > d, \end{cases}

and where i_{h+ℓ} = i_{h}, h = 1, 2, …, ℓ. Here, if {i_{h} + 1}_{d} > {i_{h+1} − 1}_{d}, the sequence of colours {i_{h} + 1}_{d}, …, {i_{h+1} − 1}_{d} must be interpreted “cyclically,” that is, as {i_{h} + 1}_{d}, {i_{h}+1}_{d}+1, …, d, 1, 2, …, {i_{h+1}−1}_{d}. As we observed above, the number of edges bounding the inner face is 2d. On the other hand, using the notation just introduced, this number also equals

2 ∑_{h=1}^{ℓ}{i_{h+1} − i_{h}}_{d} = 2 ∑_{h=1}^{ℓ} ((i_{h+1} − i_{h}) + d · χ(i_{h+1} < i_{h})) = 2d ∑_{h=1}^{ℓ} χ(i_{h+1} < i_{h}).

Hence, there is precisely one h for which i_{h+1} < i_{h}. Without loss of generality, we may assume that h = ℓ, so that i_{1} < i_{2} < ⋯ < i_{ℓ}.

The ascending colouring of the faces F_{1}, F_{2}, …, F_{ℓ} breaks the (rotation) symmetry of the d-atoll. Therefore, we may first enumerate d-atolls without any marking, and multiply the result by the number of all possible markings, which is n − 1. More precisely, let N′′_{D_{n}}(T_{1}, T_{2}, …, T_{d}) denote the number of all rotation-symmetric d-atolls on 2n vertices, in which all vertices have rotator (1, 2, …, d)^{O}, and with exactly m_{k}^{(i)} pairs of faces of colour i having k + 1 vertices, arranged symmetrically around the inner face (which is not coloured). Then,

N_{D_{n}}(T_{1}, T_{2}, …, T_{d}) = 2N′_{D_{n}}(T_{1}, T_{2}, …, T_{d})
= 2(n − 1)N′′_{D_{n}}(T_{1}, T_{2}, …, T_{d}).  (6.9)

We use a generating function approach to determine N′′_{D_{n}}(T_{1}, T_{2}, …, T_{d}), which requires a combinatorial decomposition of our objects. Let G(z) be the generating function

G(z) = ∑_{A∈A} w(A),  (6.10)

where A is the set of all rotation-symmetric d-atolls, in which all vertices have rotator (1, 2, …, d)^{O}, and where

w(A) = ∏_{i=1}^{d} z_{i}^{\frac{1}{2} #(faces of A with colour i)} ∏_{i=1}^{d} ∏_{k=1}^{∞} p_{i,k}^{\frac{1}{2} #(faces of A with colour i and k vertices)}.

Here, z = (z_{1}, z_{2}, …, z_{d}), with the z_{i}’s, i = 1, 2, …, d, and the p_{i,k}, i = 1, 2, …, d, k = 1, 2, …, being indeterminates. Clearly, in view of the bijection between minimal factorisations (6.4) and d-atolls described earlier, and by (6.9), we have

N_{D_{n}}(T_{1}, T_{2}, …, T_{d}) = 2(n − 1) ⟨z^{c} ∏_{i=1}^{d} ∏_{k=0}^{n} p_{i,k+1}^{m_{k}^{(i)}}⟩ G(z),  (6.11)

where c = (c_{1}, c_{2}, …, c_{d}), with c_{i} equal to the number of type A cycles of σ_{i}; that is, c_{i} = ∑_{k=0}^{n} m_{k}^{(i)}, i = 1, 2, …, d. Here, and in the sequel, we use the multi-index notation introduced at the beginning of Section 3. For later use, we observe that, for all i, c_{i} is related to rk T_{i} via

c_{i} = n − rk T_{i}.  (6.12)

Now, let A be a d-atoll in A such that the faces which share an edge with both the inner and outer faces are

F_{1}, F_{2}, …, F_{ℓ}, F_{ℓ+1}, …, F_{2ℓ},

where F_{h+ℓ} is an identical copy of F_{h}, where the colour of F_{h} is i_{h}, h = 1, 2, …, ℓ, and with i_{1} < i_{2} < ⋯ < i_{ℓ}. We decompose A by separating from each other the polygons which touch in vertices of the inner face. The decomposition in the case of our example in Figure 4 is shown in Figure 5. Ignoring identical copies which are there due to the rotation symmetry, we obtain a list

K_{1}, L_{i_{1}+1}^{(1)}, …, L_{i_{2}−1}^{(1)}, C_{i_{2}+1}^{(1)}, …, C_{d}^{(1)}, C_{1}^{(1)}, …, C_{i_{1}−1}^{(1)},

K_{2}, L_{i_{2}+1}^{(2)}, …, L_{i_{3}−1}^{(2)}, C_{i_{3}+1}^{(2)}, …, C_{d}^{(2)}, C_{1}^{(2)}, …, C_{i_{2}−1}^{(2)}, …

K_{ℓ}, L_{i_{ℓ}+1}^{(ℓ)}, …, L_{d}^{(ℓ)}, L_{1}^{(ℓ)}, …, L_{i_{1}−1}^{(ℓ)}, C_{i_{1}+1}^{(ℓ)}, …, C_{i_{ℓ}−1}^{(ℓ)}, (6.13)

where K_{h} is the d-cactus containing the face F_{h}, and, hence, a d-cactus in which all but two neighbouring vertices have rotator (1, 2, …, d)^{O}, the latter two vertices being incident to just one face, which is of colour i_{h}, where L_{j}^{(h)} is a face of colour j with just one vertex, and where C_{j}^{(h)} is a d-cactus in which all but one vertex have rotator (1, 2, …, d)^{O}, the distinguished vertex being incident to just one face, which is of colour j, h = 1, 2, …, ℓ and j = 1, 2, …, d. With this notation, our example in Figure 5 is one in which ℓ = 2, i_{1} = 2, i_{2} = 3.

The d-cacti K_{h} can be further decomposed. Namely, assuming that the face F_{h} is a k-gon (of colour i_{h}), let C_{1}, C_{2}, …, C_{k−2} be the d-cacti incident to this k-gon, read in clockwise order, starting with the d-cactus to the left of the two distinguished vertices. Figure 6 illustrates this further decomposition of the d-cactus K_{2} from Figure 5. After removal of F_{h}, we are left with the ordered collection C_{1}, C_{2}, …, C_{k−2} of d-cacti, each of which having the property that the rotator of all but one vertex is (1, 2, …, d)^{O}, the exceptional vertex having rotator (1, …, i_{h} − 1, i_{h} + 1, …, d)^{O}. By separating from each other the polygons of colours 1, …, i_{h} − 1, i_{h} + 1, …, d which

K_{1}2_{1} _{3}  _{C_{1}^{(1)}}_{1}_{3} _{2}  ^{K_{2}} 3 ^{2}^{1} ^{1}^{3}  ^{3}^{1}_{2}_{1} _{3}_{1}^{2}_{3}^{L_{1}^{(2)}}^{1}

Figure 5. The decomposition of the 3-atoll in Figure 4

touch in the exceptional vertex, each d-cactus C_{i} in turn can be decomposed into dcacti C_{i,1}, …, C_{i,i_{h}−1}, C_{i,i_{h}+1}, …, C_{i,d} with C_{i,j} ∈ C_{j} for all k, where C_{j} denotes the set of all d-cacti in which all but one vertex have rotator (1, 2, …, d)^{O}, the distinguished vertex being incident to just one face, which is of colour j.

Let ω_{j}(z) denote the generating function for the d-cacti in C_{j}, that is,

ω_{j}(z) = ∑_{C∈C_{j}} w(C).  (6.14)

Furthermore, for i = 1, 2, …, d, define the formal power series P_{i}(u) in one variable u via

P_{i}(u) = ∑_{k=1}^{∞} p_{i,k}u^{k−1}.

Then, by the decomposition (6.13) and the further decomposition of the K_{h}’s that we just described, the contribution of the above d-atolls to the generating function (6.10)

3 ^{C_{1}}^{2}^{1} ^{1}^{3}  ^{3}^{1}_{C_{2}}_{2}_{1} _{3}_{1}_{2}_{3}

Figure 6. The decomposition of K_{2} in Figure 5

is

( ∏_{j=1}^{ℓ} \frac{z_{i_{j}}ω_{i_{j}}(z)}{ω_{1}(z) ⋯ ω_{d}(z)} (P_{i_{j}} (\frac{ω_{1}(z) ⋯ ω_{d}(z)}{ω_{i_{j}}(z)}) − p_{i_{j},1}) )

× (\frac{∏_{j=1}^{d} z_{j}p_{j,1}}{∏_{j=1}^{ℓ} z_{i_{j}}p_{i_{j},1}} ) \frac{(ω_{1}(z) ⋯ ω_{d}(z))^{ℓ−1}}{∏_{j=1}^{ℓ} ω_{i_{j}}(z)}

= ( ∏_{j=1}^{d} \frac{z_{j}p_{j,1}}{ω_{j}(z)}) ∏_{j=1}^{ℓ} (\frac{P_{i_{j}} (\frac{ω_{1}(z)···ω_{d}(z)}{ω_{i_{j}} (z)})}{p_{i_{j},1}} − 1) ,

the term in the first line corresponding to the contribution of the K_{j}’s, the first term in the second line corresponding to the contribution of the L_{k}^{(j)}’s, and the second term in the second line corresponding to the contribution of the C_{k}^{(j)}’s. These expressions must be summed over ℓ = 2, 3, …, d and all possible choices of 1 ≤ i_{1} < i_{2} < ⋯ < i_{ℓ} ≤ d to obtain the desired generating function G(z), that is,

G(z) = ( ∏_{j=1}^{d} \frac{z_{j}p_{j,1}}{ω_{j}(z)}) ∑_{ℓ=2}^{d} ∑_{1≤i_{1}<i_{2}<···<i_{ℓ}≤d} ∏_{j=1}^{ℓ} (\frac{P_{i_{j}} (\frac{ω_{1}(z)···ω_{d}(z)}{ω_{i_{j}} (z)})}{p_{i_{j}}, 1} − 1)

= ( ∏_{j=1}^{d} \frac{z_{j}p_{j,1}}{ω_{j}(z)}) (∏_{j=1}^{d} \frac{P_{j} (\frac{ω_{1}(z)···ω_{d}(z)}{ω_{j}(z)})}{p_{j,1}} − ∑_{j=1}^{d} (\frac{P_{j} (\frac{ω_{1}(z)···ω_{d}(z)}{ω_{j}(z)})}{p_{j,1}} − 1) − 1) . (6.15)

Here we have used the elementary identity

∑_{ℓ=0}^{d} ∑_{1≤i_{1}<i_{2}<···<i_{ℓ}≤d} X_{i_{1}}X_{i_{2}} ⋯ X_{i_{ℓ}} = (1 + X_{1})(1 + X_{2}) ⋯ (1 + X_{d}).

Before we are able to proceed, we must find functional equations for the generating functions ω_{j}(z), j = 1, 2, …, d. Given a d-cactus C in C_{j} such that the distinguished vertex is incident to a k-gon (of colour j), we decompose it in a manner analogous to the decomposition of K_{h} above. To be more precise, let C_{1}, C_{2}, …, C_{k−1} be the d-cacti incident to this k-gon, read in clockwise order, starting with the d-cactus to the left of the distinguished vertex. After removal of the k-gon, we are left with the ordered collection C_{1}, C_{2}, …, C_{k−1} of d-cacti, each of which having the property that the rotator of all but one vertex is (1, 2, …, d)^{O}, the exceptional vertex having rotator (1, …, j − 1, j + 1, …, d)^{O}. By separating from each other the polygons of colours 1, …, j − 1, j + 1, …, d which touch in the exceptional vertex, each d-cactus C_{i} in turn can be decomposed into d-cacti C_{i,1}, …, C_{i,j−1}, C_{i,j+1}, …, C_{i,d} with C_{i,k} ∈ C_{k} for all k. The upshot of these combinatorial considerations is that

ω_{j}(z) = z_{j}P_{j}(ω_{1}(z) ⋯ ω_{d}(z)/ω_{j}(z)), j = 1, 2, …, d,

or, equivalently,

z_{j} = \frac{ω_{j}(z)}{P_{j}(ω_{1}(z) ⋯ ω_{d}(z)/ω_{j}(z))}, j = 1, 2, …, d.

Using this relation, the expression (6.15) for G(z) may now be further simplified, and we obtain

G(z) = 1 − ∏_{j=1}^{d} \frac{p_{j,1}}{P_{j} (\frac{ω_{1}(z)···ω_{d}(z)}{ω_{j}(z)})} ∑_{j=1}^{d} \frac{P_{j} (\frac{ω_{1}(z)···ω_{d}(z)}{ω_{j}(z)})}{p_{j,1}} + (d − 1) ∏_{j=1}^{d} \frac{p_{j,1}}{P_{j} (\frac{ω_{1}(z)···ω_{d}(z)}{ω_{j}(z)})}.

This is substituted in (6.11), to obtain

N_{D_{n}}(T_{1}, T_{2}, …, T_{d})

= −2(n − 1) ⟨z^{c} ∏_{i=1}^{d} ∏_{k=0}^{n} p_{i,k+1}^{m_{k}^{(i)}}⟩ (∏_{j=1}^{d} \frac{p_{j,1}}{P_{j} (\frac{ω_{1}(z)···ω_{d}(z)}{ω_{j}(z)})}) ∑_{j=1}^{d} \frac{P_{j} (\frac{ω_{1}(z)···ω_{d}(z)}{ω_{j}(z)})}{p_{j,1}}

+ 2(n − 1)(d − 1) ⟨z^{c} ∏_{i=1}^{d} ∏_{k=0}^{n} p_{i,k+1}^{m_{k}^{(i)}}⟩ ∏_{j=1}^{d} \frac{p_{j,1}}{P_{j} (\frac{ω_{1}(z)···ω_{d}(z)}{ω_{j}(z)})}. (6.16)

Now the problem is set up for application of the Lagrange–Good inversion formula. Let f_{i}(z) = z_{i}/P_{i}(z_{1} ⋯ z_{d}/z_{i}), i = 1, 2, …, d. If we substitute f_{i}(z) in place of z_{i}, i = 1, 2, …, d, in (6.16), and apply Theorem 1 with

g(z) = (∏_{j=1}^{d} \frac{p_{j,1}}{P_{j} (\frac{z_{1}···z_{d}}{z_{j}} )}) ∑_{j=1}^{d} \frac{P_{j} (\frac{z_{1}···z_{d}}{z_{j}} )}{p_{j,1}},

respectively

g(z) = ∏_{j=1}^{d} \frac{p_{j,1}}{P_{j} (\frac{z_{1}···z_{d}}{z_{j}} )},

we obtain that

N_{D_{n}}(T_{1}, T_{2}, …, T_{d})

= −2(n − 1) ⟨z^{0} ∏_{i=1}^{d} ∏_{k=0}^{n} p_{i,k+1}^{m_{k}^{(i)}}⟩ (∏_{i=1}^{d} p_{i,1}) (∑_{j=1}^{d} \frac{z_{j}}{f_{j}(z)p_{j,1}} ) f^{−c}(z) det_{1≤i,k≤d} (\frac{∂f_{i}}{∂z_{k}} (z))

+ 2(n − 1)(d − 1) ⟨z^{0} ∏_{i=1}^{d} ∏_{k=0}^{n} p_{i,k+1}^{m_{k}^{(i)}}⟩ (∏_{i=1}^{d} p_{i,1}) f^{−c}(z) det_{1≤i,k≤d} (\frac{∂f_{i}}{∂z_{k}} (z)) , (6.17)

where 0 stands for the vector (0, 0, …, 0). We treat the two terms on the right-hand side of (6.17) separately. We begin with the second term:

⟨z^{0} ∏_{i=1}^{d} ∏_{k=0}^{n} p_{i,k+1}^{m_{k}^{(i)}}⟩ (∏_{i=1}^{d} p_{i,1}) f^{−c}(z) det_{1≤i,k≤d} (\frac{∂f_{i}}{∂z_{k}} (z))

= ⟨z^{c} ∏_{i=1}^{d} ∏_{k=0}^{n} p_{i,k+1}^{m_{k}^{(i)}}⟩ (∏_{i=1}^{d} p_{i,1}) det_{1≤i,k≤d} (\begin{cases}P_{i}^{c_{i}−1} (\frac{z_{1} ⋯ z_{d}}{z_{i}} ) , & i = k \\ −P_{i}^{c_{i}−2} (\frac{z_{1} ⋯ z_{d}}{z_{i}} ) \\ ×P′_{i} (\frac{z_{1} ⋯ z_{d}}{z_{i}} ) \frac{z_{1} ⋯ z_{d}}{z_{k}} , & i ≠ k \end{cases}\})

= ⟨z^{c} ∏_{i=1}^{d} ∏_{k=0}^{n} p_{i,k+1}^{m_{k}^{(i)}}⟩ (∏_{i=1}^{d} p_{i,1})

× det_{1≤i,k≤d} (\begin{cases}P_{i}^{c_{i}−1} (\frac{z_{1} ⋯ z_{d}}{z_{i}} ) , & i = k \\ −\frac{1}{c_{i} − 1} (u\frac{d}{du}P_{i}^{c_{i}−1} (u)) |_{u=z_{1}···z_{d}/z_{i}}, & i ≠ k \end{cases}\}) .

Reading coefficients, we obtain

∏_{i=1}^{d} \binom{c_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}} det_{1≤i,k≤d} (\begin{cases}1, & i = k \\ −\frac{rk T_{i}}{c_{i} − 1}, & i ≠ k \end{cases}\})

= ∏_{i=1}^{d} \binom{c_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}} det_{1≤i,k≤d} (1 − χ(i ≠ k)\frac{n − 1}{c_{i} − 1}) ,

the second line being due to (6.12). Now we can apply Lemma 2 with X_{i} = c_{i} − 1 and Y_{i} = n − 1, i = 1, 2, …, d. The term

∑_{i=1}^{d} X_{i} − ∑_{i=2}^{d} Y_{i} = ∑_{i=1}^{d}(c_{i} − 1) − (d − 1)(n − 1)

= ∑_{i=1}^{d}(n − rk T_{i} − 1) − (d − 1)(n − 1)

on the right-hand side of (3.2) simplifies to −1 due to our assumption concerning the sum of the ranks of the types T_{i}. Hence, if we use the relation (6.12) once more, the second term on the right-hand side of (6.17) is seen to equal

−2(d − 1)(n − 1)^{d} ∏_{i=1}^{d} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}.

This explains the second term in the factor in big parentheses in (6.2) and the fourth term in the factor in big parentheses on the right-hand side of (6.3).

Finally, we come to the first term on the right-hand side of (6.17). We have

⟨z^{0} ∏_{i=1}^{d} ∏_{k=0}^{n} p_{i,k+1}^{m_{k}^{(i)}}⟩ (∏_{i=1}^{d} p_{i,1}) \frac{z_{j}}{f_{j}(z)p_{j,1}} f^{−c}(z) det_{1≤i,k≤d} (\frac{∂f_{i}}{∂z_{k}} (z))

= ⟨z^{c} ∏_{i=1}^{d} ∏_{k=0}^{n} p_{i,k+1}^{m_{k}^{(i)}}⟩ (_{∏_{i=1}^{d} ; i≠j}p_{i,1}) det_{1≤i,k≤d} (\begin{cases}P_{i}^{c_{i}−1+χ(i=j)} (\frac{z_{1} ⋯ z_{d}}{z_{i}} ) , & i = k \\ −P_{i}^{c_{i}−2+χ(i=j)} (\frac{z_{1} ⋯ z_{d}}{z_{i}} ) \\ ×P′_{i} (\frac{z_{1} ⋯ z_{d}}{z_{i}} ) \frac{z_{1} ⋯ z_{d}}{z_{k}} , & i ≠ k \end{cases}\})

= ⟨z^{c} ∏_{i=1}^{d} ∏_{k=0}^{n} p_{i,k+1}^{m_{k}^{(i)}}⟩ (_{∏_{i=1}^{d} ; i≠j}p_{i,1})

× det_{1≤i,k≤d} (\begin{cases}P_{i}^{c_{i}−1+χ(i=j)} (\frac{z_{1} ⋯ z_{d}}{z_{i}} ) , & i = k \\ −\frac{1}{c_{i} − 1 + χ(i = j)} (u\frac{d}{du}P_{i}^{c_{i}−1+χ(i=j)} (u)) |_{u=z_{1}···z_{d}/z_{i}}, & i ≠ k \end{cases}\}) .

Reading coefficients, we obtain

∏_{i=1}^{d} \binom{c_{i} − 1 + χ(i = j)}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}} det_{1≤i,k≤d} (\begin{cases}1, & i = k \\ −\frac{rk T_{i}}{c_{i} − 1 + χ(i = j)}, & i ≠ k \end{cases}\})

= ∏_{i=1}^{d} \binom{c_{i} − 1 + χ(i = j)}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}} det_{1≤i,k≤d} (\begin{cases}1 − χ(j ≠ k)\frac{n}{c_{j}} , & i = j \\ 1 − χ(i ≠ k)\frac{n−1}{c_{i}−1}, & i ≠ j \end{cases}\}) ,

the second line being due to (6.12). Now we can apply Corollary 3 with r = j, X_{i} = c_{i} − 1, i = 1, …, j − 1, j + 1, …, d, X_{j} = c_{j}, Y = n − 1, and Z = n. The term

Z ∑_{i=1}^{d} X_{i} + (Y − Z)X_{j} − (d − 1)Y Z = n (1 + ∑_{i=1}^{d}(c_{i} − 1)) − c_{j} − (d − 1)(n − 1)n

= n ∑_{i=1}^{d}(n − rk T_{i} − 1) + n − c_{j} − (d − 1)(n − 1)n

on the right-hand side of (3.2) simplifies to −c_{j} due to our assumption concerning the sum of the ranks of the types T_{i}. Hence, if we use the relation (6.12) once more, the second term on the right-hand side of (6.17) is seen to equal the sum over j = 1, 2, …, d of

2(n − 1)^{d−1}\binom{n − rk T_{j}}{m_{1}^{(j)}, m_{2}^{(j)}, …, m_{n}^{(j)}}_{∏_{i=1}^{d} ; i≠j} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}.

This explains the first terms in the factors in big parentheses on the right-hand sides of (6.2) and (6.3).

The proof of the theorem is complete. □

Combining the previous theorem with the summation formula of Lemma 4, we can now derive compact formulae for all type D_{n} decomposition numbers.

Theorem 10. (i) Let the types T_{1}, T_{2}, …, T_{d} be given, where

T_{i} = A_{1}^{m_{1}^{(i)}} ∗ A_{2}^{m_{2}^{(i)}} ∗ ⋯ ∗ A_{n}^{m_{n}^{(i)}}, i = 1, 2, …, j − 1, j + 1, …, d,

and

T_{j} = D_{α} ∗ A_{1}^{m_{1}^{(j)}} ∗ A_{2}^{m_{2}^{(j)}} ∗ ⋯ ∗ A_{n}^{m_{n}^{(j)}},

for some α ≥ 2. Then

N_{D_{n}}^{comb}(T_{1}, T_{2}, …, T_{d}) = (n − 1)^{d−1}\binom{n − 1}{rk T_{1} + rk T_{2} + ⋯ + rk T_{d} − 1}

× \binom{n − rk T_{j}}{m_{1}^{(j)}, m_{2}^{(j)}, …, m_{n}^{(j)}}_{∏_{i=1}^{d} ; i≠j} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}, (6.18)

where the multinomial coefficient is defined as in Lemma 4. For α ≥ 4, the number N_{D_{n}}(T_{1}, T_{2}, …, T_{d}) is given by the same formula.

(ii) Let the types T_{1}, T_{2}, …, T_{d} be given, where

T_{i} = A_{1}^{m_{1}^{(i)}} ∗ A_{2}^{m_{2}^{(i)}} ∗ ⋯ ∗ A_{n}^{m_{n}^{(i)}}, i = 1, 2, …, d.

Then

N_{D_{n}}^{comb}(T_{1}, T_{2}, …, T_{d}) = (n − 1)^{d−1}\binom{n − 1}{rk T_{1} + rk T_{2} + ⋯ + rk T_{d} − 1}

× (2 ∑_{j=1}^{d} \binom{n − rk T_{j}}{m_{1}^{(j)}, m_{2}^{(j)}, …, m_{n}^{(j)}}(_{∏_{i=1}^{d} ; i≠j} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}})

+ (\frac{(n − ∑_{ℓ=1}^{d} rk T_{ℓ}) (n − 1 − ∑_{ℓ=1}^{d} rk T_{ℓ})}{∑_{ℓ=1}^{d} rk T_{ℓ}} − 2(d − 2)(n − 1))

·∏_{i=1}^{d} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}) , (6.19)

whereas

N_{D_{n}}(T_{1}, T_{2}, …, T_{d}) = (n − 1)^{d−1}\binom{n − 1}{rk T_{1} + rk T_{2} + ⋯ + rk T_{d} − 1}

× (∑_{j=1}^{d} (_{∏_{i=1}^{d} ; i≠j} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}})(2\binom{n − rk T_{j}}{m_{1}^{(j)}, m_{2}^{(j)}, …, m_{n}^{(j)}}

+ \binom{n − rk T_{j}}{m_{1}^{(j)}, m_{2}^{(j)}, m_{3}^{(j)} − 1, m_{4}^{(j)}, …, m_{n}^{(j)}} + \binom{n − rk T_{j}}{m_{1}^{(j)} − 2, m_{2}^{(j)}, …, m_{n}^{(j)}})

+ (\frac{(n − ∑_{ℓ=1}^{d} rk T_{ℓ}) (n − 1 − ∑_{ℓ=1}^{d} rk T_{ℓ})}{∑_{ℓ=1}^{d} rk T_{ℓ}} − 2(d − 2)(n − 1))

·∏_{i=1}^{d} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}) . (6.20)

(iii) All other decomposition numbers N_{D_{n}}(T_{1}, T_{2}, …, T_{d}) and N_{D_{n}}^{comb}(T_{1}, T_{2}, …, T_{d}) are zero.

Remark. The caveats on interpretations of the formulae in Theorem 9 for critical choices of the parameters (cf. the Remark after the statement of that theorem) apply also to the formulae of Theorem 10.

Proof. We proceed in a manner similar to the proof of Theorem 8. If we write r for n − rk T_{1} − rk T_{2} − ⋯ − rk T_{d} and set Φ = D_{n}, then the relation (2.3) becomes

N_{D_{n}}(T_{1}, T_{2}, …, T_{d}) = ∑_{T:rk T =r}N_{D_{n}}(T_{1}, T_{2}, …, T_{d}, T),  (6.21)

with the same relation holding for N_{D_{n}}^{comb} in place of N_{D_{n}}.

In order to prove (6.18), we let T = A_{1}^{m_{1}} ∗ A_{2}^{m_{2}} ∗ ⋯ ∗ A_{n}^{m_{n}} and use (6.1) in (6.21), to obtain

N_{D_{n}}^{comb}(T_{1}, T_{2}, …, T_{d}) = ∑_{m_{1}+2m_{2}+···+nm_{n}=r}(n − 1)^{d} \frac{1}{n − r − 1}\binom{n − r − 1}{m_{1}, m_{2}, …, m_{n}}

· \binom{n − rk T_{j}}{m_{1}^{(j)}, m_{2}^{(j)}, …, m_{n}^{(j)}}_{∏_{i=1}^{d} ; i≠j} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}.

If we use (3.4) with M = n − r − 1, we arrive at our claim after little simplification.

Next we prove (6.19). In contrast to the previous argument, here the summation on the right-hand side of (6.21) must be taken over all types T of the form T = D_{α} ∗ A_{1}^{m_{1}} ∗ A_{2}^{m_{2}} ∗ ⋯ ∗ A_{n}^{m_{n}}, α ≥ 2, as well as of the form T = A_{1}^{m_{1}} ∗ A_{2}^{m_{2}} ∗ ⋯ ∗ A_{n}^{m_{n}}. For the sum over the former types, we have to substitute (6.1) in (6.21), to get

∑_{α=2}^{n} ∑_{m_{1}+2m_{2}+···+nm_{n}=r−α}(n − 1)^{d}\binom{n − r}{m_{1}, m_{2}, …, m_{n}}

· ∏_{i=1}^{d} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}. (6.22)

On the other hand, for the sum over the latter types, we have to substitute (6.2) in (6.21), to get

2 ∑_{m_{1}+2m_{2}+···+nm_{n}=r}(n − 1)^{d}\binom{n − r}{m_{1}, m_{2}, …, m_{n}}∏_{i=1}^{d} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}

+ ∑_{m_{1}+2m_{2}+···+nm_{n}=r}(n − 1)^{d} \frac{1}{n − r − 1}\binom{n − r − 1}{m_{1}, m_{2}, …, m_{n}}

· (2 ∑_{j=1}^{d} \binom{n − rk T_{j}}{m_{1}^{(j)}, m_{2}^{(j)}, …, m_{n}^{(j)}}_{∏_{i=1}^{d} ; i≠j} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}

−2(d − 1)(n − 1)∏_{i=1}^{d} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}) . (6.23)

We simplify (6.22) by using (3.4) with r replaced by r − α and M = n − r, and by subsequently applying the elementary summation formula

∑_{α=2}^{n} \binom{n − α − 1}{r − α} = ∑_{α=2}^{n} \binom{n − α − 1}{n − r − 1} = \binom{n − 2}{n − r} = \binom{n − 2}{r − 2}.  (6.24)

The expression which we obtain in this way explains the fraction in the third line of (6.19) multiplied by the expression in the last line. On the other hand, we simplify the sums in (6.23) by using (3.4) with M = n − r, respectively M = n − r − 1. Thus, the expression (6.23) becomes

2(n − 1)^{d}\binom{n − 1}{r}∏_{i=1}^{d} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}

+(n−1)^{d−1}\binom{n − 1}{r}(2 ∑_{j=1}^{d} \binom{n − rk T_{j}}{m_{1}^{(j)}, m_{2}^{(j)}, …, m_{n}^{(j)}}_{∏_{i=1}^{d} ; i≠j} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}

− 2(d − 1)(n − 1)∏_{i=1}^{d} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}}),

which explains the expression in the second line of (6.19) and the second expression in the third line of (6.19) multiplied by the expression in the last line.

The proof of (6.20) is analogous, using (6.3) instead of (6.2). We leave the details to the reader. □

7. Generalised non-crossing partitions

In this section we recall the definition of Armstrong’s [1] generalised non-crossing partitions poset, and its combinatorial realisation from [1] and [29] for the types A_{n}, B_{n}, and D_{n}.

Let again Φ be a finite root system of rank n, and let W = W (Φ) be the corresponding reflection group. We define first the non-crossing partition lattice NC(Φ) (cf. [8, 15]). Let c be a Coxeter element in W. Then NC(Φ) is defined to be the restriction of the partial order ≤_{T} from Section 2 to the set of all elements which are less than or equal to c in this partial order. This definition makes sense since any two Coxeter elements in W are conjugate to each other; the induced inner automorphism then restricts to an isomorphism of the posets corresponding to the two Coxeter elements. It can be shown that NC(Φ) is in fact a lattice (see [16] for a uniform proof), and moreover self-dual (this is obvious from the definition). Clearly, the minimal element in NC(Φ) is the identity element in W, which we denote by ε, and the maximal element in NC(Φ) is the chosen Coxeter element c. The term “non-crossing partition lattice” is used because NC(A_{n}) is isomorphic to the lattice of non-crossing partitions of {1, 2, …, n + 1}, originally introduced by Kreweras [30] (see also [20] and below), and since also NC(B_{n}) and NC(D_{n}) can be realised as lattices of non-crossing partitions (see [4, 32] and below).

In addition to a fixed root system, the definition of Armstrong’s generalised noncrossing partitions requires a fixed positive integer m. The poset of m-divisible noncrossing partitions associated to the root system Φ has as ground-set the following subset of (NC(Φ))^{m+1}:

NC^{m}(Φ) = {(w_{0}; w_{1}, …, w_{m}) : w_{0}w_{1} ⋯ w_{m} = c and

ℓ_{T} (w_{0}) + ℓ_{T} (w_{1}) + ⋯ + ℓ_{T} (w_{m}) = ℓ_{T} (c)}. (7.1)

The order relation is defined by

(u_{0}; u_{1}, …, u_{m}) ≤ (w_{0}; w_{1}, …, w_{m}) if and only if u_{i} ≥_{T} w_{i}, 1 ≤ i ≤ m.

(According to this definition, u_{0} and w_{0} need not be related in any way. However, it follows from [1, Lemma 3.4.7] that, in fact, u_{0} ≤_{T} w_{0}.) The poset NC^{m}(Φ) is graded by the rank function

rk ((w_{0}; w_{1}, …, w_{m})) = ℓ_{T} (w_{0}).  (7.2)

Thus, there is a unique maximal element, namely (c; ε, …, ε), where ε stands for the identity element in W, but, for m > 1, there are many different minimal elements. In particular, NC^{m}(Φ) has no least element if m > 1; hence, NC^{m}(Φ) is not a lattice for m > 1. (It is, however, a graded join-semilattice, see [1, Theorem 3.4.4].)

In what follows, we shall use the notions “generalised non-crossing partitions” and “m-divisible non-crossing partitions” interchangeably, where the latter notion will be employed particularly in contexts in which we want to underline the presence of the parameter m.

In the remainder of this section, we explain combinatorial realisations of the mdivisible non-crossing partitions of types A_{n−1}, B_{n}, and D_{n}. In order to be able to do so, we need to recall the definition of Kreweras’ non-crossing partitions of {1, 2, …, N}, his “partitions non croisées d’un cycle” of [30]. We place N vertices around a cycle, and label them 1, 2, …, N in clockwise order. The circular representation of a partition of the set {1, 2, …, N} is the geometric object which arises by representing each block {i_{1}, i_{2}, …, i_{k}} of the partition, where i_{1} < i_{2} < ⋯ < i_{k}, by the polygon consisting of the vertices labelled i_{1}, i_{2}, …, i_{k} and edges which connect these vertices in clockwise order. A partition of {1, 2, …, N} is called non-crossing if any two edges in its circular representation are disjoint. Figure 7 shows the non-crossing partition

{{1, 2, 21}, {3, 19, 20}, {4, 5, 6}, {7, 17, 18}, {8, 9, 10, 11, 12, 13, 14, 15, 16}}

of {1, 2, …, 21}. There is a natural partial order on Kreweras’ non-crossing partitions defined by refinement: a partition π_{1} is less than or equal to the partition π_{2} if every block of π_{1} is contained in some block of π_{2}.

If Φ = A_{n−1}, the m-divisible non-crossing partitions are in bijection with Krewerastype non-crossing partitions of the set {1, 2, …, mn}, in which all the block sizes are divisible by m. We denote the latter set of non-crossing partitions by ÑC^{m}(A_{n−1}). It has been first considered by Edelman in [18]. In fact, Figure 7 shows an example of a 3-divisible non-crossing partition of type A_{20}.

Given an element (w_{0}; w_{1}, …, w_{m}) ∈ NC^{m}(A_{n−1}), the bijection, ▽_{A_{n−1}}^{m} say, from [1, Theorem 4.3.8] works by “blowing up” w_{1}, w_{2}, …, w_{m}, thereby “interleaving” them, and then “gluing” them together by an operation which is called Kreweras complement in [1]. More precisely, for i = 1, 2, …, m, let τ_{m,i} be the transformation which maps a permutation w ∈ S_{n} to a permutation τ_{m,i}(w) ∈ S_{mn} by letting

(τ_{m,i}(w))(mk + i − m) = mw(k) + i − m, k = 1, 2, …, n,

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

Figure 7. Combinatorial realisation of a 3-divisible non-crossing partition of type A_{6}

and (τ_{m,i}(w))(l) = l for all l ≢ i (mod m). At this point, the reader should recall from Section 2 that W (A_{n−1}) is the symmetric group S_{n}, and that the standard choice of a Coxeter element in W (A_{n−1}) = S_{n} is c = (1, 2, …, n). With this choice of Coxeter element, the announced bijection maps (w_{0}; w_{1}, …, w_{m}) ∈ NC^{m}(A_{n−1}) to

▽_{A_{n−1}}^{m}(w_{0}; w_{1}, …, w_{m}) = (1, 2, …, mn) (τ_{m,1}(w_{1}))^{−1} (τ_{m,2}(w_{2}))^{−1} ⋯ (τ_{m,m}(w_{m}))^{−1}.

We refer the reader to [1, Sec. 4.3.2] for the details. For example, let n = 7, m = 3, w_{0} = (4, 5, 6), w_{1} = (3, 6), w_{2} = (1, 7), and w_{3} = (1, 2, 6). Then (w_{0}; w_{1}, w_{2}, w_{3}) is mapped to

▽_{A_{6}}^{3}(w_{0}; w_{1}, w_{2}, w_{3}) = (1, 2, …, 21) (7, 16) (2, 20) (18, 6, 3)
= (1, 2, 21) (3, 19, 20) (4, 5, 6) (7, 17, 18) (8, 9, …, 16).  (7.3)

Figure 7 shows the graphical representation of (7.3) on the circle, in which we represent a cycle (i_{1}, i_{2}, …, i_{k}) as a polygon consisting of the vertices labelled i_{1}, i_{2}, …, i_{k} and edges which connect these vertices in clockwise order.

It is shown in [1, Theorem 4.3.8] that ▽_{A_{n−1}}^{m} is in fact an isomorphism between the posets NC^{m}(A_{n−1}) and ÑC^{m}(A_{n−1}). Furthermore, it is proved in [1, Theorem 4.3.13]

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

Figure 8. Combinatorial realisation of a 3-divisible non-crossing partition of type B_{5}

that

c_{i}(w_{0}) = b_{i}(▽_{A_{n−1}}^{m}(w_{0}; w_{1}, …, w_{m})), i = 1, 2, …, n,  (7.4)

where c_{i}(w_{0}) denotes the number of cycles of length i of w_{0} and b_{i}(π) denotes the number of blocks of size mi in the non-crossing partition π.

If Φ = B_{n}, the m-divisible non-crossing partitions are in bijection with Kreweras-type non-crossing partitions π of the set \{1, 2, …, mn, ¯1, ¯2, …, \overline{mn}\}, in which all the block sizes are divisible by m, and which have the property that if B is a block of π then also \overline{B} := \{x̄ : x ∈ B\} is a block of π. (Here, as earlier, we adopt the convention that ¯ x̄ = x for all x.) We denote the latter set of non-crossing partitions by ÑC^{m}(B_{n}). A block B with \overline{B} = B is called a zero block. A non-crossing partition in ÑC^{m}(B_{n}) can only have at most one zero block. Figures 8 and 9 give examples of 3-divisible non-crossing partitions of type B_{5}. Figure 8 shows one without a zero block, while Figure 9 shows one with a zero block. Clearly, the condition that B is a block of the partition if and only if \overline{B} is a block translates into the condition that the geometric realisation of the partition is invariant under rotation by 180^{∘}.

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

Figure 9. A 3-divisible non-crossing partition of type B_{5} with zero block

Given an element (w_{0}; w_{1}, …, w_{m}) ∈ NC^{m}(B_{n}), the bijection, ▽_{B_{n}}^{m} say, from [1, Theorem 4.5.6] works in the same way as for NC^{m}(A_{n−1}). That is, recalling from Section 2 that W (B_{n}) can be combinatorially realised as a subgroup of the group of permutations of {1, 2, …, n, ¯1, ¯2, …, n̄}, and that, in this realisation, the standard choice of a Coxeter element is c = [1, 2, …, n] = (1, 2, …, n, ¯1, ¯2, …, n̄), the announced bijection maps (w_{0}; w_{1}, …, w_{m}) ∈ NC^{m}(B_{n}) to

▽_{B_{n}}^{m}(w_{0}; w_{1}, …, w_{m}) = [1, 2, …, mn] (τ̄_{m,1}(w_{1}))^{−1} (τ̄_{m,2}(w_{2}))^{−1} ⋯ (τ̄_{m,m}(w_{m}))^{−1},

where τ̄_{m,i} is the obvious extension of the above transformations τ_{m,i}: namely we let

(τ̄_{m,i}(w))(mk + i − m) = mw(k) + i − m, k = 1, 2, …, n, ¯1, ¯2, …, n̄,

and (τ̄_{m,i}(w))(l) = l and (τ̄_{m,i}(w))(l̄) = l̄ for all l ≢ i (mod m), where mk̄ + i − m is identified with \overline{mk + i − m} for all k and i. We refer the reader to [1, Sec. 4.5] for the details. For example, let n = 5, m = 3, w_{0} = ((2, 4)), w_{1} = [1] = (1, ¯1), w_{2} = ((1, 4)), and w_{3} = ((2, 3)) ((4, 5)). Then (w_{0}; w_{1}, w_{2}, w_{3}) is mapped to

▽_{B_{5}}^{3}(w_{0}; w_{1}, w_{2}, w_{3}) = [1, 2, …, 15] [1] ((2, 11)) ((6, 9)) ((12, 15))
= ((1, ¯2, \overline{12})) ((3, 4, 5, 6, 10, 11)) ((7, 8, 9)) ((13, 14, 15)). (7.5)

Figure 8 shows the graphical representation of (7.5).

It is shown in [1, Theorem 4.5.6] that ▽_{B_{n}}^{m} is in fact an isomorphism between the posets NC^{m}(B_{n}) and ÑC^{m}(B_{n}). Furthermore, it is proved in [1, proof of Theorem 4.3.13] that

c_{i}(w_{0}) = b_{i}(▽_{B_{n}}^{m}(w_{0}; w_{1}, …, w_{m})), i = 1, 2, …, n,  (7.6)

where c_{i}(w_{0}) denotes the number of type A cycles (recall the corresponding terminology from Section 4) of length i of w_{0} and b_{i}(π) denotes one half of the number of non-zero blocks of size mi in the non-crossing partition π. (Recall that non-zero blocks come in “symmetric” pairs.) Consequently, under the bijection ▽_{B_{n}}^{m}, the element w_{0} contains a type B cycle of length ℓ if and only if ▽_{B_{n}}^{m}(w_{0}; w_{1}, …, w_{m}) contains a zero block of size mℓ.

The m-divisible non-crossing partitions of type D_{n} cannot be realised as certain “partitions non croisées d’un cycle,” but as non-crossing partitions on an annulus with 2m(n − 1) vertices on the outer cycle and 2m vertices on the inner cycle, the vertices on the outer cycle being labelled by 1, 2, …, mn − m, ¯1, ¯2, …, \overline{mn − m} in clockwise order, and the vertices of the inner cycle being labelled by mn − m + 1, …, mn − 1, mn, \overline{mn − m + 1}, …, \overline{mn − 1}, \overline{mn} in counter-clockwise order. Given a partition π of \{1, 2, …, mn, ¯1, ¯2, …, \overline{mn}\}, we represent it on this annulus in a manner analogous to Kreweras’ graphical representation of his partitions; namely, we represent each block of π by connecting the vertices labelled by the elements of the block by curves in clockwise order, the important additional requirement being here that the curves must be drawn in the interior of the annulus. If it is possible to draw the curves in such a way that no two curves intersect, then the partition is called a non-crossing partition on the (2m(n − 1), 2m)-annulus. Figure 10 shows a non-crossing partition on the (15, 6)- annulus.

With this definition, the m-divisible non-crossing partitions of type D_{n} are in bijection with non-crossing partitions π on the (2m(n − 1), 2m)-annulus, in which successive elements of a block (successive in the circular order in the graphical representation of the block) are in successive congruence classes modulo m, which have the property that if B is a block of π then also \overline{B} := \{x̄ : x ∈ B\} is a block of π, and which satisfy an additional restriction concerning their zero block. Here again, a zero block is a block B with \overline{B} = B. The announced additional restriction says that a zero block can only occur if it contains all the vertices of the inner cycle, that is, mn − m + 1, …, mn − 1, mn, \overline{mn − m + 1}, …, \overline{mn − 1}, \overline{mn}, and at least two further elements from the outer cycle. We denote this set of non-crossing partitions on the (2m(n − 1), 2m)-annulus by ÑC^{m}(D_{n}). A non-crossing partition in ÑC^{m}(D_{n}) can only have at most one zero block. Figures 10 and 11 give examples of 3-divisible non-crossing partitions of type D_{6}, Figure 10 one without a zero block, while Figure 11 one with a zero block. Again, it is clear that the condition that B is a block of the partition if and only if \overline{B} is a block translates into the condition that the geometric realisation of the partition is invariant under rotation by 180^{∘}.

In order to clearly sort out the differences to the earlier combinatorial realisations of m-divisible non-crossing partitions of types A_{n−1} and B_{n}, we stress that for type D_{n} there are three major features which are not present for the former types: (1) here we consider non-crossing partitions on an annulus; (2) it is not sufficient to impose the

1  2  3  4 5 6 78 9 10 11 12 13 14 15 \overline{1} \overline{2} \overline{3} \overline{4} \overline{5} \overline{6} \overline{7} \overline{8}\overline{9}\overline{10} \overline{11} \overline{12} \overline{13}  \overline{14} \overline{15}  \overline{16} \overline{17} \overline{18} 16 17  18

Figure 10. Combinatorial realisation of a 3-divisible non-crossing partition of type D_{6}

condition that the size of every block is divisible by m: the condition on successive elements of a block is stronger; (3) there is the above additional restriction on the zero block (which is not present in type B_{n}).

Given an element (w_{0}; w_{1}, …, w_{m}) ∈ NC^{m}(D_{n}), the bijection, ▽_{D_{n}}^{m} say, from [29] works as follows. Recalling from Section 2 that W (D_{n}) can be combinatorially realised as a subgroup of the group of permutations of {1, 2, …, n, ¯1, ¯2, …, n̄}, and that, in this realisation, the standard choice of a Coxeter element is c = [1, 2, …, n − 1] [n] = (1, 2, …, n − 1, ¯1, ¯2, …, \overline{n − 1}) (n, n̄), the announced bijection maps (w_{0}; w_{1}, …, w_{m}) ∈ NC^{m}(D_{n}) to

▽_{D_{n}}^{m} (w_{0}; w_{1}, …, w_{m}) = [1, 2, …, m(n − 1)] [mn − m + 1, …, mn − 1, mn]

∘ (τ̄_{m,1}(w_{1}))^{−1} (τ̄_{m,2}(w_{2}))^{−1} ⋯ (τ̄_{m,m}(w_{m}))^{−1},

where τ̄_{m,i} is defined as above. We refer the reader to [29] for the details. For example, let n = 6, m = 3, w_{0} = ((2, ¯4)), w_{1} = ((2, ¯6)) ((4, 5)), w_{2} = ((1, ¯5)) ((2, 3)), and

1  2  3  4 5 6 78 9 10 11 12 13 14 15 \overline{1} \overline{2} \overline{3} \overline{4} \overline{5} \overline{6} \overline{7} \overline{8}\overline{9}\overline{10} \overline{11} \overline{12} \overline{13}  \overline{14} \overline{15}  \overline{16} \overline{17} \overline{18} 16 17  18

Figure 11. A 3-divisible non-crossing partition of type D_{6} with zero block

w_{3} = ((3, 6)). Then (w_{0}; w_{1}, w_{2}, w_{3}) is mapped to

▽_{D_{6}}^{3}(w_{0};w_{1}, w_{2}, w_{3})
= [1, 2, …, 15] [16, 17, 18]((4, \overline{16})) ((10, 13)) ((2, \overline{14})) ((5, 8)) ((9, 18))
= ((1, 2, \overline{15})) ((3, 4, \overline{17}, \overline{18}, \overline{10}, \overline{14})) ((5, 9, \overline{16})) ((6, 7, 8)) ((11, 12, 13)). (7.7)

Figure 10 shows the graphical representation of (7.7).

It is shown in [29] that ▽_{D_{n}}^{m} is in fact an isomorphism between the posets NC^{m}(D_{n}) and ÑC^{m}(D_{n}). Furthermore, it is proved in [29] that

c_{i}(w_{0}) = b_{i}(▽_{D_{n}}^{m}(w_{0}; w_{1}, …, w_{m})), i = 1, 2, …, n,  (7.8)

where c_{i}(w_{0}) denotes the number of type A cycles of length i of w_{0} and b_{i}(π) denotes one half of the number of non-zero blocks of size mi in the non-crossing partition π. (Recall that non-zero blocks come in “symmetric” pairs.) Consequently, under the bijection ▽_{D_{n}}^{m}, the element w_{0} contains a type D cycle of length ℓ if and only if ▽_{D_{n}}^{m}(w_{0}; w_{1}, …, w_{m}) contains a zero block of size mℓ.

8. Decomposition numbers with free factors, and enumeration in the poset of generalised non-crossing partitions

This section is devoted to applying our formulae from Sections 4–6 for the decomposition numbers of the types A_{n}, B_{n}, and D_{n} to the enumerative theory of generalised non-crossing partitions for these types. Theorems 11–15 present formulae for the number of minimal factorisations of Coxeter elements in types A_{n}, B_{n}, and D_{n}, respectively, where we do not prescribe the types of all the factors as for the decomposition numbers, but just for some of them, while we impose rank sum conditions on other factors. Immediate corollaries are formulae for the number of multi-chains π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{l−1}, l being given, in the posets ÑC^{m}(A_{n−1}), ÑC^{m}(B_{n}), and ÑC^{m}(D_{n}), where the poset rank of π_{i} equals r_{i}, and where the block structure of π_{1} is prescribed, see Corollaries 12, 14, and 16. These results in turn imply all known enumerative results on ordinary and generalised non-crossing partitions via appropriate summations, see the remarks accompanying the corollaries. They also imply two further new results on chain enumeration in ÑC^{m}(D_{n}), see Corollaries 18 and 19. We want to stress that, since ÑC^{m}(Φ) and NC^{m}(Φ) are isomorphic as posets for Φ = A_{n−1}, B_{n}, D_{n}, Corollaries 12, 14, 16, 17, 18 imply obvious results for NC^{m}(Φ) in place of ÑC^{m}(Φ), Φ = A_{n−1}, B_{n}, D_{n}, via (7.4), (7.6), respectively (7.8).

We begin with our results for type A_{n}. The next theorem generalises Theorem 6, which can be obtained from the former as the special case in which l = 1 and m_{1} = 1.

Theorem 11. For a positive integer d, let the types T_{1}, T_{2}, …, T_{d} be given, where

T_{i} = A_{1}^{m_{1}^{(i)}} ∗ A_{2}^{m_{2}^{(i)}} ∗ ⋯ ∗ A_{n}^{m_{n}^{(i)}}, i = 1, 2, …, d,

and let l, m_{1}, m_{2}, …, m_{l}, s_{1}, s_{2}, …, s_{l} be given non-negative integers with

rk T_{1} + rk T_{2} + ⋯ + rk T_{d} + s_{1} + s_{2} + ⋯ + s_{l} = n.

Then the number of factorisations

c = σ_{1}σ_{2} ⋯ σ_{d}σ_{1}^{(1)}σ_{2}^{(1)} ⋯ σ_{m_{1}}^{(1)}σ_{1}^{(2)}σ_{2}^{(2)} ⋯ σ_{m_{2}}^{(2)} ⋯ σ_{1}^{(l)}σ_{2}^{(l)} ⋯ σ_{m_{l}}^{(l)},  (8.1)

where c is a Coxeter element in W (A_{n}), such that the type of σ_{i} is T_{i}, i = 1, 2, …, d, and such that

ℓ_{T} (σ_{1}^{(i)}) + ℓ_{T} (σ_{2}^{(i)}) + ⋯ + ℓ_{T} (σ_{m_{i}}^{(i)}) = s_{i}, i = 1, 2, …, l,  (8.2)

is given by

(n + 1)^{d−1}( ∏_{i=1}^{d} \frac{1}{n − rk T_{i} + 1}\binom{n − rk T_{i} + 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}})

× \binom{m_{1}(n + 1)}{s_{1}}\binom{m_{2}(n + 1)}{s_{2}} ⋯ \binom{m_{l}(n + 1)}{s_{l}}, (8.3)

where the multinomial coefficient is defined as in Lemma 4.

Proof. In the factorisation (8.1), we first fix also the types of the σ_{i}^{(j)}’s. For i = 1, 2, …, m_{j} and j = 1, 2, …, l, let the type of σ_{i}^{(j)} be

T_{i}^{(j)} = A_{1}^{m_{1}^{(i,j)}} ∗ A_{2}^{m_{2}^{(i,j)}} ∗ ⋯ ∗ A_{n}^{m_{n}^{(i,j)}}.

We know that the number of these factorisations is given by (4.1) with d replaced by d+m_{1}+m_{2}+⋯+m_{l} and the appropriate interpretations of the m_{i}^{(j)}’s. Next we fix nonnegative integers r_{i}^{(j)} and sum the expression (4.1) over all possible types T_{i}^{(j)} of rank r_{i}^{(j)}, i = 1, 2, …, m_{j}, j = 1, 2, …, l. The corresponding summations are completely analogous to the summation in the proof of Theorem 6. As a result, we obtain

(n + 1)^{d−1}( ∏_{i=1}^{d} \frac{1}{n − rk T_{i} + 1}\binom{n − rk T_{i} + 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}})

× \binom{n + 1}{r_{1}^{(1)}}\binom{n + 1}{r_{2}^{(1)}} ⋯ \binom{n + 1}{r_{m_{1}}^{(1)}} × \binom{n + 1}{r_{1}^{(2)}}\binom{n + 1}{r_{2}^{(2)}} ⋯ \binom{n + 1}{r_{m_{2}}^{(2)}}

× ⋯ × \binom{n + 1}{r_{1}^{(l)}}\binom{n + 1}{r_{2}^{(l)}} ⋯ \binom{n + 1}{r_{m_{l}}^{(l)}}

for the number of factorisations under consideration. In view of (8.2) and (2.4), to obtain the final result, we must sum these expressions over all non-negative integers r_{1}^{(1)}, …, r_{m_{l}}^{(l)} satisfying the equations

r_{1}^{(j)} + r_{2}^{(j)} + ⋯ + r_{m_{j}}^{(j)} = s_{j}, j = 1, 2, …, l.  (8.4)

This is easily done by means of the multivariate version of the Chu–Vandermonde summation. The formula in (8.3) follows. □

In view of the combinatorial realisation of m-divisible non-crossing partitions of type A_{n−1} which we described in Section 7, the special case d = 1 of the above theorem has the following enumerative consequence.

Corollary 12. Let l be a positive integer, and let s_{1}, s_{2}, …, s_{l} be non-negative integers with s_{1} + s_{2} + ⋯ + s_{l} = n − 1. The number of multi-chains π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{l−1} in the poset ÑC^{m}(A_{n−1}), with the property that rk(π_{i}) = s_{1} + s_{2} + ⋯ + s_{i}, i = 1, 2, …, l − 1, and that the number of blocks of size mi of π_{1} is b_{i}, i = 1, 2, …, n, is given by

\frac{1}{b_{1} + b_{2} + ⋯ + b_{n}} \binom{b_{1} + b_{2} + ⋯ + b_{n}}{b_{1}, b_{2}, …, b_{n}}\binom{mn}{s_{2}} ⋯ \binom{mn}{s_{l}},  (8.5)

provided that b_{1} + 2b_{2} + ⋯ + nb_{n} ≤ n, and is 0 otherwise.

Remark. The conditions in the statement of the corollary imply that

s_{1} + b_{1} + b_{2} + ⋯ + b_{n} = n.  (8.6)

Proof. Let

π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{l−1}  (8.7)

be a multi-chain in ÑC^{m}(A_{n−1}). Suppose that, under the bijection ▽_{A_{n−1}}^{m}, the element π_{j} corresponds to the tuple (w_{0}^{(j)}; w_{1}^{(j)}, …, w_{m}^{(j)}), j = 1, 2, …, l − 1. The inequalities in (8.7) imply that w_{1}^{(1)}, w_{2}^{(1)}, …, w_{m}^{(1)} can be factored in the form

w_{i}^{(1)} = u_{i}^{(2)}u_{i}^{(3)} ⋯ u_{i}^{(l)}, i = 1, 2, …, m,

where u_{i}^{(l)} = w_{i}^{(l−1)} and, more generally,

w_{i}^{(j)} = u_{i}^{(j+1)}u_{i}^{(j+2)} ⋯ u_{i}^{(l)}, i = 1, 2, …, m, j = 1, 2, …, l − 1.  (8.8)

For later use, we record that

c = w_{0}^{(j)}w_{1}^{(j)} ⋯ w_{m}^{(j)}
= w_{0}^{(j)}(u_{1}^{(j+1)}u_{1}^{(j+2)} ⋯ u_{1}^{(l)})(u_{2}^{(j+1)}u_{2}^{(j+2)} ⋯ u_{2}^{(l)}) ⋯ (u_{m}^{(j+1)}u_{m}^{(j+2)} ⋯ u_{m}^{(l)}).  (8.9)

Now, by (7.4), the block structure conditions on π_{1} in the statement of the corollary translate into the condition that the type of w_{0}^{(1)} is

A_{1}^{b_{2}} ∗ A_{2}^{b_{3}} ∗ ⋯ ∗ A_{n−1}^{b_{n}}.  (8.10)

On the other hand, using (7.2), we see that the rank conditions in the statement of the corollary mean that

ℓ_{T} (w_{0}^{(j)}) = s_{1} + s_{2} + ⋯ + s_{j}, j = 1, 2, …, l − 1.

In combination with (8.9), this yields the conditions

ℓ_{T} (u_{1}^{(j)}) + ℓ_{T} (u_{2}^{(j)}) + ⋯ + ℓ_{T} (u_{m}^{(j)}) = s_{j}, j = 2, 3, …, l.  (8.11)

Thus, we want to count the number of factorisations

c = w_{0}^{(1)}(u_{1}^{(2)}u_{1}^{(3)} ⋯ u_{1}^{(l)})(u_{2}^{(2)}u_{2}^{(3)} ⋯ u_{2}^{(l)}) ⋯ (u_{m}^{(2)}u_{m}^{(3)} ⋯ u_{m}^{(l)}),  (8.12)

where the type of w_{0}^{(1)} is given in (8.10), and where the “rank conditions” (8.11) are satisfied. So, in view of (2.4), we are in the situation of Theorem 11 with n replaced by n − 1, d = 1, l replaced by l − 1, s_{i} replaced by s_{i+1}, i = 1, 2, …, l − 1, T_{1} the type in (8.10), m_{1} = m_{2} = ⋯ = m_{l−1} = m, except that the factors are not exactly in the order as in (8.1). However, by (2.2) we know that the order of factors is without relevance. Therefore we just have to apply Theorem 11 with the above specialisations. If we also take into account (8.6), then we arrive immediately at (8.5). □

This result is new even for m = 1, that is, for the poset of Kreweras’ non-crossing partitions of {1, 2, …, n}. It implies all known results on Kreweras’ non-crossing partitions and the m-divisible non-crossing partitions of Edelman. Namely, for l = 2 it reduces to Armstrong’s result [1, Theorem 4.4.4 with ℓ = 1] on the number of m-divisible non-crossing partitions in ÑC^{m}(A_{n−1}) with a given block structure, which itself contains Kreweras’ result [30, Theorem 4] on his non-crossing partitions with a given block structure as a special case. If we sum the expression (8.5) over all s_{2}, s_{3}, …, s_{l} with s_{2} + s_{3} + ⋯ + s_{l} = n − 1 − s_{1}, then we obtain that the number of all multi-chains π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{l−1} in Edelman’s poset ÑC^{m}(A_{n−1}) of m-divisible non-crossing partitions of {1, 2, …, mn} in which π_{1} has b_{i} blocks of size mi equals

\frac{1}{b_{1} + b_{2} + ⋯ + b_{n}} \binom{b_{1} + b_{2} + ⋯ + b_{n}}{b_{1}, b_{2}, …, b_{n}}\binom{(l − 1)mn}{n − s_{1} − 1}

= \frac{1}{b_{1} + b_{2} + ⋯ + b_{n}} \binom{b_{1} + b_{2} + ⋯ + b_{n}}{b_{1}, b_{2}, …, b_{n}}\binom{(l − 1)mn}{b_{1} + b_{2} + ⋯ + b_{n} − 1}, (8.13)

provided that b_{1} + 2b_{2} + ⋯ + nb_{n} ≤ n, a result originally due to Armstrong [1, Theorem 4.4.4]. On the other hand, if we sum the expression (8.5) over all possible b_{1}, b_{2}, …, b_{n}, that is, b_{2} + 2b_{3} + ⋯ + (n − 1)b_{n} = s_{1}, use of Lemma 4 with M = n − s_{1} and r = s_{1} yields that the number of all multi-chains π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{l−1} in Edelman’s poset ÑC^{m}(A_{n−1}) ≅ NC^{m}(A_{n−1}) where π_{i} is of rank s_{1} +s_{2} +⋯+s_{i}, i = 1, 2, …, l−1, equals

\frac{1}{n}\binom{n}{s_{1}}\binom{mn}{s_{2}} ⋯ \binom{mn}{s_{l}},  (8.14)

a result originally due to Edelman [18, Theorem 4.2]. Clearly, this formula contains at the same time a formula for the number of all m-divisible non-crossing partitions of {1, 2, …, mn} with a given number of blocks upon setting l = 2 (cf. [18, Lemma 4.1]), as well as that it implies that the total number of multi-chains π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{l−1} in the poset of these partitions is

\frac{1}{n}\binom{(l − 1)mn + n}{n − 1}  (8.15)

upon summing (8.14) over all non-negative integers s_{1}, s_{2}, …, s_{l} with s_{1} +s_{2} +⋯+s_{l} = n − 1 by means of the multivariate Chu–Vandermonde summation, thus recovering the formula [18, Cor. 4.4] for the zeta polynomial of the poset of m-divisible non-crossing partitions of type A_{n−1}. As special case l = 2, we recover the well-known fact that the total number of m-divisible non-crossing partitions of \{1, 2, …, mn\} is \frac{1}{n} \binom{(m+1)n}{n−1}.

We continue with our results for type B_{n}. We formulate the theorem below on factorisations in W (B_{n}) only with restrictions on the combinatorial type of some factors. An analogous result with group-theoretical type instead could be easily derived as well. We omit this here because, for the combinatorial applications that we have in mind, combinatorial type suffices. We remark that the theorem generalises Theorem 8, which can be obtained from the former as the special case in which l = 1 and m_{1} = 1.

Theorem 13. (i) For a positive integer d, let the types T_{1}, T_{2}, …, T_{d} be given, where

T_{i} = A_{1}^{m_{1}^{(i)}} ∗ A_{2}^{m_{2}^{(i)}} ∗ ⋯ ∗ A_{n}^{m_{n}^{(i)}}, i = 1, 2, …, j − 1, j + 1, …, d,

and

T_{j} = B_{α} ∗ A_{1}^{m_{1}^{(j)}} ∗ A_{2}^{m_{2}^{(j)}} ∗ ⋯ ∗ A_{n}^{m_{n}^{(j)}},

for some α ≥ 1, and let l, m_{1}, m_{2}, …, m_{l}, s_{1}, s_{2}, …, s_{l} be given non-negative integers with

rk T_{1} + rk T_{2} + ⋯ + rk T_{d} + s_{1} + s_{2} + ⋯ + s_{l} = n.  (8.16)

Then the number of factorisations

c = σ_{1}σ_{2} ⋯ σ_{d}σ_{1}^{(1)}σ_{2}^{(1)} ⋯ σ_{m_{1}}^{(1)}σ_{1}^{(2)}σ_{2}^{(2)} ⋯ σ_{m_{2}}^{(2)} ⋯ σ_{1}^{(l)}σ_{2}^{(l)} ⋯ σ_{m_{l}}^{(l)},  (8.17)

where c is a Coxeter element in W (B_{n}), such that the combinatorial type of σ_{i} is T_{i}, i = 1, 2, …, d, and such that

ℓ_{T} (σ_{1}^{(i)}) + ℓ_{T} (σ_{2}^{(i)}) + ⋯ + ℓ_{T} (σ_{m_{i}}^{(i)}) = s_{i}, i = 1, 2, …, l,  (8.18)

is given by

n^{d−1}\binom{n − rk T_{j}}{m_{1}^{(j)}, m_{2}^{(j)}, …, m_{n}^{(j)}}(_{∏_{i=1}^{d} ; i≠j} \frac{1}{n − rk T_{i}} \binom{n − rk T_{i}}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}})

× \binom{m_{1}n}{s_{1}}\binom{m_{2}n}{s_{2}} ⋯ \binom{m_{l}n}{s_{l}}, (8.19)

where the multinomial coefficient is defined as in Lemma 4.

(ii) For a positive integer d, let the types T_{1}, T_{2}, …, T_{d} be given, where

T_{i} = A_{1}^{m_{1}^{(i)}} ∗ A_{2}^{m_{2}^{(i)}} ∗ ⋯ ∗ A_{n}^{m_{n}^{(i)}}, i = 1, 2, …, d,

and let l, m_{1}, m_{2}, …, m_{l}, s_{1}, s_{2}, …, s_{l} be given non-negative integers. Then the number of factorisations (8.17) which satisfy (8.18) plus the condition that the combinatorial type of σ_{i} is T_{i}, i = 1, 2, …, d, is given by

n^{d−1}(n − rk T_{1} − rk T_{2} − ⋯ − rk T_{d})(∏_{i=1}^{d} \frac{1}{n − rk T_{i}} \binom{n − rk T_{i}}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}})

× \binom{m_{1}n}{s_{1}}\binom{m_{2}n}{s_{2}} ⋯ \binom{m_{l}n}{s_{l}}. (8.20)

Proof. We start with the proof of item (i). In the factorisation (8.17), we first fix also the types of the σ_{i}^{(j)}’s. For i = 1, 2, …, m_{j} and j = 1, 2, …, l let the type of σ_{i}^{(j)} be

T_{i}^{(j)} = A_{1}^{m_{1}^{(i,j)}} ∗ A_{2}^{m_{2}^{(i,j)}} ∗ ⋯ ∗ A_{n}^{m_{n}^{(i,j)}}.

We know that the number of these factorisations is given by (5.1) with d replaced by d+m_{1}+m_{2}+⋯+m_{l} and the appropriate interpretations of the m_{i}^{(j)}’s. Next we fix nonnegative integers r_{i}^{(j)} and sum the expression (5.1) over all possible types T_{i}^{(j)} of rank r_{i}^{(j)}, i = 1, 2, …, m_{j}, j = 1, 2, …, l. The corresponding summations are completely analogous to the first summation in the proof of Theorem 8. As a result, we obtain

n^{d−1}\binom{n − rk T_{j}}{m_{1}^{(j)}, m_{2}^{(j)}, …, m_{n}^{(j)}}(_{∏_{i=1}^{d} ; i≠j} \frac{1}{n − rk T_{i}} \binom{n − rk T_{i}}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}})

× \binom{n}{r_{1}^{(1)}}\binom{n}{r_{2}^{(1)}} ⋯ \binom{n}{r_{m_{1}}^{(1)}} × \binom{n}{r_{1}^{(2)}}\binom{n}{r_{2}^{(2)}} ⋯ \binom{n}{r_{m_{2}}^{(2)}}

× ⋯ × \binom{n}{r_{1}^{(l)}}\binom{n}{r_{2}^{(l)}} ⋯ \binom{n}{r_{m_{l}}^{(l)}}

for the number of factorisations under consideration. In view of (8.18) and (2.4), to obtain the final result, we must sum these expressions over all non-negative integers r_{1}^{(1)}, …, r_{m_{l}}^{(l)} satisfying the equations

r_{1}^{(j)} + r_{2}^{(j)} + ⋯ + r_{m_{j}}^{(j)} = s_{j}, j = 1, 2, …, l.

This is easily done by means of the multivariate version of the Chu–Vandermonde summation. The formula in (8.19) follows.

The proof of item (ii) is completely analogous, we must, however, cope with the complication that the type B cycle, which, according to Theorem 7, must occur in the disjoint cycle decomposition of exactly one of the factors on the right-hand side of (8.17), can occur in any of the σ_{i}^{(j)}’s. So, let us fix the types of the σ_{i}^{(j)}’s to

T_{i}^{(j)} = A_{1}^{m_{1}^{(i,j)}} ∗ A_{2}^{m_{2}^{(i,j)}} ∗ ⋯ ∗ A_{n}^{m_{n}^{(i,j)}},

i = 1, 2, …, m_{j}, j = 1, 2, …, l, except for (i, j) = (p, q), where we require that the type of σ_{p}^{(q)} is

T_{p}^{(q)} = B_{α} ∗ Am̃_{1} ; 1 ∗ Am̃_{2} ; 2 ∗ ⋯ ∗ Am̃_{n} ; n.

Again, we know that the number of these factorisations is given by (5.1) with d replaced by d + m_{1} + m_{2} + ⋯ + m_{l} and the appropriate interpretations of the m_{i}^{(j)}’s. Now we fix non-negative integers r_{i}^{(j)} and sum the expression (5.1) over all possible types T_{i}^{(j)} of rank r_{i}^{(j)}, i = 1, 2, …, m_{j}, j = 1, 2, …, l. Again, the corresponding summations are completely analogous to the summations in the proof of Theorem 8. In particular, the summation over all possible types T_{p}^{(q)} of rank r_{p}^{(q)} is essentially the summation on the right-hand side of (5.14) with d replaced by d + m_{1} + m_{2} + ⋯ + m_{l} and r replaced by r_{p}^{(q)}. If we use what we know from the proof of Theorem 8, then the result of the summations is found to be

n^{d−1}(∏_{i=1}^{d} \frac{1}{n − rk T_{i}} \binom{n − rk T_{i}}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}})

× \binom{n}{r_{1}^{(1)}}\binom{n}{r_{2}^{(1)}} ⋯ \binom{n}{r_{m_{1}}^{(1)}} × ⋯ × \binom{n}{r_{1}^{(q)}} ⋯ r_{p}^{(q)}\binom{n}{r_{p}^{(q)}} ⋯ \binom{n}{r_{m_{q}}^{(q)}}

× ⋯ × \binom{n}{r_{1}^{(l)}}\binom{n}{r_{2}^{(l)}} ⋯ \binom{n}{r_{m_{l}}^{(l)}}. (8.21)

The reader should note that the term r_{p}^{(q)}\binom{n}{r_{p}^{(q)}} in this expression results from the sum-

mation over all types T_{p}^{(q)} of rank r_{p}^{(q)} (compare (5.15) with r replaced by r_{p}^{(q)}; we have

\binom{n−1}{r_{p}^{(q)}−1} = \frac{r_{p}^{(q)}}{n} \binom{n}{r_{p}^{(q)}}). Using (8.16), (8.18) and (2.4), we see that the sum of all r_{p}^{(q)} over p = 1, 2, …, m_{q} and q = 1, 2, …, l must be n − rk T_{1} − rk T_{2} − ⋯ − rk T_{d}. Hence, the sum of the expressions (8.21) over all (p, q) equals

n^{d−1}(n − rk T_{1} − rk T_{2} − ⋯ − rk T_{d})(∏_{i=1}^{d} \frac{1}{n − rk T_{i}} \binom{n − rk T_{i}}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}})

× \binom{n}{r_{1}^{(1)}}\binom{n}{r_{2}^{(1)}} ⋯ \binom{n}{r_{m_{1}}^{(1)}} × ⋯ × \binom{n}{r_{1}^{(q)}}\binom{n}{r_{2}^{(q)}} ⋯ \binom{n}{r_{m_{q}}^{(q)}}

× ⋯ × \binom{n}{r_{1}^{(l)}}\binom{n}{r_{2}^{(l)}} ⋯ \binom{n}{r_{m_{l}}^{(l)}}.

Finally, we must sum these expressions over all non-negative integers r_{1}^{(1)}, …, r_{m_{l}}^{(l)} satisfying the equations

r_{1}^{(j)} + r_{2}^{(j)} + ⋯ + r_{m_{j}}^{(j)} = s_{j}, j = 1, 2, …, l.

Once again, this is easily done by means of the multivariate version of the Chu– Vandermonde summation. As a result, we obtain the formula in (8.20). □

In view of the combinatorial realisation of m-divisible non-crossing partitions of type B_{n} which we described in Section 7, the special case d = 1 of the above theorem has the following enumerative consequence.

Corollary 14. Let l be a positive integer, and let s_{1}, s_{2}, …, s_{l} be non-negative integers with s_{1} + s_{2} + ⋯ + s_{l} = n. The number of multi-chains π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{l−1} in the poset ÑC^{m}(B_{n}) with the property that rk(π_{i}) = s_{1} + s_{2} + ⋯ + s_{i}, i = 1, 2, …, l − 1, and that the number of non-zero blocks of π_{1} of size mi is 2b_{i}, i = 1, 2, …, n, is given by

\binom{b_{1} + b_{2} + ⋯ + b_{n}}{b_{1}, b_{2}, …, b_{n}}\binom{mn}{s_{2}} ⋯ \binom{mn}{s_{l}},  (8.22)

provided that b_{1} + 2b_{2} + ⋯ + nb_{n} ≤ n, and is 0 otherwise.

Remark. The conditions in the statement of the corollary imply that

s_{1} + b_{1} + b_{2} + ⋯ + b_{n} = n.  (8.23)

The reader should recall from Section 7, that non-zero blocks of elements π of ÑC^{m}(B_{n}) occur in pairs since, with a block B of π, also \overline{B} is a block of π.

Proof. The arguments are completely analogous to those of the proof of Corollary 12. The conclusion here is that we need Theorem 13 with d = 1, l replaced by l − 1, s_{i} replaced by s_{i+1}, i = 1, 2, …, l − 1, m_{1} = m_{2} = ⋯ = m_{l−1} = m, and T_{1} of the type

B_{n−b_{1}−2b_{2}−···−nb_{n}} ∗ A_{1}^{b_{2}} ∗ A_{2}^{b_{3}} ∗ ⋯ ∗ A_{n−1}^{b_{n}}

in the case that b_{1} + 2b_{2} + ⋯ + nb_{n} < n (which enforces the existence of a zero block of size 2(n − b_{1} − 2b_{2} − ⋯ − nb_{n}) in π_{1}), respectively

A_{1}^{b_{2}} ∗ A_{2}^{b_{3}} ∗ ⋯ ∗ A_{n−1}^{b_{n}}

if not. So, depending on the case in which we are, we have to apply (8.19), respectively (8.20). However, for d = 1 these two formulae become identical. More precisely, under the above specialisations, they reduce to

\binom{n − rk T_{1}}{b_{2}, b_{3}, …, b_{n}}\binom{mn}{s_{2}} ⋯ \binom{mn}{s_{l}}.

If we also take into account (8.23), then we arrive immediately at (8.22). □

This result is new even for m = 1, that is, for the poset of Reiner’s type B_{n} non-crossing partitions. It implies all known results on these non-crossing partitions and their extension to m-divisible type B_{n} non-crossing partitions due to Armstrong. Namely, for l = 2 it reduces to Armstrong’s result [1, Theorem 4.5.11 with ℓ = 1] on the number of elements of ÑC^{m}(B_{n}) with a given block structure, which itself contains Athanasiadis’ result [2, Theorem 2.3] on Reiner’s type B_{n} non-crossing partitions with a given block structure as a special case. If we sum the expression (8.22) over all s_{2}, s_{3}, …, s_{l} with s_{2} + s_{3} + ⋯ + s_{l} = n − s_{1}, then we obtain that the number of all multi-chains π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{l−1} in ÑC^{m}(B_{n}) in which π_{1} has 2b_{i} non-zero blocks of size mi equals

\binom{b_{1} + b_{2} + ⋯ + b_{n}}{b_{1}, b_{2}, …, b_{n}}\binom{(l − 1)mn}{n − s_{1}} = \binom{b_{1} + b_{2} + ⋯ + b_{n}}{b_{1}, b_{2}, …, b_{n}}\binom{(l − 1)mn}{b_{1} + b_{2} + ⋯ + b_{n}},

(8.24)

provided that b_{1} + 2b_{2} + ⋯ + nb_{n} ≤ n, a result originally due to Armstrong [1, Theorem 4.5.11]. On the other hand, if we sum the expression (8.22) over all possible b_{1}, b_{2}, …, b_{n}, that is, over b_{2} + 2b_{3} + ⋯ + (n − 1)b_{n} ≤ s_{1}, use of Lemma 4 with M = n − s_{1} and r = s_{1} − α (where α stands for the difference between s_{1} and b_{2} +2b_{3} +⋯+(n−1)b_{n}) yields that the number of all multi-chains π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{l−1} in ÑC^{m}(B_{n}) ≅ NC^{m}(B_{n}) where π_{i} is of rank s_{1} +s_{2} +⋯+s_{i}, i = 1, 2, …, l −1, equals

∑_{α=0}^{n} \binom{n − α − 1}{s_{1} − α}\binom{mn}{s_{2}} ⋯ \binom{mn}{s_{l}} = \binom{n}{s_{1}}\binom{mn}{s_{2}} ⋯ \binom{mn}{s_{l}},  (8.25)

another result due to Armstrong [1, Theorem 4.5.7]. Clearly, this formula contains at the same time a formula for the number of all elements of ÑC^{m}(B_{n}) ≅ NC^{m}(B_{n}) with a given number of blocks (equivalently, a given rank) upon setting l = 2 (cf. [1, Theorem 4.5.8]), as well as that it implies that the total number of multi-chains π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{l−1} in ÑC^{m}(B_{n}) ≅ NC^{m}(B_{n}) is

\binom{(l − 1)mn + n}{n}  (8.26)

upon summing (8.25) over all non-negative integers s_{1}, s_{2}, …, s_{l} with s_{1} +s_{2} +⋯+s_{l} = n by means of the multivariate Chu–Vandermonde summation, thus recovering the formula [1, Theorem 3.6.9] for the zeta polynomial of the poset of generalised noncrossing partitions in the case of type B_{n}. As special case l = 2, we recover the fact that the cardinality of ÑC^{m}(B_{n}) ≅ NC^{m}(B_{n}) is \binom{(m+1)n}{n} (cf. [1, Theorem 3.5.3]).

The final set of results in this section concerns the type D_{n}. We start with Theorem 15, the result on factorisations in W (D_{n}) which is analogous to Theorems 11 and 13. Similar to Theorem 13, we formulate the theorem only with restrictions on the combinatorial type of some factors. An analogous result with group-theoretical type instead could be easily derived as well. We refrain from doing this here because, again, for the combinatorial applications that we have in mind, combinatorial type suffices. We remark that the theorem generalises Theorem 10, which can be obtained from the former as the special case in which l = 1 and m_{1} = 1.

Theorem 15. (i) For a positive integer d, let the types T_{1}, T_{2}, …, T_{d} be given, where

T_{i} = A_{1}^{m_{1}^{(i)}} ∗ A_{2}^{m_{2}^{(i)}} ∗ ⋯ ∗ A_{n}^{m_{n}^{(i)}}, i = 1, 2, …, j − 1, j + 1, …, d,

and

T_{j} = D_{α} ∗ A_{1}^{m_{1}^{(j)}} ∗ A_{2}^{m_{2}^{(j)}} ∗ ⋯ ∗ A_{n}^{m_{n}^{(j)}},

for some α ≥ 2, and let l, m_{1}, m_{2}, …, m_{l}, s_{1}, s_{2}, …, s_{l} be given non-negative integers with

rk T_{1} + rk T_{2} + ⋯ + rk T_{d} + s_{1} + s_{2} + ⋯ + s_{l} = n.

Then the number of factorisations

c = σ_{1}σ_{2} ⋯ σ_{d}σ_{1}^{(1)}σ_{2}^{(1)} ⋯ σ_{m_{1}}^{(1)}σ_{1}^{(2)}σ_{2}^{(2)} ⋯ σ_{m_{2}}^{(2)} ⋯ σ_{1}^{(l)}σ_{2}^{(l)} ⋯ σ_{m_{l}}^{(l)},  (8.27)

where c is a Coxeter element in W (D_{n}), such that the combinatorial type of σ_{i} is T_{i}, i = 1, 2, …, d, and such that

ℓ_{T} (σ_{1}^{(i)}) + ℓ_{T} (σ_{2}^{(i)}) + ⋯ + ℓ_{T} (σ_{m_{i}}^{(i)}) = s_{i}, i = 1, 2, …, l,  (8.28)

is given by

(n − 1)^{d−1}\binom{n − rk T_{j}}{m_{1}^{(j)}, m_{2}^{(j)}, …, m_{n}^{(j)}}(_{∏_{i=1}^{d} ; i≠j} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}})

× \binom{m_{1}(n − 1)}{s_{1}}\binom{m_{2}(n − 1)}{s_{2}} ⋯ \binom{m_{l}(n − 1)}{s_{l}}, (8.29)

the multinomial coefficient being defined as in Lemma 4.

(ii) For a positive integer d, let the types T_{1}, T_{2}, …, T_{d} be given, where

T_{i} = A_{1}^{m_{1}^{(i)}} ∗ A_{2}^{m_{2}^{(i)}} ∗ ⋯ ∗ A_{n}^{m_{n}^{(i)}}, i = 1, 2, …, d,

and let l, m_{1}, m_{2}, …, m_{l}, s_{1}, s_{2}, …, s_{l} be given non-negative integers. Then the number of factorisations (8.27) which satisfy (8.28) as well as the condition that the combinatorial type of σ_{i} is T_{i}, i = 1, 2, …, d, is given by

2(n − 1)^{d−1}( ∑_{j=1}^{d} \binom{n − rk T_{j}}{m_{1}^{(j)}, m_{2}^{(j)}, …, m_{n}^{(j)}}_{∏_{i=1}^{d} ; i≠j} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}})

× \binom{m_{1}(n − 1)}{s_{1}}\binom{m_{2}(n − 1)}{s_{2}} ⋯ \binom{m_{l}(n − 1)}{s_{l}}

+ (n − 1)^{d}(∏_{i=1}^{d} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}})

× ∑_{j=1}^{l} m_{j}\binom{m_{1}(n − 1)}{s_{1}} ⋯ \binom{m_{j}(n − 1) − 1}{s_{j} − 2} ⋯ \binom{m_{l}(n − 1)}{s_{l}}

− 2(d − 1)(n − 1)^{d}(∏_{i=1}^{d} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}})

× \binom{m_{1}(n − 1)}{s_{1}}\binom{m_{2}(n − 1)}{s_{2}} ⋯ \binom{m_{l}(n − 1)}{s_{l}}. (8.30)

Proof. The proof of item (i) is completely analogous to the proof of item (i) in Theorem 13. Making reference to that proof, the only difference is that, instead of the expression (5.1), we must use (6.1) with d replaced by d + m_{1} + m_{2} + ⋯ + m_{l} and the appropriate interpretations of the m_{i}^{(j)}’s. The summations over types T_{i}^{(j)} with fixed rank r_{i}^{(j)} are carried out by using (3.4) with M = n − r − 1. Subsequently, the summations over the r_{i}^{(j)}’s satisfying (8.4) are done by the multivariate version of the Chu–Vandermonde summation. We leave it to the reader to fill in the details to finally arrive at (8.29).

Similarly, the proof of item (ii) is analogous to the proof of item (ii) in Theorem 13. However, we must cope with the complication that there may or may not be a type D cycle in the disjoint cycle decomposition of one of the σ_{i}^{(j)}’s on the right-hand side of (8.27). In the case that there is no type B cycle, we fix the types of the σ_{i}^{(j)}’s to

T_{i}^{(j)} = A_{1}^{m_{1}^{(i,j)}} ∗ A_{2}^{m_{2}^{(i,j)}} ∗ ⋯ ∗ A_{n}^{m_{n}^{(i,j)}},

i = 1, 2, …, m_{j}, j = 1, 2, …, l, and sum the expression (6.2) with d replaced by d + m_{1} + m_{2} + ⋯ + m_{l} and the appropriate interpretations of the m_{i}^{(j)}’s over all possible types T_{i}^{(j)} with rank r_{i}^{(j)}, i = 1, 2, …, m_{j}, j = 1, 2, …, l. This yields the expression

2(n − 1)^{d−1}( ∑_{j=1}^{d} \binom{n − rk T_{j}}{m_{1}^{(j)}, m_{2}^{(j)}, …, m_{n}^{(j)}}_{∏_{i=1}^{d} ; i≠j} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}})

× \binom{n − 1}{r_{1}^{(1)}}\binom{n − 1}{r_{2}^{(1)}} ⋯ \binom{n − 1}{r_{m_{1}}^{(1)}} × ⋯ × \binom{n − 1}{r_{1}^{(l)}}\binom{n − 1}{r_{2}^{(l)}} ⋯ \binom{n − 1}{r_{m_{l}}^{(l)}}

+ 2(n − 1)^{d}( ∑_{j=1}^{l} ∑_{i=1}^{m_{j}} ∏_{i=1}^{d} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}})

× \binom{n − 1}{r_{1}^{(1)}}\binom{n − 1}{r_{2}^{(1)}} ⋯ \binom{n − 1}{r_{m_{1}}^{(1)}} × ⋯ × \binom{n − 1}{r_{1}^{(l)}}\binom{n − 1}{r_{2}^{(l)}} ⋯ \binom{n − 1}{r_{m_{l}}^{(l)}}

− 2(d − 1)(n − 1)^{d−1}(∏_{i=1}^{d} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}})

× \binom{n − 1}{r_{1}^{(1)}}\binom{n − 1}{r_{2}^{(1)}} ⋯ \binom{n − 1}{r_{m_{1}}^{(1)}} × ⋯ × \binom{n − 1}{r_{1}^{(l)}}\binom{n − 1}{r_{2}^{(l)}} ⋯ \binom{n − 1}{r_{m_{l}}^{(l)}}. (8.31)

In the case that there appears, however, a type B cycle in σ_{p}^{(q)}, say, we adopt the same set-up as above, except that we restrict σ_{p}^{(q)} to types of the form

T_{p}^{(q)} = D_{α} ∗ Am̃_{1} ; 1 ∗ Am̃_{2} ; 2 ∗ ⋯ ∗ Am̃_{n} ; n.

Subsequently, we sum the expression (6.1) with d replaced by d + m_{1} + m_{2} + ⋯ + m_{l} and the appropriate interpretations of the m_{i}^{(j)}’s over all possible types T_{i}^{(j)} of rank r_{i}^{(j)}. This time, we obtain

(n − 1)^{d}( ∑_{q=1}^{l} ∑_{p=1}^{m_{q}} ∑_{α=2}^{n} ∏_{i=1}^{d} \frac{1}{n − rk T_{i} − 1}\binom{n − rk T_{i} − 1}{m_{1}^{(i)}, m_{2}^{(i)}, …, m_{n}^{(i)}})

× \binom{n − 1}{r_{1}^{(1)}}\binom{n − 1}{r_{2}^{(1)}} ⋯ \binom{n − 1}{r_{m_{1}}^{(1)}} × ⋯ × \binom{n − 1}{r_{1}^{(q)}} ⋯ \binom{n − α − 1}{r_{p}^{(q)} − α} ⋯ \binom{n − 1}{r_{m_{q}}^{(q)}}

× ⋯ × \binom{n − 1}{r_{1}^{(l)}}\binom{n − 1}{r_{2}^{(l)}} ⋯ \binom{n − 1}{r_{m_{l}}^{(l)}}. (8.32)

The sum over α can be evaluated by means of the elementary summation formula

∑_{α=2}^{n} \binom{n − α − 1}{r − α} = ∑_{α=2}^{n} \binom{n − α − 1}{n − r − 1} = \binom{n − 2}{n − r} = \binom{n − 2}{r − 2}.

Finally, we must sum the expressions (8.31) and (8.32) over all non-negative integers r_{1}^{(1)}, …, r_{m_{l}}^{(l)} satisfying the equations

r_{1}^{(j)} + r_{2}^{(j)} + ⋯ + r_{m_{j}}^{(j)} = s_{j}, j = 1, 2, …, l.

Once again, this is easily done by means of the multivariate version of the Chu– Vandermonde summation. After some simplification, we obtain the formula in (8.30).

□

In view of the combinatorial realisation of m-divisible non-crossing partitions of type D_{n} which we described in Section 7, the special case d = 1 of the above theorem has the following enumerative consequence.

Corollary 16. Let l be a positive integer, and let s_{1}, s_{2}, …, s_{l} be non-negative integers with s_{1} + s_{2} + ⋯ + s_{l} = n. The number of multi-chains π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{l−1} in the poset ÑC^{m}(D_{n}) with the property that rk(π_{i}) = s_{1} + s_{2} + ⋯ + s_{i}, i = 1, 2, …, l − 1, and that the number of non-zero blocks of π_{1} of size mi is 2b_{i}, i = 1, 2, …, n, is given by

\binom{b_{1} + b_{2} + ⋯ + b_{n}}{b_{1}, b_{2}, …, b_{n}}\binom{m(n − 1)}{s_{2}} ⋯ \binom{m(n − 1)}{s_{l}},  (8.33)

if b_{1} + 2b_{2} + ⋯ + nb_{n} < n − 1, and

2\binom{b_{1} + b_{2} + ⋯ + b_{n}}{b_{1}, b_{2}, …, b_{n}}\binom{m(n − 1)}{s_{2}} ⋯ \binom{m(n − 1)}{s_{l}}

+ \frac{m(n − 1)}{b_{1} + b_{2} + ⋯ + b_{n} − 1}\binom{b_{1} + b_{2} + ⋯ + b_{n} − 1}{b_{1} − 1, b_{2}, …, b_{n}}

× ∑_{j=2}^{l} \binom{m(n − 1)}{s_{2}} ⋯ \binom{m(n − 1) − 1}{s_{j} − 2} ⋯ \binom{m(n − 1)}{s_{l}}, (8.34)

if b_{1} + 2b_{2} + ⋯ + nb_{n} = n.

Remark. The conditions in the statement of the corollary imply that

s_{1} + b_{1} + b_{2} + ⋯ + b_{n} = n.  (8.35)

The reader should recall from Section 7, that non-zero blocks of elements π of ÑC^{m}(D_{n}) occur in pairs since, with a block B of π, also \overline{B} is a block of π. The condition b_{1} + 2b_{2} + ⋯ + nb_{n} < n − 1, which is required for Formula (8.33) to hold, implies that π_{1} must contain a zero block of size 2(n − b_{1} − 2b_{2} − ⋯ − nb_{n}), while the equality b_{1} + 2b_{2} + ⋯ + nb_{n} = n, which is required for Formula (8.34) to hold, implies that π_{1} contains no zero block. The extra condition on zero blocks that are imposed on elements of ÑC^{m}(D_{n}) implies that b_{1} + 2b_{2} + ⋯ + nb_{n} cannot be equal to n − 1.

Proof. Again, the arguments are completely analogous to those of the proof of Corollary 12. Here we need Theorem 15 with d = 1, l replaced by l − 1, s_{i} replaced by s_{i+1}, i = 1, 2, …, l − 1, m_{1} = m_{2} = ⋯ = m_{l−1} = m, and T_{1} of the type

D_{n−b_{1}−2b_{2}−···−nb_{n}} ∗ A_{1}^{b_{2}} ∗ A_{2}^{b_{3}} ∗ ⋯ ∗ A_{n−1}^{b_{n}}

in the case that b_{1} + 2b_{2} + ⋯ + nb_{n} < n − 1, respectively

A_{1}^{b_{2}} ∗ A_{2}^{b_{3}} ∗ ⋯ ∗ A_{n−1}^{b_{n}}

if not. So, depending on the case in which we are, we have to apply (8.29), respectively (8.30). If we also take into account (8.35), then we arrive at the claimed result after little manipulation. Since we have done similar calculations already several times, the details are left to the reader. □

This result is new even for m = 1, that is, for the poset of type D_{n} non-crossing partitions of Athanasiadis and Reiner [4], and of Bessis and Corran [9]. Not only does it imply all known results on these non-crossing partitions and their extension to mdivisible type D_{n} non-crossing partitions due to Armstrong, it allows us as well to solve several open enumeration problems on the m-divisible type D_{n} non-crossing partitions. We state these new results separately in the corollaries below.

To begin with, if we set l = 2 in Corollary 16, then we obtain the following extension to ÑC^{m}(D_{n}) of Athanasiadis and Reiner’s result [4, Theorem 1.3] on the number of type D_{n} non-crossing partitions with a given block structure.

Corollary 17. The number of all elements of ÑC^{m}(D_{n}) which have 2b_{i} non-zero blocks of size mi equals

\binom{b_{1} + b_{2} + ⋯ + b_{n}}{b_{1}, b_{2}, …, b_{n}}\binom{m(n − 1)}{b_{1} + b_{2} + ⋯ + b_{n}}  (8.36)

if b_{1} + 2b_{2} + ⋯ + nb_{n} < n − 1, and

2\binom{b_{1} + b_{2} + ⋯ + b_{n}}{b_{1}, b_{2}, …, b_{n}}\binom{m(n − 1)}{b_{1} + b_{2} + ⋯ + b_{n}}

+ \binom{b_{1} + b_{2} + ⋯ + b_{n} − 1}{b_{1} − 1, b_{2}, …, b_{n}}\binom{m(n − 1)}{b_{1} + b_{2} + ⋯ + b_{n} − 1} (8.37)

if b_{1} + 2b_{2} + ⋯ + nb_{n} = n.

On the other hand, if we sum the expression (8.33), respectively (8.34), over all s_{2}, s_{3}, …, s_{l} with s_{2} +s_{3} +⋯+s_{l} = n−s_{1}, then we obtain the following generalisation.

Corollary 18. The number of all multi-chains π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{l−1} in ÑC^{m}(D_{n}) in which π_{1} has 2b_{i} non-zero blocks of size mi equals

\binom{b_{1} + b_{2} + ⋯ + b_{n}}{b_{1}, b_{2}, …, b_{n}}\binom{(l − 1)m(n − 1)}{b_{1} + b_{2} + ⋯ + b_{n}},  (8.38)

if b_{1} + 2b_{2} + ⋯ + nb_{n} < n − 1, and

2\binom{b_{1} + b_{2} + ⋯ + b_{n}}{b_{1}, b_{2}, …, b_{n}}\binom{(l − 1)m(n − 1)}{b_{1} + b_{2} + ⋯ + b_{n}}

+ \binom{b_{1} + b_{2} + ⋯ + b_{n} − 1}{b_{1} − 1, b_{2}, …, b_{n}}\binom{(l − 1)m(n − 1)}{b_{1} + b_{2} + ⋯ + b_{n} − 1} (8.39)

if b_{1} + 2b_{2} + ⋯ + nb_{n} = n.

Next we sum the expressions (8.33) and (8.34) over all possible b_{1}, b_{2}, …, b_{n}, that is, we sum (8.33) over b_{2} + 2b_{3} + ⋯ + (n − 1)b_{n} < s_{1} − 1, and we sum the expression (8.34) over b_{2} + 2b_{3} + ⋯ + (n − 1)b_{n} = s_{1}. With the help of Lemma 4 and the simple binomial summation (6.24), these sums can indeed be evaluated. In this manner, we obtain the following result on rank-selected chain enumeration in ÑC^{m}(D_{n}).

Corollary 19. The number of all multi-chains π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{l−1} in ÑC^{m}(D_{n}) ≅ NC^{m}(D_{n}) where π_{i} is of rank s_{1} + s_{2} + ⋯ + s_{i}, i = 1, 2, …, l − 1, equals

2\binom{n − 1}{s_{1}}\binom{m(n − 1)}{s_{2}} ⋯ \binom{m(n − 1)}{s_{l}}

+ m ∑_{j=2}^{l} \binom{n − 1}{s_{1}}\binom{m(n − 1)}{s_{2}} ⋯ \binom{m(n − 1) − 1}{s_{j} − 2} ⋯ \binom{m(n − 1)}{s_{l}}

+ \binom{n − 2}{s_{1} − 2}\binom{m(n − 1)}{s_{2}} ⋯ \binom{m(n − 1)}{s_{l}}. (8.40)

This formula extends Athanasiadis and Reiner’s formula [4, Theorem 1.2(ii)] from NC(D_{n}) to ÑC^{m}(D_{n}). Setting l = 2, we obtain a formula for the number of all elements in ÑC^{m}(D_{n}) ≅ NC^{m}(D_{n}) with a given number of blocks (equivalently, of given rank); cf. [1, Theorem 4.6.3]. Next, summing (8.40) over all non-negative integers s_{1}, s_{2}, …, s_{l} with s_{1} + s_{2} + ⋯ + s_{l} = n by means of the multivariate Chu–Vandermonde summation, we find that the total number of multi-chains π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{l−1} in ÑC^{m}(D_{n}) ≅ NC^{m}(D_{n}) is given by

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

= \frac{2(l − 1)m(n − 1) + n}{n}\binom{((l − 1)m + 1)(n − 1)}{n − 1}, (8.41)

thus recovering the formula [1, Theorem 3.6.9] for the zeta polynomial of the poset of generalised non-crossing partitions for the type D_{n}. The special case l = 2 of (8.41) gives the well-known fact that the cardinality of ÑC^{m}(D_{n}) ≅ NC^{m}(D_{n}) is \frac{2m(n−1)+n}{n} \binom{(m+1)(n−1)}{n−1} (cf. [1, Theorem 3.5.3]).

In the following section, Corollary 19 will enable us to provide a new proof of Armstrong’s F = M (Ex-)Conjecture in type D_{n}.

9. Proof of the F = M Conjecture for type D

Armstrong’s F = M (Ex-)Conjecture [1, Conjecture 5.3.2], which extends an earlier conjecture of Chapoton [17], relates the “F -triangle” of the generalised cluster complex of Fomin and Reading [19] to the “M-triangle” of Armstrong’s generalised non-crossing partitions. The F -triangle is a certain refined face count in the generalised cluster complex. We do not give the definition here and, instead, refer the reader to [1, 27], because it will not be important in what follows. It suffices to know that, again fixing a finite root system Φ of rank n and a positive integer m, the F -triangle F_{Φ}^{m}(x, y) for the generalised cluster complex Δ^{m}(Φ) is a polynomial in x and y, and that it was computed in [27] for all types. What we need here is that it was shown in [27, Sec. 11, Prop. D] that

(1 − xy)^{n}F_{D_{n}}^{m} (\frac{x(1 + y)}{1 − xy}, \frac{xy}{1 − xy} )

= ∑_{r,s≥0} x^{s}y^{r}(2\binom{n − 1}{s − 1}\binom{m(n − 1)}{r}\binom{m(n − 1) + s − r − 1}{s − r}

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

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

− m\binom{n − 1}{s − 1}\binom{m(n − 1)}{r}\binom{m(n − 1) + s − r − 2}{s − r − 2}). (9.1)

The “M-triangle” of NC^{m}(Φ) is the polynomial defined by

M_{Φ}^{m}(x, y) = ∑_{u,w∈NC^{m}(Φ)} μ(u, w) x^{rk u}y^{rk w},

where μ(u, w) is the Möbius function in NC^{m}(Φ). It is called “triangle” because the Möbius function μ(u, w) vanishes unless u ≤ w, and, thus, the only coefficients in the polynomial which may be non-zero are the coefficients of x^{k}y^{l} with 0 ≤ k ≤ l ≤ n.

An equivalent object is the dual M-triangle, which is defined by

(M_{Φ}^{m})^{∗}(x, y) = ∑_{u,w∈(NC^{m}(Φ))^{∗}} μ^{∗}(u, w) x^{rk^{∗} w}y^{rk^{∗} u},

where (NC^{m}(Φ))^{∗} denotes the poset dual to NC^{m}(Φ) (i.e., the poset which arises from NC^{m}(Φ) by reversing all order relations), where μ^{∗} denotes the Möbius function in (NC^{m}(Φ))^{∗}, and where rk^{∗} denotes the rank function in (NC^{m}(Φ))^{∗}. It is equivalent since, obviously, we have

(M_{Φ}^{m})^{∗}(x, y) = (xy)^{n}M_{Φ}^{m}(1/x, 1/y).  (9.2)

Given this notation, Armstrong’s F = M (Ex-)Conjecture [1, Conjecture 5.3.2] reads as follows.

Conjecture FM. For any finite root system Φ of rank n, we have

F_{Φ}^{m}(x, y) = y^{n} M_{Φ}^{m} (\frac{1 + y}{y − x}, \frac{y − x}{y}) .

Equivalently,

(1 − xy)^{n}F_{Φ}^{m} (\frac{x(1 + y)}{1 − xy}, \frac{xy}{1 − xy} ) = ∑_{u,w∈(NC^{m}(Φ))^{∗}} μ^{∗}(u, w) (−x)^{rk^{∗} w}(−y)^{rk^{∗} u}. (9.3)

So, Equation (9.1) provides an expression for the left-hand side of (9.3) for Φ = D_{n}. With our result on rank-selected chain enumeration in NC^{m}(D_{n}) given in Corollary 19, we are now able to calculate the right-hand side of (9.3) directly. As we mentioned already in the Introduction, together with the results from [27, 28], this completes a computational case-by-case proof of Conjecture FM. A case-free proof had been found earlier by Tzanaki in [38].

The only ingredient that we need for the proof is the well-known link between chain enumeration and the Möbius function. (The reader should consult [33, Sec. 3.11] for more information on this topic.) Given a poset P and two elements u and w, u ≤ w, in the poset, the zeta polynomial of the interval [u, w], denoted by Z(u, w; z), is the number of (multi)chains from u to w of length z. (It can be shown that this is indeed a polynomial in z.) Then the Möbius function of u and w is equal to μ(u, w) = Z(u, w; −1).

Proof of Conjecture FM in type D_{n}. We now compute the right-hand side of (9.3), that is,

∑_{u,w∈(NC^{m}(D_{n}))^{∗}} μ^{∗}(u, w)(−x)^{rk^{∗} w}(−y)^{rk^{∗} u}.

In order to compute the coefficient of x^{s}y^{r} in this expression,

(−1)^{r+s} _{∑_{u,w∈(NC^{m}(D_{n}))^{∗}} with rk^{∗} u=r and rk^{∗} w=s}μ^{∗}(u, w),

we compute the sum of all corresponding zeta polynomials (in the variable z), multiplied by (−1)^{r+s},

(−1)^{r+s} _{∑_{u,w∈(NC^{m}(D_{n}))^{∗}} with rk^{∗} u=r and rk^{∗} w=s}Z(u, w; z),

and then put z = −1.

For computing this sum of zeta polynomials, we must set l = z +2, n−s_{1} = s, s_{l} = r, s_{2} + s_{3} + ⋯ + s_{l−1} = s − r in (8.40), and then sum the resulting expression over all possible s_{2}, s_{3}, …, s_{l−1}. (The reader should keep in mind that the roles of s_{1}, s_{2}, …, s_{l} in Corollary 19 have to be reversed, since we are aiming at computing zeta polynomials in the poset dual to NC^{m}(D_{n}).) By using the Chu–Vandermonde summation, one obtains

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

+ zm\binom{m(n − 1)}{r}\binom{zm(n − 1) − 1}{s − r − 2}\binom{n − 1}{s − 1} + \binom{m(n − 1)}{r}\binom{zm(n − 1)}{s − r}\binom{n − 2}{s}.

If we put z = −1 in this expression and multiply it by (−1)^{r+s}, then we obtain exactly the coefficient of x^{s}y^{r} in (9.1). □

10. A conjecture of Armstrong on maximal intervals containing a random multichain

Given a finite root system of rank n, Conjecture 3.5.13 in [1] says the following:

If we choose an l-multichain uniformly at random from the set

{π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{l} : π_{i} ∈ NC^{m}(Φ), i = 1, …, l, and rk(π_{1}) = i},  (10.1)

then the expected number of maximal intervals in NC^{m}(Φ) containing this multichain is

\frac{Nar^{m}(Φ, n − i)}{Nar^{1}(Φ, n − i)},  (10.2)

where Nar^{m}(Φ, i) is the i-th Fuß–Narayana number associated to NC^{m}(Φ), that is, the number of elements of NC^{m}(Φ) of rank i. In particular, this expected value is independent of l.

We show in this section that, for types A_{n} and B_{n}, the conjecture follows easily from Edelman’s (8.14) respectively Armstrong’s (8.25) (presumably, this fact constituted the evidence for setting up the conjecture), while an analogous computation using our new result (8.40) demonstrates that it fails for type D_{n}. At the end of this section, we comment on what we think happens for the exceptional types.

The computation of the expected value in the above conjecture can be approached in the following way. One first observes that a maximal interval in NC^{m}(Φ) is an interval between an element π_{0} of rank 0 and the global maximum (c; ε, …, ε). Therefore, to compute the proposed expected value, we may count the number of chains

π_{0} ≤ π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{l}, rk(π_{0}) = 0 and rk(π_{1}) = i,  (10.3)

and divide this number by the total number of all chains in (10.1). Clearly, in types A_{n}, B_{n}, and D_{n}, this kind of chain enumeration can be easily accessed by (8.14), (8.25), and (8.40), respectively.

We begin with type A_{n}. By (8.14), the number of chains (10.3) equals

∑_{s_{2}+···+s_{l+1}=n−i} \frac{1}{n + 1}\binom{n + 1}{0}\binom{m(n + 1)}{i}\binom{m(n + 1)}{s_{2}} ⋯ \binom{m(n + 1)}{s_{l+1}}

= \frac{1}{n + 1}\binom{m(n + 1)}{i}\binom{ml(n + 1)}{n − i},

while the number of chains in (10.1) equals

∑_{s_{2}+···+s_{l+1}=n−i} \frac{1}{n + 1}\binom{n + 1}{i}\binom{m(n + 1)}{s_{2}} ⋯ \binom{m(n + 1)}{s_{l+1}}

= \frac{1}{n + 1}\binom{n + 1}{i}\binom{ml(n + 1)}{n − i}.

In both cases, we used the multivariate Chu–Vandermonde summation to evaluate the sums over s_{2}, …, s_{l+1}. The quotient of the two numbers is

\begin{matrix}\frac{1}{n + 1} & \binom{m(n + 1)}{i} \\ \frac{1}{n + 1} & \binom{n + 1}{i} \end{matrix} = \begin{matrix}\frac{1}{n + 1} & \binom{n + 1}{n − i} & \binom{m(n + 1)}{i} \\ \frac{1}{n + 1} & \binom{n + 1}{n − i} & \binom{n + 1}{i} \end{matrix},

which by (8.14) with n replaced by n + 1, l = 2, s_{1} = n − i, and s_{2} = i agrees indeed with (10.2) for Φ = A_{n}.

For type B_{n}, there is an analogous computation using (8.25), the details of which we leave to the reader. The result is that the desired expected value equals

\begin{matrix}( & {mn \atop i} & ) \\ ( & {n \atop i} & ) \end{matrix} = \begin{matrix}\binom{n}{n − i} & \binom{mn}{i} \\ \binom{n}{n − i} & \binom{n}{i} \end{matrix},

which by (8.25) with l = 2, s_{1} = n − i, and s_{2} = i agrees indeed with (10.2) for Φ = B_{n}.

The analogous computation for type D_{n} uses (8.40). The number of chains (10.3) equals

2 ∑_{s_{2}+···+s_{l+1}=n−i} \binom{n − 1}{0}\binom{m(n − 1)}{i}\binom{m(n − 1)}{s_{2}} ⋯ \binom{m(n − 1)}{s_{l+1}}

+ m ∑_{s_{2}+···+s_{l+1}=n−i} \binom{n − 1}{0}\binom{m(n − 1) − 1}{i − 2}\binom{m(n − 1)}{s_{2}} ⋯ \binom{m(n − 1)}{s_{l+1}}

+ m ∑_{j=3}^{l+1} ∑_{s_{2}+···+s_{l+1}=n−i} \binom{n − 1}{0}\binom{m(n − 1)}{i}\binom{m(n − 1)}{s_{2}}

⋯ \binom{m(n − 1) − 1}{s_{j} − 2} ⋯ \binom{m(n − 1)}{s_{l+1}}

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

+ m(l − 1)\binom{m(n − 1)}{i}\binom{ml(n − 1) − 1}{n − i − 2},  (10.4)

while the number of chains in (10.1) equals

2 ∑_{s_{2}+···+s_{l+1}=n−i} \binom{n − 1}{i}\binom{m(n − 1)}{s_{2}} ⋯ \binom{m(n − 1)}{s_{l+1}}

+ m ∑_{j=2}^{l+1} ∑_{s_{2}+···+s_{l+1}=n−i} \binom{n − 1}{i}\binom{m(n − 1)}{s_{2}} ⋯ \binom{m(n − 1) − 1}{s_{j} − 2} ⋯ \binom{m(n − 1)}{s_{l+1}}

+ ∑_{s_{2}+···+s_{l+1}=n−i} \binom{n − 2}{i − 2}\binom{m(n − 1)}{s_{2}} ⋯ \binom{m(n − 1)}{s_{l+1}}

= 2\binom{n − 1}{i}\binom{ml(n − 1)}{n − i} + ml\binom{n − 1}{i}\binom{ml(n − 1) − 1}{n − i − 2} + \binom{n − 2}{i − 2}\binom{ml(n − 1)}{n − i}. (10.5)

The quotient of (10.4) and (10.5) gives the desired expected value. It is, however, not independent of l, and therefore Armstrong’s conjecture does not hold for Φ = D_{n}.

In the case that Φ is of exceptional type, then, as we outline in the next section, the knowledge of the corresponding decomposition numbers (see the Appendix) allows one to access the rank selected chain enumeration. Using this, the approach for computing the expected value proposed by Armstrong that we used above for the classical types can be carried through as well for the exceptional types. We have not done this, but we expect that, similarly to the case of D_{n}, for most exceptional types the expected value will depend on l, so that Armstrong’s conjecture will probably also fail in these cases.

11. Chain enumeration in the poset of generalised non-crossing partitions for the exceptional types

Although it is not the main topic of our paper, we want to briefly demonstrate in this section that the knowledge of the decomposition numbers also enables one to do refined enumeration in the generalised non-crossing partition posets NC^{m}(Φ) for exceptional root systems Φ (of rank n). We restrict the following considerations to the rank-selected chain enumeration. This means that we want to count the number of all multi-chains π_{1} ≤ π_{2} ≤ ⋯ ≤ π_{l−1} in NC^{m}(Φ), where π_{i} is of rank s_{1} + s_{2} + ⋯ + s_{i}, i = 1, 2, …, l − 1. Let us denote this number by R_{Φ}(s_{1}, s_{2}, …, s_{l}), with s_{l} = n − s_{1} − s_{2} − ⋯ − s_{l}. Now, the considerations at the beginning of the proof of Corollary 12, leading to the factorisation (8.12) with rank constraints on the factors, are also valid for NC^{m}(Φ) instead of NC^{m}(A_{n−1}), that is, they are independent of the underlying root system. Hence, to determine the number R_{Φ}(s_{1}, s_{2}, …, s_{l}), we have to count all possible factorisations

c = w_{0}^{(1)}(u_{1}^{(2)}u_{1}^{(3)} ⋯ u_{1}^{(l)})(u_{2}^{(2)}u_{2}^{(3)} ⋯ u_{2}^{(l)}) ⋯ (u_{m}^{(2)}u_{m}^{(3)} ⋯ u_{m}^{(l)}),

under the rank constraints (8.11) and ℓ_{T} (w_{0}^{(1)}) = s_{1}, where c is a Coxeter element in W (Φ). As we remarked in the proof of Corollary 12, equivalently we may count all factorisations

c = w_{0}^{(1)}(u_{1}^{(2)}u_{2}^{(2)} ⋯ u_{m}^{(2)})(u_{1}^{(3)}u_{2}^{(3)} ⋯ u_{m}^{(3)}) ⋯ (u_{1}^{(l)}u_{2}^{(l)} ⋯ u_{m}^{(l)})  (11.1)

which satisfy (8.11) and ℓ_{T} (w_{0}^{(1)}) = s_{1}. We can now obtain an explicit expression by fixing first the types of w_{0}^{(1)} and all the u_{i}^{(j)}’s. Under these constraints, the number of factorisations (11.1) is just the corresponding decomposition number. Subsequently, we sum the resulting expressions over all possible types.

Before we are able to state the formula which we obtain in this way, we need to recall some standard integer partition notation (cf. e.g. [34, Sec. 7.2]). An integer partition λ (with n parts) is an n-tuple λ = (λ_{1}, λ_{2}, …, λ_{n}) of integers satisfying λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{n} ≥ 0. It is called an integer partition of N, written in symbolic notation as λ ⊢ N, if λ_{1} + λ_{2} + ⋯ + λ_{n} = N. The number of parts (components) of λ of size i is denoted by m_{i}(λ).

Then, making again use of the notation for the multinomial coefficient introduced in Lemma 4, the expression for R_{Φ}(s_{1}, s_{2}, …, s_{l}) which we obtain in the way described above is

∑′ N_{Φ}(T_{0}^{(1)}, T_{1}^{(2)}, T_{2}^{(2)}, …, T_{n}^{(l)}) ∏_{j=2}^{l} \binom{m}{m_{1}(λ^{(j)}), m_{2}(λ^{(j)}), …, m_{n}(λ^{(j)})},  (11.2)

where ∑ ′ is taken over all integer partitions λ^{(2)}, λ^{(3)}, …, λ^{(l)} satisfying λ^{(2)} ⊢ s_{2}, λ^{(3)} ⊢ s_{3}, …, λ^{(l)} ⊢ s_{l}, over all types T_{0}^{(1)} with rk(T_{0}^{(1)}) = s_{1}, and over all types T_{i}^{(j)} with rk(T_{i}^{(j)}) = λ_{i}^{(j)}, i = 1, 2, …, n, j = 2, 3, …, l.

By way of example, using this formula and the values of the decomposition numbers N_{E_{8}}(…) given in Appendix A.7 (and a computer), we obtain that the number R_{E_{8}}(4, 2, 1, 1) of all chains π_{1} ≤ π_{2} ≤ π_{3} in NC^{m}(E_{8}), where π_{1} is of rank 4, π_{2} is of rank 6, and π_{3} is of rank 7, is given by

\frac{75m^{3} (8055m − 1141)}{2}

(which, by the independence (2.2) of decomposition numbers from the order of the types, is also equal to R_{E_{8}}(4, 1, 2, 1) and R_{E_{8}}(4, 1, 1, 2)), while the number R_{E_{8}}(2, 4, 1, 1) of all chains π_{1} ≤ π_{2} ≤ π_{3} in NC^{m}(E_{8}), where π_{1} is of rank 2, π_{2} is of rank 6, and π_{3} is of rank 7, is given by

\frac{75m^{3} (73125m^{3} − 58950m^{2} + 15635m − 2154)}{8}

(which is also equal to R_{E_{8}}(2, 1, 4, 1) and R_{E_{8}}(2, 1, 1, 4)).

Acknowledgements

The authors thank the anonymous referee for a very careful reading of the original manuscript.

Appendix A. The decomposition numbers for the exceptional types

A.1. The decomposition numbers for type I_{2}(a) [27, Sec. 13]. We have N_{I_{2}(a)}(I_{2}(a)) = 1, N_{I_{2}(a)}(A_{1}, A_{1}) = a, N_{I_{2}(a)}(A_{1}) = a, N_{I_{2}(a)}(∅) = 1, all other numbers N_{I_{2}(a)}(T_{1}, T_{2}, …, T_{d}) being zero.

A.2. The decomposition numbers for type H_{3} [27, Sec. 14]. We have N_{H_{3}}(H_{3}) = 1, N_{H_{3}}(A_{1}^{2}, A_{1}) = 5, N_{H_{3}}(A_{2}, A_{1}) = 5, N_{H_{3}}(I_{2}(5), A_{1}) = 5, N_{H_{3}}(A_{1}, A_{1}, A_{1}) = 50, plus the assignments implied by (2.2) and (2.3), all other numbers N_{H_{3}}(T_{1}, T_{2}, …, T_{d}) being zero.

A.3. The decomposition numbers for type H_{4} [27, Sec. 15]. We have N_{H_{4}}(H_{4}) = 1, N_{H_{4}}(A_{1} ∗ A_{2}, A_{1}) = 15, N_{H_{4}}(A_{3}, A_{1}) = 15, N_{H_{4}}(H_{3}, A_{1}) = 15, N_{H_{4}}(A_{1} ∗ I_{2}(5), A_{1}) = 15, N_{H_{4}}(A_{1}^{2}, A_{1}^{2}) = 30, N_{H_{4}}(A_{1}^{2}, A_{2}) = 30, N_{H_{4}}(A_{1}^{2}, I_{2}(5)) = 15, N_{H_{4}}(A_{2}, A_{2}) = 5, N_{H_{4}}(A_{2}, I_{2}(5)) = 15, N_{H_{4}}(I_{2}(5), I_{2}(5)) = 3, N_{H_{4}}(A_{1}^{2}, A_{1}, A_{1}) = 225, N_{H_{4}}(A_{2}, A_{1}, A_{1}) = 150, N_{H_{4}}(I_{2}(5), A_{1}, A_{1}) = 90, N_{H_{4}}(A_{1}, A_{1}, A_{1}, A_{1}) = 1350, plus the assignments implied by (2.2) and (2.3), all other numbers N_{H_{4}}(T_{1}, T_{2}, …, T_{d}) being zero.

A.4. The decomposition numbers for type F_{4} [27, Sec. 16]. We have N_{F_{4}}(F_{4}) = 1, N_{F_{4}}(A_{1} ∗ A_{2}, A_{1}) = 12, N_{F_{4}}(B_{3}, A_{1}) = 12, N_{F_{4}}(A_{1}^{2}, A_{1}^{2}) = 12, N_{F_{4}}(A_{1}^{2}, B_{2}) = 12, N_{F_{4}}(A_{2}, A_{2}) = 16, N_{F_{4}}(B_{2}, B_{2}) = 3, N_{F_{4}}(A_{1}^{2}, A_{1}, A_{1}) = 72, N_{F_{4}}(A_{2}, A_{1}, A_{1}) = 48, N_{F_{4}}(B_{2}, A_{1}, A_{1}) = 36, N_{F_{4}}(A_{1}, A_{1}, A_{1}, A_{1}) = 432, plus the assignments implied by (2.2) and (2.3), all other numbers N_{F_{4}}(T_{1}, T_{2}, …, T_{d}) being zero.

A.5. The decomposition numbers for type E_{6} [27, Sec. 17]. We have N_{E_{6}}(E_{6}) = 1, N_{E_{6}}(A_{1} ∗ A_{2}^{2}, A_{1}) = 6, N_{E_{6}}(A_{1} ∗ A_{4}, A_{1}) = 12, N_{E_{6}}(A_{5}, A_{1}) = 6, N_{E_{6}}(D_{5}, A_{1}) = 12, N_{E_{6}}(A_{1}^{2} ∗ A_{2}, A_{2}) = 36, N_{E_{6}}(A_{2}^{2}, A_{2}) = 8, N_{E_{6}}(A_{1} ∗ A_{3}, A_{2}) = 24, N_{E_{6}}(A_{4}, A_{2}) = 24, N_{E_{6}}(D_{4}, A_{2}) = 4, N_{E_{6}}(A_{1}^{2} ∗ A_{2}, A_{1}^{2}) = 18, N_{E_{6}}(A_{1} ∗ A_{3}, A_{1}^{2}) = 36, N_{E_{6}}(A_{4}, A_{1}^{2}) = 36, N_{E_{6}}(D_{4}, A_{1}^{2}) = 18, N_{E_{6}}(A_{1}^{3}, A_{1}^{3}) = 12, N_{E_{6}}(A_{1} ∗ A_{2}, A_{1}^{3}) = 24, N_{E_{6}}(A_{1} ∗ A_{2}, A_{1} ∗ A_{2}) = 48, N_{E_{6}}(A_{3}, A_{1}^{3}) = 36, N_{E_{6}}(A_{3}, A_{1} ∗ A_{2}) = 72, N_{E_{6}}(A_{3}, A_{3}) = 27, N_{E_{6}}(A_{1}^{2} ∗ A_{2}, A_{1}, A_{1}) = 144, N_{E_{6}}(A_{2}^{2}, A_{1}, A_{1}) = 24, N_{E_{6}}(A_{1}∗A_{3}, A_{1}, A_{1}) = 144, N_{E_{6}}(A_{4}, A_{1}, A_{1}) = 144, N_{E_{6}}(D_{4}, A_{1}, A_{1}) = 48, N_{E_{6}}(A_{1}^{3}, A_{1}^{2}, A_{1}) = 180, N_{E_{6}}(A_{1}^{3}, A_{2}, A_{1}) = 168, N_{E_{6}}(A_{1} ∗ A_{2}, A_{1}^{2}, A_{1}) = 360, N_{E_{6}}(A_{1} ∗ A_{2}, A_{2}, A_{1}) = 336, N_{E_{6}}(A_{3}, A_{1}^{2}, A_{1}) = 378, N_{E_{6}}(A_{3}, A_{2}, A_{1}) = 180, N_{E_{6}}(A_{1}^{2}, A_{1}^{2}, A_{1}^{2}) = 432, N_{E_{6}}(A_{2}, A_{1}^{2}, A_{1}^{2}) = 504, N_{E_{6}}(A_{2}, A_{2}, A_{1}^{2}) = 288, N_{E_{6}}(A_{2}, A_{2}, A_{2}) = 160, N_{E_{6}}(A_{1}^{2}, A_{1}^{2}, A_{1}, A_{1}) = 2376, N_{E_{6}}(A_{2}, A_{1}^{2}, A_{1}, A_{1}) = 1872, N_{E_{6}}(A_{2}, A_{2}, A_{1}, A_{1}) = 1056, N_{E_{6}}(A_{1}^{3}, A_{1}, A_{1}, A_{1}) = 864, N_{E_{6}}(A_{1} ∗ A_{2}, A_{1}, A_{1}, A_{1}) = 1728, N_{E_{6}}(A_{3}, A_{1}, A_{1}, A_{1}) = 1296, N_{E_{6}}(A_{1}^{2}, A_{1}, A_{1}, A_{1}, A_{1}) = 10368, N_{E_{6}}(A_{2}, A_{1}, A_{1}, A_{1}, A_{1}) = 6912, N_{E_{6}}(A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 41472, plus the assignments implied by (2.2) and (2.3), all other numbers N_{E_{6}}(T_{1}, T_{2}, …, T_{d}) being zero.

A.6. The decomposition numbers for type E_{7} [28, Sec. 6]. We have N_{E_{7}}(E_{7}) = 1, N_{E_{7}}(E_{6}, A_{1}) = 9, N_{E_{7}}(D_{6}, A_{1}) = 9, N_{E_{7}}(A_{6}, A_{1}) = 9, N_{E_{7}}(A_{1} ∗ D_{5}, A_{1}) = 9, N_{E_{7}}(A_{1}∗A_{5}, A_{1}) = 9, N_{E_{7}}(A_{2}∗D_{4}, A_{1}) = 0, N_{E_{7}}(A_{2}∗A_{4}, A_{1}) = 9, N_{E_{7}}(A_{1}^{2}∗D_{4}, A_{1}) = 0, N_{E_{7}}(A_{1}^{2} ∗A_{4}, A_{1}) = 0, N_{E_{7}}(A_{3}^{2}, A_{1}) = 0, N_{E_{7}}(A_{1} ∗A_{2} ∗A_{3}, A_{1}) = 9, N_{E_{7}}(A_{1}^{3} ∗A_{3}, A_{1}) = 0, N_{E_{7}}(A_{2}^{3}, A_{1}) = 0, N_{E_{7}}(A_{1}^{2} ∗ A_{2}^{2}, A_{1}) = 0, N_{E_{7}}(A_{1}^{4} ∗ A_{2}, A_{1}) = 0, N_{E_{7}}(A_{1}^{6}, A_{1}) = 0, N_{E_{7}}(D_{5}, A_{2}) = 18, N_{E_{7}}(A_{5}, A_{2}) = 30, N_{E_{7}}(A_{1} ∗ A_{4}, A_{2}) = 54, N_{E_{7}}(A_{1} ∗ D_{4}, A_{2}) = 9, N_{E_{7}}(A_{2} ∗ A_{3}, A_{2}) = 36, N_{E_{7}}(A_{1}^{2} ∗ A_{3}, A_{2}) = 36, N_{E_{7}}(A_{1} ∗ A_{2}^{2}, A_{2}) = 36, N_{E_{7}}(A_{1}^{3} ∗ A_{2}, A_{2}) = 12, N_{E_{7}}(A_{1}^{5}, A_{2}) = 0, N_{E_{7}}(D_{5}, A_{1}^{2}) = 54, N_{E_{7}}(A_{5}, A_{1}^{2}) = 63, N_{E_{7}}(A_{1} ∗ D_{4}, A_{1}^{2}) = 27, N_{E_{7}}(A_{1} ∗ A_{4}, A_{1}^{2}) = 81, N_{E_{7}}(A_{2} ∗ A_{3}, A_{1}^{2}) = 27, N_{E_{7}}(A_{1}^{2} ∗ A_{3}, A_{1}^{2}) = 27, N_{E_{7}}(A_{1} ∗ A_{2}^{2}, A_{1}^{2}) = 27, N_{E_{7}}(A_{1}^{3} ∗ A_{2}, A_{1}^{2}) = 9, N_{E_{7}}(A_{1}^{5}, A_{1}^{2}) = 0, N_{E_{7}}(D_{5}, A_{1}, A_{1}) = 162, N_{E_{7}}(A_{5}, A_{1}, A_{1}) = 216, N_{E_{7}}(A_{1} ∗ D_{4}, A_{1}, A_{1}) = 81, N_{E_{7}}(A_{1} ∗ A_{4}, A_{1}, A_{1}) = 324, N_{E_{7}}(A_{2} ∗ A_{3}, A_{1}, A_{1}) = 162, N_{E_{7}}(A_{1}^{2} ∗ A_{3}, A_{1}, A_{1}) = 162, N_{E_{7}}(A_{1} ∗ A_{2}^{2}, A_{1}, A_{1}) = 162, N_{E_{7}}(A_{1}^{3} ∗ A_{2}, A_{1}, A_{1}) = 54, N_{E_{7}}(A_{1}^{5}, A_{1}, A_{1}) = 0, N_{E_{7}}(D_{4}, A_{3}) = 9, N_{E_{7}}(A_{4}, A_{3}) = 54, N_{E_{7}}(A_{1} ∗ A_{3}, A_{3}) = 135, N_{E_{7}}(A_{2}^{2}, A_{3}) = 54, N_{E_{7}}(A_{1}^{2} ∗ A_{2}, A_{3}) = 162, N_{E_{7}}(A_{1}^{4}, A_{3}) = 27, N_{E_{7}}(D_{4}, A_{1}∗A_{2}) = 45, N_{E_{7}}(A_{4}, A_{1}∗A_{2}) = 162, N_{E_{7}}(A_{1}∗A_{3}, A_{1}∗A_{2}) = 243, N_{E_{7}}(A_{2}^{2}, A_{1}∗ A_{2}) = 54, N_{E_{7}}(A_{1}^{2} ∗ A_{2}, A_{1} ∗ A_{2}) = 162, N_{E_{7}}(A_{1}^{4}, A_{1} ∗ A_{2}) = 27, N_{E_{7}}(D_{4}, A_{1}^{3}) = 30, N_{E_{7}}(A_{4}, A_{1}^{3}) = 99, N_{E_{7}}(A_{1} ∗ A_{3}, A_{1}^{3}) = 126, N_{E_{7}}(A_{2}^{2}, A_{1}^{3}) = 18, N_{E_{7}}(A_{1}^{2} ∗ A_{2}, A_{1}^{3}) = 54, N_{E_{7}}(A_{1}^{4}, A_{1}^{3}) = 9, N_{E_{7}}(D_{4}, A_{2}, A_{1}) = 81, N_{E_{7}}(A_{4}, A_{2}, A_{1}) = 378, N_{E_{7}}(A_{1} ∗ A_{3}, A_{2}, A_{1}) = 783, N_{E_{7}}(A_{2}^{2}, A_{2}, A_{1}) = 270, N_{E_{7}}(A_{1}^{2} ∗ A_{2}, A_{2}, A_{1}) = 810, N_{E_{7}}(A_{1}^{4}, A_{2}, A_{1}) = 135, N_{E_{7}}(D_{4}, A_{1}^{2}, A_{1}) = 243, N_{E_{7}}(A_{4}, A_{1}^{2}, A_{1}) = 891, N_{E_{7}}(A_{1} ∗ A_{3}, A_{1}^{2}, A_{1}) = 1377, N_{E_{7}}(A_{2}^{2}, A_{1}^{2}, A_{1}) = 324, N_{E_{7}}(A_{1}^{2} ∗ A_{2}, A_{1}^{2}, A_{1}) = 972, N_{E_{7}}(A_{1}^{4}, A_{1}^{2}, A_{1}) = 162, N_{E_{7}}(D_{4}, A_{1}, A_{1}, A_{1}) = 729, N_{E_{7}}(A_{4}, A_{1}, A_{1}, A_{1}) = 2916, N_{E_{7}}(A_{1} ∗ A_{3}, A_{1}, A_{1}, A_{1}) = 5103, N_{E_{7}}(A_{2}^{2}, A_{1}, A_{1}, A_{1}) = 1458, N_{E_{7}}(A_{1}^{2} ∗ A_{2}, A_{1}, A_{1}, A_{1}) = 4374, N_{E_{7}}(A_{1}^{4}, A_{1}, A_{1}, A_{1}) = 729, N_{E_{7}}(A_{3}, A_{3}, A_{1}) = 486, N_{E_{7}}(A_{3}, A_{1} ∗ A_{2}, A_{1}) = 1458, N_{E_{7}}(A_{3}, A_{1}^{3}, A_{1}) = 891, N_{E_{7}}(A_{1} ∗ A_{2}, A_{1} ∗ A_{2}, A_{1}) = 2430, N_{E_{7}}(A_{1}∗A_{2}, A_{1}^{3}, A_{1}) = 1215, N_{E_{7}}(A_{1}^{3}, A_{1}^{3}, A_{1}) = 540, N_{E_{7}}(A_{3}, A_{2}, A_{2}) = 432, N_{E_{7}}(A_{1} ∗ A_{2}, A_{2}, A_{2}) = 1188, N_{E_{7}}(A_{1}^{3}, A_{2}, A_{2}) = 711, N_{E_{7}}(A_{3}, A_{2}, A_{1}^{2}) = 1053, N_{E_{7}}(A_{1}∗A_{2}, A_{2}, A_{1}^{2}) = 2349, N_{E_{7}}(A_{1}^{3}, A_{2}, A_{1}^{2}) = 1323, N_{E_{7}}(A_{3}, A_{1}^{2}, A_{1}^{2}) = 2430, N_{E_{7}}(A_{1}∗ A_{2}, A_{1}^{2}, A_{1}^{2}) = 3402, N_{E_{7}}(A_{1}^{3}, A_{1}^{2}, A_{1}^{2}) = 1539, N_{E_{7}}(A_{3}, A_{2}, A_{1}, A_{1}) = 3402, N_{E_{7}}(A_{1} ∗ A_{2}, A_{2}, A_{1}, A_{1}) = 8262, N_{E_{7}}(A_{1}^{3}, A_{2}, A_{1}, A_{1}) = 4779, N_{E_{7}}(A_{3}, A_{1}^{2}, A_{1}, A_{1}) = 8019, N_{E_{7}}(A_{1} ∗ A_{2}, A_{1}^{2}, A_{1}, A_{1}) = 13851, N_{E_{7}}(A_{1}^{3}, A_{1}^{2}, A_{1}, A_{1}) = 7047, N_{E_{7}}(A_{3}, A_{1}, A_{1}, A_{1}, A_{1}) = 26244, N_{E_{7}}(A_{1} ∗ A_{2}, A_{1}, A_{1}, A_{1}, A_{1}) = 52488, N_{E_{7}}(A_{1}^{3}, A_{1}, A_{1}, A_{1}, A_{1}) = 28431, N_{E_{7}}(A_{2}, A_{2}, A_{2}, A_{1}) = 2916, N_{E_{7}}(A_{2}, A_{2}, A_{1}^{2}, A_{1}) = 6561, N_{E_{7}}(A_{2}, A_{1}^{2}, A_{1}^{2}, A_{1}) = 13122, N_{E_{7}}(A_{1}^{2}, A_{1}^{2}, A_{1}^{2}, A_{1}) = 19683, N_{E_{7}}(A_{2}, A_{2}, A_{1}, A_{1}, A_{1}) = 21870, N_{E_{7}}(A_{2}, A_{1}^{2}, A_{1}, A_{1}, A_{1}) = 45927, N_{E_{7}}(A_{1}^{2}, A_{1}^{2}, A_{1}, A_{1}, A_{1}) = 78732, N_{E_{7}}(A_{2}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 157464, N_{E_{7}}(A_{1}^{2}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 295245, N_{E_{7}}(A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 1062882, plus the assignments implied by (2.2) and (2.3), all other numbers N_{E_{7}}(T_{1}, T_{2}, …, T_{d}) being zero.

A.7. The decomposition numbers for type E_{8} [28, Sec. 7]. We have N_{E_{8}}(E_{8}) = 1, N_{E_{8}}(E_{7}, A_{1}) = 15, N_{E_{8}}(D_{7}, A_{1}) = 15, N_{E_{8}}(A_{7}, A_{1}) = 15, N_{E_{8}}(A_{1} ∗ E_{6}, A_{1}) = 15, N_{E_{8}}(A_{1}∗D_{6}, A_{1}) = 0, N_{E_{8}}(A_{1}∗A_{6}, A_{1}) = 15, N_{E_{8}}(A_{2}∗D_{5}, A_{1}) = 15, N_{E_{8}}(A_{2}∗A_{5}, A_{1}) = 0, N_{E_{8}}(A_{1}^{2}∗D_{5}, A_{1}) = 0, N_{E_{8}}(A_{1}^{2}∗A_{5}, A_{1}) = 0, N_{E_{8}}(A_{3}∗D_{4}, A_{1}) = 0, N_{E_{8}}(A_{3}∗A_{4}, A_{1}) = 15, N_{E_{8}}(A_{1}∗A_{2}∗D_{4}, A_{1}) = 0, N_{E_{8}}(A_{1}∗A_{2}∗A_{4}, A_{1}) = 15, N_{E_{8}}(A_{1}^{3}∗D_{4}, A_{1}) = 0, N_{E_{8}}(A_{1}^{3}∗ A_{4}, A_{1}) = 0, N_{E_{8}}(A_{1} ∗ A_{3}^{2}, A_{1}) = 0, N_{E_{8}}(A_{2}^{2} ∗ A_{3}, A_{1}) = 0, N_{E_{8}}(A_{1}^{2} ∗ A_{2} ∗ A_{3}, A_{1}) = 0, N_{E_{8}}(A_{1}^{4} ∗A_{3}, A_{1}) = 0, N_{E_{8}}(A_{1} ∗A_{2}^{3}, A_{1}) = 0, N_{E_{8}}(A_{1}^{3} ∗A_{2}^{2}, A_{1}) = 0, N_{E_{8}}(A_{1}^{5} ∗A_{2}, A_{1}) = 0, N_{E_{8}}(A_{1}^{7}, A_{1}) = 0, N_{E_{8}}(E_{6}, A_{2}) = 20, N_{E_{8}}(D_{6}, A_{2}) = 15, N_{E_{8}}(A_{6}, A_{2}) = 60, N_{E_{8}}(A_{1} ∗ D_{5}, A_{2}) = 60, N_{E_{8}}(A_{1} ∗ A_{5}, A_{2}) = 60, N_{E_{8}}(A_{2} ∗ D_{4}, A_{2}) = 20, N_{E_{8}}(A_{2} ∗ A_{4}, A_{2}) = 90, N_{E_{8}}(A_{3}^{2}, A_{2}) = 45, N_{E_{8}}(A_{1}^{2}∗D_{4}, A_{2}) = 0, N_{E_{8}}(A_{1}^{2}∗A_{4}, A_{2}) = 90, N_{E_{8}}(A_{1}∗A_{2}∗A_{3}, A_{2}) = 90, N_{E_{8}}(A_{1}^{3}∗A_{3}, A_{2}) = 0, N_{E_{8}}(A_{2}^{3}, A_{2}) = 0, N_{E_{8}}(A_{1}^{2}∗A_{2}^{2}, A_{2}) = 45, N_{E_{8}}(A_{1}^{4}∗A_{2}, A_{2}) = 0, N_{E_{8}}(A_{1}^{6}, A_{2}) = 0, N_{E_{8}}(E_{6}, A_{1}^{2}) = 45, N_{E_{8}}(D_{6}, A_{1}^{2}) = 90, N_{E_{8}}(A_{6}, A_{1}^{2}) = 135, N_{E_{8}}(A_{1} ∗ D_{5}, A_{1}^{2}) = 135, N_{E_{8}}(A_{1} ∗ A_{5}, A_{1}^{2}) = 135, N_{E_{8}}(A_{2} ∗ D_{4}, A_{1}^{2}) = 45, N_{E_{8}}(A_{2} ∗ A_{4}, A_{1}^{2}) = 90, N_{E_{8}}(A_{3}^{2}, A_{1}^{2}) = 45, N_{E_{8}}(A_{1}^{2} ∗ D_{4}, A_{1}^{2}) = 0, N_{E_{8}}(A_{1}^{2} ∗ A_{4}, A_{1}^{2}) = 90, N_{E_{8}}(A_{1} ∗ A_{2} ∗ A_{3}, A_{1}^{2}) = 90, N_{E_{8}}(A_{1}^{3} ∗ A_{3}, A_{1}^{2}) = 0, N_{E_{8}}(A_{2}^{3}, A_{1}^{2}) = 0, N_{E_{8}}(A_{1}^{2} ∗ A_{2}^{2}, A_{1}^{2}) = 45, N_{E_{8}}(A_{1}^{4} ∗ A_{2}, A_{1}^{2}) = 0, N_{E_{8}}(A_{1}^{6}, A_{1}^{2}) = 0, N_{E_{8}}(E_{6}, A_{1}, A_{1}) = 150, N_{E_{8}}(D_{6}, A_{1}, A_{1}) = 225, N_{E_{8}}(A_{6}, A_{1}, A_{1}) = 450, N_{E_{8}}(A_{1} ∗ D_{5}, A_{1}, A_{1}) = 450, N_{E_{8}}(A_{1} ∗ A_{5}, A_{1}, A_{1}) = 450, N_{E_{8}}(A_{2} ∗ D_{4}, A_{1}, A_{1}) = 150, N_{E_{8}}(A_{2} ∗ A_{4}, A_{1}, A_{1}) = 450, N_{E_{8}}(A_{3}^{2}, A_{1}, A_{1}) = 225, N_{E_{8}}(A_{1}^{2} ∗ D_{4}, A_{1}, A_{1}) = 0, N_{E_{8}}(A_{1}^{2} ∗ A_{4}, A_{1}, A_{1}) = 450, N_{E_{8}}(A_{1} ∗ A_{2} ∗ A_{3}, A_{1}, A_{1}) = 450, N_{E_{8}}(A_{1}^{3} ∗ A_{3}, A_{1}, A_{1}) = 0, N_{E_{8}}(A_{2}^{3}, A_{1}, A_{1}) = 0, N_{E_{8}}(A_{1}^{2} ∗ A_{2}^{2}, A_{1}, A_{1}) = 225, N_{E_{8}}(A_{1}^{4} ∗ A_{2}, A_{1}, A_{1}) = 0, N_{E_{8}}(A_{1}^{6}, A_{1}, A_{1}) = 0, N_{E_{8}}(D_{5}, A_{3}) = 45, N_{E_{8}}(A_{5}, A_{3}) = 90, N_{E_{8}}(A_{1} ∗ A_{4}, A_{3}) = 315, N_{E_{8}}(A_{1} ∗ D_{4}, A_{3}) = 45, N_{E_{8}}(A_{2} ∗ A_{3}, A_{3}) = 270, N_{E_{8}}(A_{1}^{2} ∗ A_{3}, A_{3}) = 270, N_{E_{8}}(A_{1} ∗ A_{2}^{2}, A_{3}) = 225, N_{E_{8}}(A_{1}^{3} ∗ A_{2}, A_{3}) = 225, N_{E_{8}}(A_{1}^{5}, A_{3}) = 0, N_{E_{8}}(D_{5}, A_{1} ∗ A_{2}) = 195, N_{E_{8}}(A_{5}, A_{1} ∗ A_{2}) = 390, N_{E_{8}}(A_{1} ∗ A_{4}, A_{1} ∗ A_{2}) = 690, N_{E_{8}}(A_{1} ∗ D_{4}, A_{1} ∗ A_{2}) = 195, N_{E_{8}}(A_{2} ∗ A_{3}, A_{1} ∗ A_{2}) = 495, N_{E_{8}}(A_{1}^{2} ∗ A_{3}, A_{1} ∗ A_{2}) = 495, N_{E_{8}}(A_{1} ∗ A_{2}^{2}, A_{1} ∗ A_{2}) = 300, N_{E_{8}}(A_{1}^{3} ∗ A_{2}, A_{1} ∗ A_{2}) = 300, N_{E_{8}}(A_{1}^{5}, A_{1} ∗ A_{2}) = 0, N_{E_{8}}(D_{5}, A_{1}^{3}) = 150, N_{E_{8}}(A_{5}, A_{1}^{3}) = 300, N_{E_{8}}(A_{1} ∗ A_{4}, A_{1}^{3}) = 375, N_{E_{8}}(A_{1} ∗ D_{4}, A_{1}^{3}) = 150, N_{E_{8}}(A_{2} ∗ A_{3}, A_{1}^{3}) = 225, N_{E_{8}}(A_{1}^{2} ∗ A_{3}, A_{1}^{3}) = 225, N_{E_{8}}(A_{1} ∗ A_{2}^{2}, A_{1}^{3}) = 75, N_{E_{8}}(A_{1}^{3} ∗ A_{2}, A_{1}^{3}) = 75, N_{E_{8}}(A_{1}^{5}, A_{1}^{3}) = 0, N_{E_{8}}(D_{5}, A_{2}, A_{1}) = 375, N_{E_{8}}(A_{5}, A_{2}, A_{1}) = 750, N_{E_{8}}(A_{1}∗A_{4}, A_{2}, A_{1}) = 1950, N_{E_{8}}(A_{1} ∗ D_{4}, A_{2}, A_{1}) = 375, N_{E_{8}}(A_{2} ∗ A_{3}, A_{2}, A_{1}) = 1575, N_{E_{8}}(A_{1}^{2} ∗ A_{3}, A_{2}, A_{1}) = 1575, N_{E_{8}}(A_{1} ∗ A_{2}^{2}, A_{2}, A_{1}) = 1200, N_{E_{8}}(A_{1}^{3} ∗ A_{2}, A_{2}, A_{1}) = 1200, N_{E_{8}}(A_{1}^{5}, A_{2}, A_{1}) = 0, N_{E_{8}}(D_{5}, A_{1}^{2}, A_{1}) = 1125, N_{E_{8}}(A_{5}, A_{1}^{2}, A_{1}) = 2250, N_{E_{8}}(A_{1} ∗ A_{4}, A_{1}^{2}, A_{1}) = 3825, N_{E_{8}}(A_{1} ∗D_{4}, A_{1}^{2}, A_{1}) = 1125, N_{E_{8}}(A_{2} ∗A_{3}, A_{1}^{2}, A_{1}) = 2700, N_{E_{8}}(A_{1}^{2} ∗A_{3}, A_{1}^{2}, A_{1}) = 2700, N_{E_{8}}(A_{1} ∗ A_{2}^{2}, A_{1}^{2}, A_{1}) = 1575, N_{E_{8}}(A_{1}^{3} ∗ A_{2}, A_{1}^{2}, A_{1}) = 1575, N_{E_{8}}(A_{1}^{5}, A_{1}^{2}, A_{1}) = 0, N_{E_{8}}(D_{5}, A_{1}, A_{1}, A_{1}) = 3375, N_{E_{8}}(A_{5}, A_{1}, A_{1}, A_{1}) = 6750, N_{E_{8}}(A_{1} ∗ A_{4}, A_{1}, A_{1}, A_{1}) = 13500, N_{E_{8}}(A_{1} ∗ D_{4}, A_{1}, A_{1}, A_{1}) = 3375, N_{E_{8}}(A_{2} ∗ A_{3}, A_{1}, A_{1}, A_{1}) = 10125, N_{E_{8}}(A_{1}^{2} ∗ A_{3}, A_{1}, A_{1}, A_{1}) = 10125, N_{E_{8}}(A_{1} ∗ A_{2}^{2}, A_{1}, A_{1}, A_{1}) = 6750, N_{E_{8}}(A_{1}^{3} ∗ A_{2}, A_{1}, A_{1}, A_{1}) = 6750, N_{E_{8}}(A_{1}^{5}, A_{1}, A_{1}, A_{1}) = 0, N_{E_{8}}(D_{4}, D_{4}) = 5, N_{E_{8}}(D_{4}, A_{4}) = 15, N_{E_{8}}(A_{4}, A_{4}) = 138, N_{E_{8}}(D_{4}, A_{1} ∗ A_{3}) = 105, N_{E_{8}}(A_{4}, A_{1} ∗ A_{3}) = 390, N_{E_{8}}(A_{1} ∗ A_{3}, A_{1} ∗ A_{3}) = 1155, N_{E_{8}}(D_{4}, A_{2}^{2}) = 35, N_{E_{8}}(A_{4}, A_{2}^{2}) = 180, N_{E_{8}}(A_{1} ∗ A_{3}, A_{2}^{2}) = 360, N_{E_{8}}(A_{2}^{2}, A_{2}^{2}) = 95, N_{E_{8}}(D_{4}, A_{1}^{2} ∗ A_{2}) = 135, N_{E_{8}}(A_{4}, A_{1}^{2} ∗ A_{2}) = 630, N_{E_{8}}(A_{1} ∗ A_{3}, A_{1}^{2} ∗ A_{2}) = 1035, N_{E_{8}}(A_{2}^{2}, A_{1}^{2} ∗ A_{2}) = 270, N_{E_{8}}(A_{1}^{2} ∗ A_{2}, A_{1}^{2} ∗ A_{2}) = 495, N_{E_{8}}(D_{4}, A_{1}^{4}) = 30, N_{E_{8}}(A_{4}, A_{1}^{4}) = 165, N_{E_{8}}(A_{1} ∗A_{3}, A_{1}^{4}) = 255, N_{E_{8}}(A_{2}^{2}, A_{1}^{4}) = 60, N_{E_{8}}(A_{1}^{2} ∗A_{2}, A_{1}^{4}) = 135, N_{E_{8}}(A_{1}^{4}, A_{1}^{4}) = 30, N_{E_{8}}(D_{4}, A_{3}, A_{1}) = 225, N_{E_{8}}(A_{4}, A_{3}, A_{1}) = 1215, N_{E_{8}}(A_{1} ∗ A_{3}, A_{3}, A_{1}) = 4050, N_{E_{8}}(A_{2}^{2}, A_{3}, A_{1}) = 1575, N_{E_{8}}(A_{1}^{2} ∗A_{2}, A_{3}, A_{1}) = 5400, N_{E_{8}}(A_{1}^{4}, A_{3}, A_{1}) = 1350, N_{E_{8}}(D_{4}, A_{1} ∗ A_{2}, A_{1}) = 975, N_{E_{8}}(A_{4}, A_{1} ∗ A_{2}, A_{1}) = 4590, N_{E_{8}}(A_{1} ∗ A_{3}, A_{1} ∗ A_{2}, A_{1}) = 10800, N_{E_{8}}(A_{2}^{2}, A_{1} ∗ A_{2}, A_{1}) = 3450, N_{E_{8}}(A_{1}^{2} ∗ A_{2}, A_{1} ∗ A_{2}, A_{1}) = 9900, N_{E_{8}}(A_{1}^{4}, A_{1} ∗ A_{2}, A_{1}) = 2475, N_{E_{8}}(D_{4}, A_{1}^{3}, A_{1}) = 750, N_{E_{8}}(A_{4}, A_{1}^{3}, A_{1}) = 3375, N_{E_{8}}(A_{1} ∗ A_{3}, A_{1}^{3}, A_{1}) = 6750, N_{E_{8}}(A_{2}^{2}, A_{1}^{3}, A_{1}) = 1875, N_{E_{8}}(A_{1}^{2} ∗A_{2}, A_{1}^{3}, A_{1}) = 4500, N_{E_{8}}(A_{1}^{4}, A_{1}^{3}, A_{1}) = 1125, N_{E_{8}}(D_{4}, A_{2}, A_{2}) = 175, N_{E_{8}}(A_{4}, A_{2}, A_{2}) = 1140, N_{E_{8}}(A_{1}∗A_{3}, A_{2}, A_{2}) = 3300, N_{E_{8}}(A_{2}^{2}, A_{2}, A_{2}) = 1300, N_{E_{8}}(A_{1}^{2} ∗ A_{2}, A_{2}, A_{2}) = 4500, N_{E_{8}}(A_{1}^{4}, A_{2}, A_{2}) = 1125, N_{E_{8}}(D_{4}, A_{2}, A_{1}^{2}) = 675, N_{E_{8}}(A_{4}, A_{2}, A_{1}^{2}) = 3015, N_{E_{8}}(A_{1}∗A_{3}, A_{2}, A_{1}^{2}) = 8550, N_{E_{8}}(A_{2}^{2}, A_{2}, A_{1}^{2}) = 2925, N_{E_{8}}(A_{1}^{2}∗ A_{2}, A_{2}, A_{1}^{2}) = 9000, N_{E_{8}}(A_{1}^{4}, A_{2}, A_{1}^{2}) = 2250, N_{E_{8}}(D_{4}, A_{1}^{2}, A_{1}^{2}) = 1800, N_{E_{8}}(A_{4}, A_{1}^{2}, A_{1}^{2}) = 8640, N_{E_{8}}(A_{1} ∗ A_{3}, A_{1}^{2}, A_{1}^{2}) = 17550, N_{E_{8}}(A_{2}^{2}, A_{1}^{2}, A_{1}^{2}) = 5175, N_{E_{8}}(A_{1}^{2} ∗ A_{2}, A_{1}^{2}, A_{1}^{2}) = 13500, N_{E_{8}}(A_{1}^{4}, A_{1}^{2}, A_{1}^{2}) = 3375, N_{E_{8}}(D_{4}, A_{2}, A_{1}, A_{1}) = 1875, N_{E_{8}}(A_{4}, A_{2}, A_{1}, A_{1}) = 9450, N_{E_{8}}(A_{1} ∗ A_{3}, A_{2}, A_{1}, A_{1}) = 27000, N_{E_{8}}(A_{2}^{2}, A_{2}, A_{1}, A_{1}) = 9750, N_{E_{8}}(A_{1}^{2} ∗ A_{2}, A_{2}, A_{1}, A_{1}) = 31500, N_{E_{8}}(A_{1}^{4}, A_{2}, A_{1}, A_{1}) = 7875, N_{E_{8}}(D_{4}, A_{1}^{2}, A_{1}, A_{1}) = 5625, N_{E_{8}}(A_{4}, A_{1}^{2}, A_{1}, A_{1}) = 26325, N_{E_{8}}(A_{1} ∗ A_{3}, A_{1}^{2}, A_{1}, A_{1}) = 60750, N_{E_{8}}(A_{2}^{2}, A_{1}^{2}, A_{1}, A_{1}) = 19125, N_{E_{8}}(A_{1}^{2} ∗ A_{2}, A_{1}^{2}, A_{1}, A_{1}) = 54000, N_{E_{8}}(A_{1}^{4}, A_{1}^{2}, A_{1}, A_{1}) = 13500, N_{E_{8}}(D_{4}, A_{1}, A_{1}, A_{1}, A_{1}) = 16875, N_{E_{8}}(A_{4}, A_{1}, A_{1}, A_{1}, A_{1}) = 81000, N_{E_{8}}(A_{1} ∗ A_{3}, A_{1}, A_{1}, A_{1}, A_{1}) = 202500, N_{E_{8}}(A_{2}^{2}, A_{1}, A_{1}, A_{1}, A_{1}) = 67500, N_{E_{8}}(A_{1}^{2} ∗ A_{2}, A_{1}, A_{1}, A_{1}, A_{1}) = 202500, N_{E_{8}}(A_{1}^{4}, A_{1}, A_{1}, A_{1}, A_{1}) = 50625, N_{E_{8}}(A_{3}, A_{3}, A_{2}) = 1350, N_{E_{8}}(A_{3}, A_{1} ∗ A_{2}, A_{2}) = 5175, N_{E_{8}}(A_{3}, A_{1}^{3}, A_{2}) = 3825, N_{E_{8}}(A_{1} ∗ A_{2}, A_{1} ∗ A_{2}, A_{2}) = 15000, N_{E_{8}}(A_{1} ∗ A_{2}, A_{1}^{3}, A_{2}) = 9825, N_{E_{8}}(A_{1}^{3}, A_{1}^{3}, A_{2}) = 6000, N_{E_{8}}(A_{3}, A_{3}, A_{1}^{2}) = 4050, N_{E_{8}}(A_{3}, A_{1} ∗ A_{2}, A_{1}^{2}) = 13500, N_{E_{8}}(A_{3}, A_{1}^{3}, A_{1}^{2}) = 9450, N_{E_{8}}(A_{1} ∗ A_{2}, A_{1} ∗ A_{2}, A_{1}^{2}) = 30825, N_{E_{8}}(A_{1} ∗ A_{2}, A_{1}^{3}, A_{1}^{2}) = 17325, N_{E_{8}}(A_{1}^{3}, A_{1}^{3}, A_{1}^{2}) = 7875, N_{E_{8}}(A_{3}, A_{3}, A_{1}, A_{1}) = 12150, N_{E_{8}}(A_{3}, A_{1}∗A_{2}, A_{1}, A_{1}) = 42525, N_{E_{8}}(A_{3}, A_{1}^{3}, A_{1}, A_{1}) = 30375, N_{E_{8}}(A_{1} ∗ A_{2}, A_{1} ∗ A_{2}, A_{1}, A_{1}) = 106650, N_{E_{8}}(A_{1} ∗ A_{2}, A_{1}^{3}, A_{1}, A_{1}) = 64125, N_{E_{8}}(A_{1}^{3}, A_{1}^{3}, A_{1}, A_{1}) = 33750, N_{E_{8}}(A_{3}, A_{2}, A_{2}, A_{1}) = 10575, N_{E_{8}}(A_{3}, A_{2}, A_{1}^{2}, A_{1}) = 29700, N_{E_{8}}(A_{3}, A_{1}^{2}, A_{1}^{2}, A_{1}) = 76950, N_{E_{8}}(A_{1} ∗ A_{2}, A_{2}, A_{2}, A_{1}) = 35700, N_{E_{8}}(A_{1}∗A_{2}, A_{2}, A_{1}^{2}, A_{1}) = 84825, N_{E_{8}}(A_{1}∗A_{2}, A_{1}^{2}, A_{1}^{2}, A_{1}) = 171450, N_{E_{8}}(A_{1}^{3}, A_{2}, A_{2}, A_{1}) = 25125, N_{E_{8}}(A_{1}^{3}, A_{2}, A_{1}^{2}, A_{1}) = 55125, N_{E_{8}}(A_{1}^{3}, A_{1}^{2}, A_{1}^{2}, A_{1}) = 94500, N_{E_{8}}(A_{3}, A_{2}, A_{1}, A_{1}, A_{1}) = 91125, N_{E_{8}}(A_{3}, A_{1}^{2}, A_{1}, A_{1}, A_{1}) = 243000, N_{E_{8}}(A_{1} ∗ A_{2}, A_{2}, A_{1}, A_{1}, A_{1}) = 276750, N_{E_{8}}(A_{1}∗A_{2}, A_{1}^{2}, A_{1}, A_{1}, A_{1}) = 597375, N_{E_{8}}(A_{1}^{3}, A_{2}, A_{1}, A_{1}, A_{1}) = 185625, N_{E_{8}}(A_{1}^{3}, A_{1}^{2}, A_{1}, A_{1}, A_{1}) = 354375, N_{E_{8}}(A_{3}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 759375, N_{E_{8}}(A_{1} ∗ A_{2}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 2025000, N_{E_{8}}(A_{1}^{3}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 1265625, N_{E_{8}}(A_{2}, A_{2}, A_{2}, A_{2}) = 9350, N_{E_{8}}(A_{2}, A_{2}, A_{2}, A_{1}^{2}) = 24975, N_{E_{8}}(A_{2}, A_{2}, A_{1}^{2}, A_{1}^{2}) = 64350, N_{E_{8}}(A_{2}, A_{1}^{2}, A_{1}^{2}, A_{1}^{2}) = 143100, N_{E_{8}}(A_{1}^{2}, A_{1}^{2}, A_{1}^{2}, A_{1}^{2}) = 261225, N_{E_{8}}(A_{2}, A_{2}, A_{2}, A_{1}, A_{1}) = 78000, N_{E_{8}}(A_{2}, A_{2}, A_{1}^{2}, A_{1}, A_{1}) = 203625, N_{E_{8}}(A_{2}, A_{1}^{2}, A_{1}^{2}, A_{1}, A_{1}) = 479250, N_{E_{8}}(A_{1}^{2}, A_{1}^{2}, A_{1}^{2}, A_{1}, A_{1}) = 951750, N_{E_{8}}(A_{2}, A_{2}, A_{1}, A_{1}, A_{1}, A_{1}) = 641250, N_{E_{8}}(A_{2}, A_{1}^{2}, A_{1}, A_{1}, A_{1}, A_{1}) = 1569375, N_{E_{8}}(A_{1}^{2}, A_{1}^{2}, A_{1}, A_{1}, A_{1}, A_{1}) = 3341250, N_{E_{8}}(A_{2}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 5062500, N_{E_{8}}(A_{1}^{2}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 11390625, N_{E_{8}}(A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}, A_{1}) = 37968750, plus the assignments implied by (2.2) and (2.3), all other numbers N_{E_{8}}(T_{1}, T_{2}, …, T_{d}) being zero.

References

[1] D. Armstrong, Generalized noncrossing partitions and combinatorics of Coxeter groups, Ph.D. thesis, Cornell University, 2006; to appear in Mem. Amer. Math. Soc.; arχiv:math.CO/0611106.

[2] C. A. Athanasiadis, On noncrossing and nonnesting partitions for classical reflection groups, Electron. J. Combin. 5 (1998), Article #R42, 16 pp.

[3] C. A. Athanasiadis, On some enumerative aspects of generalized associahedra, European J. Combin. 28 (2007), 1208–1215.

[4] C. A. Athanasiadis and V. Reiner, Noncrossing partitions for the group D_{n}, SIAM J. Discrete Math. 18 (2004), 397–417.

[5] C. A. Athanasiadis, T. Brady and C. Watt, Shellability of noncrossing partition lattices, Proc. Amer. Math. Soc. 135 (2007), 939–949.

[6] C. A. Athanasiadis and E. Tzanaki, On the enumeration of positive cells in generalized cluster complexes and Catalan hyperplane arrangements, J. Algebraic Combin. 23 (2006), 355–375.

[7] C. A. Athanasiadis and E. Tzanaki, Shellability and higher Cohen-Macaulay connectivity of generalized cluster complexes, Israel J. Math. 167 (2008), 177–191.

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

[9] D. Bessis and R. Corran, Non-crossing partitions of type (e, e, r), Adv. Math. 202 (2006), 1–49.

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

[11] A. Björner and F. Brenti, Combinatorics of Coxeter groups, Springer–Verlag, New York, 2005.

[12] M. Bóna, M. Bousquet, G. Labelle and P. Leroux, Enumeration of m-ary cacti, Adv. Appl. Math. 24 (2000), 22–56.

[13] M. Bousquet, C. Chauve and G. Schaeffer, Énumération et génération aléatoire de cactus m-aires, Proceedings of the Colloque LaCIM 2000 (Montréal), P. Leroux (ed.), Publications du LaCIM, vol. 27, 2000, pp. 89–100.

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

[15] T. Brady and C. Watt, K(π, 1)’s for Artin groups of finite type, Geom. Dedicata 94 (2002), 225–250.

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

[17] F. Chapoton, Enumerative properties of generalized associahedra, Séminaire Lotharingien Combin. 51 (2004), Article B51b, 16 pp.

[18] P. Edelman, Chain enumeration and noncrossing partitions, Discrete Math. 31 (1981), 171–180.

[19] S. Fomin and N. Reading, Generalized cluster complexes and Coxeter combinatorics, Int. Math. Res. Notices 44 (2005), 2709–2757.

[20] S. Fomin and N. Reading, Root systems and generalized associahedra, in: Geometric combinatorics, E. Miller, V. Reiner and B. Sturmfels (eds.), IAS/Park City Math. Ser., vol. 13, Amer. Math. Soc., Providence, R.I., 2007, pp. 63–131.

[21] S. Fomin and A. Zelevinsky, Y -systems and generalized associahedra, Ann. of Math. (2) 158 (2003), 977–1018.

[22] I. J. Good, Generalizations to several variables of Lagrange’s expansion, with applications to stochastic processes, Proc. Cambridge Philos. Soc. 56 (1960), 367–380.

[23] I. P. Goulden and D. M. Jackson, The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group, Europ. J. Combin. 13 (1992), 357–365.

[24] J. E. Humphreys, Reflection groups and Coxeter groups, Cambridge University Press, Cambridge, 1990.

[25] J. Irving, Combinatorial constructions for transitive factorizations in the symmetric group, Ph.D. thesis, University of Waterloo, 2004.

[26] C. Krattenthaler, Operator methods and Lagrange inversion: A unified approach to Lagrange formulas, Trans. Amer. Math. Soc. 305 (1988), 431–465.

[27] C. Krattenthaler, The F -triangle of the generalised cluster complex, in: Topics in Discrete Mathematics, dedicated to Jarik Nešetřil on the occasion of his 60th birthday, M. Klazar, J. Kratochvil, M. Loebl, J. Matoušek, R. Thomas and P. Valtr (eds.), Springer–Verlag, Berlin, New York, 2006, pp. 93–126.

[28] C. Krattenthaler, The M-triangle of generalised non-crossing partitions for the types E_{7} and E_{8}, Séminaire Lotharingien Combin. 54 (2006), Article B54l, 34 pages.

[29] C. Krattenthaler, Non-crossing partitions on an annulus, in preparation.

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

[31] N. Reading, Chains in the noncrossing partition lattice, SIAM J. Discrete Math. 22 (2008), 875– 886.

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

[33] R. P. Stanley, Enumerative Combinatorics, vol. 1, Wadsworth & Brooks/Cole, Pacific Grove, California, 1986; reprinted by Cambridge University Press, Cambridge, 1998.

[34] R. P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999.

[35] J. R. Stembridge, coxeter, Maple package for working with root systems and finite Coxeter groups;

    available at http://www.math.lsa.umich.edu/~jrs.

[36] E. Tzanaki, Combinatorics of generalized cluster complexes and hyperplane arrangements, Ph.D. thesis, University of Crete, Iraklio, 2007.

[37] E. Tzanaki, Polygon dissections and some generalizations of cluster complexes, J. Combin. Theory Ser. A 113 (2006), 1189–1198.

[38] E. Tzanaki, Faces of generalized cluster complexes and noncrossing partitions, SIAM J. Discrete Math. 22 (2008), 15–30.

Fakultät für Mathematik, Universität Wien, Nordbergstraße 15, A-1090 Vienna,

Austria. WWW: http://www.mat.univie.ac.at/~kratt.

School of Mathematical Sciences, Queen Mary & Westfield College, University of London, Mile End Road, London E1 4NS, United Kingdom.

WWW: http://www.maths.qmw.ac.uk/~twm/.