A364457 - OEIS

%I #47 Aug 28 2023 08:22:04

%S 1,1,1,1,0,1,1,1,1,1,1,1,2,1,1,1,1,6,6,1,1,1,2,17,30,17,2,1,1,2,43,

%T 145,145,43,2,1,1,3,108,733,1294,733,108,3,1,1,4,280,3540,12109,12109,

%U 3540,280,4,1,1,5,727,17300,110017,215905,110017,17300,727,5,1

%N Number A(n,k) of tilings of a k X n rectangle using dominoes and trominoes (of any shape); square array A(n,k), n>=0, k>=0, read by antidiagonals.

%H Alois P. Heinz, <a href="/A364457/b364457.txt">Antidiagonals n = 0..25, flattened</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Domino_(mathematics)">Domino (mathematics)</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Tromino">Tromino</a>

%F A(n,k) = A(k,n).

%e A(3,2) = A(2,3) = 6:

%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,     1,       1,        2,          2,            3, ...

%e   1, 1,   2,     6,      17,       43,        108,          280, ...

%e   1, 1,   6,    30,     145,      733,       3540,        17300, ...

%e   1, 1,  17,   145,    1294,    12109,     110017,      1014847, ...

%e   1, 2,  43,   733,   12109,   215905,    3710880,     64589501, ...

%e   1, 2, 108,  3540,  110017,  3710880,  118624712,   3899306587, ...

%e   1, 3, 280, 17300, 1014847, 64589501, 3899306587, 239677657279, ...

%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; 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          `if`(k+1<nops(l) and l[k+1]=0 and l[k+2]=0, b(n, subsop(k=1,

%p               k+1=1, k+2=1, l)), 0)+b(n, subsop(k=3, l))

%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..12);

%t b[n_, l_] := b[n, l] = Module[{k, t, RP = ReplacePart}, 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, RP[l, k -> 2]] + If[k > 1 && l[[k - 1]] == 1, b[n, RP[l, {k -> 2, k - 1 -> 2}]], 0] + If[k < Length[l] && l[[k + 1]] == 1, b[n, RP[l, {k -> 2, k + 1 -> 2}]], 0] + If[k < Length[l] && l[[k + 1]] == 0, b[n, RP[l, {k -> 1, k + 1 -> 1}]] + b[n, RP[l, {k -> 1, k + 1 -> 2}]] + b[n, RP[l, {k -> 2, k + 1 -> 1}]], 0] + If[k + 1 < Length[l] && l[[k + 1]] == 0 && l[[k + 2]] == 0, b[n, RP[l, {k -> 2, k + 1 -> 2, k + 2 -> 2}]] + b[n, RP[l, {k -> 2, k + 1 -> 2, k + 2 -> 1}]], 0] + If[k + 1 < Length[l] && l[[k + 1]] == 0 && l[[k + 2]] == 0, b[n, RP[l, {k -> 1, k + 1 -> 1, k + 2 -> 1}]], 0] + b[n, RP[l, k -> 3]]]];

%t A[n_, k_] := If[n >= k, b[n, Table[0, {k}]], b[k, Table[0, {n}]]];

%t Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 12}] // Flatten (* _Jean-François Alcover_, Aug 28 2023, after _Alois P. Heinz_ *)

%Y Columns (or rows) k=0-10 give: A000012, A182097(n) = A000931(n+3), A019439, A364460, A364155, A364556, A364616, A364617, A364632, A364638, A364640.

%Y Main diagonal gives A364504.

%Y Cf. A219866, A219987, A233320.

%K nonn,tabl

%O 0,13

%A _Alois P. Heinz_, Jul 25 2023