Hello NOX Andrew Originally Posted by

**NOX Andrew** I was asked how many squares and rectangles can you find in a 4 x 3 grid? (The squares and rectangles can be constructed from multiple unit squares. For example, there are 8 squares and 18 rectangles in a 2 x 3 grid and 20 squares and 60 rectangles in a 3 x 4 grid.)

Does the general problem of finding the number of squares and rectangles in a m x n grid pertain to any branch of mathematics? If so, what branch? A formula to determine the answer to the general question would be appreciated. A proof would be even more appreciated.

First: does the pertain to any branch of mathematics? The closest is probably combinatorics, sequences and series, but a lot of it amounts to problem solving and application of logical analysis. You could say: using your common-sense - but in my experience, it's not that common!

Second, can I solve the problem? Yes.

The first thing to note is that in the examples you quote, the number of rectangles you can find includes the number of squares. So by 'rectangle' you're not excluding those rectangles that are also squares. I'll show you how to solve this one, and leave you to try the number of shapes that are specifically squares in a similar way.

First, let's agree that in an $\displaystyle m \times n$ grid, there are $\displaystyle m$ rows and $\displaystyle n$ columns. Next, when I talk about a $\displaystyle p \times q$ rectangle, I mean a rectangle that is made up of unit squares arranged in $\displaystyle p$ rows and $\displaystyle q$ columns.

OK. Let's start counting, beginning with the smallest rectangle, and working our way up to the largest, using an $\displaystyle m\times n$ grid.

$\displaystyle 1\times1$ rectangle. (Which is, of course, a square.) Obviously we can have $\displaystyle n$ of these along the bottom row (since there are $\displaystyle n$ columns in our grid), and there are $\displaystyle m$ such rows. So the total number of $\displaystyle 1\times1$ rectangles is:$\displaystyle m\times n$

$\displaystyle 2\times1$ rectangle. (That's a rectangle with $\displaystyle 2$ rows and $\displaystyle 1$ column.)We can still fit $\displaystyle n$ of these along the bottom row, since these rectangles are just $\displaystyle 1$ column wide. But we can now only make $\displaystyle (m-1)$ rows like this before we hit the top of the grid. So the total number of $\displaystyle 2\times1$ rectangles is:$\displaystyle (m-1)\times n$

$\displaystyle 3\times1$ rectangle.In a similar way, the number of these rectangles we can find is:$\displaystyle (m-2) \times n$

... and so on, all the way up to:

$\displaystyle m\times1$ rectangle. You should easily see that number of these is:$\displaystyle 1\times n$

Now we pause, and add up the number of rectangles we've found so far. It is:$\displaystyle m\times n + (m-1)\times n + (m-2) \times n + ... + 1\times n$$\displaystyle =(m + [m-1]+ [m-2] + ... + 1)\times n$

You may recognise the series in the brackets as a simple AP (the sum of the first $\displaystyle m$ whole numbers), whose sum is:$\displaystyle \tfrac12m(m+1)$

So the number of rectangles we've found so far is:$\displaystyle \tfrac12m(m+1)\times n$

Now let's look at rectangles that are $\displaystyle 2$ columns wide.

$\displaystyle 1\times 2$ rectangle (That's $\displaystyle 1$ row, $\displaystyle 2$ columns) We can't fit so many along the bottom row now. In fact, only $\displaystyle (n-1)$ of them. But we can get $\displaystyle m$ rows. So the number is:$\displaystyle m\times(n-1)$

$\displaystyle 2\times 2$ rectangle (Another square, of course.)We can still fit $\displaystyle (n-1)$ of them along the bottom row. But we can now only get $\displaystyle (m-1)$ rows. So the number is:$\displaystyle (m-1)\times(n-1)$

... and so on, up to:

$\displaystyle m\times 2$ rectangle. And the number of these is:$\displaystyle 1\times(n-1)$

Adding up in the same way as before, we now get the total:$\displaystyle \tfrac12m(m+1)\times (n-1)$

Can you see that we can continue in the same way? The total number of rectangles 3 columns wide will be:$\displaystyle \tfrac12m(m+1)\times (n-2)$

... and so on.

Finally, we get the total number of rectangles $\displaystyle n$ columns wide as: $\displaystyle \tfrac12m(m+1)\times 1$

All that remains is to add up these totals, noticing that in each one, we have a common factor of $\displaystyle \tfrac12m(m+1)$. So the overall total is:$\displaystyle \tfrac12m(m+1)\times (n+[n-1]+[n-2] + ... +1)$$\displaystyle =\tfrac12m(m+1)\times\tfrac12n(n+1)$

using the same AP formula as before, but with the $\displaystyle n$'s this time. So the formula for the number of rectangles in an $\displaystyle m \times n$ grid is:$\displaystyle \tfrac14mn(m+1)(n+1)$

Now you see if you can derive a formula for simply squares. (You may find it easier to assume that, for the sake of argument, $\displaystyle m > n$.)

Grandad