% A LaTeX file for an 11 page document
% It requires 3 files containing encapsulated postscript figures
% The 3 files are called Figure1.epsf, Figure2.epsf, Figure3.epsf
% To typeset these files the standard style file epsf.sty is needed
\documentclass[12pt]{article}
\usepackage{amstex,amssymb}
\usepackage{theorem}

\input{epsf.sty}

%EJC Running head
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 5 (1998)
\#R6\hfill}
\thispagestyle{empty}

%EJC page size
\hsize=6in
\vsize=9in

\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{definition}{Definition}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{conjecture}{Conjecture}
{\theorembodyfont{\rmfamily} \newtheorem{example}{Example}}
\newenvironment{proof}{\noindent\textsc{Proof}}{\hfill\ensuremath{\blacksquare}}
\newenvironment{remark}{\noindent\textbf{Remark}}{}
\parskip 0.1in
\parindent 0pt
\begin{document}
\title{Permutations which are the union of an increasing and a decreasing
subsequence}
\author{M.D. Atkinson \\School of Mathematical and Computational Sciences\\
North Haugh, St Andrews, Fife KY16 9SS, UK\\
\texttt{mda@@dcs.st-and.ac.uk}
}
\date{}
\maketitle
\begin{abstract} It is shown that there are ${2n\choose
n}-\sum_{m=0}^{n-1}2^{n-m-1}{2m\choose m}$ permutations which are the union of
an increasing sequence and a decreasing sequence.
\end{abstract}
\smallskip
\centerline{1991 {\em Mathematics Subject Classification} 05A15}
\smallskip
\centerline{Submitted: December 1, 1997; Accepted: January 10, 1998}
\smallskip
\section{Introduction}
{\em Merge permutations}, permutations which are the union of two increasing
subsequences, have been
studied for many years \cite{Knuth}.  It is known that they are
characterised by the property of having no decreasing subsequence of
length $3$ and that there are ${2n\choose n}/(n+1)$ such
permutations of length $n$.

Recently there has been some interest in permutations which are the
union of an increasing subsequence with a decreasing subsequence.  We
call such permutations {\em skew-merged}.  Stankova
\cite{Stankova} proved that a permutation is skew-merged if and only
if it has no subsequence $abcd$ ordered in the same way as $2143$ or
$3412$.  In \cite{BK,KSW} the more general problem of partitioning a
permutation into given numbers of increasing and decreasing
subsequences is considered.

This paper solves the enumeration problem for skew-merged permutations.
The proof yields another proof of Stankova's result.  Finally, a
corollary allows the skew-merged enumeration result to be compared
with the enumeration of merge permutations.

