2
$\begingroup$

The following is a problem from TopCoder:

Problem. Given the width and the height of a rectangular grid, return the total number of non-square rectangles that can be found on the grid.

For example, for a grid with width $ 3 $ and height $ 3 $, i.e.,

3-by-3 grid

there are

  • four $ (2 \times 3) $-rectangles,
  • six $ (1 \times 3) $-rectangles and
  • twelve $ (1 \times 2) $-rectangles.

There are thus a total number of $ 4 + 6 + 12 = 22 $ rectangles. Note that we don’t count $ (1 \times 1) $-, $ (2 \times 2) $- or $ (3 \times 3) $-rectangles because these are actually squares.

I have assumed that “$ 2 \times 3 $” means “$ 2 $ rows and $ 3 $ columns”. Is my assumption correct?

Can someone help me to find how many rectangles there are in the rectangular grid below?

5-by-7 grid

EDIT: The actual grid in the question is unknown, so a $ (5 \times 7) $-grid is being given as a working example.

$\endgroup$
11
  • 2
    $\begingroup$ I would look for the total number of rectangles including squares, and then subtract the number of squares. A rectangle is given by its top-left-to-bottom-right diagonal, which is a pair of points. $\endgroup$
    – Arthur
    Commented May 13, 2015 at 15:05
  • $\begingroup$ Based on the counts, 2x3 must mean either 2 rows and 3 columns or 2 columns and 3 rows -- i.e., both orientations of the (non-square) rectangle. Likewise for 1x3 and 1x2. $\endgroup$ Commented May 13, 2015 at 15:13
  • 1
    $\begingroup$ Arthur’s suggestion is good. To count the number of rectangles, count the number of ways to choose two points not in the same row or column. Each such pair of points determines a rectangle having a diagonal between those points. The number of such pairs of points is twice the number of rectangles (including squares), because each rectangle has two diagonals. (If you count ordered pairs of points, you will get four times the number of rectangles.) $\endgroup$
    – Steve Kass
    Commented May 13, 2015 at 15:14
  • $\begingroup$ Also, what do you mean by "the below rectangular grid"? Is there a picture missing? $\endgroup$ Commented May 13, 2015 at 15:14
  • $\begingroup$ Tried to fix up the question but I don't think the requested image was available, so put a sample grid in place - @jamesjohnson92 can you confirm what the required grid dimensions are? $\endgroup$
    – Joffan
    Commented May 13, 2015 at 16:11

2 Answers 2

5
$\begingroup$

Notation

I have assumed that “$2\times3$” means “$2$ rows and $3$ columns”. Is my assumption correct?

It depends on the context. In general I'd agree, but since the counts you quote doesn't include a separate handling of the $3\times2$ case, in this situation I'd rather assume that $2\times3$ is meant to cover both orientations, both two rows and three columns and two columns and three rows.

Total count

Can someone help me to find how many rectangles there are in the rectangular grid below?

If all you are interested in is the total number of non-square rectangles, then it doesn't matter how you write down each individual count. In fact, I'd not iterate over all possible shapes, but instead use a different approach.

For a grid of $m\times n$ tiles, there are $(m+1)\times(n+1)$ tile corners. If you consider each of them as a possible corner of a rectangle, and define each rectangle by two opposite corners, then you have a total of

$$\bigl((m+1)(n+1)\bigr)^2$$

possible combinations of two points. Obviously, that number is way too large, because we counted some things we shouldn't, and counted others more than once. So let's address those issues.

You don't want either dimension of such a rectangle to be zero. So if you picked the first point, then there are $m+n+1$ possible positions where that second point would be in the same row and/or the same column as the first. Subtract that and you are at

$$(m+1)(n+1)\bigl((m+1)(n+1)-(m+n+1)\bigr)=(m+1)(n+1)mn\;.$$

As Arthur pointed out in a comment, you can think of this as picking the second point from the $m\times n$ possible corner positions which you obtain by removing the “forbidden” row and column. At this point you have two points in distinct rows and columns, but nothing is sorted yet. So every possible rectangle is counted four times: any of its four corners might be the first point, with the opposite corner as the second point. So the number of rectangles is

$$\tfrac14(m+1)(n+1)mn\;.$$

