A003407 -id:A003407 - cp's OEIS frontend

A292523 Decimal encoding T(n,k) of the k-th non-averaging permutation of [n]; triangle T(n,k), n >= 0, k = 1..A003407(n), read by rows.

0, 1, 12, 21, 132, 213, 231, 312, 1324, 1342, 2143, 2413, 2431, 3124, 3142, 3412, 4213, 4231, 15324, 15342, 21453, 24153, 24315, 24351, 24513, 31254, 31524, 31542, 35124, 35142, 35412, 42153, 42315, 42351, 42513, 45213, 51324, 51342, 153264, 153426, 153462

Offset: 0

Alois P. Heinz, Dec 08 2017

A non-averaging permutation avoids any 3-term arithmetic progression.
The encoding of the empty permutation () is 0. For positive n each element in the permutation is encoded using 1+floor(log_10(n)) = A055642(n) digits with leading 0's if necessary. Then all elements are concatenated.
All terms are in increasing order.

			Triangle T(n,k) begins:
:            0;
:            1;
:           12, 21;
:          132, 213, 231, 312;
:         1324, 1342, 2143, 2413,  2431,    3124,  3142, 3412, 4213, 4231;
:        15324, 15342, 21453, 24153,    ...,    42513, 45213, 51324, 51342;
:       153264, 153426, 153462, 153624, ..., 624153, 624315, 624351, 624513;
:      1532764, 1537264, 1537426,       ...,       7351462, 7351624, 7356124;
:     15327648, 15327684, 15372648,     ...,     84627351, 84672315, 84672351;
:    195327648, 195327684, 195372648,   ...,   915738462, 915783426, 915783462;
:   1090503020710060408,                ...,               10020608090401050703;
:  109050302110710060408,               ...,              1103070910010502060804;
: 10905031107021006041208,              ...,             120408100206110307090105;

Alois P. Heinz, Rows n = 0..14, flattened
Eric Weisstein's World of Mathematics, Nonaveraging Sequence
Wikipedia, Arithmetic progression
Index entries related to non-averaging sequences

Cf. A003407, A030299, A055642, A088370.

T:= proc(n) option remember; local b, l, c; b, l, c:=
      proc(s, p) local ok, i, j, k;
        if nops(s) = 0 then l:= [l[], parse(p)]
      else for j in s 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;
             `if`(ok, b(s minus {j}, cat(p, 0$(c-length(j)), j)), 0)
           od
        fi
      end, [], length(n); b({$1..n}, "0"): sort(l)[]
    end:
seq(T(n), n=0..6);

A178155 Partial sums of A003407 (starting at n=1).

Original entry on oeis.org

1, 3, 7, 17, 37, 85, 189, 471, 967, 2033, 4493, 10621, 23461, 52841, 127745, 340473, 708489, 1367785, 2738841, 5675977, 12313209, 27929825, 66361381, 162909213, 361319381, 780460693, 1722272781, 3904263759, 9528920767, 24294326763, 66213009251, 187941084483, 395937137667, 756194730883, 1395731222259, 2540709556499, 4903320997075, 9814465115099

Offset: 1

Jonathan Vos Post, May 21 2010

nonn

Partial sums of number of permutations with no 3-term arithmetic progression. The subsequence of primes in this partial sum begins with 4 in a row: 3, 7, 17, 37, 967, 4493, 66361381, 780460693, 9814465115099, 1094158908254653, ...

			a(11) = 1 + 2 + 4 + 10 + 20 + 48 + 104 + 282 + 496 + 1066 + 2460 = 4493 is prime.

Cf. A003407.

a(n) = Sum_{i=1..n} A003407(i).

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

Original entry on oeis.org

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

A049773 Triangular array T read by rows: if row n is r(1),...,r(m), then row n+1 is 2r(1)-1,...,2r(m)-1,2r(1),...,2r(m).

Original entry on oeis.org

1, 1, 2, 1, 3, 2, 4, 1, 5, 3, 7, 2, 6, 4, 8, 1, 9, 5, 13, 3, 11, 7, 15, 2, 10, 6, 14, 4, 12, 8, 16, 1, 17, 9, 25, 5, 21, 13, 29, 3, 19, 11, 27, 7, 23, 15, 31, 2, 18, 10, 26, 6, 22, 14, 30, 4, 20, 12, 28, 8, 24, 16, 32, 1, 33, 17, 49, 9, 41, 25, 57, 5, 37, 21, 53, 13, 45, 29, 61, 3, 35, 19

Offset: 1

Clark Kimberling

n-th row = (r(1),r(2),...,r(m)), where m=2^(n-1), satisfies r(r(k))=k for k=1,2,...,m and has exactly 2^[ n/2 ] solutions of r(k)=k. (The function r(k) reverses bits. Or rather, r(k)=revbits(k-1)+1.)
In a knockout competition with m players, arranging the competition brackets (see links) in r(k) order, where k is the rank of the player, ensures that highest ranked players cannot meet until the later stages of the competition.  None of the top 2^p ranked players can meet earlier than the p-th from last round of the competition.  At the same time the top ranked players in each match meet the highest ranked player possible consistent with this rule.  The sequence for the top ranked players meeting the lowest ranked player possible is A131271. - Colin Hall, Jul 31 2011, Feb 29 2012
Row n contains one of A003407(2^(n-1)) non-averaging permutations of [2^(n-1)], i.e., a permutation of [2^(n-1)] without 3-term arithmetic progressions. - Alois P. Heinz, Dec 05 2017

			Triangle begins:
1;
1,  2;
1,  3, 2,  4;
1,  5, 3,  7, 2,  6,  4,  8;
1,  9, 5, 13, 3, 11,  7, 15, 2, 10,  6, 14, 4, 12,  8, 16;
1, 17, 9, 25, 5, 21, 13, 29, 3, 19, 11, 27, 7, 23, 15, 31, 2, 18, 10, 26, ...

Alois P. Heinz, Rows n = 1..13, flattened
Eric Weisstein's World of Mathematics, Nonaveraging Sequence.
Wikipedia, Arithmetic progression.
Wikipedia, Bracket (tournament).
Index entries related to non-averaging sequences.

Sum of odd-indexed terms of n-th row gives A007582. Sum of even-indexed terms gives A049775.
A030109 is another version.
Cf. A131271.
Cf. A088370.
Cf. A003407, A088208.

a049773 n k = a049773_tabf !! (n-1) !! (k-1)
a049773_row n = a049773_tabf !! (n-1)
a049773_tabf = iterate f [1] where
   f vs = (map (subtract 1) ws) ++ ws where ws = map (* 2) vs
-- Reinhard Zumkeller, Mar 14 2015

T:= proc(n) option remember; `if`(n=1, 1,
      [map(x->2*x-1, [T(n-1)])[], map(x->2*x, [T(n-1)])[]][])
    end:
seq(T(n), n=1..7);  # Alois P. Heinz, Oct 28 2011

row[1] = {1}; row[n_] := row[n] = Join[ 2*row[n-1] - 1, 2*row[n-1] ]; Flatten[ Table[ row[n], {n, 1, 7}]] (* Jean-François Alcover, May 03 2012 *)

(a(n, k) = if( k<=0 || k>=n, 0, if( k%2, n\2) + a(n\2, k\2))); {T(n, k) = if( k<=0 || k>2^n/2, 0, 1 + a(2^n/2, k-1))}; /* Michael Somos, Oct 13 1999 */

A088370 Triangle T(n,k), read by rows, where the n-th row is a binary arrangement of the numbers 1 through n.

Original entry on oeis.org

1, 1, 2, 1, 3, 2, 1, 3, 2, 4, 1, 5, 3, 2, 4, 1, 5, 3, 2, 6, 4, 1, 5, 3, 7, 2, 6, 4, 1, 5, 3, 7, 2, 6, 4, 8, 1, 9, 5, 3, 7, 2, 6, 4, 8, 1, 9, 5, 3, 7, 2, 10, 6, 4, 8, 1, 9, 5, 3, 11, 7, 2, 10, 6, 4, 8, 1, 9, 5, 3, 11, 7, 2, 10, 6, 4, 12, 8, 1, 9, 5, 13, 3, 11, 7, 2, 10, 6, 4, 12, 8, 1, 9, 5, 13, 3, 11, 7, 2, 10, 6, 14, 4, 12, 8

Offset: 1

Paul D. Hanna, Sep 28 2003

