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...