tailieunhanh - Báo cáo toán học: "Permutations generated by a stack of depth 2 and an infinite stack in series"

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: Permutations generated by a stack of depth 2 and an infinite stack in series. | Permutations generated by a stack of depth 2 and an infinite stack in series Murray Elder Department of Mathematics Stevens Institute of Technology Hoboken NJ USA http .stevens. edu melder murrayelder@ Submitted Oct 17 2005 Accepted Jul 31 2006 Published Aug 7 2006 Mathematics Subject Classification 05A05 Abstract We prove that the set of permutations generated by a stack of depth two and an infinite stack in series has a basis defining set of forbidden patterns consisting of 20 permutations of length 5 6 7 and 8. We prove this via a canonical generating algorithm. 1 Introduction In this article we examine the set of permutations that can be generated by passing the sequence 1 2 . n through a stack of depth two followed by an infinite stack as in Figure 1. The depth of a stack is the number of tokens it can hold including one space at the top for passing tokens through the stack. By convention we pass tokens right to left. We prove in Theorem 9 that a permutation can be generated in this way if and only if it avoids a list of sub-patterns of 20 permutations and furnish a deterministic procedure Algorithm 4 for generating them. These permutations were found initially by computations with a stack of depth two and a stack of depth k for increasing k by Linton 6 . The current interest in permutations that avoid sub-patterns could perhaps be traced back to Knuth who proved that a permutation can be generated by passing an ordered sequence though a single infinite stack if and only if it avoids the subsequence 3 1 2 5 1. For two infinite stacks in series the set of avoided minimal sub-patterns that characterize the permutations that can be generated is infinite 7 . But somewhere between a 1 Actually he proved the equivalent fact that a permutation can be sorted if and only if it avoids 2 3 1. He also showed that they are enumerated by the Catalan numbers. THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R68 1 1 2 3 4 5 2 3 4 5 3 4 5 B u A B LU A 1 B fij