A317714 Chessboard rectangles sequence (see Comments), also A037270 interleaved with A163102.

0, 0, 1, 2, 10, 18, 45, 72, 136, 200, 325, 450, 666, 882, 1225, 1568, 2080, 2592, 3321, 4050, 5050, 6050, 7381, 8712, 10440, 12168, 14365, 16562, 19306, 22050, 25425, 28800, 32896, 36992, 41905, 46818, 52650, 58482, 65341, 72200, 80200, 88200, 97461, 106722, 117370

Offset: 1

Author

Ivan N. Ianakiev, Aug 05 2018

Keywords

• easy
• nonn

Comments

Take a chessboard of n X n unit squares in which the a1 square is black. a(n) is the number of composite rectangles of p X q unit squares whose vertices are covered by black unit squares (1 < p <= n, 1 < q <= n).

Examples

			In a 4 X 4 chessboard there are two such rectangles (for both p = q = 3) and the coordinates of their lower left vertices are a1 and b2. Therefore, a(4) = 2.
		

Links

• Jinyuan Wang, Table of n, a(n) for n = 1..10000
• Index entries for linear recurrences with constant coefficients, signature (2,2,-6,0,6,-2,-2,1).

Crossrefs

Cf. A005993, A037270, A163102.

Programs

Magma

[(5-5*(-1)^n-12*n+12*(-1)^n*n+14*n^2-6*(-1)^n*n^2-8*n^3+2*n^4)/64: n in [1..50]]; // Vincenzo Librandi, Aug 05 2018

Mathematica

CoefficientList[Series[-((x^2 (1+4 x^2+x^4))/((-1+x)^5 (1+x)^3)),{x,0,44}],x]
LinearRecurrence[{2, 2, -6, 0, 6, -2, -2, 1}, {0, 0, 1, 2, 10, 18, 45, 72}, 80] (* Vincenzo Librandi, Aug 06 2018 *)

PARI

a(n) = sum(i = 1, n-1, floor(i/2)^3); \\ Jinyuan Wang, Aug 12 2019

Python

n, a = 0, 0
while n < 10:
    print(n,a)
n, a = n+1, a+((n+1)//2)**3 # A.H.M. Smeets, Aug 09 2019

Formula

a(n) = 2*a(n-1) + 2*a(n-2) - 6*a(n-3) + 6*a(n-5) - 2*a(n-6) - 2*a(n-7) + a(n-8), with a(1)=0, a(2)=0, a(3)=1, a(4)=2, a(5)=10, a(6)=18, a(7)=45, a(8)=72.

G.f.: -(x^3*(1+ 4*x^2 + x^4))/((-1+x)^5*(1+x)^3).

a(n) = (5 - 5*(-1)^n - 12*n + 12*(-1)^n*n + 14*n^2 - 6*(-1)^n*n^2 - 8*n^3 + 2*n^4)/64.

a(n) = Sum_{i=1..n-1} floor(i/2)^3. - Ridouane Oudra, Jul 24 2019

E.g.f.: (1/64)*exp(-x)*(-5-6*x-6*x^2+exp(2*x)*(5-4*x+4*x^2+4*x^3+2*x^4)). - Stefano Spezia, Aug 14 2019

a(2*n) = A163102(n-1) and a(2*n+1) = A037270(n). - Ridouane Oudra, Mar 24 2024

Sum_{n>=3} 1/a(n) = Pi^2 - Pi*coth(Pi) - 5. - Amiram Eldar, Jul 04 2025