A130684 Triangle read by rows: T(n,k) = number of squares (not necessarily orthogonal) all of whose vertices lie in an (n + 1) X (k + 1) square lattice.

1, 2, 6, 3, 10, 20, 4, 14, 30, 50, 5, 18, 40, 70, 105, 6, 22, 50, 90, 140, 196, 7, 26, 60, 110, 175, 252, 336, 8, 30, 70, 130, 210, 308, 420, 540, 9, 34, 80, 150, 245, 364, 504, 660, 825, 10, 38, 90, 170, 280, 420, 588, 780, 990, 1210, 11, 42, 100, 190, 315, 476, 672

Offset

1,2

Comments

Reading down the diagonal gives A002415.

Links

Joel B. Lewis, Jun 29 2007, Table of n, a(n) for n = 1..210

Problem solved on the Art of Problem Solving forum, Number of squares in a grid

Formula

T(n, k) = k*(k+1)*(k+2)*(2*n - k + 1)/12 (k <= n).

Example

T(2, 2) = 6 because there are 6 squares all of whose vertices lie in a 3 X 3 lattice: four squares of side length 1, one square of side length 2 and one non-orthogonal square of side length the square root of 2.
Triangle begins:
  1;
  2,   6;
  3,  10,  20;
  4,  14,  30,  50;
  5,  18,  40,  70, 105;
  6,  22,  50,  90, 140, 196;
  7,  26,  60, 110, 175, 252, 336;
  ...

Prog

(PARI) T(n, k) = binomial(k+2, 3)*(2*n - k + 1)/2 \\ Charles R Greathouse IV, Mar 08 2017

Crossrefs

Cf. A002415. For squares whose edges are required to be parallel to the edges of the large square, see A082652.

Sequence in context: A276578 A277810 A180428 * A295644 A079178 A322365

Adjacent sequences: A130681 A130682 A130683 * A130685 A130686 A130687

Keyword

easy,nonn,tabl

Author

Joel B. Lewis, Jun 29 2007

Status

approved