A003407 Number of permutations of [n] with no 3-term arithmetic progression. (Formerly M1201)

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

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. Jackson, 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

Index entries related to non-averaging sequences

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<n do ok, i, k:=
             not i in s xor k in s, i-1, k+1 od;
           r:= r+ `if`(ok, b(s minus {j}), 0)
         od; r
      fi
    end:
a:= n-> 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: A370583 A297183 A232466 * A151523 A317708 A265264

Adjacent sequences: A003404 A003405 A003406 * A003408 A003409 A003410

Keyword

nonn,nice

Author

N. J. A. Sloane

Extensions

Sequence extended by Bill Correll, Jr. and Randy Ho, Nov 29 2011

Status

approved