Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Enumeration Schemes for Permutations Avoiding Barred Patterns"

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í Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Enumeration Schemes for Permutations Avoiding Barred Patterns. | Enumeration Schemes for Permutations Avoiding Barred Patterns Lara Pudwell Department of Mathematics and Computer Science Valparaiso University Valparaiso IN 46383 Lara.Pudwell@valpo.edu Submitted May 18 2008 Accepted Feb 10 2010 Published Feb 15 2010 Mathematics Subject Classification 05A05 Abstract We give the first comprehensive collection of enumeration results for permutations that avoid barred patterns of length 4. We then use the method of prefix enumeration schemes to find recurrences counting permutations that avoid a barred pattern of length 4 or a set of barred patterns. 1 Introduction Let q q1 qm be a finite string of numbers. The reduction of q denoted red q is the string obtained by replacing the ith smallest letter s of q with i. For example the red 2674425 1452213. Given two permutations p G Sn q G Sm we say p contains q as a pattern if there exist 1 i1 im n such that red pi1 pim q. Otherwise p avoids q. This definition of pattern avoidance appears in the characterization of 1-stack sortable permutations 11 and the characterization of smooth Schubert varieties 6 . Further it introduces an interesting and well-studied enumeration problem namely count the elements of the set Sn Q p G Sn p avoids q for all q G Q . The focus of this paper is not the study Sn Q but a variation of pattern avoidance given by the following definitions. Given q G Sm b G 0 1 m the barred permutation q is the permutation obtained by copying the entries of qt and putting a bar over qi if and only if bi 1. Write Sm for the set of all barred permutations of length m. For example the complete set of barred permutations of length 2 is 12 12 12 12 21 21 21 21 . The author thanks an anonymous referee for several useful suggestions that simplified the organization of this paper. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R29 1 A barred permutation compactly encodes two permutations one of which contains the other. In particular let q be the permutation formed by deleting all .