Enumeration of Flats of the Extended Catalan and Shi Arrangements with Species

Norihiro Nakashima Department of Mathematics Nagoya Institute of Technology Nagoya, Aichi 466-8555 Japan

                nakashima@nitech.ac.jp

Shuhei Tsujie Department of Mathematics Hokkaido University of Education Asahikawa, Hokkaido 070-8621 Japan

            tsujie.shuhei@a.hokkyodai.ac.jp

Abstract

The number of flats of a hyperplane arrangement is considered as a generalization of the Bell number and the Stirling number of the second kind. Robert Gill gave the exponential generating function of the number of flats of the extended Catalan arrangements, using species. In this article, we introduce the species of flats of the extended Catalan and Shi arrangements and they are given by iterated substitution of species of sets and lists. Moreover, we enumerate the flats of these arrangements in terms of infinite matrices.

1 Introduction

A hyperplane arrangement is a finite collection of affine subspaces of codimension 1 in an affine space over an arbitrary field 𝕂. In spite of its simple definition, arrangements are investigated in a variety of ways, such as topological, algebrogeometric, and combinatorial aspects. A standard reference for hyperplane arrangements is the text written by Orlik and Terao [10].

Given an arrangement A, let L(A) denote the set of nonempty intersections of hyperplanes in A. Note that the ambient space is a member of L(A) since it is regarded as the intersection over the empty set. We call an element of L(A) a flat. Define a partial order on L(A) by the reverse inclusion, that is, X ≤ Y ⇔ X ⊇ Y for X, Y ∈ L(A). We call L(A) the intersection poset of A. This poset plays an important role in the theory of hyperplane arrangements. For each nonnegative integer k, let

L_{k}(A) := { X ∈ L(A) | dim X = k } .

When A is central, that is, the intersection of all hyperplanes in A is nonempty, the poset L(A) is a geometric lattice.

A set partition of a finite set V is a collection π = {B_{1}, …, B_{k}} of nonempty subsets B_{i} ⊆ V such that B_{i} ∩ B_{j} = ∅ for i ≠ j and ⋃_{i=1}^{k} B_{i} = V. Each B_{i} is called a block of π. Let π and π′ be set partitions of V. Define a partial order π ≤ π′ if each block of π is a subset of some block of π′. We also say that π refines π′ if π ≤ π′. Then the collection of the set partitions of V forms a lattice.

For a positive integer n, let [n] be the set {1, …, n} and [0] the empty set. The number of set partitions of [n] is called the Bell number, denoted by B(n), where B(0) = 1. The number of set partitions of [n] into k blocks is called the Stirling number of the second kind, denoted by S(n, k), where S(0, 0) = 1.

Let x_{1}, …, x_{n} denote coordinates of ℝ^{n} and B_{n} the n-dimensional braid arrangement (also known as the Weyl arrangement of type A_{n−1}), which consists of hyperplanes {x_{i} − x_{j} = 0} in ℝ^{n} for 1 ≤ i < j ≤ n. It is well known that there exists an isomorphism from L(B_{n}) to the lattice of set partitions of [n] which sends a k-dimensional flat to a set partition into k blocks. In other words, |L(B_{n})| = B(n) and |L_{k}(B_{n})| = S(n, k). The numbers of flats and k-dimensional flats of an arrangement is considered to be generalizations of the Bell numbers and the Stirling numbers.

Define the extended Catalan arrangement C_{n}^{m} and the extended Shi arrangement S_{n}^{m} in ℝ^{n} as follows.

C_{n}^{m} := { {x_{i} − x_{j} = a} | 1 ≤ i < j ≤ n, −m ≤ a ≤ m } , (m ≥ 0),
S_{n}^{m} := { {x_{i} − x_{j} = a} | 1 ≤ i < j ≤ n, 1 − m ≤ a ≤ m } , (m ≥ 1).

Note that C_{n}^{0} = B_{n} for every nonnegative integer n and L_{0}(C_{n}^{m}) = L_{0}(S_{n}^{m}) = ∅ unless n = 0. Gill [5] investigated the intersection posets of the extended Catalan arrangements. First Gill determined the number of maximal elements of the poset L(C_{n}^{m}) as follows.

Theorem 1 (Gill [5, Theorem 1]). Let m be a nonnegative integer. Then

∑_{n=1}^{∞} |L_{1}(C_{n}^{m})| \frac{x^{n}}{n!} = \frac{e^{x} − 1}{1 − m(e^{x} − 1)}.

In Gill’s work [5], the use of species, which were initiated by Joyal [7], is a noteworthy point. Standard references for species are the texts written by Bergeron, Labelle, and Leroux [1, 2]. Let 𝔹 denote the category of finite sets and bijections and 𝔼 the category of finite sets and maps. A species, or 𝔹-species, is a functor F: 𝔹 → 𝔼. The value of a species F at a finite set V is denoted by F[V]. Moreover, we write simply F[n] instead of F[[n]]. The symbol F(x) is used for the exponential generating function

F(x) := ∑_{n=0}^{∞} |F[n]| \frac{x^{n}}{n!} .

Example 2. Let E denote the species of sets. Namely E[V] := {V }. Then we have |E[n]| = 1 for every n and thus E(x) = ∑_{n=0}^{∞} \frac{x^{n}}{n!} = e^{x}.

Example 3. Let L denote the species of lists. Namely

L[V] := { (v_{1}, …, v_{n}) | n = |V | and V = {v_{1}, …, v_{n}} } .

We have |L[n]| = n! for every n and hence L(x) = ∑_{n=0}^{∞} x^{n} = \frac{1}{1−x}.

Making use of species enables us to calculate generating functions systematically. Namely we can define operations for species such as sum, product, and so on. These operations are compatible with the corresponding operations for the generating functions. Hence we may say that species is a refinement of the exponential generating function.

Definition 4. For species F and G, we define the sum F + G by (F + G)[V] := F[V] ⊔ G[V], where ⊔ means the disjoint union.

Then we have (F + G)(x) = F(x) + G(x).

Definition 5. For every species F and a nonnegative integer k, define the species F_{k} by

F_{k}[V] := \begin{cases}F[V], & if |V | = k; \\ ∅, & otherwise. \end{cases}

Every species F has a canonical decomposition F = ∑_{k=0}^{∞} F_{k}. Furthermore, if we write F_{+} := ∑_{k=1}^{∞} F_{k}, then F_{+}[∅] = ∅ and F_{+}(x) = F(x) − F(0).

Example 6.

E_{+}(x) = e^{x} − 1, E_{k}(x) = \frac{x^{k}}{k!} , and L_{+}(x) = \frac{1}{1 − x} − 1 = \frac{x}{1 − x}.

In this article, we frequently use the operation F ∘ G of species, called substitution (or composition).

Definition 7. Let F and G be species with G[∅] = ∅. Define

(F ∘ G)[V] := ⨆_{π∈Π[V]} (F[π] × ∏_{B∈π} G[B]) ,

where Π denotes the species of set partitions.

Substitution of species corresponds to substitution of generating functions, that is, (F ∘ G)(x) = F(G(x)). It is a functional tool for computing the generating function and explains why the exponential function e^{x} sometimes appears in the generating function.

Example 8. By definition, the exponential generating function of the Bell numbers is given by Π(x). The species of set partitions Π coincides with the species E ∘ E_{+} (See Example 18 for details). Hence we have the following.

Π(x) = (E ∘ E_{+})(x) = exp (e^{x} − 1) .

Example 9. Given a species F, let F_{+}^{∘m} be the m-times iterated self-substitution of F_{+}. For the species L of lists, we have

L_{+}^{∘2}(x) = (L_{+} ∘ L_{+})(x) = \frac{\frac{x}{1−x}}{1 − \frac{x}{1−x}} = \frac{x}{1 − 2x}.

More generally, one can show easily that

L_{+}^{∘m}(x) = \frac{x}{1 − mx}.

The construction of the extended Catalan arrangement C_{n}^{m} is functorial in n. Namely, for every finite set V, we may construct the corresponding Catalan arrangement in the vector space ℝ^{V} = Map(V, ℝ) and hence there exist species LC^{m} and L_{k}C^{m} such that LC^{m}[n] = L(C_{n}^{m}) and L_{k}C^{m}[n] = L_{k}(C_{n}^{m}). Gill’s second theorem is as follows.

Theorem 10 (Gill [5, Theorem 2]). For every m ≥ 0, the equality LC^{m} = E ∘ L_{1}C^{m} holds. Moreover, the bivariate generating function of |L_{k}(C_{n}^{m})| is given by

∑_{n=0}^{∞} ∑_{k=0}^{n} |L_{k}(C_{n}^{m})| t^{k} \frac{x^{n}}{n!} = exp (t\frac{e^{x} − 1}{1 − m(e^{x} − 1)}) .

We write F = G if there exists a natural isomorphism between species F and G. In this paper, we will improve Gill’s results in terms of species as follows.

Theorem 11. Let m and k be nonnegative integers. Then

L_{k}C^{m} = E_{k} ∘ L_{+}^{∘m} ∘ E_{+} and LC^{m} = E ∘ L_{+}^{∘m} ∘ E_{+}.

This theorem together with Example 6, Example 8, and Example 9 leads to the following corollary, which is equivalent to the generating functions in Theorem 1 and Theorem 10.

Corollary 12.

L_{k}C^{m}(x) = ∑_{n=0}^{∞} |L_{k}(C_{n}^{m})| \frac{x^{n}}{n!} = \frac{1}{k!} (\frac{e^{x} − 1}{1 − m(e^{x} − 1)})^{k} ,

LC^{m}(x) = ∑_{n=0}^{∞} |L(C_{n}^{m})| \frac{x^{n}}{n!} = exp (\frac{e^{x} − 1}{1 − m(e^{x} − 1)}) .

We will also give an analog for the extended Shi arrangement S_{n}^{m}. However, the construction of S_{n}^{m} cannot be regarded as a functor on 𝔹 since the construction requires the linear order on the set [n]. For this reason we consider 𝕃-species, that is, a functor F: 𝕃 → 𝔼, where 𝕃 denotes the category of linearly ordered finite sets and order-preserving bijections. Note that every 𝔹-species can be considered as an 𝕃-species via the forgetful functor from 𝕃 to 𝔹.

Let LS^{m} and L_{k}S^{m} denote the 𝕃-species such that LS^{m}[n] = L(S_{n}^{m}) and L_{k}S^{m}[n] = L_{k}(S_{n}^{m}). The following is another main result of this article.

Theorem 13. Let m and k be nonnegative integers. Then

L_{k}S^{m} = E_{k} ∘ L_{+}^{∘m} and LS^{m} = E ∘ L_{+}^{∘m}.

Corollary 14.

L_{k}S^{m}(x) = ∑_{n=0}^{∞} |L_{k}(S_{n}^{m})| \frac{x^{n}}{n!} = \frac{1}{k!} (\frac{x}{1 − mx})^{k} ,

LS^{m}(x) = ∑_{n=0}^{∞} |L(S_{n}^{m})| \frac{x^{n}}{n!} = exp (\frac{x}{1 − mx}) .

Moreover, we will give explicit formulas for the numbers |L_{k}(S_{n}^{m})| and |L_{k}(C_{n}^{m})| of kdimensional flats of n-dimensional extended Catalan and extended Shi arrangements with infinite matrices. Let [a_{ij}] denote the infinite matrix whose entry in the i-th row and the j-th column is a_{ij}, where i and j run over all positive integers. Let

c := [c(j, i)] and S := [S(j, i)] ,

where c(j, i) denote the unsigned Stirling number of the first kind, that is, the number of ways to partition a j-element set into i cycles. Note that most of the tables, including Tables 5–6, consisting of such numbers are lower triangular. However, our infinite matrices c and S are transposed and hence upper triangular. Namely,

c = [\begin{matrix}1 & 1 & 2 & 6 & 24 & ⋯ \\ 0 & 1 & 3 & 11 & 50 & ⋯ \\ 0 & 0 & 1 & 6 & 35 & ⋯ \\ 0 & 0 & 0 & 1 & 10 & ⋯ \\ 0 & 0 & 0 & 0 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] , S = [\begin{matrix}1 & 1 & 1 & 1 & 1 & ⋯ \\ 0 & 1 & 3 & 7 & 15 & ⋯ \\ 0 & 0 & 1 & 6 & 25 & ⋯ \\ 0 & 0 & 0 & 1 & 10 & ⋯ \\ 0 & 0 & 0 & 0 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] .

Theorem 15.

[ |L_{i}(C_{j}^{m})| ] = (Sc)^{m}S and [ |L_{i}(S_{j}^{m})| ] = (Sc)^{m}.

From Theorem 15, we may also calculate the matrices recursively as follows.

\begin{matrix}C^{0} & ⟶^{c} & S^{1} & ⟶^{S} & C^{1} & ⟶^{c} & S^{2} & ⟶^{S} & C^{2} & ⟶^{c} & ⋯ \\ S & & Sc & & ScS & & ScSc & & ScScS \end{matrix}

The Lah number is the number of ways to partition an n-element set into k nonempty lists, which is equal to the cardinality of (E_{k} ∘ L_{+})[n] (See Example 18 for details). It is well known that the Lah number is given by the following formula.

Proposition 16 (See [11, p.44] for example). Let k and n be nonnegative integers. Then

|(E_{k} ∘ L_{+})[n]| = \frac{n!(n − 1)!}{k!(k − 1)!(n − k)!}.

Using the Lah numbers, we give an explicit formula for the number of flats of the extended Shi arrangement.

Theorem 17.

|L_{k}(S_{n}^{m})| = m^{n−k} \frac{n!(n − 1)!}{k!(k − 1)!(n − k)!}.

The organization of this paper is as follows.

In §2, we give some examples of substitutions of species. Also, we introduce tree notation for the species L_{+}^{∘m}. Although actually this notation is not required for the proofs of our main theorems, it helps us to recognize elements of L_{+}^{∘m}.

In §3, we review the theory of gain graphs developed by Zaslavsky. Since the extended Catalan and Shi arrangements are expressed by using gain graphs, the intersection posets of these arrangements can be represented by a kind of partitions of the vertices of the corresponding gain graphs. This guarantees that it suffices to know the 1-dimensional flats in order to know all flats, that is, LC^{m} = E ∘ L_{1}C^{m} and LS^{m} = E ∘ L_{1}S^{m}.

Finally in §4, we will give proofs of Theorem 11, Theorem 13, Theorem 15, and Theorem 17.

In §5, as an appendix we give numerical tables for the number of flats with ID numbers in the On-Line Encyclopedia of Integer Sequences (OEIS) [9].

