A295390 -id:A295390 - cp's OEIS frontend

A295370 Number of permutations of [n] avoiding three consecutive terms in arithmetic progression.

1, 1, 2, 4, 18, 80, 482, 3280, 26244, 231148, 2320130, 25238348, 302834694, 3909539452, 54761642704, 816758411516, 13076340876500, 221396129723368, 3985720881222850, 75503196628737920, 1510373288335622576, 31634502738658957588, 696162960370556156224, 15978760340940405262668

Offset: 0

Alois P. Heinz, Nov 20 2017

nonn

These are permutations of n whose second-differences are nonzero. - Gus Wiseman, Jun 03 2019

			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.

Wikipedia, Arithmetic progression
Index entries related to non-averaging sequences

Column k=0 of A295390.
Cf. A003407, A174080, A238423, A238424, A338765.
Cf. A049988, A175342, A279945, A325545, A325849, A325850, A325851, A325874, A325875.

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

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];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 16}] (* Jean-François Alcover, Nov 20 2023, after Alois P. Heinz *)

a(22)-a(23) from Vaclav Kotesovec, Mar 22 2022

A162982 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k 3-term arithmetic progressions (n>=0; 0<=k<=floor((n-1)^2/4)).

Original entry on oeis.org

1, 1, 2, 4, 2, 10, 12, 2, 20, 48, 46, 4, 2, 48, 156, 318, 152, 40, 4, 2, 104, 460, 1112, 1690, 1152, 406, 92, 18, 4, 2, 282, 1248, 4058, 8784, 11648, 8856, 3906, 1188, 244, 80, 20, 4, 2, 496, 2924, 11360, 31776, 64020, 86676, 80700, 52800, 22212, 6948, 2158, 516, 214, 52, 22, 4, 2

Offset: 0

Emeric Deutsch, Aug 31 2009

Row n contains 1+floor((n-1)^2/4) entries.
Sum of entries in row n = n! = A000142(n).
T(n,0) = A003407(n).
The terms of the sequence have been determined by direct counting (using Maple).
The Maple program yields the generating polynomial of the specified row n.

			T(5,3) = 4 because we have 12354 (containing 123, 234, 135), 21345 (containing 234, 345, and 135), and their reversals 45321 and 54312.
Triangle starts:
   1;
   1;
   2;
   4,   2;
  10,  12,   2;
  20,  48,  46,   4,  2;
  48, 156, 318, 152, 40, 4, 2;
  ...

Alois P. Heinz, Rows n = 0..20, flattened

Cf. A000142, A003407, A295390.

n := 7: with(combinat): P := permute(n): st := proc (p) local ct, i, j, k: ct := 0: for i to nops(p)-2 do for j from i+1 to nops(p)-1 do for k from j+1 to nops(p) do if p[i]+p[k] = 2*p[j] then ct := ct+1 else end if end do end do end do; ct end proc: sort(add(t^st(P[i]), i = 1 .. factorial(n))); # yields the generating polynomial of row n

row[n_] := CoefficientList[P = Permutations[Range[n]]; st[p_List] := Module[{ct = 0, i, j, k}, For[i = 1, i <= Length[p]-2, i++, For[j = i+1, j <= Length[p]-1, j++, For[k = j+1, k <= Length[p], k++, If[p[[i]] + p[[k]] == 2*p[[j]], ct = ct+1]]]]; ct]; Sum[t^st[P[[i]]], {i, 1, n!}], t];
Table[ro = row[n]; Print[ro]; ro, {n, 0, 9}] // Flatten (* Jean-François Alcover, Sep 08 2017, adapted from Maple *)

cp's OEIS Frontend

A295370 Number of permutations of [n] avoiding three consecutive terms in arithmetic progression.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions