A285956 Number of orthogonal rectangles with vertices on an n X n square grid of points but with no vertices on the grid's diagonals.

0, 0, 0, 0, 2, 10, 30, 102, 204, 444, 740, 1300, 1950, 3030, 4242, 6090, 8120, 11032, 14184, 18504, 23130, 29250, 35750, 44110, 52932, 64020, 75660, 90012, 105014, 123214, 142170, 164850, 188400, 216240, 245072, 278800, 313650, 354042, 395694, 443574, 492860, 549100, 606900, 672420, 739662

Offset: 0

Author

Rick L. Shepherd, Apr 29 2017

Keywords

• nonn

Comments

Given an order-n magic square with n >= 4, the least number of cells that can be changed to create a new square with all sums of rows, columns, and diagonals preserved is four; the four changed cells must correspond to the vertices of one of these a(n) rectangles. Of course the same sum-preserving property occurs in these cases even when the original n X n square of numbers is not a magic square. Perhaps curiously at first glance, a 3 X 3 (magic) square requires at least six cells to be changed to preserve all the sums (reflection in the central row, column, or either diagonal has the same effect as changing exactly six cells).

Crossrefs

Cf. A000537 (orthogonal rectangles without this grid-diagonal restriction), A085582 (rectangles, orthogonal or not, also unrestricted), A113751 (rectangles, non-orthogonal, also unrestricted).

Programs

PARI

{a(n)= my(c = 0, np1 = n + 1);
for(i1 = 1, n - 1, for(i2 = i1 + 1, n, for(j1 = 1, n - 1,
  if(i1 == j1 || i1 + j1 == np1 || i2 == j1 || i2 + j1 == np1,
    continue,
    for(j2 = j1 + 1, n,
      if(i1 <> j2 && i1 + j2 <> np1 &&
         i2 <> j2 && i2 + j2 <> np1, c++)))))); c}

Formula

Conjectures from Colin Barker, May 03 2017: (Start)

G.f.: 2*x^4*(1 + 3*x + 3*x^2 + 17*x^3) / ((1 - x)^5*(1 + x)^3).

a(n) = (n^4 - 10*n^3 + 33*n^2 - 34*n) / 4 for n even.

a(n) = (n^4 - 10*n^3 + 37*n^2 - 58*n + 30) / 4 for n odd.

a(n) = 2*a(n-1) + 2*a(n-2) - 6*a(n-3) + 6*a(n-5) - 2*a(n-6) - 2*a(n-7) + a(n-8) for n>7.

(End)