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

%I #36 Mar 14 2018 03:48:00

%S 0,1,6,17,43,84,159,262,426,635,940,1311,1821,2422,3213,4124,5284,

%T 6597,8226,10045,12255,14696,17611,20802,24558,28639,33384,38507,

%U 44401,50730,57945,65656,74376,83657,94078,105129,117459,130492,144951,160190,177010

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

%C Also: Number of non-equivalent ways to place two non-attacking wazirs on an n X n board.

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

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

%H Heinrich Ludwig, <a href="/A232567/b232567.txt">Table of n, a(n) for n = 1..1000</a>

%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (2,2,-6,0,6,-2,-2,1)

%F 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.

%F 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

%e There are a(3) = 6 non-equivalent 3 X 3 matrices with two nonadjacent 1's (and no other 1's):

%e [1 0 0] [0 1 0] [1 0 0] [0 1 0] [1 0 1] [1 0 0]

%e |0 0 0| |0 0 0| |0 1 0| |1 0 0| |0 0 0| |0 0 1|

%e [0 0 1] [0 1 0] [0 0 0] [0 0 0] [0 0 0] [0 0 0]

%o (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

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

%K nonn,easy

%O 1,3

%A _Heinrich Ludwig_, Nov 26 2013