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

Comments

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

Links

Alois P. Heinz, Rows n = 0..17, flattened (first 8.5 rows from Heinrich Ludwig)

Eric Weisstein's World of Mathematics, Grid Graph

Eric Weisstein's World of Mathematics, Independence Polynomial

Formula

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;

Example

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

Maple

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<nops(l),
         b(n, subsop(k=2, k+1=1, l)), b(n, subsop(k=2, l))), 0))
      fi
    end:
T:= n-> (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

Crossrefs

Cf. A232569, A006506 (row sums).

Main diagonal gives A201511.

Sequence in context: A107492 A159257 A258997 * A256269 A256279 A363436

Adjacent sequences: A232830 A232831 A232832 * A232834 A232835 A232836

Keyword

nonn,tabf

Author

Heinrich Ludwig, Dec 01 2013

Extensions

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

Status

approved