cp's OEIS Frontend

A218663 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.

%I A218663 #16 Dec 05 2024 20:09:34
%S A218663 1,3,3,5,15,5,9,57,57,9,17,225,417,225,17,31,891,3249,3249,891,31,57,
%T A218663 3519,25533,50625,25533,3519,57,105,13905,199489,793881,793881,199489,
%U A218663 13905,105,193,54945,1560161,12383361,24879489,12383361,1560161,54945
%N A218663 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 A218663 From _Andrew Howroyd_, May 10 2017: (Start)
%C A218663 Number of n X k binary matrices with every 1 adjacent to some 0 horizontally, vertically, diagonally or antidiagonally.
%C A218663 Number of dominating sets in the n X k king graph. (End)
%H A218663 Stephan Mertens, <a href="/A218663/b218663.txt">Table of n, a(n) for n = 1..946</a> (first 240 terms from R. H. Hardin)
%H A218663 Stephan Mertens, <a href="https://arxiv.org/abs/2408.08053">Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph</a>, arXiv:2408.08053 [math.CO], Aug 2024.
%H A218663 Wikipedia, <a href="https://en.wikipedia.org/wiki/Dominating_set">Dominating set</a>
%F A218663 Empirical for column k:
%F A218663 k=1: a(n) = a(n-1) +a(n-2) +a(n-3)
%F A218663 k=2: a(n) = 3*a(n-1) +3*a(n-2) +3*a(n-3)
%F A218663 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 A218663 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 A218663 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 A218663 Table starts
%e A218663 ....1........3...........5...............9.................17
%e A218663 ....3.......15..........57.............225................891
%e A218663 ....5.......57.........417............3249..............25533
%e A218663 ....9......225........3249...........50625.............793881
%e A218663 ...17......891.......25533..........793881...........24879489
%e A218663 ...31.....3519......199489........12383361..........775176415
%e A218663 ...57....13905.....1560161.......193349025........24176619049
%e A218663 ..105....54945....12202673......3018953025.......754066017977
%e A218663 ..193...217107....95434773.....47135449449.....23517838102321
%e A218663 ..355...857871...746388537....735942652641....733484062428443
%e A218663 ..653..3389769..5837454753..11490533873361..22876204302519509
%e A218663 .1201.13394241.45654295713.179405691966081.713472099034206097
%e A218663 ...
%e A218663 Some solutions for n=3 k=4
%e A218663 ..1..1..1..0....1..0..1..1....0..1..0..1....0..1..1..0....1..0..0..0
%e A218663 ..0..1..0..0....0..0..0..0....1..0..0..1....0..0..1..1....0..0..1..1
%e A218663 ..0..1..0..1....1..1..0..1....0..1..1..1....1..1..0..1....1..1..0..0
%Y A218663 Columns 1-7 are A000213(n+1), A218657, A218658, A218659, A218660, A218661, A218662.
%Y A218663 Diagonal is A133791.
%Y A218663 Cf. A218354, A221446, A219078, A218426.
%K A218663 nonn,tabl
%O A218663 1,2
%A A218663 _R. H. Hardin_, Nov 04 2012