login
From the game of Quod: number of "squares" on an n X n array of points with the four corner points deleted.
0

%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