% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

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

\newcommand{\A}{{\mathcal A}}
\newcommand{\D}{{\mathcal D}}
\newcommand{\E}{{\mathcal E}}
\newcommand{\F}{{\mathcal F}}
\newcommand{\G}{{\mathcal G}}
\newcommand{\mH}{{\mathcal H}}
\newcommand{\B}{{\mathcal B}}
\newcommand{\R}{{\mathcal R}}
\newcommand{\T}{{\mathcal T}}
\newcommand{\Shi}{{\mathcal S}}
\newcommand{\ST}{{\mathcal{ST}}}
\newcommand{\real}{{\mathbb R}}
%\newcommand{\perm}{{\mathcal S}}
\newcommand{\mS}{{\mathcal S}}
\newcommand{\ga}{\alpha}
\newcommand{\gb}{\beta}
\newcommand{\gc}{\gamma}
\newcommand{\gd}{\delta}
\newcommand{\ve}{\varepsilon}
\newcommand{\rk}{{\rm rk}}
\newcommand{\0}{\hat{0}}
\newcommand{\fld}{{\mathbb F}}
\newcommand{\cpst}{\chi_{\ST_n}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Shi threshold arrangement}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address

\author{Seunghyun Seo\\
%\thanks{Research supported by Basic Science Research Program through
%the National Research Foundation of Korea funded by the Ministry of Education, Science and Technology(2011-0008683).}\\
\small Department of of Mathematics Education\\[-0.8ex]
\small Kangwon National University\\[-0.8ex]
\small Chuncheon 200-701, Republic of Korea\\
\small\tt shyunseo@kangwon.ac.kr\\
%\and
%Forgotten Second Author \qquad  Forgotten Third Author\\
%\small School of Hard Knocks\\[-0.8ex]
%\small University of Western Nowhere\\[-0.8ex]
%\small Nowhere, Australasiaopia\\
%\small\tt \{fsa,fta\}@uwn.edu.ao
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Feb 8, 2012}{Aug 29, 2012}\\
\small Mathematics Subject Classifications: 52C35, 05A15}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
 Richard Stanley suggested the problem of finding
the characteristic polynomial of a certain hyperplane arrangement defined by
$x_i + x_j=0,1$, which is called the Shi threshold arrangement.
We present the answer of the problem, using the finite field method.

  % keywords are optional
  %\bigskip\noindent \textbf{Keywords:} hyperplane arrangement; Shi threshold arrangement; finite field method
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}
Much work has been devoted in recent years to studying hyperplane arrangements, especially finding their characteristic polynomials and number of regions. Several authors have worked on computing the number of regions of specific hyperplane arrangements. See for examples \cite{Ath-am,PoSt,Ard}.

Stanley's paper \cite{Sta3} on hyperplane arrangements contain classic and more recent results in this field, together with numerous problems.
We consider the following problems
\cite[p.~473]{Sta3}
of finding the characteristic polynomial of the following hyperplane arrangement:
$$
x_i + x_j =0,1,\quad 1 \leq i < j \leq n.
$$
Stanley called the arrangement by ``Shi threshold arrangements"

The present paper solves this problem by the finite field method (see \cite{Ath-am, CR, Sta3}). In Section 2, we introduce the basic notations of hyperplane arrangements. In Section 3, we find the characteristic polynomial of the Shi threshold arrangement. We also calculate the exponential generating function for the characteristic polynomial of the Shi threshold arrangement.
In Section 4, we comment on some related works and further studies.

\section{Preliminaries}

We recall some of the basic concepts of hyperplane arrangements.
For a more thorough introduction, see \cite{OT, Sta2}.

\subsection{Intersection posets and characteristic polynomials}
Given a field $K$ and a positive integer $n$, a \emph{hyperplane arrangement} of dimension $n$ over $K$ is a finite set of affine hyperplanes in $V=K^n$.
We will refer to hyperplane arrangements simply as arrangements.

Now, let $V=\real^n$. A \emph{region} of an arrangement $\A$ is a connected component of the complement $X$ of the hyperplanes:
$$X=\real^n - \bigcup_{H \in \A} H.$$
Let $R(\A)$ denote the set of regions of $\A$, and let $r(\A)$ be the number of regions.

Given an arrangement $\A$ in $V$, let $L(\A)$ be the set of all nonempty intersections of hyperplanes in $\A$, including $V$. Define $x \leq y$ in $L(\A)$ if $x \supseteq y$ as a subsets of $V$. We call $L(\A)$ the \emph{intersection poset} of $\A$. It is easy to show that $L(\A)$ is a graded poset with the rank function $\rk:L(\A)\to \mathbb{N}$ defined by
$$\rk(x)=\dim(V)-\dim(x)=n-\dim(x),$$
where $\dim(x)$ is the dimension of $x$ as an affine subspace of $V$.

Given a finite poset $P$ with $\0$, the \emph{M\"{o}bious function} $\mu:P\to \mathbb{Z}$ is defined by
$$
\mu(\0)=1\quad\mbox{and}\quad \mu(x)=-\sum_{y<x} \mu(y).
$$
Originally, the M\"{o}bious function $\mu$ goes from the set of all intervals of $P$ to $\mathbb{Z}$. But we will only consider the intervals of the form $[\0,x]$, which are identified with $x \in P$.

\begin{definition}
The 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)}
$$
\end{definition}
The characteristic polynomial plays an important role in the theory of arrangements. One of the important result is as follows.
\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}

%For an example, consider the braid arrangement $\B_n$ given by
%$$x_i - x_j =0, \quad 1 \leq i < j \leq n.$$
%It is easy to show that $L(\B_n)$ is isomorphic to the poset $\Pi_n$ of all partitions on $[n]$
%ordered by refinement (see \cite[p.~97,\,129]{Sta1}).
%Thus the characteristic polynomial of $\B_n$ is given by
%\begin{align*}
%\chi_{\B_n}(t)=t(t-1)\cdots(t-n+1).
%\end{align*}
%By equation \eqref{eq:Zas}, the number of region of $\B_n$ is equal to $n!$, which is the number of all permutations of $[n]$.
\subsection{Finite field method}
In general, given an arrangement $\A$, it is hard to compute the characteristic polynomial of $\A$. However,
if $\A$ in $\mathbb{Q}^n$, (i.e., all coefficients of hyperplanes in $\A$ are rational), then there is a
powerful method for computing its characteristic polynomial. Given 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 regard all the coefficients of the equation of $H$ as integers. In this case we can take coefficients modulo $p$ and 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}[Crapo, Rota \cite{CR}; Orlik, Terao \cite{OT}; Athanasisadis \cite{Ath-am}]
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}
%For an example, consider a Coxeter arrangement $\D_n$ defined by
%$$x_i \pm x_j = 0, \quad 1\leq i<j \leq n.$$
%By the finite field method, we have
%\begin{eqnarray*}
%\chi_{\D_n}(q)
%&=& \big|\, \{(a_1,\ldots,a_n)\in \fld_q^n\mid a_i\ne a_j,~a_i\ne -a_j,~\mbox{for}~ i\ne j \} \,\big|\\
%&=& (q-1)(q-3)\cdots(q-2n+1) +\, n\,(q-1)(q-3)\cdots(q-2n+3)\\
%&=& (q-1)(q-3)\cdots(q-2n+3)(q-n+1),
%\end{eqnarray*}
%for infinitely many prime $q$'s. Thus the characteristic polynomial of $\D_n$ is given by
%$$\chi_{\D_n}(t) = (t-1)(t-3)\cdots(t-2n+3)(t-n+1).$$
%Using Zaslavsky's theorem, we also get the number of region of $\D_n$\,:
%$$r(\D_n) =(-1)^n\chi_{\D_n}(-1)= 2\cdot4 \cdots (2n-2)\cdot n = 2^{n-1}(n-1)!\,.$$

