A Note on 3-free Permutations

Let $θ(n)$ denote the number of permutations of \1,2,…,n\ that do not contain a 3-term arithmetic progression as a subsequence. Such permutations are known as 3-free permutations. We present a dynamic programming algorithm to count all 3-free permutations of \1,2,…,n\. We use the output to extend and correct enumerative results in the literature for $θ(n)$ from $n=20$ out to $n=90$ and use the new values to inductively improve existing bounds on $θ(n)$.