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

0, 1, 11, 37, 88, 175, 311, 511, 792, 1173, 1675, 2321, 3136, 4147, 5383, 6875, 8656, 10761, 13227, 16093, 19400, 23191, 27511, 32407, 37928, 44125, 51051, 58761, 67312, 76763, 87175, 98611, 111136, 124817, 139723, 155925, 173496, 192511, 213047, 235183, 259000

Offset

2,3

Comments

We count all squares whose vertices are among the points; the sides of the squares need not be horizontal or vertical.

References

Ian Stewart, How To Cut A Cake: and Other Mathematical Conundrums, Chap. 7.

Links

Table of n, a(n) for n=2..42.

Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Formula

a(n) = (n^4 - n^2 - 48*n + 84)/12.

G.f.: x^3*(1+6*x-8*x^2+3*x^3)/(1-x)^5. - Colin Barker, May 21 2012

E.g.f.: exp(x)*(84 - 48*x + 6*x^2 + 6*x^3 + x^4)/12 - 7 - 3*x. - Stefano Spezia, Sep 02 2025

Example

So for n=3 we have 5 points:
     O
    OOO
     O
The only square is formed by the 4 outer points, agreeing with a(3)=1.
For n=4 we have 12 points:
     OO
    OOOO
    OOOO
     OO
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.

Mathematica

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 *)

Crossrefs

Sequence in context: A188382 A090950 A217947 * A140373 A316191 A003020

Adjacent sequences: A124476 A124477 A124478 * A124480 A124481 A124482

Keyword

nonn,easy

Author

Joshua Zucker, Dec 18 2006

Extensions

Additional comments from Dean Hickerson, Dec 18 2006

Status

approved