A232568 -id:A232568 - cp's OEIS frontend

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

Heinrich Ludwig, Nov 26 2013

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

			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]

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)

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

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

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

A232569 Triangle T(n, k) = number of non-equivalent (mod D_4) binary n X n matrices with k pairwise not adjacent 1's; k=0,...,n^2.

Original entry on oeis.org

1, 1, 1, 1, 1, 0, 0, 1, 3, 6, 6, 3, 1, 0, 0, 0, 0, 1, 3, 17, 40, 62, 45, 20, 4, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 6, 43, 210, 683, 1425, 1936, 1696, 977, 366, 101, 21, 5, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 6, 84, 681, 4015, 16149, 46472, 95838, 143657

Offset: 1

Heinrich Ludwig, Nov 29 2013

Also number of non-equivalent ways to place k 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 corresponding numbers are A232833(n).
Row index starts from n = 1, column index k ranges from 0 to n^2.
T(n, 1) = A008805(n-1); T(n, 2) = A232567(n) for n >= 2; T(n, 3) = A232568(n) for n >= 2;
Into an n X n binary matrix there can be placed maximally A000982(n) = ceiling(n^2/2) pairwise not adjacent 1's.

			Triangle begins:
1,1;
1,1,1,0,0;
1,3,6,6,3,1,0,0,0,0;
1,3,17,40,62,45,20,4,1,0,0,0,0,0,0,0,0;
1,6,43,210,683,1425,1936,1696,977,366,101,21,5,1,0,0,0,0,0,0,0,0,0,0,0,0;
...
There are T(3, 2) = 6 non-equivalent binary 3 X 3 matrices with 2 not adjacent 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]

Heinrich Ludwig, Rows n = 1..8 of irregular triangle, flattened

Cf. A232567, A232568, A239576, A008805, A000982, A201511, A232833.

A239576 Number of non-equivalent (mod D_4) binary n X n matrices with 4 pairwise nonadjacent 1's.

Original entry on oeis.org

0, 3, 62, 683, 4015, 16989, 56196, 158271, 391917, 882683, 1836106, 3587103, 6638267, 11747613, 19985680, 32879339, 52490521, 81638211, 124000342, 184440963, 269135111, 386033453, 545007772, 758491143, 1041639045, 1413189339, 1895630946, 2516334551, 3307717267

Offset: 2

Heinrich Ludwig, Mar 28 2014

Also number of non-equivalent ways to place 4 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).
Without the restriction "non-equivalent (mod D_4)" numbers are given by A172227.

			There are a(3) = 3 non-equivalent binary 3 X 3 matrices with 4 pairwise nonadjacent 1s (x):
  [0 1 0]    [1 0 1]    [1 0 1]
  |1 0 1|    |0 1 0|    |0 0 0|
  [0 1 0]    [1 0 0]    [1 0 1]

Heinrich Ludwig, Table of n, a(n) for n = 2..1000
Index entries for linear recurrences with constant coefficients, signature (4,-1,-16,19,20,-45,0,45,-20,-19,16,1,-4,1)

Cf. A232569, A232568, A232567, A172227.

Flatten[{0,Table[(n^8-30*n^6+24*n^5+352*n^4-576*n^3-1280*n^2+3360*n-1536+If[EvenQ[n],0,(14*n^4-72*n^3+226*n^2-624*n+717)])/192,{n,3,20}]}] (* Vaclav Kotesovec after Heinrich Ludwig, Mar 28 2014 *)
Drop[CoefficientList[Series[-x^2 - x^2*(1 - x + 51*x^2 + 454*x^3 + 1374*x^4 + 2527*x^5 + 1990*x^6 + 634*x^7 - 347*x^8 - 49*x^9 + 87*x^10 + 16*x^11 - 20*x^12 + 3*x^13) / ((-1+x)^9*(1+x)^5), {x, 0, 20}], x],2] (* Vaclav Kotesovec, Mar 29 2014 *)

a(n) = (n^8 -30*n^6 +24*n^5 +352*n^4 -576*n^3 -1280*n^2 +3360*n -1536 + IF(n==1 mod 2)*(14*n^4 -72*n^3 +226*n^2 -624*n +717))/192; n>=3.

G.f.: -x^2 - x^2*(1 - x + 51*x^2 + 454*x^3 + 1374*x^4 + 2527*x^5 + 1990*x^6 + 634*x^7 - 347*x^8 - 49*x^9 + 87*x^10 + 16*x^11 - 20*x^12 + 3*x^13) / ((-1+x)^9*(1+x)^5). - Vaclav Kotesovec, Mar 29 2014

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A232569 Triangle T(n, k) = number of non-equivalent (mod D_4) binary n X n matrices with k pairwise not adjacent 1's; k=0,...,n^2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A239576 Number of non-equivalent (mod D_4) binary n X n matrices with 4 pairwise nonadjacent 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula