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
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
KEYWORD
nonn,nice
AUTHOR
EXTENSIONS
Sequence extended by Bill Correll, Jr. and Randy Ho, Nov 29 2011
STATUS
approved