A197054 -id:A197054 - 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

A217637 T(n,k)=Number of nXk arrays of the minimum value of corresponding elements and their horizontal and vertical neighbors in a random 0..1 nXk array.

Original entry on oeis.org

2, 2, 2, 4, 6, 4, 6, 16, 16, 6, 10, 38, 66, 38, 10, 16, 98, 244, 244, 98, 16, 26, 244, 968, 1418, 968, 244, 26, 42, 614, 3726, 8706, 8706, 3726, 614, 42, 68, 1542, 14520, 52120, 83074, 52120, 14520, 1542, 68, 110, 3872, 56352, 315378, 773348, 773348, 315378

Offset: 1

R. H. Hardin, Oct 09 2012

Number of maximal independent sets in the graph P_2 X P_n X P_k. - Andrew Howroyd, Jun 10 2017

			Table starts
...2.....2........4..........6...........10..............16................26
...2.....6.......16.........38...........98.............244...............614
...4....16.......66........244..........968............3726.............14520
...6....38......244.......1418.........8706...........52120............315378
..10....98......968.......8706........83074..........773348...........7272142
..16...244.....3726......52120.......773348........11181454.........163361868
..26...614....14520.....315378......7272142.......163361868........3709621842
..42..1542....56352....1900838.....68138974......2378097084.......83923710538
..68..3872...218978...11472148....639248556.....34661572702.....1901055652804
.110..9726...850620...69210290...5994907930....505010822224....43046530809006
.178.24426..3304624..417586442..56226693158...7358779655656...974841850791586
.288.61348.12837742.2519466108.527340415924.107224919634686.22075731493018104
...
Some solutions for n=3 k=4
..1..0..0..1....0..0..0..1....1..0..1..1....1..1..0..0....1..0..0..0
..0..0..0..0....0..0..1..1....0..0..0..1....0..0..1..0....1..1..0..0
..1..0..0..0....0..0..0..1....1..0..1..1....0..0..0..1....1..0..0..0

R. H. Hardin, Table of n, a(n) for n = 1..220
MacKenzie Carr, Christina M. Mynhardt, Ortrud R. Oellermann, Enumerating the Digitally Convex Sets of Powers of Cycles and Cartesian Products of Paths and Complete Graphs, arXiv:2008.02781 [math.CO], 2020.
R. Euler, P. Oleksik, Z. Skupien, Counting Maximal Distance-Independent Sets in Grid Graphs, Discussiones Mathematicae Graph Theory. Volume 33, Issue 3, Pages 531-557, ISSN (Print) 2083-5892, July 2013; see also.

Columns 1-3 are A006355(n+1), A217631, A217632.

Cf. A197054.

A197049 Number of n X 3 0..4 arrays with each element equal to the number its horizontal and vertical zero neighbors.

Original entry on oeis.org

1, 2, 4, 10, 18, 38, 78, 156, 320, 654, 1326, 2706, 5518, 11228, 22884, 46634, 94978, 193518, 394286, 803220, 1636448, 3334030, 6792334, 13838202, 28192958, 57437684, 117018884, 238404906, 485705682, 989536598, 2016000430, 4107230284, 8367729920, 17047719214

Offset: 0

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.

In other words, the number of maximal independent vertex sets (and minimal vertex covers) in the 3 X n grid graph. - Eric W. Weisstein, Aug 07 2017

			Some solutions for n=5:
  2  0  2    0  1  1    2  0  1    0  3  0    0  3  0    0  3  0    0  2  0
  0  4  0    1  2  0    0  2  1    3  0  2    2  0  2    2  0  3    1  1  1
  2  0  3    2  0  3    2  1  0    0  2  1    1  1  1    1  2  0    1  0  2
  1  2  0    0  4  0    0  2  1    1  2  0    0  3  0    0  2  1    1  2  0
  0  1  1    2  0  2    2  0  1    1  0  2    2  0  2    2  0  1    0  1  1

Alois P. Heinz, Table of n, a(n) for n = 0..2000 (terms n = 1..200 from R. H. Hardin)
George Spahn, Counting Maximal Seat Assignments that Obey Social Distancing, Talk at Rutgers Experimental Mathematics Seminar, Feb. 1, 2024. Addresses this sequence on slides 26-32, but under incorrect A-number A157049.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
Eric Weisstein's World of Mathematics, Minimal Vertex Cover
Index entries for linear recurrences with constant coefficients, signature (1,1,3,-1,-1).

