|
![](/i/fill.gif) |
Warp wrote:
> Kevin Wampler <wam### [at] u washington edu> 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
|
![](/i/fill.gif) |