login
Number A(n,k) of tilings of a k X n rectangle using polyominoes of shape I; square array A(n,k), n>=0, k>=0, read by antidiagonals.
10

%I #24 Dec 28 2019 17:04:09

%S 1,1,1,1,1,1,1,2,2,1,1,4,7,4,1,1,8,29,29,8,1,1,16,124,257,124,16,1,1,

%T 32,533,2408,2408,533,32,1,1,64,2293,22873,50128,22873,2293,64,1,1,

%U 128,9866,217969,1064576,1064576,217969,9866,128,1,1,256,42451,2078716,22734496,50796983,22734496,2078716,42451,256,1

%N Number A(n,k) of tilings of a k X n rectangle using polyominoes of shape I; square array A(n,k), n>=0, k>=0, read by antidiagonals.

%C A polyomino of shape I is a rectangle of width 1.

%C 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

%H Andrew Howroyd, <a href="/A254414/b254414.txt">Table of n, a(n) for n = 0..495</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Polyomino">Polyomino</a>

%e Square array A(n,k) begins:

%e 1, 1, 1, 1, 1, 1, 1, ...

%e 1, 1, 2, 4, 8, 16, 32, ...

%e 1, 2, 7, 29, 124, 533, 2293, ...

%e 1, 4, 29, 257, 2408, 22873, 217969, ...

%e 1, 8, 124, 2408, 50128, 1064576, 22734496, ...

%e 1, 16, 533, 22873, 1064576, 50796983, 2441987149, ...

%e 1, 32, 2293, 217969, 22734496, 2441987149, 264719566561, ...

%o (PARI)

%o step(v,S)={vector(#v, i, sum(j=1, #v, v[j]*2^hammingweight(bitand(S[i], S[j]))))}

%o mkS(k)={apply(b->bitand(b,2*b+1), [2^(k-1)..2^k-1])}

%o 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

%Y Columns (or rows) k=0-7 give: A000012, A011782, A052961, A254124, A254125, A254126, A254458, A254607.

%Y Main diagonal gives: A254127.

%Y Cf. A005683.

%K nonn,tabl

%O 0,8

%A _Alois P. Heinz_, Jan 30 2015