login
A197054
T(n,k)=Number of nXk 0..4 arrays with each element equal to the number of its horizontal and vertical zero neighbors.
15
1, 2, 2, 2, 2, 2, 3, 4, 4, 3, 4, 6, 10, 6, 4, 5, 10, 18, 18, 10, 5, 7, 16, 38, 42, 38, 16, 7, 9, 26, 78, 108, 108, 78, 26, 9, 12, 42, 156, 274, 358, 274, 156, 42, 12, 16, 68, 320, 692, 1132, 1132, 692, 320, 68, 16, 21, 110, 654, 1754, 3580, 4468, 3580, 1754, 654, 110, 21, 28
OFFSET
1,2
COMMENTS
Every 0 is next to 0 0's, every 1 is next to 1 0's, every 2 is next to 2 0's, every 3 is next to 3 0's, every 4 is next to 4 0's
Also, the number of maximal independent vertex sets in the grid graph P_n X P_k. - Andrew Howroyd, May 16 2017
LINKS
Oh, Seungsang. "Maximal independent sets on a grid graph." Discrete Mathematics 340.12 (2017): 2762-2768. Also arXiv:1709.03678.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
EXAMPLE
Table starts
..1...2....2.....3......4.......5........7.........9.........12..........16
..2...2....4.....6.....10......16.......26........42.........68.........110
..2...4...10....18.....38......78......156.......320........654........1326
..3...6...18....42....108.....274......692......1754.......4442.......11248
..4..10...38...108....358....1132.....3580.....11382......36270......114992
..5..16...78...274...1132....4468....17742.....70616.....281202.....1117442
..7..26..156...692...3580...17742....88056....439338....2192602....10912392
..9..42..320..1754..11382...70616...439338...2745186...17155374...106972582
.12..68..654..4442..36270..281202..2192602..17155374..134355866..1049189170
.16.110.1326.11248.114992.1117442.10912392.106972582.1049189170.10264692132
...
Some solutions for n=6 k=4
..0..2..1..0....0..2..0..1....2..0..2..0....0..3..0..2....0..2..1..0
..2..0..1..2....1..1..1..1....0..2..1..1....2..0..4..0....3..0..1..2
..1..1..2..0....1..0..2..0....2..1..0..2....1..2..0..2....0..3..1..0
..0..3..0..3....1..1..1..1....0..2..2..0....0..1..1..1....2..0..1..2
..3..0..4..0....0..3..0..2....3..0..1..2....1..1..1..0....1..1..2..0
..0..3..0..2....2..0..3..0....0..2..1..0....1..0..1..1....0..2..0..2
CROSSREFS
Column 1 is A000931(n+6).
Column 2 is A006355(n+1).
Columns 3-7 are A197049, A197050, A197051, A197052, A197053.
Main diagonal is A197048.
Cf. A089934 (independent sets), A218354 (dominating sets).
Sequence in context: A143594 A298949 A329097 * A337926 A120502 A099480
KEYWORD
nonn,tabl
AUTHOR
R. H. Hardin, Oct 09 2011
STATUS
approved