tailieunhanh - Báo cáo toán học: "Wilf classes of pairs of permutations of length 4"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Wilf classes of pairs of permutations of length 4. | Wilf classes of pairs of permutations of length 4 Ian Le Mathematics Department Harvard University 1 Oxford St. Cambridge MA 02138 Submitted Nov 14 2004 Accepted Apr 24 2005 Published May 26 2005 Mathematics Subject Classifications 05A05 05A15 Abstract SnU1 2 r denotes the set of permutations of length n that have no subsequence with the same order relations as any of the i- In this paper we show that Sn 1342 2143 1 Sn 3142 2341 1 and Sn 1342 3124 1 Sn 1243 2134 1-These two facts complete the classification of Wilf-equivalence classes for pairs of permutations of length four- In both instances we exhibit bijections between the sets using the idea of a block and in the former we find a generating function for Sn 1342 2143 . 1 Introduction Let Sn denote the symmetric group of permutations of 1 2 . n. We say that a permutation a 2 Sn contains another permutation 2 Sm m n if there exists i1 i2 . im with i1 i2 im such that a ik a il if and only if k l for all k and l . the subsequence a i1 a i2 . a im has the same order relations as 1 2 . m . For example the sequence 3167452 contains the permutation 132 shown in bold while 42531 does not contain 123. We sometimes say that a i1 a i2 . a im is an occurrence of in a or that a i1 a i2 . a im is a subsequence of a. We say that a avoids if a contains no occurrences of . For example 42531 avoids 123 and 32154687 avoids both 231 and 312. We denote the set of permutations in Sn that avoid 1 2 . r by Sn 1 2 . r . A problem of much interest is to determine Please send correspondence to the following address 67 Danville Dr- Princeton Jct- NJ 08550 THE ELECTRONIC JOURNAL OF COMBINATORICS 12 2005 R25 1 Sn 1 2 . r I the number of elements in Sn 1 2 . r . For example a result of Erdos-Szekeres tells us that Sn 123 k l 321 0 for n kl k l. Also it is well known that Sn 132 n i 2 n Cn the nth Catalan number 5 . Another problem is to determine when for some two permutations 1 2 2 Sm Sn 1 ISn 2 for all n. In this case we say that 1 and 2