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

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

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

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

Prog

(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
(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

Crossrefs

Cf. A235454, A279437, A279452, A279453, A279454.

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

Sequence in context: A372662 A205328 A328735 * A205590 A369244 A213284

Adjacent sequences: A279444 A279445 A279446 * A279448 A279449 A279450

Keyword

nonn,easy

Author

Heinrich Ludwig, Dec 17 2016

Status

approved