\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage{pstricks}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\newcommand{\A}{{\mathcal A}}
\newcommand{\T}{{\mathcal T}}
\newcommand{\Shi}{{\mathcal S}}
\newcommand{\Cat}{{\mathcal C}}
\newcommand{\ST}{{\mathcal{ST}}}
\newcommand{\CT}{{\mathcal{CT}}}
\newcommand{\real}{{\mathbb R}}
\newcommand{\0}{\hat{0}}
\newcommand{\fld}{{\mathbb F}}
\newcommand{\cpst}{\chi_{\ST_n}}
\newcommand{\cpct}{\chi_{\CT_n}}
\newcommand{\dff}[1]{{(\!({#1})\!)}}

\newcommand\comment[1]{{\textcolor{red}{\bf [[ #1 ]]}}}

\begin{center}
\vskip 1cm{\LARGE\bf The Catalan Threshold Arrangement}  \vskip 1cm
\large
Seunghyun Seo\\
Department of Mathematics Education\\
Kangwon National University\\
The Republic of Korea\\
\href{mailto:shyunseo@kangwon.ac.kr}{\tt shyunseo@kangwon.ac.kr} \\
\end{center}

\vskip .2 in

\begin{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.
\end{abstract}

\section{Introduction}

Hyperplane arrangements are very interesting combinatorial objects and many results can be found in the literature. For instance, several papers
\cite{Ard, Ath, PoSt, Seo} are concerned with
the characteristic polynomials and the number of regions of a hyperplane
arrangement.

In his paper \cite{Sta3}, Stanley reviewed various hyperplane arrangements raising interesting questions, one of which is related to the following hyperplane arrangement:
$$
x_i + x_j =0,1,\quad 1 \leq i < j \leq n.
$$
This is called the Shi threshold arrangement \cite[p.\ 473]{Sta3}. Stanley asked to find the characteristic polynomial of the Shi threshold arrangement. In a recent paper~\cite{Seo}, 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 \cite{Ath}.

In this paper, we study the following generalization of the Shi threshold arrangement: 
\begin{equation*}
x_i + x_j =0,1,-1, \quad 1 \leq i < j \leq n. 
\end{equation*}
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~\ref{sec2}, we recall some basic facts on hyperplane arrangements and related combinatorial objects that are used in the sequel. In Section~\ref{sec3}, we prove our main result in 
Theorem~\ref{thm:ch-poly} by the finite field method. The exponential generating function for the characteristic polynomial of the Catalan threshold arrangement is proven in Equation~\eqref{eq:gen-cha-ct}.

\section{Preliminaries} \label{sec2}
We recall some notation and concepts of hyperplane arrangements and related combinatorial objects.
For a more thorough introduction, see \cite{Comt, OT, Sta3}.

\subsection{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 \emph{hyperplane arrangement} (or \emph{arrangement} for short).
Now, let $K=\real$. A \emph{region} of an arrangement $\A$ is a connected component of $\real^n - \bigcup_{H \in \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 \leq y$ in $L(\A)$ if $x \supseteq y$. We call $L(\A)$ the \emph{intersection poset} of $\A$. 

For a finite poset $P$ with $\0$, the \emph{M\"{o}bius function} $\mu:P\to \mathbb{Z}$ is defined by
$$
\mu(\0)=1\quad\mbox{and}\quad \mu(x)=-\sum_{y<x} \mu(y).
$$

\begin{definition}
The \emph{characteristic polynomial} $\chi_{\A}(t)$ of the arrangement $\A$ is defined by
$$
\chi_{\A}(t):=\sum_{x \in L(\A)} \mu(x)\,t^{\dim(x)},
$$
where $\dim(x)$ is the dimension of $x$ as an affine subspace of $V$.
\end{definition}
The characteristic polynomial plays an important role in analyzing arrangements. One of the fundamental result is the following theorem.
\begin{theorem}[Zaslavsky \cite{Za}]
 For any arrangement $\A$ in $\real^n$, we have
\begin{equation*}\label{eq:Zas}
r(\A)=(-1)^n \,\chi_{\A}(-1).
\end{equation*}
\end{theorem}

In general, it is hard to compute the characteristic polynomial of an arrangement $\A$. However,
if $\A$ is in $\mathbb{Q}^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 $\fld_p$ be the finite field of order $p$. If $H$ is a hyperplane of $\A$ in $\mathbb{Q}^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 $\fld_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)$.
\begin{theorem}[Athanasiadis \cite{Ath}]
Let $\A$ be an arrangement in $\mathbb{Q}^n$. If $L(\A) \cong L(\A_q)$ for some prime $q$, then
$$
\chi_{\A}(q)= \left|\, \fld_q^{\,n} - \bigcup_{H\in \A_q} H\,\right|
= q^n - \left|\,\bigcup_{H\in \A_q} H\, \right|\,,
$$
which is called the \emph{finite field method}.
\end{theorem}

We now consider two special hyperplane arrangements: the {\em Catalan arrangement} and the {\em threshold arrangement}.
The {\em Catalan arrangement}~$\Cat_n$ is given by
$$x_i - x_j = 0,1,-1 \quad 1\leq i<j \leq n.$$
The characteristic polynomial of $\Cat_n$  is
\begin{equation*}\label{eq:cat-c}
\chi_{\Cat_n}(t)=t(t-n-1)(t-n-2)\cdots(t-2n+1).
\end{equation*}
Applying Zaslavsky's theorem,
we have
\begin{equation*}\label{eq:cat-r}
r(\Cat_n)=(2n)(2n-1)\cdots(n+2)=n!C_n,
\end{equation*}
where $C_n = \frac{1}{n+1}\binom{2n}{n}$ is the $n$-th Catalan number \seqnum{A000108}. 

The {\em threshold arrangement} ${\mathcal T}_n$ is given by
$$x_i + x_j =0,\quad  1\leq i<j \leq n .$$
The ``threshold" comes from threshold graphs introduced by
Chv\'atal and Hammer \cite{CH}.
There is a canonical bijection between the set of regions of ${\mathcal T}_n$ and the set of threshold graphs on the vertex set $[n]:=\{ 1,2,\ldots,n \}$. The number of threshold graphs appears in \seqnum{A005840}.
Stanley \cite[p.\ 473]{Sta3} showed that 
the exponential generating function for the characteristic polynomial
of ${\mathcal T}_n$ is given by
\begin{equation*}
\sum_{n\geq 0} \chi_{{\mathcal T}_n}(t)\frac{x^n}{n!}=(1+x)(2e^{x}-1)^{{(t-1)}/{2}}.
\label{eqn:thr-c}
\end{equation*}

\subsection{Delannoy numbers and Schr\"oder 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 \emph{Delannoy number} \seqnum{A008288}. For an nonnegative integer $n$, $D(n,n)$ is called the \emph{central Delannoy number} \seqnum{A001850}. The following properties of Delannoy numbers are well known \cite[p.\ 81]{Comt}.
\begin{proposition}
The Delannoy number $D(p,q)$ satisfies the following:
\begin{enumerate} 
\item The Delannoy number $D(p,q)$ has two expressions
\begin{align}
D(p,q)&= \sum_{d \ge 0} \binom{q}{d}\binom{p+q-d}{q}, \label{id_Del1}\\ 
D(p,q)&= \sum_{d \ge 0}  2^d \binom{p}{d}\binom{q}{d}. \label{id_Del2}
\end{align}  
\item The Delannoy number $D(p,q)$ satisfies the recurrence relation
\begin{equation} \label{rec_Del}
D(p,q)=D(p-1,q)+D(p,q-1)+D(p-1,q-1).
\end{equation}
\item The generating function $D(x)$ for $D(n,n)$ is
\begin{equation} \label{gf_cDel}
D(x):=\sum_{n\ge 0}D(n,n)x^n  = \frac{1}{\sqrt{1-6x+x^2}}.
\end{equation} 
\end{enumerate}
\end{proposition}

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 \emph{Schr\"oder number} \seqnum{A006318}.
The following properties of Schr\"oder numbers are well known \cite{Sul}.

\begin{proposition}
The Schr\"oder number $r_n$ satisfies the following:
\begin{enumerate} 
\item The Schr\"oder number $r_n$ satisfies the recurrence relation
$$
r_n=r_{n-1}+\sum_{k=0}^{n-1}r_k \,r_{n-1-k}\,,\quad r_0=1.
$$
\item The generating function $R(x)$ for $r_n$ is
\begin{equation} \label{gf_Sch}
R(x):=\sum_{n\ge 0}r_n x^n  = \frac{1-x-\sqrt{1-6x+x^2}}{2x}.
\end{equation}
\end{enumerate}
\end{proposition}

\section{Main result}
\label{sec3}

Recall that the Catalan threshold arrangement is defined by 
 \begin{equation} \label{def:catarr}
x_i + x_j =0,1,-1,\quad 1 \leq i < j \leq n.
\end{equation}
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.

\subsection{The characteristic polynomial of $\CT_n$}
Let $X$ be the set defined by 
\begin{equation} \label{eq:setX}
X=\{(a_1,\ldots,a_n)\in \fld_q^n\mid a_i+ a_j \ne 0,1,-1,~\mbox{for}~ i< j \}.
\end{equation}
By the finite field method, there exist infinitely many odd primes $q=2r+1$ such that
\begin{equation*}
\cpct(q)= |X|.
\end{equation*}
Let $G_q$ be a simple graph such that
$$V(G_q)=\fld_q \quad \mbox{and}\quad E(G_q)=\{\,\{u,v\}\,|\,u,v\in \fld_q~\mbox{with}~u+v=0,1,-1 \,\}.$$
See Figure~\ref{fig:Gq} for $G_{11}$.
\begin{figure} 
\centering
\begin{pspicture}
(6,2)
\setlength{\unitlength}{1cm}\thicklines
\put(1.5,0.5){
\put(0,0){\line(0,1){1}}
\put(1,0){\line(0,1){1}}
\put(2,0){\line(0,1){1}}
\put(3,0){\line(0,1){1}}
\put(4,0){\line(0,1){1}}

\put(0,0){\psline(0,0)(-0.8,0.5)}
\put(0,0){\psline(0,1)(-0.8,0.5)}
\put(0,0){\line(1,0){4}}
\put(0,1){\line(1,0){4}}
\put(0,1.2){\makebox(0,0){$-1$}}
\put(1,1.2){\makebox(0,0){$2$}}
\put(2,1.2){\makebox(0,0){$-3$}}
\put(3,1.2){\makebox(0,0){$4$}}
\put(4,1.2){\makebox(0,0){$-5$}}
\put(0,-.2){\makebox(0,0){$1$}}
\put(1,-.2){\makebox(0,0){$-2$}}
\put(2,-.2){\makebox(0,0){$3$}}
\put(3,-.2){\makebox(0,0){$-4$}}
\put(4,-.2){\makebox(0,0){$5$}}

\put(-1,0.5){\makebox(0,0){$0$}}
}

\end{pspicture}
\caption{Graph $G_{11}$}\label{fig:Gq}
\end{figure}
We can regard an element $(a_1,\ldots,a_n)$ in $\fld_q^n$ as a function $f:[n]\to \fld_q$ satisfying $f(i)=a_i$ for all $i=1,2,\ldots,n$.
It is obvious that $f\in\fld_q^n$ belongs to $X$ if and only if $f$ satisfies the following two conditions.
\begin{enumerate}
\item[(C1)] The image of $f$, i.e., $f([n])$ is an independent set of $G_q$, and
\item[(C2)] $|f^{-1}(0)|\le 1$, $|f^{-1}(r)|\le 1$, and $|f^{-1}(-r)|\le 1$ hold.
\end{enumerate}
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=\emptyset$ is always an independent set.
Now, we will count the number of functions $f:[n]\to \fld_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,\ldots,m\}\cup\{1',2',\ldots,m'\}$ with the edge set
$$E(A_m)=\{\{i,i+1\}\,|\,1\le i \le m-1 \}\cup\{\{i',(i+1)'\}\,|\,1\le i \le m-1 \}
\cup\{\{i,i'\}\,|\,1\le i \le m \},$$
for $m \ge 1$ and $A_0$ be the empty graph.
We also define the graph $B_m$ by $A_{m+1} - (m+1)'$. See Figure~\ref{fig:AB} for $A_3$ and $B_3$.

\begin{figure} 
\centering
\begin{pspicture}
(9,2)
\setlength{\unitlength}{1cm}\thicklines
\put(1,0.5){
\put(0,0){\line(0,1){1}}
\put(1,0){\line(0,1){1}}
\put(2,0){\line(0,1){1}}

\put(0,0){\line(1,0){2}}
\put(0,1){\line(1,0){2}}
\put(0,1.2){\makebox(0,0){$1'$}}
\put(1,1.2){\makebox(0,0){$2'$}}
\put(2,1.2){\makebox(0,0){$3'$}}
\put(0,-.2){\makebox(0,0){$1$}}
\put(1,-.2){\makebox(0,0){$2$}}
\put(2,-.2){\makebox(0,0){$3$}}

\put(-0.5,0.5){\makebox(0,0){$A_3$:}}
}
\put(5.5,0.5){
\put(0,0){\line(0,1){1}}
\put(1,0){\line(0,1){1}}
\put(2,0){\line(0,1){1}}

\put(0,0){\line(1,0){3}}
\put(0,1){\line(1,0){2}}
\put(0,1.2){\makebox(0,0){$1'$}}
\put(1,1.2){\makebox(0,0){$2'$}}
\put(2,1.2){\makebox(0,0){$3'$}}
\put(0,-.2){\makebox(0,0){$1$}}
\put(1,-.2){\makebox(0,0){$2$}}
\put(2,-.2){\makebox(0,0){$3$}}
\put(3,-.2){\makebox(0,0){$4$}}

\put(-0.5,0.5){\makebox(0,0){$B_3$:}}
}

\end{pspicture}
\caption{Graphs $A_3$ and $B_3$}\label{fig:AB}
\end{figure}
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)=\delta_{0,k}$, for the empty graph $A_0$ which has the unique independent set $\emptyset$.
\begin{lemma} \label{lem:abD}
For nonnegative integers $k$ and $m$, we have 
\begin{align}
 b(m,k)&=D(m-k+1,k) \label{id_b-Del},\\
 a(m,k+1)&=D(m-k,k+1)-D(m-k,k). \label{id_a-Del}
\end{align}
Here $D(p,q)$ is the {Delannoy number}.
\end{lemma}
\begin{proof}
To select a $k$-independent set $I$ of $B_m$, we can consider three cases: (i) $m \notin I$ and $m+1 \notin I$, (ii)  $m \notin I$ and $m+1 \in I$, (iii)  $m \in I$. From this, we see that
\begin{equation*} \label{rec_b}
b(m,k)=b(m-1,k)+b(m-1,k-1)+b(m-2,k-1),
\end{equation*}
which shows that $b(m,k)$ satisfies the same recursion as $D(m-k+1,k)$ in \eqref{rec_Del}.

We now check the initial conditions. Note that
$$
b(m,k)=
\begin{cases}
0, & \text{$k-m \ge 2$;}  \\
1, & \text{$k-m=1$ or $k=0$;} \\
3, & \text{$k=m=1$,} 
\end{cases}
\quad\mbox{and}\quad
D(p,q)=
\begin{cases}
0, & \text{$p\le -1$;}  \\
1, & \text{$p=0$ or $q=0$;} \\
3, & \text{$p=q=1$.} 
\end{cases}
$$
Thus, $b(m,k)=D(m-k+1,k)$ for all nonnegative integer $m$ and $k$.

Next, we prove  \eqref{id_a-Del}. To select a $(k+1)$-independent set $J$ of $B_{m}$, we can consider two cases: 
(i) $m+1\notin J$ and (ii) $m+1\in 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)$.
\end{proof}
From Lemma~\ref{lem:abD} we can easily get a number of functions $f$ satisfying 
the condition (C1).
\begin{lemma} \label{lem:select}
For positive integers $m$ and $n$, the number of $f:[n]\to V(A_m)$ satisfying that $f([n])$ is an independent set of $A_m$ is
\begin{equation*} \label{eq:select-a}
\sum_{1 \le j \le \min(m,n)} a(m,j) \,S(n,j)\,j!,
\end{equation*}
and
the number of $f:[n]\to V(B_m)$ satisfying that $f([n])$ is an independent set of $B_m$ is
\begin{equation*} \label{eq:select-b}
\sum_{1 \le j \le \min(m,n)} b(m,j) \,S(n,j)\,j!,
\end{equation*}
where $S(n,j)$ is the Stirling number of the second kind.
\end{lemma}
For a nonnegative integers  $m$ and $n$, let
$a_m(n)$ and $b_m(n)$ be
\begin{gather} 
a_m(n):=\sum_{0 \le j \le \min(m,n)} a(m,j) \,S(n,j)\,j! \label{eq:amn}\,,\\
b_m(n):=\sum_{0 \le j \le \min(m,n)} b(m,j) \,S(n,j)\,j! \label{eq:bmn}\,.
\end{gather}
Now we go back to Catalan threshold arrangements.
To compute the size of $X$ in~\eqref{eq:setX}, we should also regard the second condition (C2). Among $f=(f(1),\ldots,f(n))\in X$, each $0$, $r$ and $-r$ can be chosen at most once. So we have four cases to consider. 
\begin{enumerate}
\item[(i)] None of them are selected.
\item[(ii)] Only $0$ is selected.
\item[(iii)] $0$ is not selected and either $r$ or $-r$ is selected. 
\item[(iv)] $0$ is selected and either $r$ or $-r$ is selected. 
\end{enumerate}
By Lemma~\ref{lem:select}, the number of elements $f$ of the case (i) is
$$\sum_{0 \le j \le \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\sum_{0 \le j \le \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.

\begin{theorem}[Main result]\label{thm:ch-poly}
The characteristic polynomial of the Catalan threshold arrangement $\CT_n$ is given by
\begin{align} \label{eq:main}
\chi_{\CT_n}(t)
&= n!\sum_{k=0}^{n}\sum_{\ell=0}^k \alpha_{n,k,\ell}\,\frac{\dff{t-2k-1}_\ell}{\ell !}\,,
\end{align}
where $\dff{x}_k$ is defined by $\dff{x}_0=1$ and $\dff{x}_k=x(x-2)(x-4)\cdots(x-2k+2)$ for $k \ge 1$. Here $\alpha_{n,k,\ell}$ is given by
$\alpha_{0,0,0}=\alpha_{1,0,0}=1$, and for $n \ge 2$ or $k^2+\ell^2>0$,
$$
\alpha_{n,k,\ell}
=\binom{k-1}{\ell-1}{s}_{n,k}
+\binom{k-2}{\ell-1}{s}_{n-1,k-1}
+2\binom{k-1}{\ell}{s}_{n-1,k-1}
+2\binom{k-2}{\ell}{s}_{n-2,k-2}\,,
$$
where ${s}_{n,k}$ is defined by ${s}_{n,k}=\frac{k!}{n!}S(n,k)$.
\end{theorem}

\begin{proof}
Since we can easily check that \eqref{eq:main} holds for $n\le 2$,
we may assume $n \ge 3$.
By considering all the cases (i)--(iv), we have
\begin{align}\label{lin-combin}
\chi_{\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)\\
=& \sum_{j\geq 0}a\left(\frac{q-3}{2},j\right)\,j!\,S(n,j)
+ n \sum_{j\geq 0}a\left(\frac{q-5}{2},j\right)\,j!\,S(n-1,j)\notag\\
&+ 2n \sum_{j\geq 0}b\left(\frac{q-5}{2},j\right)\,j!\,S(n-1,j)
+ 2n(n-1) \sum_{j\geq 0}b\left(\frac{q-7}{2},j\right)\,j!\,S(n-2,j)\,,\notag
\end{align}
for infinitely many primes $q=2r+1$. 
Since $n \ge 3$, we can ignore the case $j=0$. By applying~\eqref{id_b-Del},~\eqref{id_a-Del}, and~\eqref{id_Del2},  we have
\begin{align*}
\chi_{\CT_n}(t)
=& \sum_{j=1}^{n}\sum_{d=1}^j S(n,j)\frac{j!}{d!}\binom{j-1}{d-1}\dff{t-2j-1}_d\\
&+ \sum_{j=1}^{n}\sum_{d=1}^j n\,S(n-1,j)\frac{j!}{d!}\binom{j-1}{d-1}\dff{t-2j-3}_d\\
&+ \sum_{j=1}^{n}\sum_{d=0}^j 2n\,S(n-1,j)\frac{j!}{d!}\binom{j}{d}\dff{t-2j-3}_d\\
&+ \sum_{j=1}^{n}\sum_{d=0}^j 2n(n-1)\,S(n-2,j)\frac{j!}{d!}\binom{j}{d}\dff{t-2j-5}_{d} \,.
\end{align*}
Let $\left[\dff{t-2k-1}_{\ell} \right] F(x)$ be the ``coefficient" of $\dff{t-2k-1}_{\ell}$ in $F(x)$. Then
\begin{align*}
\left[\dff{t-2k-1}_{\ell}\right]&\chi_{\CT_n}(t)
\,=\,S(n,k)\frac{k!}{\ell !}\binom{k-1}{\ell-1}
+nS(n-1,k-1)\frac{(k-1)!}{\ell !}\binom{k-2}{\ell-1}\\
&+2nS(n-1,k-1)\frac{k!}{\ell !}\binom{k-1}{\ell}
+2n(n-1)S(n-2,k-2)\frac{(k-2)!}{\ell !}\binom{k-2}{\ell}.
\end{align*}
Since $\alpha_{n,k,\ell}=\frac{\ell !}{n!}\left[\dff{t-2k-1}_{\ell}\right]\chi_{\CT_n}(t)$, we have
\begin{align*}
\alpha_{n,k,\ell}
=&\frac{k!}{n!} S(n,k)\binom{k-1}{\ell-1}
+\frac{(k-1)!}{(n-1)!}S(n-1,k-1)\binom{k-2}{\ell-1} \\
&+2\frac{(k-1)!}{(n-1)!}S(n-1,k-1)\binom{k-1}{\ell}
+2\frac{(k-2)!}{(n-2)!}S(n-2,k-2)\binom{k-2}{\ell} \,.
\end{align*}
\end{proof}
For instance $\chi_{\CT_0}(t)=1$,~~$\chi_{\CT_1}(t)=t$,~~$\chi_{\CT_2}(t)=t^2 -3t$,~~and
\begin{eqnarray*}
\chi_{\CT_3}(t) &=& t^3-9t^2+27t-27 \\
\chi_{\CT_4}(t) &=& t^4-18t^3+135t^2-483t+675\\
\chi_{\CT_5}(t) &=& t^5-30t^4+405t^3-2955t^2+11340t-17993.
\end{eqnarray*}
Applying Zaslavsky's theorem, we have the following result.
\begin{corollary}
The number of regions of the Catalan threshold arrangement $\CT_n$ is given by
\begin{align*}
r(\CT_n)
&= (-1)^n n!\sum_{k=0}^{n}\sum_{\ell=0}^k \alpha_{n,k,\ell}\,(-2)^{\ell} \binom{k+1}{\ell}\,,
\end{align*}
where $\alpha_{n,k,\ell}$ is defined in Theorem~\ref{thm:ch-poly}.
\end{corollary}
The sequence $(r(\CT_n))_{n \geq 0}$ starts with
$$1,\,1,\,4,\,64,\,1312,\,32724,\,979316,~\ldots$$
which is not listed in the On-Line Encyclopedia of Integer Sequences \cite{Slo1}.

\subsection{The exponential generating function for $\cpct(t)$}
Recall the definition of $b_m(n)$ in \eqref{eq:bmn}. By the exponential formula we have
$$
b_m(n)= \sum_{j \ge 0} b(m,j) \left[\frac{x^n}{n!} \right] (e^x-1)^j,
$$
where $\left[\frac{x^n}{n!} \right] F(x)$ is the coefficient of $\frac{x^n}{n!}$ in the power series $F(x)$.
Thus
\begin{equation} \label{eq:gen-amn-m}
\sum_{n \ge 0} b_m(n)\frac{x^n}{n!} = \sum_{j \ge 0} b(m,j)(e^x-1)^j.
\end{equation}
It is easy to show that
\begin{equation} \label{eq:gen-amn-l}
\sum_{j \ge 0} D(j+\alpha,j){z^j} = \frac{{R(z)}^{\alpha}}{D(z)}\,,
\end{equation}
where $D(z)$ and $R(z)$ are given in~\eqref{gf_cDel} and~\eqref{gf_Sch}.
Note that this is an extended version of the following well known (for example~\cite[p.\ 54]{Wi}) identity

\begin{equation*} 
\sum_{j \ge 0} \binom{2j+\alpha}{j}{z^j} = \frac{{C(z)}^{\alpha}}{\sqrt{1-4z}}\,,
\end{equation*}
where $C(z)$ is the ordinary generating function for the Catalan number.

Recall $b(m,j)=D(m-j+1,j)$. By \eqref{id_Del1}, we see that $b(m,j)$ can be considered as a monic polynomial in $m$ with degree $j$.
By simple calculation, we have
\begin{align*}
D(m-j+1,j)
&=\sum_{0\le d \le j} \binom{j}{d} \binom{m+1-d}{j}\\
&=(-1)^j \sum_{0\le d \le j} \binom{j}{d} \binom{j-m-2+d}{j}\\
&=(-1)^j \sum_{0\le c\le j} \binom{j}{c} \binom{2j-m-2-c}{j} \tag{$c=j-d$}\\
&=(-1)^j D(j-m-2,j).
\end{align*}
By replacing $\alpha=-m-2$ and $z=-(e^x-1)$, we obtain
\begin{equation} \label{eq:gen-amn-r}
\sum_{j \ge 0} D(j+\alpha,j){z^j} =\sum_{j \ge 0} b(m,j)(e^x -1)^{j}\,.
\end{equation}
Combining \eqref{eq:gen-amn-m}, \eqref{eq:gen-amn-l}, and \eqref{eq:gen-amn-r} yields that
\begin{equation*} \label{eq:gen-amn}
\sum_{n \ge 0} b_m(n)\frac{x^n}{n!} = \frac{{R(1-e^x)}^{-m-2}}{D(1-e^x)}\,.
\end{equation*}
Meanwhile, from~\eqref{eq:amn}, we deduce that
\begin{align*} \label{eq:gen-amn1}
\sum_{n \ge 0} a_m(n)\frac{x^n}{n!}
&=\sum_{n\ge 0}\sum_{j\ge 0} a(m,j)S(n,j)j! \frac{x^n}{n!} \\
&=\sum_{n\ge 0}\sum_{j\ge 0} b(m-1,j)S(n,j)j!\frac{x^n}{n!} 
+\sum_{n\ge 0}\sum_{j\ge 1} b(m-2,j-1)S(n,j)j! \frac{x^n}{n!} \\  
&= \sum_{n \ge 0} b_{m-1}(n)\frac{x^n}{n!}+\sum_{j\ge 1} b(m-2,j-1)(e^x -1)^j\\
&= \sum_{n \ge 0} b_{m-1}(n)\frac{x^n}{n!}+(e^x-1)\sum_{n \ge 0} b_{m-2}(n)\frac{x^n}{n!} .
\end{align*}
Thus we have 
\begin{equation*} \label{eq:gen-amn1}
\sum_{n \ge 0} a_m(n)\frac{x^n}{n!} 
= \frac{{R(1-e^x)}^{-m-1}-{R(1-e^x)}^{-m}}{D(1-e^x)}\,.
\end{equation*}

As seen in~\eqref{lin-combin}, the characteristic polynomial $\chi_{\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
$\chi_{\CT_n}(t)$:
\begin{equation}\label{eq:gen-cha-ct}
\sum_{n \geq 0} \chi_{\CT_n}(t)\frac{x^n}{n!} ~=~\frac{{R(1-e^x)}^{\frac{1-t}{2}}}{D(1-e^x)}
\Big(1+xR(1-e^x) \Big) \Big(1+2x-(1-e^x)R(1-e^x) \Big)\,.
\end{equation}
Put $t=-1$ and $x=-x$ in~\eqref{eq:gen-cha-ct} to get
the exponential generating function for $r(\CT_n)$:
\begin{equation}\label{eq:gen-reg-ct}
\sum_{n \geq 0} r(\CT_n)\frac{x^n}{n!} ~=~
\frac{{R(1-e^{-x})}}{D(1-e^{-x})}
\Big(1-xR(1-e^{-x}) \Big) \Big(1-2x-(1-e^{-x})R(1-e^{-x}) \Big)\,.
\end{equation}

\subsection{Remark}
Consider a generalized threshold arrangement such as
\begin{equation*} \label{arr:gen}
x_i + x_j =-\ell,-\ell+1,\ldots,m-1,m\quad  1\leq i < j \leq n,
\end{equation*}
for nonnegative integers $\ell$ and $m$. We denote the arrangement by $\T_n^{[-\ell,m]}$. By parallel translation, $\T_n^{[-\ell,m]}$ is transformed to either $\T_n^{[-k+1,k]}$ or $\T_n^{[-k,k]}$, which can be called an \emph{extended Shi threshold arrangement} or an \emph{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 \ge 2$.

\section{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.

\begin{thebibliography}{99}

\bibitem{Ard}
F. Ardila,
Computing the {T}utte polynomial of a hyperplane arrangement,
{\em Pacific J. Math.} {\bf 230} (2007), 1--26.

\bibitem{Ath}
C. A. Athanasiadis,
Characteristic polynomials of subspace arrangements and finite fields,
{\em Adv. Math.} {\bf 122} (1996), 193--233.

\bibitem{CH}
V. Chv{\'a}tal and P. L. Hammer,
Aggregation of inequalities in integer programming,
{\em Ann. of Discrete Math.} {\bf 1} (1977), 145--162.

\bibitem{Comt}
L. Comtet,
{\em Advanced Combinatorics},
D. Reidel Publishing Co., 1974.

\bibitem{OT}
P. Orlik and H. Terao,
{\em Arrangements of Hyperplanes},
Springer-Verlag, 1992.

\bibitem{PoSt}
A. Postnikov and R. P. Stanley,
Deformations of Coxeter hyperplane arrangements,
{\em J. Combin. Theory Ser. A} {\bf 91} (2000), 544--597.

\bibitem{Seo}
S. Seo,
Shi threshold arrangement,
{\em Electron. J. Combin.} {\bf 19} (3) (2012), {\#}P39.

\bibitem{Slo1} 
N. J. A. Sloane, 
The On-Line Encyclopedia of Integer Sequences.
Published electronically at \url{http://oeis.org}, 2016.

\bibitem{Sta3}
R. P. Stanley,
An introduction to hyperplane arrangements,
in E. Miller, V. Reiner, and B. Sturmfels, eds.,
{\em Geometric Combinatorics}, Amer. Math. Soc., 2007, pp.~389--496. 

\bibitem{Sul}
R. A. Sulanke,
Bijective recurrences concerning {S}chr\"oder paths,
{\em Electron. J. Combin.} {\bf 5} (1998), {\#}R47.

\bibitem{Wi}
H. S. Wilf,
{\em generatingfunctionology},
Academic Press Inc., 1994.

\bibitem{Za}
T. Zaslavsky,
Facing up to arrangements: face-count formulas for partitions of
space by hyperplanes,
{\em Mem. Amer. Math. Soc.} {\bf 1} (1975), No.~154.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary 52C35;
Secondary 05A15.

\noindent \emph{Keywords:}
hyperplane arrangement, Catalan threshold arrangement, finite field method.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received July 27 2016;
revised version received December 22 2016.  Published in
{\it Journal of Integer Sequences}, December 23 2016.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in

\end{document}