A296997 Number of ways to place 3 points on an n X n point grid so that no point is equally distant from two other points on the same row or the same column.

0, 4, 78, 544, 2260, 7068, 18298, 41472, 85032, 161300, 287430, 486624, 789308, 1234604, 1871730, 2761728, 3979088, 5613732, 7772862, 10583200, 14193060, 18774844, 24527338, 31678464, 40487800, 51249588, 64295478, 79997792, 98772492, 121082700, 147441890, 178417664

Offset: 1

Author

Heinrich Ludwig, Dec 23 2017

Keywords

• nonn
• easy

Comments

Rotations and reflections of a placement are counted. If they are to be ignored, see A296996.

The condition of placements is also known as "no 3-term arithmetic progressions".

Links

• Heinrich Ludwig, Table of n, a(n) for n = 1..256
• Index entries for linear recurrences with constant coefficients, signature (5,-8,0,14,-14,0,8,-5,1).

Crossrefs

Cf. A296468, A296996, A296998.

Programs

Mathematica

Array[(#^6 - 3 #^4 - 3 #^3 + 8 #^2)/6 - # Boole[OddQ@ #]/2 &, 32] (* Michael De Vlieger, Dec 23 2017 *)
CoefficientList[ Series[-2x (2 + 29x + 93x^2 + 82x^3 + 32x^4 + x^5 + x^6)/((x - 1)^7 (x + 1)^2), {x, 0, 31}], x] (* or *)
LinearRecurrence[{5, -8, 0, 14, -14, 0, 8, -5, 1}, {0, 4, 78, 544, 2260, 7068, 18298, 41472, 85032}, 32] (* Robert G. Wilson v, Jan 15 2018 *)

PARI

concat(0, Vec(2*x^2*(2 + 29*x + 93*x^2 + 82*x^3 + 32*x^4 + x^5 + x^6) / ((1 - x)^7*(1 + x)^2) + O(x^40))) \\ Colin Barker, Dec 23 2017

Formula

a(n) = (n^6 - 3*n^4 - 3*n^3 + 8*n^2)/6 - (n == 1 (mod 2))*n/2.

a(n) = (n^6 - 3*n^4 - 3*n^3 + 8*n^2)/6 for n even,

a(n) = (n^6 - 3*n^4 - 3*n^3 + 8*n^2 - 3*n)/6 for n odd.

From Colin Barker, Dec 23 2017: (Start)

G.f.: 2*x^2*(2 + 29*x + 93*x^2 + 82*x^3 + 32*x^4 + x^5 + x^6) / ((1 - x)^7*(1 + x)^2).

a(n) = 5*a(n-1) - 8*a(n-2) + 14*a(n-4) - 14*a(n-5) + 8*a(n-7) - 5*a(n-8) + a(n-9) for n>9.

(End)