Number of Squares and Rectangles in a Grid

**NOX Andrew** · March 8th 2010, 12:11 PM

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.

**Grandad** · March 9th 2010, 05:34 AM

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 $m \times n$ grid, there are $m$ rows and $n$ columns. Next, when I talk about a $p \times q$ rectangle, I mean a rectangle that is made up of unit squares arranged in $p$ rows and $q$ columns.

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

$1\times1$ rectangle. (Which is, of course, a square.)

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

$m\times n$

$2\times1$ rectangle. (That's a rectangle with $2$ rows and $1$ column.)

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

$(m-1)\times n$

$3\times1$ rectangle.

In a similar way, the number of these rectangles we can find is:

$(m-2) \times n$

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

$m\times1$ rectangle.

You should easily see that number of these is:

$1\times n$

Now we pause, and add up the number of rectangles we've found so far. It is:

$m\times n + (m-1)\times n + (m-2) \times n + ... + 1\times n$

$=(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 $m$ whole numbers), whose sum is:

$\tfrac12m(m+1)$

So the number of rectangles we've found so far is:

$\tfrac12m(m+1)\times n$

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

$1\times 2$ rectangle (That's $1$ row, $2$ columns)

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

$m\times(n-1)$

$2\times 2$ rectangle (Another square, of course.)

We can still fit $(n-1)$ of them along the bottom row. But we can now only get $(m-1)$ rows. So the number is:

$(m-1)\times(n-1)$

... and so on, up to:

$m\times 2$ rectangle.

And the number of these is:

$1\times(n-1)$

Adding up in the same way as before, we now get the total:

$\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:

$\tfrac12m(m+1)\times (n-2)$

... and so on.

Finally, we get the total number of rectangles $n$ columns wide as:

$\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 $\tfrac12m(m+1)$ . So the overall total is:

$\tfrac12m(m+1)\times (n+[n-1]+[n-2] + ... +1)$

$=\tfrac12m(m+1)\times\tfrac12n(n+1)$

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

$\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, $m > n$ .)

Grandad

**Opalg** · March 9th 2010, 11:38 PM

Originally Posted by Grandad

So the formula for the number of rectangles in an $m \times n$ grid is:

$\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, $m > n$ .)

Another way to see this is that there are $\textstyle{m\choose2} = \frac12m(m-1)$ ways to choose two rows out of m, and $\textstyle{n\choose2} = \frac12n(n-1)$ ways to choose two columns out of n. Taking these to be the rows and columns along which the rectangle has its edges, you get a total of $\tfrac14mn(m-1)(n-1)$ rectangles.

But I don't think that you can use that short-cut method to find the number of squares.

**Grandad** · March 10th 2010, 12:48 AM

Hello Opalg

Originally Posted by Opalg

Another way to see this is that there are $\textstyle{m\choose2} = \frac12m(m-1)$ ways to choose two rows out of m, and $\textstyle{n\choose2} = \frac12n(n-1)$ ways to choose two columns out of n. Taking these to be the rows and columns along which the rectangle has its edges, you get a total of $\tfrac14mn(m-1)(n-1)$ rectangles.

But I don't think that you can use that short-cut method to find the number of squares.

I like this solution - it's much quicker than mine, but shouldn't you use the $(m+1)$ horizontal lines that make up the $m$ rows, and the $(n+1)$ vertical lines that make up the $n$ columns? So the result is:

$\binom{m+1}{2}\binom{n+1}{2}=\tfrac14mn(m+1)(n+1)$

Grandad

**Opalg** · March 10th 2010, 05:03 AM

Originally Posted by Grandad

shouldn't you use the $(m+1)$ horizontal lines that make up the $m$ rows, and the $(n+1)$ vertical lines that make up the $n$ columns? So the result is:

$\binom{m+1}{2}\binom{n+1}{2}=\tfrac14mn(m+1)(n+1)$

Thanks, I didn't notice that when I wrote my previous comment. I tend to think of a grid as consisting of points (which form the vertices of the squares and rectangles). But this question refers to a grid consisting of cells, which form the contents of the squares and rectangles. So my m and n should be replaced by m+1 and n+1.

Thread: Number of Squares and Rectangles in a Grid

LinkBack

Thread Tools

Display

Number of Squares and Rectangles in a Grid

Similar Math Help Forum Discussions

Number of rectangles on a checkerboard

calculate the number of best fit golden rectangles in a given area

Divide a polygon in minimum number of rectangles and triangles

The number of cycles in the grid N x M

how to calculate the number of grid lines within a circle?

Search Tags