login
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.
13
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
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
Cf. A232569, A006506 (row sums).
Main diagonal gives A201511.
Sequence in context: A107492 A159257 A258997 * A256269 A256279 A363436
KEYWORD
nonn,tabf
AUTHOR
Heinrich Ludwig, Dec 01 2013
EXTENSIONS
T(0,0)=1 inserted by Alois P. Heinz, Apr 16 2024
STATUS
approved