A218354 -id:A218354 - cp's OEIS frontend

A089934 Table T(n,k) of the number of n X k matrices on {0,1} without adjacent 0's in any row or column.

2, 3, 3, 5, 7, 5, 8, 17, 17, 8, 13, 41, 63, 41, 13, 21, 99, 227, 227, 99, 21, 34, 239, 827, 1234, 827, 239, 34, 55, 577, 2999, 6743, 6743, 2999, 577, 55, 89, 1393, 10897, 36787, 55447, 36787, 10897, 1393, 89, 144, 3363, 39561, 200798, 454385, 454385, 200798

Offset: 1

Marc LeBrun, Nov 15 2003

Recurrence orders are A089935. n X 1/1 X n patterns interpreted as binary values is A003714.
Number of independent vertex sets in the P_n X P_k grid graph. - Andrew Howroyd, Jun 06 2017
All columns (or rows) are linear recurrences with constant coefficients and order of the recurrence <= A001224(k+1). - Andrew Howroyd, Dec 24 2019
The enumeration of tiling "W-shaped" polyominoes in a (n+1) X (k+1) rectangle, whose shapes are (no flipping or rotating allowed):
   .. .._.   ...     ...
   || ||_| .||_|   .||_|
       ||   ||_|   .||_|
             ||     ||_|
                     ||       ... - _Liang Kai, Apr 19 2025

			Table starts:
  ========================================================
  n\k|  1   2     3      4       5        6          7
  ---|----------------------------------------------------
  1  |  2   3     5      8      13       21         34 ...
  2  |  3   7    17     41      99      239        577 ...
  3  |  5  17    63    227     827     2999      10897 ...
  4  |  8  41   227   1234    6743    36787     200798 ...
  5  | 13  99   827   6743   55447   454385    3729091 ...
  6  | 21 239  2999  36787  454385  5598861   69050253 ...
  7  | 34 577 10897 200798 3729091 69050253 1280128950 ...
  ... - _Andrew Howroyd_, Jun 06 2017
a(2,2)=7:
  11 11 11 10 10 01 01
  11 10 01 11 01 11 10

Liang Kai, Antidiagonals n = 1..77, flattened (antidiagonals n = 1..49 from Alois P. Heinz)
Kai Liang, Independent Set Enumeration and Estimation of Related Constants of Grid Graphs, arXiv:2507.04007 [math.CO], 2025. See p. 4.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Independent Vertex Set

T(n, 0) = T(0, m) = 1. Zero based table is A089980.
Rows 1-7 are A000045, A001333, A051736, A051737, A089936, A089937, A089938.
Main diagonal is A006506.
Cf. A089935, A001224, A197054 (maximal independent sets), A218354, A003714.

step(v, S)={vector(#v, i, sum(j=1, #v, v[j]*!bitand(S[i], S[j])))}
mkS(k)={select(b->!bitand(b,b>>1), [0..2^k-1])}
T(n,k)={my(S=mkS(k), v=vector(#S, i, i==1)); for(n=1, n, v=step(v,S)); vecsum(v)} \\ Andrew Howroyd, Dec 24 2019

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

A218663 T(n,k) = Hilltop maps: number of n X k binary arrays indicating the locations of corresponding elements not exceeded by any king-move neighbor in a random 0..1 n X k array.

Original entry on oeis.org

1, 3, 3, 5, 15, 5, 9, 57, 57, 9, 17, 225, 417, 225, 17, 31, 891, 3249, 3249, 891, 31, 57, 3519, 25533, 50625, 25533, 3519, 57, 105, 13905, 199489, 793881, 793881, 199489, 13905, 105, 193, 54945, 1560161, 12383361, 24879489, 12383361, 1560161, 54945

Offset: 1

R. H. Hardin, Nov 04 2012

From Andrew Howroyd, May 10 2017: (Start)
Number of n X k binary matrices with every 1 adjacent to some 0 horizontally, vertically, diagonally or antidiagonally.
Number of dominating sets in the n X k king graph. (End)

			Table starts
....1........3...........5...............9.................17
....3.......15..........57.............225................891
....5.......57.........417............3249..............25533
....9......225........3249...........50625.............793881
...17......891.......25533..........793881...........24879489
...31.....3519......199489........12383361..........775176415
...57....13905.....1560161.......193349025........24176619049
..105....54945....12202673......3018953025.......754066017977
..193...217107....95434773.....47135449449.....23517838102321
..355...857871...746388537....735942652641....733484062428443
..653..3389769..5837454753..11490533873361..22876204302519509
.1201.13394241.45654295713.179405691966081.713472099034206097
...
Some solutions for n=3 k=4
..1..1..1..0....1..0..1..1....0..1..0..1....0..1..1..0....1..0..0..0
..0..1..0..0....0..0..0..0....1..0..0..1....0..0..1..1....0..0..1..1
..0..1..0..1....1..1..0..1....0..1..1..1....1..1..0..1....1..1..0..0

Stephan Mertens, Table of n, a(n) for n = 1..946 (first 240 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.
Wikipedia, Dominating set

Columns 1-7 are A000213(n+1), A218657, A218658, A218659, A218660, A218661, A218662.
Diagonal is A133791.
Cf. A218354, A221446, A219078, A218426.

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) +3*a(n-2) +3*a(n-3)
k=3: a(n) = 6*a(n-1) +11*a(n-2) +26*a(n-3) -5*a(n-4) -5*a(n-6)
k=4: a(n) = 12*a(n-1) +45*a(n-2) +180*a(n-3) -27*a(n-4) -81*a(n-6)
Columns k=1..z+1 for an underlying 0..z array: a(n) = sum(i=1..2z+1){(2^k-1)*a(n-i)} checked for z=1..3.

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

Original entry on oeis.org

1, 11, 291, 28661, 10982565, 16031828359, 89373230342147, 1904212088591018521, 155026375803222057878889, 48225130114674924906540348115, 57322477811272486520770053115140403, 260351257812272076026660518356378279922077

Offset: 1

R. H. Hardin, Dec 24 2007

nonn

Number of dominating sets in the grid graph P_n X P_n. - Andrew Howroyd, May 10 2017

Stephan Mertens, Table of n, a(n) for n = 1..24 (first 15 terms from ZhaoYang Liang)
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, Dominating Set
Eric Weisstein's World of Mathematics, Grid Graph
Wikipedia, Dominating set

Main diagonal of A218354.

a(12) from Andrew Howroyd, May 10 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).

A286912 Array read by antidiagonals: T(m,n) = number of edge covers in the grid graph P_m X P_n.

Original entry on oeis.org

0, 1, 1, 1, 7, 1, 2, 43, 43, 2, 3, 277, 969, 277, 3, 5, 1777, 23663, 23663, 1777, 5, 8, 11407, 571099, 2180738, 571099, 11407, 8, 13, 73219, 13807469, 198906617, 198906617, 13807469, 73219, 13, 21, 469981, 333735575, 18169793971, 68534828391, 18169793971, 333735575, 469981, 21

Offset: 1

Andrew Howroyd, May 15 2017

			Table starts:
======================================================================
m\n| 1     2        3           4              5                 6
---|------------------------------------------------------------------
1  | 0     1        1           2              3                 5 ...
2  | 1     7       43         277           1777             11407 ...
3  | 1    43      969       23663         571099          13807469 ...
4  | 2   277    23663     2180738      198906617       18169793971 ...
5  | 3  1777   571099   198906617    68534828391    23650967140325 ...
6  | 5 11407 13807469 18169793971 23650967140325 30833670159649637 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..276
Eric Weisstein's World of Mathematics, Edge Cover
Eric Weisstein's World of Mathematics, Grid Graph

Rows 1-3 are A000045(n-1), A286911, A288031.
Main diagonal is A286913.
Cf. A210662, A099390, A089934, A218354.

T(1,1) corrected by Andrew Howroyd, Jun 04 2017

A350820 Array read by antidiagonals: T(m,n) is the number of minimum dominating sets in the grid graph P_m X P_n.

Original entry on oeis.org

1, 2, 2, 1, 6, 1, 4, 3, 3, 4, 3, 12, 10, 12, 3, 1, 2, 29, 29, 2, 1, 8, 17, 1, 2, 1, 17, 8, 4, 2, 2, 52, 52, 2, 2, 4, 1, 20, 11, 92, 22, 92, 11, 20, 1, 13, 2, 46, 2, 13, 13, 2, 46, 2, 13, 5, 24, 1, 4, 3, 288, 3, 4, 1, 24, 5, 1, 2, 3, 324, 344, 34, 34, 344, 324, 3, 2, 1

Offset: 1

Andrew Howroyd, Jan 17 2022

The domination number of the grid graphs is tabulated in A350823.

			Table begins:
===================================
m\n | 1  2  3  4   5   6  7   8
----+------------------------------
  1 | 1  2  1  4   3   1  8   4 ...
  2 | 2  6  3 12   2  17  2  20 ...
  3 | 1  3 10 29   1   2 11  46 ...
  4 | 4 12 29  2  52  92  2   4 ...
  5 | 3  2  1 52  22  13  3 344 ...
  6 | 1 17  2 92  13 288 34   2 ...
  7 | 8  2 11  2   3  34  2  34 ...
  8 | 4 20 46  4 344   2 34  52 ...
  ...

Stephan Mertens, Table of n, a(n) for n = 1..946 (first 276 terms from Andrew Howroyd)
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, Minimum Dominating Set

Rows 1..4 are A347633, A347558, A350821, A350822.
Main diagonal is A347632.
Cf. A218354 (dominating sets), A286847 (minimal dominating sets), A303293, A350815, A350823.

T(m,n) = T(n,m).

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

Original entry on oeis.org

1, 3, 3, 4, 9, 4, 4, 24, 24, 4, 4, 56, 129, 56, 4, 4, 136, 613, 613, 136, 4, 4, 328, 2997, 5617, 2997, 328, 4, 4, 792, 14713, 52955, 52955, 14713, 792, 4, 4, 1912, 72169, 502521, 964755, 502521, 72169, 1912, 4, 4, 4616, 353853, 4763717, 17625829, 17625829, 4763717, 353853, 4616, 4

Offset: 1

Andrew Howroyd, Sep 04 2017

			Array begins:
===============================================================
m\n| 1   2     3       4         5           6             7
---|-----------------------------------------------------------
1  | 1   3     4       4         4           4             4...
2  | 3   9    24      56       136         328           792...
3  | 4  24   129     613      2997       14713         72169...
4  | 4  56   613    5617     52955      502521       4763717...
5  | 4 136  2997   52955    964755    17625829     321381919...
6  | 4 328 14713  502521  17625829   617429805   21550989109...
7  | 4 792 72169 4763717 321381919 21550989109 1436456861467...
...

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

Row 2 is A291706.
Main diagonal is A287690.
Cf. A218354 (dominating), A287151 (connected).
Cf. A291873 (king).

A286514 Array read by antidiagonals: T(m,n) = number of dominating sets in the stacked prism graph C_m X P_n.

Original entry on oeis.org

1, 3, 3, 5, 11, 7, 9, 41, 51, 11, 17, 149, 383, 183, 21, 31, 547, 2865, 2629, 663, 39, 57, 2007, 21449, 38437, 18635, 2435, 71, 105, 7361, 160579, 561743, 531669, 133709, 8935, 131, 193, 27001, 1202181, 8207075, 15179657, 7455797, 956009, 32775, 241

Offset: 1

Andrew Howroyd, May 10 2017

			Table starts:
===========================================================
m\n|  1    2      3         4           5             6
---|-------------------------------------------------------
1  |  1    3      5         9          17            31 ...
2  |  3   11     41       149         547          2007 ...
3  |  7   51    383      2865       21449        160579 ...
4  | 11  183   2629     38437      561743       8207075 ...
5  | 21  663  18635    531669    15179657     433200191 ...
6  | 39 2435 133709   7455797   416118655   23213149395 ...
7  | 71 8935 956009 104209625 11369806353 1239821606103 ...
...

Stephan Mertens, Table of n, a(n) for n = 1..325 (first 91 terms from Andrew Howroyd)
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, Dominating Set
Eric Weisstein's World of Mathematics, Stacked Prism Graph
Wikipedia, Dominating set

Column 2 is A284702.
Row 3 is A285880.
Main diagonal is A286914.
Cf. A286513, A218354 (P_n X P_n).

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

Original entry on oeis.org

0, 1, 1, 3, 9, 3, 4, 25, 25, 4, 5, 81, 161, 81, 5, 9, 289, 961, 961, 289, 9, 16, 961, 6235, 11236, 6235, 961, 16, 25, 3249, 39601, 137641, 137641, 39601, 3249, 25, 39, 11025, 251433, 1677025, 3270375, 1677025, 251433, 11025, 39

Offset: 1

Andrew Howroyd, Apr 18 2018

Equivalently, the number of n X m binary matrices with every element adjacent to some 0 horizontally or vertically.

			Table begins:
=======================================================================
m\n|  1    2      3        4          5            6              7
---|-------------------------------------------------------------------
1  |  0    1      3        4          5            9             16 ...
2  |  1    9     25       81        289          961           3249 ...
3  |  3   25    161      961       6235        39601         251433 ...
4  |  4   81    961    11236     137641      1677025       20430400 ...
5  |  5  289   6235   137641    3270375     76405081     1783064069 ...
6  |  9  961  39601  1677025   76405081   3416753209   152598828321 ...
7  | 16 3249 251433 20430400 1783064069 152598828321 13057656650476 ...
...

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

Rows 1..2 are A195971(n-1), A141583(n+1).
Main diagonal is A133793.
Cf. A218354 (dominating sets), A291872 (connected dominating sets).
Cf. A303114 (king graph), A303118 (minimal total dominating sets).

cp's OEIS Frontend

A089934 Table T(n,k) of the number of n X k matrices on {0,1} without adjacent 0's in any row or column.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

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

A218663 T(n,k) = Hilltop maps: number of n X k binary arrays indicating the locations of corresponding elements not exceeded by any king-move neighbor in a random 0..1 n X k array.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

A286912 Array read by antidiagonals: T(m,n) = number of edge covers in the grid graph P_m X P_n.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A350820 Array read by antidiagonals: T(m,n) is the number of minimum dominating sets in the grid graph P_m X P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

A286514 Array read by antidiagonals: T(m,n) = number of dominating sets in the stacked prism graph C_m X P_n.

Views

Author

Keywords

Examples

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples