Đang chuẩn bị liên kết để tải về tài liệu:
Enumerating permutations that avoid three term arithmetic progressions Arun Sharma Department of

Enumerating permutations that avoid three term arithmetic progressions Arun Sharma Department of Mathematics University of California, Berkeley Berkeley, CA 94720 asharma@math.berkeley.edu Submitted: Aug 15, 2008; Accepted: May 4, 2009; Published: May 15, 2009 Mathematics Subject Classifications: 05A15, 05C55. Abstract It is proved that the number of permutations of the set {1, 2, 3, . . . , n} that n avoid three term arithmetic progressions is at most (2.7) for n ≥ 11 and at 21 each end of any such permutation, at least ⌊ n ⌋−6 entries have the same parity. 2 1. Introduction Let S be an n-element set. | Enumerating permutations that avoid three term arithmetic progressions Arun Sharma Department of Mathematics University of California Berkeley Berkeley CA 94720 asharma@math.berkeley.edu Submitted Aug 15 2008 Accepted May 4 2009 Published May 15 2009 Mathematics Subject Classifications 05A15 05C55 Abstract It is proved that the number of permutations of the set 1 2 3 . n that 1.1 2.7 1 avoid three term arithmetic progressions is at most 21 for n 11 and at each end of any such permutation at least nJ 6 entries have the same parity. 1. Introduction Let S be an n-element set of positive integers. By a permutation of S we mean a one-to-one sequence ai a2 . an where ai G S for each i 1 i n. We use letters from the Greek alphabet to denote permutations. A permutation a ai a2 . an of S is said to contain a k-term arithmetic progression briefly a k-progression if there exists a set of indices ii i2 ik such that the subsequence ai1 ai2 . aik is either an increasing or a decreasing arithmetic progression. If a contains no k-progression we say it is k-free. The main goal of this paper is to examine the following Problem. How many permutations of the segment n 1 2 3 . n are 3-free This avoidance problem in Ramsey Theory on the integers was first raised in 4 where after a prodigious expenditure of computer time the number call it ớ n of such permutations was computed for n 20 see Appendix . Deeming the task of finding a formula for ỡ n to be hopelessly difficult the editor of the Problem Section of the Monthly observed that several conjectures concerning the behavior of the function ỡ n 0 n 1 suggested themselves. In particular he asked if it were true that lim 2. 11. u n More recently another intriguing question about ỡ n has been raised see 1 Problem 7.11 asking whether lim ớ n exists. These questions are still open and apart n from the bounds for ỡ n found in 2 not much else is known about the behavior of ớ n . In this paper the method applied in 2 to obtain the lower bound