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.

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

Links

Table of n, a(n) for n=0..13.

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. 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.

Sequence in context: A007727 A303352 A226011 * A325850 A052689 A139104

Adjacent sequences: A174082 A174083 A174084 * A174086 A174087 A174088

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