|
|
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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
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).
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|