 
\documentstyle[12pt]{article}  
\renewcommand{\baselinestretch}{1.3}
\sloppy
%\pagestyle{plain}
\setlength{\oddsidemargin}{0.05in}
\setlength{\evensidemargin}{0.05in}
\setlength{\topmargin}{-0.62in}
\setlength{\textheight}{9in}
\setlength{\textwidth}{5.7in}
\newtheorem{veta}{Theorem}[section]
\newtheorem{lemma}{Lemma}[section]
%\newtheorem{problem}[veta]{Problem}
\newtheorem{dusl}[veta]{Corollary}
%\newtheorem{pozor}[veta]{Observation}
\newenvironment{duk}{{\bf Proof.}\ }{ \hfill $\Box$ \par \bigskip }
\newcommand{\B}{{\cal B}}
\newcommand{\C}{{\cal C}}

\begin{document}
\vspace*{15mm}
\centerline{\huge Counting bad bracketings}
\bigskip
\bigskip
\centerline{\Large Martin Klazar}
\bigskip
\begin{center}
Department of Applied Mathematics of Charles University
\par Malostransk\'e n\'am\v est\'\i\ 25
\par 118 00 Praha 1
\par Czech Republic
\par {\tt klazar@kam.ms.mff.cuni.cz}
\end{center}
\begin{abstract}Suppose a partition of $\{1,2,\ldots,2n\}$ into $n$ 2-element blocks 
is given. By its crossing graph we mean the graph describing the intertwinings
of the blocks. We use power series to find numbers of partitions whose crossing graph (1) is connected, (2) has no isolated vertex, 
(3) is a tree, or (4) is a path. We determine the parity of that number in case (2) and we show that the numbers in cases (1) and (2) do not form a P-recursive sequence. For (1) and (2) we count also the symmetric bracketings. We extend and simplify some results of Stein \cite{stei}.
\end{abstract}

\section{Introduction}

A {\em bracketing\/} $B$ with $n$ {\em brackets\/} is a partition of $\{1,2,\ldots,2n\}$ into $n$ 2-element sets. We use the symbol $|B|$ 
to refer to the number of brackets of $B$. The set
${\cal B}(n)$ of all bracketings with $n$ brackets has $(2n-1)!!=(2n-1)\cdot (2n-3)\cdots 3\cdot 1$ elements. We shall investigate the cardinalities
$a_i(n)=|\B_i(n)|$ of seven subfamilies $\B_i(n)\subset \B(n)$, $i\in \{0,1,2,3,4,5,6\}$, defined below. By $\B_i$ we denote $\bigcup_{n\ge 1}\B_i(n)$, the empty bracketing  is denoted by $\emptyset$.

Two brackets $b$ and $c$ of a bracketing $B$ {\em cross\/} if either $\min b<\min c<\max b<\max c$ or the same holds with $b$ and $c$ switched. The {\em crossing graph\/} $G(B)$ has $B$ as its vertex set, two brackets are adjacent iff they cross. The {\em reflection\/} $\overline{B}$ of $B\in \B(n)$ is $\overline{B}=\{\{2n-i+1,2n-j+1\}:\ \{i,j\}\in B\}$. A bracketing is {\em symmetric\/} if it coincides with its reflection.

Crossing graphs are known in graph theory as {\em circle graphs\/} --- 
intersection graphs of circle chords --- and are intesively studied. See, for instance, Bouchet \cite{bouc}. Here, however, we are interested in the representations of crossing graphs by bracketings and not in the graphs themselves. 

{\em Good bracketings\/} $\B_0(n)$ are the ones whose crossing graph has no edge. {\em Connected bracketings\/} $\B_1(n)$ have connected crossing graph. {\em Symmetric connected bracketings\/} $\B_2(n)$ form the subset of symmetric bracketings in $\B_1(n)$.
{\em Bad bracketings\/} $\B_3(n)$ have crossing graph with no isolated vertex.
Those which are symmetric form the set $\B_4(n)$ of {\em symmetric bad bracketings\/}. Crossing graphs of {\em tree bracketings\/} $\B_5(n)$
are trees. Finally, {\em path bracketings\/} $\B_6(n)$ have path as their
crossing graph.

The family of good bracketings is a classical one. The families $\B_1(n)$ and $\B_2(n)$ have been investigated before but the remaining families seem new. The families $\B_0(n)$, $\B_5(n)$, and $\B_6(n)$ can be counted more easily and nicely than the other families. 

Our results are as follows. We start Section 2 with some more definitions and
then we review briefly the properties of the numbers $a_0(n)$ and some papers 
concerning counting arrangements of circle chords.
We prove in a simpler way the known recurrence for $a_1(n)$ and derive
a new simpler recurrence for $a_2(n)$. We derive a recurrence
for $a_3(n)$ and a relation for $a_4(n)$. In Section 3 it is shown that $a_1(n)$ and $a_3(n)$ satisfy no homogeneous linear recurrence with polynomial coefficients 
(in fact, we prove something stronger). The parity
patterns of the numbers $a_i(n), i\le 4$, are determined. Tree and path bracketings are enumerated. The first nine values of any $a_i(n)$ are given 
in the table. We finish by mentioning some questions which might be worth of further investigation.

\section{Recurrences} 

By an {\em arc\/} we mean here any plane semicircle, i.e., any intersection
$H\cap C$ where $H$ is a closed halfplane with the borderline going through the center of a circle $C$. A bracketing $B\in \B(n)$ can be depicted in the following way.
We draw a horizontal line $l$ and mark on it from left to right $2n$ distinct points $p_1, p_2, \ldots,p_{2n}$, called the {\em endpoints\/} of $B$. For each bracket $b=\{i,j\}\in B$ we join
$p_i$ and $p_j$ by an arc $A_b=A_{ij}$ lying above $l$. Any $p_i$ lies on exactly
one arc and $A_b$ and $A_c$ intersect iff $b$ and $c$ cross. We call this
a {\em picture\/} $p(B)$ of $B$. We prefer this way of visualization (it is used also in \cite{klei}, \cite{stei_a_ever}, \cite{stei}), the transition to circle chords is obvious. The points $p_i$ split $l$ into $2n+1$ {\em gaps of\/} $B$, the two unbounded ones are called the {\em outer gaps\/} and the $2n-1$ remaining ones are called the {\em inner gaps\/}. From now on we will work with pictures rather than with 
partitions. The words as component, vertex, path etc. used in connection with a picture $p(B)$ refer to the corresponding crossing graph $G(B)$.

Let $B_1, B_2\subset p(B)$ be two {\em separated\/} --- that is, disjoint and connected by no edge in $G(B)$ --- subbracketings. In the case that all
endpoints of $B_1$ are localized in one inner gap of $B_2$ we write $B_1<B_2$.
In the case they lie in one outer gap we write $B_1<>B_2$ (then also $B_2<>B_1$). 
If $B_1$ and $B_2$ are two different components of $G(B)$ then clearly
$B_1<B_2$ or $B_2<B_1$ or $B_1<>B_2$. 

The numbers $a_0(n)$ are the well known {\em Catalan numbers\/}
\begin{equation}
\label{catalannumbers}
a_0(n)={1\over n+1}{2n\choose n}
\end{equation}
following the basic recurrences $a_0(0)=1$,
\begin{equation}
\label{catalanrec1}
a_0(n)=\sum_{i=1}^{n}a_0(i-1)a_0(n-i),
\end{equation}
and
\begin{equation}
\label{catalanrec2}
(n+1)a_0(n)-(4n-2)a_0(n-1)=0.
\end{equation}

Their bracket representation is also classical. Catalan numbers pop out in many situations in combinatorics. The probability that $n+1$ random points chosen uniformly and independently in the unit square form a convex $n+1$-gon is $(a_0(n)/n!)^2$. The conditional probability that they form a convex chain,
provided they form a convex $n+1$-gon, is $1/a_0(n)$. See Valtr \cite{valt1} and
\cite{valt2} for details.

The problem to count all nonintersecting arrangements of $n$ circle chords with $2n$ distinct (and labeled) ends --- the anwer is, of course, that there are $a_0(n)$ of them --- was proposed and solved by Errera \cite{erre} in 1931. 
Touchard enumerated in the papers \cite{touc1}, \cite{touc2}, and 
\cite{touc3} general arrangements of circle chords by the number of intersections (in our terminology by the number of edges of $G(B)$). Riordan \cite{rior} continued in this direction. The families $\B_1(n)$ and $\B_2(n)$ were enumerated recursively by Stein in \cite{stei}. There they are called {\em irreducible diagrams} and {\em symmetric diagrams\/}. Stein and Everett  \cite{stei_a_ever} proved that
$$\label{asympt} 
a_1(n)\;\sim\;{(2n-1)!!\over e}.
$$
Much shorter proof of this asymptotics was given by Kleitman  
\cite{klei}. A generalization of this result to a wider class of diagrams is 
in the paper \cite{hsie} of Hsieh.

The nice relation $a_1(1)=1$,     
\begin{equation}
\label{hezka}
a_1(n)=(n-1)\sum_{i=1}^{n-1}a_1(i)a_1(n-i),
\end{equation}
is proved in \cite{stei} in a circumvential way via another, more complicated recurrence.
We give now a simple direct argument.

Let $B\in \B_1(n)$ for $n\ge 2$. We delete from $p(B)$ the leftmost arc $A_{1i}$ and obtain a bracketing with $n-1$ arcs. Its components form a chain $B_1>B_2>\ldots>B_k$ and $p_i$ lies in some, say the $j$th one, inner gap of $B_k$. Thus $B$ decomposes into $(B^*,B_k,j)$ where $B^*$ arises from $B$
by removing $B_k$. Therefore $\B_1(n)$ corresponds bijectively to the triples
$(A,B,j)$ where $A$ and $B$ are connected bracketings, $|A|+|B|=n$, and $1\le j\le 2|B|-1$. Hence
$$a_1(n)=\sum_{i=1}^{n-1}(2i-1)a_1(i)a_1(n-i),$$
and (\ref{hezka}) follows by pairing $a_1(i)a_1(n-i)$ with $a_1(n-i)a_1(i)$.

We introduce the (formal) power series $F_1(x)=\sum_{n\ge 1}a_1(n)x^n$. The above combinatorial
decomposition reads in terms of $F_1$ as $F_1=F_1\cdot (2x{d\over dx}F_1-F_1)+x$. Hence
\begin{equation}
\label{f1}
F_1^{\prime}={F_1^2+F_1-x\over 2xF_1}.
\end{equation}

We proceed to enumerate symmetric connected bracketings. We use decomposition techniques
similar to those in \cite{stei}. The recurrence we obtain is more transparent and compact
than the one in \cite{stei}.

\begin{veta}
\label{symetricke}
We define $a_2(0)=-1$. We have $a_2(1)=1$ and, for $n\ge 2$,
\begin{equation}
\label{a2rec}
a_2(n)=\sum_{i=1}^{n-2}a_2(i)a_2(n-i)+\sum_{i=1}^{n/2}(2n-4i-1)a_1(i)a_2(n-2i).
\end{equation}
\end{veta}
\begin{duk}
Let $B\in \B_2(n)$ for $n\ge 2$. We delete from $p(B)$ the first and last arcs $X=A_{1i}$ and $Y=A_{2n-i+1,2n}$ 
and obtain a symmetric bracketing with $n-2$ arcs. Its components split uniquely
in three groups $\{B_1,\ldots,B_{k-1}\}$, $C_k$, and $D_k$ ($C_k$ and $D_k$ are chains of components) where $B_1>B_2>\ldots >B_{k-1}>C_k, D_k$ and $C_k<>D_k$. The following holds.
\begin{itemize}
\item $B_j\in \B_2$, $B_{j+1}$ lies in the central
inner gap of $B_j$.
\item $C_k$ and $D_k$ are reflections of one another, $C_k\in \B\cup \{\emptyset \}$, $C_k$ and $D_k$ lie in the symmetric pair of (not necessarily distinct) inner gaps of $B_{k-1}$.
\item The point $p_i$ lies in an inner gap of $C_k$ and $p_{2n-i+1}$ lies in an inner gap of $D_k$ or vice versa. In the former case we put $C_k^*=C_k\cup \{X\}$ and $D_k^*=D_k\cup \{Y\}$, in the latter case we switch
$X$ and $Y$. Then $C_k^*=\overline{D_k^*}$ and $C_k^*$ is a general nonempty connected bracketing. 
\item In the case that
$X$ and $Y$ do not intersect we have $k\ge 2$, otherwise $k\ge 1$.
\end{itemize}

This decomposition expresses in terms of the power series $F_2(x)=\sum_{n\ge 1}
a_2(n)x^n$ and $F_1(x)$ as
$$F_2(x)=2xF_1(x^2)\sum_{k\ge 0}F_2^{\prime}(x)F_2^k(x)+F_1(x^2)+x.$$
Here the coefficient 2 accounts for the two cases of crossing and noncrossing $X$ and $Y$,
the derivative accounts for the locations of $C_k$ and $D_k$, and the first occurrence of $F_1(x^2)$ accounts for
$C_k^*\cup D_k^*$. The second occurrence of $F_1(x^2)$ accounts for the case when there is no $B_j$.

Using the geometric series formula and simplifying we can recast this as
$$
F_2^2-(1+x)F_2+F_1(x^2)(2xF_2^{\prime}-F_2+1)+x=0.
$$
Equating the coefficient at $x^n$ to zero we obtain (\ref{a2rec}).  
\end{duk}

Now we enumerate bad bracketings.
\begin{veta}
\label{spatne}
We set $a_3(-1)=a_3(0)=1$. Then, for $n\ge 1$,
\begin{equation}
\label{a3rec}
a_3(n)=\sum\ (2m+1)a_3(k)a_3(l)a_3(m),
\end{equation}
we sum over integer triples $(k,l,m)$ satisfying $-1\le k,l,m\le n-1$,
$k\neq -1$, and $k+l+m=n-2$.
\end{veta}
\begin{duk}
We claim that the power series $F_3(x)=\sum_{n\ge 0}a_3(n)x^n$ satisfies
the equation
\begin{equation}
\label{prvnif3}
F_3=\sum_{k\ge 0}(x(2xF_3^{\prime}+F_3))^k-xF_3^2
\end{equation}
that can be written as
\begin{equation}
\label{f3}
F_3\cdot (1+xF_3)\cdot (1-xF_3-2x^2F_3^{\prime})=1.
\end{equation}
Or, to isolate the derivative, as
\begin{equation}
\label{derivacef3}
F_3^{\prime}={-x^2F_3^3+F_3-1\over 2x^3F_3^2+2x^2F_3}.
\end{equation}

To see this we delete from $B\in \B_3(n), n\ge 1,$ the first arc $A_{1i}$
and consider the structure of the resulting bracketing. It is as follows.
\begin{itemize}
\item The point components must form a chain $O_1>O_2>\ldots >O_k$ (any $O_j$
is a single arc).
\item The rest splits uniquely into separated bracketings $B_j\in \B_3\cup\{\emptyset \}$,
$j=1,\ldots,k+1$, such that $O_j>B_{j+1}$ and $B_j>O_j$ or $B_j<>O_j$.
\item If $k>0$ the point $p_i$ lies in one of the $2|B_{k+1}|+1$ gaps of $B_{k+1}$ and in the inner gap of $O_k$.
\item The case $k=0$ is different, the gaps splitting $B_1$ into $C_1<>C_2$,
$C_j\in \B_3\cup \{\emptyset \}$, are for $p_i$ forbidden.
\end{itemize}

It is not difficult to translate this to generating functions, then (\ref{prvnif3}) is obtained. The coefficient extraction and indices
shift transform (\ref{f3}) to (\ref{a3rec}).
\end{duk}

Finally, we enumerate symmetric bad bracketings. A combination
of arguments of Theorems \ref{symetricke} and \ref{spatne} yields an equation 
involving $F_3(x)$ and $F_4(x)$. A recurrent 
relation can be obtained but is not too pleasant to be stated. For the sake of brevity we omit the details.

\begin{veta}
Let $P(x)=1-2x^4F_3^{\prime}(x^2)-x^2F_3(x^2)$ and $a_4(0)=1$. The power series $F_4(x)=\sum_{n\ge 0}a_4(n)x^n$ satisfies the equation
$$
x(1+x^2F_3(x^2))PF_4^2+(2x^2-(1+x+x^2F_3(x^2))P)F_4+2x^3F_4^{\prime}+P=0.
$$
\end{veta}
\begin{duk}
(Sketch) Considering a symmetric bad bracketing and deleting from it the first 
and last arcs we obtain
$$
F_4=2x^2(xF_4^{\prime}+F_4)\sum_{k\ge 0}(xF_4)^k\cdot \sum_{k\ge 0}
(x^2(xF_3(x^2)^{\prime}+F_3(x^2)))^k-x^2F_3(x^2)F_4+1.
$$
\end{duk}


\section{P-recursivity, Parity, Trees, and Paths}
A sequence of complex numbers $\{a(n)\}_{n\ge 0}$ is called {\em P-recursive\/} (short for polynomially recursive) if there are $j+1$ polynomials $P_0(x),\ldots, P_{j}(x)\in {\bf C}[x]$, $P_j(x)\not\equiv 0$, such that
for any integer $n\ge 0$
\begin{equation}
\label{polyrekurence}
P_0(n)a(n)+P_1(n)a(n+1)+\ldots +P_j(n)a(n+j)=0.
\end{equation}
P-recursive sequences are certainly "nice" sequences because
(\ref{polyrekurence}) provides us with an easy way to calculate quickly their values. Therefore for any counting sequence $s$ it is
 of some interest to know whether $s$ is P-recursive. The formula (\ref{catalanrec2}) shows that Catalan numbers form
a P-recursive sequence. We shall see that $\{a_5(n)\}_{n\ge 0}$ and $\{a_6(n)\}_{n\ge 0}$
are P-recursive as well. On the other hand we prove now that $\{a_1(n)\}_{n\ge 0}$ and
$\{a_3(n)\}_{n\ge 0}$ are not P-recursive.

The basic reference for P-recursivity is Stanley \cite{stan}. 
There it is proved 
that the P-recursivity of $\{a(n)\}_{n\ge 0}$ is equivalent to the fact that
$F(x)=\sum_{n\ge 0}a(n)x^n$ satisfies, for some $m+1$ polynomials
$R_0(x),\ldots, R_{m}(x)\in {\bf C}[x]$, $R_m(x)\not\equiv 0$,
the differential equation
\begin{equation}
\label{rovnice}
R_m(x)F^{(m)}(x)+\ldots +R_1(x)F^{\prime}(x)+R_0(x)F(x)=0.
\end{equation}
This property of $F(x)$ is called {\em D-finiteness\/}. 

We define now a property weaker than P-recursivity and we prove that the sequences $\{a_{1,3}(n)\}_{n\ge 0}$ still do not have it. We say that
a sequence of complex numbers $\{a(n)\}_{n\ge 0}$ is {\em approximately P-recursive\/} if there is a P-recursive sequence $\{b(n)\}_{n\ge 0}$ and a 
constant $c>0$ such that $|a(n)-b(n)|<c^n$ for any $n\ge 0$. A power series 
$F(x)=\sum_{n\ge 0}a(n)x^n$ is {\em analytic\/} if it has a nonzero radius of 
convergence, i.e. if $|a(n)|<c^n$ for any $n\ge 0$ for some constant $c>0$.

\begin{veta}
\label{prek}
Let $P(x,y)$ and $Q(x,y)$ be two polynomials satisfying 
$$\mbox{$Q(x,0)\equiv 0$
and $P(x,0)\cdot (Q/y)(x,0)\not\equiv 0$},$$
and let $F(x)=\sum_{n\geq 0} a(n)x^n$
be a nonanalytic power series satisfying
$$F^{\prime}={P(x,F)\over Q(x,F)}.$$
Then $\{a(n)\}_{n\ge 0}$ is not approximately P-recursive.
\end{veta}
\begin{duk}
We show that for any $k\ge 1$
\begin{equation} 
\label{derivace}
F^{(k)}={P_k(x,F)\over Q(x,F)^{2k-1}}
\end{equation}
where $P_k$ is a bivariate polynomial such that $P_k(x,0)\not\equiv 0$. 
For $k=1$ it is true. Assuming the claim for $k\ge 1$ and taking the derivative
of $F^{(k)}$ we obtain
$$F^{(k+1)}={{P_k^{\prime}}Q^2-(2k-1)P_kQ^{\prime}Q\over Q^{2k+1}}.$$
Substituting the expression for $F^{\prime}$ we see that  $P_{k+1}=P_k^{\prime}Q^2-(2k-1)P_kQ^{\prime}Q$ is a polynomial in $x$ and $F$.
By our asumption  $(Q^{\prime}Q)(x,0)\not\equiv 0$, so by induction
$P_{k+1}(x,0)\not\equiv 0$.

Now assume that $\{a(n)\}_{n\ge 0}$ is approximately P-recursive. Thus 
for some analytic power series $G(x)$ the sum $H(x)=F(x)+G(x)$ is D-finite. The derivatives $H^{(k)}(x)=F^{(k)}(x)+G^{(k)}(x)$ satisfy an equation of the type  (\ref{rovnice}). 
Substituting the expressions (\ref{derivace}) and clearing out the denominators
we obtain the relation
$$Q^{2m-1}(x,F)\,R_0(x)\,F+\sum_{i=1}^m Q^{2m-2i}(x,F)\,R_i(x)\,P_i(x,F)+ $$
$$+Q^{2m-1}(x,F)\sum_{i=0}^m R_i(x)\,G^{(i)}(x)=0.$$
The left side does not vanish because the specialization $F=0$ yields the nonzero polynomial $R_m(x)\,P_m(x,0)$. Thus $F$ satisfies a nontrivial
algebraic equation
$$S_0(x)+S_1(x)\,F(x)+\ldots +S_r(x)F^r(x)=0$$
where the coefficients $S_i(x)$ are analytic power series. By M. Artin's approximation theorem, see Ruiz's book \cite{ruiz},  pp. 94 and 106,, $F(x)$ itself must be analytic. But this contradicts our assumption. Hence $\{a(n)\}_{n\ge 0}$ is not approximately P-recursive. 
\end{duk}

\begin{dusl}
The sequences $\{a_1(n)\}_{n\ge 1}$ and $\{a_3(n)\}_{n\ge 0}$
counting connected bracketings and bad bracketings are not
approximately P-recursive.
\end{dusl}
\begin{duk}
The formal differential equations (\ref{f1}) and (\ref{derivacef3})
are in the right form. The recurrences (\ref{hezka}) and (\ref{a3rec}) show that the sequences $\{a_{1,3}(n)\}_{n\ge 0}$ grow faster than any exponential function. Thus $F_1$ and $F_3$ are nonanalytic.
\end{duk}

It is a well known and neat property of Catalan numbers that $a_0(n)$ is odd
iff $n=2^m-1$. Although $a_1(n)$ and $a_3(n)$ are not P-recursive, their parity
follows a P-recursive pattern. To describe it we use the symbol ($a$ mod $b$) meaning, for $a,b\in {\bf N}$, the least $c\in {\bf N}$ congruent mod $b$ with $a$.

\begin{veta}
The number $a_1(n)$ is odd iff $n=2^m$. The numbers $a_3(2m+1)$ are even.
Finally, $a_3(2m)$ is even iff there is an $r\in {\bf N}$ such that 
$$(m \mbox{ \rm mod } 2^r)>{2^{r+1}\over 3}.$$
\end{veta}
\begin{duk}
For $n>1$ odd, by (\ref{hezka}), $a_1(n)$
is even. For $n$ even we have, by (\ref{hezka}), $a_1(n)\equiv a_1(n/2)\ ({\rm mod}\ 2)$ and the claim follows by induction. This is, of course, exactly the same proof as for Catalan numbers by means of (\ref{catalanrec1}).

Reducing  (\ref{f3}) mod 2 we obtain the equation
$$
x^2F^3-F+1=0
$$
whose unique power series solution $F(x)=\sum_{n\ge 0}a(n)x^n$ is coefficientwise congruent mod 2 with $F_3(x)$. Substituting $G=xF$ we obtain 
the equation 
$$
G={x\over 1-G^2}
$$
that can be easily resolved by the Lagrange inversion formula (see, for instance,
the book of Wilf \cite{wilf}). By the formula the coefficient at $x^n$ in $G$ equals to the
coefficient at $y^{n-1}$ in $(1-y^2)^{-n}/n$. We obtain
$$
a_3(n)\equiv a(n)=\left\{
\begin{array}{ll}
0 & \mbox{ for $n$ odd } \\
{1\over n+1}{3n/2\choose n} & \mbox{ for $n$ even.}
\end{array}
\right.
$$
To obtain for $n=2m$ an explicit parity criterion we have to
determine the parity of ${3m\choose m}/(2m+1)$. This is a standard task
for elementary number theory. The argument uses the formula 
$$\left\lfloor{n\over p}\right\rfloor+
\left\lfloor{n\over p^2}\right\rfloor+
\left\lfloor{n\over p^3}\right\rfloor+\ldots$$
for the highest power in which a prime $p$ divides $n!$
and we omit it.
\end{duk}
For example, $a_3(304)$ is even because 152 mod 32 is 24. On the other hand 
$a_3(296)$ is odd because 148 mod 2 and 4 is 0, mod 8 and 16 is 4, mod 32, 64, and 128 is 20, and mod 256 is 148.

Obviously $a_2(n)$ has the same parity as $a_1(n)$ for it differs from $a_1(n)$
by the number of nonsymmetric connected bracketings which come in pairs.
The same for $a_3(n)$ and $a_4(n)$. 

The Catalan numbers (\ref{catalannumbers}) enumerate also {\em rp\/} (short for rooted plane) {\em trees\/} with $n-1$ vertices. These are unlabeled trees with a specified vertex called a {\em root}, with all edges directed away from the root, and with a linear order on any set of children of a vertex. {\em Ternary
 rp trees\/} are rp trees in which each vertex has either 3 or 0 children. 
It is not difficult to prove by the Lagrange inversion formula that there are
\begin{equation}
\label{ternarni}
{1\over 2n+1}{3n\choose n}
\end{equation}
ternary rp trees with $3n+1$ vertices.

\begin{veta}
The number of tree bracketings with $n$ brackets is given by the formula
$$
a_5(n)={1\over 2n-1}{3n-3\choose n-1}.
$$
\end{veta}
\begin{duk}
We present a bijection between $\B_5(n)$ and the set of ternary rp trees with
$3n-2$ vertices. Let $B\in B_5(n)$, consider the picture $p(B)$. We define
a graph $H(B)$ whose vertices are the endpoints of the arcs, except for the rightmost one, and the arc intersections. The root is the counterclockwise first
vertex on the rightmost arc. Two vertices form an edge iff they are connected by an arc segment
with no vertex inbetween.

Obviously $H(B)$ is connected and has no cycle because $G(B)$ is a tree. Directing the edges away from the root we turn $H(B)$ into a ternary rp tree.
$H(B)$ has $(2n-1)+(n-1)$ vertices. The transformation of $B$ in $H(B)$ is the
desired bijection. The inverse reconstruction of $B$ from $H(B)$ is left to
the reader. Hence, by (\ref{ternarni}), the formula for $a_5(n)$ follows. 
\end{duk}

We finish enumerating the path bracketings.
\begin{veta}
The ordinary generating function $F_6(x)=\sum_{n\ge 1}a_6(n)x^n$ counting path bracketings is
\begin{equation}
\label{f6}
F_6(x)={1\over 2x}\left( 1-x-\sqrt{{1-3x-x^2-x^3\over 1-x}}\;\right)-{x^2\over 1-x}.
\end{equation}
\end{veta}
\begin{duk}
We call an arc $X$ in the picture $p(B)$ of a bracketing $B$ {\em free\/} if 
$Y>X$ for no other arc $Y$. It is 
easy to see that there is only one bracketing in $\B_6(n)$, $n>1$, having free both of the arcs corresponding to the endvertices of the path $G(B)$. We call 
this exceptional bracketing a {\em chain\/}.

Now delete from a path bracketing $B\in \B_6(n)$, $n>1$, the first arc $X=A_{1i}$. The crossing graph $G(B^*)$ of the remaining bracketing $B^*$ is a path or has two path components. Suppose first $G(B^*)$ is a path. The point $p_i$ must lie in the inner gap which is covered by the free endvertex of $G(B^*)$ and which is not covered by any other arc. So we have only one way 
how to add $X$ back to obtain $B$, except for $B^*$ a chain when we have two ways. Such $B$'s are accounted for by the coefficient in $x(F_6-x^2/(1-x)+2x^2/(1-x))$.

Suppose $G(B^*)$ has two path components $C>D$. As in the previous case, $C$ has only one gap $D$ can lie in, except for $C$ a chain when there are two such gaps. The same for the location of the endpoint $p_i$ in $D$. Therefore, such $B$'s are  accounted for in $x(F_6+x^2/(1-x))^2$. 

Finally, the single arc bracketing is accounted for by $x$. Altogether we have
$$F_6=x\left(F_6+{x^2\over 1-x}\right)^2+x\left(F_6+{x^2\over 1-x}\right)+x.$$
This leads to the quadratic equation $(1-x)xG^2-(1-x)^2G+x=0$ where $G=F_6+x^2/(1-x)$. Solving the equation we obtain the formula (\ref{f6}).
\end{duk}

The reader may wonder what is the P-recurrence for $\{a_6(n)\}_{n\ge 1}$. Writing  $H(x)$ for the radical in (\ref{f6}) we find that
$$H^{\prime}(x)\cdot (x^4+2x^2-4x+1)-H(x)\cdot (x^3-x^2-x-1)=0.$$
Using this relation we obtain after some additional calculations 
the recurrence ($n\ge 6$)
$$
(n+1)a_6(n)-(4n-1)a_6(n-1)+(2n-1)a_6(n-2)+a_6(n-3)+(n-4)a_6(n-4)=2.
$$
The initial values are:
$a_6(2)=1$, $a_6(3)=3$, $a_6(4)=8$, $a_6(5)=21$. We could easily make  the recurrence homogeneous but for the cost of enlarging its span. 

In the table below we list first few values of the numbers $a_i(n)$. 

\bigskip
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
$n$ & $a_0$ & $a_1$ & $a_2$ & $a_3$ & $a_4$ & $a_5$ & $a_6$ \\\hline
1 & 1 & 1 & 1 & 0 & 0 & 1 & 1 \\\hline
2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 \\\hline
3 & 5 & 4 & 2 & 4 & 2 & 3 & 3 \\\hline
4 & 14 & 27 & 7 & 31 & 9 & 12 & 8 \\\hline
5 & 42 & 248 & 22 & 288 & 26 & 55 & 21  \\\hline
6 & 132 & 2830 & 96 & 3272 & 122 & 273 & 56 \\\hline
7 & 429 & 38232 & 380 & 43580 & 466 & 1428 & 153 \\\hline
8 & 1430 & 593859 & 1853 & 666143 & 2299 & 7752 & 428 \\\hline
9 & 4862 & 10401712 & 8510 & 11491696 & 10316 & 43263 & 1222 \\\hline
\end{tabular}

\end{center}

\bigskip
The obvious question is whether $\{a_2(n)\}_{n\ge 0}$ and $\{a_4(n)\}_{n\ge 0}$ 
are P-recursive. We think that the anwer is negative. One can eliminate $F_1$ from the equation for $F_2$ but the resulting relation contains 
the second derivative of $F_2$. A theorem more involved than Theorem \ref{prek} is necessary. The situation for $F_4$ is even more complicated.

One can consider, besides the approximate P-recursivity, another way of approximating a non P-recursive sequence by a P-recursive one. We say that a sequence  of integers $\{a(n)\}_{n\ge 0}$ is {\em P-recursive mod p\/}, $p$ being prime, if there 
is a P-recursive sequence of integers $\{b(n)\}_{n\ge 0}$ such that $b(n)\equiv a(n)$ mod $p$ for any $n\ge 0$. We have shown that any of the four sequences  $\{a_{1,2,3,4}(n)\}_{n\ge 0}$ is P-recursive mod 2. We conjecture that this is not the case for any $p>2$.


\begin{thebibliography}{22}

\bibitem{bouc} A. Bouchet, Reducing prime graphs and recognizing circle graphs,
{\em Combinatorica\/} {\bf 7} (1987), 243--254.

\bibitem{erre} A. Errera, {\em Mem. Acad. Bruxelles}  $8^{\circ}$ (2) {\bf 11} (1931).

\bibitem{hsie} W. N. Hsieh, Proportions of irreducible diagrams, {\em Studies in
Appl. Math.\/} {\bf 52} (1973), 277--283.

\bibitem{klei} D. J. Kleitman, Proportions of irreducible diagrams, {\em Studies in
Appl. Math.\/} {\bf 49} (1970), 297--299.

\bibitem{rior} J. Riordan, The distribution of crossings of chords joining pairs
of $2n$ points on a circle, {\em Math. Comp.\/} {\bf 29} (1975), 215--222.

\bibitem{ruiz} J. M. Ruiz, {\em The basic theory of power series\/}, Vieweg, 
Braunsch\-weig/Wies\-baden 1993.

\bibitem{stan} R. P. Stanley, Differentiably finite power series, {\em Europ. J. Combinatorics} {\bf 1} (1980), 175--188.

\bibitem{stei} P. R. Stein, On a class of linked diagrams, I. Enumeration, {\em 
J. of Combinatorial Th.\/} Series A {\bf 24} (1978), 357--366.

\bibitem{stei_a_ever} P. R. Stein and J. A. Everett, On a class of linked diagrams, II. Asymptotics, {\em Disc. Math.\/} {\bf 21} (1978), 309--318.

\bibitem{touc1} J. Touchard, Sur une probl\`eme de configurations, 
{\em C. R. Acad. Sci. Paris\/} {\bf 230} (1950), 1997--2008.

\bibitem{touc2} J. Touchard, Contribution \`a l'\'etude du probl\`eme des 
timbres-poste, {\em Canad. J. Math.\/} {\bf 2} (1950), 385--398. 

\bibitem{touc3} J. Touchard, Sur une probl\`eme de configurations et sur les fractions continues,
{\em Canad. J. Math.\/} {\bf 4} (1952), 2--25.

\bibitem{valt1} P. Valtr, Probability that $n$ random points are in convex position, {\em Discrete Comput. Geom.\/} {\bf 13} (1995), 637--643.

\bibitem{valt2} P. Valtr, Catalan numbers via random planar point sets,
submitted.

\bibitem{wilf} H. S. Wilf, {\em Generatingfunctionology\/}, Academic Press, New York 1994.

\end{thebibliography}


\end{document}
