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
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
MATHEMATICA
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 *)
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Heinrich Ludwig, Dec 01 2013
EXTENSIONS
T(0,0)=1 inserted by Alois P. Heinz, Apr 16 2024
STATUS
approved