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

Links

Alois P. Heinz, Antidiagonals n = 0..29, flattened

Wikipedia, Tromino

Example

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

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<nops(l) and l[k+1]=1, b(n, subsop(k=2, k+1=2, l)), 0)+
         `if`(k<nops(l) and l[k+1]=0, b(n, subsop(k=1, k+1=2, l))+
            b(n, subsop(k=2, k+1=1, l))+ b(n, subsop(k=2, k+1=2, l)), 0)+
         `if`(k+1<nops(l) and l[k+1]=0 and l[k+2]=0,
            b(n, subsop(k=2, k+1=2, k+2=2, l)), 0)
      fi
    end:
A:= (n, 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 *)

Crossrefs

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

Main diagonal gives: A220061.

Sequence in context: A094635 A358347 A367989 * A263152 A075463 A026518

Adjacent sequences: A220051 A220052 A220053 * A220055 A220056 A220057

Keyword

nonn,tabl

Author

Alois P. Heinz, Dec 03 2012

Status

approved