A089934 -id:A089934 - cp's OEIS frontend

A089936 Number of 5 X n matrices with entries {0,1} without adjacent 0's in any row or column. 5th row of A089934.

13, 99, 827, 6743, 55447, 454385, 3729091, 30584687, 250916131, 2058249165, 16884649135, 138508056265, 1136221529549, 9320704799431, 76460212316453, 627222736888811, 5145271430670385, 42207992410219447, 346243111960194009

Offset: 1

Marc LeBrun, Nov 15 2003

nonn

Row/columns 1 through 7 are A000045, A001333, A051736, A051737, A089936, A089937, A089938.

Number of independent vertex sets in the grid graph P_5 X P_n. - Andrew Howroyd, Jun 06 2017

Andrew Howroyd, Table of n, a(n) for n = 1..200
Reinhardt Euler, The Fibonacci Number of a Grid Graph and a New Class of Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.6.

Row 5 of A089934.

Cf. A000045, A001333, A051736, A051737, A089935, A089937, A089938.

G.f.: x*(13 + 47*x - 37*x^2 - 129*x^3 + 68*x^4 + 49*x^5 - 23*x^6 - 3*x^7 + x^8) / (1 - 4*x - 36*x^2 + 105*x^4 - 15*x^5 - 64*x^6 + 20*x^7 + 4*x^8 - x^9) (conjectured). - Colin Barker, Jun 06 2017

The above conjecture is correct since the order of the recurrence is A089935(5) = 9. - Andrew Howroyd, Dec 24 2019

A089937 Number of 6 X n matrices with entries {0,1} without adjacent 0's in any row or column. 6th row of A089934.

Original entry on oeis.org

21, 239, 2999, 36787, 454385, 5598861, 69050253, 851302029, 10496827403, 129422885699, 1595777230271, 19675706193157, 242599324206721, 2991220223776445, 36881397137844409, 454743263319217787, 5606930966068061311, 69132797971282998447

Offset: 1

Marc LeBrun, Nov 15 2003

nonn

Row/columns 1 through 7 are A000045, A001333, A051736, A051737, A089936, A089937, A089938.

Number of independent vertex sets in the grid graph P_6 X P_n. - Andrew Howroyd, Jun 06 2017

Andrew Howroyd, Table of n, a(n) for n = 1..200

Row 6 of A089934.

Cf. A000045, A001333, A051736, A051737, A089935, A089936, A089938.

G.f.: x*(21 + 71*x - 215*x^2 - 385*x^3 + 668*x^4 + 234*x^5 - 400*x^6 + 9*x^7 + 49*x^8 - 3*x^9 - x^10) / (1 - 8*x - 62*x^2 + 78*x^3 + 375*x^4 - 300*x^5 - 486*x^6 + 385*x^7 + 30*x^8 - 52*x^9 + 2*x^10 + x^11) (conjectured). - Colin Barker, Jun 06 2017

The above conjecture is correct because the order of the recurrence is A089935(6) = 11. - Andrew Howroyd, Dec 24 2019

Terms a(17) and beyond from Andrew Howroyd, Jun 06 2017

A089938 Number of 7 X n matrices with entries {0,1} without adjacent 0's in any row or column. 7th row of A089934.

Original entry on oeis.org

34, 577, 10897, 200798, 3729091, 69050253, 1280128950, 23720149995, 439621976195, 8147000813446, 150985649174085, 2798109826697003, 51855860689753372, 961012671564107667, 17809889025037476097, 330060028036299469334, 6116807668464485142495

Offset: 1

Marc LeBrun, Nov 15 2003

nonn

Row/columns 1 through 7 are A000045, A001333, A051736, A051737, A089936, A089937, A089938.

Number of independent vertex sets in the grid graph P_7 X P_n. - Andrew Howroyd, Jun 06 2017

Andrew Howroyd, Table of n, a(n) for n = 1..200

Cf. A000045, A001333, A051736, A051737, A089936, A089937, A089934.

