Ruby, 58 bytes
This is a straightforward implementation of the algorithm in Releasing Helium Nuclei's C answer.
I have been investigating why this formula works, with limited success. It's easy to confirm that the number of upright rectangles is equal to
(m+1)*m/2 * (n+1)*n/2, the number of diagonal rectangles is a little more elusive.
Neil has confirmed for
m==n that the number of tilted rectangles in an
n*n square is
(4*n**4-n*n-3*n)/6 and that when
m>n you need to add an additional
(m-n)(n*(4*n*n-1)/3) (related to OEIS A000447), though this does not explain where those two formulas came from. I have found part of the answer.
m==n, the shape inside the grid is an Aztec diamond.
The number of rectangles in an Aztec diamond is the sum of number of large rectangles superimposed to make it (for the fourth diamond, which is found in a
8x2) minus the number of the rectangles counted twice (the number of rectangles in the previous Aztec diamond).
The formula here is (TeX to be added later):
# superimposed rectangles, 2x(2n-2), 4*(2n-4), ...
f = lambda n: sum( (2*k)*(2*k+1)/2 * (2*n-2*k)*(2*n-2*k+1)/2 for k in range(1, n) )
aztec_rect = f(n) - f(n-1)
According to Wolfram Alpha, the closed form for
1/30*(n-1)*n*(4*n**3+14*n**2+19*n+9) and the closed form for
aztec_rect is, as Neil discovered,
1/6*n*(n-1)*(4*n**2+4*n+3) == 1/6*(4*n**4-n**2-3*n).
I have yet to discover why
(m-n)(n*(4*n*n-1)/3) works, though I suspect that it is because one definition of A000447 is
binomial(2*n+1, 3). I will keep you posted.
Update: I have reason to believe that the function of the number of rectangles in an extended Aztec diamond
m>n is related to the number of superimposed
2k*2(n-k) rectangles in the diamond minus
F(m-1,n-1). More results when I have them.
Update: I tried a different route and ended up with another formula for extended Aztec diamonds that is mostly explainable but has one term that I don't yet understand. Huzzah! :D
if n > m:
if n == 0:
A quick breakdown of that last formula:
(m-n+1)*(4*n**4-n*n-3*n)/6 is the number of superimposed Aztec diamonds of size
n in the structure, as
f(n,n) = (4*n**4-n*n-3*n)/6.
f(7,3) has 5 superimposed Aztec diamonds size
f(3,3) has only 1 diamond.
-f(m-1,n-1) removes some of the duplicate rectangles from the middle of the superimposed diamonds.
+(m-n)*2 accounts for 2 extra
(2n-1) rectangles for each extra diamond.
+(m-n)*(n-2) accounts for an extra
n square for each extra diamond.
-(m-n-1)*f(n-1,n-1) This is the new puzzling term. Apparently I have not accounted for some extra squares in my counting, but I haven't figured out where they are in the extended diamond.
m-n-1 = -1, meaning that this last term adds squares to the counting. I might be missing something in my regular formula. Full disclosure, this was only meant to be a patch to an earlier draft of this formula that just happened to work. Clearly, I still need to dig into what's going on, and it may be that my formula has some bugs in it. I'll keep you posted.
Russell, Gary and Weisstein, Eric W. "Aztec Diamond." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/AztecDiamond.html