A232567 Number of non-equivalent binary n X n matrices with two nonadjacent 1's.

0, 1, 6, 17, 43, 84, 159, 262, 426, 635, 940, 1311, 1821, 2422, 3213, 4124, 5284, 6597, 8226, 10045, 12255, 14696, 17611, 20802, 24558, 28639, 33384, 38507, 44401, 50730, 57945, 65656, 74376, 83657, 94078, 105129, 117459, 130492, 144951, 160190, 177010

Offset: 1

Author

Heinrich Ludwig, Nov 26 2013

Keywords

• nonn
• easy

Comments

Also: Number of non-equivalent ways to place two 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).

This sequence counts equivalence classes induced by the dihedral group D_4. If equivalent matrices are distinguished, the number of matrices is A172225(n).

Examples

			There are a(3) = 6 non-equivalent 3 X 3 matrices with two nonadjacent 1's (and no other 1's):
  [1 0 0]    [0 1 0]    [1 0 0]    [0 1 0]    [1 0 1]    [1 0 0]
  |0 0 0|    |0 0 0|    |0 1 0|    |1 0 0|    |0 0 0|    |0 0 1|
  [0 0 1]    [0 1 0]    [0 0 0]    [0 0 0]    [0 0 0]    [0 0 0]
		

Links

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

Crossrefs

Cf. A232568, A232569, A239576, A201511, A172225.

Programs

PARI

x='x+O('x^99); concat(0, Vec(x*(1+x+x^2)*(1+3*x-x^2+x^3)/((1+x)^3*(1-x)^5))) \\ Altug Alkan, Mar 14 2018

Formula

a(n) = (n^4 + 2*n^2 - 4*n)/16 if n is even; a(n) = (n^4 + 4*n^2 - 8*n + 3)/16 if n is odd.

G.f.: x * (1 + x + x^2)*(1 + 3*x - x^2 + x^3) / ((1 + x)^3*(1 - x)^5). - Bruno Berselli, Nov 28 2013