\magnification=1200
\hsize=4in
\overfullrule=0pt
\nopagenumbers
\noindent
%
%
{\bf Emeric Deutsch, A. J. Hildebrand and Herbert S. Wilf}
%
%
\medskip
\noindent
%
%
{\bf Longest Increasing Subsequences in Pattern-Restricted Permutations}
%
%
\vskip 5mm
\noindent
%
%
%
%
Inspired by the results of Baik, Deift and Johansson on the limiting
distribution of the lengths of the longest increasing subsequences in
random permutations, we find those limiting distributions for
pattern-restricted permutations in which the pattern is any one of
the six patterns of length 3. We show that the (132)-avoiding case is
identical to the distribution of heights of ordered trees, and that
the (321)-avoiding case has interesting connections with a well known
theorem of Erd\H os-Szekeres.
\bye