Column 3 of A197054.

Empirical: a(n) = a(n-1) +a(n-2) +3*a(n-3) -a(n-4) -a(n-5) for n>6.
Equivalent g.f.: -(2*x^6-x^5+x^4-x^3-x^2-x-1)/(x^5+x^4-3*x^3-x^2-x+1). - R. J. Mathar, Oct 10 2011
Spahn (see link) provides a proof of the generating function. - Hugo Pfoertner, Apr 18 2024

a(0)=1 prepended by Alois P. Heinz, Apr 18 2024

A332347 Array read by antidiagonals: T(m,n) is the number of maximal independent sets in the m X n king graph.

Original entry on oeis.org

1, 2, 2, 2, 4, 2, 3, 6, 6, 3, 4, 12, 8, 12, 4, 5, 20, 22, 22, 20, 5, 7, 36, 40, 79, 40, 36, 7, 9, 64, 82, 194, 194, 82, 64, 9, 12, 112, 176, 537, 544, 537, 176, 112, 12, 16, 200, 340, 1519, 1882, 1882, 1519, 340, 200, 16, 21, 352, 722, 4011, 6490, 8197, 6490, 4011, 722, 352, 21

Offset: 1

Andrew Howroyd, Feb 10 2020

Also the number of minimal vertex covers in the m X n king graph.

			Array begins:
=====================================================
m\n | 1   2   3    4     5      6       7       8
----+------------------------------------------------
  1 | 1   2   2    3     4      5       7       9 ...
  2 | 2   4   6   12    20     36      64     112 ...
  3 | 2   6   8   22    40     82     176     340 ...
  4 | 3  12  22   79   194    537    1519    4011 ...
  5 | 4  20  40  194   544   1882    6490   20534 ...
  6 | 5  36  82  537  1882   8197   36301  144409 ...
  7 | 7  64 176 1519  6490  36301  201611 1009321 ...
  8 | 9 112 340 4011 20534 144409 1009321 6214593 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..496
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
Eric Weisstein's World of Mathematics, Minimal Vertex Cover

Rows 1..4 are A000931(n+6), A107383(n+2), A332348, A332349.
Main diagonal is A288956.
Cf. A197054 (grid graph), A218663 (dominating sets), A245013 (independent sets), A286849 (minimal dominating sets).

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

A197048 Number of n X n 0..4 arrays with each element equal to the number of its horizontal and vertical zero neighbors.

Original entry on oeis.org

1, 2, 10, 42, 358, 4468, 88056, 2745186, 134355866, 10264692132, 1234801357470, 232966546265096, 68939282741912248

Offset: 1

R. H. Hardin, Oct 09 2011

nonn

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_n. - Andrew Howroyd, May 16 2017

			Some solutions for n=4
..0..2..0..2....2..0..1..1....2..0..3..0....0..3..0..2....1..0..3..0
..1..1..2..0....0..3..1..0....0..4..0..2....3..0..3..0....1..2..0..3
..2..0..2..1....3..0..2..1....3..0..2..1....0..2..1..1....0..1..3..0
..0..3..0..1....0..3..0..1....0..2..1..0....1..1..0..1....1..1..0..2

Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set

Diagonal of A197054.

Cf. A006506 (independent vertex sets), A133515 (dominating sets).

A197054 = Cases[Import["https://oeis.org/A197054/b197054.txt", "Table"], {, }][[All, 2]];
a[n_] := A197054[[2 n^2 - 2 n + 1]];
Table[a[n], {n, 1, 13}] (* Jean-François Alcover, Sep 23 2019 *)

A197050 Number of nX4 0..4 arrays with each element equal to the number its horizontal and vertical zero neighbors.

Original entry on oeis.org

3, 6, 18, 42, 108, 274, 692, 1754, 4442, 11248, 28488, 72146, 182712, 462728, 1171876, 2967826, 7516146, 19034954, 48206826, 122085820, 309187486, 783030352, 1983057390, 5022176478, 12718873752, 32211084212, 81575929322, 206594481604

Offset: 1

R. H. Hardin, Oct 09 2011

nonn

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.

Column 4 of A197054.

			Some solutions for n=5
..0..2..1..0....2..0..3..0....0..3..0..2....2..0..3..0....0..3..0..1
..3..0..2..1....0..4..0..3....3..0..4..0....0..4..0..3....2..0..2..1
..0..4..0..2....2..0..4..0....0..4..0..2....3..0..3..0....1..1..2..0
..3..0..4..0....1..2..0..3....3..0..2..1....0..2..1..1....0..3..0..3
..0..3..0..2....0..1..2..0....0..2..1..0....1..1..0..1....2..0..3..0

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

Empirical: a(n) = a(n-1) +3*a(n-2) +3*a(n-3) -a(n-4) -2*a(n-5) -a(n-6) for n>7.

Equivalent empirical g.f.: 3*x - 2*x^2*(1+x)*(x^4+3*x^3-3*x-3) / ( 1-x-3*x^2-3*x^3+x^4+2*x^5+x^6 ). - R. J. Mathar, Oct 10 2011

A197051 Number of nX5 0..4 arrays with each element equal to the number its horizontal and vertical zero neighbors.

Original entry on oeis.org

4, 10, 38, 108, 358, 1132, 3580, 11382, 36270, 114992, 365628, 1162290, 3692624, 11733828, 37293892, 118504546, 376583590, 1196750110, 3803034578, 12085297922, 38405269512, 122045123484, 387837623386, 1232482503260, 3916616317912

Offset: 1

R. H. Hardin, Oct 09 2011

nonn

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.

Column 5 of A197054.

			Some solutions for n=4
..0..1..2..0..2....1..1..0..3..0....0..3..0..3..0....0..2..1..0..2
..2..1..0..4..0....0..2..2..0..3....3..0..3..0..2....2..0..2..2..0
..0..1..3..0..3....3..0..2..2..0....0..2..1..1..1....1..2..0..2..1
..1..1..0..3..0....0..3..0..1..1....1..1..0..2..0....0..1..2..0..1

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

Empirical: a(n) = a(n-1) +4*a(n-2) +10*a(n-3) +4*a(n-4) -20*a(n-5) +a(n-6) -2*a(n-7) +2*a(n-8) -16*a(n-9) +4*a(n-10) +a(n-13) for n>14.

Equivalent empirical g.f.: 4*x - 2*x^2*(5+14*x+15*x^2-x^3-39*x^4-8*x^5+6*x^6-21*x^7-13*x^8-x^9+x^10+3*x^11+3*x^12) / ( -1+x+4*x^2+10*x^3+4*x^4-20*x^5+x^6-2*x^7+2*x^8-16*x^9+4*x^10+x^13 ). - R. J. Mathar, Oct 10 2011

A197052 Number of nX6 0..4 arrays with each element equal to the number its horizontal and vertical zero neighbors.

Original entry on oeis.org

5, 16, 78, 274, 1132, 4468, 17742, 70616, 281202, 1117442, 4448148, 17693664, 70390082, 280040518, 1114106280, 4432207738, 17633023628, 70149839190, 279079644000, 1110273409628, 4417041071578, 17572471614384, 69909222737482

Offset: 1

R. H. Hardin Oct 09 2011

nonn

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

Column 6 of A197054

			Some solutions for n=4
..0..3..0..2..0..2....0..3..0..2..1..0....2..0..3..0..3..0....0..2..0..3..0..1
..2..0..2..1..2..0....2..0..4..0..2..1....0..4..0..3..0..3....1..1..2..0..2..1
..1..1..2..0..1..2....1..2..0..4..0..2....3..0..2..1..2..0....2..0..2..1..2..0
..0..2..0..2..1..0....0..1..2..0..3..0....0..2..1..0..1..1....0..3..0..2..0..2

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

Empirical: a(n) = 2*a(n-1) +7*a(n-2) +9*a(n-3) -15*a(n-4) -38*a(n-5) +45*a(n-6) -16*a(n-7) -91*a(n-9) +117*a(n-10) -63*a(n-11) +52*a(n-12) -19*a(n-13) +5*a(n-14) +8*a(n-15) -10*a(n-16) +4*a(n-17) -4*a(n-18) for n>19

