TAILIEUCHUNG - 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

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.