A140304 Number of n X n binary matrices with no more than one 1 in any 3 X 3 sub-block.

1, 2, 5, 10, 60, 437, 2875, 36409, 704468, 14783959, 461938624, 22488554884, 1378748967395, 115759328877461, 14408020654986447, 2435526103569141336, 559083220302137929773, 182904062593977747117174, 83283166161035345074485948, 52012981990902321891650583747, 45449967513840995133445585972949

Offset: 0

Author

R. H. Hardin, May 27 2008

Keywords

• nonn

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..23
• R. J. Mathar, Tiling n X m rectangles with 1 X 1 and s X s squares, arXiv:1609.03964 [math.CO], 2016.

Crossrefs

Cf. A139810. Row sums of A276171.

Programs

Mathematica

$RecursionLimit = 10^4;
b[n_, l_] := b[n, l] = Module[{k, m}, m = Min[l]; Which[n < 3, 1, m > 0, b[n - m, l - m], True, k = 1; While[l[[k]] > 0, k++]; b[n, ReplacePart[l, k -> 1]] + Expand[If[k + 1 < Length[l] && l[[k + 1 ;; k + 2]] == {0, 0}, b[n, ReplacePart[l, {k -> 3, k + 1 -> 3, k + 2 -> 3}]]*x, 0]]]];
a[n_] := a[n] = Function[p, Sum[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n + 2, Table[0, n + 2]]];
Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 0, 15}] (* Jean-François Alcover, Nov 11 2017, after Alois P. Heinz *)