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, 17450444866, 227152227940

Offset: 0

Author

Isaac Lambert, Apr 20 2010

Keywords

• nonn
• more

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

Examples

			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.

Formula

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

Extensions

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