%I M1201 #155 May 31 2023 10:49:22
%S 1,1,2,4,10,20,48,104,282,496,1066,2460,6128,12840,29380,74904,212728,
%T 368016,659296,1371056,2937136,6637232,15616616,38431556,96547832,
%U 198410168,419141312,941812088,2181990978,5624657008,14765405996,41918682488,121728075232
%N Number of permutations of [n] with no 3-term arithmetic progression.
%C The n-th term is the number of "non-averaging" permutations of 1,2,3,...,n. That is, the n-th term is the number of ways of rearranging 1,2,3,...,n so that for each pair x, y, the number (x+y)/2 does not appear between x and y in the list. For example, when n = 4, the 10 non-averaging permutations of 1,2,3,4 are: {1 3 2 4}, {1 3 4 2}, {2 1 4 3}, {2 4 1 3}, {2 4 3 1}, {3 1 2 4}, {3 1 4 2}, {3 4 1 2}, {4 2 1 3}, {4 2 3 1}. - Tom C. Brown (tbrown(AT)sfu.ca), Jul 20 2010
%C The tightest known bounds on the number of 3-free permutations of 1,2,3,...,n appear in the paper in the Electronic Journal of Combinatorial Number Theory listed below. - _Bill Correll, Jr._, Nov 08 2017
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Alois P. Heinz, <a href="/A003407/b003407.txt">Table of n, a(n) for n = 0..200</a> (terms up to n=90 from Bill Correll, Jr. and Randy W. Ho)
%H B. Correll, Jr., <a href="http://dx.doi.org/10.1109/SSP.2012.6319740">The Density of Costas Arrays And Three-Free Permutations</a>, Proceedings of IEEE Statistical Signal Processing Conference, 2012, 492-495.
%H Bill Correll, Jr. and Randy W. Ho, <a href="http://math.colgate.edu/~integers/r55/r55.Abstract.html">A note on 3-free permutations</a>, INTEGERS, A17 (2017), #A55.
%H Bill Correll, Jr. and Randy W. Ho, <a href="https://arxiv.org/abs/1712.00105">A note on 3-free permutations</a>, arXiv:1712.00105 [math.CO], 2017.
%H Davis, J. A.; Entringer, R. C.; Graham, R. L.; and Simmons, G. J.; <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa34/aa3417.pdf">On permutations containing no long arithmetic progressions</a>, Acta Arith. 34 (1977/78), no. 1, 81-90.
%H R. C. Entringer and D. E. Jackson, <a href="http://www.jstor.org/stable/2319140">Problem E2440</a>, Amer. Math. Monthly, 82 (1975), 74-77.
%H P. Erdős and P. Turan, <a href="https://www.renyi.hu/~p_erdos/1936-05.pdf">On some sequences of integers</a>, J. London Math. Soc., 11 (1936), 261-264.
%H Timothy D. LeSaulnier and Sujith Vijay, <a href="http://dx.doi.org/10.1016/j.disc.2010.10.006">On permutations avoiding arithmetic progressions</a>, Discrete Math. 311 (2011), no. 2-3, 205207.
%H A. Sharma, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v16i1r63">Enumerating permutations that avoid 3-free permutations</a>, Electronic Journal of Combinatorics, vol. 16, pp. 1-15, 2009.
%H G. J. Simmons, <a href="/A003407/a003407.pdf">Letters to N. J. A. Sloane, 1974-5</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/NonaveragingSequence.html">Nonaveraging Sequence</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Arithmetic_progression">Arithmetic progression</a>
%H <a href="/index/No#non_averaging">Index entries related to non-averaging sequences</a>
%p b:= proc(s) option remember; local n, r, ok, i, j, k;
%p if nops(s) = 1 then 1
%p else n, r:= max(s), 0;
%p for j in s minus {n} do ok, i, k:= true, j-1, j+1;
%p while ok and i>=0 and k<n do ok, i, k:=
%p not i in s xor k in s, i-1, k+1 od;
%p r:= r+ `if`(ok, b(s minus {j}), 0)
%p od; r
%p fi
%p end:
%p a:= n-> b({$0..n}):
%p seq(a(n), n=0..20); # _Alois P. Heinz_, Nov 30 2017
%t b[s_] := b[s] = Module[{n, r, ok, i, j, k}, If[Length[s] == 1, 1, {n, r} = {Max[s], 0}; Do[{ok, i, k} = {True, j - 1, j + 1}; While[ok && i >= 0 && k < n, {ok, i, k} = {FreeQ[s, i] ~Xor~ MemberQ[s, k], i - 1, k + 1}]; r = r + If[ok, b[s ~Complement~ {j}], 0], {j, s ~Complement~ {n}}]; r]];
%t a[n_] := b[Range[0, n]];
%t Table[a[n], {n, 0, 32}] (* _Jean-François Alcover_, Dec 10 2017,after _Alois P. Heinz_ *)
%Y Column k=0 of A162982.
%Y Row sums of A296529.
%Y Cf. A002620, A011782, A292523.
%K nonn,nice
%O 0,3
%A _N. J. A. Sloane_
%E Sequence extended by _Bill Correll, Jr._ and Randy Ho, Nov 29 2011