login
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
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 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
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 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).
CROSSREFS
Cf. A179040 (number of permutations of 1..n with no three elements collinear).
Cf. A003407 for another interpretation of avoiding 3-term APs.
Sequence in context: A007727 A303352 A226011 * A325850 A052689 A139104
KEYWORD
nonn,more
AUTHOR
Isaac Lambert, Apr 20 2010
EXTENSIONS
a(0)-a(3) and a(10)-a(13) from David Bevan, Jun 16 2021
STATUS
approved