A232568 Number of non-equivalent binary n X n matrices with three pairwise nonadjacent 1's.

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

Author

Heinrich Ludwig, Nov 28 2013

Keywords

• nonn
• easy

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

Examples

			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]
		

Links

• Heinrich Ludwig, Table of n, a(n) for n = 2..1001
• Index entries for linear recurrences with constant coefficients, signature (3,1,-11,6,14,-14,-6,11,-1,-3,1).

Crossrefs

Cf. A232567, A239576, A232569, A172226.

Programs

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

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