OFFSET
1,4
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).
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).
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
EXAMPLE
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.
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 *)
PROG
(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
(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
(PARI) a(n) = sum(i = 1, n-1, floor(i/2)^3); \\ Jinyuan Wang, Aug 12 2019
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Ivan N. Ianakiev, Aug 05 2018
STATUS
approved