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@ 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 . 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 . 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
