|
%I #14 Jul 18 2020 05:54:57
%S 1,3,3,5,11,5,9,41,41,9,17,149,291,149,17,31,547,2069,2069,547,31,57,
%T 2007,14811,28661,14811,2007,57,105,7361,105913,401253,401253,105913,
%U 7361,105,193,27001,757305,5609569,10982565,5609569,757305,27001,193,355
%N T(n,k) = Hilltop maps: number of nXk binary arrays indicating the locations of corresponding elements not exceeded by any horizontal or vertical neighbor in a random 0..1 n X k array.
%C From _Andrew Howroyd_, May 10 2017: (Start)
%C Number of n X k binary matrices with every 1 vertically or horizontally adjacent to some 0.
%C Number of dominating sets in the grid graph P_n X P_k. (End)
%H R. H. Hardin, <a href="/A218354/b218354.txt">Table of n, a(n) for n = 1..198</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DominatingSet.html">Dominating Set</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) +2*a(n-2) +2*a(n-3) -a(n-4) -a(n-5).
%F k=3: a(n) = 6*a(n-1) +5*a(n-2) +22*a(n-3) +7*a(n-4) +8*a(n-5) -18*a(n-6) -20*a(n-7) -a(n-8) +4*a(n-9) +3*a(n-10) +a(n-12).
%F Column k=1 for an underlying 0..z array: a(n) = sum(i=1..2z+1){a(n-i)} z=1,2,3,4
%e Table starts
%e ....1.......3...........5..............9.................17
%e ....3......11..........41............149................547
%e ....5......41.........291...........2069..............14811
%e ....9.....149........2069..........28661.............401253
%e ...17.....547.......14811.........401253...........10982565
%e ...31....2007......105913........5609569..........300126903
%e ...57....7361......757305.......78394141.........8199377227
%e ..105...27001.....5415209.....1095695529.......224032447213
%e ..193...99043....38722037....15314367301......6121258910011
%e ..355..363299...276885777...214044940145....167250519310183
%e ..653.1332617..1979899795..2991651891557...4569773233045519
%e .1201.4888173.14157473937.41813576818545.124859601874166153
%e ...
%e Some solutions for n=3 k=4
%e ..1..0..1..1....1..1..1..0....1..1..1..0....1..0..1..1....1..0..1..1
%e ..1..0..1..0....1..0..1..0....0..0..1..0....1..0..1..1....1..1..0..1
%e ..0..0..1..0....1..1..0..1....0..1..1..1....1..1..1..1....1..1..1..0
%Y Columns 1-7 are A000213(n+1), A218348, A218349, A218350, A218351, A218352, A218353.
%Y Diagonal is A133515.
%Y Cf. A089934 (independent vertex sets), A210662 (matchings).
%K nonn,tabl
%O 1,2
%A _R. H. Hardin_, Oct 26 2012
| 