|
| |
|
|
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
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: A307768 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
|
| |
|
|
