TAILIEUCHUNG - Báo cáo toán học: "Growth rates for subclasses of Av(321)"

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:Growth rates for subclasses of Av(321). | Growth rates for subclasses of Av 321 M. H. Albert1 M. D. Atkinson1 R. Brignall2 N. Ruskuc3 Rebecca Smith4 and J. West5 department of Computer Science University of Otago department of Mathematics and Statistics The Open University 3School of Mathematics and Statistics University of St Andrews department of Mathematics SUNY Brockport 5Heilbronn Institute for Mathematical Research University of Bristol Submitted Jan 15 2010 Accepted Sep 27 2010 Published Oct 22 2010 Mathematics Subject Classification 05A05 05A16 Abstract Pattern classes which avoid 321 and other patterns are shown to have the same growth rates as similar but strictly larger classes obtained by adding articulation points to any or all of the other patterns. The method of proof is to show that the elements of the latter classes can be represented as bounded merges of elements of the original class and that the bounded merge construction does not change growth rates. 1 Introduction A pattern class is roughly a collection of permutations that satisfy certain restrictions on the configurations of their elements formal definitions can be found in the next section . Most commonly the restrictions are expressed by prohibiting particular types of subsequence. For example the collection of all permutations containing no descending subsequence of length 3 is a pattern class. More generally if B is any set of such restrictions we write Av B to denote the pattern class they define. The study of such classes dates back at least to work of Knuth 7 or even further to the celebrated result of Erdos and Szekeres 5 that every permutation of length greater than ad must include either an ascending subsequence of length a 1 or a descending one of length d 1. Initially research into pattern classes focussed on enumeration - determining the number of permutations of length n in a given pattern class. An early result of this type 7 was that Av 231 and Av 321 are both enumerated by the Catalan sequence and by easy symmetries

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học