\section{Points and colours}
We shall consider sets of `points' $(a,b)$ in the $(x,y)$-plane.  Our
point sets will always have the property that there is no duplicated
first coordinate or second coordinate.  In view of that condition
there are two natural total orders on  points.
If $P=(a,b)$ and $Q=(c,d)$ are points then we define
$P..Q$ if $a<c$ and $P<Q$ if $b<d$.

Two sets of points $S,T$ are said to be {\em order isomorphic} if
there is a one-to one correspondence between them which respects both
total orders.  A set of $n$ points is called {\em normal} if its sets of
$x$-coordinates and $y$-coordinates are each $\{1,2,\ldots,n\}$.
It is easy to see that every set of points is order isomorphic to a
unique
normal set.  Note that a point set corresponds to a poset of
dimension $2$.

Every permutation $\sigma=[s_{1},\ldots,s_{n}]$ defines and is defined
by a normal set $\{(i,s_{i})\}_{i=1}^{n}$ and we shall find it
helpful to depict a permutation by its set of points plotted in the
$(x,y)$-plane.  If the permutation is skew-merged this graph looks
like Figure 1 where the increasing and decreasing subsequences are
clearly visible.  In the terminology of dimension $2$ posets, an
increasing subsequence is a chain and a decreasing subsequence is an
anti-chain.

\begin{figure}[t]
        \centerline{\epsffile{Figure1.epsf}}
        \caption{The graph of a skew-merged permutation}
\end{figure}

There are three involutory symmetry operations $r,s,t$ on point sets and
permutations defined on the points $P=(a,b)$ of a permutation $\sigma$ of
length $n$
as follows
\begin{eqnarray*}
r(P)&=&(n+1-a,b)\\
s(P)&=&(a,n+1-b)\\
t(P)&=&(b,a)
\end{eqnarray*}
We let $r(\sigma),s(\sigma),t(\sigma)$ be the corresponding
permutations and note the following elementary result:

\begin{lemma}
\begin{enumerate}
\item[(i)]If $P,Q$ are points of the permutation
$\sigma$, then $P..Q$ if and only if $r(Q)..r(P)$ in $r(\sigma)$ if and
only if
$s(P)..s(Q)$ in $s(\sigma)$ if and only if $t(P)<t(Q)$ in $t(\sigma)$
\item[(ii)] $\sigma$ is skew-merged if and only if any or all of
$r(\sigma),s(\sigma),t(\sigma)$ are skew-merged.
\end{enumerate}
\end{lemma}

If $P$ is one of the points in the set ${\cal P}$ of points of
the permutation $\sigma$ then ${\cal P}\setminus P$ is a set of
points with no duplicate first or second coordinates and therefore it
corresponds to some permutation $\tau$ and we write
\[\tau=\sigma-P\]
This corresponds to removing one of the components of
$\sigma=[s_{1},\ldots,s_{n}]$ and relabelling and renumbering the
remaining components appropriately.

We divide the points of a permutation $\sigma$ into 5 classes Red,
Blue, Green, Yellow, and White by the following rules:
\begin{enumerate}
\item[(r)] if $P..Q..R$ and $Q<R<P$ then $P$ is red
\item[(b)] if $P..Q..R$ and $Q<P<R$ then $R$ is blue
\item[(g)] if $P..Q..R$ and $P<R<Q$ then $P$ is green
\item[(y)] if $P..Q..R$ and $R<P<Q$ then $R$ is yellow
\item[(w)] if $P$ is not red, blue, green or yellow, then $P$ is white
\end{enumerate}

There is a more convenient way of expressing these conditions.  If
$P,Q,R$ are any $3$ points and $[a,b,c]$ is any permutation of $1,2,3$
then we write $PQR\sim abc$ if $P..Q..R$ and, with respect
to ``$<$'', $P,Q,R$ are ordered in the same way as $a,b,c$.  The
premises of (r), (b), (g), (y) above are then $PQR\sim 312$, $PQR\sim
213$, $PQR\sim 132$, $PQR\sim 231$ respectively.  We also adopt this
language for sets of $4$ or more points.  For example, if $P,Q,R,S$
are $4$ points such that $P..Q..R..S$ and $Q<P<S<R$ we would write
$PQRS\sim 2143$.

The aim of this section is to prove the following
\begin{theorem}\label{graph}  The graph of a skew-merged permutation
has the form shown in Figure 2.  In this figure the vertical and
horizontal lines have the obvious separation meaning; for example, if
$R$ and $W$ are red and white points we would have $R..W$ and $W<R$.
Furthermore, the green and blue points are increasing, the red and yellow
points are decreasing, and the white points are either increasing or
decreasing.
\end{theorem}

\begin{figure}[t]
        \centerline{\epsffile{Figure2.epsf}}
        \caption{Disposition of colours}
\end{figure}

In proving this theorem we shall use only the property of skew-merged
permutations that they avoid $3412$ and $2143$; in our `point'
terminology this means that there do not exist $4$ points $P,Q,R,S$
with $PQRS\sim 3412$ or $PQRS\sim 2143$.  Since a
permutation with a graph of the above form is evidently skew-merged we
obtain another proof of Stankova's result.


\begin{lemma}\label{symmetry} Let $P$ be a point of a permutation $\sigma$.
Then
\begin{enumerate}
\item[(i)] $P$ is red in $\sigma$ if and only if $r(P)$ is blue in
$r(\sigma)$
\item [(ii)] $P$ is green in $\sigma$ if and only if $r(P)$ is yellow in
$r(\sigma)$
\item [(iii)] $P$ is red in $\sigma$ if and only if $s(P)$ is green in
$s(\sigma)$
\item [(iv)] $P$ is blue in $\sigma$ if and only if $s(P)$ is yellow in
$s(\sigma)$
\item [(v)] $P$ is red in $\sigma$ if and only if $t(P)$ is yellow in
$t(\sigma)$
\item [(vi)] $P$ is green in $\sigma$ if and only if $t(P)$ is green in
$t(\sigma)$
\item [(vii)] $P$ is blue in $\sigma$ if and only if $t(P)$ is blue in
$t(\sigma)$
\item [(viii)] $P$ is white in $\sigma$ if and only if any or all of
$r(P),s(P),t(P)$ are white in $r(\sigma),s(\sigma),t(\sigma)$
respectively.
\end{enumerate}
\end{lemma}
\begin{proof} All the statements follow easily from the definitions.
For example, suppose that $P$ is red in $\sigma$ so that there are
points $Q,R$ with $PQR\sim 312$.  Then $r(P),r(Q),r(R)$ are points of
$r(\sigma)$ with $r(R)r(Q)r(P)\sim 213$; therefore
$r(P)$ is blue in $r(\sigma)$
\end{proof}

\begin{lemma} In a skew-merged permutation $\sigma$ every point has
exactly one colour.
\end{lemma}
\begin{proof}  Suppose first that a point $P$ is coloured both red and green
in $\sigma$.  Then there are points $Q,R,S,T$ with
$P..Q..R$, $P..S..T$, $Q<R<P$,  and $P<T<S$.
In particular, $Q<R<P<T<S$.  If $Q..S$ then  $PQST\sim 2143$, a
contradiction, and if $S..Q$ then  $PSQR\sim 3412$, also a contradiction.

It now follows from the symmetry operations and Lemma \ref{symmetry}
that $P$ cannot be
coloured both blue and yellow (or $r(P)$ would be both red and green
in $r(\sigma)$); nor can $P$ be both yellow and green (or $t(P)$ would
be red and green in $t(\sigma)$); nor can $P$ be both red and blue (or
$t(s(P))$ would be both red and green in $t(s(\sigma))$).

Suppose next that $P$ is both red and yellow in $\sigma$.  Then there
are points $Q,R,S,T$ with
$P..Q..R, S..T..P, Q<R<P$, and $P<S<T$
But then  $STQR\sim 3412$.  The remaining
possibility, that $P$ is both blue and green, can also be excluded by
symmetry ($r(P)$ would be red and yellow in $r(\sigma)$).
\end{proof}

\begin{lemma} If $\sigma$ is skew-merged and $P..S$ are points of
$\sigma$ then
\begin{enumerate}
\item[(i)] if $P,S$ are both red or both yellow then $S<P$
\item[(ii)] if $P,S$ are both blue or both green then $P<S$
\end{enumerate}
\end{lemma}
\begin{proof} Suppose that $P,S$ are both red.  Then there are points
$Q,R,T,U$ with
$P..Q..R$, $S..T..U$, $Q<R<P$,  and $T<U<S$.
Suppose, for a contradiction, that $P<S$.  Then, since $P..S..T..U$
and $PSTU\not\sim 3412$ we must have $P<U$.  Also, $S..Q$
is impossible, otherwise $PSQR\sim 3412$.  But now $PQSU\sim 2143$ which
is the required contradiction.

Suppose next that $P,S$ are both yellow.  Then, as $P..S$, $t(P)<t(S)$
in $t(\sigma)$ and $t(P),t(S)$ are red in $t(\sigma)$.  But we have
just seen that this means $t(S)..t(P)$ in $t(\sigma)$ and therefore
$S<P$ in $\sigma$.

For part (ii), if $P,S$ are both blue (green) then $s(P),s(S)$ are
both red (yellow) and $s(P)..s(S)$.  So, by part (i), $s(S)<s(P)$ and
therefore $P<S$.
\end{proof}

