

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.


3



1, 1, 2, 4, 18, 72, 396, 2328, 17050, 131764, 1199368, 11379524, 123012492, 1386127700
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

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 2dimensional arithmetic progression of length 3: that is, no three points (i,p(i)), (j,p(j)) and (k,p(k)) such that ji = kj and p(j)p(i) = p(k)p(j).  David Bevan, Jun 16 2021


LINKS



FORMULA

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


EXAMPLE

a(3) = 4; 123 and 321 each contain a 3term 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).


CROSSREFS

Cf. A179040 (number of permutations of 1..n with no three elements collinear).
Cf. A003407 for another interpretation of avoiding 3term APs.


KEYWORD

nonn,more


AUTHOR



EXTENSIONS

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


STATUS

approved



