The Catalan Threshold Arrangement

Seunghyun Seo Department of Mathematics Education Kangwon National University The Republic of Korea

                    shyunseo@kangwon.ac.kr

Abstract

The Catalan threshold arrangement is a hyperplane arrangement defined by x_{i} + x_{j} = 0, 1, −1. Using the finite field method, we obtain the number of regions and the characteristic polynomial of the Catalan threshold arrangement. We also give the exponential generating function for the characteristic polynomial of the Catalan threshold arrangement.

1 Introduction

Hyperplane arrangements are very interesting combinatorial objects and many results can be found in the literature. For instance, several papers [1, 2, 6, 7] are concerned with the characteristic polynomials and the number of regions of a hyperplane arrangement.

In his paper [9], Stanley reviewed various hyperplane arrangements raising interesting questions, one of which is related to the following hyperplane arrangement:

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

This is called the Shi threshold arrangement [9, p. 473]. Stanley asked to find the characteristic polynomial of the Shi threshold arrangement. In a recent paper [7], the author provided an answer to that question by applying the finite field method. The finite field method was first developed into a tool for computing characteristic polynomials by Athanasiadis [2].

In this paper, we study the following generalization of the Shi threshold arrangement:

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

Throughout this paper, we will call this arrangement the Catalan threshold arrangement. The main result of this paper is the characteristic polynomial of the Catalan threshold arrangement. We also obtain the exponential generating function for the characteristic polynomial.

This paper is organized as follows. In Section 2, we recall some basic facts on hyperplane arrangements and related combinatorial objects that are used in the sequel. In Section 3, we prove our main result in Theorem 8 by the finite field method. The exponential generating function for the characteristic polynomial of the Catalan threshold arrangement is proven in Equation (17).

2 Preliminaries

We recall some notation and concepts of hyperplane arrangements and related combinatorial objects. For a more thorough introduction, see [4, 5, 9].

2.1 Basic concepts of hyperplane arrangements

Given a positive integer n and a field K, a finite set of affine hyperplanes in the vector space K^{n} is called a hyperplane arrangement (or arrangement for short). Now, let K = ℝ. A region of an arrangement A is a connected component of ℝ^{n} − ⋃_{H∈A} H. We denote the number of regions of A by r(A).

Given an arrangement A in a vector space V, let L(A) be the set of all nonempty intersections of hyperplanes in A, including V. We define x ≤ y in L(A) if x ⊇ y. We call L(A) the intersection poset of A.

For a finite poset P with ˆ0, the Möbius function μ : P → ℤ is defined by

μ(ˆ0) = 1 and μ(x) = − ∑_{y<x} μ(y).

Definition 1. The characteristic polynomial χ_{A}(t) of the arrangement A is defined by

χ_{A}(t) := ∑_{x∈L(A)} μ(x) t^{dim(x)},

where dim(x) is the dimension of x as an affine subspace of V.

The characteristic polynomial plays an important role in analyzing arrangements. One of the fundamental result is the following theorem.

Theorem 2 (Zaslavsky [12]). For any arrangement A in ℝ^{n}, we have

r(A) = (−1)^{n} χ_{A}(−1).

In general, it is hard to compute the characteristic polynomial of an arrangement A. However, if A is in ℚ^{n} (i.e., all coefficients of hyperplanes in A are rational), then there is a powerful method in computing its characteristic polynomial. For a prime number p, let 𝔽_{p} be the finite field of order p. If H is a hyperplane of A in ℚ^{n}, by multiplying a proper integer to the equation of H, we can make all the coefficients of the equation of H integers. We then reduce the coefficients modulo p to get an arrangement A_{p} in 𝔽_{p}^{n}. It is well known that there are all but finitely many primes p such that L(A) is isomorphic to L(A_{p}).

Theorem 3 (Athanasiadis [2]). Let A be an arrangement in ℚ^{n}. If L(A) ≅ L(A_{q}) for some prime q, then

χ_{A}(q) = | 𝔽_{q}^{n} − ⋃_{H∈A_{q}} H | = q^{n} − | ⋃_{H∈A_{q}} H | ,

which is called the finite field method.

We now consider two special hyperplane arrangements: the Catalan arrangement and the threshold arrangement. The Catalan arrangement C_{n} is given by

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

The characteristic polynomial of C_{n} is

χ_{C_{n}}(t) = t(t − n − 1)(t − n − 2) ⋯ (t − 2n + 1).

Applying Zaslavsky’s theorem, we have

r(C_{n}) = (2n)(2n − 1) ⋯ (n + 2) = n!C_{n},

where C_{n} = \frac{1}{n+1} \binom{2n}{n} is the n-th Catalan number \underline{A000108}.

The threshold arrangement T_{n} is given by

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

The “threshold” comes from threshold graphs introduced by Chvátal and Hammer [3]. There is a canonical bijection between the set of regions of T_{n} and the set of threshold graphs on the vertex set [n] := \{1, 2, …, n\}. The number of threshold graphs appears in \underline{A005840}. Stanley [9, p. 473] showed that the exponential generating function for the characteristic polynomial of T_{n} is given by

∑_{n≥0} χ_{T_{n}}(t)\frac{x^{n}}{n!} = (1 + x)(2e^{x} − 1)^{(t−1)/2}.

2.2 Delannoy numbers and Schröder numbers

Given nonnegative integers p and q, consider a lattice path P in the plane from (0, 0) to (p, q) using steps (1, 0), (0, 1), or (1, 1). The total number D(p, q) of such paths is called the Delannoy number \underline{A008288}. For an nonnegative integer n, D(n, n) is called the central Delannoy number \underline{A001850}. The following properties of Delannoy numbers are well known [4, p. 81].

Proposition 4. The Delannoy number D(p, q) satisfies the following:

1. The Delannoy number D(p, q) has two expressions

D(p, q) = ∑_{d≥0} \binom{q}{d}\binom{p + q − d}{q},  (1)

D(p, q) = ∑_{d≥0} 2^{d}\binom{p}{d}\binom{q}{d}.  (2)

2. The Delannoy number D(p, q) satisfies the recurrence relation

D(p, q) = D(p − 1, q) + D(p, q − 1) + D(p − 1, q − 1).  (3)

3. The generating function D(x) for D(n, n) is

D(x) := ∑_{n≥0} D(n, n)x^{n} = \frac{1}{\sqrt{1 − 6x + x^{2}}} .  (4)

For a nonnegative integer n, consider a lattice path P in the plane from (0, 0) to (n, n) using steps (1, 0), (0, 1), or (1, 1), such that P never passes above the line y = x. The total number r_{n} of such paths is called the Schröder number \underline{A006318}. The following properties of Schröder numbers are well known [10].

Proposition 5. The Schröder number r_{n} satisfies the following:

1. The Schröder number r_{n} satisfies the recurrence relation

r_{n} = r_{n−1} + ∑_{k=0}^{n−1} r_{k} r_{n−1−k} , r_{0} = 1.

2. The generating function R(x) for r_{n} is

R(x) := ∑_{n≥0} r_{n}x^{n} = \frac{1 − x − \sqrt{1 − 6x + x^{2}}}{2x} .  (5)

−1 2 −3 4 −5 1 −2 3 −4 5 0
Figure 1: Graph G_{11}

3 Main result

Recall that the Catalan threshold arrangement is defined by

x_{i} + x_{j} = 0, 1, −1, 1 ≤ i < j ≤ n.  (6)

We denote by CT_{n} the Catalan threshold arrangement. In this section, we will find the characteristic polynomial of Catalan threshold arrangement and its exponential generating function.

3.1 The characteristic polynomial of CT_{n}

Let X be the set defined by

X = {(a_{1}, …, a_{n}) ∈ 𝔽_{q}^{n} | a_{i} + a_{j} ≠ 0, 1, −1, for i < j}.  (7)

By the finite field method, there exist infinitely many odd primes q = 2r + 1 such that

χ_{CT_{n}}(q) = |X|.

Let G_{q} be a simple graph such that

V (G_{q}) = 𝔽_{q} and E(G_{q}) = { {u, v} | u, v ∈ 𝔽_{q} with u + v = 0, 1, −1 }.

See Figure 1 for G_{11}. We can regard an element (a_{1}, …, a_{n}) in 𝔽_{q}^{n} as a function f : [n] → 𝔽_{q} satisfying f(i) = a_{i} for all i = 1, 2, …, n. It is obvious that f ∈ 𝔽_{q}^{n} belongs to X if and only if f satisfies the following two conditions.

(C1) The image of f, i.e., f([n]) is an independent set of G_{q}, and