\begin{lemma}  Suppose that $\sigma$ is skew-merged with points
$R,B,G,Y$ coloured red, blue, green, yellow respectively.  Then

\begin{tabular}{llll}
(i) $R..Y$ & (ii) $G..B$ & (iii) $G<B$ & (iv) $Y<R$\\
(v) $R..B$ & (vi) $G..Y$ & (vii) $G<R$ & (viii) $Y<B$\\
\end{tabular}
%\[ R..Y, G..B, G<B, Y<R\]
\end{lemma}
\begin{proof} Since $R$ is red and $Y$ is yellow there are points
$S,T,U,V$ with
$R..S..T$, $U..V..Y$, $S<T<R$, $Y<U<V$.
Suppose that $Y..R$.  Then either
\begin{enumerate}
\item[(a)] $T<U$ in which case $UVST\sim 3412$, or
\item[(b)] $U<T$ in which case $UYRT\sim 2143$
\end{enumerate}
This contradiction proves that $R..Y$.

Symmetry arguments prove relations (ii), (iii), and (iv).  Thus, since
$s(G)$ is red and $s(B)$ is yellow in $s(\sigma)$, we have
$s(G)..s(B)$ and therefore $G..B$.  Next, since
$t(R),t(B),t(G),t(Y)$ are yellow, blue, green, red respectively, we
have $t(Y)..t(R)$ and $t(G)..t(B)$ in $t(\sigma)$ and so $Y<R$ and
$G<B$ in $\sigma$.

To prove part (v) we consider two points $X, Z$ such that $XZB\sim 213$
which exist since $B$ is blue.
Suppose that $B..R$.  Then either
\begin{enumerate}
\item[(a)] $T<X$ in which case $XBST\sim 3412$, or
\item[(b)] $X<T$ in which case $XZRT\sim 2143$
\end{enumerate}
This contradiction proves that $R..B$ and, as before,
symmetry arguments justify the other relations.
%$s(G),s(Y)$ are red, blue respectively in $s(\sigma)$ so
%$s(G)..s(Y)$ and G..Y
%$t(R),t(B),t(G),t(Y) are yellow, blue, green, red in $t(\sigma)$
%respectively so $t(Y)..t(B)$ and $t(G)..t(R)$; so $Y<B$ and $G<R$
\end{proof}

These lemmas have proved that the disposition of the red, blue, green,
and yellow points in the graph of a skew-merged permutation $\sigma$
is as given in Theorem \ref{graph}.
The next two lemmas show that the white points are disposed as claimed.
\begin{lemma} If $R,B,G,Y$ are points of colour red, blue, green,
yellow in a permutation, and $P$ is a white point, then

\begin{tabular}{llll}
(i) $R..P$ & (ii) $G..P$ & (iii) $P..B$ & (iv) $P..Y$\\
(v) $G<P$ & (vi) $Y<P$ & (vii) $P<R$ & (viii) $P<B$\\
\end{tabular}
\end{lemma}
\begin{proof}  Since $R$ is red there are two points $S,T$ with
$RST\sim 312$.  If $P..R$ then either $T<P$ in which case
$PST\sim 312$ so $P$ would be red, or $P<T$ in which case
$PRT\sim 132$ and $P$ would be green.  All the other
statements  follow by symmetry.
\end{proof}

To complete the proof of Theorem \ref{graph} we have
\begin{lemma} The white points of a
permutation are either increasing or decreasing.
\end{lemma}
\begin{proof}  From the definitions of red, blue, green, yellow every
triple $A..B..C$ of white points must satisfy $ABC\sim 123$ or
$ABC\sim 321$.  Since every triple is either increasing or decreasing
the lemma follows.
\end{proof}

\section{Enumeration}

In this section we use Theorem \ref{graph} to derive the following
theorem.
\begin{theorem} \label{main} The number of skew-merged permutations of
length $n$
is
\[{2n\choose n}-\sum_{m=0}^{n-1}2^{n-m-1}{2m\choose m}\]
\end{theorem}

