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

1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 1, 1, 2, 3, 3, 2, 1, 1, 1, 0, 2, 4, 3, 4, 2, 0, 1, 1, 0, 3, 8, 8, 8, 8, 3, 0, 1, 1, 1, 4, 13, 21, 28, 21, 13, 4, 1, 1, 1, 0, 5, 19, 31, 65, 65, 31, 19, 5, 0, 1, 1, 0, 7, 35, 70, 170, 267, 170, 70, 35, 7, 0, 1

Offset: 0

Author

Alois P. Heinz, Dec 02 2012

Keywords

• nonn
• tabl

Examples

			A(4,4) = 3, because there are 3 tilings of a 4 X 4 rectangle using straight (3 X 1) trominoes and 2 X 2 tiles:
  ._._____.  ._____._.  ._._._._.
  | |_____|  |_____| |  | . | . |
  | | . | |  | | . | |  |___|___|
  |_|___| |  | |___|_|  | . | . |
  |_____|_|  |_|_____|  |___|___| .
Square array A(n,k) begins:
  1,  1,  1,  1,  1,   1,    1,     1,     1, ...
  1,  0,  0,  1,  0,   0,    1,     0,     0, ...
  1,  0,  1,  1,  1,   2,    2,     3,     4, ...
  1,  1,  1,  2,  3,   4,    8,    13,    19, ...
  1,  0,  1,  3,  3,   8,   21,    31,    70, ...
  1,  0,  2,  4,  8,  28,   65,   170,   456, ...
  1,  1,  2,  8, 21,  65,  267,   804,  2530, ...
  1,  0,  3, 13, 31, 170,  804,  2744, 12343, ...
  1,  0,  4, 19, 70, 456, 2530, 12343, 66653, ...
		

Links

• Liang Kai, Antidiagonals n = 0..35, flattened (Antidiagonals 0..27 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-10 give: A000012, A079978, A000931(n+3), A219968, A202536, A219969, A219970, A219971, A219972, A219973, A219974.

Main diagonal gives: A219975.

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=3, l))+
         `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}, If [Max[l] > n, 0, If[n == 0 || l == {}, 1, If[ Min[l] > 0 ,t = Min[l]; b[n-t, l-t], k = Position[l, 0, 1][[1, 1]]; b[n, ReplacePart[l, k -> 3]] + If[k < Length[l] && l[[k+1]] == 0, 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 -> 1, k+1 -> 1, k+2 -> 1}]], 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 16 2013, translated from Maple *)