A003407 Number of permutations of [n] with no 3-term arithmetic progression.

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

Author

N. J. A. Sloane

Keywords

• nonn
• nice

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

Crossrefs

Column k=0 of A162982.

Row sums of A296529.

Cf. A002620, A011782, A292523.

Programs

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 *)

Extensions

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