cp's OEIS Frontend

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

%I A218354 #19 Feb 16 2025 08:33:18
%S A218354 1,3,3,5,11,5,9,41,41,9,17,149,291,149,17,31,547,2069,2069,547,31,57,
%T A218354 2007,14811,28661,14811,2007,57,105,7361,105913,401253,401253,105913,
%U A218354 7361,105,193,27001,757305,5609569,10982565,5609569,757305,27001,193,355
%N A218354 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 A218354 From _Andrew Howroyd_, May 10 2017: (Start)
%C A218354 Number of n X k binary matrices with every 1 vertically or horizontally adjacent to some 0.
%C A218354 Number of dominating sets in the grid graph P_n X P_k. (End)
%H A218354 Stephan Mertens, <a href="/A218354/b218354.txt">Table of n, a(n) for n = 1..946</a> (first 198 terms from R. H. Hardin)
%H A218354 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 A218354 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>
%H A218354 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DominatingSet.html">Dominating Set</a>
%H A218354 Wikipedia, <a href="https://en.wikipedia.org/wiki/Dominating_set">Dominating Set</a>
%F A218354 Empirical for column k:
%F A218354 k=1: a(n) = a(n-1) +a(n-2) +a(n-3).
%F A218354 k=2: a(n) = 3*a(n-1) +2*a(n-2) +2*a(n-3) -a(n-4) -a(n-5).
%F A218354 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 A218354 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 A218354 Table starts
%e A218354 ....1.......3...........5..............9.................17
%e A218354 ....3......11..........41............149................547
%e A218354 ....5......41.........291...........2069..............14811
%e A218354 ....9.....149........2069..........28661.............401253
%e A218354 ...17.....547.......14811.........401253...........10982565
%e A218354 ...31....2007......105913........5609569..........300126903
%e A218354 ...57....7361......757305.......78394141.........8199377227
%e A218354 ..105...27001.....5415209.....1095695529.......224032447213
%e A218354 ..193...99043....38722037....15314367301......6121258910011
%e A218354 ..355..363299...276885777...214044940145....167250519310183
%e A218354 ..653.1332617..1979899795..2991651891557...4569773233045519
%e A218354 .1201.4888173.14157473937.41813576818545.124859601874166153
%e A218354 ...
%e A218354 Some solutions for n=3 k=4
%e A218354 ..1..0..1..1....1..1..1..0....1..1..1..0....1..0..1..1....1..0..1..1
%e A218354 ..1..0..1..0....1..0..1..0....0..0..1..0....1..0..1..1....1..1..0..1
%e A218354 ..0..0..1..0....1..1..0..1....0..1..1..1....1..1..1..1....1..1..1..0
%Y A218354 Columns 1-7 are A000213(n+1), A218348, A218349, A218350, A218351, A218352, A218353.
%Y A218354 Diagonal is A133515.
%Y A218354 Cf. A089934 (independent vertex sets), A210662 (matchings).
%K A218354 nonn,tabl
%O A218354 1,2
%A A218354 _R. H. Hardin_, Oct 26 2012