Count the rectangles in a diagonal grid

Question

As a follow-up to this challenge, we now want to count the number of rectangles in grid with r rows and c columns where there is a line crossing through every diagonal of a square in the grid. Now, we are still counting the the same rectangles as before, but this time we must also include rectangles that are tilted by 45 degrees.

Your goal is to create a function or program that given the number of rows r and columns c outputs the number of rectangles in a diagonal grid with dimensions (r, c).

As a demonstration, this is an animation that iterates through all 37 rectangles formed by a (2 x 3) diagonal grid.

Test Cases

Each case is [rows, columns] = # of rectangles
[0, 0] = 0
[0, 1] = 0
[1, 0] = 0
[1, 1] = 1
[3, 2] = 37
[2, 3] = 37
[6, 8] = 2183
[7, 11] = 5257
[18, 12] = 40932
[42, 42] = 2889558
[51, 72] = 11708274

Rules

• This is code-golf so the shortest code wins.
• Builtins that solve this are not allowed.

Answer 1

Ruby, 58 bytes

This is a straightforward implementation of the algorithm in Releasing Helium Nuclei's C answer.

g=->m,n{n>m ?g[n,m]:m*~m*n*~n/4+n*((2*m-n)*(4*n*n-1)-3)/6}

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.

For 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 5x5 grid, 2x8, 4x6, 6x4, and 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 f is 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

def f(m,n):
 if n > m:
     return f(n,m)
 if n == 0:
     return 0
 else:
     return(m-n+1)*(4*n**4-n*n-3*n)/6-f(m-1,n-1)+(m-n)*2+(m-n)*(n-2)-(m-n-1)*f(n-1,n-1)

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 3, while 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 2-by-(2n-1) rectangles for each extra diamond.
• +(m-n)*(n-2) accounts for an extra n-by-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.

Note: when m==n, 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}

Answer 2

C, 71 64 bytes

f(m,n){return n>m?f(n,m):m*~m*n*~n/4+n*((2*m-n)*(4*n*n-1)-3)/6;}

Try it on Ideone

Answer 3

Python, 73 68 bytes

x=lambda m,n:m*~m*n*~n/4+n*((2*m-n)*(4*n*n-1)-3)/6if m>n else x(n,m)

And while the following version has a higher bytecount (75), it was a nice exercise in finding places to use ~:

def f(r,c):
 if r<c:r,c=c,r
 x=(4*c**3-c)/3
 return r*c*~r*~c/4+x*r--~x*c/2

Answer 4

Convex, 37 36 bytes

__:)+×½½\~æ<{\}&:N\¦\-N¦¦N*(*3-N*6/+

Try it online!

Uses betseg's algorithm modified and optimized for a stack-based language. Explanation to come when I have some more free time. I bet this can be shortened but I'm not going to bother at the moment.

Answer 5

Batch, 82 bytes

@if %2 gtr %1 %0 %2 %1
@cmd/cset/a%1*~%1*%2*~%2/4+((%1+%1-%2)*(%2*%2*4-1)-3)*%2/6