Note that, throughout of this paper, we will construct several natural transformations. However, we will omit proofs of commutativity of diagrams for the natural transformations since they are obvious.

2 Substitution of species and tree notation

2.1 Examples

Let F and G be species with G[∅] = ∅. Recall the definition of the substitution F ∘ G.

(F ∘ G)[V] := ⨆_{π∈Π[V]} (F[π] × ∏_{B∈π} G[B]) ,

where Π denotes the species of set partitions.

The substitution F ∘ G has the external and internal structure. Namely, for each set partition π, we take an element of F[π], which is the external structure. For every block B of π, we choose an element of G[B], which is the internal structure. In the usual case, a constituent of the external structure is labeled with blocks of a partition and if we “substitute” the labels with internal structures, then we obtain an element of (F ∘ G)[V].

Example 18. Let G be a species such that if g ∈ G[B], g′ ∈ G[B′], and g = g′, then B = B′. We will see that the species E ∘ G may be considered as a species of set partitions consisting of G-structures. By definition,

(E ∘ G)[V] = ⨆_{π∈Π[V]} (E[π] × ∏_{B∈π} G[B]) = ⨆_{π∈Π[V]} ({π} × ∏_{B∈π} G[B]) .

For any set partition π = {B_{1}, …, B_{k}}, every element (π, (g_{B_{1}}, …, g_{B_{k}})) ∈ {π}×∏_{B∈π} G[B] can be identified with the set {g_{B_{1}}, …, g_{B_{k}}}. Then the set (E ∘ G)[V] is identified with

{ {g_{B_{1}}, …, g_{B_{k}}} | {B_{1}, …, B_{k}} ∈ Π[V], g_{B_{i}} ∈ G[B_{i}] } .

In particular, E ∘ E_{+} gives set partitions consisting of sets, that is, ordinary set partitions. Namely E ∘ E_{+} = Π. Therefore |(E_{k} ∘ E_{+})[n]| is the Stirling number of the second kind. For the same reason |(E_{k} ∘ L_{+})[n]| yields the Lah number.

We sometimes omit commas in sets, lists, and so on. For example, we write {123} instead of {1, 2, 3}.

1 2 3  2 4 3 1

Figure 1: (123) and (2431)

Example 19. Let G be as above. By the similar discussion, we may say that the species L∘G may be considered as a species of lists consisting of G-structures. Namely the set (L ∘ G)[V] can be identified naturally with

{ (g_{B_{1}}, ⋯, g_{B_{k}}) | {B_{1}, …, B_{k}} ∈ Π[V], g_{B_{i}} ∈ G[B_{i}] } .

The species L ∘ E_{+} is known as a species of set compositions (or ordered set partitions). The cardinality |(L ∘ E_{+})[n]| is called the ordered Bell number (or Fubini number). For instance |(L ∘ E_{+})[3]| = 13 since it consists of the following set compositions.

({123}), ({12}{3}), ({13}{2}), ({23}{1}), ({3}{12}), ({2}{13}), ({1}{23}),
({1}{2}{3}), ({1}{3}{2}), ({2}{1}{3}), ({2}{3}{1}), ({3}{1}{2}), ({3}{2}{1}).

Example 20. The species E_{1} of singletons behaves as the identity element with respect to substitution. Namely, E_{1} ∘ G = G and F ∘ E_{1} = F.

A lot of researchers have been studied iterated substitutions of species of sets and lists. For example, Motzkin [8] investigated several structures including, “sets of sets” E∘E_{+}, “sets of lists” E ∘ L_{+}, “lists of sets” L ∘ E_{+}, and “lists of lists” L ∘ L_{+}. Sloane and Wieder [12] call an element of (E ∘ L_{+} ∘ E_{+})[n] a hierarchical ordering (or society). Callan [3, Section 2] gave a bijection between lists of noncrossing sets and sets of lists E ∘ L_{+}. Hedmark [6, Subsection 5.2] introduced an α-colored partition lattice for a positive integer α and stated that it can be regarded as L_{+}^{∘α} ∘ E_{+}.

2.2 Tree notation for L_{+}^{∘m}

The species L_{+}^{∘m} can be considered as the species of “m-dimensional lists”. For example (((49)(5))((3)(71)(6))((82))) is an element of L_{+}^{∘3}[9]. However, it is difficult to understand the structure of this at first glance. Hence we introduce tree notation for L_{+}^{∘m}.

The idea is very simple. We just regard a list as an ordered rooted tree of height one with labeled leaves, where an ordered rooted tree means a rooted tree whose sibling sets are linearly ordered as lists. For example the lists (123) and (2413) are expressed as in Figure 1.

Then the species L_{+}^{∘m} can be regarded as a rooted tree of height m. For example,

(((49)(5))((3)(71)(6))((82))) ∈ L_{+}^{∘3}[9]

4 9 5 3 7 1 6 8 2  \begin{matrix}\{57\} \\ \{3\} \\ \{149\} \\ \{26\} \\ \{8\} \end{matrix}
Figure 2: Elements in L_{+}^{∘3}[9] and (L_{+}^{∘2} ∘ E_{+})[9]

is expressed as the left in Figure 2. We also can express elements of L_{+}^{∘m} ∘E_{+} by taking labels consisting of sets. For example

(({57}{3})({149}{26}{8})) ∈ (L_{+}^{∘2} ∘ E_{+})[9]

is as the right in Figure 2.

3 Gain graphs and the associated posets

3.1 Review of graphic arrangements

First we recall graphic arrangements and their intersection lattices. Let Γ = (V_{Γ}, E_{Γ}) be a simple graph on vertex set V_{Γ} = [n]. We can associate Γ with a hyperplane arrangement A_{Γ} in ℝ^{n}, called the graphic arrangement, consisting of hyperplanes defined by {x_{i} − x_{j} = 0} with {i, j} ∈ E_{Γ}, where x_{1}, …, x_{ℓ} denote coordinates of ℝ^{ℓ}.

It is well known that the intersection lattice L(A_{Γ}) can be represented by using set partitions as explained below. A connected partition of Γ is a set partition of V_{Γ} whose every block induces a connected subgraph of Γ. Let L(Γ) be the set of all connected partitions of Γ with the partial order defined by refinement. Namely, π ≤ π′ if each block of π′ is the union of some blocks of π. We call L(Γ) the lattice of connected partitions (or the lattice of contractions), which is naturally isomorphic to L(A_{Γ}).

Note that the braid arrangement B_{n} can be regarded as a graphic arrangement with the complete graph K_{n}. Since L(K_{n}) consists of all set partitions of [n], the number of flats of the braid arrangement is associated with the Bell number and the Stirling number of the second kind.

3.2 Integral gain graphs and affinographic arrangements

The extended Catalan and Shi arrangements are represented by using gain graphs. Gain graphs were introduced by Zaslavsky [14] for abstraction of linear independence of hyperplanes of the form {x_{i} − x_{j} = a} with a ∈ ℤ. Roughly speaking, a gain graph is a graph with labeled edges (i, j, a), which corresponds to the {x_{i} − x_{j} = a}. However, since {x_{i} − x_{j} = a} = {x_{j} − x_{i} = −a}, we must identify (i, j, a) with (j, i, −a). Here we give a formal definition of gain graphs which are required in this article. See the paper by Zaslavsky [14] for a general treatment.

Definition 21. An integral gain graph is a pair Γ = (V_{Γ}, E_{Γ}) satisfying the following conditions.

(i) V_{Γ} is a finite set.

(ii) E_{Γ} is a finite subset of { (u, v, a) ∈ V_{Γ} × V_{Γ} × ℤ | u ≠ v } divided by the equivalence relation ∼ generated by (u, v, a) ∼ (v, u, −a).

Let {u, v}_{a} denote the equivalence class containing (u, v, a). Then {u, v}_{a} = {v, u}_{−a}. Elements in V_{Γ} and E_{Γ} are called vertices and edges of the gain graph Γ.

Definition 22. Suppose that Γ is an integral gain graph on [n]. Define an affine arrangement A_{Γ} in ℝ^{n} by

A_{Γ} := { {x_{i} − x_{j} = a} | {i, j}_{a} ∈ E_{Γ} } .

We call A_{Γ} the affinographic arrangement of Γ.

Note that every simple graph is regarded as a gain graph by regarding {u, v} as {u, v}_{0}. So every graphic arrangement is considered to be an affinographic arrangement. Hence there is no confusion to use the same symbol A_{Γ} for the graphic and affinographic arrangements.

Definition 23. Let A be a finite subset of ℤ. For every positive integer n, define K_{n}^{A} as an integral gain graph on [n] with edges

E_{K_{n}^{A}} := { {i, j}_{a} | 1 ≤ i < j ≤ n, a ∈ A } .

We call K_{n}^{A} the complete gain graph with gain A.

For integers a, b with a ≤ b, let [a, b] := {a, a + 1, …, b} ⊆ ℤ.

Example 24. The extended Catalan arrangements and the extended Shi arrangements are obtained by

C_{n}^{m} = A_{K_{n}^{[−m,m]}} and S_{n}^{m} = A_{K_{n}^{[1−m,m]}}.

3.3 Poset of connected partitions

A height function on a finite set B is a map h: B → ℤ such that min(h(B)) = 0.

Let Γ be an integral gain graph. Consider a pair (B, h), where B ⊆ V_{Γ} and h is a height function on B. Define Γ[B, h] as the integral gain graph on B with edges

E_{Γ[B,h]} := { {u, v}_{a} ∈ E_{Γ} | u, v ∈ B, h(u) + a = h(v) }
= { {u, v}_{−h(u)+h(v)} ∈ E_{Γ} | u, v ∈ B } .

Let v_{1}, v_{2}, …, v_{r} be distinct vertices of an integral gain graph Γ. A path on the vertices v_{1}, …, v_{r} is a set of edges {v_{1}, v_{2}}_{a_{1}}, {v_{2}, v_{3}}_{a_{2}}, …, {v_{r−1}, v_{r}}_{a_{r−1}}. We say that Γ is connected if there exists a path joining any two distinct vertices. A connected partition of Γ is a collection π = {(B_{1}, h_{1}), …, (B_{k}, h_{k})} such that {B_{1}, …, B_{k}} is a set partition of V_{Γ} and each Γ[B_{i}, h_{i}] is connected. An element of π is called a block.

Let π and π′ be connected partitions. We say that π refines π′, denoted by π ≤ π′ if for any (B, h) ∈ π there exist (B′, h′) ∈ π′ and g ∈ ℤ such that B ⊆ B′ and h(v) = g + h′(v) for any v ∈ B. Let L(Γ) denote the set of all connected partitions, which forms a poset together with the refinement. Call L(Γ) the poset of connected partitions of Γ.

Note that when a simple graph Γ is viewed as a gain graph, connected partitions coincide with the usual connected partitions of the simple graph Γ. Therefore the poset of connected partitions of a gain graph is a generalization of the lattice of connected partitions of a simple graph. Remark 25. For a general gain graph with gain group G, we need notion of G-labeled set to define connected partitions. However, for integral gain graphs, we need only height functions, which were introduced by Corteel, Forge, and Ventos [4].

Theorem 26. Let Γ be an integral gain graph on [n].

(1) If (B, h) is a block of a connected partition of Γ with B = {i_{1}, …, i_{r}}, then

X_{(B,h)} := ⋂_{{i,j}_{a}∈E_{Γ[B,h]}}{x_{i} − x_{j} = a} = {x_{i_{1}} + h(i_{1}) = ⋯ = x_{i_{r}} + h(i_{r})}.

(2) The following map is an isomorphism of posets.

\begin{matrix}L(Γ) & ⟶ & L(A_{Γ}) \\ π & ⟼ & ⋂_{(B,h)∈π} X_{(B,h)}. \end{matrix}

(3) For any nonnegative integer k, the isomorphism in (2) induces a bijection between L_{k}(Γ) and L_{k}(A_{Γ}), where

L_{k}(Γ) := { π ∈ L(Γ) | |π| = k }

and |π| denotes the number of blocks of π.

Proof. (1) Recall E_{Γ[B,h]} = { {i, j}_{−h(i)+h(j)} ∈ E_{Γ} | i, j ∈ B }. The hyperplane corresponding to the edge {i, j}_{−h(i)+h(j)} is

{x_{i} − x_{j} = −h(i) + h(j)} = {x_{i} + h(i) = x_{j} + h(j)}.

Since Γ[B, h] is connected, the intersection coincides with the right hand side.

(2) This follows from theorems by Zaslavsky [15, Corollary 4.5(a)], [13, Lemma 3.1A and 3.1B].

(3) Obvious from (2).

3.4 Partitional decompositions

Let A be a finite subset of ℤ. The construction of the complete gain graph with gain A is considered to be an 𝕃-species. Namely, for each finite linearly ordered set V, we may construct the complete gain graph K_{V}^{A} on V with gain A. Hence, there exist 𝕃-species LK^{A} and L_{k}K^{A} such that LK^{A}[n] = L(K_{n}^{A}) and L_{k}K^{A}[n] = L_{k}(K_{n}^{A}). In particular, if −A = A, then the 𝕃-species LK^{A} and L_{k}K^{A} may be considered to be species.

Lemma 27. Let A be a finite subset of ℤ. Then

L_{k}K^{A} = E_{k} ∘ L_{1}K^{A} and LK^{A} = E ∘ L_{1}K^{A}

In particular,

L_{k}C^{m} = L_{k}K^{[−m,m]} = E_{k} ∘ L_{1}K^{[−m.m]},  LC^{m} = LK^{[−m,m]} = E ∘ L_{1}K^{[−m.m]},

L_{k}S^{m} = L_{k}K^{[1−m,m]} = E_{k} ∘ L_{1}K^{[1−m.m]}, LS^{m} = LK^{[1−m,m]} = E ∘ L_{1}K^{[1−m.m]}.

Proof. Let (B, h) be a block of a connected partition of K_{n}^{A}. Then the block (B, h) may be regarded as an element of L_{1}K^{A}[B]. This identification leads to the natural isomorphisms L_{k}K^{A} = E_{k} ∘ L_{1}K^{A} and LK^{A} = E ∘ L_{1}K^{A}. The rest follows by Theorem 26.

4 Proofs

4.1 Proof of Theorem 11

In order to describe LC^{m}, it is sufficient to determine the species L_{1}K^{[−m,m]} by Lemma 27. Given a finite set V, an element of L_{1}K^{[−m,m]}[V] = L_{1}(K_{V}^{[−m,m]}) is identified with a height function h on V such that K_{V}^{[−m,m]}[V, h] is connected. In order to characterize such functions, define gap(h) and level(h) for each height functions as follows.

Suppose that h(V) = {a_{1}, …, a_{k}} with 0 = a_{1} < a_{2} < ⋯ < a_{k}. Then we define

level(h) := (h^{−1}(a_{1}), h^{−1}(a_{2}), …, h^{−1}(a_{k})) ,
gap(h) := (a_{2} − a_{1}, a_{3} − a_{2}, …, a_{k} − a_{k−1}).

Let max(gap(h)) denote the maximum of entries of gap(h).

Lemma 28. Let V be a finite set and h a height function on V. For every nonnegative integer m, K_{V}^{[−m,m]}[V, h] is connected if and only if max(gap(h)) ≤ m.

Proof. Let level(h) = (B_{1}, …, B_{k}) and gap(h) = (α_{1}, …, α_{k−1}). Suppose that K_{V}^{[−m,m]}[V, h] is connected. Then for every i ∈ {1, …, k − 1} there exists an edge {u, v}_{a}, where u ∈ B_{1}∪⋯∪B_{i} and v ∈ B_{i+1}∪⋯∪B_{k}. Then α_{i} ≤ h(v)−h(u) = a ≤ m. Thus max(gap(h)) ≤ m.

\begin{matrix}\{57\} \\ \{3\} \\ \{149\} \\ \{26\} \\ \{8\} \\ α \\ 1 \\ 2 \\ 1 \\ 1 \\ h \\ 0 \\ 1 \\ 3 \\ 4 \\ 5 \end{matrix}

Figure 3: An example of the correspondence for the extended Catalan arrangement

To prove the converse, suppose that max(gap(h)) ≤ m. Suppose that u, v ∈ B_{i} for some i ∈ {1, …, k}. Then {u, v}_{0} is an edge of K_{V}^{[−m,m]}[V, h]. Now, let i ∈ {1, …, k − 1} and take vertices u ∈ B_{i} and v ∈ B_{i+1}. Then h(v) − h(u) = α_{i} ≤ max(gap(h)) ≤ m. Therefore {u, v}_{α_{i}} is an edge of K_{V}^{[−m,m]}[V, h]. Hence we can deduce K_{V}^{[−m,m]}[V, h] is connected.

Lemma 29. Let m be a nonnegative integer. Then L_{1}K^{[−m,m]} = L_{+}^{∘m} ∘ E_{+}.

Proof. We proceed by induction on m. First suppose that m = 0. Let V be a finite set. Then K_{V}^{{0}}[V, h] is connected if and only if h is identically 0 by Lemma 28. Hence the identification (V, 0) with V yields the natural isomorphism L_{1}K^{{0}} = E_{+}.

Now suppose that m ≥ 1. We will prove L_{1}K^{[−m,m]} = L_{+} ∘ L_{1}K^{[−(m−1),m−1]}. Define a natural transformation η: L_{1}K^{[−m,m]} → L_{+} ∘ L_{1}K^{[−(m−1),m−1]} as follows. Let V be a finite set and h be a height function on V such that K_{V}^{[−m,m]}[V, h] is connected. Let level(h) = (B_{1}, …, B_{k}) and gap(h) = (α_{1}, …, α_{k−1}) and suppose that { j | α_{j} = m } = {j_{1}, …, j_{s−1}} with j_{1} < ⋯ < j_{s−1}. For each i ∈ {1, …, s} define C_{i} := B_{j_{i−1}+1} ∪ B_{j_{i−1}+2} ∪ ⋯ ∪ B_{j_{i}}, where j_{0} := 0 and j_{s} := k. Define the height function h_{i} on C_{i} by h_{i}(v) := h(v) − min(h(C_{i})) (v ∈ C_{i}). Then max(gap(h_{i})) ≤ m − 1 and hence (C_{i}, h_{i}) is an element of L_{1}K^{[−(m−1),m−1]}[C_{i}]. Therefore we define η_{V} by η_{V} ((V, h)) := ((C_{1}, h_{1}), …, (C_{s}, h_{s})).

We will construct another natural transformation ξ: L_{+} ∘ L_{1}K^{[−(m−1),m−1]} → L_{1}K^{[−m,m]} as follows. Let V be a finite set and take an element ((C_{1}, h_{1}), …, (C_{s}, h_{s})) from L_{+} ∘ L_{1}K^{[−(m−1),m−1]}. Then {C_{1}, …, C_{s}} is a set partition of V and (C_{i}, h_{i}) ∈ L_{1}K^{[−(m−1),m−1]}[C_{i}] for every i ∈ {1, …, s}. By Lemma 28 max(gap(h_{i})) ≤ m − 1. Let h be the height function on V defined by h(v) := h_{i}(v)+∑_{j=1}^{i−1} (m + max(h_{j}(C_{j}))) for v ∈ C_{i}. Since max(gap(h)) ≤ m, (V, h) ∈ L_{1}K^{[−m,m]}[V]. Thus we may define ξ_{V} by ξ_{V} (((C_{1}, h_{1}), …, (C_{s}, h_{s}))) := (V, h).

It is obvious that η and ξ are inverse to each other. Therefore L_{1}K^{[−m,m]} = L_{+} ∘ L_{1}K^{[−(m−1),m−1]}. By induction hypothesis, we can conclude that L_{1}K^{[−m,m]} = L_{+}^{∘m} ∘ E_{+}.

Proof of Theorem 11. Use Lemma 27 and Lemma 29.

Example 30. Consider ((B_{1}B_{2})(B_{3}B_{4}B_{5})) = (({57}{3})({149}{26}{8})) ∈ (L_{+}^{∘2} ∘ E_{+})[9] (See Figure 3). We construct the corresponding flat of the extended Catalan arrangement C_{9}^{2}. First, for each i, let α_{i} denote the height of the minimal tree containing leaves B_{i} and B_{i+1}. In this case we have the integer composition α = (α_{1}, α_{2}, α_{3}, α_{4}) = (1, 2, 1, 1). By taking the partial sum ∑_{j=1}^{i−1} α_{j} for each i, we obtain the sequence of heights (0, 1, 3, 4, 5). The height function h : [9] → ℤ is obtained by the following table.

\begin{matrix}v & 5 & 7 & 3 & 1 & 4 & 9 & 2 & 6 & 8 \\ h(v) & 0 & 0 & 1 & 3 & 3 & 3 & 4 & 4 & 5 \end{matrix}

The corresponding flat in C_{9}^{2} is

{x_{5} = x_{7} = x_{3} + 1 = x_{1} + 3 = x_{4} + 3 = x_{9} + 3 = x_{2} + 4 = x_{6} + 4 = x_{8} + 5}.

4.2 Proof of Theorem 13

We assume that all species in this subsection are 𝕃-species and V denotes a finite linearly ordered set. The symbols min(B) and max(B) stand for the minimum and the maximum elements of a subset B ⊆ V.

Lemma 31. Let V be a finite linearly ordered set and h a height function on V. Let level(h) = (B_{1}, …, B_{k}) and gap(h) = (α_{1}, …, α_{k−1}). For every positive integer m, the graph K_{V}^{[1−m,m]}[V, h] is connected if and only if max(gap(h)) ≤ m holds and α_{i} = m implies min(B_{i}) < max(B_{i+1}).

Proof. Suppose that K_{V}^{[1−m,m]}[V, h] is connected. Then K_{V}^{[−m,m]}[V, h] is also connected since K_{V}^{[1−m,m]}[V, h] is a subgraph of K_{V}^{[−m,m]}[V, h]. Therefore max(gap(h)) ≤ m by Lemma 28. Suppose that α_{i} = m. Then there exist vertices u ∈ B_{i} and v ∈ B_{i+1} such that {u, v}_{m} is an edge of K_{V}^{[1−m,m]}[V, h] since K_{V}^{[1−m,m]}[V, h] is connected, which implies u < v in V. Thus it follows that min(B_{i}) < max(B_{i+1}). The proof of the converse is similar to the proof of Lemma 28.

Lemma 32. Let m be a positive integer. Then L_{1}K^{[1−m,m]} = L_{+}^{∘m}.

Proof. We proceed by induction on m. Suppose that m = 1. We will construct a natural transformation η: L_{1}K^{[0,1]} → L_{+}. Let V be a finite linearly ordered set and h a height function on V such that K_{V}^{[0,1]}[V, h] is connected. Let level(h) = (B_{1}, …, B_{k}). Make the list β_{i} = (v_{i1}, …, v_{ij_{i}}) such that B_{i} = {v_{i1}, …, v_{ij_{i}}} with v_{i1} > ⋯ > v_{ij_{i}}. Define η_{V} as the list obtaining by concatenating β_{1}, …, β_{k}.

Next we will construct another natural transformation ξ: L_{+} → L_{1}K^{[0,1]}. Every list in L_{+}[V] can be expressed as (v_{11}, …, v_{1j_{1}}, v_{21}, …, v_{2j_{2}}, …, v_{k1}, …, v_{kj_{k}}), where v_{i1} > ⋯ > v_{ij_{i}} and v_{ij_{i}} < v_{i+1 1} for each i ∈ {1, … k − 1}. Let B_{i} := {v_{i1}, …, v_{ij_{i}}} and define the height function on V by h(v) := i − 1 for v ∈ B_{i}. Then max(gap(h)) ≤ 1 and min(B_{i}) = v_{ij_{i}} < v_{i+1 1} = max(B_{i+1}). Therefore by Lemma 31 (V, h) ∈ L_{1}K^{[0,1]}[V]. Thus we may define ξ_{V} by the correspondence above. One can show that η and ξ are inverse to each other and hence L_{1}K^{[0,1]} = L_{+}.

495371682α 12321231α′ 11220230h 012466811 11

Figure 4: An example of the correspondence for the extended Shi arrangement

Assume that m ≥ 2 and we will prove that L_{1}K^{[1−m,m]} = L_{+} ∘ L_{1}K^{[2−m,m−1]}. We will construct a natural transformation η: L_{1}K^{[1−m,m]} → L_{+} ∘ L_{1}K^{[2−m,m−1]}. Let h be a height function on a finite linearly ordered set V such that K_{V}^{[1−m,m]}[V, h] is connected. Let level(h) = (B_{1}, …, B_{k}) and gap(h) = (α_{1}, …, α_{k−1}). Suppose that { j | α_{j} = m } ∪ { j | α_{j} = m − 1, min(B_{j}) > max(B_{j+1}) } = {j_{1}, …, j_{s−1}} with j_{1} < ⋯ < j_{s−1}. For each i ∈ {1, …, s}, put C_{i} := B_{j_{i−1}+1} ∪ ⋯ ∪ B_{j_{i}}, where j_{0} = 0 and j_{s} := k. Define the height function h_{i} on C_{i} by h_{i}(v) := h(v) − min(h(C_{i})) for v ∈ C_{i}. Then max(gap(h_{i})) ≤ m − 1 and level(h_{i}) = (B_{j_{i−1}+1}, …, B_{j_{i}}). Moreover for i ∈ {j_{i−1} + 1, …, j_{i}}, if α_{i} = m − 1, then min(B_{i}) < max(B_{i+1}). Therefore (C_{i}, h_{i}) ∈ L_{1}K^{[2−m,m−1]}[C_{i}] by Lemma 31. Thus we may define η_{V} by η_{V} ((V, h)) := ((C_{1}, h_{1}), …, (C_{s}, h_{s})).

To construct another natural transformation ξ: L_{+} ∘ L_{1}K^{[2−m,m−1]} → L_{1}K^{[1−m,m]}, take an element ((C_{1}, h_{1}), …, (C_{s}, h_{s})) ∈ L_{+} ∘L_{1}K^{[2−m,m−1]}[V]. For each i ∈ {1, …, s−1}, define the integer μ_{i} as follows. If the minimum of the terminal block of level(h_{i}) is less than the maximum of the initial block of level(h_{i+1}), then μ_{i} := m. Otherwise let μ_{i} := m − 1. Define the height function h on V by h(v) := h_{i}(v) + ∑_{j=1}^{i−1} (μ_{j} + max(h_{j}(C_{j}))) for v ∈ C_{i}. Then one can deduce that (V, h) ∈ L_{1}K^{[1−m,m]}[V] by Lemma 31. Hence we may define ξ_{V} by ξ_{V} (((C_{1}, h_{1}), …, (C_{s}, h_{s}))) := (V, h).

It is easy to show that η and ξ are inverse to each other and hence L_{1}K^{[1−m,m]} = L_{+} ∘ L_{1}K^{[2−m,m−1]}. Finally by the induction hypothesis, we have L_{1}K^{[1−m,m]} = L_{+}^{∘m}.

Proof of Theorem 13. Use Lemma 27 and Lemma 32.

Example 33. Consider

(((v_{1}v_{2})(v_{3}))((v_{4})(v_{5}v_{6})(v_{7}))((v_{8}v_{9}))) = (((49)(5))((3)(71)(6))((82))) ∈ L_{+}^{∘3}[9]

(See Figure 4). We construct the corresponding flat of the extended Shi arrangement S_{9}^{3}. First let α be the integer composition obtained in a similar way in Example 30. In this case α = (1, 2, 3, 2, 1, 2, 3, 1). Next define the integer composition α′ by

α′_{i} := \begin{cases}α_{i}, & if v_{i} < v_{i+1}; \\ α_{i} − 1, & if v_{i} > v_{i+1}. \end{cases}

In this case α′ = (1, 1, 2, 2, 0, 2, 3, 0). By taking the partial sum ∑_{j=1}^{i−1} α_{j} for each i, we obtain the sequence of heights (0, 1, 2, 4, 6, 6, 8, 11, 11). The height function h is obtained by the following table.

\begin{matrix}v & 4 & 9 & 5 & 3 & 7 & 1 & 6 & 8 & 2 \\ h(v) & 0 & 1 & 2 & 4 & 6 & 6 & 8 & 11 & 11 \end{matrix}

The corresponding flat is

{x_{4} = x_{9} + 1 = x_{5} + 2 = x_{3} + 4 = x_{7} + 6 = x_{1} + 6 = x_{6} + 8 = x_{8} + 11 = x_{2} + 11}.

4.3 Proof of Theorem 15

Let F be a species with F[∅] = ∅. We consider the infinite matrix [|(E_{i} ∘ F)[j]|]. Note that almost all entries of each column of the matrix are 0 since

∑_{i=1}^{∞} |(E_{i} ∘ F)[j]| = |(E ∘ F)[j]| < ∞.

We show that substitution of species is compatible with product of the infinite matrices.

Proposition 34. Let F and G be species with F[∅] = G[∅] = ∅. Then

[|(E_{i} ∘ F)[j]|][|(E_{i} ∘ G)[j]|] = [|(E_{i} ∘ F ∘ G)[j]|].

