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

Author

Joel B. Lewis, Jun 29 2007

Keywords

• easy
• nonn
• tabl

Comments

Reading down the diagonal gives A002415.

Examples

			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;
  ...
		

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

Crossrefs

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

Programs

PARI

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

Formula

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