Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Packing densities of patterns. | Packing densities of patterns Reid W. Barton Department of Mathematics Massachusetts Institute of Technology Cambridge MA 02139 rwbarton@ Submitted Aug 8 2004 Accepted Nov 5 2004 Published Nov 12 2004 Mathematics Subject Classifications Primary 05A15 Secondary 05A16 Abstract The packing density of a permutation K of length n is the maximum proportion of subsequences of length n which are order-isomorphic to K in arbitrarily long permutations Ơ. For the generalization to patterns K which may have repeated letters two notions of packing density have been defined. In this paper we show that these two definitions are equivalent and we compute the packing density for new classes of patterns. 1 Definition of packing density A pattern or word is a string of letters from a totally ordered alphabet E. Two patterns 1 and 2 are said to be order-isomorphic or simply isomorphic if they have the same length and any two symbols of 1 have the same order relation or as the symbols in the corresponding positions in 2. An occurrence of a pattern in a word Ơ is a subsequence of symbols of Ơ not necessarily consecutive which form a pattern order-isomorphic to . We use the notation k n for the set of all n-letter words on the standard k-letter alphabet k 1 2 . kg. The terms pattern and word are interchangeable but we will generally use them as in the last sentence of the previous paragraph that is we are counting occurrences of patterns in words. Note that since Ơ can contain repeated symbols multiple occurrences of in Ơ can be equal as sequences of letters in E but should be counted as distinct occurrences. For example the word Ơ 122 contains the pattern 12 twice not once. Definition 1 Let n be a collection of patterns of length m no two of which are isomorphic. For a word Ơ 2 k n we define v n ơ to be the total number of occurrences of patterns 2 n in Ơ. The density of n in Ơ is then d n ơ V n ơ m. THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 R80 1 We require that patterns .
