A322494 - OEIS

%I #20 Dec 18 2018 16:52:25

%S 1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,3,3,1,1,1,1,5,8,5,1,1,1,1,8,18,18,

%T 8,1,1,1,1,13,44,68,44,13,1,1,1,1,21,107,233,233,107,21,1,1,1,1,34,

%U 257,838,1262,838,257,34,1,1,1,1,55,621,2989,6523,6523,2989,621,55,1,1

%N Number A(n,k) of tilings of a k X n rectangle using V (2m+1)-ominoes (m >= 0) in standard orientation; square array A(n,k), n>=0, k>=0, read by antidiagonals.

%C The shapes of the tiles are:

%C                        ._.

%C               ._.      | |

%C        ._.    | |      | |

%C   ._.  | |_.  | |_._.  | |_._._.

%C   |_|  |___|  |_____|  |_______|  ... .

%C .

%C The sequence of column k (or row k) satisfies a linear recurrence with constant coefficients of order 2^(k-1) for k>0.

%H Alois P. Heinz, <a href="/A322494/b322494.txt">Antidiagonals n = 0..23, flattened</a>

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

%e A(3,3) = 8:

%e   ._____.  ._____.  ._____.  ._____.  ._____.  ._____.  ._____.  ._____.

%e   |_|_|_|  | |_|_|  |_|_|_|  |_| |_|  |_|_|_|  |_| |_|  | |_|_|  | | |_|

%e   |_|_|_|  |___|_|  | |_|_|  |_|___|  |_| |_|  | |___|  | |_|_|  | |___|

%e   |_|_|_|  |_|_|_|  |___|_|  |_|_|_|  |_|___|  |___|_|  |_____|  |_____|.

%e .

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

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

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

%e   1, 1,  2,   3,     5,      8,      13,       21,        34, ...

%e   1, 1,  3,   8,    18,     44,     107,      257,       621, ...

%e   1, 1,  5,  18,    68,    233,     838,     2989,     10687, ...

%e   1, 1,  8,  44,   233,   1262,    6523,    34468,    181615, ...

%e   1, 1, 13, 107,   838,   6523,   51420,   396500,   3086898, ...

%e   1, 1, 21, 257,  2989,  34468,  396500,  4577274,  52338705, ...

%e   1, 1, 34, 621, 10687, 181615, 3086898, 52338705, 888837716, ...

%p b:= proc(n, l) option remember; local k, m, r;

%p       if n=0 or l=[] then 1

%p     elif min(l)>0 then (t-> b(n-t, map(h->h-t, l)))(min(l))

%p     elif l[-1]=n then b(n, subsop(-1=[][], l))

%p     else for k while l[k]>0 do od; r:= 0;

%p          for m from 0 while k+m<=nops(l) and l[k+m]=0 and n>m do

%p            r:= r+b(n, [l[1..k-1][], 1$m, m+1, l[k+m+1..nops(l)][]])

%p          od; r

%p       fi

%p     end:

%p A:= (n, k)-> b(max(n, k), [0$min(n, k)]):

%p seq(seq(A(n, d-n), n=0..d), d=0..14);

%t b[n_, l_] := b[n, l] = Module[{k, m, r}, Which[n == 0 || l == {}, 1, Min[l] > 0, Function[t, b[n-t, l-t]][Min[l]], l[[-1]] == n, b[n, ReplacePart[ l, -1 -> Nothing]], True, For[k=1, l[[k]] > 0, k++]; r = 0; For[m=0, k+m <= Length[l] && l[[k+m]] == 0 && n>m, m++, r = r + b[n, Join[l[[1 ;; k-1]], Array[1&, m], {m+1}, l[[k+m+1 ;; Length[l]]]]]]; r]];

%t A[n_, k_] := b[Max[n, k], Array[0&, Min[n, k]]];

%t Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* _Jean-François Alcover_, Dec 18 2018, after _Alois P. Heinz_ *)

%Y Columns (or rows) k=0+1,2-10 give: A000012, A000045(n+1), A322496, A322497, A322498, A322499, A322500, A322501, A322502, A322503.

%Y Main diagonal gives A322495.

%Y Cf. A226444.

%K nonn,tabl

%O 0,13

%A _Alois P. Heinz_, Dec 12 2018