OFFSET
0,8
COMMENTS
A polyomino of shape I is a rectangle of width 1.
All columns (or rows) are linear recurrences with constant coefficients. An upper bound on the order of the recurrence is A005683(k+2). This upper bound is exact for at least 1 <= k <= 10. - Andrew Howroyd, Dec 23 2019
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..495
Wikipedia, Polyomino
EXAMPLE
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, ...
1, 1, 2, 4, 8, 16, 32, ...
1, 2, 7, 29, 124, 533, 2293, ...
1, 4, 29, 257, 2408, 22873, 217969, ...
1, 8, 124, 2408, 50128, 1064576, 22734496, ...
1, 16, 533, 22873, 1064576, 50796983, 2441987149, ...
1, 32, 2293, 217969, 22734496, 2441987149, 264719566561, ...
PROG
(PARI)
step(v, S)={vector(#v, i, sum(j=1, #v, v[j]*2^hammingweight(bitand(S[i], S[j]))))}
mkS(k)={apply(b->bitand(b, 2*b+1), [2^(k-1)..2^k-1])}
T(n, k)={if(k<2, if(k==0||n==0, 1, 2^(n-1)), my(S=mkS(k), v=vector(#S, i, i==1)); for(n=1, n, v=step(v, S)); vecsum(v))} \\ Andrew Howroyd, Dec 23 2019
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Jan 30 2015
STATUS
approved