Enumerating permutations that avoid three term arithmetic progressions Arun Sharma Department of Mathematics University of California, Berkeley Berkeley, CA 94720 asharma@ 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 () 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@ 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 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 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
