Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Longest increasing subsequences in pattern-restricted permutations | Longest increasing subsequences in pattern-restricted permutations Emeric Deutsch Polytechnic University Brooklyn NY 11201 deutsch@ A. J. Hildebrand University of Illinois Urbana IL 61801 hildebr@ Herbert S. Wilf University of Pennsylvania Philadelphia PA 19104-6395 wilf@ Submitted Apr 8 2003 Accepted Apr 21 2003 Published May 3 2003 MR Subject Classifications 05A16 05A05 Abstract 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 Erdos-Szekeres. 1 Introduction A great deal of spectacular work has been done on determining the distribution of the length of the longest increasing subsequence LIS p in a random permutation p. This work culminated in the paper of Baik Deift and Johansson 2 which found the limiting distribution function. Historically the average length fj n of the LIS had been found to be y n 2 6 and then 2ựn 12 . The correct order of magnitude was established in 18 where it was shown to be A n. Next the standard deviation ơ n had been estimated 13 to be approximately n1 6 but was not proved to be so. Finally in 2 the complete limiting distribution function of the normalized random variable LIS ia n n1 6 was determined. We can ask the same questions in some given subset of the set of all permutations. For example what is the distribution of the length of the longest increasing subsequence in a randomly chosen permutation from the set of those that avoid the pattern1 231 1A permutation p avoids 132 resp. 231 321 if there do not exist 1 i j k n . p i p k p j resp. p k p i p j p i p j p k . .
