A279447 Number of nonequivalent ways to place 3 points on an n X n square grid so that no more than 2 points are on a vertical or horizontal straight line.

0, 1, 14, 73, 301, 890, 2321, 5166, 10654, 20055, 35880, 60511, 98419, 153608, 233331, 343820, 496076, 699261, 969234, 1318885, 1770185, 2340646, 3059749, 3950618, 5051786, 6393075, 8023756, 9981531, 12328239, 15110740, 18405415, 22269656, 26796504, 32055353, 38158166

Offset: 1

Author

Heinrich Ludwig, Dec 17 2016

Keywords

• nonn
• easy

Comments

Column 4 of A279453.

Rotations and reflections of placements are not counted. For numbers if they are to be counted see A279437.

For condition "no more than 2 points on straight lines at any angle", see A235454.

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. A235454, A279437, A279452, A279453, A279454.

Same problem but 2, 4..7 points: A014409, A279448, A279449, A279450, A279451.

Programs

Magma

I:=[0,1,14,73,301,890,2321,5166,10654,20055,35880]; [n le 11 select I[n] else 3*Self(n-1)+Self(n-2)-11*Self(n-3)+ 6*Self(n-4)+14*Self(n-5)-14*Self(n-6)-6*Self(n-7)+11*Self(n-8)-Self(n-9)-3*Self(n-10)+Self(n-11): n in [1..40]]; // Vincenzo Librandi, Dec 17 2016

Mathematica

LinearRecurrence[{3, 1, -11, 6, 14, -14, -6, 11, -1, -3, 1},{0, 1, 14, 73, 301, 890, 2321, 5166, 10654, 20055, 35880}, 35] (* Vincenzo Librandi Dec 17 2016 *)

PARI

concat(0, Vec(x^2*(1 + 11*x + 30*x^2 + 79*x^3 + 62*x^4 + 55*x^5 + 4*x^6 - x^7 - x^8) / ((1 - x)^7*(1 + x)^4) + O(x^30))) \\ Colin Barker, Dec 17 2016

Formula

a(n) = (n^6 - 5*n^4 + 14*n^3 - 14*n^2 + 4*n)/48 + IF(MOD(n, 2) = 1, 2*n^3 - 3*n^2 + 1)/16.

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

G.f.: x^2*(1 + 11*x + 30*x^2 + 79*x^3 + 62*x^4 + 55*x^5 + 4*x^6 - x^7 - x^8) / ((1 - x)^7*(1 + x)^4). - Colin Barker, Dec 17 2016