Results 1 to 5 of 5

Math Help - Number of Squares and Rectangles in a Grid

  1. #1
    Member
    Joined
    Dec 2009
    Posts
    226

    Number of Squares and Rectangles in a Grid

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello NOX Andrew
    Quote Originally Posted by NOX Andrew View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Grandad View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello Opalg
    Quote Originally Posted by Opalg View Post
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Grandad View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of rectangles on a checkerboard
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 27th 2012, 08:27 PM
  2. calculate the number of best fit golden rectangles in a given area
    Posted in the Math Challenge Problems Forum
    Replies: 4
    Last Post: July 12th 2012, 03:01 AM
  3. Replies: 3
    Last Post: January 25th 2011, 11:34 PM
  4. The number of cycles in the grid N x M
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 2nd 2010, 08:25 AM
  5. Replies: 12
    Last Post: September 24th 2010, 11:10 AM

Search Tags


/mathhelpforum @mathhelpforum