Proof. Fix a positive integer i. By definition,

(E_{i} ∘ F ∘ G)(x) = ∑_{j=0}^{∞} |(E_{i} ∘ F ∘ G)[j]| \frac{x^{j}}{j!} .

We give another calculation of the series as follows.

(E_{i} ∘ F ∘ G)(x) = (E_{i} ∘ F)(G(x))

= ∑_{k=0}^{∞} |(E_{i} ∘ F)[k]| \frac{G(x)^{k}}{k!}

= ∑_{k=0}^{∞} |(E_{i} ∘ F)[k]| (E_{k} ∘ G)(x)

= ∑_{k=0}^{∞} |(E_{i} ∘ F)[k]| ∑_{j=0}^{∞} |(E_{k} ∘ G)[j]| \frac{x^{j}}{j!}

= ∑_{j=0}^{∞} (∑_{k=0}^{∞} |(E_{i} ∘ F)[k]| |E_{k} ∘ G[j]|) \frac{x^{j}}{j!} .

Therefore we have

|E_{i} ∘ F ∘ G[j]| = ∑_{k=0}^{∞} |E_{i} ∘ F[k]| |E_{k} ∘ G[j]|

for any positive integers i and j. Hence the assertion holds.

Example 35. Let C denote the species of cyclic permutations. Then the substitution E ∘ C_{+} coincides with the species of permutations. As mentioned in [1, p. 346], we have that L = E ∘ C_{+} as 𝕃-species. Indeed let each permutation σ ∈ (E ∘ C_{+})[n] correspond to the list (σ(1), σ(2), ⋯, σ(n)) ∈ L[n]. It is easy to see that this correspondence is bijective. Note that L and E∘C_{+} are not isomorphic as 𝔹-species. Recall that c, S, and [|(E_{i} ∘L_{+})[j]|] is the infinite upper triangular matrix consisting of Stirling numbers of the first and second kind, and Lah numbers. We can recover the following well-known equality.

[|(E_{i} ∘ L_{+})[j]|] = [|(E_{i} ∘ E_{+} ∘ C_{+})[j]|] = [|(E_{i} ∘ E_{+})[j]|][|(E_{i} ∘ C_{+})[j]|] = Sc.

Proof of Theorem 15. From Theorem 11, Proposition 34, and Example 35

[ |L_{i}(C_{j}^{m})| ] = [ |L_{i}C^{m}[j]| ] = [ |(E_{i} ∘ L_{+}^{∘m} ∘ E_{+})[j]| ]
= [|(E_{i} ∘ L_{+})[j]|]^{m}[|(E_{i} ∘ E_{+})[j]|] = (Sc)^{m}S.

Similarly from Theorem 13, Proposition 34, and Example 35

[ |L_{i}(S_{j}^{m})| ] = [ |L_{i}S^{m}[j]| ] = [ |(E_{i} ∘ L_{+}^{∘m})[j]| ]
= [|(E_{i} ∘ L_{+})[j]|]^{m} = (Sc)^{m}.

4.4 Proof of Theorem 17

Let a_{ij} denote the Lah number |(E_{i} ∘ L_{+})[j]|. By Proposition 16, a_{ij} = \frac{j!(j−1)!}{i!(i−1)!(j−i)!}. Note that if i > j, then a_{ij} = 0.

Lemma 36. For every positive integer m, [a_{ij}]^{m} = [m^{j−i}a_{ij}].

Proof. We proceed by induction on m. If m = 1, then it is trivial. Assume that m ≥ 2. By the induction hypothesis, the (i, j)-entry of the matrix [a_{ij}]^{m} = [a_{ij}][a_{ij}]^{m−1} is

∑_{k=i}^{j} a_{ik}(m − 1)^{j−k}a_{kj} = ∑_{k=i}^{j} \frac{k!(k − 1)!}{i!(i − 1)!(k − i)!}(m − 1)^{j−k} \frac{j!(j − 1)!}{k!(k − 1)!(j − k)!}

= \frac{j!(j − 1)!}{i!(i − 1)!(j − i)!} ∑_{k=i}^{j} \frac{(j − i)!}{(j − k)!(k − i)!}(m − 1)^{j−k}

= a_{ij} ∑_{k=i}^{j} \binom{j − i}{k − i}(m − 1)^{j−k} = a_{ij} ∑_{k=0}^{j−i} \binom{j − i}{k}(m − 1)^{j−i−k} = m^{j−i}a_{ij}.

This completes the proof. Proof of Theorem 17. The assertion holds immediately from Proposition 16, Theorem 15 and Lemma 36.

5 Numerical tables

n  1, 2, 3,  4,  5,  6,  7 OEIS
L(B_{n}) 1, 2, 5, 15,  52,  203,  877 \underline{A000110}
L(C_{n}^{1}) 1, 4, 23, 173, 1602, 17575, 222497 \underline{A075729}
L(C_{n}^{2}) 1, 6, 53, 619, 8972, 155067, 3109269 \underline{A109092}
L(C_{n}^{3}) 1, 8, 95, 1497, 29362, 688439, 18766393 None
L(C_{n}^{4}) 1, 10, 149, 2951, 72852, 2152651, 74031869 None

Table 1: The numbers of flats of the extended Catalan arrangements

n 1, 2, 3,  4,  5,  6,  7 OEIS
L(S_{n}^{1}) 1, 3, 13, 73,  501,  4051,  37633 \underline{A000262}
L(S_{n}^{2}) 1, 5, 37, 361, 4361, 62701, 1044205 \underline{A025168}
L(S_{n}^{3}) 1, 7, 73, 1009, 17341, 355951, 8488117 \underline{A321837}
L(S_{n}^{4}) 1, 9, 121, 2161, 48081, 1279801, 39631369 \underline{A321847}
L(S_{n}^{5}) 1, 11, 181, 3961, 108101, 3532651, 134415961 \underline{A321848}

Table 2: The numbers of flats of the extended Shi arrangements

n  1, 2, 3,  4,  5,  6,  7 OEIS
L_{1}(B_{n}) 1, 1, 1,  1,  1,  1,  1 \underline{A000012}
L_{1}(C_{n}^{1}) 1, 3, 13, 75, 541,  4683,  47293 \underline{A000670}
L_{1}(C_{n}^{2}) 1, 5, 37, 365, 4501, 66605, 1149877 \underline{A050351}
L_{1}(C_{n}^{3}) 1, 7, 73, 1015, 17641, 367927, 8952553 \underline{A050352}
L_{1}(C_{n}^{4}) 1, 9, 121, 2169, 48601, 1306809, 40994521 \underline{A050353}

Table 3: The numbers of 1-dimensional flats of the extended Catalan arrangements

n  1, 2, 3,  4,  5,  6,  7 OEIS
L_{1}(S_{n}^{1}) 1, 2, 6, 24, 120,  720,  5040 \underline{A000142}
L_{1}(S_{n}^{2}) 1, 4, 24, 192, 1920, 23040, 322560 \underline{A002866}
L_{1}(S_{n}^{3}) 1, 6, 54, 648, 9720, 174960, 3674160 \underline{A034001}
L_{1}(S_{n}^{4}) 1, 8, 96, 1536, 30720, 737280, 20643840 \underline{A034177}
L_{1}(S_{n}^{5}) 1, 10, 150, 3000, 75000, 2250000, 78750000 \underline{A034325}

