%I #16 Dec 28 2019 17:04:03
%S 2,3,3,5,7,5,8,17,17,8,13,41,63,41,13,21,99,227,227,99,21,34,239,827,
%T 1234,827,239,34,55,577,2999,6743,6743,2999,577,55,89,1393,10897,
%U 36787,55447,36787,10897,1393,89,144,3363,39561,200798,454385,454385,200798
%N Table T(n,k) of the number of n X k matrices on {0,1} without adjacent 0's in any row or column.
%C Recurrence orders are A089935. n X 1/1 X n patterns interpreted as binary values is A003714.
%C Number of independent vertex sets in the P_n X P_k grid graph. - _Andrew Howroyd_, Jun 06 2017
%C All columns (or rows) are linear recurrences with constant coefficients and order of the recurrence <= A001224(k+1). - _Andrew Howroyd_, Dec 24 2019
%H Andrew Howroyd, <a href="/A089934/b089934.txt">Table of n, a(n) for n = 1..1225</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependentVertexSet.html">Independent Vertex Set</a>
%e Table starts:
%e ========================================================
%e n\k| 1 2 3 4 5 6 7
%e ---|----------------------------------------------------
%e 1 | 2 3 5 8 13 21 34 ...
%e 2 | 3 7 17 41 99 239 577 ...
%e 3 | 5 17 63 227 827 2999 10897 ...
%e 4 | 8 41 227 1234 6743 36787 200798 ...
%e 5 | 13 99 827 6743 55447 454385 3729091 ...
%e 6 | 21 239 2999 36787 454385 5598861 69050253 ...
%e 7 | 34 577 10897 200798 3729091 69050253 1280128950 ...
%e ... - _Andrew Howroyd_, Jun 06 2017
%e a(2,2)=7:
%e 11 11 11 10 10 01 01
%e 11 10 01 11 01 11 10
%o (PARI)
%o step(v, S)={vector(#v, i, sum(j=1, #v, v[j]*!bitand(S[i], S[j])))}
%o mkS(k)={select(b->!bitand(b,b>>1), [0..2^k-1])}
%o 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
%Y T(n, 0) = T(0, m) = 1. Zero based table is A089980.
%Y Rows 1-7 are A000045, A001333, A051736, A051737, A089936, A089937, A089938.
%Y Main diagonal is A006506.
%Y Cf. A089935, A001224, A197054 (maximal independent sets), A218354, A003714.
%K nonn,tabl
%O 1,1
%A _Marc LeBrun_, Nov 15 2003