\documentclass{article}
\usepackage{amsmath,amssymb}
\usepackage{theorem}
\textwidth 6.5in
\hoffset-.8in
\pagestyle{myheadings} 
          \markright{\sc the electronic journal of combinatorics 5 (1998), Comment for \#R6\hfill} 
          \thispagestyle{empty} 
\begin{document}
\noindent
\begin{center}
Comment on\\ ``Permutations which are the Union of an Increasing and a Decreasing Subsequence,'' by M.D. Atkinson.\end{center} 
\begin{center}by Volker Strehl\\ February 17, 1998.\end{center}

\vspace{.2in}

These comments contain a somewhat shorter proof of Atkinson's Theorem 2 and give some pointers to closely related literature.


Let $s_n$ denote the set of {\it skew-merged} permutations of $[1..n]$.
The characteristic property of these permutations is precisely described
in the title of Atkinson's article. Each such permutation,
if represented as a cloud of points on a $n \times n$-grid in the
traditional manner, has a number $k$ (where $0 \leq k \leq n)$ of
{\it  white} elements (see Atkinson, Theorem 1).
These are the elements that simultaneously belong to an increasing
subsequence of maximum length and to a decreasing subsequence of
maximum length. We will denote by $t_k(n)$ the set elements of $s_n$
with precisely $k$ white elements (which form an increasing or decreasing
sequence of ``contiguous'' elements).
For further reference we introduce the set
\[
y_n := t_1(n) + t_2(n) + \ldots + t_n(n)
\]
of skew-merged permutations with {\it at least one} white element.
In the sequel I use the symbols $s_n, t_k(n), y_n$ also to denote the
cardinalities of the corresponding sets; this follows Atkinson's
notation.
Equality signs should then be read as ``there exists a bijection''.
Finally I introduce the set $z_n$ of skew-merged permutation where
exactly one of the white elements has been {\it marked}.
Using the convention just mentioned we may simply write
\[
z_n = 1\cdot t_1(n) + 2 \cdot t_2(n) + \ldots + n \cdot t_n(n)
\]
More specifically, for $a,b$ such that $0 \leq a,b < n$ and
$a+b=n+1$ $z_{a,b}$ will denote the set of all elements of $z_n$
such that the underlying permutation is the union of an increasing subsequence
of length $a+1$ and a decreasing subsequence of length $b+1$ (both are
necessarily monotone subsequences of either kind of maximal length).

Lemma 9 of Atkinson's article, proved using Schensted's theorem
\cite{Sch61}, stated:
\begin{equation}
y_n = \sum_{a=0}^{n-1} \binom{n-1}{a}^2 = \binom{2(n-1)}{n-1}
\end{equation}
A proof of this is already contained
in the paper by Baer and Brock \cite{BB62}, see Theorem 9, p. 292.,
but these authors already point to the work by Schensted in \cite{Sch61},
even though Schensted's article had not yet appeared when they
submitted their paper, see the footnote on p.286 of \cite{BB62}.

Our new proof of Atkinson's Theorem 2 is via
Brock's identity \cite{B60},\cite{BB62}:
\begin{equation}
z_{a,b} - z_{a-1,b} - z_{a,b-1} = \binom{a+b}{a}^2
\end{equation}
Equation (2) first appeared as a problem, posed by P. Brock,
in the SIAM review \cite{B60}. It is not difficult to see that
\[
z_{a,b} = \sum_{i=0}^{a}\sum_{j=0}^{b}
\binom{i+j}{j}
\binom{a-i+j}{a-i}
\binom{b-j+i}{i}
\binom{a-i+b-j}{b-j}
\]
But if these sums are substituted for the $z$-terms in (2), then
a binomial identity of considerable complexity shows up --- this is the
way in which the problem was presented. A (rather involved)
proof of (2) was given in the Appendix 1 of \cite{BB62}.
A proof of (2) using generating functions was given by Slepian \cite{Sl62},
and this approach was then taken up by Carlitz \cite{C64}, which
marks only the beginning of interesting ``generatingfunctionological''
investigations, variations, extensions by Carlitz and many others.
A combinatorial proof of (2) was first presented by Church, jr.
in \cite{Ch85}, and independently by Strehl in \cite{S88}. The idea
is indeed very simple:
\begin{quote}
Consider the elements of $z_{m,n}$. If the marked white element
is not the leftmost white element, then the marked element and
its predecessor (also a white element) can be lumped together.
Carrying over the mark to this new element, we obtain either an
element of $z_{a-1,b}$ or $z_{a,b-1}$, depending on whether the
sequence of white elements was increasing or decreasing. This
mapping is reversible. The elements of $z_{m,n}$ left untouched
are those elements, where the leftmost white element is marked.
But marking the leftmost white element is as good as not
marking at all -- so this set is in bijection with skew-merged
permutations of length $n$ which are unions of an increasing subsequence of
length $a+1$ and a decreasing subsequence of length $b+1$.
\end{quote}
Note that by summing over all $a,b$ in (2) we get
\[
z_n - 2 z_{n-1} =
\sum_{a+b=n-1} \binom{a+b}{a}^2 = \binom{2(n-1)}{n-1} = y_n
\]
which can also be established directly using the combinatorial argument above.
Induction now leads to
\begin{equation}
z_{n} = \sum_{m=1}^n 2^{n-m} y_m
\end{equation}

\bigskip

We can now give our new proof of Atkinson's Theorem 2:
\[
s_n = \binom{2n}{n} - \sum_{m=0}^{n-1} 2^{n-m-1} \binom{2m}{m}
\]
or equivalently, by (1) and (3),
\begin{equation}
y_{n+1} = s_n + \sum_{m=1}^{n-1} 2^{n-m} y_m = s_n + z_n
\end{equation}
By Lemmas 10 and 12 of Atkinson's paper
\[
t_0(n) = t_1(n+1)~~\hbox{and}~~t_k(n) = t_{k+1}(n+1)~~(k \geq 2)
\]
so that (4) is equivalent
\[
t_2(n+1) = t_1(n) + z_n
\]
But this is true due to the simple combinatorial observation
that the two white elements, forming an increasing (decreasing, resp.)
sequence, from an element of the l.h.s. can be lumped together into one
{\it marked} element of the decreasing (increasing, resp.)
white sequence of an element on the r.h.s., which gives
an element of $z_n$. Some care has to be taken if the white sequence
on the r.h.s. degenerates into one element, which introduces the
additional term $t_1(n)$. (A similar reasoning could already be
applied to (4)).


\bigskip


What is perhaps more important than presenting a simpler proof is
to point out that the enumeration of skew-merged permutations
(with at least one white element), as initiated by the work of Baer
and Brock, has a long history and has,
via Brock's identity, given rise to many interesting investigations,
in particular on the associated generating functions.
The seminar report~\cite{S88} contains much of the history and
some of my own work in this field, a comprehensive treatment is given in my
``Habilitationsschrift''~\cite{S90}, a short account of all
that has been presented at the 4th FPSAC conference in Montr\'eal\cite{S92}.

\begin{thebibliography}{9}

\bibitem{B60}
P. Brock, On a binomial identity arising from a sorting problem, problem 60-2,
{\it SIAM Review} 6 (1964), 20-30.
\bibitem{Sch61}
C. Schensted, Longest increasing and decreasing sequences,
{\it Canad. J. Math.} 13 (1961), 179-191.
\bibitem{BB62}
R.M. Baer and P. Brock, Natural sorting,
{\it SIAM Journal} 10 (1962), 284-304.
\bibitem{Sl62}
D. Slepian,
Solution to problem 60-2,
{\it SIAM Review} 4 (1962),  396-398.
\bibitem{C64}
L.  Carlitz,
A binomial identity arising from a sorting problem,
{\it SIAM Review} 6 (1964), 20-30.
\bibitem{Ch85}
C.A. Church, jr.,
Combinatorial proof of a sorting problem identity,
{\it Fibonacci Quart.} 33 (1985), 366-368.
\bibitem{S88}
V. Strehl, Endliche Funktionen und spezielle Funktionen: eine kombinatorische
Theorie zu einer Identit\"at von P. Brock und deren Erweiterungen.
{\it Seminaire Lotharingien de Combinatoire}, 17e session, Bienno,
1987.
Published in {\it Publications I.R.M.A. Strasbourg},
Actes du S\'eminaire, 1988, 348/S-17, 23-67.
\bibitem{S90}
V. Strehl, {\it Zykel-Enumeration bei lokal strukturierten Funktionen.}
Habilitationsschrift, 311 p., Universit\"at  Erlangen, 1992.
\bibitem{S92}
V. Strehl, Combinatorics of Special Functions: Facets of Brock's Identity.
Invited talk presented at the 4th Colloquium {\it Formal Power Series and
Algebraic Combinatorics}, Montr\'eal 1992.
(see the conference proceedings published by LaCIM, pp. 363-378)
\end{thebibliography}

\bigskip
\noindent
Volker Strehl\\
Department of Artificial Intelligence (Informatik 8)\\
University of Erlangen-N\"urnberg\\
Am Weichselgarten 9\\
D-91058 Erlangen, Germany\\
\texttt{strehl@informatik.uni-erlangen.de}
\end{document}

