OFFSET
0,13
LINKS
EXAMPLE
A(3,3) = 8, because there are 8 tilings of a 3 X 3 rectangle using dominoes and right trominoes:
.___._. .___._. .___._. .___._.
|___| | |___| | |___| | |_. | |
| ._|_| | | |_| | |___| | |_|_|
|_|___| |_|___| |_|___| |_|___|
._.___. ._.___. ._.___. ._.___.
| |___| | | ._| | |___| | |___|
|___| | |_|_| | |_|_. | |_| | |
|___|_| |___|_| |___|_| |___|_|
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, 1, ...
1, 0, 1, 0, 1, 0, 1, 0, ...
1, 1, 2, 5, 11, 24, 53, 117, ...
1, 0, 5, 8, 55, 140, 633, 1984, ...
1, 1, 11, 55, 380, 2319, 15171, 96139, ...
1, 0, 24, 140, 2319, 21272, 262191, 2746048, ...
1, 1, 53, 633, 15171, 262191, 5350806, 100578811, ...
1, 0, 117, 1984, 96139, 2746048, 100578811, 3238675344, ...
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=2, 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=1, l))+
b(n, subsop(k=1, k+1=2, l))+b(n, subsop(k=2, k+1=1, 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))+
b(n, subsop(k=2, k+1=2, k+2=1, 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}, If[Max[l] > n, 0, If[n == 0 || l == {}, 1, If[Min[l] > 0, t = Min[l]; b[n-t, l-t], For[k = 1, True, k++, If[l[[k]] == 0, Break[]]]; b[n, ReplacePart[l, k -> 2]] + 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 -> 1}]] + b[n, ReplacePart[l, {k -> 1, k+1 -> 2}]] + b[n, ReplacePart[l, {k -> 2, k+1 -> 1}]], 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}]] + b[n, ReplacePart[l, {k -> 2, k+1 -> 2, 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 05 2013, translated from Alois P. Heinz's Maple program *)
PROG
(Sage)
from sage.combinat.tiling import TilingSolver, Polyomino
def A(n, k):
p = Polyomino([(0, 0), (0, 1)])
q = Polyomino([(0, 0), (0, 1), (1, 0)])
T = TilingSolver([p, q], box=[n, k], reusable=True, reflection=True)
return T.number_of_solutions()
# Ralf Stephan, May 21 2014
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Dec 02 2012
STATUS
approved