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.

%I A232833 #37 Aug 12 2025 03:45:05
%S A232833 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,
%T A232833 0,0,0,0,0,0,0,1,25,260,1474,5024,10741,14650,12798,7157,2578,618,106,
%U A232833 14,1,0,0,0,0,0,0,0,0,0,0,0,0,1,36,570,5248,31320,127960,368868
%N 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.
%C A232833 Also number of ways to place k non-attacking wazirs on an n X n board.
%C A232833 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).
%C A232833 If only non-equivalent (mod D_4) matrices are counted, the corresponding numbers are given by A232569.
%C A232833 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
%H A232833 Alois P. Heinz, <a href="/A232833/b232833.txt">Rows n = 0..17, flattened</a> (first 8.5 rows from Heinrich Ludwig)
%H A232833 R. J. Mathar, <a href="https://vixra.org/abs/2404.0122">Bivariate generating functions for non-attacking Wazirs on rectangular boards</a>, viXra:2404.0122 (2024) page 14
%H A232833 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>
%H A232833 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IndependencePolynomial.html">Independence Polynomial</a>
%F A232833 T(n,0) = A000012(n);
%F A232833 T(n,1) = A000290(n), n >= 1;
%F A232833 T(n,2) = A172225(n), n >= 2;
%F A232833 T(n,3) = A172226(n), n >= 2;
%F A232833 T(n,4) = A172227(n), n >= 2;
%F A232833 T(n,5) = A172228(n), n >= 3;
%F A232833 T(n,6) = A178409(n), n >= 3;
%F A232833 T(n,7) = A201507(n), n >= 3;
%F A232833 T(n,8) = A201508(n), n >= 3;
%F A232833 T(n,9) = A201510(n), n >= 3;
%e A232833 Triangle begins:
%e A232833   1;
%e A232833   1,  1;
%e A232833   1,  4,  2,   0,   0;
%e A232833   1,  9, 24,  22,   6,   1,   0,  0, 0, 0;
%e A232833   1, 16, 96, 276, 405, 304, 114, 20, 2, 0, 0, 0, 0, 0, 0, 0, 0;
%e A232833   ...
%p A232833 b:= proc(n, l) option remember; local k;
%p A232833       if n=0 then 1
%p A232833     elif min(l)>0 then b(n-1, map(x-> x-1, l))
%p A232833     else for k while l[k]>0 do od;
%p A232833          b(n, subsop(k=1, l))+expand(x*`if`(n>0, `if`(k<nops(l),
%p A232833          b(n, subsop(k=2, k+1=1, l)), b(n, subsop(k=2, l))), 0))
%p A232833       fi
%p A232833     end:
%p A232833 T:= n-> (p-> seq(coeff(p,x,i), i=0..n^2))(b(n, [0$n])):
%p A232833 seq(T(n), n=0..6);  # _Alois P. Heinz_, Apr 16 2024
%t A232833 b[n_, l_] := b[n, l] = Module[{k},
%t A232833    Which[n == 0, 1,
%t A232833    Min[l] > 0, b[n - 1, l - 1],
%t A232833    True, For[k = 1, l[[k]] > 0, k++];
%t A232833       b[n, ReplacePart[l, k -> 1]] + Expand[x*If[n > 0, If[k < Length[l],
%t A232833       b[n, ReplacePart[l, {k -> 2, k + 1 -> 1}]],
%t A232833       b[n, ReplacePart[l, k -> 2]], 0]]]]];
%t A232833 T[n_] := With[{p = b[n, Table[0, {n}]]}, Table[Coefficient[p, x, i], {i, 0, n^2}]]
%t A232833 Table[T[n], {n, 0, 6}] // Flatten (* _Jean-François Alcover_, Aug 09 2024, after _Alois P. Heinz_ *)
%Y A232833 Cf. A232569, A006506 (row sums).
%Y A232833 Main diagonal gives A201511.
%K A232833 nonn,tabf
%O A232833 0,5
%A A232833 _Heinrich Ludwig_, Dec 01 2013
%E A232833 T(0,0)=1 inserted by _Alois P. Heinz_, Apr 16 2024