O.g.f.: - (X - 1)*(X^19 + 10*X^18 - 58*X^17 - 576*X^16 + 651*X^15 + 8054*X^14 - 5381*X^13 - 42910*X^12 + 32530*X^11 + 90357*X^10 - 90813*X^9 - 52366*X^8 + 79558*X^7 - 8263*X^6 - 13918*X^5 + 2501*X^4 + 894*X^3 - 94*X^2 - 26*X - 1)/(X^21 + 9*X^20 - 87*X^19 - 546*X^18 + 2227*X^17 + 9369*X^16 - 25564*X^15 - 54187*X^14 + 139011*X^13 + 100779*X^12 - 340142*X^11 + 21372*X^10 + 308107*X^9 - 127405*X^8 - 82823*X^7 + 48558*X^6 + 6975*X^5 - 5659*X^4 - 210*X^3 + 203*X^2 + 9*X - 1)

Terms a(16) and beyond from Andrew Howroyd, Jun 06 2017

A089935 a(n) = order of recurrence generating row (or column) n of A089934.

Original entry on oeis.org

2, 2, 4, 5, 9, 11, 21, 30, 51, 76, 127, 195, 322, 504, 826

Offset: 1

Marc LeBrun, Nov 15 2003

The only known value where a(n) is strictly less than the theoretical upper bound A001224(n+1) is a(6) = 11. - Andrew Howroyd, Dec 24 2019

			a(2)=2 because the recurrence relation for the second row/column is a(n) = 2 a(n-1) + a(n-2).

Row/columns 1 through 7 of A089934 are A000045, A001333, A051736, A051737, A089936, A089937, A089938.

Cf. A001224.

a(n) <= A001224(n+1). - Andrew Howroyd, Dec 24 2019

a(8)-a(10) from Andrew Howroyd, Dec 24 2019

a(11)-a(15) from Max Alekseyev, Dec 12 2024

A006506 Number of n X n binary matrices with no 2 adjacent 1's, or number of configurations of non-attacking princes on an n X n board, where a "prince" attacks the four adjacent (non-diagonal) squares. Also number of independent vertex sets in an n X n grid.

Original entry on oeis.org

1, 2, 7, 63, 1234, 55447, 5598861, 1280128950, 660647962955, 770548397261707, 2030049051145980050, 12083401651433651945979, 162481813349792588536582997, 4935961285224791538367780371090, 338752110195939290445247645371206783, 52521741712869136440040654451875316861275

Offset: 0

N. J. A. Sloane, R. H. Hardin, Paul Zimmermann

A two-dimensional generalization of the Fibonacci numbers.
Also the number of vertex covers in the n X n grid graph P_n X P_n.
A181030 (Number of n X n binary matrices with no leading bitstring in any row or column divisible by 4) is the same sequence. Proof from Steve Butler, Jan 26 2015: This is trivially true. A181030 is equivalent to this sequence by interchanging the roles of 0 and 1. In particular, A181030 looks for binary matrices with no leading bitstring divisible by 4, but a bitstring is divisible by 4 if and only if its last two digits is 0; in a binary matrix this can only be avoided if there are no two adjacent 0's (i.e., for any two adjacent 0's take the bitstring starting in that row or column and we are done); the present sequence looks for no two adjacent 1's. Similar reasons show that the array A181031 is equivalent to the array A089980.
Let R(n) be the set of squares that have vertices at integer coordinates and lie in the region of the plane |x|+|y| <= n+1, and let S(n) be the set of squares that have vertices at integer coordinates and lie in the region of the plane |x|+|y-1/2| <= n+2.  Further let T be the collection of rectangular tiles with dimensions i X 1 or 1 X i with i arbitrary.  Then a(2n) is the number of ways to tile R(n) using tiles from T and a(2n+1) is the number of ways to tile S(n) using tiles from T. (Note R(n) is the Aztec diamond of order n.) - Steve Butler, Jan 26 2015

Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 342-349.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Jin-Guo Liu, Table of n, a(n) for n = 0..39 (terms 1..33 from Robert Gerbicz, 34..35 from P. Butera and M. Pernici, 37..38 from Casey Mills Davis)
P. Butera and M. Pernici, Sums of permanental minors using Grassmann algebra, arXiv preprint arXiv:1406.5337 [hep-lat], 2014.
Casey Mills Davis, C++ program used to generate a(n) for n = 36..37
Steven R. Finch, Hard Square Entropy Constant [Broken link]
Steven R. Finch, Hard Square Entropy Constant [From the Wayback machine]
Xuanzhao Gao, Xiaofeng Li, and Jinguo Liu, Programming guide for solving constraint satisfaction problems with tensor networks, arXiv:2501.00227 [physics.comp-ph], 2024. See p. 24.
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p.372.
Jin-Guo Liu, Xun Gao, Madelyn Cain, Mikhail D. Lukin and Sheng-Tao Wang, Computing solution space properties of combinatorial optimization problems via generic tensor networks, arXiv:2205.03718 [cond-mat.stat-mech], 2022. Terms 38..39.
I. Mezo, Periodicity of the Last Digits of Some Combinatorial Sequences, J. Int. Seq. 17 (2014) #14.1.1.
B. D. Stosic, T. Stosic, I. P. Fittipaldi and J. J. P. Veerman, Residual entropy of the square Ising antiferromagnet in the maximum critical field: the Fibonacci matrix, Journal of Physics A: Mathematical and General, Volume 30, Number 10, 1997, pp. L331-L337.
Peter Tittmann, Enumeration in Graphs
Eric Weisstein's World of Mathematics, (0,1)-Matrix
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Hard Square Entropy Constant
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Vertex Cover
Index entries for sequences related to binary matrices

