A220054 Number A(n,k) of tilings of a k X n rectangle using right trominoes and 1 X 1 tiles; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 11, 11, 1, 1, 1, 1, 33, 39, 33, 1, 1, 1, 1, 87, 195, 195, 87, 1, 1, 1, 1, 241, 849, 2023, 849, 241, 1, 1, 1, 1, 655, 3895, 16839, 16839, 3895, 655, 1, 1, 1, 1, 1793, 17511, 151817, 249651, 151817, 17511, 1793, 1, 1

Offset: 0

Author

Alois P. Heinz, Dec 03 2012

Keywords

• nonn
• tabl

Examples

			A(2,2) = 5, because there are 5 tilings of a 2 X 2 rectangle using right trominoes and 1 X 1 tiles:
  ._._.   ._._.   .___.   .___.   ._._.
  |_|_|   | |_|   | ._|   |_. |   |_| |
  |_|_|   |___|   |_|_|   |_|_|   |___|
Square array A(n,k) begins:
  1,  1,   1,     1,       1,        1,          1,            1, ...
  1,  1,   1,     1,       1,        1,          1,            1, ...
  1,  1,   5,    11,      33,       87,        241,          655, ...
  1,  1,  11,    39,     195,      849,       3895,        17511, ...
  1,  1,  33,   195,    2023,    16839,     151817,      1328849, ...
  1,  1,  87,   849,   16839,   249651,    4134881,     65564239, ...
  1,  1, 241,  3895,  151817,  4134881,  128938297,   3814023955, ...
  1,  1, 655, 17511, 1328849, 65564239, 3814023955, 207866584389, ...
		

Links

• Liang Kai, Antidiagonals n = 0..35, flattened (antidiagonals n = 0..29 from Alois P. Heinz)
• Kai Liang, Solving tiling enumeration problems by tensor network contractions, arXiv:2503.17698 [math.CO], 2025. See p. 25, Table 4.
• Wikipedia, Tromino

Crossrefs

Columns (or rows) k=0+1, 2-10 give: A000012, A127864, A127867, A127870, A220055, A220056, A220057, A220058, A220059, A220060.

Main diagonal gives: A220061.

Programs

Maple

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

Mathematica

b[n_, l_] := b[n, l] = Module[{k, t}, Which[ Max[l] > n , 0, n == 0 || l == {} , 1 , Min[l] > 0 , t := Min[l]; b[n - t, l - t] , True, For[k = 1, True, k++, If[ l[[k]] == 0 , Break[] ] ]; b[n, ReplacePart[l, k -> 1]] + If[k > 1 && l[[k - 1]] == 1, b[n, ReplacePart[l, {k -> 2, k - 1 -> 2}]], 0] + If[k < Length[l] && l[[k + 1]] == 1, b[n, ReplacePart[l, {k -> 2, k + 1 -> 2}]], 0] + If[k < Length[l] && l[[k + 1]] == 0, b[n, ReplacePart[l, {k -> 1, k + 1 -> 2}]] + b[n, ReplacePart[l, {k -> 2, k + 1 -> 1}]] + b[n, ReplacePart[l, {k -> 2, k + 1 -> 2}]], 0] + If[k + 1 < Length[l] && l[[k + 1]] == 0 && l[[k + 2]] == 0, b[n, ReplacePart[l, {k -> 2, k + 1 -> 2, k + 2 -> 2}]], 0] ] ]; a[n_, k_] := If[n >= k, b[n, Array[0 &, k]], b[k, Array[0 &, n]]]; Table [Table [a[n, d - n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Dec 09 2013, translated from Maple *)