\subsection{Shi arrangement and threshold arrangement}
Now we consider two special hyperplane arrangements.
The {\em Shi arrangement} $\Shi_n$ is given by
$$x_i - x_j = 0,1, \quad 1\leq i<j \leq n,$$
which was first appeared in \cite[\S 7]{Shi}. Using Poincar\'{e} polynomials, Headley \cite{Hea} found that the characteristic polynomial of $\Shi_n$  is
\begin{equation}\label{eq:shi-c}
\chi_{\Shi_n}(t)=t(t-n)^{n-1}.
\end{equation}
Athanasiadis \cite{Ath-am} proved it by the finite field method.

Applying Zaslavsky's theorem to the equation \eqref{eq:shi-c}, we have
\begin{equation}\label{eq:shi-r}
r(\Shi_n)=(n+1)^{n-1}.
\end{equation}
%which is the number of
%all parking functions of length $n$ or all labeled trees on $[n+1]$.
Pak and Stanley \cite[\S 4]{Sta4} and Athanasiadis and Linusson \cite{AL} proved \eqref{eq:shi-r}
bijectively. They gave bijections from $\R(\Shi_n)$ to the set of all parking functions on $[n]$.

The {\em threshold arrangement} ${\mathcal T}_n$ is given by
$$x_i + x_j =0,\quad  1\leq i<j \leq n .$$
The notation ``threshold" comes from threshold graphs that were introduced by
Chv\'atal and Hammer \cite{CH}.
%One of the convenient definition is as following: a simple graph $G$ is {\em threshold}
%if every induced subgraph of $G$ has a dominating or an isolated vertex.
%Threshold graphs have many interesting properties (see \cite{PS,Sim,MR}).
%Given a threshold graph $G$, we can recursively select dominating or isolated vertices sets of $G$ in alternating order.
%Thus for $n \ge 2$, a threshold graphs on $[n]$ corresponds to an ``ordered" set partition
%$(B_1,\dots,B_k)$ of $[n]$, where the last block $B_k$ is not a singleton.
%Here is an interesting
%property of threshold graphs:
%Fix positive integer $n$ and set $[n]:=\{1,2,\dots,n\}$. Let $Z$ be the convex hull in $\real^n$
%generated by the set of all degree sequences $(d_1,\dot,d_n)$ of simple graphs on $[n]$.
%Peled and Srinivasan \cite{PS} proved that
There is a canonical bijection from ${\mathcal T}_n$ to the set of threshold graphs on $[n]$.
Therefore the exponential generating function for the number
of regions of ${\mathcal T}_n$ is given by
\begin{equation}
\sum_{n\geq 0} r({\mathcal T}_n)\frac{x^n}{n!}=\frac{e^x (1-x)}{2-e^{x}}.
\label{eqn:thr-r}
\end{equation}
Later, Stanley \cite[p.~473]{Sta3} showed that the exponential generating function for the characteristic polynomial %$\chi_{{\mathcal T}_n}(t)$
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}
Note that it is open to find a combinatorial interpretation of each coefficient of
$\chi_{{\mathcal T}_n}(t)$ as the number of certain threshold graphs.


\section{Shi threshold arrangement}
As a {\em generalized} threshold arrangement, we consider an arrangement defined by
$$
x_i + x_j =0,1,\quad 1 \leq i < j \leq n.
$$
Stanley \cite[p.~473]{Sta3} introduced the arrangement
and called the {\em Shi threshold arrangement}. Let $\ST_n$ denote the Shi threshold arrangement.
We will find the characteristic polynomial of Shi threshold arrangement and its exponential generating function.

\subsection{Characteristic polynomial of $\ST_n$}
From the finite field method, there exist infinitely many odd primes $q=2r+1$ such that
\begin{equation}
\cpst(q)= \big|\, \{(a_1,\ldots,a_n)\in \fld_q^n\mid a_i+ a_j \ne 0,~a_i + a_j \ne 1,~\mbox{for}~ i< j \} \,\big|\,.
\end{equation}
Let $X$ be the set $\{(a_1,\ldots,a_n)\in \fld_q^n\mid a_i+ a_j \ne 0,~a_i + a_j \ne 1,~\mbox{for}~ i< j \}$. Clearly we have $|X|=\cpst(q)$.
Given a sequence $(u_1,\ldots,u_q)=(0,1,-1,2,-2,\ldots,r,-r)$ of $\fld_q$,
let $Y$ be the set of all $n$-tuples
$(b_1,\ldots,b_n)\in \fld_q^{\,n}$ satisfying the following conditions:
\begin{itemize}
\item $|\,\{i \in [n]\mid b_i =0 \}\,| \le 1$ and $|\,\{i \in [n]\mid b_i =-r \}\,| \le 1.$
%Each $0$ and $-r$ can be chosen at most once.
\item If $u_j \in \{b_i \mid i\in[n]\}$ for some $j\in [q]$, then $\{u_{j-1},u_{j+1}\}\cap\{b_i \mid i\in[n]\}=\emptyset$.
%Two consecutive numbers $u_i$ and $u_{i+1}$ cannot be chosen for all $1\le i \le q-1$.
\end{itemize}
 It is obvious that $X$ and $Y$ are the same set which depends on $q$. Thus, to give $\cpst(q)$, it suffices to find the cardinality of $Y$.