The n-th row differs from the prior row only by the presence of n. See A088371 for the positions in the n-th row that n is inserted.
From Clark Kimberling, Aug 02 2007: (Start)
At A131966, this sequence is cited as the fractal sequence of the Cantor set C.
Recall that C is the set of fractions in [0,1] whose base 3 representation consists solely of 0's and 2's.
Arrange these fractions as follows:
0
0, .2
0, .02, .2
0, .02, .2, .22
0, .002, .02, .2, .22, etc.
Replace each number x by its order of appearance, counting each distinct predecessor of x only once, getting
1;
1, 2;
1, 3, 2;
1, 3, 2, 4;
1, 5, 3, 2, 4;
Concatenate these to get the current sequence, which is a fractal sequence as defined in "Fractal sequences and interspersions".
One property of such a sequence is that it properly contains itself as a subsequence (infinitely many times). (End)
Row n contains one of A003407(n) non-averaging permutations of [n], i.e., a permutation of [n] without 3-term arithmetic progressions. - Alois P. Heinz, Dec 05 2017

			Row 5 is formed from row 3, {1,3,2} and row 2, {1,2}, like so:
{1,5,3, 2,4} = {1*2-1, 3*2-1, 2*2-1} | {1*2, 2*2}.
Triangle begins:
  1;
  1,  2;
  1,  3, 2;
  1,  3, 2,  4;
  1,  5, 3,  2,  4;
  1,  5, 3,  2,  6,  4;
  1,  5, 3,  7,  2,  6,  4;
  1,  5, 3,  7,  2,  6,  4,  8;
  1,  9, 5,  3,  7,  2,  6,  4,  8;
  1,  9, 5,  3,  7,  2, 10,  6,  4,  8;
  1,  9, 5,  3, 11,  7,  2, 10,  6,  4,  8;
  1,  9, 5,  3, 11,  7,  2, 10,  6,  4, 12,  8;
  1,  9, 5, 13,  3, 11,  7,  2, 10,  6,  4, 12,  8;
  1,  9, 5, 13,  3, 11,  7,  2, 10,  6, 14,  4, 12,  8;
  1,  9, 5, 13,  3, 11,  7, 15,  2, 10,  6, 14,  4, 12,  8;
  1,  9, 5, 13,  3, 11,  7, 15,  2, 10,  6, 14,  4, 12,  8, 16;
  1, 17, 9,  5, 13,  3, 11,  7, 15,  2, 10,  6, 14,  4, 12,  8, 16;
  ...

Clark Kimberling, "Fractal sequences and interspersions," Ars Combinatoria 45 (1997) 157-168.

Alois P. Heinz, Rows n = 1..141, flattened
Eric Weisstein's World of Mathematics, Nonaveraging Sequence
Wikipedia, Arithmetic progression
Index entries related to non-averaging sequences

Cf. A003407, A088371, A309371.

Diagonal gives A053644. Cf. A049773. - Alois P. Heinz, Oct 28 2011

T:= proc(n) option remember;
      `if`(n=1, 1, [map(x-> 2*x-1, [T(n-iquo(n,2))])[],
                    map(x-> 2*x,   [T(  iquo(n,2))])[]][])
    end:
seq(T(n), n=1..20);  # Alois P. Heinz, Oct 28 2011

T[1] = {1}; T[n_] := T[n] = Join[q = Quotient[n, 2]; 2*T[n-q]-1, 2*T[q]]; Table[ T[n], {n, 1, 20}] // Flatten (* Jean-François Alcover, Feb 26 2015, after Alois P. Heinz *)

{T(n,k) = if(k==0, 1, if(k<=n\2, 2*T(n\2,k) - 1, 2*T((n-1)\2,k-1-n\2) ))}
for(n=0,20,for(k=0,n,print1(T(n,k),", "));print(""))

T(n,n) = 2^(floor(log(n)/log(2))). Construction. The 2n-th row is the concatenation of row n, after multiplying each term by 2 and subtracting 1, with row n, after multiplying each term by 2. The (2n-1)-th row is the concatenation of row n, after multiplying each term by 2 and subtracting 1, with row n-1, after multiplying each term by 2.

Sum_{k=1..n} k * A088370(n,k) = A309371(n). - Alois P. Heinz, Jul 26 2019

A238569 Number of compositions of n avoiding any 3-term arithmetic progression.

Original entry on oeis.org

1, 1, 2, 3, 7, 11, 19, 28, 53, 83, 140, 201, 332, 486, 775, 1207, 1716, 2498, 3870, 5623, 8020, 11276, 17168, 23323, 34746, 46141, 64879, 90467, 127971, 176201, 242869, 333508, 456683, 606403, 844818, 1125922, 1496466, 2005446, 2737912, 3543506, 4824442

Offset: 0

Joerg Arndt and Alois P. Heinz, Feb 28 2014

nonn

			a(3) = 3: [1,2], [2,1], [3].
a(4) = 7: [1,1,2], [1,2,1], [1,3], [2,1,1], [2,2], [3,1], [4].
a(5) = 11: [1,1,3], [1,2,2], [1,3,1], [1,4], [2,1,2], [2,2,1], [2,3], [3,1,1], [3,2], [4,1], [5].
a(6) = 19: [1,1,2,2], [1,1,4], [1,2,1,2], [1,2,2,1], [1,3,2], [1,4,1], [1,5], [2,1,1,2], [2,1,2,1], [2,1,3], [2,2,1,1], [2,3,1], [2,4], [3,1,2], [3,3], [4,1,1], [4,2], [5,1], [6].

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..85
Index entries related to non-averaging sequences

Cf. A003407 (the same for permutations).
Cf. A178932 (the same for strict partitions).
Cf. A238423 (the same for consecutive 3-term arithmetic progressions).
Cf. A238571 (the same for partitions).
Cf. A238686.

b:= proc(n, i, o) option remember; `if`(n=0, 1, add(
      `if`(j in o, 0, b(n-j, i union {j}, select(y->02*j-x, i)))), j=1..n))
    end:
a:= n-> b(n, {}, {}):
seq(a(n), n=0..30);

