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

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, 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, 257, 838, 1262, 838, 257, 34, 1, 1, 1, 1, 55, 621, 2989, 6523, 6523, 2989, 621, 55, 1, 1

Offset: 0

Author

Alois P. Heinz, Dec 12 2018

Keywords

• nonn
• tabl

Comments

The shapes of the tiles are:

._.

._. | |

._. | | | |

.. | |. | |.. | |.._.

|| |__| |___| |_____| ... .

.

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

Examples

			A(3,3) = 8:
  ._____.  ._____.  ._____.  ._____.  ._____.  ._____.  ._____.  ._____.
  |_|_|_|  | |_|_|  |_|_|_|  |_| |_|  |_|_|_|  |_| |_|  | |_|_|  | | |_|
  |_|_|_|  |___|_|  | |_|_|  |_|___|  |_| |_|  | |___|  | |_|_|  | |___|
  |_|_|_|  |_|_|_|  |___|_|  |_|_|_|  |_|___|  |___|_|  |_____|  |_____|.
.
Square array A(n,k) begins:
  1, 1,  1,   1,     1,      1,       1,        1,         1, ...
  1, 1,  1,   1,     1,      1,       1,        1,         1, ...
  1, 1,  2,   3,     5,      8,      13,       21,        34, ...
  1, 1,  3,   8,    18,     44,     107,      257,       621, ...
  1, 1,  5,  18,    68,    233,     838,     2989,     10687, ...
  1, 1,  8,  44,   233,   1262,    6523,    34468,    181615, ...
  1, 1, 13, 107,   838,   6523,   51420,   396500,   3086898, ...
  1, 1, 21, 257,  2989,  34468,  396500,  4577274,  52338705, ...
  1, 1, 34, 621, 10687, 181615, 3086898, 52338705, 888837716, ...
		

Links

• Alois P. Heinz, Antidiagonals n = 0..23, flattened
• Wikipedia, Polyomino

Crossrefs

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

Main diagonal gives A322495.

Cf. A226444.

Programs

Maple

b:= proc(n, l) option remember; local k, m, r;
      if n=0 or l=[] then 1
    elif min(l)>0 then (t-> b(n-t, map(h->h-t, l)))(min(l))
    elif l[-1]=n then b(n, subsop(-1=[][], l))
    else for k while l[k]>0 do od; r:= 0;
         for m from 0 while k+m<=nops(l) and l[k+m]=0 and n>m do
           r:= r+b(n, [l[1..k-1][], 1$m, m+1, l[k+m+1..nops(l)][]])
         od; r
      fi
    end:
A:= (n, k)-> b(max(n, k), [0$min(n, k)]):
seq(seq(A(n, d-n), n=0..d), d=0..14);

Mathematica

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]];
A[n_, k_] := b[Max[n, k], Array[0&, Min[n, k]]];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Dec 18 2018, after Alois P. Heinz *)