|
%I #31 Nov 20 2023 11:14:15
%S 1,1,2,4,18,80,482,3280,26244,231148,2320130,25238348,302834694,
%T 3909539452,54761642704,816758411516,13076340876500,221396129723368,
%U 3985720881222850,75503196628737920,1510373288335622576,31634502738658957588,696162960370556156224,15978760340940405262668
%N Number of permutations of [n] avoiding three consecutive terms in arithmetic progression.
%C These are permutations of n whose second-differences are nonzero. - _Gus Wiseman_, Jun 03 2019
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Arithmetic_progression">Arithmetic progression</a>
%H <a href="/index/No#non_averaging">Index entries related to non-averaging sequences</a>
%e a(3) = 4: 132, 213, 231, 312.
%e a(4) = 18: 1243, 1324, 1342, 1423, 2134, 2143, 2314, 2413, 2431, 3124, 3142, 3241, 3412, 3421, 4132, 4213, 4231, 4312.
%p b:= proc(s, j, k) option remember; `if`(s={}, 1,
%p add(`if`(k=0 or 2*j<>i+k, b(s minus {i}, i,
%p `if`(2*i-j in s, j, 0)), 0), i=s))
%p end:
%p a:= n-> b({$1..n}, 0$2):
%p seq(a(n), n=0..12);
%t Table[Length[Select[Permutations[Range[n]],!MemberQ[Differences[#,2],0]&]],{n,0,5}] (* _Gus Wiseman_, Jun 03 2019 *)
%t 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}]];
%t a[n_] := a[n] = b[Range[n], 0, 0];
%t Table[Print[n, " ", a[n]]; a[n], {n, 0, 16}] (* _Jean-François Alcover_, Nov 20 2023, after _Alois P. Heinz_ *)
%Y Column k=0 of A295390.
%Y Cf. A003407, A174080, A238423, A238424, A338765.
%Y Cf. A049988, A175342, A279945, A325545, A325849, A325850, A325851, A325874, A325875.
%K nonn
%O 0,3
%A _Alois P. Heinz_, Nov 20 2017
%E a(22)-a(23) from _Vaclav Kotesovec_, Mar 22 2022
|
