|
%I #40 Jul 26 2023 19:41:47
%S 1,1,1,1,0,1,1,1,1,1,1,0,2,0,1,1,1,5,5,1,1,1,0,11,8,11,0,1,1,1,24,55,
%T 55,24,1,1,1,0,53,140,380,140,53,0,1,1,1,117,633,2319,2319,633,117,1,
%U 1,1,0,258,1984,15171,21272,15171,1984,258,0,1
%N Number A(n,k) of tilings of a k X n rectangle using dominoes and right trominoes; square array A(n,k), n>=0, k>=0, read by antidiagonals.
%H Alois P. Heinz, <a href="/A219987/b219987.txt">Antidiagonals n = 0..31, flattened</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Domino_(mathematics)">Domino</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Tromino">Tromino</a>
%e A(3,3) = 8, because there are 8 tilings of a 3 X 3 rectangle using dominoes and right trominoes:
%e .___._. .___._. .___._. .___._.
%e |___| | |___| | |___| | |_. | |
%e | ._|_| | | |_| | |___| | |_|_|
%e |_|___| |_|___| |_|___| |_|___|
%e ._.___. ._.___. ._.___. ._.___.
%e | |___| | | ._| | |___| | |___|
%e |___| | |_|_| | |_|_. | |_| | |
%e |___|_| |___|_| |___|_| |___|_|
%e Square array A(n,k) begins:
%e 1, 1, 1, 1, 1, 1, 1, 1, ...
%e 1, 0, 1, 0, 1, 0, 1, 0, ...
%e 1, 1, 2, 5, 11, 24, 53, 117, ...
%e 1, 0, 5, 8, 55, 140, 633, 1984, ...
%e 1, 1, 11, 55, 380, 2319, 15171, 96139, ...
%e 1, 0, 24, 140, 2319, 21272, 262191, 2746048, ...
%e 1, 1, 53, 633, 15171, 262191, 5350806, 100578811, ...
%e 1, 0, 117, 1984, 96139, 2746048, 100578811, 3238675344, ...
%p b:= proc(n, l) option remember; local k, t;
%p if max(l[])>n then 0 elif n=0 or l=[] then 1
%p elif min(l[])>0 then t:=min(l[]); b(n-t, map(h->h-t, l))
%p else for k do if l[k]=0 then break fi od;
%p b(n, subsop(k=2, l))+
%p `if`(k>1 and l[k-1]=1, b(n, subsop(k=2, k-1=2, l)), 0)+
%p `if`(k<nops(l) and l[k+1]=1, b(n, subsop(k=2, k+1=2, l)), 0)+
%p `if`(k<nops(l) and l[k+1]=0, b(n, subsop(k=1, k+1=1, l))+
%p b(n, subsop(k=1, k+1=2, l))+b(n, subsop(k=2, k+1=1, l)), 0)+
%p `if`(k+1<nops(l) and l[k+1]=0 and l[k+2]=0,
%p b(n, subsop(k=2, k+1=2, k+2=2, l))+
%p b(n, subsop(k=2, k+1=2, k+2=1, l)), 0)
%p fi
%p end:
%p A:= (n, k)-> `if`(n>=k, b(n, [0$k]), b(k, [0$n])):
%p seq(seq(A(n, d-n), n=0..d), d=0..14);
%t 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 *)
%o (Sage)
%o from sage.combinat.tiling import TilingSolver, Polyomino
%o def A(n,k):
%o p = Polyomino([(0,0), (0,1)])
%o q = Polyomino([(0,0), (0,1), (1,0)])
%o T = TilingSolver([p,q], box=[n,k], reusable=True, reflection=True)
%o return T.number_of_solutions()
%o # _Ralf Stephan_, May 21 2014
%Y Columns (or rows) k=0-10 give: A000012, A059841, A052980, A165716, A165791, A219988, A219989, A219990, A219991, A219992, A219993.
%Y Main diagonal gives: A219994.
%Y Cf. A219866, A364457.
%K nonn,tabl
%O 0,13
%A _Alois P. Heinz_, Dec 02 2012
|
