Enumerating Permutations that Avoid Three Term Arithmetic Progressions

  • Arun Sharma

Abstract

It is proved that the number of permutations of the set $\{1, 2, \dots, n\}$ that avoid three term arithmetic progressions is at most ${(2.7)^n} \over 21$ for $n \ge 11$ and at each end of any such permutation, at least ${\lfloor {n \over 2} \rfloor} - 6$ entries have the same parity.

Published
2009-05-15
Article Number
R63