Table 4: The numbers of 1-dimensional flats of the extended Shi arrangements

\begin{matrix}L_{k}(B_{n}) & & & & \underline{A008277} \\ n\k & 1, & 2, & 3, & 4, & 5 \\ 1 & 1, \\ 2 & 1, & 1, \\ 3 & 1, & 3, & 1, \\ 4 & 1, & 7, & 6, & 1, \\ 5 & 1, & 15, & 25, & 10, & 1 \end{matrix} \begin{matrix}L_{k}(S_{n}^{1}) & & & & \underline{A105278} \\ n\k & 1, & 2, & 3, & 4, & 5 \\ 1 & 1, \\ 2 & 2, & 1, \\ 3 & 6, & 6, & 1, \\ 4 & 24, & 36, & 12, & 1, \\ 5 & 120, & 240, & 120, & 20, & 1 \end{matrix}

\begin{matrix}L_{k}(C_{n}^{1}) & & & & \underline{A088729} \\ n\k & 1, & 2, & 3, & 4, & 5 \\ 1 & 1, \\ 2 & 3, & 1, \\ 3 & 13, & 9, & 1, \\ 4 & 75, & 79, & 18, & 1, \\ 5 & 541, & 765, & 265, & 30, & 1 \end{matrix} \begin{matrix}L_{k}(S_{n}^{2}) & & & & \underline{A079621} \\ n\k & 1, & 2, & 3, & 4, & 5 \\ 1 & 1, \\ 2 & 4, & 1, \\ 3 & 24, & 12, & 1, \\ 4 & 192, & 144, & 24, & 1, \\ 5 & 1920, & 1920, & 480, & 40, & 1 \end{matrix}

Table 5: Triangles of the number of k-dimensional flats, part 1

6 Acknowledgments

This work was supported by JSPS KAKENHI Grant Number JP20K14282. The authors are very grateful to the anonymous referee for helpful comments.

\begin{matrix}L_{k}(C_{n}^{2}) & & & & \underline{A308440} \\ n\k & 1, & 2, & 3, & 4, & 5 \\ 1 & 1, \\ 2 & 5, & 1, \\ 3 & 37, & 15, & 1, \\ 4 & 365, & 223, & 30, & 1, \\ 5 & 4501, & 3675, & 745, & 50, & 1 \end{matrix} \begin{matrix}L_{k}(S_{n}^{3}) & & & & \underline{A308281} \\ n\k & 1, & 2, & 3, & 4, & 5 \\ 1 & 1, \\ 2 & 6, & 1, \\ 3 & 54, & 18, & 1, \\ 4 & 648, & 324, & 36, & 1, \\ 5 & 9720, & 6480, & 1080, & 60, & 1 \end{matrix}

\begin{matrix}L_{k}(C_{n}^{3}) & & & & NONE \\ n\k & 1, & 2, & 3, & 4, & 5 \\ 1 & 1, \\ 2 & 7, & 1, \\ 3 & 73, & 21, & 1, \\ 4 & 1015, & 439, & 42, & 1, \\ 5 & 17641, & 10185, & 1465, & 70, & 1 \end{matrix} \begin{matrix}L_{k}(S_{n}^{4}) & & & & \underline{A048786} \\ n\k & 1, & 2, & 3, & 4, & 5 \\ 1 & 1, \\ 2 & 8, & 1, \\ 3 & 96, & 24, & 1, \\ 4 & 1536, & 576, & 48, & 1, \\ 5 & 30720, & 15360, & 1920, & 80, & 1 \end{matrix}

\begin{matrix}L_{k}(C_{n}^{4}) & & & & NONE \\ n\k & 1, & 2, & 3, & 4, & 5 \\ 1 & 1, \\ 2 & 9, & 1, \\ 3 & 121, & 27, & 1, \\ 4 & 2169, & 727, & 54, & 1, \\ 5 & 48601, & 21735, & 2425, & 90, & 1 \end{matrix} \begin{matrix}L_{k}(S_{n}^{5}) & & & & \underline{A308282} \\ n\k & 1, & 2, & 3, & 4, & 5 \\ 1 & 1, \\ 2 & 10, & 1, \\ 3 & 150, & 30, & 1, \\ 4 & 3000, & 900, & 60, & 1, \\ 5 & 75000, & 30000, & 3000, & 100, & 1 \end{matrix}

Table 6: Triangles of the number of k-dimensional flats, part 2

References

[1] F. Bergeron, G. Labelle, and P. Leroux, Combinatorial Species and Tree-like Structures, Encyclopedia of Mathematics and its Applications, vol. 67, Cambridge University Press, 1998.

[2] F. Bergeron, G. Labelle, and P. Leroux, Introduction to the theory of species of struc-

tures, 2013. Available at http://bergeron.math.uqam.ca/species/.

[3] D. Callan, Sets, lists and noncrossing partitions, J. Integer Sequences 11 (2008), Article 08.1.3.

[4] S. Corteel, D. Forge, and V. Ventos, Bijections between affine hyperplane arrangements and valued graphs, European J. Combin. 50 (2015), 30–37.

[5] R. Gill, The number of elements in a generalized partition semilattice, Discrete Math. 186 (1998), 125–134.

[6] D. G. Hedmark, The partition lattice in many guises, Ph.D. thesis, University of Kentucky, 2017.

[7] A. Joyal, Une théorie combinatoire des séries formelles, Adv. Math. 42 (1981), 1–82.

[8] T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proceedings of Symposia in Pure Mathematics, No. 19, American Mathematical Society, 1971, pp. 167–176.

[9] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2021, Available

    at http://oeis.org.

[10] P. Orlik and H. Terao, Arrangements of Hyperplanes, Grundlehren der mathematischen Wissenschaften, Vol. 300, Springer, 1992.

[11] J. Riordan, Introduction to Combinatorial Analysis, Dover, 2002.

[12] N. J. A. Sloane and T. Wieder, The number of hierarchical orderings, Order 21 (2004), 83–89.

[13] T. Zaslavsky, Geometric lattices of structured partitions I. Gain-graphic matroids and group valued partitions, preprint, 1985.

[14] T. Zaslavsky, Biased graphs. I. bias, balance, and gains, J. Combin. Theory Ser. B 47 (1989), 32–52.

[15] T. Zaslavsky, Biased graphs IV: geometrical realizations, J. Combin. Theory Ser. B 89 (2003), 231–297.

2020 Mathematics Subject Classification: Primary 05A19; Secondary 05A18, 05C22, 52C35. Keywords: hyperplane arrangement, Shi arrangement, Catalan arrangement, intersection poset, species, gain graph, set partition, Bell number, Stirling number, Lah number.

(Concerned with sequences \underline{A000012}, \underline{A000110}, \underline{A000142}, \underline{A000262}, \underline{A000670}, \underline{A002866}, \underline{A008277}, \underline{A025168}, \underline{A034001}, \underline{A034177}, \underline{A034325}, \underline{A048786}, \underline{A050351}, \underline{A050352}, \underline{A050353}, \underline{A075729}, \underline{A079621}, \underline{A088729}, \underline{A105278}, \underline{A109092}, \underline{A308281}, \underline{A308282}, \underline{A308440}, \underline{A321837}, \underline{A321847}, and \underline{A321848}.)

Received June 18 2021; revised version received September 29 2021. Published in Journal of Integer Sequences, September 30 2021.

Return to Journal of Integer Sequences home page.