Counting Rectangles within Rectangles

Squares

How many squares can be found in the checkerboard shown in the figure, below?

There is one 8x8 square, the outer border of the figure.  There are four 7x7 squares, one aligned with each corner.   There are nine 6x6 squares, etc.  So the sum of the first 8 squares 1+4+9+16+25+36+47+64=204 is the answer.  In general, the sum of the first n squares is given by the formula

(2n³+3n²+n)/6

Formulas for sums of the first n numbers of a given power are always polynomials of degree one higher than the given power.  For example, the sum of n fourth powers is given by a fifth degree polynomial in n.  The Method of Successive Differences can be used to find such polynomials.

Rectangles

Now, how many rectangles can be found within an m x n rectangle?

The answer to this question is the same as the answer to another question:

How many ways can I draw two horizontal lines and two vertical lines through an array of (m+1) by (n+1) dots?

(Think of the dots formed at the corners of the little squares within the rectangle)

The two horizontal lines can be drawn C(m+1,2) ways, and the two vertical lines can be drawn C(n+1,2) ways, so the total number of rectangles within an m x n rectangle is

C(m+1,2) C(n+1,2)

Squares within Rectangles

How many squares can be found within an m x n rectangle?  (m > n)

To answer this question, start with an n x n square, and then you know the number of squares in this portion of it from the first section:

(2n³+3n²+n)/6

Now, consider adding one row of squares at the bottom, making it an n+1 by n rectangle.  Think of the dots formed at the corners of the little squares you added to make the bottom row.   Now, for every pair of newly-added dots, you can find one new square.  So the number of new squares you can find in the now larger rectangle is the number of pairs of n+1 dots, which is C(n+1,2).  If you need convincing, there's another way to think of it.  By adding a new row of n little squares, you can now find within the large rectangle one new n x n square, two new n-1 x n-1 squares, three new n-2 x n-2 squares, etc.  So the number of new squares added this way is the sum of the first n counting numbers, which is C(n+1,2).

Now, add another row of squares at the bottom, making it an n+2 by n rectangle.  This adds the same number of new squares, C(n+1,2).

Now I'm sure you see the picture.  The number of squares that can be found within an m x n rectangle (m > n) is given by this formula:

(2n³+3n²+n)/6 + (m-n) C(n+1,2)

Internet References

Method of Successive Differences to find the coefficients of a polynomial f(k), given a few values of f(k) for successive integers, k.

Related Pages in this Website

Go back to Counting 

How many squares? puzzle question, from the 2004 Academic Decathlon test.

Method of Successive Differences to find the coefficients of a polynomial f(k), given a few values of f(k) for successive integers, k.

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]