Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "The packing density of other layered permutations"

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: The packing density of other layered permutations | The packing density of other layered permutations Peter A. Hasto Department of Mathematics P. O. Box 4 00014 University of Helsinki Finland peter.hasto@helsinki.fi Submitted Aug 21 2002 Accepted Oct 10 2002 Published Oct 31 2002 MR Subject Classifications Primary 05A15 Secondary 05A16 Abstract In this paper the packing density of various layered permutations is calculated thus solving some problems suggested by Albert Atkinson Handley Holton Stromquist Electron. J. Combin. 9 2002 R5 . Specifically the density is found for layered permutations of type mi . mr when log r 1 min mj . It is also shown how to derive good estimates for the packing density of permutations of type k 1 k when k 3. Both results are based on establishing the number of layers in near optimal permutations using a layer-merging technique. 1 Introduction Let a E Sn the symmetric group of n letters and n E Sm. The number of occurrences of n in a is the number of m element subsets E of n 1 2 . n such that ơ e and n are isomorphic as mappings of ordered sets . For instance the permutation 1374625 contains 5 occurrences of the permutation 1423 namely 1746 1745 1725 3746 and 3745. Two quite different problems related to such permutation containment have been studied the number or characterization of permutations not containing a given permutation e.g. 2 5 6 8 and the maximum number of containments of a given permutation 1 4 7 . It is the latter problem that will concern us in this paper. Let us denote the number of times that n E Sm is contained in a E Sn by V n a . If we divide this number by the total number of subsequences of a of length m for m n we get the density of n in a V n a d n a znA . mJ Since we want to determine the maximum number of containments we further define dn n maxd n a . ơeSn Supported in part by the Academy of Finland THE ELECTRONIC JOURNAL OF COMBINATORICS 9 2 2002 R1 1 We say that a permutation ơ G Sn is n-maximal if dn n d n ơ . It turns out that dn n is decreasing in n and .