login
A232568
Number of non-equivalent binary n X n matrices with three pairwise nonadjacent 1's.
4
0, 6, 40, 210, 681, 1919, 4443, 9481, 18206, 33164, 56570, 92996, 146175, 223565, 330981, 479779, 678508, 943586, 1287036, 1731654, 2293765, 3004011, 3883935, 4973645, 6300906, 7917064, 9857198, 12185816, 14946491, 18218969, 22056585, 26556551, 31783320
OFFSET
2,2
COMMENTS
Also: Number of non-equivalent ways to place three non-attacking wazirs on an n X n board.
Two matrix elements are considered adjacent if the difference of their row indices is 1 and the column indices are equal, or vice versa (von Neumann neighborhood).
Counted for this sequence are equivalence classes induced by the dihedral group D_4. If equivalent matrices are being destinguished, the number of matrices is A172226(n).
LINKS
Index entries for linear recurrences with constant coefficients, signature (3,1,-11,6,14,-14,-6,11,-1,-3,1).
FORMULA
a(n) = (n^6 - 15*n^4 + 20*n^3 + 50*n^2 - 116*n + 48)/48 if n is even; a(n) = (n^6 - 15*n^4 + 28*n^3 + 29*n^2 - 76*n - 15)/48 if n is odd.
G.f.: x^3*(x^9-4*x^8+x^7+12*x^6+9*x^5-70*x^4-77*x^3-84*x^2-22*x-6) / ((x-1)^7*(x+1)^4). - Colin Barker, Dec 06 2013
a(n) = (n^6 - 15n^4 + 28n^3 + 29n^2 - 76n - 15 - ((n+1) mod 2) * (8n^3 - 21n^2 + 40n - 63))/48. - Wesley Ivan Hurt, Dec 06 2013
EXAMPLE
There are a(3) = 6 non-equivalent 3 X 3 matrices with three pairwise nonadjacent 1's (and no other 1's):
[1 0 0] [1 0 1] [1 0 0] [1 0 1] [1 0 1] [0 1 0]
|0 1 0| |0 0 0| |0 0 1| |0 0 0| |0 1 0| |1 0 1|
[0 0 1] [1 0 0] [0 1 0] [0 1 0] [0 0 0] [0 0 0]
MAPLE
A232568:=n->(n^6-15*n^4+28*n^3+29*n^2-76*n-15-((n+1) mod 2)*(8*n^3-21*n^2+40*n-63))/48; seq(A232568(n), n=2..50); # Wesley Ivan Hurt, Dec 06 2013
MATHEMATICA
Table[(n^6-15n^4+28n^3+29n^2-76n-15-Mod[n+1, 2](8n^3-21n^2+40n-63))/48, {n, 2, 50}] (* Wesley Ivan Hurt, Dec 06 2013 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Heinrich Ludwig, Nov 28 2013
STATUS
approved