Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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: Shape-Wilf-Ordering on Permutations of Length 3. | Shape-Wilf-Ordering on Permutations of Length 3 Zvezdelina Stankova Dept. of Mathematics and Computer Science Mills College Oakland California USA stankova@mills.edu Submitted Sep 19 2006 Accepted Aug 9 2007 Published Aug 20 2007 Mathematics Subject Classification 05A20 Abstract The research on pattern-avoidance has yielded so far limited knowledge on Wilf-ordering of permutations. The Stanley-Wilf limits limn 1 n Sn T and further works suggest asymptotic ordering of layered versus monotone patterns. Yet Bóna has provided essentially the only known up to now result of its type on complete ordering of Sk for k 4 Sn 1342 Sn 1234 Sn 1324 for n 7 along with some other sporadic examples in Wilf-ordering. We give a different proof of this result by ordering S3 up to the stronger shape-Wilf-order SY 213 Sy 123 Sy 312 for any Young diagram Y derive as a consequence that Sy k 2 k 1 k 3 t Sy k 1 k 2 k 3 t Sy k 3 k 1 k 2 t for any T 2 Sk and find out when equalities are obtained. In particular for specific Y s we find out that SY 123 SY 312 coincide with every other Fibonacci term. This strengthens and generalizes Bona s result to arbitrary length permutations. While all length-3 permutations have been shown in numerous ways to be Wilf-equivalent the current paper distinguishes between and orders these permutations by employing all Young diagrams. This opens up the question of whether shape-Wilf-ordering of permutations or some generalization of it is not the true way of approaching pattern-avoidance ordering. 1 Introduction We review first basic concepts and results that are crucial to the present paper and direct the reader to 18 19 22 23 for further introductory definitions and examples on pattern-avoidance. A permutation T of length k is written as a1 a2 . ak where T i ai5 1 i k. For k 10 we suppress the commas without causing confusion. As usual Sn denotes the symmetric group on n 1 2 . ng. THE ELECTRONIC JOURNAL OF COMBINATORICS 14 2007 R56 1 Definition 1. Let T and V .