Cf. A027683 for toroidal version.
Table of values for n x m matrices: A089934.
Cf. A232833 for refinement by number of 1's.
Cf. also A191779.
Cf. A201511, A212270.

A006506 := proc(N) local i,j,p,q; p := 1+x11;
if n=0 then return 1 fi;
for i from 2 to N do
   q := p-select(has,p,x||(i-1)||1);
   p := p+expand(q*x||i||1)
od;
for j from 2 to N do
   q := p-select(has,p,x1||(j-1));
   p := subs(x1||(j-1)=1,p)+expand(q*x1||j);
   for i from 2 to N do
      q := p-select(has,p,{x||(i-1)||j,x||i||(j-1)});
      p := subs(x||i||(j-1)=1,p)+expand(q*x||i||j);
   od
od;
map(icontent,p)
end:
seq(A006506(n), n=0..15);

a[n_] := a[n] = (p = 1 + x[1, 1]; Do[q = p - Select[p, ! FreeQ[#, x[i-1, 1]] &]; p = p + Expand[q*x[i, 1]], {i, 2, n}]; Do[q = p - Select[p, ! FreeQ[#, x[1, j-1]] &]; p = (p /. x[i, j-1] :> 1) + Expand[q*x[1, j]]; Do[q = p - Select[ p, ! FreeQ[#, x[i-1, j]] || ! FreeQ[#, x[i, j-1]] &]; p = (p /. x[i, j-1] :> 1) + Expand[q*x[i, j]], {i, 2, n}], {j, 2, n}]; p /. x[, ] -> 1); a /@ Range[14] (* Jean-François Alcover, May 25 2011, after Maple prog. *)
Table[With[{g = GridGraph[{n, n}]}, Count[Subsets[Range[n^2], Length @ First @ FindIndependentVertexSet[g]], ?(IndependentVertexSetQ[g, #] &)]], {n, 5}] (* _Eric W. Weisstein, May 28 2017 *)

a(n)=L=fibonacci(n+2);p=v=vector(L,i,1);c=0; for(i=0,2^n-1,j=i;while(j&&j%4<3,j\=2);if(j%4<3,p[c++]=i)); for(i=2,n,w=vector(L,j,0); for(j=1,L, for(k=1,L,if(bitand(p[j],p[k])==0,w[j]+=v[k])));v=w); sum(i=1,L,v[i]) \\ Robert Gerbicz, Jun 17 2011

Limit_{n->oo} a(n)^(1/n^2) = c1 = 1.50304... is the hard square entropy constant A085850. - Benoit Cloitre, Nov 16 2003
a(n) appears to behave like A * c3^n * c1^(n^2) where c1 is as above, c3 = 1.143519129587 approximately, A = 1.0660826 approximately. This is based on numerical analysis of a(n) for n up to 19. - Brendan McKay, Nov 16 2003
From n up to 39 we have A = 1.06608266035... - Vaclav Kotesovec, Jan 29 2024

Sequence extended by Paul Zimmermann, Mar 15 1996
Maple program updated and sequence extended by Robert Israel, Jun 16 2011
a(0)=1 prepended by Alois P. Heinz, Jan 29 2024

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.

Original entry on oeis.org

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

R. H. Hardin, Oct 26 2012

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)

			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

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

Columns 1-7 are A000213(n+1), A218348, A218349, A218350, A218351, A218352, A218353.
Diagonal is A133515.
Cf. A089934 (independent vertex sets), A210662 (matchings).

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

A197054 T(n,k)=Number of nXk 0..4 arrays with each element equal to the number of its horizontal and vertical zero neighbors.

Original entry on oeis.org

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

R. H. Hardin, Oct 09 2011

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

			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

R. H. Hardin, Table of n, a(n) for n = 1..364
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

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

A286513 Array read by antidiagonals: T(m,n) is the number of independent sets in the stacked prism graph C_m X P_n.

Original entry on oeis.org

1, 1, 3, 1, 7, 4, 1, 17, 13, 7, 1, 41, 43, 35, 11, 1, 99, 142, 181, 81, 18, 1, 239, 469, 933, 621, 199, 29, 1, 577, 1549, 4811, 4741, 2309, 477, 47, 1, 1393, 5116, 24807, 36211, 26660, 8303, 1155, 76, 1, 3363, 16897, 127913, 276561, 307983, 143697, 30277, 2785, 123

Offset: 1

Andrew Howroyd, May 10 2017

Equivalently, the number of vertex covers in the stacked prism graph C_m X P_n.

			Table starts:
=============================================================
m\n|   1    2     3      4        5         6           7
---|---------------------------------------------------------
1  |   1    1     1      1        1         1           1 ...
2  |   3    7    17     41       99       239         577 ...
3  |   4   13    43    142      469      1549        5116 ...
4  |   7   35   181    933     4811     24807      127913 ...
5  |  11   81   621   4741    36211    276561     2112241 ...
6  |  18  199  2309  26660   307983   3557711    41097664 ...
7  |  29  477  8303 143697  2488431  43089985   746156517 ...
8  |  47 1155 30277 788453 20546803 535404487 13951571713 ...
...

Liang Kai, Table of n, a(n) for n = 1..704 (terms up to a(435) from Andrew Howroyd)
Kai Liang, Independent Set Enumeration and Estimation of Related Constants of Grid Graphs, arXiv:2507.04007 [math.CO], 2025. See p. 13.
Eric Weisstein's World of Mathematics, Independent Vertex Set.
Eric Weisstein's World of Mathematics, Stacked Prism Graph.
Wikipedia, Independent set.

Rows 3..8 are A003688(n+1), A051926, A181989, A181961, A182014, A182019.
Columns 1..4 are A000032, A051927, A050400, A050401.
Main diagonal is A212270.
Cf. A089934 (P_m X P_n), A027683, A286514.

A051736 Number of 3 X n (0,1)-matrices with no consecutive 1's in any row or column.

Original entry on oeis.org

1, 5, 17, 63, 227, 827, 2999, 10897, 39561, 143677, 521721, 1894607, 6879979, 24983923, 90725999, 329460929, 1196397873, 4344577397, 15776816033, 57291635519, 208047769363, 755500774443, 2743511349031, 9962735709201, 36178491743225, 131377896967213, 477083233044745

Offset: 0

Stephen G Penrice, Dec 06 1999

Also the number of independent vertex sets and vertex covers in the 3 X n grid graph. - Eric W. Weisstein, Sep 21 2017

			There are five 3 X 1 (0,1)-matrices with no consecutive 1's:
  0 0 0
  0 0 1
  0 1 0
  1 0 0
  1 0 1
There are 17 3 X 2 (0,1)-matrices with no consecutive 1's:
0 0, 0 1, 0 0, 0 0, 0 1, 1 0, 1 0, 1 0, 0 0, 0 1, 0 0, 0 1, 0 0, 0 1, 0 0, 1 0, 1 0
0 0, 0 0, 0 1, 0 0, 0 0, 0 0, 0 1, 0 0, 1 0, 1 0, 1 0, 1 0, 0 0, 0 0, 0 1, 0 0, 0 1
0 0, 0 0, 0 0, 0 1, 0 1, 0 0, 0 0, 0 1, 0 0, 0 0, 0 1, 0 1, 1 0, 1 0, 1 0, 1 0, 1 0

Reinhard Zumkeller, Table of n, a(n) for n = 0..999
N. J. Calkin and H. S. Wilf, The number of independent sets in a grid graph, preprint, SIAM J. Discrete Math., 11(1), 54-60.
N. J. Calkin and H. S. Wilf, The number of independent sets in a grid graph, SIAM J. Discrete Math, 11 (1998) 54-60.
Reinhardt Euler, The Fibonacci Number of a Grid Graph and a New Class of Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.6.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Vertex Cover
Index entries for linear recurrences with constant coefficients, signature (2,6,0,-1).

Row 3 of A089934. Row sums of A371967.

Cf. A051737.

a051736 n = a051736_list !! (n-1)
a051736_list = 1 : 5 : 17 : 63 : zipWith (-) (map (* 2) $ drop 2 $
   zipWith (+) (map (* 3) a051736_list) (tail a051736_list)) a051736_list
-- Reinhard Zumkeller, Apr 02 2012

LinearRecurrence[{2, 6, 0, -1}, {1, 5, 17, 63}, 40] (* Harvey P. Dale, Mar 05 2013 *)
CoefficientList[Series[(1 + 3 x + x^2 - x^3)/(1 - 2 x - 6 x^2 + x^4), {x, 0, 20}], x] (* Eric W. Weisstein, Sep 21 2017 *)
Table[-RootSum[1 - 6 #1^2 - 2 #1^3 + #1^4 &, 263 #1^n - 657 #1^(n + 1) - 331 #1^(n + 2) + 81 #1^(n + 3) &]/1994, {n, 0, 20}] (* Eric W. Weisstein, Sep 21 2017 *)

Vec((1+3*x+x^2-x^3)/(1-2*x-6*x^2+x^4)+O(x^50)) \\ Michel Marcus, Sep 17 2014

a(n) = 2*a(n-1) + 6*a(n-2) - a(n-4).

G.f.: (1+x)*(1+2*x-x^2)/(1-2*x-6*x^2+x^4). - Philippe Deléham, Sep 07 2006

More terms from James Sellers, Dec 08 1999
More terms from Michel Marcus, Sep 17 2014
Offset fixed by Eric W. Weisstein, Sep 21 2017

A286847 Array read by antidiagonals: T(m,n) = number of minimal dominating sets in the grid graph P_m X P_n.

Original entry on oeis.org

1, 2, 2, 2, 6, 2, 4, 7, 7, 4, 4, 18, 16, 18, 4, 7, 39, 53, 53, 39, 7, 9, 75, 154, 306, 154, 75, 9, 13, 155, 436, 1167, 1167, 436, 155, 13, 18, 310, 1268, 4939, 6958, 4939, 1268, 310, 18, 25, 638, 3660, 21313, 40931, 40931, 21313, 3660, 638, 25

Offset: 1

Andrew Howroyd, Aug 01 2017

			Table begins:
===============================================================
m\n|  1   2    3     4       5        6         7          8
---|-----------------------------------------------------------
1  |  1   2    2     4       4        7         9         13...
2  |  2   6    7    18      39       75       155        310...
3  |  2   7   16    53     154      436      1268       3660...
4  |  4  18   53   306    1167     4939     21313      88161...
5  |  4  39  154  1167    6958    40931    254754    1519544...
6  |  7  75  436  4939   40931   349178   3118754   26797630...
7  |  9 155 1268 21313  254754  3118754  40307167  497709474...
8  | 13 310 3660 88161 1519544 26797630 497709474 8863408138...
...

Andrew Howroyd, Table of n, a(n) for n = 1..153
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Minimal Dominating Set

Rows 1-3 are A253412, A290379, A286848.
Main diagonal is A290382.
Cf. A218354 (dominating sets), A089934 (independent), A286868 (irredundant).
Cf. A286849 (king graph).

cp's OEIS Frontend

A089936 Number of 5 X n matrices with entries {0,1} without adjacent 0's in any row or column. 5th row of A089934.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A089937 Number of 6 X n matrices with entries {0,1} without adjacent 0's in any row or column. 6th row of A089934.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A089938 Number of 7 X n matrices with entries {0,1} without adjacent 0's in any row or column. 7th row of A089934.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A089935 a(n) = order of recurrence generating row (or column) n of A089934.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A006506 Number of n X n binary matrices with no 2 adjacent 1's, or number of configurations of non-attacking princes on an n X n board, where a "prince" attacks the four adjacent (non-diagonal) squares. Also number of independent vertex sets in an n X n grid.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A197054 T(n,k)=Number of nXk 0..4 arrays with each element equal to the number of its horizontal and vertical zero neighbors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A286513 Array read by antidiagonals: T(m,n) is the number of independent sets in the stacked prism graph C_m X P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A051736 Number of 3 X n (0,1)-matrices with no consecutive 1's in any row or column.

Views

Author

Keywords

Comments