tailieunhanh - Phân loại các lớp học

Một hoán vị? được cho là một subpermutation của một hoán vị? (Hoặc được tham gia vào ) Nếu? có một dãy được sắp xếp trong cùng một cách tương đối. Đối với ví dụ 231 là một subpermutation của 35412 vì 351 dãy của nó có cùng một khuôn mẫu tạp chí điện tử của tổ hợp 12 (2005), # R31 1 là 231. Chúng tôi nói như vậy? tránh? nếu? không phải là một subpermutation?. Lý thuyết phát triển các mô hình hoán vị là một phần thành lập tổ hợp (xem, ví dụ, [12]). Lý thuyết này đã được thúc đẩy bởi việc nghiên. | Sorting classes M. H. Albert R. E. L. Aldred Department of Computer Science University of Otago malbert@ M. D. Atkinson Department of Computer Science University of Otago mike@ D. A. Holton Department of Mathematics and Statistics University of Otago dholton@ Department of Mathematics and Statistics University of Otago raldred@ C. C. Handley Department of Computer Science University of Otago chandley@ D. J. McCaughan Department of Mathematics and Statistics University of Otago dmccaughan@ H. van Ditmarsch Department of Computer Science University of Otago hans@ Submitted Dec 20 2004 Accepted Jun 17 2005 Published Jun 26 2005 Mathematics Subject Classifications 05A15 05A16 Abstract Weak and strong sorting classes are pattern-closed classes that are also closed downwards under the weak and strong orders on permutations. They are studied using partial orders that capture both the subpermutation order and the weak or strong order. In both cases they can be characterised by forbidden permutations in the appropriate order. The connection with the corresponding forbidden permutations in pattern-closed classes is explored. Enumerative results are found in both cases. 1 Introduction A permutation is said to be a subpermutation of a permutation a or to be involved in a if a has a subsequence that is ordered in the same relative way as . For example 231 is a subpermutation of 35412 because of its subsequence 351 which has the same pattern THE ELECTRONIC JOURNAL OF COMBINATORICS 12 2005 R31 1 as 231. We say that Ơ avoids K if K is not a subpermutation of Ơ. The developing theory of permutation patterns is now a well-established part of combinatorics see for example 12 . This theory was originally motivated by the study of the sortable permutations associated with various computing devices abstract data types such as stacks and deques 8 token passing networks 3 or hardware .