To prove this we enumerate the skew-merged permutations according to their
number of white points.  Let $t_{i}(n)$ denote the number of
skew-merged permutations of length $n$ with exactly $i$ white points.
\begin{lemma} \label{eq1} $\sum_{i=0}^{n}(i+1)t_{i}(n)={2n \choose n}$
\end{lemma}
\begin{proof} Suppose that $\sigma$ is skew-merged and let
$\alpha,\beta$ be a pair of increasing and decreasing subsequences
whose union is $\sigma$.  Let ${\cal A},{\cal B}$ be the sets of points of
$\alpha,\beta$.  Consider a red point $R$ and let $S,T$ be the
corresponding points satisfying $R..S..T$ and $S<T<R$.  Suppose that
$R\in {\cal A}$.  Then, since $R..S$ and $S<R$, $S$ cannot also belong
to ${\cal A}$.  Therefore $S\in {\cal B}$ and, similarly, $T\in {\cal
B}$.  However, $S..T$ and $S<T$ and this is a contradiction.
Therefore all red points belong to ${\cal B}$.  By a similar argument
all yellow points belong to ${\cal B}$ also, and all blue and green
points belong to ${\cal A}$.

Suppose that $\sigma$ has $i$ white points which, without loss in
generality, we shall suppose are increasing.  Then at most one of the
white points can belong to ${\cal B}$.  It follows that there are at most
$i+1$ possibilities for the pair $(\alpha,\beta)$ and, by Theorem
\ref{graph}, all of these possibilities do indeed yield a
pair of increasing and decreasing subsequences whose union is $\sigma$.

The left-hand side of the equation in the lemma therefore counts the
number of increasing, decreasing pairs $(\alpha,\beta)$ whose union is
a skew-merged permutation.  However, we can count these in another
way.  If $|\alpha|=r$ we may choose the first components of the
points of ${\cal A}$
in ${n\choose r}$ ways and, independently, the second components in
${n\choose r}$ ways also.  So the number of $(\alpha,\beta)$ pairs is
therefore
\[\sum_{r=0}^{n}{n\choose r}^{2}={2n \choose n}\]
\end{proof}

\begin{lemma} \label{eq2} $\sum_{i=1}^{n}t_{i}(n)={2n-2 \choose n-1}$
\end{lemma}
\begin{proof}  The left-hand side of the equation in the lemma is the
number of skew-merged permutations with at least one white point.
These permutations are exactly those which are the union of an
increasing subsequence $\alpha$ and a decreasing subsequence $\beta$
that have a common point.  In such a permutation ($\sigma$, say) $\alpha$ is a
maximal increasing subsequence and $\beta$ is a maximal decreasing
subsequence.  It follows that the pair of Young tableaux which
correspond, in the Robinson-Schensted correspondence, to $\sigma$ are
shaped like
the one shown in Figure 3.

\begin{figure}[t]
        \centerline{\epsffile{Figure3.epsf}}
        \caption{Young tableau}
\end{figure}

Conversely, every such pair of Young tableaux corresponds to a
skew-merged permutation with at least one white point.  By the hook
formula \cite{Knuth} \S5.1.4, the number of such tableaux with
exactly $r$ cells in the first row is
\[\frac{n!}{n(r-1)!(n-r)!}={n-1 \choose r-1}\]
and hence the number of tableaux pairs is
\[\sum_{r=1}^{n}{n-1 \choose r-1}^{2}={2n-2 \choose n-1}\]
\end{proof}

Note that skew-merged permutations with no white points
correspond to Young tableau pairs
with a shape similar to Figure 3 but with a cell in the $(2,2)$
position.  Unfortunately, not every Young tableau pair of this form
gives a skew-merged permutation.

\begin{lemma} \label{i>2} For all $i>2$, $t_{i}(n)=t_{i-1}(n-1)$
\end{lemma}
\begin{proof} Suppose that $\sigma$ is a permutation of length $n$
with $i$ white points.  Then, by Theorem \ref{graph}, $\sigma-W$ is
independent of $W$ provided
only that $W$ is a white point of $\sigma$.  Since $i>2$ the deletion
of $W$ cannot change the colour of any point of $\sigma$ and so
$\sigma-W$ has $i-1$ white points.

Conversely, suppose that $\tau$ is of length $n-1$ with $i-1$ white
points which, since $i>2$ are either increasing or decreasing but not
both.  Then there is a unique permutation $\sigma$ with $i$ white
points such that $\sigma-W=\tau$ for some white point $W$ of
$\sigma$.  This one to one correspondence proves the lemma.
\end{proof}

\begin{lemma} Suppose that $\sigma$ is a skew-merged permutation with
either one white point (or no white points).  Then there exist points
$R,B,G,Y$ with colours red, blue, green, yellow such that either
\begin{enumerate}
\item[(i)]$RGWBY\sim 41352$ (or $RGBY\sim 3142$) and $W$ is the only point
(or there is no point) in $G..W..B$, or
\item[(ii)]$GRWYB\sim 25314$ (or $GRYB\sim 2413$) and $W$ is the only point
(or there is no point) in $R..W..Y$
\end{enumerate}
\end{lemma}
\begin{proof} Choose red, blue, green, yellow points $R,B,G,Y$ so that
$R,G$ are largest of their colour with respect to ``$..$'' and $B,Y$
are smallest of their colour (equivalently, $G,Y$ are largest of
their colour under ``$<$'' and $R,B$ are smallest of their colour).
According to Theorem \ref{graph}, $R, B, G, Y$ are ordered
under ``$..$'' as $R..G..B..Y$, $R..G..Y..B$, $G..R..B..Y$, or
$G..R..Y..B$.  Similarly there are four possible ways in which they
can be ordered under ``$<$''.

Consider the ordering $R..G..Y..B$.  Since $G$ is green there are
points $P,Q$ with $G..P..Q$ and $G<Q<P$.  Not both $P,Q$ can be blue
since the blue points are increasing, and nor, by hypothesis, can
both be white.  Further, neither can be red or green since $R..G$ and
$R$ and $G$ are the maximal red and green points under ``$..$''.  Thus at
least one of them, $P$ say is yellow.  Since the yellow points are
decreasing and $Y$ is the smallest yellow point under ``$..$'' we
have $Y..P$ or $Y=P$, and so $G<P\leq Y$.  By a similar argument based
on the condition that $Y$ is yellow we can deduce that $Y<G$, a
contradiction.  Thus $R..G..Y..B$ is impossible.

The symmetry conditions now also exclude the possibilities
$G..R..B..Y$ and also $G<Y<B<R$, and $Y<G<R<B$.

Suppose next that $R..G..B..Y$ and $Y<G<B<R$.  Since $G$ is green
there are points $G..P..Q$ with $G<Q<P$.  Since $Y<G$, $P$ and $Q$
cannot be yellow and so they must be white or blue with not both
white; it follows that $P<Q$, a contradiction.  Finally, symmetry
rules out the case $G..R..Y..B$, $G<Y<R<B$.

The remaining cases are
\begin{enumerate}
\item[(i)] $R..G..B..Y$ and $G<Y<R<B$
\item[(ii)] $G..R..Y..B$ and $Y<G<B<R$
\end{enumerate}
In case (i) a single white point $W$ must, by Theorem \ref{graph},
satisfy $G..W..B$ and $Y<W<R$ so that $RGWBY\sim 41352$ giving the
first alternative of the lemma.  Case (ii) gives the second
alternative.
\end{proof}


