## Monday, June 4, 2018

### Shape-Counting Problem #2

How many rectangles are there in a 3 x 4 grid? The obvious generalization is to ask how many rectangles there are in an x m grid. As with the first shape-counting problem, we get a two-dimensional array of problems:
Again, the easiest problems to solve are the ones in the top row and the ones in the leftmost column. As this picture illustrates, the number of rectangles in a 1 x m grid is T(m), the mth triangular number.
Similarly, the number of rectangles in an n x 1 grid is T(n). It turns out that we can use the solutions to these problems to solve every other problem. There is a one-to-one correspondence between rectangles in an n x m grid and pairs of rectangles from the n x 1 and 1 x m grids.
So the number of rectangles in an n x m grid is T(n)*T(m). For the 3 x 4 grid that's T(3)*T(4) = 6*10 = 60. Notice the similarity with the first shape-counting problem. To get the solution to a given problem in our array, just multiply the solution to the leftmost problem in the row by the solution to the top problem in the column.

Common Factors
The way I just explained the solution is not the way I originally figured it out. To arrive at the solution I looked at a particular example, found a product that gave the number of each type of rectangle, and then factored.
So working on this problem might provide students a good opportunity to apply their factoring skills.

Summation Notation
Another way to solve the problem is to manipulate some nasty sigma notation. We might realize that the number of rectangles in an n x m grid is the sum of all the answers to these questions: how many i x j rectangles are there in an n x m grid? For example, how many 5 x 8 rectangles are there in a 12 x 17 grid? The answer is (12 - 4)(17 - 7). The number of i x j rectangles in a n x m grid is (n - i + 1)(m - j + 1). So the total number of rectangles in an n x m grid is this double summation:
If you evaluate this sum for some particular values like n = 3 and m = 4 you can figure out the form of the solution like we did above. Alternatively, you can simplify the summation by realizing that
and then manipulating the sum like this:
Thanks for reading! If you solved the problem a different way or have any ideas about how this task could be implemented with students, I would be excited to hear from you!