A232569 -id:A232569 - cp's OEIS frontend

A232833 Triangle read by rows: T(n,k) = number of n X n binary matrices with k pairwise nonadjacent 1's, n >= 0, k = 0..n^2.

1, 1, 1, 1, 4, 2, 0, 0, 1, 9, 24, 22, 6, 1, 0, 0, 0, 0, 1, 16, 96, 276, 405, 304, 114, 20, 2, 0, 0, 0, 0, 0, 0, 0, 0, 1, 25, 260, 1474, 5024, 10741, 14650, 12798, 7157, 2578, 618, 106, 14, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 36, 570, 5248, 31320, 127960, 368868

Offset: 0

Heinrich Ludwig, Dec 01 2013

Also number of 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).
If only non-equivalent (mod D_4) matrices are counted, the corresponding numbers are given by A232569.
Rows with trailing zeros dropped give the coefficients of the independence polynomial for the n X n grid graph. - Eric W. Weisstein, May 31 2017

			Triangle begins:
  1;
  1,  1;
  1,  4,  2,   0,   0;
  1,  9, 24,  22,   6,   1,   0,  0, 0, 0;
  1, 16, 96, 276, 405, 304, 114, 20, 2, 0, 0, 0, 0, 0, 0, 0, 0;
  ...

Alois P. Heinz, Rows n = 0..17, flattened (first 8.5 rows from Heinrich Ludwig)
R. J. Mathar, Bivariate generating functions for non-attacking Wazirs on rectangular boards, viXra:2404.0122 (2024) page 14
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Independence Polynomial

Cf. A232569, A006506 (row sums).

Main diagonal gives A201511.

b:= proc(n, l) option remember; local k;
      if n=0 then 1
    elif min(l)>0 then b(n-1, map(x-> x-1, l))
    else for k while l[k]>0 do od;
         b(n, subsop(k=1, l))+expand(x*`if`(n>0, `if`(k (p-> seq(coeff(p,x,i), i=0..n^2))(b(n, [0$n])):
seq(T(n), n=0..6);  # Alois P. Heinz, Apr 16 2024

b[n_, l_] := b[n, l] = Module[{k},
   Which[n == 0, 1,
   Min[l] > 0, b[n - 1, l - 1],
   True, For[k = 1, l[[k]] > 0, k++];
      b[n, ReplacePart[l, k -> 1]] + Expand[x*If[n > 0, If[k < Length[l],
      b[n, ReplacePart[l, {k -> 2, k + 1 -> 1}]],
      b[n, ReplacePart[l, k -> 2]], 0]]]]];
T[n_] := With[{p = b[n, Table[0, {n}]]}, Table[Coefficient[p, x, i], {i, 0, n^2}]]
Table[T[n], {n, 0, 6}] // Flatten (* Jean-François Alcover, Aug 09 2024, after Alois P. Heinz *)

T(n,0) = A000012(n);
T(n,1) = A000290(n), n >= 1;
T(n,2) = A172225(n), n >= 2;
T(n,3) = A172226(n), n >= 2;
T(n,4) = A172227(n), n >= 2;
T(n,5) = A172228(n), n >= 3;
T(n,6) = A178409(n), n >= 3;
T(n,7) = A201507(n), n >= 3;
T(n,8) = A201508(n), n >= 3;
T(n,9) = A201510(n), n >= 3;

T(0,0)=1 inserted by Alois P. Heinz, Apr 16 2024

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

Original entry on oeis.org

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

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

Original entry on oeis.org

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

Heinrich Ludwig, Nov 28 2013

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

			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]

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

Cf. A232567, A239576, A232569, A172226.

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

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

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

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

A232833 Triangle read by rows: T(n,k) = number of n X n binary matrices with k pairwise nonadjacent 1's, n >= 0, k = 0..n^2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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