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

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

A089939 T(i,j) = 1 if F(i) AND F(j) = 0, otherwise 0, where F is A003714 and AND is the bitwise logical-and operation. Table read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1

Offset: 0

Marc LeBrun, Nov 15 2003

Encodes which row/column patterns may be adjacent in 01-matrices where no two 0 elements may be adjacent. Contains many interesting recursive patterns such as Fibonacci-sized blocks of 0's along main diagonal.

			T(3,4) = 0 because F(3) AND F(4) = 4 AND 5 = 1, which is nonzero.

Cf. A003714 (Fibbinary), A005614 (row or column 1).
Cf. A000045, A047999.
Cf. A001333, A051736, A051737, A089934, A089935, A089936, A089937, A089938.

Name clarified by Jon E. Schoenfield, Aug 19 2022

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

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

A089939 T(i,j) = 1 if F(i) AND F(j) = 0, otherwise 0, where F is A003714 and AND is the bitwise logical-and operation. Table read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions