Sum of the area of all the rectangles in a rectangular

Question

We have a rectangular shape with the size n × m meters is divided into rectangles of size 1 × 1 meters.

• Question: Sum of the area of all the rectangles that can be seen in that rectangular is how much?

Example for n=1, m=2: $$ \text{Sum of areas}=a_{1,1}+a_{1,2}=2+2=4 $$ I think the answer is

$${n+2\choose 3}\cdot{m+2\choose 3}\ $$

but I'm not sure. please answer this question if you can prove it.

Answer 1

Consider a rectangle $i\times j$ oriented as the original $n\times m$ rectangle. We can place its upper left corner in any square of a $(n-i+1)\times(m-j+1)$ rectangle, so the sum of all the areas is $$ \sum_{i=1}^{n}\sum_{j=1}^{m} ij(n-1+1)(m-j+1) = \left(\sum_{i=1}^{n}i(n-i+1)\right)\cdot\left(\sum_{j=1}^{m}j(m-j+1)\right).$$ Now we have $$\sum_{i=1}^{n}i(n-i+1)=(n+2)\sum_{i=1}^{n}\binom{i}{1}-2\sum_{i=1}^{n}\binom{i+1}{2}=(n+2)\binom{n+1}{2}-2\binom{n+2}{3};$$ on the other hand: $$(n+2)\binom{n+1}{2}-2\binom{n+2}{3}=3\binom{n+2}{3}-2\binom{n+2}{3}=\binom{n+2}{3},$$ so all the areas sum up to $$\binom{n+2}{3}\cdot\binom{m+2}{3}$$ as claimed.

Answer 2

For a rectangle consisting of $M$ columns and $N$ rows, there will be $(M-m+1)(N-n+1)$ rectangles of $m$ columns and $n$ rows, with $1 \leq m \leq M, 1 \leq n \leq N.$ This can be seen by inspection.

For simplicity, let's say that $M \geq N$ (it's a "landscape" rectangle not a "portrait" rectangle).

So we add up the areas of this many rectangles over all possible $m, n$ and subtract out those for which $m=n$ because we counted them twice:

$$A(M,N) = \left(\sum_{m=1}^M \sum_{n=1}^N (M-m+1)(N-n+1)mn\right) - \sum_{k=1}^N (M-k+1)(N-k+1)k^2.$$

This looks like it agrees with your answer. I hand-checked it for $M=5, N=3.$

We know $\sum_{i=1}^n i = \frac{1}{2}n(n+1)$ and $\sum_{i=1}^n i^2 = \frac{1}{6}n(n+1)(2n+1)$. We can also show that the double sum of the products is simply the product of the single sums. This lets us evaulate the double sums with terms in $mn, m^2n, mn^2, m^2n^2$.

Further, $\sum_{i=1}^n i^3 = \frac{1}{4}n^2(n+1)^2$, and $\sum_{i=1}^n i^4 = \frac{1}{30}(6n^5+15n^4+10n^3-n)$. This lets us evaluate the remaining terms in the second single summation.

Then, it's just a matter of simplification of the individual single sums and individual double sums.

Answer 3

Consider the one-dimensional situation first: We have to sum up the lengths of all lattice segments $S\subset[0,n]$.

Instead we count the number of unit intervals $I$ occurring in these $S$. Each instance $I\subset S$ can be encoded as binary word of length $n+2$ in the following way: Write a string of $n$ zeros representing the $n$ unit subintervals of $[0,n]$, replace the zero representing $I$ by a one; and finally insert a one at each of the two endpoints of $S$. The one representing $I$ will then be the middle of the three.

In this way each binary word of length $n+2$ containing $3$ ones and the rest zeros appears exactly once. There are ${n+2\choose 3}$ such words; therefore the total length of all these segments is ${n+2\choose 3}$.

From the cartesian product structure of the full problem it then immediately follows that the sum of the areas of all lattice rectangles in $[0,n]\times[0,m]$ is given by $${n+2\choose 3}\cdot{m+2\choose 3}\ ,$$ as conjectured by the poser.