A279448 Number of nonequivalent ways to place 4 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, 17, 202, 1397, 6582, 24185, 73496, 195086, 463875, 1013505, 2061426, 3956947, 7222992, 12640817, 21312992, 34801420, 55215621, 85424721, 129174250, 191397185, 278361226, 398108777, 560635032, 778491962, 1066995527, 1445034305, 1935301746, 2565356031, 3367870500

Offset: 1

Author

Heinrich Ludwig, Dec 18 2016

Keywords

• nonn
• easy

Comments

Column 5 of A279453.

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

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

Links

• Heinrich Ludwig, Table of n, a(n) for n = 1..1000
• Index entries for linear recurrences with constant coefficients, signature (4,-1,-16,19,20,-45,0,45,-20,-19,16,1,-4,1).

Crossrefs

Cf. A235455, A279438, A279452, A279453, A279454.

Same problem but 2,3,5,6,7 points: A014409, A279447, A279449, A279450, A279451.

Programs

PARI

concat(0, Vec(x^2*(1 +13*x +135*x^2 +622*x^3 +1449*x^4 +2143*x^5 +1557*x^6 +781*x^7 +34*x^8 -8*x^9 -8*x^10 +x^11) / ((1 -x)^9*(1 +x)^5) + O(x^40))) \\ Colin Barker, Dec 18 2016

Formula

a(n) = (n^8 - 14*n^6 + 30*n^5 + 12*n^4 - 60*n^3 + 40*n^2)/192 + IF(MOD(n, 2) = 1, 4*n^4 - 20*n^3 + 22*n^2 - 2*n - 7)/64.

a(n) = 4*a(n-1) - a(n-2) - 16*a(n-3) + 19*a(n-4) + 20*a(n-5) - 45*a(n-6) + 45*a(n-8) - 20*a(n-9) - 19*a(n-10) + 16*a(n-11) + a(n-12) - 4*a(n-13) + a(n-14).

G.f.: x^2*(1 +13*x +135*x^2 +622*x^3 +1449*x^4 +2143*x^5 +1557*x^6 +781*x^7 +34*x^8 -8*x^9 -8*x^10 +x^11) / ((1 -x)^9*(1 +x)^5). - Colin Barker, Dec 18 2016