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,5

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).

Links

Table of n, a(n) for n=0..44.

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)

Prog

(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}

Crossrefs

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

Sequence in context: A318579 A064932 A343513 * A219667 A192381 A162249

Adjacent sequences: A285953 A285954 A285955 * A285957 A285958 A285959

Keyword

nonn

Author

Rick L. Shepherd, Apr 29 2017

Status

approved