# Sum of the area of all the rectangles in a rectangular

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.

-

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.

-

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.

-

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.8247134685516357, "perplexity": 176.97388480433204}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2015-40/segments/1443736676622.16/warc/CC-MAIN-20151001215756-00141-ip-10-137-6-227.ec2.internal.warc.gz"}