A231884 Number of maximal 2-independent sets in the 3-dimensional (2, 2, n) grid graph.

Original entry on oeis.org

0, 4, 4, 20, 32, 80, 180, 408, 940, 2072, 4824, 10792, 24660, 55748, 126760, 287584, 652280, 1481184, 3359900, 7627296, 17305472, 39277688, 89131928, 202276640, 459045772, 1041743020, 2364140452, 5365103100, 12175556108, 27630957644, 62705400664, 142302685268

Offset: 0

N. J. A. Sloane, Nov 17 2013

Andrew Howroyd, Table of n, a(n) for n = 0..200
R. Euler, P. Oleksik, Z. Skupien, Counting Maximal Distance-Independent Sets in Grid Graphs, Discussiones Mathematicae Graph Theory. Volume 33, Issue 3, Pages 531-557, ISSN (Print) 2083-5892, July 2013; see also.
Index entries for linear recurrences with constant coefficients, signature (0,3,4,4,0,-9,-3).

Cf. A197054, A231886, A231887, A231888, A217631, A217632.

Join[{0}, LinearRecurrence[{0, 3, 4, 4, 0, -9, -3}, {4, 4, 20, 32, 80, 180, 408}, 31]] (* Jean-François Alcover, Nov 01 2017 *)

concat(0, Vec(4*x*(1 + x)*(1 + 2*x^2 - x^3 - 2*x^4 - x^5) / (1 - 3*x^2 - 4*x^3 - 4*x^4 + 9*x^6 + 3*x^7) + O(x^40))) \\ Colin Barker, Oct 04 2017

Euler et al. give an explicit g.f. and recurrence.
From Colin Barker, Oct 04 2017: (Start)
G.f.: 4*x*(1 + x)*(1 + 2*x^2 - x^3 - 2*x^4 - x^5) / (1 - 3*x^2 - 4*x^3 - 4*x^4 + 9*x^6 + 3*x^7).
a(n) = 3*a(n-2) + 4*a(n-3) + 4*a(n-4) - 9*a(n-6) - 3*a(n-7) for n>7.
(End)

Terms a(11) and beyond from Andrew Howroyd, Jun 10 2017

A231887 Number of maximal 2-independent sets in the 3-dimensional (3, 3, n) grid graph.

Original entry on oeis.org

0, 11, 46, 182, 1026, 4836, 23922, 118674, 584516, 2889306, 14266546, 70455052, 347980122, 1718525298, 8487343508, 41916544250, 207013446378, 1022380190332, 5049238367202, 24936725579450, 123155267567884, 608228181611074, 3003862808227186, 14835208208589988

Offset: 0

N. J. A. Sloane, Nov 17 2013

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..100
R. Euler, P. Oleksik, Z. Skupien, Counting Maximal Distance-Independent Sets in Grid Graphs, Discussiones Mathematicae Graph Theory. Volume 33, Issue 3, Pages 531-557, ISSN (Print) 2083-5892, July 2013; see also.

Cf. A197054, A231884, A231886, A231888, A217631, A217632.

Terms a(13) and beyond from Andrew Howroyd, Jun 10 2017

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

A217637 T(n,k)=Number of nXk arrays of the minimum value of corresponding elements and their horizontal and vertical neighbors in a random 0..1 nXk array.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A197049 Number of n X 3 0..4 arrays with each element equal to the number its horizontal and vertical zero neighbors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A332347 Array read by antidiagonals: T(m,n) is the number of maximal independent sets in the m X n king graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A197048 Number of n X n 0..4 arrays with each element equal to the number of its horizontal and vertical zero neighbors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A197050 Number of nX4 0..4 arrays with each element equal to the number its horizontal and vertical zero neighbors.

Views

Author

Keywords

Comments

Examples

Links

Formula

A197051 Number of nX5 0..4 arrays with each element equal to the number its horizontal and vertical zero neighbors.

Views

Author

Keywords

Comments

Examples

Links

Formula

A197052 Number of nX6 0..4 arrays with each element equal to the number its horizontal and vertical zero neighbors.

Views

Author

Keywords

Comments

Examples

Links

Formula

A231884 Number of maximal 2-independent sets in the 3-dimensional (2, 2, n) grid graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica