How many unique squares can be drawn inside a 16 x 16 square if their vertices must lie on a grid (lattice) of integer points? The sides of these smaller squares need not be parallel to the sides of the large square. Any vertex or edge on the boundary of the large square is counted as inside the large square. Bonus: can you generalize this to an n x n square?

Note: This is not a packing problem. These squares can overlap. How many such squares are there?

We start with a catalog of possible squares. We define a "drawing rule" (i,j) that represents the x & y displacement between the 1st and second vertices. Let i range from 1 to 16, and j from 0 to 15.  A square is formed by successive displacements from an (x,y) vertex: (i,j) (-j,i), (-i,-j), and (j,-i), to get back to the original vertex. This covers all possible squares. For each rule, we count how many squares fit inside the boundaries. The smallest square is (i,j) = (1,0) and there are 256. The largest, a 16x16 square is (i,j)= (16,0) and there is 1. As all (i,j) shapes are considered, we find that i+j=k is the governing number: For any k, [k (n+1-k)^2] of them may be drawn. The reason for this is that as the number of ways to make i+j grows linearly, the number of grid points they may be drawn from goes as n+1-k squared.

The table below lists how many i+j=3 squares may be drawn in each row, showing the min and max column in each row. When no square can be drawn in a row, the range is listed as "99 - -1". The are k=3 types of squares: (3,0),(2,1), (1,2) and (n+1-k)^2 = 14^2 = 196 of each fit in the 16x16 grid.

The full table is here list123.txt and the program that generates it is here sf123.f. 

( i  j) row  col min-max  tot  

=========================================

( 3, 0)   0     0 - 13    14

( 3, 0)   1     0 - 13    14

.

.

.

( 3, 0)  13     0 - 13    14

( 3, 0)  14    99 - -1     0

( 3, 0)  15    99 - -1     0 

----------------total for shape (3,0) 196

( 2, 1)   0     1 - 14    14

( 2, 1)   1     1 - 14    14

.

.

.

( 2, 1)  13     1 - 14    14

( 2, 1)  14    99 - -1     0

( 2, 1)  15    99 - -1     0

----------------total for shape (2,1) 196

( 1, 2)   0     2 - 15    14

( 1, 2)   1     2 - 15    14

.

.

.

( 1, 2)  13     2 - 15    14

( 1, 2)  14    99 - -1     0

( 1, 2)  15    99 - -1     0

----------------total for shape (1,2) 196

etc...

The program also summarized the whole collection of (i,j) squares

9n one table as shown below. 6936 total squares are possible in the 16x16 case. 

      1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16

    ----------------------------------------------------------------

  0 256 225 196 169 144 121 100  81  64  49  36  25  16   9   4   1

  1 225 196 169 144 121 100  81  64  49  36  25  16   9   4   1   0

  2 196 169 144 121 100  81  64  49  36  25  16   9   4   1   0   0

  3 169 144 121 100  81  64  49  36  25  16   9   4   1   0   0   0

  4 144 121 100  81  64  49  36  25  16   9   4   1   0   0   0   0

  5 121 100  81  64  49  36  25  16   9   4   1   0   0   0   0   0

  6 100  81  64  49  36  25  16   9   4   1   0   0   0   0   0   0

  7  81  64  49  36  25  16   9   4   1   0   0   0   0   0   0   0

  8  64  49  36  25  16   9   4   1   0   0   0   0   0   0   0   0

  9  49  36  25  16   9   4   1   0   0   0   0   0   0   0   0   0

 10  36  25  16   9   4   1   0   0   0   0   0   0   0   0   0   0

 11  25  16   9   4   1   0   0   0   0   0   0   0   0   0   0   0

 12  16   9   4   1   0   0   0   0   0   0   0   0   0   0   0   0

 13   9   4   1   0   0   0   0   0   0   0   0   0   0   0   0   0

 14   4   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0

 15   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0

The total is 6936

If we look at the results for n=15 as well, we see the pattern: 

lord@rabbit resolve % q

  n? 

15

      1   2   3   4   5   6   7   8   9  10  11  12  13  14  15

  0 225 196 169 144 121 100  81  64  49  36  25  16   9   4   1

  1 196 169 144 121 100  81  64  49  36  25  16   9   4   1   0

  2 169 144 121 100  81  64  49  36  25  16   9   4   1   0   0

  3 144 121 100  81  64  49  36  25  16   9   4   1   0   0   0

  4 121 100  81  64  49  36  25  16   9   4   1   0   0   0   0

  5 100  81  64  49  36  25  16   9   4   1   0   0   0   0   0

  6  81  64  49  36  25  16   9   4   1   0   0   0   0   0   0

  7  64  49  36  25  16   9   4   1   0   0   0   0   0   0   0

  8  49  36  25  16   9   4   1   0   0   0   0   0   0   0   0

  9  36  25  16   9   4   1   0   0   0   0   0   0   0   0   0

 10  25  16   9   4   1   0   0   0   0   0   0   0   0   0   0

 11  16   9   4   1   0   0   0   0   0   0   0   0   0   0   0

 12   9   4   1   0   0   0   0   0   0   0   0   0   0   0   0

 13   4   1   0   0   0   0   0   0   0   0   0   0   0   0   0

 14   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0

The total is 5440

All cases are here. lista123.txt

We see the result for an n is the series sum:

a(n) = SUM(i=1->n) [(n+1-i) i^2]

Running cases n=1,16 gives

lord@rabbit resolve %

   n  =  1   2   3   4   5    6    7    8    9   10   11   12   13   13   15   16

  a(n) = 1   6  20  50 105  196  336  540  825 1210 1716 2366 3185 4200 5440 6936

To gauge this series as a possible closed polynomial form, we take differences:

 1   6  20  50 105  196  336  540  825 1210 1716 2366 3185 4200 5440 6936

   5  14  30  55  91  140  204  285  385  506  650  819 1015 1240 1496

     9  16  25  36  49   64   81  100  121  144  169  196  225  256

      7   9  11  13  15   17   19   21   23   25   27   29   31

        2   2   2   2   2    2    2    2    2    2    2    2

This indicates a(n) is a 4th order polynomial. 

a(n) = A + B n + c n^2 + D n^3 + E n^4