Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Packing patterns into words"

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í toán học quốc tế đề tài: Packing patterns into words | Packing patterns into words Alexander Burstein Peter Hasto Department of Mathematics Department of Mathematics Iowa State University University of Michigan Ames IA 50011-2064 USA Ann Arbor MI 48105-1109 USA burstein@math.iastate.edu peter.hasto@helsinki.fi Toufik Mansour Department of Mathematics Haifa University 31905 Haifa Israel toufik@math.haifa.ac.il Submitted May 29 2003 Accepted Nov 14 2003 Published Nov 20 2003 MR Subject Classifications Primary 05A15 Secondary 05A16 Abstract In this article we generalize packing density problems from permutations to patterns with repeated letters and generalized patterns. We are able to find the packing density for some classes of patterns and several other short patterns. The string 213322 contains three subsequences 233 133 122 each of which is orderisomorphic or simply isomorphic to the string 122 i.e. ordered in the same way as 122. In this situation we call the string 122 a pattern. Herb Wilf first proposed the systematic study of pattern containment in his 1992 address to the SIAM meeting on Discrete Mathematics. However several earlier results on pattern containment exist for example those by Knuth 9 and Tarjan 15 . Most results on pattern containment actually deal with pattern avoidance in other words enumerate or consider properties of strings over a totally ordered alphabet which avoid a given pattern or set of patterns. There is considerably less research on other aspects of pattern containment specifically on packing patterns into strings over a totally ordered alphabet but see 1 3 7 12 14 . In fact all pattern packing except the one in 14 later generalized in 1 dealt with packing permutation patterns into permutations i.e. strings without repeated letters . In this paper we generalize the packing statistics and results to patterns over strings with repeated letters and relate them to the corresponding results on permutations. We deal THE ELECTRONIC JOURNAL OF COMBINATORICS 9 2 2003 R20 1 with monotone and .