Number of rectangles in an m-by-n square grid of points

lookagain

Elite Member
Joined
Aug 22, 2010
Messages
3,186
Suppose there is an m-by-n square grid of points.

You want to form all possible rectangles (squares and non-square rectangles)
such that each vertex (corner) of a rectangle coincides with one of the
grid points.

Come up with a formula in terms of m and n for the total of all of these rectangles.
 
Hello, lookagain!

Are you including rectangles like \(\displaystyle ABCD\) below?


. . . . . \(\displaystyle \begin{array}{cccccc} * & * & B & * & * & * \\ * & o & * & o & * & * \\ A & * & * & * & o & * \\ * & o & * & * & * & C \\ * & * & o & * & o & * \\ * & * & * & D & * & * \end{array}\)
 
How many individual rectangles can be identified by dividing a given rectangle with n horizontal and n vertical lines ?

Rectangles parallel to the m and n sides.



The object here is to divide the rectangle up into smaller rectangles, none of which are squares. As with any problem of this type, the first thing to do is to derive what data you can by examining small values of m and n first.
If we draw a rectangle and divide the sides into 2 segments by drawing one horizontal and one vertical line, we see rather quickly that we can visualize 9 rectangles including the given rectangle.
If we divide the sides into 3 segments by drawing two horizontal and vertical lines, with some care, we can define a total of 36 distinct rectangles.
Putting our eyes to the test, what if we divide the sides into 4 segments by drawing three horizontal and vertical lines? With some care, we can define 100 distinct rectangles. What can we learn from this information? Lets summarize in a chart:

Lines-n.....................0......1......2......3 n horizontal and n vertical
R(nxn) rectangles......1......9.....36...100 (including the given rectangle)

Is their anything familiar about the numbers we see here? In particular, 1, 9, 36, 100? Some of our very familiar perfect squares, of course. This would lead me to believe that subsequent quantities of rectangles within a rectangle can be derived from a very simple expression. But lets take another look at what else pops up from our extended table of data, assuming that the square law applies to higher values of n.

Term........................1......2......3......4......5......6...................n
Number of Lines-n.....0......1......2......3......4......5 n horizontal and n vertical
R(nxn) rectangles......1......9.....36...100...225..441 (including the given rectangle)
Sqrt(R).....................1......3......6.....10....15 ...21

Anything look familiar about the last row of numbers? They are the triangular numbers derived from Tn = n(n + 1)/2. What this says, in all its simplicity, is that the number of rectangles created within a given rectangle by constructing "n" horizontal and "n" vertical lines within the rectangle is defined by R(nxn) = T(n+1)^2. Stated another way, a rectangle divided up by "n" horizontal and "n" vertical lines contains a number of rectangles in the quantity of the (n+1)th triangular number squared. How simple. In all cases the number includes the initial given rectangle.

Another way of expressing it is to consider n as the number of spaces the lines divide the rectangle into. In other words, 2 lines divided the rectangle into 3 sections while 3 lines divided the rectangle into 4 sections. If we use "n" to equal the number of spaces, then R(nxn) = (Tn)^2 = [n(n+1)/2]^2.

Lets take this one step further now and ask ourselves how many individual rectangles can be identified by dividing a given rectangle with "m" horizontal and "n" vertical lines ? Lets see what results.


Horizontal lines-m.....1......2......3......4......5
Vertical lines-n.........0......1......2......3......4
R(mxn) rectangles....3.....18....60...150...315

If we review these numbers we soon see that 3 = 1x3, 18 = 3x6, 60 = 6x10, 150 = 10x15, and 315 = 15x21, or the products of successive triangular numbers. Therefore, since our earlier data gave us R(nxn) = T(n+1)^2, we can now write that R(mxn) = T(m+1)xT(n+1) where m and n represent the number of howizontal and vertical lines.
If we again use "m" and "n" to represent the number of spaces the lines create, R(mxn) = TmxTn = [m(m+1)/2]x[n(n+1)/2] = mn(m+1)(n+1)/4.







 
Suppose there is an m-by-n square grid of points. You want to form all possible rectangles (squares and non-square rectangles) such that each vertex (corner) of a rectangle coincides with one of the grid points.
Assuming that you mean that there a total of \(\displaystyle m\times n\) grid points and the rectangles that have horizontal and vertical sides, then the answer is:
\(\displaystyle \dbinom{m}{2}\dbinom{n}{2}.\)
 
Hello, lookagain!

Are you including rectangles like \(\displaystyle ABCD\) below?


. . . . . \(\displaystyle \begin{array}{cccccc} * & * & B & * & * & * \\ * & o & * & o & * & * \\ A & * & * & * & o & * \\ * & o & * & * & * & C \\ * & * & o & * & o & * \\ * & * & * & D & * & * \end{array}\)

\(\displaystyle \texdt{Yes.}\)
 
Assuming that you mean that there a total of \(\displaystyle m\times n\) grid points
and the rectangles that have horizontal and vertical sides, then the answer is:
\(\displaystyle \dbinom{m}{2}\dbinom{n}{2}.\)

The rectangles intended here are not just those. They include all of the orientations
of rectangles, such as the ones in the subset asked about by soroban.
 
Top