login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 16
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,2

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)

LINKS

R. H. Hardin, Table of n, a(n) for n = 1..198

Wikipedia, Dominating Set

Eric Weisstein's World of Mathematics, Grid Graph

Eric Weisstein's World of Mathematics, Dominating Set

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

EXAMPLE

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

CROSSREFS

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

Diagonal is A133515.

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

Sequence in context: A326175 A072337 A132751 * A286514 A235859 A279790

Adjacent sequences:  A218351 A218352 A218353 * A218355 A218356 A218357

KEYWORD

nonn,tabl

AUTHOR

R. H. Hardin Oct 26 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 17 18:08 EST 2020. Contains 330987 sequences. (Running on oeis4.)