Counting Rectangles¶

Let $R(m, n)$ give the number of rectangles contained in an $m \times n$ grid. We will derive a simple formula for $R$. First, observe that an $m \times 1$ grid contains $\frac{m(m+1)}{2}$ rectangles, i.e. $$R(m, 1) = \frac{m(m+1)}{2}$$ (You could prove this inductively if you really wanted to).

Then, we can derive the following recursive formula for $R$. $$R(m, n) = R(m, n - 1) + n R(m, 1)$$ To make sense of this formula, consider that the number of rectangles in an $m \times n$ grid must be the sum of the number of rectangles in an $m \times (n-1)$ grid (i.e. $R(m, n-1)$) and the number of rectangles in an $m \times n$ grid that are at least partially in the bottom row - these are disjoint sets, so there's no double counting with this approach. We already know the number of rectangles that lie entirely in the bottom row - it's just $R(m, 1)$. We can then make any of those rectangles any height we want between 1 and $n$, giving the formula $n R(m, 1)$.

At this point, we could easily translate this into a recursive function to compute $R$, but we can also simplify this into a closed formula. Substituting the formula for $R(m,1)$ from above, we get $$R(m, n) = R(m, n - 1) + \frac{mn(m+1)}{2}$$ Then, by repeatedly substituting $R(m, n-1)$ with our recursive formula, we get $$R(m, n) = \frac{mn(m+1)}{2} + \frac{m(n-1)(m+1)}{2} + \frac{m(n-2)(m+1)}{2} + \cdots + \frac{m(m+1)}{2} = \sum_{k=1}^n \frac{mk(m+1)}{2}$$ Applying some summation identities (also see problem 1), this simplifies to $$R(m, n) = \frac{mn(m+1)(n+1)}{4}$$ Interestingly, this formula is really just the product of $m$th and $n$th triangular numbers.

In [1]:
def R(m, n):
    return m * n * (m + 1) * (n + 1) // 4

Figuring out the formula's the hard part - now we can just iterate over grid sizes to calculate how many rectangles they have.

In [2]:
totals = dict()

for x in range(1, 2001):
    for y in range(1, 2001):
        r = R(x, y)
        totals[(x,y)] = r
        if r > 2000000:
            break

We'll figure out which grid is the closest to containing 2000000 rectangles.

In [3]:
m, n = min(totals, key=lambda x: abs(totals[x] - 2000000))
m, n
Out[3]:
(36, 77)

The area of that grid is our answer.

In [4]:
m * n
Out[4]:
2772

Relevant sequences¶

  • Number of rectangles in an $m \times n$ grid: A098358

Copyright (C) 2025 filifa¶

This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International license and the BSD Zero Clause license.