login
Table T(n,k) of the number of n X k matrices on {0,1} without adjacent 0's in any row or column.
16

%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