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

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

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)

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

Example

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]

Prog

(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

Crossrefs

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

Sequence in context: A365409 A171507 A099858 * A062020 A066183 A262297

Adjacent sequences: A232564 A232565 A232566 * A232568 A232569 A232570

Keyword

nonn,easy

Author

Heinrich Ludwig, Nov 26 2013

Status

approved