|
|
A295370
|
|
Number of permutations of [n] avoiding three consecutive terms in arithmetic progression.
|
|
16
|
|
|
1, 1, 2, 4, 18, 80, 482, 3280, 26244, 231148, 2320130, 25238348, 302834694, 3909539452, 54761642704, 816758411516, 13076340876500, 221396129723368, 3985720881222850, 75503196628737920, 1510373288335622576, 31634502738658957588, 696162960370556156224, 15978760340940405262668
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
These are permutations of n whose second-differences are nonzero. - Gus Wiseman, Jun 03 2019
|
|
LINKS
|
|
|
EXAMPLE
|
a(3) = 4: 132, 213, 231, 312.
a(4) = 18: 1243, 1324, 1342, 1423, 2134, 2143, 2314, 2413, 2431, 3124, 3142, 3241, 3412, 3421, 4132, 4213, 4231, 4312.
|
|
MAPLE
|
b:= proc(s, j, k) option remember; `if`(s={}, 1,
add(`if`(k=0 or 2*j<>i+k, b(s minus {i}, i,
`if`(2*i-j in s, j, 0)), 0), i=s))
end:
a:= n-> b({$1..n}, 0$2):
seq(a(n), n=0..12);
|
|
MATHEMATICA
|
Table[Length[Select[Permutations[Range[n]], !MemberQ[Differences[#, 2], 0]&]], {n, 0, 5}] (* Gus Wiseman, Jun 03 2019 *)
b[s_, j_, k_] := b[s, j, k] = If[s == {}, 1, Sum[If[k == 0 || 2*j != i + k, b[s~Complement~{i}, i, If[MemberQ[s, 2*i - j ], j, 0]], 0], {i, s}]];
a[n_] := a[n] = b[Range[n], 0, 0];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|