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.

1, 3, 3, 5, 11, 5, 9, 41, 41, 9, 17, 149, 291, 149, 17, 31, 547, 2069, 2069, 547, 31, 57, 2007, 14811, 28661, 14811, 2007, 57, 105, 7361, 105913, 401253, 401253, 105913, 7361, 105, 193, 27001, 757305, 5609569, 10982565, 5609569, 757305, 27001, 193, 355

Offset: 1

Author

R. H. Hardin, Oct 26 2012

Keywords

• nonn
• tabl

Comments

From Andrew Howroyd, May 10 2017: (Start)

Number of n X k binary matrices with every 1 vertically or horizontally adjacent to some 0.

Number of dominating sets in the grid graph P_n X P_k. (End)

Examples

			Table starts
....1.......3...........5..............9.................17
....3......11..........41............149................547
....5......41.........291...........2069..............14811
....9.....149........2069..........28661.............401253
...17.....547.......14811.........401253...........10982565
...31....2007......105913........5609569..........300126903
...57....7361......757305.......78394141.........8199377227
..105...27001.....5415209.....1095695529.......224032447213
..193...99043....38722037....15314367301......6121258910011
..355..363299...276885777...214044940145....167250519310183
..653.1332617..1979899795..2991651891557...4569773233045519
.1201.4888173.14157473937.41813576818545.124859601874166153
...
Some solutions for n=3 k=4
..1..0..1..1....1..1..1..0....1..1..1..0....1..0..1..1....1..0..1..1
..1..0..1..0....1..0..1..0....0..0..1..0....1..0..1..1....1..1..0..1
..0..0..1..0....1..1..0..1....0..1..1..1....1..1..1..1....1..1..1..0
		

Links

• Stephan Mertens, Table of n, a(n) for n = 1..946 (first 198 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.
• Eric Weisstein's World of Mathematics, Grid Graph
• Eric Weisstein's World of Mathematics, Dominating Set
• Wikipedia, Dominating Set

Crossrefs

Columns 1-7 are A000213(n+1), A218348, A218349, A218350, A218351, A218352, A218353.

Diagonal is A133515.

Cf. A089934 (independent vertex sets), A210662 (matchings).

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) +2*a(n-2) +2*a(n-3) -a(n-4) -a(n-5).

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

Column k=1 for an underlying 0..z array: a(n) = sum(i=1..2z+1){a(n-i)} z=1,2,3,4