tailieunhanh - Báo cáo toán học: " Completion of the Wilf-Classification of 3-5 Pairs Using Generating Trees"

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: Completion of the Wilf-Classification of 3-5 Pairs Using Generating Trees. | Completion of the Wilf-Classification of 3-5 Pairs Using Generating Trees Mark Lipson Harvard University Department of Mathematics Cambridge MA 02138 Submitted Jan 31 2006 Accepted Mar 15 2006 Published Apr 4 2006 Mathematics Subject Classifications 05A05 05A15 Abstract A permutation K is said to avoid the permutation T if no subsequence in K has the same order relations as T. Two sets of permutations Hl and H2 are Wilf-equivalent if for all n the number of permutations of length n avoiding all of the permutations in H1 equals the number of permutations of length n avoiding all of the permutations in H2. Using generating trees we complete the problem of finding all Wilf-equivalences among pairs of permutations of which one has length 3 and the other has length 5 by proving that 123 32541 is Wilf-equivalent to 123 43251 and that 123 42513 is Wilf-equivalent to 132 34215 . In addition we provide generating trees for fourteen other pairs among which there are two examples of pairs that give rise to isomorphic generating trees. 1 Introduction Pattern Avoidance and Wilf-Equivalence We denote a permutation of the numbers 1 2 . n by M 2 n where i i for 1 i n. For permutations 1 2 n and T T1T2 Tm we say that contains T if there exist indices 1 i1 i2 im n such that ik il if and only if Tk Tị. If no such indices exist then we say that avoids T. For a set of permutations n we let Sn n denote the set of permutations of length n avoiding all of the permutations T 2 n and we let sn n denote the cardinality of Sn n . Two sets n and E are said to be Wilf-equivalent if sn n sn E for all n. Please send correspondance to the following address 9 Sheridan St. Lexington MA 02420 THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R31 1 Wilf-equivalence defines an equivalence relation on sets of permutations and we call the resulting equivalence classes Wilf-classes. The problem of counting the permutations avoiding a given permutation or set of permutations is a .