|
%I #10 May 10 2017 21:36:07
%S 1,3,3,5,15,5,9,57,57,9,17,225,417,225,17,31,891,3249,3249,891,31,57,
%T 3519,25533,50625,25533,3519,57,105,13905,199489,793881,793881,199489,
%U 13905,105,193,54945,1560161,12383361,24879489,12383361,1560161,54945
%N T(n,k) = Hilltop maps: number of n X k binary arrays indicating the locations of corresponding elements not exceeded by any king-move neighbor in a random 0..1 n X k array.
%C From _Andrew Howroyd_, May 10 201: (Start)
%C Number of n X k binary matrices with every 1 adjacent to some 0 horizontally, vertically, diagonally or antidiagonally.
%C Number of dominating sets in the n X k king graph. (End)
%H R. H. Hardin, <a href="/A218663/b218663.txt">Table of n, a(n) for n = 1..240</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Dominating_set">Dominating set</a>
%F Empirical for column k:
%F k=1: a(n) = a(n-1) +a(n-2) +a(n-3)
%F k=2: a(n) = 3*a(n-1) +3*a(n-2) +3*a(n-3)
%F k=3: a(n) = 6*a(n-1) +11*a(n-2) +26*a(n-3) -5*a(n-4) -5*a(n-6)
%F k=4: a(n) = 12*a(n-1) +45*a(n-2) +180*a(n-3) -27*a(n-4) -81*a(n-6)
%F 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.
%e Table starts
%e ....1........3...........5...............9.................17
%e ....3.......15..........57.............225................891
%e ....5.......57.........417............3249..............25533
%e ....9......225........3249...........50625.............793881
%e ...17......891.......25533..........793881...........24879489
%e ...31.....3519......199489........12383361..........775176415
%e ...57....13905.....1560161.......193349025........24176619049
%e ..105....54945....12202673......3018953025.......754066017977
%e ..193...217107....95434773.....47135449449.....23517838102321
%e ..355...857871...746388537....735942652641....733484062428443
%e ..653..3389769..5837454753..11490533873361..22876204302519509
%e .1201.13394241.45654295713.179405691966081.713472099034206097
%e ...
%e Some solutions for n=3 k=4
%e ..1..1..1..0....1..0..1..1....0..1..0..1....0..1..1..0....1..0..0..0
%e ..0..1..0..0....0..0..0..0....1..0..0..1....0..0..1..1....0..0..1..1
%e ..0..1..0..1....1..1..0..1....0..1..1..1....1..1..0..1....1..1..0..0
%Y Columns 1-7 are A000213(n+1), A218657, A218658, A218659, A218660, A218661, A218662.
%Y Diagonal is A133791.
%Y Cf. A218354, A221446, A219078, A218426.
%K nonn,tabl
%O 1,2
%A _R. H. Hardin_, Nov 04 2012
| 