b[n_, i_List, o_List] := b[n, i, o] = If[n == 0, 1, Sum[If[MemberQ[o, j], 0, b[n - j, i  ~Union~ {j}, Select[o ~Union~ (2j-i), 0<# && # <= n &]]], {j, 1, n}]]; a[n_] := b[n, {}, {}]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 06 2015, translated from Maple *)

A238571 Number of partitions of n avoiding any 3-term arithmetic progression.

Original entry on oeis.org

1, 1, 2, 2, 4, 5, 6, 8, 12, 12, 19, 23, 27, 34, 43, 49, 62, 74, 88, 104, 127, 145, 176, 199, 239, 272, 324, 378, 430, 490, 583, 654, 750, 876, 988, 1112, 1291, 1441, 1642, 1877, 2121, 2358, 2682, 2977, 3365, 3830, 4237, 4734, 5357, 5868, 6590, 7398, 8182, 9049

Offset: 0

Joerg Arndt and Alois P. Heinz, Feb 28 2014

nonn

			a(3) = 2: [2,1], [3].
a(4) = 4: [2,1,1], [2,2], [3,1], [4].
a(5) = 5: [2,2,1], [3,1,1], [3,2], [4,1], [5].
a(6) = 6: [2,2,1,1], [3,3], [4,1,1], [4,2], [5,1], [6].
a(7) = 8: [3,2,2], [3,3,1], [4,2,1], [4,3], [5,1,1], [5,2], [6,1], [7].
a(8) = 12: [3,3,1,1], [3,3,2], [4,2,1,1], [4,2,2], [4,3,1], [4,4], [5,2,1], [5,3], [6,1,1], [6,2], [7,1], [8].

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..300
Index entries related to non-averaging sequences

Cf. A003407 (the same for permutations).
Cf. A178932 (the same for strict partitions).
Cf. A238569 (the same for compositions).
Cf. A238433 (partitions avoiding equidistant 3-term arithmetic progressions).
Cf. A238424 (partitions avoiding three consecutive parts in arithmetic progression).
Cf. A238687.

a[n_] := a[n] = Count[IntegerPartitions[n], P_ /; {} == SequencePosition[P, {_, i_, _, j_, _, k_, _} /; j - i == k - j, 1]];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 50}] (* Jean-François Alcover, Oct 29 2021 *)

A296529 Number T(n,k) of non-averaging permutations of [n] with first element k; triangle T(n,k), n >= 0, k = 0..n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 2, 3, 3, 2, 0, 2, 5, 6, 5, 2, 0, 5, 6, 13, 13, 6, 5, 0, 10, 10, 16, 32, 16, 10, 10, 0, 28, 26, 36, 51, 51, 36, 26, 28, 0, 24, 50, 62, 74, 76, 74, 62, 50, 24, 0, 50, 50, 134, 138, 161, 161, 138, 134, 50, 50, 0, 124, 120, 146, 302, 345, 386, 345, 302, 146, 120, 124

Offset: 0

Alois P. Heinz, Dec 14 2017

A non-averaging permutation avoids any 3-term arithmetic progression.

T(0,0) = 1 by convention.

			T(5,1) = 2: 15324, 15342.
T(5,2) = 5: 21453, 24153, 24315, 24351, 24513.
T(5,3) = 6: 31254, 31524, 31542, 35124, 35142, 35412.
T(5,4) = 5: 42153, 42315, 42351, 42513, 45213.
T(5,5) = 2: 51324, 51342.
Triangle T(n,k) begins:
  1;
  0,  1;
  0,  1,  1;
  0,  1,  2,   1;
  0,  2,  3,   3,   2;
  0,  2,  5,   6,   5,   2;
  0,  5,  6,  13,  13,   6,   5;
  0, 10, 10,  16,  32,  16,  10,  10;
  0, 28, 26,  36,  51,  51,  36,  26,  28;
  0, 24, 50,  62,  74,  76,  74,  62,  50, 24;
  0, 50, 50, 134, 138, 161, 161, 138, 134, 50, 50;
  ...

Alois P. Heinz, Rows n = 0..99, flattened
Eric Weisstein's World of Mathematics, Nonaveraging Sequence
Wikipedia, Arithmetic progression
Index entries related to non-averaging sequences

Columns k=0-1 give: A000007, A296530 (for n>0).
Row sums give A003407.
T(n,n) gives A296530.
T(n,ceiling(n/2)) gives A296531.
Cf. A292523.

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 `if`(k=0, 0^n, b({$0..n} minus {k-1})):
seq(seq(T(n, k), k=0..n), n=0..14);

b[s_List] := b[s] = Module[{n = Max[s], r = 0, ok, i, j, k}, If[Length[s] == 1, 1, 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]];
T[0, 0]=1; T[n_, k_] := If[k==0, 0^n, b[Range[0, n] ~Complement~ {k-1}]];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 14}] // Flatten (* Jean-François Alcover, Dec 18 2017, after Alois P. Heinz *)

T(n,k) = T(n,n+1-k) > 0 for k=1..n.

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

A174085 Number of permutations of length n with no consecutive triples i,...i+r,...i+2r for all positive and negative r, and for all equal spacings d.

Original entry on oeis.org

1, 1, 2, 4, 18, 72, 396, 2328, 17050, 131764, 1199368, 11379524, 123012492, 1386127700, 17450444866, 227152227940

Offset: 0

Isaac Lambert, Apr 20 2010

Here we count both the sequence 1,2,3 (r=1) as a progression in 1,2,3,0,4,5, (note d=1) and in 1,0,2,4,3,5 (here, d=2).

Number of permutations of 1..n with no 2-dimensional arithmetic progression of length 3: that is, no three points (i,p(i)), (j,p(j)) and (k,p(k)) such that j-i = k-j and p(j)-p(i) = p(k)-p(j). - David Bevan, Jun 16 2021

			a(3) = 4; 123 and 321 each contain a 3-term arithmetic progression.
Since the only possibilities for progressions for n=4 are d=1 and r=1 and -1, we get the same term as A095816(4).

Cf. A095816, A174084, A174086, A174087.
Cf. A179040 (number of permutations of 1..n with no three elements collinear).
Cf. A003407 for another interpretation of avoiding 3-term APs.

a(n) >= A003407(n) with equality only for n in {0, 1, 2, 3}.

a(0)-a(3) and a(10)-a(13) from David Bevan, Jun 16 2021

a(14)-a(15) from Bert Dobbelaere, May 18 2025

cp's OEIS Frontend

A292523 Decimal encoding T(n,k) of the k-th non-averaging permutation of [n]; triangle T(n,k), n >= 0, k = 1..A003407(n), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A178155 Partial sums of A003407 (starting at n=1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A049773 Triangular array T read by rows: if row n is r(1),...,r(m), then row n+1 is 2r(1)-1,...,2r(m)-1,2r(1),...,2r(m).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

A088370 Triangle T(n,k), read by rows, where the n-th row is a binary arrangement of the numbers 1 through n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A238569 Number of compositions of n avoiding any 3-term arithmetic progression.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A238571 Number of partitions of n avoiding any 3-term arithmetic progression.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A296529 Number T(n,k) of non-averaging permutations of [n] with first element k; triangle T(n,k), n >= 0, k = 0..n, read by rows.

Views

Author