\begin{lemma} \label{lem:select}
For positive integers $m$ and $n$,
let ${\bf u} = (u_1,\ldots,u_m)$ be a sequence of distinct $m$ elements. From the set $\{u_1,\ldots, u_m\}$,
choose $n$-tuples $(b_1,\ldots,b_n)$ in $\{u_1,\ldots, u_m\}^n$ such that no consecutive elements can be chosen.
Then the number of such ways is
\begin{equation} \label{eq:select}
\sum_{1 \le j \le \min(n,\lfloor\frac{m+1}{2} \rfloor)} \binom{m-j+1}{j} \,S(n,j)\,j!,
\end{equation}
where $S(n,j)$ is the Stirling number of the second kind.
\end{lemma}
\begin{proof}
let $Z$ be the set of all functions $f:[n]\to [m]$ such that the inverse images
$f^{-1}(\{i\})$ or $f^{-1}(\{i+1\})$ are empty for all $i=1,\ldots,m-1$.
Correspond an element $(b_1,\ldots,b_n)$ satisfying the condition
to a function $f\in Z$ via $f(i):=j$, where $b_i = u_j$.
It is obvious that the correspondence indeed a bijection.
If $f \in Z$ then the image $f([n])=A$ is the subset of $[m]$ such that
no consecutive numbers belong to $A$. Thus the number of selecting such $A$
is  equal to $\binom{m-j+1}{j}$. Once $A$ is chosen, the number of surjective functions
from $[n]$ to $A$ is equal to $j!\,S(n,j)$, which completes the equation~\eqref{eq:select}.
\end{proof}
For convention we allow $j=0$ in~\eqref{eq:select}, because $S(n,0)=0$ if $n>0$. For nonnegative integers  $m$ and $n$, let
$a_m(n)$ be
\begin{equation} \label{eq:amn}
a_m(n):=\sum_{0 \le j \le n} \binom{m-j+1}{j} \,S(n,j)\,j!\,,
\end{equation}
where $S(n,k)$ is the Stirling number of the second kind.
Now we go back to Shi threshold arrangements, i.e.,
$$
{\bf u} = (u_1,\ldots,u_q)= (0,1,-1,2,-2,\ldots,r,-r).
$$
To enumerate the set $Y$, we should regard the additional condition: Each $0$ and $-r$ can be chosen at most once. So we have three cases to consider.
\begin{enumerate}
\item Neither $0$ nor $-r$ are selected.
\item Either $0$ or $-r$ is selected.
\item Both $0$ and $-r$ are selected.
\end{enumerate}
By Lemma~\ref{lem:select}, the number of elements $(b_1,\ldots,b_n)$ of the first case is
$$\sum_{0 \le j \le \min(n, r)} \binom{2r-j}{j} \,S(n,j)\,j!,$$
which becomes $a_{2r-1}(n)$ for $r \ge n$, i.e., for infinitely many sufficiently large primes $q=2r+1$.
Similarly, the second case is $2n\, a_{2r-2}(n-1)$ and the third case is $n(n-1)\, a_{2r-3}(n-2)$ for infinitely many sufficiently large primes $q=2r+1$.
Thus we have the following result:
\begin{theorem}\label{thm:ch-poly}
The characteristic polynomial of the Shi-threshold arrangement $\ST_n$ is given by
\begin{align*}
\chi_{\ST_n}(t)
=& \sum_{j\geq 0}\,(t-j-1)_j\,S(n,j)
\,+\, 2n \sum_{j\geq 0}\,(t-j-2)_j\,S(n-1,j)\\
&+\, n(n-1) \sum_{j\geq 0}\,(t-j-3)_j\,S(n-2,j),
\end{align*}
where $(x)_k$ is defined by $(x)_0=1$ and $(x)_k=x(x-1)\cdots(x-k+1)$ for $k \ge 1$.
\end{theorem}
For instance $\chi_{\ST_0}(t)=1$,~~$\chi_{\ST_1}(t)=t$,~~$\chi_{\ST_2}(t)=t^2 -2t$,~~and
\begin{eqnarray*}
\chi_{\ST_3}(t) &=& t^3-6t^2+12t-8 \\
\chi_{\ST_4}(t) &=& t^4 -12t^3 +60t^2 - 142t +130\\
\chi_{\ST_5}(t) &=& t^5-20t^4+180t^3-870t^2+2190t-2252.
\end{eqnarray*}
Applying the Zaslovsky's Theorem, we have the followings.
\begin{corollary}
The number of regions in the Shi-threshold arrangement $\ST_n$ is given by
\begin{align*}
r(\ST_n)
=& \sum_{j\geq 0}\binom{2j+1}{j}\,j!\,(-1)^{n-j} S(n,j)
+ 2n \sum_{j\geq 0}\binom{2j+2}{j}\,j!\,(-1)^{n-j}S(n-1,j)\\
&+ n(n-1) \sum_{j\geq 0}\binom{2j+3}{j}\,j!\,(-1)^{n-j}S(n-2,j)\,.
\end{align*}
\end{corollary}
The sequence $\{r(\ST_n)\}_{n \geq 0}$ starts with
$$1,~1,~3,~27,~345,~5513,~106619,~2426819,~\ldots$$
which is not listed in the ``Online Encyclopedia of Integer Sequences".

\subsection{Generating function for $\chi_{\ST_n}(t)$}
Recall the definition of $a_m(n)$ in equation~\eqref{eq:amn}. By exponential formula we have
$$
a_m(n)= \sum_{j \ge 0} \binom{m-j+1}{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} a_m(n)\frac{x^n}{n!} = \sum_{j \ge 0} \binom{m-j+1}{j}(e^x-1)^j.
\end{equation}
It is well known (for example~\cite[p.~54]{Wi}) that
%According to Wilf's bo
\begin{equation} \label{eq:gen-amn-l}
\sum_{j \ge 0} \binom{2j+\alpha }{j}{z^j} = \frac{{C(z)}^{\alpha}}{\sqrt{1-4z}}\,,
\end{equation}
where $C(z)$ is the generating function for the Catalan number, i.e.,
$$C(z)=\frac{1-\sqrt{1-4z}}{2z}=\sum_{n\geq 0}\frac{1}{n+1}\binom{2n}{n} z^n.$$
Substitute $\alpha=-m-2$ and $z=-(e^x-1)$ then
\begin{equation} \label{eq:gen-amn-r}
\sum_{j \ge 0} \binom{2j+\alpha }{j}{z^j} = \sum_{j \ge 0} \binom{m-j+1}{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} a_m(n)\frac{x^n}{n!} = \frac{{C(1-e^x)}^{-m-2}}{\sqrt{4e^x -3}}\,.
\end{equation*}

