OFFSET
1,2
COMMENTS
From Andrew Howroyd, May 10 201: (Start)
Number of n X k binary matrices with every 1 adjacent to some 0 horizontally, vertically, diagonally or antidiagonally.
Number of dominating sets in the n X k king graph. (End)
LINKS
Stephan Mertens, Table of n, a(n) for n = 1..946 (first 240 terms from R. H. Hardin)
Stephan Mertens, Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph, arXiv:2408.08053 [math.CO], Aug 2024.
Wikipedia, Dominating set
FORMULA
Empirical for column k:
k=1: a(n) = a(n-1) +a(n-2) +a(n-3)
k=2: a(n) = 3*a(n-1) +3*a(n-2) +3*a(n-3)
k=3: a(n) = 6*a(n-1) +11*a(n-2) +26*a(n-3) -5*a(n-4) -5*a(n-6)
k=4: a(n) = 12*a(n-1) +45*a(n-2) +180*a(n-3) -27*a(n-4) -81*a(n-6)
Columns k=1..z+1 for an underlying 0..z array: a(n) = sum(i=1..2z+1){(2^k-1)*a(n-i)} checked for z=1..3.
EXAMPLE
Table starts
....1........3...........5...............9.................17
....3.......15..........57.............225................891
....5.......57.........417............3249..............25533
....9......225........3249...........50625.............793881
...17......891.......25533..........793881...........24879489
...31.....3519......199489........12383361..........775176415
...57....13905.....1560161.......193349025........24176619049
..105....54945....12202673......3018953025.......754066017977
..193...217107....95434773.....47135449449.....23517838102321
..355...857871...746388537....735942652641....733484062428443
..653..3389769..5837454753..11490533873361..22876204302519509
.1201.13394241.45654295713.179405691966081.713472099034206097
...
Some solutions for n=3 k=4
..1..1..1..0....1..0..1..1....0..1..0..1....0..1..1..0....1..0..0..0
..0..1..0..0....0..0..0..0....1..0..0..1....0..0..1..1....0..0..1..1
..0..1..0..1....1..1..0..1....0..1..1..1....1..1..0..1....1..1..0..0
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
R. H. Hardin, Nov 04 2012
STATUS
approved