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,2

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

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)

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 *)

Prog

(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

Crossrefs

Cf. A296468, A296996, A296998.

Sequence in context: A201984 A210519 A279437 * A220240 A246606 A210903

Adjacent sequences: A296994 A296995 A296996 * A296998 A296999 A297000

Keyword

nonn,easy

Author

Heinrich Ludwig, Dec 23 2017

Status

approved