A296996 Number of nonequivalent (mod D_8) 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, 1, 14, 75, 310, 911, 2373, 5254, 10824, 20305, 36300, 61081, 99294, 154735, 234955, 345836, 498848, 702609, 973674, 1324135, 1776950, 2348511, 3069649, 3961970, 5065800, 6408961, 8043048, 10003189, 12354174, 15139615, 18439575, 22307416, 26840704, 32103905, 38214470

Offset: 1

Author

Heinrich Ludwig, Jan 12 2018

Keywords

• nonn
• easy

Comments

Rotations and reflections of placements are not counted. If they are to be counted see A296997.

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

Links

• Heinrich Ludwig, Table of n, a(n) for n = 1..1000
• Index entries for linear recurrences with constant coefficients, signature (3,1,-11,6,14,-14,-6,11,-1,-3,1).

Crossrefs

Cf. A296997.

Programs

Mathematica

Array[(#^6 - 3 #^4 + 5 #^3 - 4 #^2 + 4 #)/48 + Boole[OddQ@ #] (8 #^3 - 18 #^2 + 7 #)/48 &, 35] (* or *)
Rest@ CoefficientList[Series[x^2*(1 + 11 x + 32 x^2 + 82 x^3 + 54 x^4 + 57 x^5 + 2 x^6 + 2 x^7 - x^8)/((1 - x)^7*(1 + x)^4), {x, 0, 35}], x] (* Michael De Vlieger, Jan 12 2018 *)

PARI

concat(0, Vec(x^2*(1 + 11*x + 32*x^2 + 82*x^3 + 54*x^4 + 57*x^5 + 2*x^6 + 2*x^7 - x^8) / ((1 - x)^7*(1 + x)^4) + O(x^40))) \\ Colin Barker, Jan 12 2018

Formula

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

From Colin Barker, Jan 12 2018: (Start)

G.f.: x^2*(1 + 11*x + 32*x^2 + 82*x^3 + 54*x^4 + 57*x^5 + 2*x^6 + 2*x^7 - x^8) / ((1 - x)^7*(1 + x)^4).

a(n) = (n^6 - 3*n^4 + 5*n^3 - 4*n^2 + 4*n) / 48 for n even.

a(n) = (n^6 - 3*n^4 + 13*n^3 - 22*n^2 + 11*n) / 48 for n odd.

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

(End)