login
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.
11
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
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
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Dec 03 2012
STATUS
approved