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

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

Original entry on oeis.org

1, 8, 41, 227, 1234, 6743, 36787, 200798, 1095851, 5980913, 32641916, 178150221, 972290957, 5306478436, 28961194501, 158061670175, 862654025422, 4708111537971, 25695485730239, 140238391149386, 765379824048327, 4177217595760125, 22798023012345528, 124424893212114297

Offset: 0

Stephen G Penrice, Dec 06 1999

Colin Barker, Table of n, a(n) for n = 0..1000
N. J. Calkin and H. S. Wilf, The number of independent sets in a grid graph, preprint.
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.
Y. Kong, General recurrence theory of ligand binding on a three-dimensional lattice, J. Chem. Phys. Vol. 111 (1999), pp. 4790-4799 (set omega = 1 in Eq. (48)).
Index entries for linear recurrences with constant coefficients, signature (4,9,-5,-4,1).

Row 4 of A089934.

Cf. A051736.

LinearRecurrence[{4, 9, -5, -4, 1}, {1, 8, 41, 227, 1234}, 24] (* Jean-François Alcover, Nov 05 2017 *)

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

From Yong Kong (ykong(AT)curagen.com), Dec 24 2000: (Start)
a(n) = 4*a(n - 1) + 9*a(n - 2) - 5*a(n - 3) - 4*a(n - 4) + a(n - 5);
G.f.: (1 + 4*x - 4*x^3 + x^4)/(1 - 4*x - 9*x^2 + 5*x^3 + 4*x^4 - x^5). (End)
a(n) = 2*a(n - 1) + 18*a(n - 2) + 9*a(n - 3) - 23*a(n - 4) - 2*a(n - 5) + 6*a(n - 6) - a(n - 7).

More terms from James Sellers, Dec 08 1999

More terms from Michel Marcus, Sep 17 2014

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

Original entry on oeis.org

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

A371967 Irregular triangle T(r,w) read by rows: number of ways of placing w non-attacking wazirs on a 3 X r board.

Original entry on oeis.org

1, 1, 3, 1, 1, 6, 8, 2, 1, 9, 24, 22, 6, 1, 1, 12, 49, 84, 61, 18, 2, 1, 15, 83, 215, 276, 174, 53, 9, 1, 1, 18, 126, 442, 840, 880, 504, 158, 28, 2, 1, 21, 178, 792, 2023, 3063, 2763, 1478, 472, 93, 12, 1, 1, 24, 239, 1292, 4176, 8406, 10692, 8604, 4374, 1416, 297, 38, 2, 1, 27, 309

Offset: 0

R. J. Mathar, Apr 14 2024

			The triangle starts with r>=0 rows and w>=0 wazirs as
  1 ;
  1 3 1 ;
  1 6 8 2  ;
  1 9 24 22 6 1 ;
  1 12 49 84 61 18 2  ;
  1 15 83 215 276 174 53 9 1 ;
  1 18 126 442 840 880 504 158 28 2  ;
  1 21 178 792 2023 3063 2763 1478 472 93 12 1 ;
  1 24 239 1292 4176 8406 10692 8604 4374 1416 297 38 2  ;
  1 27 309 1969 7731 19591 32716 36257 26674 13035 4264 945 142 15 1 ;
  ...

Alois P. Heinz, Rows r = 0..165 (first 17 rows from R. J. Mathar)
R. J. Mathar, Bivariate Generating Functions for Non-attacking Wazirs on Rectangular Boards
Jacob A. Siehler, Selections without adjacency on a rectangular grid, arXiv:1409.3869 [math.CO] (2014) Table 2.
Wikipedia, Wazir (chess)

Cf. A051736 (row sums), A035607 (on 2Xr board), A011973 (on 1Xr board), A232833 (on rXr board).
T(n,n) gives A371978.
Row maxima give A371979.
Cf. A007494.

b:= proc(n, l) option remember; `if`(n=0, 1,
      add(`if`(Bits[And](j, l)>0, 0, expand(b(n-1, j)*
      x^add(i, i=Bits[Split](j)))), j=[0, 1, 2, 4, 5]))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..10);  # Alois P. Heinz, Apr 14 2024

b[n_, l_] := b[n, l] = If[n == 0, 1, Sum[If[BitAnd[j, l] > 0, 0, Expand[b[n - 1, j]*x^DigitCount[j, 2, 1]]], {j, {0, 1, 2, 4, 5}}]];
T[n_] := CoefficientList[b[n, 0], x];
Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Jun 05 2024, after Alois P. Heinz *)

T(r,0) = 1.
T(r,1) = 3*r.
T(r,2) = A064225(r-1).
T(r,3) = A172229(r).
T(r,4) = 27*r^4/8 -117*r^3/4 +829*r^2/8 -715*r/4 +126. [Siehler Table 3]
T(3,w) = A232833(3,w).
G.f.: (1+x*y) *(1 +x*y +x*y^2 -x^2*y^3)/(1 -x -x*y -x^2*y^3 -2*x^2*y -3*x^2*y^2 -x^3*y^2 +x^3*y^4 +x^4*y^4). - R. J. Mathar, Apr 21 2024

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

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

A371967 Irregular triangle T(r,w) read by rows: number of ways of placing w non-attacking wazirs on a 3 X r board.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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