In Theorem~\ref{thm:ch-poly}, $\chi_{\ST_n}(t)$ is expressed by a linear combination of $a_m(n)$'s.
So, with simple calculations, we can deduce the exponential generating function for
$\chi_{\ST_n}(t)$, which is
\begin{equation}\label{eq:gen-cha-st}
\sum_{n \geq 0} \chi_{\ST_n}(t)\frac{x^n}{n!} ~=~\frac{C(1-e^x)^{-t}}{\sqrt{4e^x-3}}\left(x\,C(1-e^x)+1\right)^2.
\end{equation}
%where $C(z)$ is the generating function for the Catalan number, i.e.,
%$$C(z)=\frac{1-\sqrt{1-4z}}{2z}=\sum_{n\geq 0}\frac{1}{n+1}\binom{2n}{n} z^n.$$
%%\vspace{15pt}
Put $t=-1$ and $x=-x$ in~\eqref{eq:gen-cha-st} to get
\begin{equation}\label{eq:gen-reg-st}
\sum_{n \geq 0} r(\ST_n)\frac{x^n}{n!} ~=~\frac{C(1-e^{-x})}{\sqrt{4e^{-x}-3}}\left(x\,C(1-e^{-x})-1\right)^2\,.
\end{equation}
Unfortunately, it looks like that right hand sides of equations~\eqref{eq:gen-cha-st} and \eqref{eq:gen-reg-st} cannot be simplified.
\section{Remarks}
A similar problem was solved by Athanasiadis in his PhD~thesis~\cite[Cor~7.3.3]{Ath-phd}, about the arrangement defined by
\begin{equation} \label{arr:ath}
x_i + x_j =0,1 \qquad  1\leq i \le j \leq n.
\end{equation}
The difference between this arrangement and the Shi-threshold arrangement is whether $i\leq j$ or $i<j$. In fact, the arrangement~\eqref{arr:ath} is exponentially stable~\cite[p.~97]{Ath-phd}, but the Shi-threshold arrangement is not, so
we cannot apply~his method in~\cite[Thm~7.3.2]{Ath-phd}.

Ardila~\cite[Thm~4.5]{Ard} computed the Tutte polynomials of various arrangements including the threshold arrangement.
It would be interesting to find the Tutte polynomial of Shi threshold arrangement.

Finally consider a ``generalized" threshold arrangement such as
\begin{equation} \label{arr:gen}
x_i + x_j =-l,-l+1,\ldots,m-1,m\quad  1\leq i \le j \leq n.
\end{equation}
It would be desirable to find the characteristic polynomial or the Tutte polynomial for the arrangement~\eqref{arr:gen}.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
We thanks the anonymous referee for valuable comments and suggestions to improve this article. This research was supported
by Basic Science Research Program through the National Research Foundation of Korea funded by the Ministry of Educations, Science and Technology (2012-0004476).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain}
% \bibliography{myBibFile}
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file

\begin{thebibliography}{Ath96b}


\bibitem[AL99]{AL}
Christos~A. Athanasiadis and Svante Linusson.
\newblock A simple bijection for the regions of the {S}hi arrangement of
  hyperplanes.
\newblock {\em Discrete Math.}, 204(1-3):27--39, 1999.

\bibitem[Ard07]{Ard}
Federico Ardila.
\newblock Computing the {T}utte polynomial of a hyperplane arrangement.
\newblock {\em Pacific J. Math.}, 230(1):1--26, 2007.

\bibitem[Ath96a]{Ath-phd}
Christos~A. Athanasiadis.
\newblock {\em Algebraic combinatorics of graph spectra, subspace arrangements
  and {T}utte polynomials}.
\newblock 1996.
\newblock Thesis (Ph.D.)--Massachusetts Institute of Technology.

\bibitem[Ath96b]{Ath-am}
Christos~A. Athanasiadis.
\newblock Characteristic polynomials of subspace arrangements and finite
  fields.
\newblock {\em Adv. Math.}, 122(2):193--233, 1996.

\bibitem[CH77]{CH}
V{\'a}clav Chv{\'a}tal and Peter~L. Hammer.
\newblock Aggregation of inequalities in integer programming.
\newblock In {\em Studies in integer programming ({P}roc. {W}orkshop, {B}onn,
  1975)}, pages 145--162. Ann. of Discrete Math., Vol. 1. North-Holland,
  Amsterdam, 1977.

\bibitem[CR70]{CR}
Henry~H. Crapo and Gian-Carlo Rota.
\newblock {\em On the foundations of combinatorial theory: {C}ombinatorial
  geometries}.
\newblock The M.I.T. Press, Cambridge, Mass.-London, preliminary edition, 1970.

\bibitem[Hea97]{Hea}
Patrick Headley.
\newblock On a family of hyperplane arrangements related to the affine {W}eyl
  groups.
\newblock {\em J. Algebraic Combin.}, 6(4):331--338, 1997.

\bibitem[OT92]{OT}
Peter Orlik and Hiroaki Terao.
\newblock {\em Arrangements of hyperplanes}.
\newblock Springer-Verlag, Berlin, 1992.

\bibitem[PS00]{PoSt}
Alexander Postnikov and Richard~P. Stanley.
\newblock Deformations of {C}oxeter hyperplane arrangements.
\newblock {\em J. Combin. Theory Ser. A}, 91(1-2):544--597, 2000.

\bibitem[Shi86]{Shi}
Jian~Yi Shi.
\newblock {\em The {K}azhdan-{L}usztig cells in certain affine {W}eyl groups},
  volume 1179 of {\em Lecture Notes in Mathematics}.
\newblock Springer-Verlag, Berlin, 1986.

\bibitem[Sta98]{Sta4}
Richard~P. Stanley.
\newblock Hyperplane arrangements, parking functions and tree inversions.
\newblock In {\em Mathematical essays in honor of {G}ian-{C}arlo {R}ota
  ({C}ambridge, {MA}, 1996)}, volume 161 of {\em Progr. Math.}, pages 359--375.
  Birkh\"auser Boston, Boston, MA, 1998.

\bibitem[Sta99]{Sta2}
Richard~P. Stanley.
\newblock {\em Enumerative combinatorics. {V}ol. 2}.
\newblock Cambridge University Press, Cambridge, 1999.

\bibitem[Sta07]{Sta3}
Richard~P. Stanley.
\newblock An introduction to hyperplane arrangements.
\newblock In {\em Geometric combinatorics}, volume~13 of {\em IAS/Park City
  Math. Ser.}, pages 389--496. Amer. Math. Soc., Providence, RI, 2007.

\bibitem[Wil94]{Wi}
Herbert~S. Wilf.
\newblock {\em generatingfunctionology}.
\newblock Academic Press Inc., Boston, MA, second edition, 1994.

\bibitem[Zas75]{Za}
Thomas Zaslavsky.
\newblock Facing up to arrangements: face-count formulas for partitions of
  space by hyperplanes.
\newblock {\em Mem. Amer. Math. Soc.}, 1(issue 1, 154):vii+102, 1975.

\end{thebibliography}



\end{document}
