Warp wrote:
> Kevin Wampler <wam### [at] uwashingtonedu> wrote:
>> Warp wrote:
>>>   So the task is simple: Write a function f(m,n) which tells how many
>>> rectangles can be found in an m x n grid. (Explain how you came up
>>> with the function).
> 
>> You mean just something like n*m*(n-1)*(m-1)/4?  The derivation is 
>> pretty direct from the one-dimensional case.
> 
>   It would be interesting to see that derivation.

Let's consider the one-dimensional case (so set m=1).  In this case we 
have one rectangle of width n-1, two rectangles of width n-2, three of 
width n-3, ..., and n-1 of width 1.  We can express the total number of 
rectangles as the sum:

sum_{i=1:n-1} i

Which as the solution n*(n-1)/2.

If we relax the restriction that m=1, then we instead get the double sum:

sum_{j=1:m-1} j * sum_{i=1:n-1} i

Intuitively you can think of this as follows: for each of the 
one-dimensional rectangles along the m-axis, we have sum_{i=1:n-1} 
rectangles along the n-axis.  You can view this sum as expressing every 
rectangle as being defined by two line segments along the n- and m- 
axes.  In any case, the value of the sum is easy to compute:

sum_{j=1:m-1} j * sum_{i=1:n-1} i

= sum_{j=1:m-1} j * n*(n-1)/2

= (n*(n-1)/2) * sum_{j=1:m-1} j

= (n*(n-1)/2) * (m*(m-1)/2)

= n*m*(n-1)*(m-1)/4

Post a reply to this message