5
$\begingroup$

This question is about a surprising formula that is the answer to a counting problem. To me it suggests that there might just be a nice combinatorial interpretation of the problem that I have not yet found. Even if there is not, I'm sure there are much more elegant solutions than mine.


The problem

Suppose we have an $n\times m$ grid of squares with $n$ rows and $m$ columns. In every square we write the number of rectangles that can be made inside the grid and in which it is contained. Consider for example the green square in the image below.

enter image description here

We see that it is contained in $8$ rectangles that can be made inside this $2 \times 3$ grid. If we count this number for every square we get.

enter image description here

Now let $f(n,m)$ denote the sum of these numbers, so $f(2,3)=4 \cdot 6 + 2 \cdot 8=40$. The task is to find a general formula for $f(n,m)$.


My solution

Consider the square with coordinates $(i,j)$, as in the image below. Any rectangle that it is contained in must have its top left corner in the area shown in red. Its bottom right corner must be in the area shown in blue. So the square $(i,j)$ is contained in exactly $\color{red}{ i \cdot j} \cdot \color{blue}{ \left( n - i + 1 \right) \cdot \left( m - j + 1 \right)}$ rectangles.

enter image description here

Now we only need to sum over all squares to get $$ f(n,m)= \sum_{i=1}^n \sum_{j=1}^m \left [ i \cdot j \cdot \left( n - i + 1 \right) \cdot \left( m - j + 1 \right) \right ].$$ To make this calculation a little easier we can introduce $S_n = \displaystyle \sum_{i=1}^n i$ and $T_n = \displaystyle \sum_{i=1}^n i^2$ so that \begin{align*} f(n,m) &= \sum_{i=1}^n \sum_{j=1}^m \left [ i \cdot j \cdot \left( n - i + 1 \right) \cdot \left( m - j + 1 \right) \right ] \\ &= \sum_{i=1}^n \sum_{j=1}^m \left [ i^2 j^2 - m\cdot i^2 j -i^2 j - n \cdot i j^2 -i j^2+ n m \cdot i j+ m \cdot i j + n \cdot i j +i j \right ] \\ &= T_n T_m - m\cdot T_n S_m - T_n S_m - n \cdot S_n T_m - S_n T_m + n m \cdot S_n S_m + m \cdot S_n S_m + n \cdot S_n S_m + S_n S_m \\ &= \left(S_n + n\cdot S_n - T_n\right)\cdot \left(S_m + m\cdot S_m - T_m\right) \end{align*}

Now we can use the well known formulas for $S_n$ and $T_n$ to find that $$ S_n + n\cdot S_n - T_n = \frac{1}{6} n (n+1) (n+2) = \binom{n+2}{3}. $$ Putting this together we get that $$ f(n,m) = \binom{n+2}{3} \cdot \binom{m+2}{3}. $$


I was pretty surprised by the simple nature of this answer. Especially by the fact that it seems to suggest that somewhere along the line $3$ things get chosen out of $n+2$ things and also from $m+2$ things. It gives me a small spark of hope that there exists a nice counting argument that solves this problem. Can anyone give a combinatorial interpretation of the formula for $f(n,m)$? More elegant solutions to the problem are also welcome.

$\endgroup$
8
$\begingroup$

Each combination of rectangle and contained cell determines and is completely determined by a pair of ordered triples: the first lists the rows of the top edge of the rectangle, the cell, and the bottom edge of the rectangle, and the second does the same for the columns. The row triples correspond to multisets of $3$ elements chosen from the set $[n]=\{1,\ldots,n\}$, and there are

$$\left(\!\!\binom{n}3\!\!\right)=\binom{n+3-1}3=\binom{n+2}3$$

of these. Similarly, there $\binom{m+2}3$ column triples, so there are

$$\binom{n+2}3\binom{m+2}3$$

combinations of cell and containing rectangle.

$\endgroup$
6
$\begingroup$

Your sum is [the number of ways to choose a square and a rectangle containing it],
which equals [the number of ways to choose a rectangle and a square inside it].


The row parts of the ways to choose [a rectangle and point inside it]
correspond to length-(n+2) strings consisting of

a beginning-of-rectangle symbol
and
a green-row symbol
and
an end-of-rectangle symbol
and
n-1 blank-row symbols

where the 3 special symbols must be in that order,
giving exactly ​ 3+n-1 choose 3 ​ possibilities for the rows.
Similarly, there are exactly ​ m+2 choose 3 ​ possibilities for the columns.
The product of those gives your expression.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.