Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

enter image description here 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.

share|improve this question
add comment

3 Answers 3

up vote 1 down vote accepted
+50

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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