A296529 -id:A296529 - cp's OEIS frontend

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

N. J. A. Sloane

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

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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

Column k=0 of A162982.
Row sums of A296529.
Cf. A002620, A011782, A292523.

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

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

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

A296530 Number of non-averaging permutations of [n] with first element n.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 5, 10, 28, 24, 50, 124, 283, 528, 1266, 3715, 10702, 8740, 15414, 31988, 68465, 160964, 380124, 890738, 2230219, 3990852, 8354276, 20281732, 46056920, 131289988, 349369117, 1054037937, 3081527146, 2440225484, 4201202020, 7475926894, 13276918426

Offset: 0

Alois P. Heinz, Dec 14 2017

nonn

A non-averaging permutation avoids any 3-term arithmetic progression.

a(0) = 1 by convention.

			a(4) = 2: 4213, 4231.
a(5) = 2: 51324, 51342.
a(6) = 5: 621453, 624153, 624315, 624351, 624513.
a(7) = 10: 7312564, 7315264, 7315426, 7315462, 7315624, 7351264, 7351426, 7351462, 7351624, 7356124.

Alois P. Heinz, Table of n, a(n) for n = 0..99
Eric Weisstein's World of Mathematics, Nonaveraging Sequence
Wikipedia, Arithmetic progression
Index entries related to non-averaging sequences

Main diagonal of A296529.

Cf. A003407, A292523.

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} minus {n-1}):
seq(a(n), n=0..30);

b[s_] := b[s] = Module[{n = Max[s], r = 0, ok, i, j, k}, If[Length[s] == 1, 1, 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[Complement[Range[0, n], {n - 1}]]
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jun 02 2018, from Maple *)

a(n) = A296529(n,n).

A296531 Number of non-averaging permutations of [n] with first element ceiling(n/2).

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 13, 32, 51, 76, 161, 386, 903, 2280, 5018, 12828, 19720, 27656, 48788, 100120, 220686, 537208, 1258242, 3123166, 7056165, 17189752, 35968308, 82137764, 189847917, 509880208, 1322092262, 3807727932, 5678509066, 7721623440, 13293899416, 23650787296

Offset: 0

Alois P. Heinz, Dec 14 2017

nonn

A non-averaging permutation avoids any 3-term arithmetic progression.

a(0) = 1 by convention.

			a(5) = 6: 31254, 31524, 31542, 35124, 35142, 35412.
a(6) = 13: 312564, 315264, 315426, 315462, 315624, 351264, 351426, 351462, 351624, 354126, 354162, 354612, 356124.

Alois P. Heinz, Table of n, a(n) for n = 0..99
Eric Weisstein's World of Mathematics, Nonaveraging Sequence
Wikipedia, Arithmetic progression
Index entries related to non-averaging sequences

Cf. A003407, A292523, A296529.

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} minus {ceil(n/2)-1}):
seq(a(n), n=0..25);

b[s_] := b[s] = Module[{n = Max[s], r = 0, ok, i, j, k}, If[Length[s] == 1, 1, 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[Complement[Range[0, n], {Ceiling[n/2] - 1}]];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Jun 02 2018, from Maple *)

a(n) = A296529(n,ceiling(n/2)).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A296530 Number of non-averaging permutations of [n] with first element n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A296531 Number of non-averaging permutations of [n] with first element ceiling(n/2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula