A296999 Number of nonequivalent (mod D_8) ways to place 4 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, 17, 226, 1550, 7221, 26120, 78484, 206242, 486640, 1056377, 2137506, 4085167, 7430276, 12964014, 21801632, 35520743, 56249658, 86880957, 131186720, 194133425, 282024809, 402949496, 566950056, 786640454, 1077397347, 1458190435, 1951789266, 2585856152, 3393157995

Offset: 1

Author

Heinrich Ludwig, Jan 21 2018

Keywords

• nonn
• easy

Comments

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

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,-4,4,-4,5,1,-5,6,-10,8,-8,10,-6,5,-1,-5,4,-4,4,1,-3,1).

Crossrefs

Cf. A014409, A296996, A296998.

Programs

Mathematica

Array[(#^8 - 6 #^6 - 12 #^5 + 64 #^4 + 8 #^3 - 136 #^2 + Boole[OddQ@ #] (14 #^4 - 96 #^3 + 162 #^2 - 92 # + 93))/192 + Boole[Mod[#, 6] == 2] #/6 + Boole[Mod[#, 4] == 2] #/4 + Boole[Mod[#, 6] == 5] (# + 1)/6 &, 30] (* Michael De Vlieger, Jan 21 2018 *)

Formula

a(n) = (n^8 - 6*n^6 - 12*n^5 + 64*n^4 + 8*n^3 - 136*n^2 + (n == 1 (mod 2))*(14*n^4 - 96*n^3 + 162*n^2 - 92*n + 93))/192 + (n == 2 (mod 6))*n/6 + (n == 2 (mod 4))*n/4 + (n == 5 (mod 6))*(n + 1)/6.

a(n) = (n^8 - 6*n^6 - 12*n^5)/192 + b(n) + c(n), where

b(n) = (64*n^4 + 8*n^3 - 136*n^2)/192 for n even,

b(n) = (78*n^4 - 88*n^3 + 26*n^2 - 92*n + 93)/192 for n odd,

c(n) = 0 for n == 0, 1, 3, 4, 7, 9 (mod 12),

c(n) = n/4 for n == 6, 10 (mod 12),

c(n) = n/6 for n == 8 (mod 12),

c(n) = 5/12*n for n == 2 (mod 12),

c(n) = (n + 1)/6 for n == 5, 11 (mod 12).

Conjectures from Colin Barker, Jan 21 2018: (Start)

G.f.: x^2*(1 + 14*x + 176*x^2 + 893*x^3 + 2861*x^4 + 6847*x^5 + 12704*x^6 + 20412*x^7 + 27052*x^8 + 33142*x^9 + 33910*x^10 + 33289*x^11 + 26586*x^12 + 20709*x^13 + 12212*x^14 + 7178*x^15 + 2639*x^16 + 1094*x^17 + 134*x^18 + 68*x^19 - 3*x^20 + 2*x^21) / ((1 - x)^9*(1 + x)^5*(1 - x + x^2)*(1 + x^2)^2*(1 + x + x^2)^2).

a(n) = 3*a(n-1) - a(n-2) - 4*a(n-3) + 4*a(n-4) - 4*a(n-5) + 5*a(n-6) + a(n-7) - 5*a(n-8) + 6*a(n-9) - 10*a(n-10) + 8*a(n-11) - 8*a(n-13) + 10*a(n-14) - 6*a(n-15) + 5*a(n-16) - a(n-17) - 5*a(n-18) + 4*a(n-19) - 4*a(n-20) + 4*a(n-21) + a(n-22) - 3*a(n-23) + a(n-24) for n>24.

(End)