In an n x n grid of squares, how many squares are there?

> 1. In a n x n grid of squares how many squares are there?

There are n^2 1x1 squares, (n-1)^2 2x2 squares, ... , 1 nxn square
so the answer is 1+4+9+...+(n-1)^2+n^2 = n(n+1)(2n+1)/6.

> 2. The number of all rectangles (including squares) in a n x n grid?

There are (n+1-i)(n+1-j) rectangles of size ixj, so summing for all i
and for all j one gets (1+...+n)(1+...+n) = n^2.(n+1)^2/4.

> 3. The number of triangles in a n x n equilateral triangle grid?

I'll assume what you mean is for n=3,

     /\
    /__\
   /\  /\
  /__\/__\
 /\  /\  /\
/__\/__\/__\

The "upwards" triangles of side i : there are 1+...+(n+1-i), so the
total sum over i is 1.n+2.(n-1)+...+i(n+1-i)+...+(n-1).2+n.1 that is
(n+1)(1+2+...+n)-(1+4+...+n^2)=n(n+1)^2/2-n(n+1)(2n+1)/6 and the
result is n(n+1)(n+2)/6.
The downwards triangles of side i : there are 1+...+(n+1-2i) =
(n+1-2i)(n+2-2i)/2 = (n+1)(n+2)/2 - (2n+3)i + 2i^2 and summing over i :

- if n=2k : sum i=1..i=k, which gives n(n+1)(n+2)/4 - n(n+2)(2n+3)/8 +
  n(n+2)(n+1)/12 = n(n+1)(n+2)/12 - n(n+2)/8 = (2n-1)n(n+2)/24

- if n=2k+1 : sum i=1..i=k, gives (n-1)(n+1)(n+2)/4 - (n-1)(n+1)(2n+3)/8
  + (n-1)(n+1)n/12 = (n-1)(n+1)(n/12 + 1/8) = (2n+3)(n-1)(n+1)/24

So if n is even the final answer is

n(n+1)(n+2)/6 + n(n+2)(2n-1)/24 = n(n+2)(6n+3)/24 = n(n+2)(2n+1)/8.

If n is odd, the final answer is

n(n+1)(n+2)/6 + (2n+3)(n-1)(n+1)/24 = (n+1)(6n^2+9n-3)/24 =
(n+1)(2n^2+3n-1)/8.

-- Denis Auroux <auroux@clipper.ens.fr>

[ Editor: from a 1998 thread about counting the rectangles on a
chessboard. ]

"Chris Nicks" <nickscb@shoneys.com> said:

>I used a spreadsheet.  It was set up to calculate 1*1 + 1*2 + ... + 1*8 +
>2*1 + 2*2 + ... 8*8 squares.  after a little thought and drawing, I
>determined that it was possible to have 9-n rectangles of side n, for
>every n 1 to 8.  In other words, if the rectangle was 3 squares wide,
>it's possible to have 9-3=6 rectangles in that row.  Extrapolating this
>to cover an 8x8 board, my 64 row spreadsheet calculates that there are
>1,296 distinct rectangles, and, in the same manner that you used, 204
>distinct squares.

Finding the number of rectangles on a chessboard can be done much more
elegantly than the summation.  There are 9 horizontal lines and 9
vertical lines that mark the boundaries of the smaller squares.  There
is a 1-1 correspondance between rectangles and choices of 2 horizontal
and 2 vertical lines from that set.  Therefore, the answer is
C(9,2)^2 = 36^2 = 1296.

-- Matthew Daly <mwdaly@pobox.com>, October 1998

naineni@sequent.com (Malahal Rao Naineni) writes:
>I am trying to solve the following problem. Any help?
>Let a triangle ABC be divided into smaller triangles in the
>following way. Mark points on the sides, dividing each side into n
>EQUAL points. Draw lines parallel to the sides (AB, BC, CA) through these
>points. How many triangles (of all sizes) are created?

The answer satisfies a third-order recurrence relation with 1 as a
triple root, inhomogeneous term (3+(-1)^n)/2, and initial conditions
0,1,5 for n=0,1,2.  Applying the characteristic equation method for
solving recurrence relations yields the formula
(1/16) [4n^3 + 10n^2 + 4n -1 + (-1)^n ] .

-- Douglas West <west@turan.math.uiuc.edu>, April 1996

[ Editor: this agrees with Denis Auroux's two formulas above; e.g. for
n = 3, (108+90+12-1-1)/16 = 13 = 4*(18+9-1)/8. ]