Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "A short proof for the number of permutations containing pattern 321 exactly once"
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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: A short proof for the number of permutations containing pattern 321 exactly once. | A short proof for the number of permutations containing pattern 321 exactly once Alexander Burstein Department of Mathematics Howard University Washington DC 20059 USA aburstein@howard.edu Submitted May 30 2011 Accepted Aug 23 2011 Published Sep 2 2011 Mathematics Subject Classification 05A05 05A15 Abstract We give a short proof for J. Noonan s result on the number of permutations containing pattern 321 exactly once. In this paper we give a short proof for the result of Noonan 3 that the number of permutations of length n containing exactly one occurence of pattern 321 is -U2 . n n 3 To be precise Noonan considered permutations avoiding patterns 123 but taking the reversal of those i.e. reading them right-to-left we get an additional nice property. This fact was later re-proved by Noonan and Zeilberger 4 using generating functions. A pattern is an equivalence class of sequences under order isomorphism. Two sequences T1 and t2 over totally ordered alphabets are order-isomorphic if for any pair of positions i and j we have t1 ĩ ũt1 j if and only if T2 i ŨT2 j where is any one of . We say that a sequence Ơ contains a pattern t if Ơ has a subsequence order-isomorphic to t otherwise we say that Ơ avoids t. Example 1 The sequence Ơ 3614725 contains pattern t 321 since Ơ has a subsequence 642 order-isomorphic to 321. Notation 2 The set of permutations in Sn i.e. of length n avoiding pattern t is denoted Sn t . The set of permutations in Sn containing pattern t exactly r times is denoted Sn t r . In fact in Example 1 642 is the only occurrence of 321 in Ơ. In 1995 Noonan 3 enumerated permutations of length n containing exactly one occurrence of pattern 321. Theorem 3 Noonan Sn 321 1 2n . n n 3 THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2 2011 P21 1 Figure 1 An injection f Sn 321 1 Sn 2 321 . The 3 and 1 in the unique occurrence of 321 are each replaced by two new points in blue . The proofs in 3 4 enumerated a more general set of objects with additional restrictions and an