|
| |
|
|
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.
|
|
16
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
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
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
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 ...
a(2,2)=7:
11 11 11 10 10 01 01
11 10 01 11 01 11 10
|
|
|
PROG
|
(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
|
|
|
CROSSREFS
|
T(n, 0) = T(0, m) = 1. Zero based table is A089980.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