\begin{lemma} \label{i=0} $t_{1}(n)=t_{0}(n-1)$
\end{lemma}
\begin{proof} Suppose $\sigma$ is of length $n$ and has exactly one
white point.  Let $R,B,G,Y$ be the points guaranteed by the previous
lemma.  If we remove the single white point we are left with $4$
points such that
\begin{enumerate}
\item[(i)] $RGBY\sim 3142$ with no point between $G..B$ or
\item[(ii)] $GRYB\sim 2413$ with no point between $R..Y$
\end{enumerate}
These points remain coloured as they were ($GBY\sim 132$ ensures $G$ is
green, $RGB\sim 213$ ensures $B$ is blue etc) and so we have obtained a
sequence with no white points.  Conversely, the last lemma shows that
a sequence without white points has this form for
some $R,B,G,Y$.  If
we insert a point $W$ satisfying $G..W..B$ and $Y<W<R$ in case (i) and
$R..W..B$ and $G<W<B$ in case (ii) this point must be white (as it is
part of both an increasing sequence and a decreasing sequence in a
skew-merged decomposition, see the proof of Lemma \ref{eq1}).  We therefore
have a one-to-one
correspondence proving that $t_{1}(n)=t_{0}(n-1)$.
\end{proof}

Since $t_{n-i}(n)$ is independent of $n$ if $i\leq n-2$ (Lemma
\ref{i>2}) we may set $b_{i}=t_{n-i}(n)$ for all $i\leq n-2$.  Also,
we let $a_{n}=t_{0}(n)$ from which, by Lemma \ref{i=0}, we find
$t_{1}(n)=t_{0}(n-1)=a_{n-1}$.  Hence the number of skew-merged
permutations is
\begin{eqnarray*}
s_{n}&=&t_{0}(n)+t_{1}(n)+\ldots +t_{n}(n)\\
&=&a_{n}+a_{n-1}+b_{n-2}+\ldots +b_{0}
\end{eqnarray*}
Rewriting Lemmas \ref{eq1} and \ref{eq2} we obtain
\begin{eqnarray*}
a_{n}+2a_{n-1}+3b_{n-2}+4b_{n-3}+\ldots +(n+1)b_{0}&=&{2n\choose n}\\
a_{n-1}+b_{n-2}+b_{n-3}+\ldots +b_{0}={2n-2\choose n-1}
\end{eqnarray*}
These equations are easily solved.  Differencing reduces them to a
pair of low order inhomogeneous linear recurrence equations to which the
method of
generating functions may be applied.  We obtain the generating
function
\[\sum_{n=0}^{\infty}s_{n}x^{n}=\frac{(1-3x)}{(1-2x)\sqrt{1-4x}}\]
from which we find
\[s_{n}={2n\choose n}-\sum_{m=0}^{n-1}2^{n-m-1}{2m\choose m}\]
proving Theorem \ref{main}.  Finally, we have an asymptotic result.
\begin{corollary} \[\frac{s_{n}}{{2n\choose n}}\rightarrow 1/2\mbox{ as }
n\rightarrow\infty\]
\end{corollary}
\begin{proof} From Theorem \ref{main} it follows that
\[s_{n}=2s_{n-1}+\frac{n-2}{n}{2n-2\choose n-1}\]
In this equation we divide through by ${2n\choose n}$, and put
$r_{n}=s_{n}/{2n\choose n}$ to obtain
\[r_{n}=\frac{n}{2n-1}r_{n-1}+\frac{n-2}{4n-2}\] and take the limit as
$n\rightarrow\infty$.
\end{proof}

\noindent {\bf Acknowledgement} I thank Dominic Tulley for several
useful observations during the course of this work.

\begin{thebibliography}{99}
\bibitem{BK} A. Brandst\"adt, D. Kratsch: On partitions of
permutations into increasing and decreasing subsequences. Elektron.
Informationsverarb. Kybernet. 22 (1986), 263--273
\bibitem{KSW}A.E. K\'{e}zdy, H.S. Snevily, C. Wang: Partitioning
permutations into increasing and decreasing subsequences, J. Combinatorial
Theory A 74 (1996), 353--359.
\bibitem{Knuth} D.E. Knuth: Sorting and Searching (The Art of Computer
Programming volume 3), Addison Wesley, Reading, MA, 1973.
\bibitem{Stankova}  Z. E. Stankova: Forbidden subsequences, Discrete Math. 132
(1994),     291--316
\end{thebibliography}

\end{document}