A Note on 3-free Permutations

Let $\theta (n)$ denote the number of permutations of $\{1,2,\dots ,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,\dots ,n\}$. We use the output to extend and correct enumerative results in the literature for $\theta (n)$ from $n=20$ out to $n=90$ and use the new values to inductively improve existing bounds on $\theta (n)$.