(C2) |f^{−1}(0)| ≤ 1, |f^{−1}(r)| ≤ 1, and |f^{−1}(−r)| ≤ 1 hold.

Here, an independent set of G_{q} is a subset I of V (G_{q}) such that no two vertices of I represent an edge of G_{q}. Note that I = ∅ is always an independent set. Now, we will count the number of functions f : [n] → 𝔽_{q} satisfying two conditions (C1) and (C2).

To consider the condition (C1), we need to find the number of independent sets of the following graph. Given a nonnegative integer m, let A_{m} be a graph on the vertex set V (A_{m}) = {1, 2, …, m} ∪ {1′, 2′, …, m′} with the edge set

E(A_{m}) = {{i, i + 1} | 1 ≤ i ≤ m − 1} ∪ {{i′, (i + 1)′} | 1 ≤ i ≤ m − 1} ∪ {{i, i′} | 1 ≤ i ≤ m},

1′ 2′ 3′ 1 2 3 A_{3}:  ^{1′ 2′ 3′ 1 2 3 4 B_{3}:}
Figure 2: Graphs A_{3} and B_{3}

for m ≥ 1 and A_{0} be the empty graph. We also define the graph B_{m} by A_{m+1} − (m + 1)′. See Figure 2 for A_{3} and B_{3}.

For nonnegative integers k and m, let a(m, k) be the number of k-independent sets of A_{m}, and b(m, k) be the number of k-independent sets of B_{m}. By convention, we set a(0, k) = δ_{0,k}, for the empty graph A_{0} which has the unique independent set ∅.

Lemma 6. For nonnegative integers k and m, we have

b(m, k) = D(m − k + 1, k),  (8)
a(m, k + 1) = D(m − k, k + 1) − D(m − k, k).  (9)

Here D(p, q) is the Delannoy number.

Proof. To select a k-independent set I of B_{m}, we can consider three cases: (i) m ∉ I and m + 1 ∉ I, (ii) m ∉ I and m + 1 ∈ I, (iii) m ∈ I. From this, we see that

b(m, k) = b(m − 1, k) + b(m − 1, k − 1) + b(m − 2, k − 1),

which shows that b(m, k) satisfies the same recursion as D(m − k + 1, k) in (3). We now check the initial conditions. Note that

b(m, k) = \begin{cases}0, & k − m ≥ 2; \\ 1, & k − m = 1 or k = 0; \\ 3, & k = m = 1, \end{cases} and D(p, q) = \begin{cases}0, & p ≤ −1; \\ 1, & p = 0 or q = 0; \\ 3, & p = q = 1. \end{cases}

Thus, b(m, k) = D(m − k + 1, k) for all nonnegative integer m and k.

Next, we prove (9). To select a (k + 1)-independent set J of B_{m}, we can consider two cases: (i) m + 1 ∉ J and (ii) m + 1 ∈ J. Thus we have

b(m, k + 1) = a(m, k + 1) + b(m − 1, k),

which yields a(m, k + 1) = b(m, k + 1) − b(m − 1, k).

From Lemma 6 we can easily get a number of functions f satisfying the condition (C1).

Lemma 7. For positive integers m and n, the number of f : [n] → V (A_{m}) satisfying that f([n]) is an independent set of A_{m} is

∑_{1≤j≤min(m,n)} a(m, j) S(n, j) j!,

and the number of f : [n] → V (B_{m}) satisfying that f([n]) is an independent set of B_{m} is

∑_{1≤j≤min(m,n)} b(m, j) S(n, j) j!,

where S(n, j) is the Stirling number of the second kind.

For a nonnegative integers m and n, let a_{m}(n) and b_{m}(n) be

a_{m}(n) := ∑_{0≤j≤min(m,n)} a(m, j) S(n, j) j! ,  (10)
b_{m}(n) := ∑_{0≤j≤min(m,n)} b(m, j) S(n, j) j! .  (11)

Now we go back to Catalan threshold arrangements. To compute the size of X in (7), we should also regard the second condition (C2). Among f = (f(1), …, f(n)) ∈ X, each 0, r and −r can be chosen at most once. So we have four cases to consider.

(i) None of them are selected. (ii) Only 0 is selected. (iii) 0 is not selected and either r or −r is selected. (iv) 0 is selected and either r or −r is selected. By Lemma 7, the number of elements f of the case (i) is

∑_{0≤j≤min(r−1,n)} a(r − 1, j) S(n, j) j! ,

which reduces to a_{r−1}(n). Similarly, the case (ii) is n a_{r−2}(n − 1). The case (iii) is

2n ∑_{0≤j≤min(r−2,n−1)} b(r − 2, j) S(n − 1, j) j!,

which reduces to 2n b_{r−2}(n − 1). Similarly, the case (iv) is 2n(n − 1) b_{r−3}(n − 2). Thus we have the following result.

Theorem 8 (Main result). The characteristic polynomial of the Catalan threshold arrangement CT_{n} is given by

χ_{CT_{n}}(t) = n! ∑_{k=0}^{n} ∑_{ℓ=0}^{k} α_{n,k,ℓ} \frac{((t − 2k − 1))_{ℓ}}{ℓ!} ,  (12)

where ((x))_{k} is defined by ((x))_{0} = 1 and ((x))_{k} = x(x − 2)(x − 4) ⋯ (x − 2k + 2) for k ≥ 1. Here α_{n,k,ℓ} is given by α_{0,0,0} = α_{1,0,0} = 1, and for n ≥ 2 or k^{2} + ℓ^{2} > 0,

α_{n,k,ℓ} = \binom{k − 1}{ℓ − 1}s_{n,k} + \binom{k − 2}{ℓ − 1}s_{n−1,k−1} + 2\binom{k − 1}{ℓ}s_{n−1,k−1} + 2\binom{k − 2}{ℓ}s_{n−2,k−2} ,

where s_{n,k} is defined by s_{n,k} = \frac{k!}{n!}S(n, k).

Proof. Since we can easily check that (12) holds for n ≤ 2, we may assume n ≥ 3. By considering all the cases (i)–(iv), we have

χ_{CT_{n}}(q) =a_{r−1}(n) + n a_{r−2}(n − 1) + 2n b_{r−2}(n − 1) + 2n(n − 1) b_{r−2}(n − 2)  (13)
= ∑_{j≥0} a (\frac{q − 3}{2}, j) j! S(n, j) + n ∑_{j≥0} a (\frac{q − 5}{2}, j) j! S(n − 1, j)

+ 2n ∑_{j≥0} b (\frac{q − 5}{2}, j) j! S(n − 1, j) + 2n(n − 1) ∑_{j≥0} b (\frac{q − 7}{2}, j) j! S(n − 2, j) ,

for infinitely many primes q = 2r + 1. Since n ≥ 3, we can ignore the case j = 0. By applying (8), (9), and (2), we have

χ_{CT_{n}}(t) = ∑_{j=1}^{n} ∑_{d=1}^{j} S(n, j)\frac{j!}{d!}\binom{j − 1}{d − 1}((t − 2j − 1))_{d}

+ ∑_{j=1}^{n} ∑_{d=1}^{j} n S(n − 1, j)\frac{j!}{d!}\binom{j − 1}{d − 1}((t − 2j − 3))_{d}

+ ∑_{j=1}^{n} ∑_{d=0}^{j} 2n S(n − 1, j)\frac{j!}{d!}\binom{j}{d}((t − 2j − 3))_{d}

+ ∑_{j=1}^{n} ∑_{d=0}^{j} 2n(n − 1) S(n − 2, j)\frac{j!}{d!}\binom{j}{d}((t − 2j − 5))_{d} .

Let [((t − 2k − 1))_{ℓ}] F (x) be the “coefficient” of ((t − 2k − 1))_{ℓ} in F (x). Then

[((t − 2k − 1))_{ℓ}]χ_{CT_{n}}(t) = S(n, k)\frac{k!}{ℓ!}\binom{k − 1}{ℓ − 1} + nS(n − 1, k − 1)\frac{(k − 1)!}{ℓ!}\binom{k − 2}{ℓ − 1}

+ 2nS(n − 1, k − 1)\frac{k!}{ℓ!}\binom{k − 1}{ℓ} + 2n(n − 1)S(n − 2, k − 2)\frac{(k − 2)!}{ℓ!}\binom{k − 2}{ℓ}.

Since α_{n,k,ℓ} = \frac{ℓ!}{n!} [((t − 2k − 1))_{ℓ}] χ_{CT_{n}}(t), we have

α_{n,k,ℓ} =\frac{k!}{n!}S(n, k)\binom{k − 1}{ℓ − 1} + \frac{(k − 1)!}{(n − 1)!}S(n − 1, k − 1)\binom{k − 2}{ℓ − 1}

+ 2\frac{(k − 1)!}{(n − 1)!}S(n − 1, k − 1)\binom{k − 1}{ℓ} + 2\frac{(k − 2)!}{(n − 2)!}S(n − 2, k − 2)\binom{k − 2}{ℓ} .

For instance χ_{CT_{0}}(t) = 1, χ_{CT_{1}}(t) = t, χ_{CT_{2}}(t) = t^{2} − 3t, and

χ_{CT_{3}}(t) = t^{3} − 9t^{2} + 27t − 27
χ_{CT_{4}}(t) = t^{4} − 18t^{3} + 135t^{2} − 483t + 675
χ_{CT_{5}}(t) = t^{5} − 30t^{4} + 405t^{3} − 2955t^{2} + 11340t − 17993.

Applying Zaslavsky’s theorem, we have the following result. Corollary 9. The number of regions of the Catalan threshold arrangement CT_{n} is given by

r(CT_{n}) = (−1)^{n}n! ∑_{k=0}^{n} ∑_{ℓ=0}^{k} α_{n,k,ℓ} (−2)^{ℓ}\binom{k + 1}{ℓ} ,

where α_{n,k,ℓ} is defined in Theorem 8.

The sequence (r(CT_{n}))_{n≥0} starts with

1, 1, 4, 64, 1312, 32724, 979316, …

which is not listed in the On-Line Encyclopedia of Integer Sequences [8].

3.2 The exponential generating function for χ_{CT_{n}}(t)

Recall the definition of b_{m}(n) in (11). By the exponential formula we have

b_{m}(n) = ∑_{j≥0} b(m, j) [\frac{x^{n}}{n!} ] (e^{x} − 1)^{j},

where [\frac{x^{n}}{n!} ] F (x) is the coefficient of \frac{x^{n}}{n!} in the power series F (x). Thus

∑_{n≥0} b_{m}(n)\frac{x^{n}}{n!} = ∑_{j≥0} b(m, j)(e^{x} − 1)^{j}.  (14)

It is easy to show that

∑_{j≥0} D(j + α, j)z^{j} = \frac{R(z)^{α}}{D(z)} ,  (15)

where D(z) and R(z) are given in (4) and (5). Note that this is an extended version of the following well known (for example [11, p. 54]) identity

∑_{j≥0} \binom{2j + α}{j}z^{j} = \begin{matrix}C(z) & α \\ √ & \overline{1 − 4z} \end{matrix} ,

where C(z) is the ordinary generating function for the Catalan number.

Recall b(m, j) = D(m − j + 1, j). By (1), we see that b(m, j) can be considered as a monic polynomial in m with degree j. By simple calculation, we have

D(m − j + 1, j) = ∑_{0≤d≤j} \binom{j}{d}\binom{m + 1 − d}{j}

= (−1)^{j} ∑_{0≤d≤j} \binom{j}{d}\binom{j − m − 2 + d}{j}

= (−1)^{j} ∑_{0≤c≤j} \binom{j}{c}\binom{2j − m − 2 − c}{j}  (c = j − d)

= (−1)^{j}D(j − m − 2, j).

By replacing α = −m − 2 and z = −(e^{x} − 1), we obtain

∑_{j≥0} D(j + α, j)z^{j} = ∑_{j≥0} b(m, j)(e^{x} − 1)^{j} .  (16)

Combining (14), (15), and (16) yields that

∑_{n≥0} b_{m}(n)\frac{x^{n}}{n!} = \frac{R(1 − e^{x})^{−m−2}}{D(1 − e^{x})} .

Meanwhile, from (10), we deduce that

∑_{n≥0} a_{m}(n)\frac{x^{n}}{n!} = ∑_{n≥0} ∑_{j≥0} a(m, j)S(n, j)j!\frac{x^{n}}{n!}

= ∑_{n≥0} ∑_{j≥0} b(m − 1, j)S(n, j)j!\frac{x^{n}}{n!} + ∑_{n≥0} ∑_{j≥1} b(m − 2, j − 1)S(n, j)j!\frac{x^{n}}{n!}

= ∑_{n≥0} b_{m−1}(n)\frac{x^{n}}{n!} + ∑_{j≥1} b(m − 2, j − 1)(e^{x} − 1)^{j}

= ∑_{n≥0} b_{m−1}(n)\frac{x^{n}}{n!} + (e^{x} − 1) ∑_{n≥0} b_{m−2}(n)\frac{x^{n}}{n!} .

Thus we have

∑_{n≥0} a_{m}(n)\frac{x^{n}}{n!} = \frac{R(1 − e^{x})^{−m−1} − R(1 − e^{x})^{−m}}{D(1 − e^{x})} .

As seen in (13), the characteristic polynomial χ_{CT_{n}}(t) can be expressed as a linear combination of a_{m}(n) and b_{m}(n). So, with simple calculations, we can deduce the exponential generating function for χ_{CT_{n}}(t):

∑_{n≥0} χ_{CT_{n}}(t)\frac{x^{n}}{n!} = \frac{R(1 − e^{x})^{\frac{1−t}{2}}}{D(1 − e^{x})} (1 + xR(1 − e^{x}))(1 + 2x − (1 − e^{x})R(1 − e^{x})) . (17)

Put t = −1 and x = −x in (17) to get the exponential generating function for r(CT_{n}):

∑_{n≥0} r(CT_{n})\frac{x^{n}}{n!} = \frac{R(1 − e^{−x})}{D(1 − e^{−x})}(1 − xR(1 − e^{−x}))(1 − 2x − (1 − e^{−x})R(1 − e^{−x})) . (18)

3.3 Remark

Consider a generalized threshold arrangement such as

x_{i} + x_{j} = −ℓ, −ℓ + 1, …, m − 1, m 1 ≤ i < j ≤ n,

for nonnegative integers ℓ and m. We denote the arrangement by T_{n}^{[−ℓ,m]}. By parallel translation, T_{n}^{[−ℓ,m]} is transformed to either T_{n}^{[−k+1,k]} or T_{n}^{[−k,k]}, which can be called an extended Shi threshold arrangement or an extended Catalan threshold arrangement. In particular, T_{n}^{[0,1]} = ST_{n} and T_{n}^{[−1,1]} = CT_{n}. It would be interesting to find the characteristic polynomials of these two arrangements for k ≥ 2.

4 Acknowledgments

This paper was written during the author’s sabbatical year in the Department of Mathematics at the Pennsylvania State University. The author wishes to thank the Department, in particular, A. J. Yee, for her support, hospitality, and helpful advice. This study has been worked with the support of a research grant from Kangwon National University in 2015.

References

[1] F. Ardila, Computing the Tutte polynomial of a hyperplane arrangement, Pacific J. Math. 230 (2007), 1–26.

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

[3] V. Chvátal and P. L. Hammer, Aggregation of inequalities in integer programming, Ann. of Discrete Math. 1 (1977), 145–162.

[4] L. Comtet, Advanced Combinatorics, D. Reidel Publishing Co., 1974.

[5] P. Orlik and H. Terao, Arrangements of Hyperplanes, Springer-Verlag, 1992.

[6] A. Postnikov and R. P. Stanley, Deformations of Coxeter hyperplane arrangements, J. Combin. Theory Ser. A 91 (2000), 544–597.

[7] S. Seo, Shi threshold arrangement, Electron. J. Combin. 19 (3) (2012), #P39.

[8] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electroni-

    cally at http://oeis.org, 2016.

[9] R. P. Stanley, An introduction to hyperplane arrangements, in E. Miller, V. Reiner, and B. Sturmfels, eds., Geometric Combinatorics, Amer. Math. Soc., 2007, pp. 389–496.

[10] R. A. Sulanke, Bijective recurrences concerning Schröder paths, Electron. J. Combin. 5 (1998), #R47.

[11] H. S. Wilf, generatingfunctionology, Academic Press Inc., 1994.

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

2010 Mathematics Subject Classification: Primary 52C35; Secondary 05A15. Keywords: hyperplane arrangement, Catalan threshold arrangement, finite field method.

(Concerned with sequences \underline{A000108}, \underline{A001850}, \underline{A005840}, \underline{A006318}, and \underline{A008288}.)

Received July 27 2016; revised version received December 22 2016. Published in Journal of Integer Sequences, December 23 2016.

Return to Journal of Integer Sequences home page.