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

Author

Marc LeBrun, Nov 15 2003

Keywords

• nonn
• tabl

Comments

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

Examples

			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
		

Links

• 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

Crossrefs

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.

Programs

PARI

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