The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A003407 Number of permutations of [n] with no 3-term arithmetic progression. (Formerly M1201) 13
 1, 1, 2, 4, 10, 20, 48, 104, 282, 496, 1066, 2460, 6128, 12840, 29380, 74904, 212728, 368016, 659296, 1371056, 2937136, 6637232, 15616616, 38431556, 96547832, 198410168, 419141312, 941812088, 2181990978, 5624657008, 14765405996, 41918682488, 121728075232 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS 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 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 REFERENCES N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). LINKS Alois P. Heinz, Table of n, a(n) for n = 0..200 (terms up to n=90 from Bill Correll, Jr. and Randy W. Ho) B. Correll, Jr., The Density of Costas Arrays And Three-Free Permutations, Proceedings of IEEE Statistical Signal Processing Conference, 2012, 492-495. Bill Correll, Jr. and Randy W. Ho, A note on 3-free permutations, INTEGERS, A17 (2017), #A55. Bill Correll, Jr. and Randy W. Ho, A note on 3-free permutations, arXiv:1712.00105 [math.CO], 2017. Davis, J. A.; Entringer, R. C.; Graham, R. L.; and Simmons, G. J.; On permutations containing no long arithmetic progressions, Acta Arith. 34 (1977/78), no. 1, 81-90. R. C. Entringer and D. E. Lackson, Problem E2440, Amer. Math. Monthly, 82 (1975), 74-77. P. Erdős and P. Turan, On some sequences of integers, J. London Math. Soc., 11 (1936), 261-264. Timothy D. LeSaulnier and Sujith Vijay, On permutations avoiding arithmetic progressions, Discrete Math. 311 (2011), no. 2-3, 205207. A. Sharma, Enumerating permutations that avoid 3-free permutations, Electronic Journal of Combinatorics, vol. 16, pp. 1-15, 2009. G. J. Simmons, Letters to N. J. A. Sloane, 1974-5 Eric Weisstein's World of Mathematics, Nonaveraging Sequence Wikipedia, Arithmetic progression MAPLE b:= proc(s) option remember; local n, r, ok, i, j, k;       if nops(s) = 1 then 1     else n, r:= max(s), 0;          for j in s minus {n} do ok, i, k:= true, j-1, j+1;            while ok and i>=0 and k b({\$0..n}): seq(a(n), n=0..20);  # Alois P. Heinz, Nov 30 2017 MATHEMATICA 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]]; a[n_] := b[Range[0, n]]; Table[a[n], {n, 0, 32}] (* Jean-François Alcover, Dec 10 2017, after Alois P. Heinz *) CROSSREFS Column k=0 of A162982. Row sums of A296529. Cf. A002620, A011782, A292523. Sequence in context: A307768 A297183 A232466 * A151523 A317708 A265264 Adjacent sequences:  A003404 A003405 A003406 * A003408 A003409 A003410 KEYWORD nonn,nice AUTHOR EXTENSIONS Sequence extended by Bill Correll, Jr. and Randy Ho, Nov 29 2011 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 26 22:58 EDT 2020. Contains 334634 sequences. (Running on oeis4.)