Enumerating Permutations that Avoid Three Term Arithmetic Progressions

Arun Sharma


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.

Full Text: PDF