Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Longest alternating subsequences in pattern-restricted permutations. | Longest alternating subsequences in pattern-restricted permutations Ghassan Firro Department of Mathematics University of Haifa 31905 Haifa Israel gferro@ Toufik Mansour Department of Mathematics University of Haifa 31905 Haifa Israel toufik@ Mark C. Wilson Department of Computer Science University of Auckland Private Bag 92019 Auckland New Zealand mcw@ Submitted Sep 20 2006 Accepted Apr 29 2007 Published May 9 2007 Mathematics Subject Classification 05A05 05A15 05A16 Abstract Inspired by the results of Stanley and Widom concerning the limiting distribution of the lengths of longest alternating subsequences in random permutations and results of Deutsch Hildebrand and Wilf on the limiting distribution of the longest increasing subsequence for pattern-restricted permutations we find the limiting distribution of the longest alternating subsequence for pattern-restricted permutations in which the pattern is any one of the six patterns of length three. Our methodology uses recurrences generating functions and complex analysis and also yields more detailed information. Several ideas for future research are listed. 1 Introduction Let Sn be the symmetric group of permutations of 1 2 . n and let X X1X2 Xn 2 Sn. An increasing subsequence in X of length is a subsequence . .Xi satisfying Xix Xi2 Xị note that we are not considering subwords so the indices i1 . i need not be contiguous . Several authors have studied properties of the length of the THE ELECTRONIC JOURNAL OF COMBINATORICS 14 2007 R34 1 longest increasing subsequence isn k of a permutation K and the associated random variable isn given by taking an element of Sn uniformly at random. Logan and Shepp 10 and Vershik and Kerov 13 showed that the asymptotic expectation satisfies E isn ny -K Sn isn 2ựn when n 1 and the limiting distribution of a suitably scaled and translated version of isn was determined by Baik Deift and Johansson 4 . Recently Stanley 12 developed