Now you still have to get rid of those squares. How many are there? Let's look for a pattern. There are $m\times n$ squares of size $1$. There are $(m-1)\times(n-1)$ squares of size $2$, and so on. The maximal size such a square can have is the smaller of the dimensions of your tile grid. So there are

$$\sum_{i=1}^{\min(m,n)}(m+1-i)(n+1-i)$$

squares in total. Assuming $m\le n$ this simplifies to

$$\sum_{i=1}^{m}(m+1-i)(n+1-i)=\tfrac16 m(m+1)(3n-m+1)\;.$$

Now take the number of all rectangles, subtract all squares, and you are done. If you expand and then factor the result, you get a total count of

$$\tfrac1{12}m(m+1)(3n^2 + 2m - 3n - 2)= \tfrac1{12}m(m+1)\bigl(3n(n-1) + 2(m-1)\bigr)\;.$$

For $m=n=3$ this indeed yields a count of $22$. For $m=5,n=7$ (remember to ensure $m\le n$) this gives a count of $335$ non-square rectangles. You can verify that count with a brute-force computation.

Bonus question

If you want to, it might be interesting to think about why that formula always results in an integer if $m,n$ are integers.

Either $m$ or $m+1$ is divisible by two, so their product is even. For the same reason, $n(n-1)$ is even, and since $2(m-1)$ is even, too, $\bigl(3n(n-1) + 2(m-1)\bigr)$ must be even. So the whole thing is the product of two even numbers, and therefore divisible by four.

Exactly one of $m,(m+1),(m-1)$ is divisible by three. In the first two cases, the whole product is obviously divisible by three. In the last case, $\bigl(3n(n-1) + 2(m-1)\bigr)$ is divisible by three since it's the sum of two integers which are divisible by three. As the whole thing is divisible by four and by three, it is divisible by twelve.

$\endgroup$
4
  • $\begingroup$ Good answer! Well thought out, steps shown, and a clean formula at the end. Seriously, you've made a great answer. $\endgroup$
    – Asimov
    Commented May 13, 2015 at 17:26
  • 1
    $\begingroup$ Very good answer, but it could be slightly cleaner. $(m+1)(n+1)-(m+n+1)$ simplifies to $mn$, with the interpretation that after picking one vertex, you delete a row and a column, so there are $mn$ vertices left. $\endgroup$
    – Arthur
    Commented May 13, 2015 at 18:19
  • $\begingroup$ @Arthur: Good point. I deliberately avoided simplifications just for the sake of shorter formulas at that point, but with that interpretation this is indeed a win in both complexity and clarity. I incorporated that in my post. $\endgroup$
    – MvG
    Commented May 13, 2015 at 18:29
  • $\begingroup$ @MvG I have understood the equations. One more help, can you explain " how to get rid of squares" and why did you choose min(m,n) ? $\endgroup$
    – James K J
    Commented May 16, 2015 at 14:29
1
$\begingroup$

Let the lattice be composed of m rows and n columns forming m*n squares.

The lattice is actually composed by (m+1) horizontal and (n+1) vertical and lines. An object (it doesn’t matter where it is a rectangle or a square) is formed by any two horizontal lines and any two vertical lines. Thus, the number of such objects = $\binom {m+1}{2} \cdot \binom {n+1}{2}$ …. (1).

Let us count the total number of 1 x 1 squares. Notice that each these squares has a distinct right-bottom corner point. We found m x n those right-bottom corner points. This means there are are [m] . [n] square whose size is 1 x 1. See figure 1.

enter image description here

We use the similar fashion to count the number of 2 x 2 squares and there are [m – 1] . [n – 1] in total. See figure 2.

enter image description here

The other sizes of squares can be counted similarly and the counting stops when any one of the square bracket terms has reached a $1$.

Thus, the total number of squares = [m] . [n] + [m – 1][n – 1] + [m – 2] . [n – 2] + … …… (2)

(2) has a regualar pattern and can therefore be re-written in some closed form.

The required total = (1) – (2)

For a 3 by 3 lattice, TOTAL = 36 – 14 = 22

For a 7 by 5 lattice, TOTAL = $\frac {6*5}{1*2} * \frac {8*7}{1*2} – ([7].[5] + [6].[4] + … [3].[1]) = 335$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .