%I #15 Apr 16 2022 15:44:24
%S 0,1,11,37,88,175,311,511,792,1173,1675,2321,3136,4147,5383,6875,8656,
%T 10761,13227,16093,19400,23191,27511,32407,37928,44125,51051,58761,
%U 67312,76763,87175,98611,111136,124817,139723,155925,173496,192511,213047,235183,259000
%N From the game of Quod: number of "squares" on an n X n array of points with the four corner points deleted.
%C We count all squares whose vertices are among the points; the sides of the squares need not be horizontal or vertical.
%D Ian Stewart, How To Cut A Cake: and Other Mathematical Conundrums, Chap. 7.
%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (5,-10,10,-5,1).
%F a(n) = (n^4 - n^2 - 48*n + 84)/12.
%F G.f.: x^3*(1+6*x-8*x^2+3*x^3)/(1-x)^5. [_Colin Barker_, May 21 2012]
%e So for n=3 we have 5 points:
%e .....O
%e ....OOO
%e .....O
%e The only square is formed by the 4 outer points, agreeing with a(3)=1.
%e For n=4 we have 12 points:
%e .....OO
%e ....OOOO
%e ....OOOO
%e .....OO
%e There are 5 unit squares, 4 tilted ones with sides sqrt(2) and 2 tilted ones with sides sqrt(5), agreeing with a(4)=11.
%t Drop[CoefficientList[Series[x^3(1+6x-8x^2+3x^3)/(1-x)^5,{x,0,50}],x],2] (* or *) LinearRecurrence[{5,-10,10,-5,1},{0,1,11,37,88},50] (* _Harvey P. Dale_, Apr 16 2022 *)
%K nonn,easy
%O 2,3
%A _Joshua Zucker_, Dec 18 2006
%E Additional comments from _Dean Hickerson_, Dec 18 2006