A254414 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.

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, 32, 533, 2408, 2408, 533, 32, 1, 1, 64, 2293, 22873, 50128, 22873, 2293, 64, 1, 1, 128, 9866, 217969, 1064576, 1064576, 217969, 9866, 128, 1, 1, 256, 42451, 2078716, 22734496, 50796983, 22734496, 2078716, 42451, 256, 1

Offset: 0

Author

Alois P. Heinz, Jan 30 2015

Keywords

• nonn
• tabl

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

Examples

			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, ...
		

Links

• Liang Kai, Table of n, a(n) for n = 0..1377 (terms 0..495 from Andrew Howroyd)
• Wikipedia, Polyomino

Crossrefs

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

Main diagonal gives: A254127.

Cf. A005683.

Programs

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